Encyclopedia
Please note this is an old version of this entry, which may differ significantly from the current revision.
The application of artificial intelligence in everyday life is becoming all-pervasive and unavoidable. Within that vast field, a special place belongs to biomimetic/bio-inspired algorithms for multiparameter optimization, which find their use in a large number of areas. Novel methods and advances are being published at an accelerated pace.
- bio-inspired computation
- multiparameter optimization
- metaheuristic algorithms
- genetic algorithms
- artificial intelligence
- deep learning
1. Introduction
Nowadays, we are witnessing an enormous popularity and a literal avalanche of bio-inspired algorithms [1] permeating practically all facets of life. Procedures using artificial intelligence (AI) [2] are being built into a vast number of different systems that include Internet search engines [3], cloud computing systems [4], Internet of Things [5], autonomous (self-driving) vehicles [6], AI chips in flagship smartphones [7], expert medical systems [8], robots [9], agriculture [10], architectural designs [11] and data mining [12], to quote just a tiny fragment. AI can chat with humans and even solve problems stated in the common human language [13], generate paintings and other artworks at a textual prompt [14], create music [15], translate between different languages [16], play very complex games and win them [17], etc. AI artworks have been winning art competitions (and creating controversies at that) [15]. Questions are even posed as to whether AI can show its own creativity comparable to that of humans [18]. Many AI functionalities are met in ordinary life, and we may not even recognize them. All of the mentioned applications and many more are exponentially multiplying, becoming more powerful and more spectacular. The possibilities, at least currently, appear endless. Concerns have been raised for possible dangers for humanity as a whole with using AI, and some legislations have already brought laws limiting the allowed performances and uses of artificial intelligence [19].
Not all results in the field of biomimetic computing are so spectacularly in the spotlight and followed by hype as those that mimic human behavior or even our creativity. However, maybe the most important achievements are hidden among the results that do not belong to this group. They include handling big data, performing time analysis or performing multi-criteria optimization. Such intelligent algorithms that are mostly “invisible” to the eyes of the general public are causing a silent revolution not only in engineering, physics, chemistry, medicine, healthcare and life sciences, but also in economics, finance, business, cybersecurity, language processing and many more fields.
Bio-inspired optimization algorithms are extremely versatile and convenient for complex optimization problems. The result of such wide applicability is their overwhelming presence in diverse fields—there are practically no areas of human interest where they do not appear. As an illustration of their ubiquity, this section mentions just some selected fields where their applications have been reported. They encompass various branches of engineering, including mechanical engineering (automotive [20,21], aerospace [22], fluid dynamics [23], thermal engineering [24], automation [25], robotics [26], mechatronics [27], MEMS [28,29], etc.), electrical engineering [30] (including power engineering [31], electronics [32], microelectronics [33] and nanoelectronics [33], control engineering [34], renewable energy [35], biomedical engineering [36], telecommunications [36], signal processing [37]), geometrical optics [38], photonics [39], nanophotonics and nanoplasmonics [40], image processing [41] including pattern recognition [42], computing [30], [43], networking (computer networks [44] including Internet and Intranet [45], social networks [46], networks on a chip [47], optical networks [48], cellular (mobile) networks [49], wireless sensor networks [50], Internet of things [51], etc.), data clustering and mining [52], civil engineering [53,54], architectural design [55], urban engineering [56], smart cities [57], traffic control and engineering [58], biomedicine and healthcare [59,60], pharmacy [61,62], bioinformatics [63], genomics [64], computational biology [60], environmental pollution control [65] and computational chemistry [66]. Other optimization fields where biomimetic algorithms find application include transportation and logistics [67], industrial production [68], manufacturing including production planning, supply chains, resource allocation and management [69], food production and processing [70], agriculture [71], financial markets [72] including stock market prediction [73], as well as cryptocurrencies and blockchain technology [74], and even such seemingly unlikely fields as language processing and sentiment analysis [75]. The cited applications are just a tip of an iceberg, and there is a vast number of other uses not even mentioned here.
2. A Possible Taxonomy of Bio-Inspired Algorithms
This section presents one possible hierarchical classification of bio-inspired algorithms. The consideration has been made without taking into account any specific targeted applications of the algorithms. Generally, taxonomies of bio-inspired algorithms are relatively rarely considered in the literature. The majority of papers simply skip the topic altogether or handle it casually, presenting only the methods that are of immediate interest to the subject of the paper or, even more often, giving only a partial and non-systematic picture and denoting it as a classification. This is not to say that exhaustive and systematic papers on the subject do not exist. However, it appears that no consensus has been reached about the taxonomy of at least some bio-inspired algorithms yet.
A problem when attempting to define a categorization in this field is that some approaches, although having different names, actually present algorithms very similar or even basically identical to those previously published. Often they offer only incremental advances, such as somewhat better results at benchmarks of precision or computing speed. This is a very slippery ground, however, since according to the previously mentioned No Free Lunch Theorem [76], no algorithm is convenient for all purposes, and while one of them may offer a fast and accurate solution to one class of optimization problems, there is no guarantee that it will not perform drastically worse with other problems, become stuck in a local optimum, never even reaching a global optimum, or even fail completely to give a meaningful solution. For this reason, it is very difficult to decide which procedures merit inclusion in the classification and which do not.
A number of benchmarks have been proposed to compare different optimization procedures, and the most recent publications in the field use them to prove the qualities and advantages of their proposals over the competing ones. A systematic review of methods to compare the performance of different algorithms has been published by Beiranvand, Hare and Lucet [81]. A more recent consideration of that kind dedicated to metaheuristics has been presented by Halim, Ismail and Das [82], who offered an exhaustive and systematic review of measures for determining the efficiency and the effectiveness of optimization algorithms. A benchmarking process for five global approaches for nanooptics optimization has been described by Scheider et al. [83].
One can find various taxonomy proposals in the literature, each with its own merits and disadvantages. Figure 2 represents the scheme of a possible classification of bio-inspired optimization methods.
Figure 2. Possible classification of bio-inspired optimization methods.
3. Heuristics
Heuristics can be briefly described as problem solving through approximate algorithms. The word stems from the Ancient Greek εὑρίσκω (meaning “to discover”). It includes approaches that do not mandatorily result in an optimum solution and are actually imperfect, yet are adequate for attaining a “workable” solution, i.e., a sufficiently good one that will probably be useful and accurate enough for a majority of cases. On the other hand, they may not work in certain cases, or may consistently introduce systematic errors in others. The methods used include pragmatic trade-offs, rules of thumb (use of approximations based on prior knowledge in similar situations), a trial and error approach, the process of elimination, guesswork (“educated guesses”) and acceptable/satisfactory approximations. The main benefit is that heuristic approaches usually have vastly lower computational cost, and their main deficiencies are that they are usually dependent on a particular problem (i.e., not generally applicable in all situations) and their accuracy may be quite low in certain cases, while inherently they do not offer a way to estimate that accuracy.
Heuristic approaches include common heuristic algorithms, metaheuristic algorithms and hyper-heuristic algorithms. All of these approaches are considered to represent the foundations of AI.
“Basic” Heuristic Algorithms
The heuristic algorithms represent the oldest approximate approach to optimization problems, from which metaheuristics and hyper-heuristics evolved. They include a number of approximate goal attainment methods. While there is no universally accepted taxonomy of common heuristic algorithms, a possible classification is presented in Table 1. Metaheuristic and hyper-heuristic algorithms are not included in this subsection, since these are covered separately in the next two sections. This is a short overview only, presented for the sake of generality, since the quoted algorithms are mostly unrelated to bio-inspired methods. The comprehensiveness of the table is not claimed, and some quoted methods may overlap more or less, thus appearing in multiple categories at the same time.
Table 1. Selected heuristic algorithms, excluding metaheuristics or hyper-heuristics.
| Algorithm Name | The Main Properties of the Algorithm | Ref. |
|---|---|---|
| Divide and Conquer Algorithm | The problem is decomposed into smaller, manageable sub-problems that are first independently solved in an approximate manner and then merged into the final solution. | [84] |
| Hill Climbing | The algorithm explores the neighboring solutions and picks those with the best properties, so that the algorithm constantly “climbs” toward them. | [85] |
| Greedy Algorithms | Immediate local improvements are prioritized without taking into account the effect on global optimization. The underlying assumption is that such “greedy” choices will result in an acceptable approximation. | [86] |
| Approximation Algorithms | Solutions are searched for within provable limits around the optimal solution. The aim is to achieve the maximum efficiency. This is convenient for difficult nondeterministic polynomial time problems. | [87] |
| Local Search Algorithms | An initial solution is assumed, and it is iteratively improved by exploring the immediate vicinity and making small local modifications. No completely new solutions are constructed. | [88] |
| Constructive Algorithms | Solutions are built part-by-part from an empty set by adding one building block at a time. The procedure is iterative and uses heuristics for the choice of the building blocks. | [89] |
| Constraint Satisfaction Algorithms | A set of constraints is defined at the beginning. The solution space is then searched locally, each time applying the constraints until all of them are satisfied. | [90] |
| Branch And Bound Algorithm | The solution space is systematically divided into smaller sub-problems, the search space is bounded according to problem-specific criteria, and branches that result in suboptimal solutions are pruned and removed. | [91] |
| Cutting Plane Algorithm | An optimization method solving linear programming problems. It finds the optimal solution by iteratively adding new, additional constraints (cutting planes), thus gradually tightening the region of possible solutions and converging towards the optimum. | [92] |
| Iterative Improvement Algorithms | Here the goal is to iteratively improve an initially proposed problem solution. Thus, systematic adjustments and improvements are made to the initial set by targeting the predefined objectives. The values may be reordered, retuned or swapped until the desired optimization is complete. | [93] |
4. Metaheuristics
Metaheuristics is easily the most important approach to biomimetic optimization. The algorithms belonging to this group are the most numerous. Metaheuristics represent a conceptual generalization and enhancement of the heuristic approach. While the literature usually does not appear to provide a clear and consistent definition of metaheuristics and there seems not to be a consensus about it, it does offer various descriptions, among which is that metaheuristic algorithms represent iterative global optimization methods that make use of some underlying heuristics by making an intelligent combination of various higher-level strategies for exploring the search space, seeking to avoid local optima and to find an approximate solution for the global optimum [94,95]. The mentioned approaches are typically inspired by natural phenomena and mimic them. These phenomena may be for instance animal or human collective behavior, physiological processes or plant properties, but they also include some non-biological processes such as physical, astrophysical or chemical phenomena and mathematical procedures [96] (these non-biomimetic algorithms are not covered by this entry).
The methods in metaheuristics are sometimes denoted as metaphor-based since their naming and design are more or less inspired by actual biological and other processes. The metaheuristics are the best known, most popular and by far most often applied among the heuristic methods, and the papers dealing with them are the most numerous group of publications on nature-based optimization algorithms.
Many new procedures that belong to this group are constantly being proposed, almost on a daily basis. A paper by Ma et al. [97] presented an exhaustive list of more than 500 metaphor-based metaheuristic algorithms and their benchmark basis. While many of the proposed methods simply represent reiteration or sometimes even literal renaming of known methods, some newly described approaches do show relevance and usability and introduce new levels of sophistication and performance. As mentioned before in this text, the existing tsunami of metaphor-based algorithms has been heavily criticized by some researchers, who have been arguing that the approach is fundamentally flawed and that a new taxonomy should be introduced since it would expose the essential similarity among many of the newly proposed methods [98].
Swarm intelligence (SI) algorithms (mostly based on the collective behavior of animals) are by far the largest of the metaheuristic procedures and biomimetic computation approaches generally. They encompass the largest part of bio-inspired algorithms, amounting to about 67.12% of all of them. The article [80] calculates that about 49% of all nature-based methods belong to this class; however, if we do not take into account those of non-biological origin, a simple recalculation brings us to a percentage of more than 67%.
As an illustration and a direction for further reading, Table 2 presents some selected metaheuristic algorithms. It does not include basic heuristic algorithms, nor hyper-heuristic. The metaheuristic algorithms are divided into several main subgroups.
Table 2. Selected metaheuristic algorithms, excluding simple heuristics or hyper-heuristics
| Algorithm Group | Algorithm name | abbr. | Ref. |
| Evolutionary Algorithms | Genetic algorithm | GA | [99] |
| Memetic Algorithm | MA | [100] | |
| Differential Evolution | DE | [101] | |
| Swarm Intelligence Algorithms | Particle Swarm Optimization | PSO | [104] |
| Whale Optimization Algorithm | WOA | [105] | |
| Gray Wolf Optimizer | GWO | [106] | |
| Artificial Bee Colony Algorithm | ABCA | [107] | |
| Ant Colony Optimization | ACO | [108] | |
| Artificial Fish Swarm Algorithm | AFSA | [109] | |
| Firefly Algorithm | FA | [110] | |
| Fruit Fly Optimization Algorithm | FFOA | [111] | |
| Cuckoo Search Algorithm | CS | [112] | |
| Bat Algorithm | BA | [113] | |
| Bacterial Foraging | BFA | [114] | |
| Social Spider Optimization | SSO | [115] | |
| Locust Search Algorithm | LS | [116] | |
| Symbiotic Organisms Search | SOS | [117] | |
| Moth-flame Optimization | MFOA | [118] | |
| Honey Badger Algorithm | HBA | [119] | |
| Elephant Herding Optimization | EHO | [120] | |
| Grasshopper Algorithm | GOA | [121] | |
| Harris Hawks Optimization | HHO | [122] | |
| Orca Predation Algorithm | OPA | [123] | |
| Starling Murmuration Optimizer | SMO | [124] | |
| Serval Optimization Algorithm | SOA | [125] | |
| Coral Reefs Optimization Algorithm | CROA | [126] | |
| Krill Herd Algorithm | KH | [127] | |
| Gazelle optimization algorithm | GOA | [128] | |
| Algorithms Mimicking human or zoological physiological functions | Artificial Immune Systems | AIS | [142] |
| Neural Network Algorithm | NNA | [143] | |
| Human mental search | HMS | [144] | |
| Anthropological algorithms (Mimicking human social behavior) | Imperialist Competitive Algorithm | ICA | [148] |
| Anarchic Society Optimization | ASO | [149] | |
| Teaching-Learning Base Optimizat. | TLBO | [150] | |
| Society and civilization optimization | SC | [151] | |
| League Championship algorithm | LCA | [152] | |
| Volleyball Premier League algorithm | VPL | [153] | |
| Duelist algorithm | DA | [154] | |
| Tabu search | TS | [155] | |
| Human urbanization algorithm | HUA | [156] | |
| Political Optimizer | PO | [157] | |
| Plant-Based Algorithms | Flower Pollination Algorithm | FPA | [159] |
| Invasive Weed Optimization | IWO | [160] | |
| Plant Propagation Algorithm | PPA | [161] | |
| Plant Growth Optimization | PGO | [162] | |
| Tree Seed Algorithm | TSA | [163] | |
| Paddy Field Algorithm | PFA | [164] |
5. Hyper-Heuristics
The hyper-heuristic algorithms [169] were first introduced as “heuristics to choose heuristics”, i.e., an approach to automate the selection or design (generation) of metaheuristic algorithms to be able to solve the most difficult optimization problems. The term was coined by Cawling, Kendall and Soubeiga in 2000 [170]. Hyper-heuristics may be a learning method or a search procedure. They use conventional heuristics or metaheuristics as their “base” and explore them, seeking strategies to combine them, select the most convenient ones among them or generate the optimal ones. Thus, a hyper-heuristic algorithm operates in the search space of heuristics/metaheuristics, in contrast to ordinary heuristics/metaheuristics which operate in the search space of an optimization problem. Its goal is to reach a generality instead of targeting a specific problem space. The goal of hyper-heuristic algorithms is to find effective strategies through a high-level approach that are adaptable to a range of different problems and problem domains. Regardless of the methodology used, one can implement them as iterative procedures, where a sequence of lower-level algorithms keeps reiterating, all the time attempting to improve the solution(s) from the previous step. Reinforcement learning techniques [171,172] can be also utilized to automatically learn and improve the hyper-heuristic procedure.
A possible workflow for hyper-heuristics includes the initialization step where a set of base heuristics or their constitutive parts is selected or generated, followed by an iterative exploration of the search space of possible heuristics/metaheuristics or their parts, adapting or refining the available heuristics or generating new ones. The final step is the performance evaluation of the obtained solutions in the meta-search space and, in dependence on its results, arrival at the termination criteria.
6. Hybridization Methods
One of the relatively often used approaches in bio-inspired optimization is the hybridization of two or more different techniques, each with its own advantages and disadvantages, in order to boost their advantages and to lessen or even cancel disadvantages. In order to belong to the main topic of this survey, at least one of them should be biomimetic. Hybrid approaches make use of the complementary strengths of the combined methods. In this way, the solution quality and accuracy are enhanced, and the efficiency and robustness of the resulting strategies are improved over their constitutive blocks. In this way, an effective and flexible and effective method to solve complex optimization problems is obtained. The choice of hybridization type will be dependent on the particular problem, as well as the required optimization objectives.
The subject of hybrid metaheuristics is almost a separate science field in itself. For an excellent overview of its methods, taxonomy and approaches, see [174]. Figure 25 shows a possible classification of the hybridization methods, based on the mentioned reference by Raidl, but somewhat modified. The classification is by no means exhaustive, and it could be extended to include more methods.
Figure 25. Metaheuristic hybridization method classification according to [174], but somewhat modified and extended.
7. Multi-Objective Optimization (MOO)
The vast majority of the algorithms presented so far in this text are single-objective algorithms, meaning that they have a single objective function, their solution space is unimodal (with a single optimal solution or a global optimum) and their algorithms tend to be simpler and computationally less demanding. However, many practical problems come with more than one objective function that should be optimized at the same time, typically with conflicting requests. The approach dedicated to their solving is multi-objective optimization or multi-criteria optimization. Other names found in the literature for this method are vector optimization, Pareto optimization and multi-attribute optimization.
Contrary to single-objective algorithms, MOO algorithms have two or more conflicting/competing objectives, and there are multiple objective functions that have to be simultaneously optimized. Their solution space is either non-unimodal or multimodal. Since multi-objective optimization considers multiple objectives simultaneously, instead of finding an optimal or near-optimal solution as in optimization related to a single-objective function, it rather aims to find a set of solutions that achieve a trade-off between these objectives. The set of solutions that represent the best possible trade-offs among the conflicting objectives is called the Pareto front or Pareto set. A solution is considered Pareto-optimal if there is no other solution that can improve one objective without worsening at least one other objective, if there is no other feasible solution that dominates it (a solution A dominates another solution B if it performs better in at least one objective without being worse in any other objective). This means that the Pareto set is the set of all Pareto-optimal solutions in the objective space, i.e., the set of all non-dominated solutions. The algorithm aims to find a set of solutions that covers this front. Multi-objective algorithms are generally more complex due to the need to handle multiple objectives and to explore the whole Pareto front. In the case of MOO, the decision making is more complicated since there is no single best solution. The decision maker must take into account all of the trade-offs between conflicting objectives and make informed decisions based on personal preferences or domain-specific criteria.
There are serious challenges with MOO. Among them is the problem of high dimensionality. The mathematical and computational complexity of the problem exponentially increases with the number of variables, and this becomes very serious for large-scale problems. Thus, a thorough exploration of the solution space becomes exceedingly difficult. Finding and representing the Pareto front as accurately as possible is a significant challenge in multi-objective optimization since it requires extensive exploration of the solution space. This results in another closely connected challenge, that of large computational complexity: the solutions of multi-objective algorithms are generally vastly more computationally demanding than those for single-objective ones. The main challenge of MOO lies in finding a balance among numerous conflicting objectives and determining the right trade-offs. The challenge is further aggravated because these both problems are subjective and depend on the preferences of the decision maker, a situation that may be problematic, to say the least, and is definitely difficult to quantify in any meaningful way. Yet another problem is the need for tools and methods to help the decision maker in the decision, especially those for the visual presentation of data in multidimensional spaces. Further, generation of a set of different solutions that adequately and without redundancy covers the entire Pareto front can be challenging. This generation usually requires special tweaking of algorithms and even the generation of new ones, either customized to the problem at hand or created as hybrids of two or more software approaches.
The question of choice between single- or multiple-objective (or hybrid) algorithms reduces to the question of the number of conflicting objectives posed by the problem. However, if there is an obvious, recognizable and relatively easily resolved trade-off among multiple objectives, then the decision maker might decide to utilize a single-objective approach in spite of the problem having more than one objective. This reduces to the question of the complexity of the problem: if it is not possible to make a decision regarding the trade-off, or if the structure of the problem is non-unimodal or multimodal, then the MOO is more appropriate. Another decision factor is determined by the available computational resources and the time constraints, bearing in mind that MOO is highly demanding for both. Finally, the subjective personal preferences of the decision maker will often tip the balance toward one of the available options.
8. Neural Networks and Multi-Objective Optimization
Most neural networks (NNs) are general computational models belonging to AI; as such, they themselves do not belong to bio-inspired optimization algorithms, except in name. However, even such types of NNs can be used together with bio-inspired optimization algorithms as a combination or hybrid. Many of the NNs can be utilized in multi-objective optimization, in situations where traditional approaches meet serious problems due to the high dimensionality and the need to reach trade-offs, which is naturally followed by the vastly increased computational complexity of the problems. Some types of neural networks do belong to biomimetic procedures, the most important among them being artificial neural networks (ANN). Apart from being biomimetic per se, artificial neural networks incorporate optimization algorithms which are often biomimetic, i.e. they are used in hybridized solutions. Some examples of the use of biomimetic optimization algorithms such as Genetic Algorithms (GA), Ant Colony Optimization (ACO), Differential Evolution (DE) or Particle Swarm Optimization (PSO) together with artificial neural networks are reported in [213-215]. Many complex multi-objective problems can be solved by such combined algorithms.
This entry is adapted from the peer-reviewed paper 10.3390/biomimetics8030278
This entry is offline, you can click here to edit this entry!
