1 Introduction

Research optimization as a mathematical discipline concerns the search for either minima or maxima of functions or objective functions in terms of real-world problems, subject to given constraints. In general, optimization comprises of a wide variety of methods from operation research, artificial intelligence, computer science, and machine learning, as used to improve business processes in practically all human endeavour and industries. More so, optimization problems arise naturally in many different disciplines. For example, in engineering design, a structural engineer designing a multi-storey building must choose materials and proportions for different structural components in the building in order to have a safe structure that is as economical as possible. Similarly, in portfolio management, a portfolio manager must choose investments that generate the largest possible rate of return for its investors while keeping the risk of major losses to acceptably low levels. Optimization problem can be formulated either as a continuous or combinatorial design search space. Continuous optimization is the process of searching for maxima (or minima) of a function \(f\left(x\right),\) \(x=\left\{{x}_{1},{x}_{2},\dots ,{x}_{D}\right\}\in {R}^{D}\) subject to \({g}_{i}\left(x\right)\le 0\), \(\left(i=\mathrm{1,2},\dots ,M\right),\) \({h}_{j}\left(x\right)=0\), \(\left(j=\mathrm{1,2},\dots ,N\right)\), \({x}_{kL}\le {x}_{k}\le {x}_{kU},\left(k=\mathrm{1,2},\dots ,N\right)\), in a D-dimensional continuous search space, where \({g}_{i}\) and \({h}_{j}\) are the inequality and equality constraints, respectively (Abbass 2001). The terms \(L\) and \(U\) are bounds on optimization variables. For a combinatorial optimization problem, it is the process of finding the best solution for problems with discrete set of feasible solutions. Similarly, this process also involves the searching for either maximal or minimal value of an objective function \(f\) whose domain is a discrete but large configuration search space, as opposed to a \(D\)-dimensional continuous search space. Formally, a combinatorial optimization problem can be defined as a tuple \(\left(S,f, \Omega \right)\), where \(S\) is usually called a search (or solution) space with \(x=\left\{{x}_{1},{x}_{2},\dots ,{x}_{n}\right\}\) set of variables, \(f\) is the objective function to be minimized or maximized and is defined over a mapping \(f:{\Omega }_{1}\times {\Omega }_{2}\times \cdots \times {\Omega }_{n}\mapsto {R}^{+}\), and the variable \(\Omega\) is the set of constraints that have to be satisfied to obtain feasible solutions. To solve a combinatorial optimization problem the solution \({s}^{*}\in S\) with minimum objective function value needs to be determined such that \(f\left({s}^{*}\right)\le f\left(s\right) \forall s\in S\). The solution \({s}^{*}\) is called the globally optimal solution of the tuple \(\left(S,f, \Omega \right)\) and \({s}^{*}\subset S\) is called the set of globally optimal solutions (Ezugwu et al. 2020; Weise 2009). Figure 1 below illustrates the graphical representation of an optimization problem.

Fig. 1
figure 1

An optimization problem illustration

Full size image

There are a wide class of optimization techniques, including linear programming, quadratic programming, convex optimization, interior-point method, trust-region method, conjugate-gradient methods, evolutionary algorithms, heuristics and metaheuristics (Meyers 2009). Therefore, for solving optimization problems, a broad class of exact and heuristics approaches do exist. In addition, the revolution of the artificial intelligence era has led to the recent development of intelligent optimization techniques that are able to comfortably provide near-optimal solutions to hard and complex real-world optimization problems, which would not have been practicable using the traditional or exact optimization methods. More so, this revolution also triggered the development of several well-known natural and bio-inspired metaheuristics global optimization techniques. Therefore, this study takes a deeper look into an interesting research area of metaheuristics design, classifications and applications areas that have been reported so far from inception to date in the literature. A brief summary of the classification of global optimization methods is illustrated in Fig. 2. It is noteworthy to mention here that a concrete definition of heuristic and metaheuristic has been elusive and in practice, many researchers and practitioners interchange these terms. However, in a more general sense, the heuristic algorithms are known to be very specific in their search for solution and problem-dependent as well. On the other hand, the metaheuristic algorithms are high-level problem-independent techniques that can be applied to a broad range of problems.

Fig. 2
figure 2

A brief classification of optimization methods

Full size image

Research in the application of nature-inspired metaheuristic algorithms has increasingly gained high popularity over the last four decades. However, there are many reasons for this popularity, which may have been strongly attributed to the successes achieved by these algorithms. In general, it is evidence to say that one of the leading reasons is that these algorithms have been inspired and designed by mimicking some of the most interesting successful phenomenon in nature (Fister et al. 2013). These natural occurring processes that have inspired the development of virtually 99% of metaheuristic algorithms can simply be classified into two namely, biological occurring process and physical laws or systems include those from chemistry and physics. It is equally interesting to note that one of the main reason why research in this area of study have continuously made progress is due to the simple fact that there are no established or well-defined mathematical principles and computational complexity analysis which present clues as to how exactly these algorithms work and interact to achieve high efficiency (Yang 2018a, b). More so, the last decade, however, has witnessed an explosive increase in the number of natural or man-made processes, that have been used as a metaphor for the development of new generation metaheuristic algorithms. However, there is an obvious desire and calls by researchers to single out those state-of-the-art metaheuristics that have long standing history of high profile performance and robustness and make them perpetual optimization tools. The principle of extracting weeds from plants can also be seen as the best possible means of minimizing the proliferation of supposedly novel metaphor-based metaheuristic algorithms that neither perform well, nor provide any useful insight.

Despite the above affirmation of acknowledging the fact that the metaheuristic research community are currently witnessing an explosive increase in the number of new algorithms being developed every day, that is not to say that the current study is taking side by recognizing only the achievements of the classical metaheuristic algorithms. In fact, there are a record number of new and novel evolutionary techniques that have been able to yielded successfully the best solutions for some hard benchmark problem instances that were initially considered to be unsolvable (Dokeroglu et al. 2019). Therefore, there is the need for a proper documentation of all the metaheuristic algorithms developed so far with the motivation to analyze, categorize and synthesize them in a meaningful manner based on their design inspirational source, useful impact and application areas.

