On stability and convergence of the population-dynamics in differential evolution

Article type: Research Article

Authors: Dasgupta, Sambarta | Das, Swagatam | Biswas, Arijit | Abraham, Ajith^;

Affiliations: Department of Electronics and Telecommunication Engineering, Jadavpur University, Kolkata, India | Center of Excellence for Quantifiable Quality of Service, Norwegian University of Science and Technology, Norway

Note: [] Corresponding author: E-mail: [email protected].

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 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.

Keywords: Differential evolution, numerical optimization, gradient decent search, asymptotic stability

DOI: 10.3233/AIC-2009-0440

Journal: AI Communications, vol. 22, no. 1, pp. 1-20, 2009