Abstract
Metaheuristics have been extensively used for solving difficult optimization problems in recent years. However, according to the famous theory (No Free Lunch), it is infeasible for a metaheuristic to optimally solve all problems. As a result, novel metaheuristics have been incessantly introduced. In this paper, we provide a bibliography on recent development in metaheuristics. This work lists and categorizes 112 metaheuristic articles published from 2009 to 2015. The key aim of this work is to gather a group of metaheuristics that plays a fundamental role in development of metaheuristics in the coming years. This paper reveals that the growth of new metaheuristics continues as well as has not seen any interruption. Although this study cannot assert to be comprehensive, it involves a main part of novel publications and therefore, is a helpful guide for new metaheuristic researches.
Introduction
Optimization is a process of searching the solutions to a problem1 [115]. As mentioned by Minhas and Arif [72], a global optimization (GO) tries to obtain the overall optimum of a multidimensional function. A problem of GO may be depicted mathematically as a maximization model with the goal to obtain a point
Recently, metaheuristics have been widely employed for solving intricate OP. Metaheuristics are a class of approximate techniques that have been extended considerably since their beginning in the 1980s. Dogan and Olmez [23] explained that approximate methods can be classified into two categories: i) heuristics and ii) metaheuristics. Heuristics are provided just for a special problem. But metaheuristics are appropriate to a large range of OP. A number of the famous metaheuristics are Simulated Annealing (SA), Particle Swarm Optimization (PSO), Genetic Algorithm (GA), Ant Colony Optimization (ACO), Differential Evolution (DE), Tabu Search (TS), and Artificial Bee Colony (ABC).
Although the results that are produced by metaheuristics are not essentially the optimum, they can be achieved in a reasonable time [55]. Gandomi and Alavi [38] mentioned that metaheuristics are more potent than the classical techniques such as DP for tackling complex problems generally. Due to their appropriate performance and simplicity of execution, metaheuristics have been extensively applied to different real problems [28, 57]. Briefly, owing to ease, flexibility, derivation-independent structure and local optimum avoidance, metaheuristics have become outstandingly widespread in recent years [75].
According to Toscano and Lyonnet [114], the key attribute of metaheuristics is the use of a random procedure to search. They believed that the application of a random search method is indispensable for searching a good result. However, Formato [36] proposed an efficient deterministic metaheuristic called central force optimization (CFO).
Let us recall that the efficiency of a metaheuristic depends on a suitable equilibrium between exploitation (intensification) and exploration (diversification). The exploration is the capability to explore in the solution area to detect the optimum. On the other hand, the exploitation is the skill to do a good move to search better moves [12]. More formally, swift convergence may lead to captivity in a local point. Alternatively, desired quality of solutions can result in wider inspection and as a result slower convergence. To cope with these subjects, the scholars have developed the existing metaheuristics or have suggested new metaheuristics [94, 51]. For example, according to Zhu and Kwong [133], ABC is strong at diversification and is weak at intensification. Also according to Cuevas et al. [21], although DE and PSO are known as two of the most common metaheuristics for various OP, they fail to balance between diversification and intensification usually. Finally, Patel and Savsani [89] warned that appropriate compromise between diversification and intensification is an unsolved topic in metaheuristics field. As a result, novel metaheuristics are always required to deal with particular problems [16]. Finally, Fig. 1 describes that how a metaheuristic acts (it is a rough structure) [30].
General skeleton of the metaheuristic.
Various classification factors have been introduced for the metaheuristics (e.g., [75, 12, 38, 23] and [13]). Perhaps the most instinctive method is on the basis of the origin of the metaheuristics. But Blum and Roli [12] explained that this categorization is not necessarily significant. According to Mirjalili et al. [73] and Dogan and Olmez [23], metaheuristics may be classified into two key groups: (i) Single-solution based techniques such as SA and TS and (ii) Population-Based techniques such as GA and ABC. Single-solution based techniques begin the problem-solving procedure with a single solution. But in popu- lation-based techniques, several solutions are generated and improved iteratively. Clearly, the first step is “create a primary population” in these techniques. However, how this task is to be done finds very little mention.
According to “No Free Lunch” theorem [120], it is unattainable for a metaheuristic to tackle every optimization problem. Namely, a metaheuristic can provide a good outcome in a given problem, but the same technique may give a weak outcome in other problem [75]. In other words, there is no a metaheuristic to arrive the best solution for every problem. For example, Hertz and de Werra [48] argued that TS is very better than SA in GCP. On the other hand, according to Kuik et al. [59], SA is better than TS in LSP. But Lee and Kim [61] explained that TS and SA had the same efficiency in PSP. However, Yang [125] claimed that there is no an approved approach for comparing efficiency of various metaheuristics. Therefore, finding new more efficient metaheuristics is an open topic [94, 103]. Noteworthy, Mernik et al. [69] pointed out a number of misunderstandings in comparing metaheuristics. For example, Yang [126] introduced a novel metaheuristic called flower pollination algorithm (FPA). He claimed that FPA is more competent than PSO and GA. However, according to Draa [24], FPA does not suggest any outstanding performance. In other words, FPA has quite limited efficiency. Finally, Crepinsek et al. [19] warned that a meaningful comparison among various metaheuristics is very hard. We refer to Crepinsek et al. [19] and Mernik et al. [69] for details on suitable comparison methods among metaheuristics.
According to Kaveh and Mahdavi [56], a metaheuristic is often tuned for a given problem. But one of the attractive aspects of a strong metaheuristic is the ability to implement to a large group of problems. In view of this, two main directions in metaheuristics have been: (i) the introduction of novel metaheuristic on the basis of newfound ideas, and (ii) the extension of hybrid metaheuristic [128]. Hybrid metaheuristic tries to take the strong aspects from more than a metaheuristic and/or some algorithmic concepts as well as various paradigms. Talbi [107] reported that the importance of hybrid metaheuristics has increased very much in recent years. He claimed that the best solutions for a lot of problems are generated by hybrid algorithms. Please see Talbi [107] for a good review of hybrid metaheuristic. Anyway, according Yi et al. [128], the study on metaheuristics have changed from a technique-oriented approach to a problem-oriented approach.
Boussaïd et al. [13] claimed that the origins of approximately all metaheuristics are in nature. Namely, although we are the cleverest creature, nature is the mankind teacher for all time [28]. However, the intricacy of living creature is not analogous to the difficulty of any metaheuristics. Therefore, “motivations from nature” are relatively ambiguous [90]. According to Yang [123], nature-inspired techniques are among the most potent metaheuristics. Also bio-inspired metaheuristics are one of the significant classes of the nature-inspired techniques [38]. Evolutionary algorithms (these methods imitate the route of natural selection principle such as GA and DE), swarm intelligence (these techniques mimic the group conducts of animals such as ACO and PSO) and ecology based algorithm are three famous groups of these metaheuristics [38, 27]. Yang [125] explained that one of the key causes for this achievement is that these metaheuristics have been generated by imitation the most worthy systems in the real world. However, all metaheuristics are not on the basis of nature (e.g., music, philosophy, game…). Merrikh-Bayat [71] mentioned that although the foundations of inspiration are distinct, they have several resemblances. However, Piotrowski et al. [90] claimed that many metaheuristics with different names have been initiated and are argued to be motivated by various roots by scholars. But indeed, they are only a development of the others. For example, according to Piotrowski et al. [90], DE and PSO are just the extensions of GA. It should be noted that Sorensen [103] claimed that many of these metaheuristics are not only dispensable but also detrimental to the scientific value of this area. Unfortunately, the evidences in Sorensen [103] study are poor in various aspects.
All metaheuristics have benefits and deficiencies compared to other techniques. For example, the classic PSO frequently gets trapped when handling intricate multimodal frameworks [78]. SA is extremely slow [49]. Moein and Logeswaran [78] pointed out that GA gives no complete guarantee of detecting the optimum. Rao et al. [93] explained that the key weakness of PSO, DE and GA is that several parameters must be adjusted for suitable result. A variation in the parameters alters the achievement of a metaheuristic. To remedy this problem, Rao et al. [93] suggested a parameter-less metaheuristic called teaching and learning-based optimization (TLBO). They claimed that compared with a number of efficient metaheuristics, TLBO leads to superior results. But according to Crepinsek et al. [18], this metaheuristic suffers from various miscalculations.
As mentioned before, metaheuristic have been extensively used to various problems. Yi et al. [128] mentioned that metaheuristics have become a main sector of optimization techniques. Nevertheless, according to Yang [125], there are several significant topics which stay undetermined about metaheuristics. For example, except SA and PSO, convergence in none of the metaheuristics has been demonstrated [125]. Duan and Luo [26] pointed out that it is essential to extend a standard framework for studying the complexity of a metaheuristic. For example, ACO is an accepted metaheuristic. But the study about the hardness of ACO in various structures (e.g., multi objective problems) stays imperfect. Finally, some researchers have reviewed metaheuristic papers in various time periods. We refer to Osman and Laporte [86], Blum and Roli [12], Parpinelli and Lopes [88], Yang [125], Boussaïd et al. [13], Sorensen [103] and Duan and Luo [26] for additional information on metaheuristics.
Owing to the quick spreading of metaheuristics, this study prepares a bibliography of some of the key metaheuristics during 2009–2015. Let us recall that we concentrate on main novel metaheuristics and therefore, this study does not cover hybrid metaheuristics.
The rest of this study is arranged as follows. Section 2 explains the study methodology and then pre- sents a bibliography on metaheuristics. Diverse results of this research are discussed in Section 3. Finally, this study will be concluded in Section 4.
We adopt SCOPUS as the data origin of this work. SCOPUS is one of the largest databases in the world. Also we employ other famous sources such as Google Scholar for more corroboration. In this review, novel metaheuristic papers are searched from these sources with care. It should be noted that we restricted the time of this bibliography to 2009–2015, which corresponds to the following years to the time discussed in previous literature review such as Blum and Roli [12], Parpinelli and Lopes [88], Yang [125], Boussaïd et al. [13] and Duan and Luo [26]. It is very essential to note that this paper is a bibliography and therefore has not a literature review structure. Also we could sense the growing path of novel metaheuristics during recent years (2009–2015). Therefore, this year, namely 2009 is selected as the beginning date for this review. For finding the papers about our study, we have searched various keywords such as “new metaheuristic”, “optimization algorithm”, “optimizer”, “nature-inspired algorithm”, “global optimization”, etc. from 2009 to 2015. Studies that have any of these keywords in the title or keyword have been collected for more assessment. Based on this search, 112 novel metaheuristics from various journal articles, conference papers and books emerged. Noteworthy, all articles that were used in this review are in English. Therefore, the journals in another language were overlooked. Fortunately, these articles are a very small part of the total studies. Let us mention that one of the most important features of this study is that conferences proceeding articles, books and book chapters are included. However, the majority of previous review articles focused only on journal articles. After searching and collecting these papers, 112 new metaheuristics have been listed from 2009 to 2015 in Table 1.
The list of novel metaheuristics
The list of novel metaheuristics
Owing to the complexity of OP, metaheuristics are becoming significantly interesting as a strong technique for optimization. Thus, new metaheuristic papers are growing at a very quick rate. Figure 2 depicts that from 2009 to 2015, the novel metaheuristic papers have developed increasingly. Also from 2012 to 2015, the numbers of new metaheuristics have considerably raised. As a result, at this time, we can say metaheuristic has become a main wing of optimization methods. Although great attempt was allocated to collect various peer-reviewed references, this list is undoubtedly not perfect and will be endlessly renewed. Noteworthy, the data were collected in December 2015.
Circulation of publications year.
A number of journals cited in this study are Computers & Structures, Information Sciences, Applied Soft Computing, Advances in Engineering Software, International Journal of Bio-Inspired Computation, Neural Computing and Applications, Expert Systems with Applications, AI Communications, Acta Mechanica, Knowledge-Based Systems, Applied Mathematics and Computation, Soft Computing, Swarm Evolutionary Computation, and so on.According to Table 1, in publishing novel metaheuristic Information Sciences, Applied Soft Computing and Computers & Structures are the most famous journals. The Neural Computing and Applications, International Journal of Bio-Inspired Computation and Advances in Engineering Software are three other popular journals. Figure 3 depicts the top 7 journals in this area. According to this figure, the “Information Sciences” is number one.
The top 7 journals.
Many countries such as Iran, China, USA, Turkey, Greece, Taiwan, UK, Morocco, Spain, Australia, India, Mexico, Malaysia, France, South Korea, Pakistan, Germany, Cuba, Egypt, Italy, Hong Kong, Ethiopia, Brazil, Iraq and Japan have participated to this bibliography. The majority of metaheuristics papers are from Iranian scholars. Also there have been 25 countries that have given at least one article. Most studies are from Asia compared to Europe, America, Australia and Africa. This distribution has some similarities with Behzadian et al.’s [11] review on the Technique for Order Preference by Similarity to Ideal Solution (TOPSIS). TOPSIS is one of the most accepted techniques for multiple criteria decision making (MCDM).
By analyzing the aforementioned papers, five reputable metaheuristics between 2009 and 2015 can be selected as Gravitational Search Algorithm [94], Teaching and Learning-Based Optimization [93], Krill herd, Grey Wolf Optimizer [75], Charged System Search [54] and Intelligent Water Drops [100]. They have a large effect on the application of metaheuristics indicated by amount of citations in Google Scholar 1370, 339, 285, 203, and 193, respectively on 20 December 2015.
Distribution of principle of inspiration.
The origins of inspiration.
As mentioned before, there are several approaches to categorize metaheuristics. In this study, metaheuristics are dissected to six classes on the basis of inspiration: Animal-inspired, Physics-inspired, Human-inspired, Plant-inspired, Natural and Biological events-based and others. (i) Animal-based: the origin of motivation is diverse behaviors of animals. For example African Wild Dog Algorithm [104] imitates the hunting treatment of African dogs. (ii) Physics-based: the foundation of motivation is physical or chemical rules. For example, the gravitational search algorithm [94] was introduced on the basis of the principle of gravity. (iii) Human-based: the basis of inspiration is various behaviors of human beings. For example, Brain Storm Optimization Algorithm [101] was motivated by the brainstorming technique. (iv) Plant-based: the source of motivation is special behaviors of plants. For example, Runner-Root Algorithm [71] simulates the task of the root of plants. (v) Natural and Biological events-inspired: the origin of motivation is natural and biological events. For example, Symbiotic Organisms Search [16] imitates symbiotic plans that creatures employ to live. According to Figs 4 and 5, animal is the most popular foundation of inspiration. Physics and Plant are two other popular themes. Although the basis of stimulation for nature inspired metaheuristic is distinct, they have several resemblances. Please see Merrikh-Bayat [71] for other details on this topic. Noteworthy, according to Blum and Roli [12], in some cases, it is intricate to ascribe a metaheuristic to one of these categories. Finally, although metaheuristic techniques do not have any restriction on source of inspiration, the key root of motivation is “Nature”. But according to Piotrowski et al. [90], some debates on foundations of inspiration are required. They mentioned that: “Can we say that some of its sources are “better” or “worse” if the inspiration is useful?” Shi [101] claimed that mankind is the smartest animal. Therefore, a metaheuristic inspired by human should be better than a metaheuristic motivated by group behavior of animal. Piotrowski et al. [90] studied different viewpoints on this issue. They explained that a physical law or a non-living creature may be assumed as a better root of motivation. Because they are human-independent and not subjective, and hence, lead to outcomes that are really seen in the world. Briefly, the physical themes only pursue the forces that stimulate them. They do not gather any knowledge and do not select any choice. However, according to another opinion a living creature can be the best origin of inspiration. Perhaps this is the cause why the majority of new metaheuristics have been motivated by the natural characteristics of living creatures [90]. Although the issue whether such incentives are significant stays an open topic, the natural inspirations may have various advantages. In fact, “Life” is a mysterious example of optimization for millions of years.
Metaheuristics has been applied effectively in numerous problems with different structures. Due to the complexity of OP, metaheuristics are becoming more and more interesting as a strong technique for optimization. Today, searching for more powerful techniques is a very hot issue. Therefore, the introduction of novel metaheuristics is substantially growing. In this work, we have listed several recent researches (112 new metaheuristics) from 2009 to 2015. Although this study cannot declare to be comprehensive, it involves a main part of new novel publications and therefore is a helpful guide for new metaheuristic researchers. We hope that our work helps to simplify future research. Future studies can concentrate on applications and study on citation in metaheuristic context.
Footnotes
In this study, the terms “optimization problem” and “problem” are utilized interchangeably.
Acknowledgments
The authors would like to thank Professor P. De Meo and the anonymous reviewers.
