Markov Chain Analysis of Evolution Strategies on a Linear Constraint Optimization Problem

04/11/2014
by   Alexandre Chotard, et al.
0

This paper analyses a (1,λ)-Evolution Strategy, a randomised comparison-based adaptive search algorithm, on a simple constraint optimisation problem. The algorithm uses resampling to handle the constraint and optimizes a linear function with a linear constraint. Two cases are investigated: first the case where the step-size is constant, and second the case where the step-size is adapted using path length control. We exhibit for each case a Markov chain whose stability analysis would allow us to deduce the divergence of the algorithm depending on its internal parameters. We show divergence at a constant rate when the step-size is constant. We sketch that with step-size adaptation geometric divergence takes place. Our results complement previous studies where stability was assumed.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset