Hybridizing Differential Evolution and Particle Swarm Optimization to Design Powerful Optimizers: A Review and Taxonomy <s> A. Tradeoff Between Exploration and Exploitation <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> A. Tradeoff Between Exploration and Exploitation <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> A. Tradeoff Between Exploration and Exploitation <s> Abstract Simulated annealing is a naturally serial algorithm, but its behavior can be controlled by the cooling schedule. Genetic algorithm exhibits implicit parallelism and can retain useful redundant information about what is learned from previous searches by its representation in individuals in the population, but GA may lose solutions and substructures due to the disruptive effects of genetic operators and is not easy to regulate GA's convergence. By reasonably combining these two global probabilistic search algorithms, we develop a general, parallel and easily implemented hybrid optimization framework, and apply it to job-shop scheduling problems. Based on effective encoding scheme and some specific optimization operators, some benchmark job-shop scheduling problems are well solved by the hybrid optimization strategy, and the results are competitive with the best literature results. Besides the effectiveness and robustness of the hybrid strategy, the combination of different search mechanisms and structures can relax the parameter-dependence of GA and SA. Scope and purpose Job-shop scheduling problem (JSP) is one of the most well-known machine scheduling problems and one of the strongly NP-hard combinatorial optimization problems. Developing effective search methods is always an important and valuable work. The scope and purpose of this paper is to present a parallel and easily implemented hybrid optimization framework, which reasonably combines genetic algorithm with simulated annealing. Based on effective encoding scheme and some specific optimization operators, the job-shop scheduling problems are well solved by the hybrid optimization strategy. <s> BIB003 </s> Hybridizing Differential Evolution and Particle Swarm Optimization to Design Powerful Optimizers: A Review and Taxonomy <s> A. Tradeoff Between Exploration and Exploitation <s> An evolutionary recurrent network which automates the design of recurrent neural/fuzzy networks using a new evolutionary learning algorithm is proposed in this paper. This new evolutionary learning algorithm is based on a hybrid of genetic algorithm (GA) and particle swarm optimization (PSO), and is thus called HGAPSO. In HGAPSO, individuals in a new generation are created, not only by crossover and mutation operation as in GA, but also by PSO. The concept of elite strategy is adopted in HGAPSO, where the upper-half of the best-performing individuals in a population are regarded as elites. However, instead of being reproduced directly to the next generation, these elites are first enhanced. The group constituted by the elites is regarded as a swarm, and each elite corresponds to a particle within it. In this regard, the elites are enhanced by PSO, an operation which mimics the maturing phenomenon in nature. These enhanced elites constitute half of the population in the new generation, whereas the other half is generated by performing crossover and mutation operation on these enhanced elites. HGAPSO is applied to recurrent neural/fuzzy network design as follows. For recurrent neural network, a fully connected recurrent neural network is designed and applied to a temporal sequence production problem. For recurrent fuzzy network design, a Takagi-Sugeno-Kang-type recurrent fuzzy network is designed and applied to dynamic plant control. The performance of HGAPSO is compared to both GA and PSO in these recurrent networks design problems, demonstrating its superiority. <s> BIB004 </s> Hybridizing Differential Evolution and Particle Swarm Optimization to Design Powerful Optimizers: A Review and Taxonomy <s> A. Tradeoff Between Exploration and Exploitation <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> BIB005 </s> Hybridizing Differential Evolution and Particle Swarm Optimization to Design Powerful Optimizers: A Review and Taxonomy <s> A. Tradeoff Between Exploration and Exploitation <s> Abstract As a novel optimization technique, chaos has gained much attention and some applications during the past decade. For a given energy or cost function, by following chaotic ergodic orbits, a chaotic dynamic system may eventually reach the global optimum or its good approximation with high probability. To enhance the performance of particle swarm optimization (PSO), which is an evolutionary computation technique through individual improvement plus population cooperation and competition, hybrid particle swarm optimization algorithm is proposed by incorporating chaos. Firstly, adaptive inertia weight factor (AIWF) is introduced in PSO to efficiently balance the exploration and exploitation abilities. Secondly, PSO with AIWF and chaos are hybridized to form a chaotic PSO (CPSO), which reasonably combines the population-based evolutionary searching ability of PSO and chaotic searching behavior. Simulation results and comparisons with the standard PSO and several meta-heuristics show that the CPSO can effectively enhance the searching efficiency and greatly improve the searching quality. <s> BIB006 </s> Hybridizing Differential Evolution and Particle Swarm Optimization to Design Powerful Optimizers: A Review and Taxonomy <s> A. Tradeoff Between Exploration and Exploitation <s> Differential evolution (DE) was very successful in solving the global continuous optimization problem. It mainly uses the distance and direction information from the current population to guide its further search. Estimation of distribution algorithm (EDA) samples new solutions from a probability model which characterizes the distribution of promising solutions. This paper proposes a combination of DE and EDA (DE/EDA) for the global continuous optimization problem. DE/EDA combines global information extracted by EDA with differential information obtained by DE to create promising solutions. DE/EDA has been compared with the best version of the DE algorithm and an EDA on several commonly utilized test problems. Experimental results demonstrate that DE/EDA outperforms the DE algorithm and the EDA. The effect of the parameters of DE/EDA to its performance is investigated experimentally. <s> BIB007 </s> Hybridizing Differential Evolution and Particle Swarm Optimization to Design Powerful Optimizers: A Review and Taxonomy <s> A. Tradeoff Between Exploration and Exploitation <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> A. Tradeoff Between Exploration and Exploitation <s> This paper concerns multiobjective optimization in scenarios where each solution evaluation is financially and/or temporally expensive. We make use of nine relatively low-dimensional, nonpathological, real-valued functions, such as arise in many applications, and assess the performance of two algorithms after just 100 and 250 (or 260) function evaluations. The results show that NSGA-II, a popular multiobjective evolutionary algorithm, performs well compared with random search, even within the restricted number of evaluations used. A significantly better performance (particularly, in the worst case) is, however, achieved on our test set by an algorithm proposed herein-ParEGO-which is an extension of the single-objective efficient global optimization (EGO) algorithm of Jones et al. ParEGO uses a design-of-experiments inspired initialization procedure and learns a Gaussian processes model of the search landscape, which is updated after every function evaluation. Overall, ParEGO exhibits a promising performance for multiobjective optimization problems where evaluations are expensive or otherwise restricted in number. <s> BIB009 </s> Hybridizing Differential Evolution and Particle Swarm Optimization to Design Powerful Optimizers: A Review and Taxonomy <s> A. Tradeoff Between Exploration and Exploitation <s> Particle swarm optimization is a stochastic algorithm for optimizing continuous functions. It uses a population of particles that follow trajectories through the search space towards good optima. This paper proposes adding a local search component to PSO to improve its convergence speed. Two possible methods are discussed. The first adds a term containing estimated gradient information to the velocity of each particle. The second explicitly incorporates the Nelder-Mead algorithm, a known local search technique, within PSO. The suggested methods have been applied to the problem of estimating parameters of a gene network model. Results indicate the effectiveness of the proposed strategies. <s> BIB010 </s> Hybridizing Differential Evolution and Particle Swarm Optimization to Design Powerful Optimizers: A Review and Taxonomy <s> A. Tradeoff Between Exploration and Exploitation <s> This paper proposes an effective particle swarm optimization (PSO)-based memetic algorithm (MA) for the permutation flow shop scheduling problem (PFSSP) with the objective to minimize the maximum completion time, which is a typical non-deterministic polynomial-time (NP) hard combinatorial optimization problem. In the proposed PSO-based MA (PSOMA), both PSO-based searching operators and some special local searching operators are designed to balance the exploration and exploitation abilities. In particular, the PSOMA applies the evolutionary searching mechanism of PSO, which is characterized by individual improvement, population cooperation, and competition to effectively perform exploration. On the other hand, the PSOMA utilizes several adaptive local searches to perform exploitation. First, to make PSO suitable for solving PFSSP, a ranked-order value rule based on random key representation is presented to convert the continuous position values of particles to job permutations. Second, to generate an initial swarm with certain quality and diversity, the famous Nawaz-Enscore-Ham (NEH) heuristic is incorporated into the initialization of population. Third, to balance the exploration and exploitation abilities, after the standard PSO-based searching operation, a new local search technique named NEH_1 insertion is probabilistically applied to some good particles selected by using a roulette wheel mechanism with a specified probability. Fourth, to enrich the searching behaviors and to avoid premature convergence, a simulated annealing (SA)-based local search with multiple different neighborhoods is designed and incorporated into the PSOMA. Meanwhile, an effective adaptive meta-Lamarckian learning strategy is employed to decide which neighborhood to be used in SA-based local search. Finally, to further enhance the exploitation ability, a pairwise-based local search is applied after the SA-based search. Simulation results based on benchmarks demonstrate the effectiveness of the PSOMA. Additionally, the effects of some parameters on optimization performances are also discussed <s> BIB011 </s> Hybridizing Differential Evolution and Particle Swarm Optimization to Design Powerful Optimizers: A Review and Taxonomy <s> A. Tradeoff Between Exploration and Exploitation <s> This paper describes a PSO-Nelder Mead Simplex hybrid multi-objective optimization algorithm based on a numerical metric called µ -fuzzy dominance. Within each iteration of this approach, in addition to the position and velocity update of each particle using PSO, the k-means algorithm is applied to divide the population into smaller sized clusters. The Nelder-Mead simplex algorithm is used separately within each cluster for added local search. The proposed algorithm is shown to perform better than MOPSO on several test problems as well as for the optimization of a genetic model for flowering time control in Arabidopsis. Adding the local search achieves faster convergence, an important feature in computationally intensive optimization of gene networks. <s> BIB012 </s> Hybridizing Differential Evolution and Particle Swarm Optimization to Design Powerful Optimizers: A Review and Taxonomy <s> A. Tradeoff Between Exploration and Exploitation <s> We propose a crossover-based adaptive local search (LS) operation for enhancing the performance of standard differential evolution (DE) algorithm. Incorporating LS heuristics is often very useful in designing an effective evolutionary algorithm for global optimization. However, determining a single LS length that can serve for a wide range of problems is a critical issue. We present a LS technique to solve this problem by adaptively adjusting the length of the search, using a hill-climbing heuristic. The emphasis of this paper is to demonstrate how this LS scheme can improve the performance of DE. Experimenting with a wide range of benchmark functions, we show that the proposed new version of DE, with the adaptive LS, performs better, or at least comparably, to classic DE algorithm. Performance comparisons with other LS heuristics and with some other well-known evolutionary algorithms from literature are also presented. <s> BIB013 </s> Hybridizing Differential Evolution and Particle Swarm Optimization to Design Powerful Optimizers: A Review and Taxonomy <s> A. Tradeoff Between Exploration and Exploitation <s> This paper proposes a hybrid algorithm based on particle swarm optimization (PSO) for a multiobjective permutation flow shop scheduling problem, which is a typical NP-hard combinatorial optimization problem with strong engineering backgrounds. Not only does the proposed multiobjective algorithm (named MOPSO) apply the parallel evolution mechanism of PSO characterized by individual improvement, population cooperation, and competition to effectively perform exploration but it also utilizes several adaptive local search methods to perform exploitation. First, to make PSO suitable for solving scheduling problems, a ranked-order value (ROV) rule based on a random key technique to convert the continuous position values of particles to job permutations is presented. Second, a multiobjective local search based on the Nawaz-Enscore-Ham heuristic is applied to good solutions with a specified probability to enhance the exploitation ability. Third, to enrich the searching behavior and to avoid premature convergence, a multiobjective local search based on simulated annealing with multiple different neighborhoods is designed, and an adaptive meta-Lamarckian learning strategy is employed to decide which neighborhood will be used. Due to the fusion of multiple different searching operations, good solutions approximating the real Pareto front can be obtained. In addition, MOPSO adopts a random weighted linear sum function to aggregate multiple objectives to a single one for solution evaluation and for guiding the evolution process in the multiobjective sense. Due to the randomness of weights, searching direction can be enriched, and solutions with good diversity can be obtained. Simulation results and comparisons based on a variety of instances demonstrate the effectiveness, efficiency, and robustness of the proposed hybrid algorithm. <s> BIB014 </s> Hybridizing Differential Evolution and Particle Swarm Optimization to Design Powerful Optimizers: A Review and Taxonomy <s> A. Tradeoff Between Exploration and Exploitation <s> This paper describes genetic and hybrid approaches for multiobjective optimization using a numerical measure called fuzzy dominance. Fuzzy dominance is used when implementing tournament selection within the genetic algorithm (GA). In the hybrid version, it is also used to carry out a Nelder-Mead simplex-based local search. The proposed GA is shown to perform better than NSGA-II and SPEA-2 on standard benchmarks, as well as for the optimization of a genetic model for flowering time control in rice. Adding the local search achieves faster convergence, an important feature in computationally intensive optimization of gene networks. The hybrid version also compares well with ParEGO on a few other benchmarks. The proposed hybrid algorithm is then applied to estimate the parameters of an elaborate gene network model of flowering time control in Arabidopsis. Overall solution quality is quite good by biological standards. Tradeoffs are discussed between accuracy in gene activity levels versus in the plant traits that they influence. These tradeoffs suggest that data mining the Pareto front may be useful in bioinformatics. <s> BIB015 </s> Hybridizing Differential Evolution and Particle Swarm Optimization to Design Powerful Optimizers: A Review and Taxonomy <s> A. Tradeoff Between Exploration and Exploitation <s> Global optimization process can often be divided into two subprocesses: exploration and exploitation. The tradeoff between exploration and exploitation (T:Er&Ei) is crucial in search and optimization, having a great effect on global optimization performance, e.g., accuracy and convergence speed of optimization algorithms. In this paper, definitions of exploration and exploitation are first given based on information correlation among samplings. Then, some general indicators of optimization hardness are presented to characterize problem difficulties. By analyzing a typical contraction-based three-stage optimization process, optimal contraction theorem is presented to show that T:Er&Ei depends on the optimization hardness of problems to be optimized. T:Er&Ei will gradually lean toward exploration as optimization hardness increases. In the case of great optimization hardness, exploration-dominated optimizers outperform exploitation-dominated optimizers. In particular, random sampling will become an outstanding optimizer when optimization hardness reaches a certain degree. Besides, the optimal number of contraction stages increases with optimization hardness. In an optimal contraction way, the whole sampling cost is evenly distributed in all contraction stages, and each contraction takes the same contracting ratio. Furthermore, the characterization of optimization hardness is discussed in detail. The experiments with several typical global optimization algorithms used to optimize three groups of test problems validate the correctness of the conclusions made by T:Er&Ei analysis. <s> BIB016 </s> Hybridizing Differential Evolution and Particle Swarm Optimization to Design Powerful Optimizers: A Review and Taxonomy <s> A. Tradeoff Between Exploration and Exploitation <s> This paper proposes an effective hybrid algorithm based on differential evolution (DE), namely HDE, to solve multi-objective permutation flow shop scheduling problem (MPFSSP) with limited buffers between consecutive machines, which is a typical NP-hard combinatorial optimization problem with strong engineering background. Firstly, to make DE suitable for solving scheduling problems, a largest-order-value (LOV) rule is presented to convert the continuous values of individuals in DE to job permutations. Secondly, after the DE-based exploration, an efficient local search, which is designed based on the landscape of MPFSSP with limited buffers, is applied to emphasize exploitation. Thus, not only does the HDE apply the parallel evolution mechanism of DE to perform effective exploration (global search) in the whole solution space, but it also adopts problem-dependent local search to perform thorough exploitation (local search) in the promising sub-regions. In addition, the concept of Pareto dominance is used to handle the updating of solutions in sense of multi-objective optimization. Moreover, the convergence property of HDE is analyzed by using the theory of finite Markov chain. Finally, simulations and comparisons based on benchmarks demonstrate the effectiveness and efficiency of the proposed HDE. <s> BIB017 </s> Hybridizing Differential Evolution and Particle Swarm Optimization to Design Powerful Optimizers: A Review and Taxonomy <s> A. Tradeoff Between Exploration and Exploitation <s> Nowadays, a promising way to obtain hybrid metaheuristics concerns the combination of several search algorithms with strong specialization in intensification and/or diversification. The flexible architecture of evolutionary algorithms allows specialized models to be obtained with the aim of providing intensification and/or diversification. The outstanding role that is played by evolutionary algorithms at present justifies the choice of their specialist approaches as suitable ingredients to build hybrid metaheuristics. This paper focuses on hybrid metaheuristics with evolutionary algorithms specializing in intensification and diversification. We first give an overview of the existing research on this topic, describing several instances grouped into three categories that were identified after reviewing specialized literature. Then, with the aim of complementing the overview and providing additional results and insights on this line of research, we present an instance that consists of an iterated local search algorithm with an evolutionary perturbation technique. The benefits of the proposal in comparison to other iterated local search algorithms proposed in the literature to deal with binary optimization problems are experimentally shown. The good performance of the reviewed approaches and the suitable results shown by our instance allow an important conclusion to be achieved: the use of evolutionary algorithms specializing in intensification and diversification for building hybrid metaheuristics becomes a prospective line of research for obtaining effective search algorithms. <s> BIB018
Exploration and exploitation are also referred to as diversification (breadth first) and intensification (depth first), respectively  , BIB018 . In BIB018 , through an extensive investigation of hybrid metaheuristics that are based on EAs, Lozano and Martínez concluded that the use of EAs specializing in diversification and intensification (Er&Ei) to build hybrid metaheuristics becomes a prospective line of research to obtain effective search algorithms. Admittedly, the Tr:Er&Ei is a core of all kinds of optimizers, which can be seen from the ideas of the inventors of different hybrids. Generally, excessive exploitation will depress diversity and induce premature convergence. Excessive exploration will result in slow convergence. Therefore, an appropriate Tr:Er&Ei is essential for efficient problem solving. Chen et al. pointed out that the best Tr:Er&Ei is dominated by the optimization hardness of problems to be optimized, and it will gradually lean toward exploration as optimization hardness increases BIB016 . The diversity of practical problems gives rise to diverse demands on the Tr:Er&Ei. In essence, the hybridization of optimizers is a means of adjusting the Tr:Er&Ei. Usually, various optimizers differ in their exploration and exploitation patterns, as well as the Tr:Er&Ei. For example, an important motivation behind many hybrids, such as MAs, is the synergy of explorative (global) search and exploitative (local) search. However, the rationale in terms of the Tr:Er&Ei is not very clear in embedding-based hybridization and assistance-based hybridization. It is hard to predict the performance of an embedding-based hybrid according to the performance of its parents, since the hybridization is neither a temporal assignment nor a spatial assignment of the parents in search space, but an integration that gives birth to a new holistic optimizer. In this sense, embedding-based hybridization usually implies more empirical attempts and a higher risk of design failure. As for assistance-based hybrids, the assistant parent is expected to improve the search behavior of the master parent, and its contribution to performance improvement has to be attached to the framework of its master, consequently being hard to estimate. Therefore, the Tr:Er&Ei in assistancebased hybrids essentially relies much on a delicate regulation of the Tr:Er&Ei about the master parent. Note that the statement given earlier is not negating the embedding PR or assistance PR, but reminding designers of the two hybridization schemes' basic features. In most cases, incorporation of LSs into explorative optimizers is a promising, feasible, and efficient hybridization pattern to draw a better Tr:Er&Ei, especially to solve complex combinatorial optimization problems. This is one of the important reasons for the success of many efficient hybrid optimizers, especially those that are frequently cited and whose high quality and efficiency have been proved in practice BIB004 BIB001 BIB002 BIB006 BIB005 BIB003  BIB007 . Like other population-based global optimizers, DE and PSO stress on exploration and lack exploitation; therefore, many researchers have tried to hybridize them with LS to strike a balance BIB013 BIB017  BIB011 BIB014 , BIB009 BIB012 BIB015 BIB010 . However, how to incorporate LSs to ensure the expected problem-solving efficiency is still an open issue. See the MA tutorial of Krasnogor and Smith for more design issues on how to balance global search and LS BIB008 . Although we focus in this paper on the hybridization of two parent optimizers, the proposed taxonomy can also be utilized to analyze some intricate hybridization that involves more parents. One can also follow the hierarchical framework that is shown in Fig. 4 to determine primary hybridization factors one by one to design a hybrid that involves more parent optimizers. When designing a hybrid, one should also consider the computation complexity that is possibly introduced by the incorporation of too many optimizers. However, a sophisticated hybridization that is based on multiple parents may be prospective for timeconsuming high-dimensional numerical optimization, since the computational cost that is introduced by complicated hybridization is usually insignificant in contrast to the inherent computation complexity and optimization hardness of high-dimensional problems.