Indeed, it is a very challenging task to present a systematic classification of all the available metaheuristic algorithm in the literature. However, few research papers have tried to present only a handful of these algorithms. For example, Fister et al. (2013) provided a brief review of nature-inspired algorithms for optimization, with about 75 list of different algorithms that were classified into two main groups, namely swarm intelligence-based algorithms and bio-inspired based algorithms. The review in Fister et al. (2013) only provided a useful insight to the aforementioned two classifications without covering the individual algorithm inspirational design sourced and application areas. Brownlee (2011) presented a well-documented reference text that describes to an extent a large number of algorithmic techniques that covers bio-inspired computation, computational intelligence and metaheuristics in a complete, consistent, and centralized manner for the research community. However, study have shown that the list of metaheuristic algorithms presented in Brownlee (2011) is quite limited or rather incomplete per say and more so, considering the fact that the study was done in 2011 for an area that have consistently evolved afterwards. Xing and Gao (2014) presented a compilation list of 134 computational intelligence algorithms, with the goal of providing to the scientific community a sense of motivation to further analyze the existing research on metaheuristic techniques for categorizing and synthesizing it in a meaningful manner. A similar more recent study was presented by Rajpurohit et al. (2017), in which a glossary of metaheuristics was provided with the authors focusing majorly on providing the core sources of inspiration for the listed algorithms. In this current study, we present a more comprehensive compilation of approximately 300 different metaheuristic algorithms with their classifications based on design inspiration, variants, useful impacts and application areas. Furthermore, the main technical contributions of this paper are summarized as follows:

  • The intrinsic structure of the publications and citations count is presented as a part of bibliomteric analysis. This analysis is extended with the visual representation of the bibliographic coupling among authors, countries, institutions, and sources of publications.

  • A comprehensive collation of over 200 metaheuristics algorithms starting from 1960 to 2019 with the aim of providing useful insights to some of the fundamental design concepts associated with these algorithms.

  • A systematic categorization of both classical and new generation metaheuristic algorithms with emphasis on design inspirational source, variants, classification, impacts, and application areas.

  • A concise presentation of a glossary of metaheuristic algorithms for easy reference by metaheuristic research enthusiasts.

The rest of the paper is organized as follows. Section 2 covers the comparative summary of the background work related to the area. In Sect. 3, we provide the refined bibliometric analysis of the area of metaheuristic. In Sect. 4, we present a discussion on some of the main inspirational source for the various algorithmic design concepts of all the well-known metaheuristic algorithms. In Sect. 5, we present a brief analysis of the useful impacts of all the metaheuristics, while in Sect. 6, we provide a comprehensive list of metaheuristic algorithms covering algorithm authors, summary of inspiration source, summary of classification, algorithm variants, impact, and application areas. Finally, Sect. 7 presents the study concluding remarks.

2 Background work on nature inspired metaheuristic algorithms

The purpose of this section is to clearly discuss the difference between the already published review on nature inspired metaheuristic algorithms and the present work. There have been attempts in the literature to comprehensively gather the metaheuristic algorithms in a single literature for easy access by researchers. For example, Fister et al. (2013) published a relatively comprehensive list of nature inspired algorithms. It covers different classes of the algorithms including swarm, bioinspired, chemistry, physics and others including sources of inspirations. Brownlee (2011) presents corpus of nature inspired algorithms covering different classes of the algorithms including stochastic, evolutionary, physical, probabilistic, swarm, immune and neural algorithms. Xing and Gao (2014) presents a rough guide to nature inspired metaheuristic algorithms. The algorithms were categorized into biology, physics, chemistry and mathematics. The core working principles and performance of each of the algorithms in the different category were presented. Sörensen (2015) traced the history of nature inspired metaheuristic algorithms in the literature. Publications or important events, application domains and paradigm shift were discussed.

Despite the efforts made by researchers to bring together a comprehensive list of the metaheuristic algorithms, only the study of Xing and Gao (2014) covered 134 metaheuristic algorithms while other attempted works covers less than 100 metaheuristic algorithms. However, over 200 nature inspired metaheuristic algorithms are scattered in the literature. The previous works mainly focuses on the core operations, applications and inspirational sources of the nature inspired metaheuristic algorithms. None of the previous works attempted bibliometric analysis of the comprehensive list of the nature inspired metaheuristic algorithms to show the impact of the algorithms in different domain despite the significance of bibliometric analysis in the literature. Table 1 presents the summary of the previous works compared to the present work.

Table 1 Summary of the previous review on metaheuristic algorithms
Full size table

3 Bibliometric analysis

The Bibliometrics (or Scientometrics) study is a study often performed to extract and understand the intrinsic structure of a particular research area. This type of study is available since 1969, the literal meaning of which can be found in (Pritchard 1969; Broadus 1987). Some previous notable works are (Alonso et al. 2009; Hirsch 2005; Franceschini and Maisano 2010). In recent times, bibliometric analysis has gathered a lot of attention among the researchers. Not only it provides a standalone platform for the overall growth of an area but also opens the possible scope for future studies. Moreover, young researchers can get starting point for their individual research, rather than lost in the ocean of articles.

These have been several such studies in the important research domains. More recently, Muhuri et al. (2019) studied the bibliometric aspect of Industry 4.0 and also reviewed the background work in that area. Shukla et al. (2020) provided the detailed bibliometric analysis on type-2 fuzzy sets and systems. Atanassov’s intuitionistic fuzzy set was studied in this manner by Yu and Shi (2015), with the help of citation analysis. Some other crucial research areas with bibliometric studies are: real-time operating systems (Shukla et al. 2018), green supply chain (Amirbagheri et al. 2019), energy efficiency (Trianni et al. 2018) etc. Lately, there have been several journal specific studies also i.e. the bibliometric analysis on a particular journal. Some of such studies are as follows: Applied Soft Computing (Muhuri et al. 2018), Engineering Applications of Artificial Intelligence (Shukla et al. 2019), IEEE Transactions on Fuzzy Systems (Yu et al. 2017a, b), Knowledge-Based Systems (Cobo et al. 2015), Information Sciences (Yu et al. 2017a, b), European Journal of Operational Research (Laengle et al. 2017), International Journal of Intelligent Systems (Merigó et al. 2017), Neurocomputing (Janmaijaya et al. 2018), etc.

3.1 data collection technique and document types

