×

On stability and convergence of the population-dynamics in differential evolution. (English) Zbl 1200.68185

Summary: 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 canonical Differential Evolution (DE) algorithm with DE/rand/1 type mutation and binomial crossover. Differential Evolution (DE) is well known as a simple and efficient algorithm for global optimization over continuous spaces. Since its inception in 1995, DE has been finding many important applications in real-world optimization problems from diverse domains of science and engineering.
The paper proposes a simple mathematical model of the underlying evolutionary dynamics of a one-dimensional DE-population. The model shows that the fundamental dynamics of each search-agent (parameter vector) in DE employs the gradient-descent type search strategy (although it uses no analytical expression for the gradient itself), with a learning rate parameter that depends on control parameters like scale factor F and crossover rate CR of DE. The stability and convergence behavior of the proposed dynamics is analyzed in the light of Lyapunov’s stability theorems very near to the isolated equilibrium points during the final stages of the search. Empirical studies over simple objective functions are conducted in order to validate the theoretical analysis.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
65K05 Numerical mathematical programming methods
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C52 Methods of reduced gradient type
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI