A Simple Modification in CMA-ES Achieving Linear Time and Space Complexity

Raymond Ros 1 Nikolaus Hansen 1, 2
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 proposes a simple modification of the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) for high dimensional objective functions, reducing the internal time and space complexity from quadratic to linear. The covariance matrix is constrained to be diagonal and the resulting algorithm, sep-CMA-ES, samples each coordinate independently. Because the model complexity is reduced, the learning rate for the covariance matrix can be increased. Consequently, on essentially separable functions, sep-CMA-ES significantly outperforms CMA-ES. For dimensions larger than a hundred, even on the non-separable Rosenbrock function, the sep-CMA-ES needs fewer function evaluations than CMA-ES.
Type de document :
Communication dans un congrès
10th International Conference on Parallel Problem Solving From Nature, Sep 2008, Dortmund, Germany. 2008
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00287367
Contributeur : Raymond Ros <>
Soumis le : lundi 23 juin 2008 - 18:04:18
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : vendredi 28 septembre 2012 - 15:51:01

Fichier

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

Identifiants

  • HAL Id : inria-00287367, version 1

Collections

Citation

Raymond Ros, Nikolaus Hansen. A Simple Modification in CMA-ES Achieving Linear Time and Space Complexity. 10th International Conference on Parallel Problem Solving From Nature, Sep 2008, Dortmund, Germany. 2008. 〈inria-00287367〉

Partager

Métriques

Consultations de la notice

637

Téléchargements de fichiers

505