EUVIMEDEUVIMED entdecken
Crossref

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

Alexandre Chotard, Anne Auger, Nikolaus Hansen

Evolutionary Computation · 2015-12 · 23 (4) · 611-640

DOI: 10.1162/evco_a_00166 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Evolutionary Computation, 2015-12. Verfasst von Alexandre Chotard und 2 weiteren Autor:innen. Beteiligte Einrichtung: Univ. Paris-Sud, LRI, Rue Noetzlin, Bat 660, 91405 Orsay Cedex France chotard@lri.fr. Hauptthemen laut MEDLINE: Algorithms, Biological Evolution, Markov Chains. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 19 Literaturangaben.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

This paper analyzes a [Formula: see text]-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 behavior 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 behavior. 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.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

AlgorithmsBiological EvolutionMarkov ChainsComputational BiologyComputer SimulationHumansLinear ModelsModels, Statistical

Stichwörter der Autor:innen

CMA-ESContinuous optimizationconstrained problemcumulative step-size adaptationevolution strategies

Autor:innen und Institutionen

  • Univ. Paris-Sud, LRI, Rue Noetzlin, Bat 660, 91405 Orsay Cedex France chotard@lri.fr.
  • Inria, Univ. Paris-Sud, LRI, Rue Noetzlin, Bat 660, 91405 Orsay Cedex France auger@lri.fr.
  • Inria, Univ. Paris-Sud, LRI, Rue Noetzlin, Bat 660, 91405 Orsay Cedex France hansen@lri.fr.

Zitieren

APA

Chotard, A., Auger, A., & Hansen, N. (2015). Markov Chain Analysis of Cumulative Step-Size Adaptation on a Linear Constrained Problem. Evolutionary Computation, 23(4), 611-640. https://doi.org/10.1162/evco_a_00166

Vancouver

Chotard A, Auger A, Hansen N. Markov Chain Analysis of Cumulative Step-Size Adaptation on a Linear Constrained Problem. Evolutionary Computation. 2015;23(4):611-640. doi:10.1162/evco_a_00166

BibTeX
@article{Chotard2015,
  author = {Chotard, Alexandre and Auger, Anne and Hansen, Nikolaus},
  title = {Markov Chain Analysis of Cumulative Step-Size Adaptation on a Linear Constrained Problem},
  journal = {Evolutionary Computation},
  year = {2015},
  volume = {23},
  number = {4},
  pages = {611--640},
  doi = {10.1162/evco_a_00166}
}
Kostenlos starten →