Eur. Phys. J. B 21, 145-152 (2001)
https://doi.org/10.1007/PL00011116

Stochastic dynamics of adaptive evolutionary search

A study on population-based incremental learning

Institute of Physics, University of Wuerzburg, Am Hubland, 97074 Wuerzburg, Germany

Corresponding author: ^a elvisgalic@hotmail.com

Received: 23 October 2000
Revised: 22 February 2001
Published online: 15 May 2001

Abstract

In this paper the stochastic dynamics of adaptive evolutionary search, as performed by the optimization algorithm Population-Based Incremental Learning, is analyzed with physicists' methods for stochastic processes. The master equation of the process is approximated by van Kampen's small fluctuations assumption. It results in an elegant formalism which allows for an understanding of the macroscopic behaviour of the algorithm together with its fluctuations. We consider the search process to be adaptive since the algorithm iteratively reduces its mutation rate while approaching an optimum. On the one hand, it is this feature which allows the algorithm to quickly converge towards an optimum. On the other hand it results in the possibility to get trapped by a local optimum only. To arrive at a detailed understanding we discuss the influence of fluctuations, as caused by mutation, on this behaviour. We study the algorithm for rather small sytem sizes in order to gain an intuitive understanding of the algorithm's performance.