Reconsidering the Progress Rate Theory for Evolution
Strategies in Finite Dimensions
A. Auger and N. Hansen
Abstract. This paper investigates the limits of the predictions based
on the classical progress rate theory for Evolution Strategies. We
explain on the sphere function why positive progress rates give
convergence in mean, negative progress rates divergence in mean and
show that almost sure convergence can take place despite divergence
in mean. Hence step-sizes associated to negative progress can
actually lead to almost sure convergence. Based on these results we
provide an alternative progress rate definition related to almost
sure convergence. We present Monte Carlo simulations to investigate
the discrepancy between both progress rates and therefore both types
of convergence. This discrepancy vanishes when dimension
increases. The observation is supported by an asymptotic estimation
of the new progress rate definition.
In: Proceedings of the Genetic and Evolutionary Computation Conference
(GECCO 2006), pp.445-452, ACM Press, 2006.
ERRATUM:
Theorem 2, last equation should read
sigma^n = sigma^*_opt ||X_n|| / d (instead sigma^*_opt / ||X_n|| / d)
ADDENDUM: Also for Figure 3, we set lambda=5.
BIBTEX:
@conference{auger2006reconsidering,
title={Reconsidering the progress rate theory for evolution strategies in finite dimensions},
author={Auger, A. and Hansen, N.},
booktitle={Proceedings of the 8th annual conference on genetic and evolutionary computation {GECCO}},
pages={445--452},
year={2006},
organization={ACM}
}