The bibliometric data is extracted from the Web of Science (WoS) repository. WoS is one of the widely used databases for bibliometric analysis. Scopus and Google scholar are other options available, however, due to the wide range of article indexing, they suffer from many inconsistencies and irrelevant publications. On the other hand, WoS not only is one of the largest databases for the bibliometric analysis but also contains the exclusive indexing of quality sources including SCI indexed journals and ranked international conferences. Therefore, WoS is accounted for the indexing of high-quality publications (Shukla et al. 2019; Yu et al. 2017a, b; Zavadskas et al. 2014; Merigó et al. 2017). Majority of analysis works are performed only with WoS data. We have used two of the widely used citations indexes such as: Science Citation Index Expanded (SCI-EXPANDED) and Social Sciences Citation Index (SSCI). The keyword used is “metaheuristic” and the search is performed till the end of 2019. The search year is from 1989 to 2019, making it the data comprises of 30 years. Because as the bibliometric point of view, it is to be noted that the term “metaheuristic” came into light only around mid-90′s. It may also be verified from the year of the first publication, which came in 1994 (see Fig. 1).

According to the collected data, there were total of 5163 papers published till the end of 2019. All the publications were classified into 11 categories or document types as marked by WoS. Table 2 shows the list of all document types which are as follows: Article (5018), Proceedings paper (304), Review (122), Early Access (56), Correction (7), Editorial Material (7), Meeting Abstract (7), Bibliography (1), Book chapter (1), Book Review (1), and Retracted Publications (1). The last percentage (%) column shows the contribution of each document types. Note that, there could be few document types lay under two categories. Thus, overall sum % may go above 100%.

Table 2 Document types in WoS
Full size table

3.2 Publications and citations: structure analysis

Here, we provide the publication and citation structure in metaheuristic research domain over the last 30 years. As can be seen from Fig. 3, the first publication which used the term metaheuristic came in 1994. The topic didn’t see the light till starting four years, as there were only total of 12 publications. However, publications started to increase from 1998 (TP = 14). It reached in three numbers i.e. 100 publications in just 13 years (2006). The growth rate has then been tremendous over the years. It can be justified by the fact that in just last 4 years (2015–2019), the publication count is 52.84% (TP = 2728) of the total publications in the metaheuristic domain. The year 2019 saw the highest number of 941 publications and as per the trend year 2020 is supposed to publish more than 1000 papers.

Fig. 3
figure 3

Publication structure over the years in WoS

Full size image

Another trend to analyze is the citation structure of a research area. Figure 4 represents the line graph of the citation received by the papers publishing in metaheuristic domain. As seen with number of publications, there were only 12 citations of the work related to this area. After that, there’s been an exponential growth in the citation count over the years. The highest citations of 19,506 were received in year 2019, while it is continuous four years when number of citations is more than 10,000.

Fig. 4
figure 4

Citation structure over the years, as per WoS

Full size image

3.3 vosviewer visualization

This section is the visualization section using the widely used tool called VOSviewer. This is basically graphical mapping software used for visualizing the bibliographic network among various entities. Here, entities could be journals, organization, documents, countries, keywords etc. These entities may be inter-connected by citations, co-citations, co-authorship or bibliographic coupling. First, we have presented the bibliographic coupling among different entities. The link between the entities corresponds to the strength between them either in terms of number of publications, common references or co-citations. These entities or items may belong to a group of cluster. In the visualization, the items within a same cluster are marked with same color. The entities may be represented by the circular node and its size may vary depending on the weight of the entity.

The bibliographic coupling between the top 25 authors is shown in Fig. 5. Zandieh, Mladenovic, and Marinakis form a cluster of green color. These are the names which are visible; there are possibly other names also. This cluster implies that degree of overlap between the reference lists of publications of these authors is more. Similarly, the red color cluster of Kaveh, Yang, Deb, Coelho, Das, Soto, and Gandomi are likely working on same area (Definalty “metaheuristic”) and citing the same source in their reference lists. Figure 6 shows the bibliographic coupling of the top 25 most productive countries. Here, bibliographic coupling indicates that there are more common reference list in the papers published by these countries. There are clearly two clusters, one with green color (USA, Spain, Canada, England, Germany, Italy, Brazil, Belgium, Mexico, France, Greece and Poland) and the other with Red color (China, India, Iran, Turkey, Taiwan, Australia, Malaysia, Saudi Arabia, Algeria, Egypt, Vietnam, Japan, and South Korea). The link between the China, India and Iran can be seen as thicker as compared to others. This shows the commonality and intersection of the literature work between these two countries.

Fig. 5
figure 5

Bibliographic coupling among the authors

Full size image
Fig. 6
figure 6

Bibliographic coupling among the countries

Full size image

The clusters in Fig. 7 shows that the Universities of Granada, Malaga, Bologna, Vienna, Laguna, Belgrade and Huazhong university of science and technology belongs to a single green cluster and most likely to have common research interest area. On the top there are two institutions from Iran viz. Shahid Beheshti University and Amirkabir University of Technology, forming a separate cluster of blue color. The biggest cluster is of red color comprising of Islamic Azad University (Iran), University of Tehran (Iran), Iran University of science and Technology (Iran), National Taiwan University of Science and Technology (Taiwan), National Institute of Technology (India), Indian Institute of Technology (India), Middlesex University (England), etc. It can be observed that three universities of Iran are working in meteheuristic with most similar literature background. Moreover, the underlying relationship between the authors, the countries and the institutions can be estimated with the fact that countries in the same clusters also have the authors exhibiting such behavior. For example, Swagatham Das and Yang Xin-She have together published the paper: “Bio-inspired computation: Where we stand and what's next.” and certainly referenced many publications which can be seen by the bibliographic coupling of their countries and institutions.

Fig. 7
figure 7

Bibliographic coupling among institutions/organizations

Full size image

Bibliogrpahic coupling between the journals implies that the papers published in these journals have more common reference lists. Clearly there are two clusters viz. the green one (Computers and Operations Research, Computer and Industrial Engineering, Journal of Heuristics, Annals of Operations Research, and International Journal of Production) and the red one (Applied Soft Computing, Information Sciences, Neural Computing and Applications, IEEE Access, Engineering Optimization, Artificial Intelligence Review, Mathematical Problems in Engineering, Swarm and Evolutionary Optimization, Engineering Applications of Artificial Intelligence, Applied Intelligence and Turkish Journal of Electrical Engineering Computer Sciences). Pictorial representation can be seen in Fig. 8.

