Markov Chain Analysis of Cumulative Step-size Adaptation on a Linear Constrained Problem

Alexandre Chotard 1, 2, * Anne Auger 1, 2 Nikolaus Hansen 2, 1
* Auteur correspondant
2 TAO - Machine Learning and Optimisation
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : This paper analyzes a (1, λ)-Evolution Strategy, a randomized comparison-based adaptive search algorithm, optimizing a linear function with a linear constraint. The algorithm uses resampling to handle the 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 cumulative step-size adaptation. We exhibit for each case a Markov chain describing the behaviour of the algorithm. Stability of the chain implies, by applying a law of large numbers, either convergence or divergence of the algorithm. Divergence is the desired behaviour. In the constant step-size case, we show stability of the Markov chain and prove the divergence of the algorithm. In the cumulative step-size adaptation case, we prove stability of the Markov chain in the simplified case where the cumulation parameter equals 1, and discuss steps to obtain similar results for the full (default) algorithm where the cumulation parameter is smaller than 1. The stability of the Markov chain allows us to deduce geometric divergence or convergence , depending on the dimension, constraint angle, population size and damping parameter, at a rate that we estimate. Our results complement previous studies where stability was assumed.
Type de document :
Article dans une revue
Evolutionary Computation, Massachusetts Institute of Technology Press (MIT Press), 2015, 23 (4), pp. 611-640 〈10.1109/4235.873238〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01215727
Contributeur : Alexandre Chotard <>
Soumis le : mercredi 14 octobre 2015 - 17:37:12
Dernière modification le : samedi 18 février 2017 - 01:09:44
Document(s) archivé(s) le : lundi 18 janvier 2016 - 05:44:26

Fichiers

p1236-single.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Alexandre Chotard, Anne Auger, Nikolaus Hansen. Markov Chain Analysis of Cumulative Step-size Adaptation on a Linear Constrained Problem. Evolutionary Computation, Massachusetts Institute of Technology Press (MIT Press), 2015, 23 (4), pp. 611-640 〈10.1109/4235.873238〉. 〈hal-01215727〉

Partager

Métriques

Consultations de la notice

572

Téléchargements de fichiers

81