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.