Fig. 8
figure 8

Bibliographic coupling among the Journals/ Sources

Full size image

3.3.1 Co-author-author visualization

Here, the analysis type is co-authorship and the unit of analysis is authors. This will produce the visualization of the authors publishing together and working on similar research areas. The threshold of minimum number of papers by an author is five (5). The total of 304 authors meets the threshold among all 11,241 authors. However, the largest set of connected entities consists of only 107 authors, whose visual representation is depicted in Fig. 9a. From the figure, there are total of 15 clusters. There are maximum of 13 items in one of the cluster, although it may not be clear from the optimized version of the Fig. 9a. Thus, we have also shown that particular cluster in Fig. 9b. The connected link depicts that these authors have same paper. For example, Zeschia, Scharef, and Di Gaspero have a common publication on metaheuristic (Ceschia et al. 2011). The thickness of the link between these three authors indicates more common publications. In the overall authors (Fig. 9a), the prominent authors with bold nodes are: Subramanian, Glover, Juan, Ghomi, Mladenovic, Laporte, Das, Vega-rodriguez etc.

Fig. 9
figure 9

a Co-authorship and Authors’ analysis. b Largest cluster snippet of the Co-authorship and Authors’ analysis

Full size image

3.3.2 Citations analysis visualization

Here, two crucial visualizations are presented with respect to the biliometric analysis. Figure 10 shows the citations analysis among the top 25 publication sources. A link between two sources (A and B) implies that the publications in source A have cited publications in Source B. The thickness and link strength signifies more number of references. From Fig. 10, two clusters can be easily visualized. In the red color cluster, Applied Soft Computing is the prominent sources, implying that the other sources in that cluster viz. engineering optimization, computers structures, IEEE access etc. have cited applied soft computing more number of times. Similarly, there are two prominent nodes in cluster 2 with green color i.e. Computers and operations research and European Journal of operational research.

Fig. 10
figure 10

Citations analysis among the journals/sources

Full size image

Figure 11 is the citation analysis among the top 25 universities/institutions. There are 3 clusters in the visualization. Red color cluster has Islamic Azad University, Iran has the prominent node, implying that other universities in this cluster Middlesex university, Amir Kabir University, and University of Bologna have cited more papers on metaheuristic from Islamic Azad University. The other cluster is the blue color containing, National Metsovio Polythechnic, Greece, University Federal Fluminense, Brazil, Athens University of Economics and Business, Greece etc. The prominent nodes in third cluster of green colors are: University of Belgrade, Serbia, and University of La Laguna, Spain.

Fig. 11
figure 11

Citations analysis among the institutions/universities

Full size image

4 Metaheuristics inspirational source

In this day and age, full of computational challenges of ever-growing complexity there is no iota of doubt, within the research community, that behavioral patterns and phenomena observed in nature have laid the foundations of many metaheuristic algorithms (Ser et al. 2019). Virtually, all the metaheuristics designs available in the literature claimed to have been inspired by some form of natural or physical occurring phenomenon. Some of these sources of inspiration are triggered by processes emanating from biology, chemistry and physics, with the algorithmic design interactions partly or completely mimicking the respective behavioral convolutions of the aforementioned phenomenon. In recent times, many of the so-called metaheuristic algorithms have been tagged as nature-inspired, and this is because the algorithmic design concepts have been motivated by simply borrowing some sort of inspirational source from nature. Therefore, metaheuristics are often classified into sub-categories depending on the inspirational source type as mentioned earlier. For simplicity and replication purpose, we will broadly classify these metaheuristics into two main categories, namely bio-inspired and physical-inspired metaheuristics, while both falls under the generic term nature-inspired metaheuristics. Further, nature-inspired metaheuristics are a much wider class of algorithms that have been developed by drawing inspiration from nature and they are almost all population-based algorithms (Yang 2018a, b). Subsequently, we present some brief descriptions of each of the forementioned sub-classifications with carefully selected illustrative examples using few of the new proposed metaheuristics developed in 2014 and 2019 respectively.

The bio-inspired metaheuristic algorithms are more popular and common in the optimization literature, more so, these algorithms are commonly based on a metaphor of a typical biological process or interactions. These processes can range from the ecological interaction among living organisms that are pushing for survival of the fittest to the behaviors of birds in search for food source. Examples of these bio-inspired algorithms include, the symbiotic organisms search algorithm, particle swarm optimization, ant colony optimization, genetic algorithms, evolutionary algorithms, artificial bee colony, bees algorithm, firefly algorithm, invasive weed optimization, biogeography-based optimization, evolution strategy, differential evolution, shuffled frog leaping algorithm, genetic algorithm, salp swarm algorithm, harris hawks optimization, and so on. This simply means that virtually all biological processes can easily be used or translated into a metaphor for yet another new metaheuristic optimization technique and as such the listing of these algorithms becomes endless. It is noteworthy to also mention here that these algorithms on the one hand can be referred to as swarm intelligence based metaheuristic algorithms going be the concept of multiple agents in this case swarm of either bees, birds or even school of fishes collaborating to search for possible food sources or routes. Genetic algorithm, particle swarm optimization and ant colony optimization algorithms are among the early optimization methods that have attracted wide spread research interest and with recognizable industrial influence in terms of their problem solving capabilities and robustness.

In illustrating one of the bio-inspired metaheuristics techniques, we consider the symbiotic organism search, a population-based metaheuristic algorithm that was proposed in 2014 by Cheng and Prayogo (2014). This algorithm’s design inspirational source was pulled from the well-known symbiotic biological relationships that most organisms often adopt for their survival in the ecosystem. Basically, there are three symbiotic relationship types namely, mutualism, commensalism and parasitism employed by organisms to enable them coexist in a very complex and dynamic environment like the ecosystem. In this case the commensalism relation denotes a situation where two living organisms benefit reciprocally. One common example of mutualism is the interaction between the Oxpecker birds and Rhinoceros. The Oxpecker lives on the rhino, sustaining itself by eating the bugs and parasites on the animal and the Rhinoceros get pest control (Ezugwu and Prayogo 2019). On the one hand, the commensalism interaction is where one of the organisms derives all the associated benefits and the coexisting organism is not affected by the immediate interaction. For example, the interaction between cattle egrets that eat the insects from the foraging activities of cattle. Lastly, when the benefit derived by one organism causes harm to another organism, the relationship is said to be a parasitism relationship. An example is the mosquitoes that rely on human blood to produce their eggs. the human (host) is affected negatively and the mosquito (parasite) benefits from the relationship. The symbiotic organism search algorithm design inspiration source is further represented using the diagram shown in Fig. 12.

