Algorithms (X,sigma,eta) : quasi-random mutations for Evolution Strategies

Olivier Teytaud 1 Mohamed Jebalia 1 Anne Auger 1
1 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : Randomization is an efficient tool for global optimization. We here define a method which keeps : - the order 0 of evolutionary algorithms (no gradient) ; - the stochastic aspect of evolutionary algorithms ; - the efficiency of so-called "low-dispersion" points ; and which ensures under mild assumptions global convergence with linear convergence rate. We use i) sampling on a ball instead of Gaussian sampling (in a way inspired by trust regions), ii) an original rule for step-size adaptation ; iii) quasi-monte-carlo sampling (low dispersion points) instead of Monte-Carlo sampling. We prove in this framework linear convergence rates i) for global optimization and not only local optimization ; ii) under very mild assumptions on the regularity of the function (existence of derivatives is not required). Though the main scope of this paper is theoretical, numerical experiments are made to backup the mathematical results. Algorithm XSE: quasi-random mutations for evolution strategies. A. Auger, M. Jebalia, O. Teytaud. Proceedings of EA'2005.
Type de document :
Communication dans un congrès
Evolution Artificielle, 2005, Lille, France. Springer (Artificial Evolution), 12 p., 2005
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00000544
Contributeur : Olivier Teytaud <>
Soumis le : lundi 18 février 2013 - 19:06:06
Dernière modification le : mercredi 28 novembre 2018 - 15:36:02
Document(s) archivé(s) le : dimanche 19 mai 2013 - 04:06:00

Fichier

XSEshort2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00000544, version 2

Collections

Citation

Olivier Teytaud, Mohamed Jebalia, Anne Auger. Algorithms (X,sigma,eta) : quasi-random mutations for Evolution Strategies. Evolution Artificielle, 2005, Lille, France. Springer (Artificial Evolution), 12 p., 2005. 〈inria-00000544v2〉

Partager

Métriques

Consultations de la notice

256

Téléchargements de fichiers

127