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

Alexandre Chotard 1, 2, * Anne Auger 1 Nikolaus Hansen 1
* Auteur correspondant
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.
Type de document :
Communication dans un congrès
Amir Hussain; Zhigang Zeng; Nian Zhang. IEEE Congress on Evolutionary Computation, Jul 2014, Beijing, China. 2014
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00977379
Contributeur : Alexandre Chotard <>
Soumis le : vendredi 5 décembre 2014 - 14:44:17
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : lundi 9 mars 2015 - 07:55:29

Fichiers

chotard2014linearconstraint_ca...
Fichiers produits par l'(les) auteur(s)

Identifiants

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

Collections

Citation

Alexandre Chotard, Anne Auger, Nikolaus Hansen. Markov Chain Analysis of Evolution Strategies on a Linear Constraint Optimization Problem. Amir Hussain; Zhigang Zeng; Nian Zhang. IEEE Congress on Evolutionary Computation, Jul 2014, Beijing, China. 2014. 〈hal-00977379v2〉

Partager

Métriques

Consultations de la notice

506

Téléchargements de fichiers

98