Fig. 12
figure 12

Source from left—commensalism (Oxpeckers on a Rhinoceros back), mutualism (Cattle egrets and Cattle), and parasitism (Mosquito feeding on Human blood) (Ezugwu and Prayogo 2019)

Symbiotic organism search algorithm design inspirational.

Full size image

The physical-inspired metaheuristics are those algorithms which inspirational design concepts were drawn from physical process that ranges from chemical reactions, music harmony and orchestra playing, water falls, sports, annealing process, black hole, physics laws, teaching and learning process, flight, politics, refraction of lights, spiral movement of galaxies to mention but a few. Some common example of these metaheuristics include, simulated annealing, black hole algorithm, tabu search, intelligent water fall algorithm, wingsuit flying search, cultural algorithm, colonial competitive algorithm, harmony search, teaching–learning-based optimization, and so on. Obviously, these sets of metaheuristic algorithms are basically driven by the principle of physical laws and complex interactions, chemical reactions and socio-economic or demographic unfolding factors. Simulated annealing and tabu search are among the physical-inspired based algorithms that have achieved significantly high profile industrial application throughputs.

Simply put, it is very clear that researchers in metaheuristic designs are picking up mundane ideas that are essentially found in some well-known traditionally based exact or classical mathematical optimization methods. For example, consider the most recent wingsuit search algorithm developed by mimicking the intention of a flier to land at the lowest possible point of the Earth surface within their range as illustrated in Fig. 13 (Covic and Lacevic 2020). The wingsuit fly search algorithm is a very clear illustration of an algorithm design idea that was copied from the principle of aerodynamics flight mechanisms with an already accomplished existing exact solution approaches coming from the spectrum of computational fluid dynamics (Nyberg 2012). Also consider another new metaphor-based metaheuristic algorithm called the Ludo game-based metaheuristics proposed by Singh et al. (2019). The Ludo game search algorithm claims to have drawn its inspiration from the household board game played with family, friends and kids across the globe (see Fig. 14). This algorithm in tis interactions mimics the rules of playing the game Ludo using two or four players to perform an update process for different swarm intelligent behaviors exhibited by the individual players in a row. Similarly, the algorithm uses the concepts of two and four players to enhance the exploration and exploitation of problem landscape analysis. However, taking a closer look into the design concepts of each of these new algorithms will definitely escalate the fear already highlighted by some authors in the field of metaheuristic research on the lack of originality or novelty in what is being proposed and published as new metaheuristic techniques. More so, these recent proposals are nothing short of a change in metaphor with a deceptive variation in mathematical or computational notations from the popular exact optimization methods.

Fig. 13
figure 13

Wingsuit fly search algorithm originally inspired by the wingsuit aerodynamics flight mechanisms (Nyberg 2012)

Full size image
Fig. 14
figure 14

The Ludo game-based metaheuristic (Singh et al. 2019)

Full size image

Similarly, in 2020, Zhao et al. (2020) proposed yet another new metaheuristic search optimizer called the spherical search optimizer that was primarily inspired by the principle of basic hypercube search style and basic reduced hypercube search style. The algorithmic design concept and search optimization techniques of this metaheuristic can be explained as follows: consider an instance of the search process of two individuals say A and B in a three-dimensional space represented in Fig. 15 below. In order to create an initial population for the search space, two vectors (see the two blue lines on the graphs of Fig. 13) are created, which in this case denote the two individuals A and B. According to the search updating equation, the individual A searches in a cube region by a diagonal line with vertex A and B. The individual A which in this case is the original individual can walk to arbitrary position in this cube region to B using the uniform distribution model. In the cube region, B denotes the guided individual. A possible search trajectory that may be followed by the individual A is here represented by the red broken lines. It can be observed that there is no section of the broken line, which stands perpendicularly to a plane because three dimensions of A change synchronously according to the basic characteristic of the cube search style.

Fig. 15
figure 15

On the left is the hypercube search style and on the right is the reduced hypercube search style (Zhao et al. 2020)

Full size image

On a high note, the recorded advancements in the domain of global optimization, specifically in the area of metaheuristic algorithm designs have been quite interesting and probably most profitable to wide range of optimization research enthusiasts mostly in the academia. However, despite the proliferation in the manner in which these algorithms are being proposed and published on monthly basis, there have been relatively no any new signs of novelty in the design and implementation of these so-called new arrivals or new generation metaheuristic techniques. Again, notably, other than a mere change and variation in metaphor or notations, as rightly pointed out by Sörensen (2015), these metaheuristics apparently appears to be counterproductive in producing truly pioneering research of high quality in recent times. This is equally very true since the scientific research communities have drifted and focused their attention more on popularizing the quantity of research output rather than the novelty of research contents presented by a researcher.

5 Generalized classification of metaheuristic algorithms

