Accelerating Differential Evolution Using an Adaptive Local Search
IEEE Transactions on Evolutionary ComputationPublished 1 February 2008
Nasimul Noman, Hitoshi Iba
Citations601
SJR quartileQ1
SJR score3.50
SNIP3.12
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that the proposed new version of DE, with the adaptive LS, performs better, or at least comparably, to classic DE algorithm.
Abstract
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.
Keywords
Computer Science
Choice Reviews OnlineGenetic algorithms in search, optimization, and machine learning
49,278 Citations1989
This book brings together the computer techniques, mathematical tools, and research results that will enable both students and practitioners to apply genetic algorithms to problems in many fields.
Particle swarm optimization
47,523 Citations2002James Kennedy, R.C. Eberhart
Journal of Global OptimizationDifferential Evolution – A Simple and Efficient Heuristic for global Optimization over Continuous Spaces
28,706 Citations1997Rainer Storn, Kenneth V. Price
It is demonstrated that the new heuristic approach for minimizing possibly nonlinear and non-differentiable continuous spacefunctions Converges faster and with more certainty than manyother acclaimed global optimization methods.
Genetic Algorithms in Search, Optimization and Machine Learning
17,773 Citations1988David E. Goldberg, David Robson
Artificial intelligenceGenetic Algorithms + Data Structures = Evolution Programs
11,598 Citations1992Zbigniew Michalewicz
Handbook of Genetic Algorithms
7,308 Citations1991Lawrence Davis
Genetic Algorithms + Data Structures = Evolution Programs
5,029 Citations1996Zbigniew Michalewicz
GAs and Evolution Programs for Various Discrete Problems, a Hierarchy of Evolution Programs and Heuristics, and Conclusions.
Evolutionary ComputationCompletely Derandomized Self-Adaptation in Evolution Strategies
4,254 Citations2001Nikolaus Hansen, Andreas Ostermeier
This paper puts forward two useful methods for self-adaptation of the mutation distribution - the concepts of derandomization and cumulation and reveals local and global search properties of the evolution strategy with and without covariance matrix adaptation.
IEEE Transactions on Evolutionary ComputationEvolutionary programming made faster
3,897 Citations1999Xin Yao, Yong Liu +1 more
A "fast EP" (FEP) is proposed which uses a Cauchy instead of Gaussian mutation as the primary search operator and is proposed and tested empirically, showing that IFEP performs better than or as well as the better of FEP and CEP for most benchmark problems tested.
IEEE Transactions on Evolutionary ComputationSelf-Adapting Control Parameters in Differential Evolution: A Comparative Study on Numerical Benchmark Problems
3,055 Citations2006Janez Brest, Sao Greiner +3 more
The results show that the algorithm with self-adaptive control parameter settings is better than, or at least comparable to, the standard DE algorithm and evolutionary algorithms from literature when considering the quality of the solutions obtained.
Foundations of genetic algorithmsReal-Coded Genetic Algorithms and Interval-Schemata
1,645 Citations1993Larry J. Eshelman, J. David Schaffer
It is shown how interval-schemata are analogous to Holland's symbol- schemata and provide a key to understanding the implicit parallelism of real-valued GAs and support the intuition that real-coded GAs should have an advantage over binary coded GAs in exploiting local continuities in function optimization.
Medical Entomology and ZoologyOn Evolution, Search, Optimization, Genetic Algorithms and Martial Arts : Towards Memetic Algorithms
1,514 Citations1989Pablo Moscato
Self-adaptive Differential Evolution Algorithm for Numerical Optimization
1,194 Citations2005A. K. Qin, Ponnuthurai Nagaratnam Suganthan
A novel self-adaptive differential evolution algorithm (SaDE), where the choice of learning strategy and the two control parameters F and CR are not required to be pre-specified.
Soft ComputingA Fuzzy Adaptive Differential Evolution Algorithm
818 Citations2004Jiazeng Liu, Jouni Lampinen
IEEE Transactions on Evolutionary ComputationBalance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling
770 Citations2003Hisao Ishibuchi, Takafumi Yoshida +1 more
This paper shows how the performance of evolutionary multiobjective optimization (EMO) algorithms can be improved by hybridization with local search: the improvement in the convergence speed to the Pareto front and the increase in the computation time per generation.
IEEE Transactions on Evolutionary ComputationMeta-Lamarckian Learning in Memetic Algorithms
655 Citations2004Yew-Soon Ong, Andy J. Keane
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.
Evolutionary ComputationA Computationally Efficient Evolutionary Algorithm for Real-Parameter Optimization
612 Citations2002Kalyanmoy Deb, Ashish Anand +1 more
The proposed generic parent-centric recombination operator (PCX) and a steady-state, elite-preserving, scalable, and computationally fast population-alteration model (G3 model) are proposed and found to consistently and reliably perform better than all other methods used in the study.
A comparative study of differential evolution variants for global optimization
591 Citations2006Efrén Mezura‐Montes, Jesús Velázquez-Reyes +1 more
An empirical comparison of some Differential Evolution variants to solve global optimization problems to identify which one of them is more suitable to solve an optimization problem, depending on the problem's features and also to identify the variant with the best performance, regardless of the features of the problem to be solved.
Real-Parameter Optimization with Differential Evolution
569 Citations2005Jani Rönkkönen, Saku Kukkonen +1 more
This study reports how the differential evolution (DE) algorithm performed on the test bed developed for the CEC05 contest for real parameter optimization.
IEEE Transactions on Evolutionary ComputationSystem design by constraint adaptation and differential evolution
548 Citations1999Rainer Storn
A simple optimization procedure for constraint-based problems is described which works with a simplified cost function or even without one and is well suited for constraint satisfaction, constrained optimization, and design centering problems.
Journal of Global OptimizationA Trigonometric Mutation Operation to Differential Evolution
522 Citations2003Huiyuan Fan, Jouni Lampinen
A new local search operation, trigonometric mutation, is proposed and embedded into the differential evolution algorithm, which enables the algorithm to get a better trade-off between the convergence rate and the robustness.
IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics)Classification of adaptive memetic algorithms: a comparative study
515 Citations2006Yew-Soon Ong, Meng‐Hiot Lim +2 more
This paper presents a classification of memes adaptation in adaptive MAs on the basis of the mechanism used and the level of historical knowledge on the memes employed, and the asymptotic convergence properties of the adaptive M as considered are analyzed.
DEPSO: hybrid particle swarm with differential evolution operator
403 Citations2004Wenjun Zhang, Xiaofeng Xie
A hybrid particle swarm with differential evolution operator, termed DEPSO, which provide the bell-shaped mutations with consensus on the population diversity along with the evolution, while keeping the self-organized particle swarm dynamics, is proposed.
Two improved differential evolution schemes for faster global search
370 Citations2005Swagatam Das, Amit Konar +1 more
Two new, improved variants of differential evolution are presented, shown to be statistically significantly better on a seven-function test bed for the following performance measures: solution quality, time to find the solution, frequency of finding the solutions, and scalability.
Information SciencesDE/EDA: A new evolutionary algorithm for global optimization
326 Citations2004Junwei Sun, Qingfu Zhang +1 more
Experimental results demonstrate that DE/EDA outperforms the DE algorithm and the EDA, and combines global information extracted by EDA with differential information obtained by DE to create promising solutions.
Evolutionary ComputationReal-Coded Memetic Algorithms with Crossover Hill-Climbing
324 Citations2004Manuel Lozano, Francisco Herrera +2 more
Experimental results show that, for a wide range of problems, the method proposed here consistently outperforms other real-coded memetic algorithms which appeared in the literature.
Tokyo Tech Research Repository (Tokyo Institute of Technology)Multi-parent recombination with simplex crossover in real coded genetic algorithms
320 Citations1999Shigeyoshi Tsutsui, M. Yamamura +1 more
Experimental results using test functions showed SPX works well on functions having multimodality and/or epistasis with a medium number of parents: 3-parent on a low dimensional function or 4 parents on high dimensional functions.
Dynamic Multi-Swarm Particle Swarm Optimizer with Local Search
291 Citations2005Jing Liang, Ponnuthurai Nagaratnam Suganthan
The quasi-Newton method is combined to improve its local search ability and the performance of a modified dynamic multi-swarm particle swarm optimizer (DMS-PSO) on the set of benchmark functions provided by CEC2005 is reported.
A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems
280 Citations2002Bernd Freisleben, P. Merz
The combination of local search heuristics and genetic algorithms is a promising approach for finding near-optimum solutions to the traveling salesman problem (TSP) and the results indicate that it is possible to arrive at high quality solutions in reasonable time.
IEEE Transactions on Evolutionary ComputationOn self-adaptive features in real-parameter evolutionary algorithms
252 Citations2001Hans-Georg Beyer, Kalyanmoy Deb
The postulations and population variance calculations explain why self-adaptive genetic algorithms and evolution strategies have shown similar performance in the past and also suggest appropriate strategy parameter values, which must be chosen while applying and comparing different SA-EAs.
Studies in fuzziness and soft computingKnowledge Incorporation in Evolutionary Computation
190 Citations2005Yaochu Jin
This chapter discusses Knowledge Incorporation Through Lifetime Learning, the use of Collective Memory in Genetic Programming, and integrating User Preferences into Evolutionary Multi-Objective Optimization.
Optimizing global-local search hybrids
168 Citations1999David E. Goldberg, Siegfried Voessner
This paper develops a framework for optimizing global-local hybrids of search or optimization procedures and derives a two-basin optimality criterion, which appears to be useful immediately in better understanding the economy of effective hybridization.
UWE Research Repository (UWE Bristol)A Memetic Algorithm with self-adaptive local search: TSP as a case study
163 Citations2000Natalio Krasnogor, James E. Smith
A promising hybridization scheme for a Memetic Algorithm composed of two optimization processes, a Genetic Algorithm and a Monte Carlo method, which comment it successful application to a molecular conformational problem: Protein Folding.
Evolutionary ComputationFitness Landscapes, Memetic Algorithms, and Greedy Operators for Graph Bipartitioning
145 Citations2000Peter Merz, Bernd Freisleben
It will be shown that a simple hybrid multi-start local search exploiting locality in the structure of the graphs is able to find optimum or near optimum solutions very quickly, however, if the problem size increases or the graphs become unstructured, a memetic algorithm (a genetic algorithm incorporating local search) is shown to be much more effective.
Noisy optimization problems - a particular challenge for differential evolution?
128 Citations2004Thiemo Krink, Bogdan Filipič +1 more
It is demonstrated that standard methods of evolutionary optimization are able to outperform differential evolution on noisy problems when the fitness of candidate solutions approaches the fitness variance caused by the noise.
A study on non-random mating and varying population size in genetic algorithms using a royal road function
124 Citations2002Carlos M. Fernandes, Alessandro Pasquale De Rosa
The results suggest that genetic diversity is kept at a higher level by niGAVaPS and nAMGA VaPS, preventing the premature convergence of the algorithms to local optima.
Enhancing differential evolution performance with local search for high dimensional function optimization
122 Citations2005Nasimul Noman, Hitoshi Iba
It is shown that proposed FIR increases the convergence velocity of DE for well known benchmark functions as well as improves the robustness of DE against variation of population.
Improving particle swarm optimization with differentially perturbed velocity
81 Citations2005Swagatam Das, Amit Konar +1 more
A novel scheme of improving the performance of particle swarm optimization by a vector differential operator borrowed from differential evolution (DE), which is shown to be statistically significantly better on a seven-function test suite for the following performance measures.
IEEE Transactions on Evolutionary ComputationSystematic Integration of Parameterized Local Search Into Evolutionary Algorithms
77 Citations2004Neal K. Bambha, Shuvra S. Bhattacharyya +2 more
It is shown that the simulated heating technique better utilizes the given optimization time resources than standard hybrid methods that employ fixed parameters, and that the technique is less sensitive to these parameter settings.
Natural computing seriesA Real-coded Genetic Algorithm using the Unimodal Normal Distribution Crossover
74 Citations2003Isao Ono, Hajime Kita +1 more
A real-coded genetic algorithm using the Unimodal Normal Distribution Crossover (UNDX) that can efficiently optimize functions with epistasis among parameters and some improvements of the UNDX under the guidelines are discussed.
Cybernetics & SystemsCULTURAL ALGORITHMS: COMPUTATIONAL MODELING OF HOW CULTURES LEARN TO SOLVE PROBLEMS: AN ENGINEERING EXAMPLE
64 Citations2005Robert G. Reynolds, Bin Peng
The emergent features are suggested to be what give cultural systems their power to learn and adapt in a completely different problem environment.
Soft ComputingIntegrating adaptive mutations and family competition into genetic algorithms as function optimizer
39 Citations2000Jinn‐Moon Yang, C.-Y. Kao
The proposed approach, based on the family competition and multiple adaptive rules, successfully integrates the decreasing-based Gaussian mutation and self-adaptive Cauchy mutation to balance the exploitation and exploration.
Evolutionary ComputationIntroduction to the Special Issue: Self-Adaptation
19 Citations2001Thomas Bäck
Today, it is widely accepted in the evolutionary computation community that the principle of self-adaptation of strategy parameters, as proposed by Schwefel (1992) is one of the most sophisticated methods to tackle the problem of adjusting the control parameters of an evolutionary algorithm during the course of the optimization process.
A new generation alternation model for differential evolution
18 Citations2006Nasimul Noman, Hitoshi Iba
It is shown that selecting parents for breeding and offspring for survival, Differential Evolution's search capability can be further accelerated, which will be particularly useful for expensive function optimizations.