Analyzing the Impact of Mirrored Sampling and Sequential Selection in Elitist Evolution Strategies

Anne Auger 1 Dimo Brockhoff 2 Nikolaus Hansen 1, 3, 4
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
2 X - École polytechnique
3 LRI - Laboratoire de Recherche en Informatique
4 MSR - INRIA - Microsoft Research - Inria Joint Centre
Abstract : This paper presents a refined single parent evolution strategy that is derandomized with mirrored sampling and/or uses sequential selection. The paper analyzes some of the elitist variants of this algorithm. We prove, on spherical functions with finite dimension, linear convergence of different strategies with scale-invariant step-size and provide expressions for the convergence rates as the expectation of some known random variables. In addition, we derive explicit asymptotic formulae for the convergence rate when the dimension of the search space goes to infinity. Convergence rates on the sphere reveal lower bounds for the convergence rate of the respective step-size adaptive strategies. We prove the surprising result that the (1+2)-ES with mirrored sampling converges at the same rate as the (1+1)-ES without and show that the tight lower bound for the (1+λ)-ES with mirrored sampling and sequential selection improves by 16% over the (1+1)-ES reaching an asymptotic value of about -0.235.
Type de document :
Communication dans un congrès
Foundations of Genetic Algorithms (FOGA 2011), Jan 2011, Schwarzenberg, Austria. pp.127-138, 2011, 〈10.1145/1967654.1967666〉
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00587507
Contributeur : Dimo Brockhoff <>
Soumis le : mercredi 20 avril 2011 - 15:20:57
Dernière modification le : jeudi 10 mai 2018 - 01:17:48
Document(s) archivé(s) le : jeudi 21 juillet 2011 - 03:08:23

Fichier

foga22v-augerAuthorVersion.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INRIA | UMR8623 | LRI-AO | X | PARISTECH

Citation

Anne Auger, Dimo Brockhoff, Nikolaus Hansen. Analyzing the Impact of Mirrored Sampling and Sequential Selection in Elitist Evolution Strategies. Foundations of Genetic Algorithms (FOGA 2011), Jan 2011, Schwarzenberg, Austria. pp.127-138, 2011, 〈10.1145/1967654.1967666〉. 〈inria-00587507〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

663

Téléchargements de fichiers

193

Contact


archive-ouverte@inria.fr