Metaheuristic algorithms are generalised algorithm to find solutions as close to the optimal as possible. Due to the non-deterministic in nature, the guaranty of the optimal solution is not provided. They usually follow the repeated sequence of generating or searching an efficient solution. Evidently, no single metaheuristic algorithm can satisfy the need of all the optimisation problem as explained by the no free lunch theorem by Wolpert and Macready (1997). Most of the well-known metaheuristics algorithms are nature-inspired, but few took the motivation from other processes such as physics/chemistry-based, social science, sports-based etc. Nature-inspired metaheuristic algorithms are algorithms inspired by intelligent bahaviour of natural systems. These kind of algorithms could be from biological systems (e.g. human brain, behavior of animals and plants); nature (e.g. Big bang, waterfall and gravitation); human activities (e.g. football and interior decoration). Genetic algorithm and artificial neural network are the early nature-inspired algorithms that were inspired by biological systems. The two algorithms brought a significant breakthrough in the area of artificial intelligence. These two pioneering algorithms motivated the research community to starts proposing different nature inspired metaheuristic algorithms for solving real world problems. The salient features of the nature-inspired algorithms that make them stand out from the traditional algorithms are as follows: scalability, tolerance to missing data, interpretability, flexibility, optimization capability, adaptability, accessibility and capability to solve highly none linear and complex problems. The nature inspired mate-heuristic algorithms can be classified into different classes depending on the nature and operational capabilities of the algorithms. The taxonomy of the nature inspired metaheuristic algorithms point out the class in which a specific algorithm belongs. In addition, the relationship that exist among the nature inspired metaheuristic algorithms in shown in the taxonomy for a reader to make sense of the entire spectrum of the nature inspired metaheuristic algorithms. As already discussed, the nature inspired metaheuristic algorithms in Brownlee (2011) falls into different classes as follows:

5.1 Genetic algorithms

The trend in research in the field of metaheuristics started after 1950, but one of the landmark studies which initiate the trend of work in this type of algorithm is genetic algorithm(GA) by Holland (1962). GA is one of the simplest algorithm, it includes a set of prospective solutions considered as population. New solutions are generated using genetic operators (crossover, mutation) to replace the existing solution in the population. The inspiration behind the GA is based upon the idea of Darwin’s survival of the fittest.

5.2 Simulated annealing

In metallurgy, the cooling process in the furnace is used to make a metaheuristic algorithm known as simulated annealing (SA) by Kirkpatrick et al. (1983). In SA, the probability to consider the low-value solution decreases throughout the algorithm run. By doing this, the chances to get a global best increases.

After the introduction and success of GA, SA and a few other research works for solving complex problems, researchers also started studying various natural or manmade processes to make an efficient solver. (i.e. to take the inspiration for the efficient algorithm).

5.3 Swarm intelligence

Algorithms inspired by the behaviour of a group (swarm) of organisms found in nature are called swarm optimization algorithms.

The swarm intelligence (SI) house the nature inspired metaheuristic algorithms that are inspired from group intelligent behavior of animals. Typically, the group intelligent behaviour involves collective work among the agents within a certain environment to achieve their goal such as flocks of birth, school of fish and colonies of ants. The intelligent behavior is in different organizational format aiming to solve problem which includes: distributed, self-organizing and de-centralization within the environment. Let us look at some of the common goals that such kind of collective intelligent behavior tends to achieve, for example, foraging for food, re-location of colony and evading of prey. The agent work together in harmony, information flows within the participating agents or stored or it is communicated within the environment, for example, the communication can be performed through the use of ants pheromones, fish proximity, bees dancing, etc. The typical example of the nature inspired algorithms that falls within this category includes but not limited to: Particle swarm optimization, Ant Colony Optimization algorithm, Bees algorithm and bacterial foraging. These category of algorithms are the second generation of the nature inspired algorithms that starts springing up motivated from the first generation algorithms that is the EC.

Particle swarm optimization (PSO) by Mitchell (1998) and Kennedy and Eberhart (1995), ant colony optimization (ACO) by Dorigo et al. (2006), artificial bee colony (ABC) by Karaboga (2005), firefly algorithm in Yang (2009, 2010a, b), and cuckoo search by Yang and Deb (2009), etc. are few swarm intelligence based algorithms.

Swarm intelligence is a relatively new field. The proper research on this field is started with the introduction of PSO. Earlier, there are very few studies based on the behaviour of animals for computation. In PSO, candidate solutions are treated as particles which explore the search space. The search for better solutions is guided by the local best and global best present. The change in solution toward better one is done using velocity by which a particle moves in the search space. PSO is inspired by the movement of a flock of birds or a school of fish. There is another algorithm that is based upon the ant behaviour of finding the resources(food). In ACO, artificial ants represent candidate solutions. These ants explore the search space and release pheromones. Pheromone's strength is judged by the strength of the solution. These pheromones help other ants to explore nearby areas to find a better solution. Following similar nature, another algorithm that uses bee as inspiration was proposed. In ABC, the behaviour of bees is used to scout better solutions in the search space. Firefly algorithm is another swarm intelligence based algorithm. As the name suggests, it is inspired by the firefly. The flashing ability of firefly attracts other fireflies. Each firefly is considered as a prospective solution. The brightness of flashing indicates the strength of the solution, higher the fitness of the solution gives more brightness of flashing, which results in attracting other solutions towards itself. Cuckoo search algorithm utilises the intrusive behaviour of the cuckoo laying eggs in other bird’s nest. Cuckoo eggs are considered new solutions if this solution is better than the existing solution, then it may replace the existing one.

5.4 Physics and chemistry based metaheuristic approaches

The most well-known algorithm based on physics is gravitational search algorithm (GSA) by Rashedi et al. (2009). GSA is based upon the gravity and motion which basic law of physics. Like gravity, there are algorithm based upon magnetism also such as electromagnetism-like algorithm (Birbil and Fang 2003), electromagnetic field optimization by Abedinpourshotorban et al. (2016) etc. Similarly, there are algorithm inspired by chemical processes such as chemical reaction optimisation algorithm (CRO) (Lam and Li 2009) and artificial chemical reaction optimisation algorithm for global optimisation (ACROA) by Alatas (2011) etc. Both of these algorithms utilise the feature of processes going toward the equilibrium in the chemical reaction.

5.5 Social Science based metaheuristic approaches

The algorithms based on social sciences are imperialist competitive algorithm (ICA) by Atashpaz-Gargari and Lucas (2007), brainstorm optimisation algorithm (BSO) by Shi (2011) etc. ICA utilises the idea of colonies and empire. Less efficient empire is collapse, and strong survive long. The new empires are formed by invading the older weaker ones. Another well-known algorithm based on social science is BSO. BSO inspired by the ability of humans to come up with creative ideas to solve the problem.

