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

* Corresponding author
1 TAO - Machine Learning and Optimisation
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique
Abstract : This paper analyses a $(1,\lambda)$-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.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [11 references]

https://hal.inria.fr/hal-00977379
Contributor : Alexandre Chotard Connect in order to contact the contributor
Submitted on : Friday, December 5, 2014 - 2:44:17 PM
Last modification on : Thursday, July 8, 2021 - 3:47:52 AM
Long-term archiving on: : Monday, March 9, 2015 - 7:55:29 AM

### Files

chotard2014linearconstraint_ca...
Files produced by the author(s)

### Identifiers

• HAL Id : hal-00977379, version 2
• ARXIV : 1404.3023

### Citation

Alexandre Chotard, Anne Auger, Nikolaus Hansen. Markov Chain Analysis of Evolution Strategies on a Linear Constraint Optimization Problem. IEEE Congress on Evolutionary Computation, http://www.ieee-wcci2014.org/committees.htm, Jul 2014, Beijing, China. ⟨hal-00977379v2⟩

Record views