A bibliography of metaheuristics-review from 2009 to 2015

1. 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 x ∗ ∈ F from a feasible area F ⊂ ℜ d that a d -dimensional goal function f : ℜ d → ℜ is maximized, namely f ⁢ ( x ∗ ) ⩾ f ⁢ ( x ) . The majority of the real-world problems in the engineering can be formulated as GO problems. However, many real optimization problems (OP) are naturally intricate and very hard to solve. Some real problems are project scheduling problem (PSP), graph coloring problem (GCP), lot sizing problem (LSP), job shop scheduling problem (JSSP), vehicle routing problem (VRP), flow shop scheduling problem (FSSP), facilities location problem (FLP), etc. There are various techniques such as linear programming (LP) and dynamic programming (DP) for tackling these problems. But nearly all of these solving approaches require rigid secondary properties such as continuity and convexity of a given problem. Furthermore, such methods frequently are unfruitful to handle a problem that has several local maximum and/or minimum [23, 93]. Mathematically, most real-world problems are NP-hard, namely nobody has obtained a polynomial time technique for solving them. These problems are intractable, namely the large-scale problems are very CPU time-consuming. The conventional methods usually miscarry to handle such large size or non-linear problems (NLP).

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].

OPEN IN VIEWER

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.