Not only from physics, chemistry and social sciences there are algorithms available which are inspired from varieties of processes such as sport based, water-based, music-based, math-based etc. Intelligent water drops algorithm (IWD) by Shah-Hosseini (2009), water cycle algorithm (WCA) by Eskandar et al. (2012), water evaporation optimisation (WEO) by Kaveh and Bakhshpoori (2016), water wave optimisation (WWO) by Zheng (2015) are water-based algorithms. League championship algorithm (LCA) by Kashan (2014) etc. are sport based algorithms. Sine Cosine Algorithm by Mirjalili (2016a, b) is a math-based algorithm. Harmony search by Geem et al. (2001) is music-based algorithm. Apart from these well-known algorithms, there are various metaheuristics algorithms. In addition to that, the improved versions of these algorithms are also vast in numbers.

5.6 Multi/many objective optimization approaches

These algorithms work on single objective or combined objective optimisation. But to solve the multi objective simultaneously, new extended versions of metaheuristics are immerged such as multi objective genetic algorithm (MOGA) by Murata and Ishibuchi (1995), non-dominated sorting genetic algorithm (NSGA-II) by Deb et al. (2002), strength pareto archive algorithm (SPEA2) by Zitzler et al. (2001), multiobjective evolutionary algorithm based upon decomposition (MOEA/D) by Zhang and Li (2007) etc. In addition to multi objective optimisation there is more complex problems solving known as many objective optimisations which include more than three objectives problems. The algorithms to solve these optimisations problems are NSGA-III by Yuan et al. (2014), hypervolume-based many-objective optimization (HypE) by Bader and Zitzler (2011) etc.

NSGA-II is based upon Pareto optimality and dominance relation; it helps in differentiating solutions based upon two or more objectives. SPEA2 uses an external archive and clustering to differentiate better solution from the population. In MOEA/D, objectives are decomposed, and a reference vector is introduced to optimise multiobjective problems. MOEA/D is also an efficient procedure for many objective optimisation, but NSGA-II and SPEA2 fail with the increase in the number of objectives. Using the same reference measure used in MOEA/D, NSGA-II is extended to NSGA-III to handle many objectives. There are other procedures which use performance measure such as hypervolume by Sun et al. (2018), inverted generational distance by Ishibuchi et al. (2015) etc. to solve many objective problems.

5.7 Evolutionary computation

The evolutionary computation (EC) involved the type of nature inspired metaheuristic algorithms that falls within the reams of natural evolution processes and mechanism. The evolution is the way of selection in a natural system involving changes pioneered by Darwin for survival in environment based on fitness. In this case, the processes and mechanism of evolution is described from inception to genetic material. The evolutionary algorithms investigate the computational system that looks similar to the processes and mechanism with simplified versions that tends to achieve the effective adaptive system development. The evolutionary algorithms family produce the pioneered nature inspired metaheuristic algorithm called genetic algorithm where the initial population represent the candidate solutions to the problem and the solution space is the environment. The candidate solutions evolve through natural selection process and the candidate with the best fitness survived, as such, selected as the best solution to the problem. Other algorithms in this class of EC includes but not limited to evolutionary strategy, genetic programming and differential evolution.

5.8 Immune algorithms

The immune algorithm (IA) are the category of algorithms that derived their inspiration from natural immune system processes and mechanism to create artificial immune system. The immunity of the natural system is an agent in the natural system that tries to protect the host organism from any external intrusion from pathogens and toxic substances. The pathogens contained bacteria, viruses, parasites and pollen as microorganism. The function of the natural immunity is the detection of the intrusion of the pathogen and it is protected from harming the horst organism by eliminating the pathogen. The typical example of the IA includes but not limited to artificial immune systems, clonal selection algorithms, negative selection algorithms and immune network algorithms.

5.9 Physical algorithms

The physical algorithms (PA) are the types of nature inspired metaheuristic algorithms that are derived from the computational process and mechanism of physical systems. These type of algorithms are not biologically inspired but fit well into the mate-heuristics and computational intelligence. Therefore, the algorithms can be viewed as nature inspired metaheuristic algorithms. The physical systems that inspired such types of algorithms includes: music, metallurgy, dynamic systems that is complex, interplay between evolution and culture (e.g. avalanche). The algorithms in this category mostly stochastic algorithms with a combination of both local and global techniques of searching. The algorithms that falls in this category involves simulated annealing, extremal optimization, harmony search, memetic algorithm and cultural algorithm.

5.9.1 Search techniques

Iterated Local Search: The iterated local search is the extension of multi start search. It can be considered to have double phase approach for searching combining the greedy randomized adaptive search procedure and variable neighborhood search. Guided Local Search algorithm: The guided local search algorithm is global optimization algorithm that is embedded with a local search. It has been extended from the local search algorithm e.g. Hill climbing. Tabu Search: The Tabu search is an algorithm for the control of embedded heuristic technique. The Tabu search is the category for the larger group of derivative techniques that embedded metaheuristic with memory structure, example, includes reactive and parallel Tabu search.

Below there are two summary figures which depicts the generalized classifications of metaheuristics search techniques (Fig. 16) and taxonomy of metaheuristics application areas (Fig. 17). More so, the scientometrics study carried out in Sect. 3 above generally shows that there are essentially six (6) most important application areas in which several of the popular metaheuristic algorithms have been applied to solve difficult and complex problems. Theses application areas includes, engineering, biological sciences, management, factories or industry, natural sciences, and computer science, while other areas of applications that were not named in this paper are grouped under general application area category.

Fig. 16
figure 16

Generalized classifications of metaheuristics search techniques (De Castro and Von Zuben 2000)

Full size image
Fig. 17
figure 17

Taxonomy of metaheuristics application areas

Full size image

6 Taxonomic categorization of metaheuristic

In this section, we present in a tabular form the various categorizations of metaheuristics that have been developed so far and available in the literature. However, because metaheuristic techniques are very common and popular, they do not require much detailed introduction. The categorization provided in this space is driven by the algorithm design inspirational source, characteristics of search methods denoted as class and number of swarm or agents employed during the search process. Other factors considered for this categorization include existing variants of the algorithms and their application and citation impacts. Basically, the taxonomical categorizations of these optimization techniques are as presented in Table 3 below.

Table 3 Metaheuristic algorithms sorted on the basis of impact
Full size table

