Hybridizing Differential Evolution and Particle Swarm Optimization to Design Powerful Optimizers: A Review and Taxonomy <s> C. Differences and Connections With Previous Taxonomies <s> This paper discusses the trade-off between accuracy, reliability and computing time in global optimization. Particular compromises provided by traditional methods (Quasi-Newton and Nelder-Mead's simplex methods) and genetic algorithms are addressed and illustrated by a particular application in the field of nonlinear system identification. Subsequently, new hybrid methods are designed, combining principles from genetic algorithms and "hill-climbing" methods in order to find a better compromise to the trade-off. Inspired by biology and especially by the manner in which living beings adapt themselves to their environment, these hybrid methods involve two interwoven levels of optimization, namely evolution (genetic algorithms) and individual learning (Quasi-Newton), which cooperate in a global process of optimization. One of these hybrid methods appears to join the group of state-of-the-art global optimization methods: it combines the reliability properties of the genetic algorithms with the accuracy of Quasi-Newton method, while requiring a computation time only slightly higher than the latter. <s> BIB001 </s> Hybridizing Differential Evolution and Particle Swarm Optimization to Design Powerful Optimizers: A Review and Taxonomy <s> C. Differences and Connections With Previous Taxonomies <s> We propose a hybrid algorithm for finding a set of nondominated solutions of a multi objective optimization problem. In the proposed algorithm, a local search procedure is applied to each solution (i.e., each individual) generated by genetic operations. Our algorithm uses a weighted sum of multiple objectives as a fitness function. The fitness function is utilized when a pair of parent solutions are selected for generating a new solution by crossover and mutation operations. A local search procedure is applied to the new solution to maximize its fitness value. One characteristic feature of our algorithm is to randomly specify weight values whenever a pair of parent solutions are selected. That is, each selection (i.e., the selection of two parent solutions) is performed by a different weight vector. Another characteristic feature of our algorithm is not to examine all neighborhood solutions of a current solution in the local search procedure. Only a small number of neighborhood solutions are examined to prevent the local search procedure from spending almost all available computation time in our algorithm. High performance of our algorithm is demonstrated by applying it to multi objective flowshop scheduling problems. <s> BIB002 </s> Hybridizing Differential Evolution and Particle Swarm Optimization to Design Powerful Optimizers: A Review and Taxonomy <s> C. Differences and Connections With Previous Taxonomies <s> Hybrid metaheuristics have received considerable interest these recent years in the field of combinatorial optimization. A wide variety of hybrid approaches have been proposed in the literature. In this paper, a taxonomy of hybrid metaheuristics is presented in an attempt to provide a common terminology and classification mechanisms. The taxonomy, while presented in terms of metaheuristics, is also applicable to most types of heuristics and exact optimization algorithms. ::: ::: As an illustration of the usefulness of the taxonomy an annoted bibliography is given which classifies a large number of hybrid approaches according to the taxonomy. <s> BIB003 </s> Hybridizing Differential Evolution and Particle Swarm Optimization to Design Powerful Optimizers: A Review and Taxonomy <s> C. Differences and Connections With Previous Taxonomies <s> This paper shows how evolutionary algorithms can be described in a concise, yet comprehensive and accurate way. A classification scheme is introduced and presented in a tabular form called TEA (Table of Evolutionary Algorithms). It distinguishes between different classes of evolutionary algorithms (e.g., genetic algorithms, ant systems) by enumerating the fundamental ingredients of each of these algorithms. At the end, possible uses of the TEA are illustrated on classical evolutionary algorithms. <s> BIB004 </s> Hybridizing Differential Evolution and Particle Swarm Optimization to Design Powerful Optimizers: A Review and Taxonomy <s> C. Differences and Connections With Previous Taxonomies <s> In this paper, a fitness landscape analysis for several instances of the quadratic assignment problem (QAP) is performed, and the results are used to classify problem instances according to their hardness for local search heuristics and meta-heuristics based on local search. The local properties of the fitness landscape are studied by performing an autocorrelation analysis, while the global structure is investigated by employing a fitness distance correlation analysis. It is shown that epistasis, as expressed by the dominance of the flow and distance matrices of a QAP instance, the landscape ruggedness in terms of the correlation length of a landscape, and the correlation between fitness and distance of local optima in the landscape together are useful for predicting the performance of memetic algorithms-evolutionary algorithms incorporating local search (to a certain extent). Thus, based on these properties, a favorable choice of recombination and/or mutation operators can be found. Experiments comparing three different evolutionary operators for a memetic algorithm are presented. <s> BIB005 </s> Hybridizing Differential Evolution and Particle Swarm Optimization to Design Powerful Optimizers: A Review and Taxonomy <s> C. Differences and Connections With Previous Taxonomies <s> Manifold possibilities of hybridizing individual metaheuristics with each other and/or with algorithms from other fields exist. A large number of publications documents the benefits and great success of such hybrids. This article overviews several popular hybridization approaches and classifies them based on various characteristics. In particular with respect to low-level hybrids of different metaheuristics, a unified view based on a common pool template is described. It helps in making similarities and different key components of existing metaheuristics explicit. We then consider these key components as a toolbox for building new, effective hybrid metaheuristics. This approach of thinking seems to be superior to sticking too strongly to the philosophies and historical backgrounds behind the different metaheuristic paradigms. Finally, particularly promising possibilities of combining metaheuristics with constraint programming and integer programming techniques are highlighted. <s> BIB006 </s> Hybridizing Differential Evolution and Particle Swarm Optimization to Design Powerful Optimizers: A Review and Taxonomy <s> C. Differences and Connections With Previous Taxonomies <s> Over the last decade, memetic algorithms (MAs) have relied on the use of a variety of different methods as the local improvement procedure. Some recent studies on the choice of local search method employed have shown that this choice significantly affects the efficiency of problem searches. Given the restricted theoretical knowledge available in this area and the limited progress made on mitigating the effects of incorrect local search method choice, we present strategies for MA control that decide, at runtime, which local method is chosen to locally improve the next chromosome. The use of multiple local methods during a MA search in the spirit of Lamarckian learning is here termed Meta-Lamarckian learning. Two adaptive strategies for Meta-Lamarckian learning are proposed in this paper. Experimental studies with Meta-Lamarckian learning strategies on continuous parametric benchmark problems are also presented. Further, the best strategy proposed is applied to a real-world aerodynamic wing design problem and encouraging results are obtained. It is shown that the proposed approaches aid designers working on complex engineering problems by reducing the probability of employing inappropriate local search methods in a MA, while at the same time, yielding robust and improved design search performance. <s> BIB007 </s> Hybridizing Differential Evolution and Particle Swarm Optimization to Design Powerful Optimizers: A Review and Taxonomy <s> C. Differences and Connections With Previous Taxonomies <s> The combination of evolutionary algorithms with local search was named "memetic algorithms" (MAs) (Moscato, 1989). These methods are inspired by models of natural systems that combine the evolutionary adaptation of a population with individual learning within the lifetimes of its members. Additionally, MAs are inspired by Richard Dawkin's concept of a meme, which represents a unit of cultural evolution that can exhibit local refinement (Dawkins, 1976). In the case of MA's, "memes" refer to the strategies (e.g., local refinement, perturbation, or constructive methods, etc.) that are employed to improve individuals. In this paper, we review some works on the application of MAs to well-known combinatorial optimization problems, and place them in a framework defined by a general syntactic model. This model provides us with a classification scheme based on a computable index D, which facilitates algorithmic comparisons and suggests areas for future research. Also, by having an abstract model for this class of metaheuristics, it is possible to explore their design space and better understand their behavior from a theoretical standpoint. We illustrate the theoretical and practical relevance of this model and taxonomy for MAs in the context of a discussion of important design issues that must be addressed to produce effective and efficient MAs. <s> BIB008 </s> Hybridizing Differential Evolution and Particle Swarm Optimization to Design Powerful Optimizers: A Review and Taxonomy <s> C. Differences and Connections With Previous Taxonomies <s> The interest about hybrid optimization methods has grown for the last few years. Indeed, more and more papers about cooperation between heuristics and exact techniques are published. In this paper, we propose to extend an existing taxonomy for hybrid methods involving heuristic approaches in order to consider cooperative schemes between exact methods and metaheuristics. First, we propose some natural approaches for the different schemes of cooperation encountered, and we analyse, for each model, some examples taken from the literature. Then we recall and complement the proposed grammar and provide an annotated bibliography. <s> BIB009
There exist several taxonomies in the literature, which present certain classification of hybrid metaheurisitcs BIB003 , BIB006 , BIB009 , EAs BIB004 , or MAs BIB008 . Talbi proposed a taxonomy for hybrid metaheuristics, which considers solutions to design and implementation issues BIB003 . Regarding each issue, Talbi adopted both a hierarchical classification and a flat one. Jourdan et al. extended Talbi's taxonomy to the case of cooperation between metaheuristics and exact methods BIB009 . The taxonomy that is proposed by Raidl [18] is very similar to Talbi's taxonomy, but it removes some flat classification mechanisms and introduces a new classification mechanism, i.e., control strategy, to differentiate integrative hybridization and collaborative hybridization. In integrative hybridization, one parent is considered as a subordinate, embedded component of another parent. In collaborative hybridization, parents exchange information, but are not part of each other. The collaborative hybridization and the integrative hybridization reflect the collaboration-based PR and the embedding-based PR, respectively. Krasnogor and Smith proposed a scheduler-based taxonomy for the classification of different MAs BIB008 . The MA taxonomy provides a very useful tool to capture the interaction between LS and standard evolutionary operators (mutation, crossover, selection). Calégari et al. proposed a taxonomy of EAs, namely table of EAs (TEA), to distinguish different classes of EAs by the enumeration of the fundamental ingredients of each of these algorithms BIB004 . The TEA is competent for the identification of the differences between EAs in detail; however, it does not provide any classification mechanisms of hybridization strategies. In the following, the new taxonomy that we proposed will be compared with Talbi's taxonomy. Talbi introduced many classification criteria in his taxonomy, including "low level versus high level," "relay versus teamwork," "homogeneous versus heterogeneous," "global versus partial," "specialist versus general," etc. Distinct from the notions of HL and OL, the low/high level that Talbi mentioned refers to the issue of whether a given function of a parent optimizer is replaced by another one (low level: replaced; high level: self-contained). Relay is de facto equivalent to the sequential OO. In contrast, teamwork hybridization represents "cooperative optimization models, which involve many parallel cooperating agents, where each agent carries out a search in a solution space" BIB003 . Therefore, the term "teamwork" does not refer to the parallel OO of parents but highlights the feature of cooperatively improving multiple solutions. The homogeneity here (homogeneous/heterogeneous) indicates whether the parent optimizers are same or not. A global hybrid means that all parent optimizers work in the whole search space. In contrast, parents of a partial hybrid are designated to different subproblems, which are determined by a decomposition of the original problem. Obviously, partial hybrids can be categorized into the class C,C,?,? . The criterion "specialist/general" indicates whether or not some parent optimizers are used to solve other problems beyond searching in solution space (general: no; specialist: yes). In particular, a hybrid in which a parent is used to optimize another one can be classified as a specialist hybrid. Therefore, the specialist hybridization conceptually shares much similarity with the assistance-based hybridization. The OL of parents, the TIT, and the TTI are not considered in Talbi's taxonomy. According to Talbi's taxonomy, the well-known MA will be placed within the low-level teamwork class BIB003 , BIB008 . In contrast, the new taxonomy indicates that the MA is a hybridization framework with diversified implementation schemes. An MA can be an instance of C,?,?,? , where the mapping (operations) of global search and LS can be separated, and for example, LS can be implemented in each generation after a GA completes all of its operations. In this case, the mapping of the MA can be denoted by (GA : and f LS represent the mapping of selection, crossover, mutation, and LS operators, respectively. The GA's original consecutive operation can be extracted from the composite mapping and separated from LS. An MA can also be embedding based, where the mappings of global search and LS cannot be separated. For example, if LS is implemented after both crossover and mutation of the GA BIB005 , the mapping of LS will be integrated (inserted) into the GA, that is to say, the GA's mapping in this case cannot be extracted from the MA as It is obvious that the original consecutive operation of the GA, which is denoted by f S • f C • f M , is broken by LS. In addition, even within C,?,?,? , an MA can be achieved by different schemes, such as C,P,S,S (e.g., GQD BIB001 ), C,P,S,D (e.g., MOGLS BIB002 ), and C,I,S,D (e.g., MA-S1 and MA-S2 BIB007 ). By comparison, the five hybridization factors in the new taxonomy that is proposed in this paper give rise to a more comprehensive, coherent, hierarchical classification tool, benefiting a step-by-step analysis/design of any hybrid.