Markov Chain Analysis of Evolution Strategies on a Linear Constraint Optimization Problem
This provides theoretical insights into algorithm stability for evolutionary computation researchers, but it is incremental as it builds on prior studies.
The paper analyzes a (1,λ)-Evolution Strategy on a linear constraint optimization problem, showing that with a constant step-size, the algorithm diverges at a constant rate, and with step-size adaptation, geometric divergence occurs.
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.