The naming convention or metaphors associated with the metaheuristics listing presented in Table 3 is taken basically from biology, physics, psychology, chemistry and surprisingly human interactions or activities. The data collected for this study also revealed that most of the metaheuristics are bio-inspired, for example, the process of natural selection, natural immune system, foraging behavior of ant colonies, parasitic behavior of cuckoo species and the Levy flight behavior of some birds and fruit flies. There are also significant number of methods adopted from physics, for example, cosmology, electricity, law of gravity and mass interactions, electromagnetics. Others includes metaphors from our daily life such as, interior design, sports, music, vocational skills, military, politics, economics, interaction from our ecosystem.

Similarly, from Table 3, it is equally interesting to note that some of the classical algorithms such as simulated annealing with 45,020 impact, differential evolution with 20,661 impact, particle swarm optimization with 14,588 impact, genetic algorithm with 14,573 impact, and ant colony optimization with 11,527 impact, all have five significant digit numbers relative to their level of application relevance. However, the popularity achieved by these five standard algorithms can be attributed to the fact that each of these algorithm in one way or the other have concrete theoretical and mathematical analyses framework which supports their superior performances. Further, the theoretical and mathematical frameworks provide good reasons as to why these algorithms work well in real-world.

7 Metaheuristics applications areas

In this section, we present a summary of the different application areas for the 300 list of metaheuristic techniques presented in this paper (see the glossary of metaheuristics presented in Table 5). The advancement in computing powers in the last few decades has raised a large number of real-world optimization problems in different research and application domain that are extremely complex and difficult to solve. A metaheuristic technique is said to define algorithmic frameworks that can be applied to solve such complex problems in an approximate or near-optima way, by combining constructive methods with local and swarm-based search strategies, as well as strategies for escaping local optima that hinders the scalability of the exact methods as discussed in Torres-Jiménez and Pavón (2014).

In general, studies in the design and application of metaheuristics techniques has grown massively in the past three decades as a practical solution approaches to solving wide range of real-world optimization problems. More so, beside the fact that metaheuristics have scaled perfectly well in finding good quality solutions to many complex and NP-hard problems (Nondeterministic polynomial time-hard problems), they are also able to perform extremely very well in situations where the classical or traditional exact optimization methods would fail to deliver satisfactory results. Obviously, one of the main strength of metaheuristic techniques that has drawn wide interest to the scientific community and industry practitioners alike is the fact that metaheuristic problem solving techniques are able to generate good quality solution in relatively much less time than their exact optimization techniques counterparts. Therefore, because of these associated advantages, metaheuristics have find applications in a wide range of areas such as engineering design, management, factory or industries, finance, pattern recognition, networking, and scheduling. It is noteworthy to mention here that there is no universal metaheuristic approach to be applied to all the application domains. Therefore, after extensive analysis that was carried out, we have compiled the possible application areas for the respective identified metaheuristic techniques, which is presented in Table 4.

Table 4 Application areas of the metaheuristic algorithms (application area citations are not included due to page limit)
Full size table

8 Glossary of metaheuristics

The following list presents a glossary of metaheuristic algorithms comprising of both classical and new generation algorithms. As aforementioned earlier, these two class of metaheuristic are differentiated based on the decades in which the algorithm was actually developed. Each algorithm in this list has been discussed previous and therefore, only their names a presented here for easy summary. For each metaheuristic algorithms, Table 5 lists their authors, class of metaheuristic and published year.

Table 5 Glossary of the metaheuristic techniques
Full size table

9 Conclusion

In general, several metaheuristic techniques that are available in the literature appears to be very popular and have been proven beyond reasonable doubt to be efficient in solving complex real-world problems. It is noteworthy to mention here also that these approximate solution methods are considered to be tremendously fascinating research area with high significant practical ramifications. It is equally true to say that because optimization problems abound in nature and are certainly embedded in our day to day life experiences, the area of metaheuristics research has drawn a lot of curiosity and enthusiasm specifically among young researchers who continuously to explore their surroundings for possible inspirational source that might lead to the formulation of new and efficient metaheuristic algorithms. On the one hand, because mother nature in itself is very complex and diverse, the source of inspiration for metaheuristic design and development also appears to be very diverse and consequently the resulting proposed metaheuristic algorithms to date are likewise enormous. In fact, our earlier study reveals that there are over 200 metaheuristic techniques available in the literature and virtually every month there is at least one or more new algorithms released to the scientific community and the counting is still ongoing.

Obviously, the recorded successes of some standard metaheuristic techniques reported in the literature can be attributed to the steep increase in the cumulative number of the basic and variants of the metaheuristics proposed over the last decades. More so, the proliferation of literature in this research domain has equally made it extremely difficult and confusing for interested researchers and the scientific community to easily identify novel research trends and challenges with practical bearing. In the past, just very few study have been dedicated towards identifying and classifying some of the existing metaheuristic techniques. Similarly, some other related studies have equally attempted to create a complete taxonomy of all the published metaheuristics for the easy of identifying strengths, weaknesses and possible application areas of the global optimization metaheuristic methods. However, despite these audacious and noble attempt to provide a comprehensive classification and taxonomy, little or no success have so far been achieved in this undertaking over the years. The reason for this unsuccessfulness can be completely tied to the fact that the listing of the metaheuristic appears to be endless for now, especially with the proposal and arrival of new metaheuristic on a monthly basis.

In this study we have holistically ventured into collating the general algorithmic profiles of over 250 metaheuristic algorithms in terms of design inspirational source, classification based on swarm or evolutionary search concept, existing variation from the original design, and application areas. Similarly, the bibliometric analysis of the field of metaheuristic was critically examined. Further, we successfully presented a more comprehensive and relatively new taxonomic classification list of both classical and new generation sets of metaheuristic algorithms available in the literature, with the aim of providing an easily accessible collection of popular optimization tools for the global optimization research community who are at the forefront in utilizing these tools for solving complex and difficult real-world problems. However, even though several similar research attempt have been previously established as aforementioned earlier, the current study does not in any way claim any completeness in its own endeavor. This is because it is difficult to provide a complete taxonomy of optimization methods since optimization itself has many subfields with multiple links. We hope that the overall overview and the detailed classifications of all the available up-to-date state-of-the-art and new generation metaheuristic techniques presented in this study will inspire further novel research in the field of global optimization methods and subsequently provide better insight into future designs of more practicable metaheuristic algorithms that would be capable of handling complex and large-scale real-world problems.