On stability and convergence of the population-dynamics in differential evolution
AI CommunicationsPublished 1 January 2009
Sambarta Dasgupta, Swagatam Das, Arijit Biswas, Ajith Abraham
Citations84
SJR quartileQ3
SJR score0.37
SNIP0.71
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
The paper proposes a simple mathematical model of the underlying evolutionary dynamics of a one-dimensional DE-population and shows that the fundamental dynamics of each search-agent in DE employs the gradient-descent type search strategy, with a learning rate parameter that depends on control parameters like scale factor F and crossover rate CR of DE.
Abstract
Theoretical analysis of the dynamics of evolutionary algorithms is believed to be very important to understand the search behavior of evolutionary algorithms and to develop more efficient algorithms. In this paper we investigate the dynamics of a can
Keywords
Computer Science
IEEE Transactions on Evolutionary ComputationThe particle swarm - explosion, stability, and convergence in a multidimensional complex space
8,768 Citations2002Maurice Clerc, James Kennedy
Practical Methods of Optimization
6,403 Citations2000R. Ian Fletcher
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.
Information Processing LettersThe particle swarm optimization algorithm: convergence analysis and parameter selection
2,597 Citations2003Ioan-Cristian Trelea
The particle swarm optimization algorithm is analyzed using standard results from the dynamic system theory and graphical parameter selection guidelines are derived, resulting in results superior to previously published results.
IEEE Transactions on Neural NetworksConvergence analysis of canonical genetic algorithms
1,456 Citations1994Günter Rudolph
This paper analyzes the convergence properties of the canonical genetic algorithm with mutation, crossover and proportional reproduction applied to static optimization problems and shows variants of CGA's that always maintain the best solution in the population are shown to converge to the global optimum due to the irreducibility property of the underlying original nonconvergent CGA.
A comparative study of differential evolution, particle swarm optimization, and evolutionary algorithms on numerical benchmark problems
1,205 Citations2005Jørgen Vesterstrøm, René Thomsen
The results from this study show that DE generally outperforms the other algorithms, however, on two noisy functions, both DE and PSO were outperformed by the EA.
Nonlinear Dynamical Systems and Control: A Lyapunov-Based Approach
863 Citations2008Wassim M. Haddad, V. Chellaboina
Medical Entomology and ZoologyThe Simple Genetic Algorithm: Foundations and Theory
701 Citations1999Michael D. Vose
Although Michael D. Vose describes the SGA in terms of heuristic search, the book is not about search or optimization perse.
Genetic Algorithms: Principles and Perspectives: A Guide to GA Theory
562 Citations2002Colin R. Reeves, Jonathan E. Rowe
This chapter discusses GAs as Markov processes as well as the Dynamical Systems Model, which helps clarify the role of language in the development of GA performance.
Handbook of Metric Fixed Point Theory
525 Citations2001W. A. Kirk, Brailey Sims
The self-adaptive Pareto differential evolution algorithm
401 Citations2003Hussein A. Abbass
The emphasis of this paper is to analyze the dynamics and behavior of SPDE, a new version of PDE with self-adaptive crossover and mutation that is very competitive with other EMO algorithms.
IEEE Transactions on Evolutionary ComputationStability analysis of the particle dynamics in particle swarm optimizer
371 Citations2006Visakan Kadirkamanathan, Kirusnapillai Selvarajah +1 more
Simulation results confirm the prediction from theory that stability of the particle dynamics requires increasing the maximum value of the random parameter when the inertia factor is reduced.
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.
Lecture notes in computer scienceSelf-adaptive Differential Evolution
265 Citations2005Mahamed G. H. Omran, Ayed Salman +1 more
A self-adaptive DE (SDE) is proposed where parameter tuning is not required and the performance of SDE is investigated and compared with other versions of DE.
IEEE Transactions on Evolutionary ComputationAdaptive Computational Chemotaxis in Bacterial Foraging Optimization: An Analysis
251 Citations2009Sambarta Dasgupta, Swagatam Das +2 more
This paper presents a mathematical analysis of the chemotactic step in BFOA from the viewpoint of the classical gradient descent search, and investigates an interesting application of the proposed adaptive variants of BFI to the frequency-modulated sound wave synthesis problem, appearing in the field of communication engineering.
Artificial IntelligenceTowards an analytic framework for analysing the computation time of evolutionary algorithms
181 Citations2003Jun He, Xin Yao
The first step towards a systematic comparative study among different EAs and their first hitting times has been made in the paper, and the framework is built on the absorbing Markov chain model of evolutionary algorithms.
Exact analysis of the sampling distribution for the canonical particle swarm optimiser and its convergence during stagnation
84 Citations2007Riccardo Poli, David S. Broomhead
A novel method is introduced, which allows one to exactly determine all the characteristics of a PSO's sampling distribution and explain how they change over any number of generations, in the presence stochasticity.
Evolutionary ComputationAnalysis of Convergence of an Evolutionary Algorithm with Self-Adaptation using a Stochastic Lyapunov function
53 Citations2003Mikhail A. Semenov, Dmitri A. Terkel
This paper analyses the convergence of evolutionary algorithms using a technique which is based on a stochastic Lyapunov function and developed within the martingale theory, and shows that the convergence velocity of the evolutionary algorithm with self-adaptation is asymptotically exponential, similar to the Velocity of the optimal deterministic algorithm on the class of unimodal functions.
Lecture notes in computer scienceAdaptive Pareto Differential Evolution and Its Parallelization
50 Citations2004Daniela Zaharie, Dana Petcu
An adaptive Pareto differential evolution algorithm for multi-objective optimization is proposed and its effectiveness on approximating the Pare to front is compared with that of SPEA and of SPDE.
Lecture notes in computer scienceOn the “Explorative power” of ES/EP-like algorithms
33 Citations1998Hans-Georg Beyer
It is shown that the sometimes invoked model of a perturbed gradient search does not seem to give an appropriate picture of the search process, and the search behavior is described as the antagonism of exploitation and exploration, where exploitation works in one dimension, whereas the exploration is a random walk on a (N−1)-dimensional manifold in the search space.
On the Dynamics of EAs without Selection.
24 Citations1998Hans-Georg Beyer
This paper investigates the dynamics of evolutionary algorithms (EAs) without tness based selection (constant tness) and finds that such algorithms exhibit a behavior similar to the MISR eeect (mutation-induced speciation by recombination) which has been found in the analysis of (== D ;) evolution strategies.
Hybrid methods using evolutionary algorithms for on-line training
18 Citations2002George D. Magoulas, Vassilis P. Plagianakos +1 more
A novel hybrid evolutionary approach is presented for improving the performance of neural network classifiers in slowly varying environments using both the global search capabilities of evolutionary strategies and the effectiveness of online gradient descent.
ViewOn The Dynamics Of Evolutionary Multi-objective Optimization
15 Citations2002Tatsuya Okabe, Yaochu Jin +1 more
It is found that the movement of the individuals on the FS is strongly dependent on the characteristics of the projected distribution, and the mapping of a normal distribution in the parameter space (PS) onto the FS.
Evolutionary multi-objective optimisation with a hybrid representation
14 Citations2004Tatsuya Okabe, Yaochu Jin +1 more
A hybrid representation, composed of binary and real-valued representations for multi-objective optimisation problems, is proposed, which shows that the hybrid representation exhibits better and more stable performance than the single binary or real- valued representation.
Foundations of genetic algorithmsOrder Statistics for Convergence Velocity Analysis of Simplified Evolutionary Algorithms
9 Citations1995Thomas Bäck
The order statistics approach turns out to be a very useful theoretical framework for the derivation of quite general results on the convergence velocity of evolutionary algorithms, including upper bounds on the convergence velocity of evolutionary algorithms.