Evolutionary algorithms for continuous-space optimisation

Abstract

From a global viewpoint, evolutionary algorithms (EAs) working on continuous search-spaces can be regarded as homogeneous Markov chains (MCs) with discrete time and continuous state. We analyse from this viewpoint the (1 + 1)EA on the inclined plane fitness landscape, and derive a closed-form expression for the probability of occupancy of an arbitrary target zone, at an arbitrary iteration of the EA. For the hitting-time of an arbitrary target zone, we provide lower and upper bounds, as well as an asymptotic limit. Discretization leads to an MC with discrete time, whose simple structure is exploited to carry out efficient numerical investigations of the theoretical results obtained. The numerical results thoroughly confirm the theoretical ones, and also suggest various conjectures which go beyond the theory.

Keywords:

• evolutionary algorithms with continuous-state space
• Markov transition function
• discretization of Markov chains
• renewal process
• convolution of distributions
• hitting time
• non-commutative binomial

Acknowledgements

The first author acknowledges support from DAAD (German Academic Exchange Service), study and research grant A/10/05445, and from CNCSIS-UEFISCSU, project number 844 PNII - IDEI, code 1778/2008. The second author acknowledges financial support from an Organized Research Grant at Tarleton State University.

Notes

Note

1. The program runs on one of the two cores of an Intel Pentium @ 2.2 GHz.