Local and global order 3/2 convergence of a surrogate evolutionary algorithm
Anne Auger, Marc Schoenauer, Olivier Teytaud · 2005
A Quasi-Monte-Carlo method based on the computation of a surrogate model of the fitness function is proposed, and its convergence at super-linear rate 3/2 is proved under rather mild assumptions on the fitness function -- but assuming that the starting point lies within a small neighborhood of a global maximum. A memetic algorithm is then constructed, that performs both a random exploration of the search space and the exploitation of the best-so-far points using the previous surrogate local algorithm, coupled through selection. Under the same mild hypotheses, the global convergence of the memetic algorithm, at the same 3/2 rate, is proved.