Projection-Based Restricted Covariance Matrix Adaptation for High Dimension

Youhei Akimoto 1, * Nikolaus Hansen 1
* Auteur correspondant
1 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 : We propose a novel variant of the covariance matrix adaptation evolution strategy (CMA-ES) using a covariance matrix parameterized with a smaller number of parameters. The motivation of a restricted covariance matrix is twofold. First, it requires less internal time and space complexity that is desired when optimizing a function on a high dimensional search space. Second, it requires less function evaluations to adapt the covariance matrix if the restricted covariance matrix is rich enough to express the variable dependencies of the problem. In this paper we derive a computationally efficient way to update the restricted covariance matrix where the model richness of the covariance matrix is controlled by an integer and the internal complexity per function evaluation is linear in this integer times the dimension, compared to quadratic in the dimension in the CMA-ES. We prove that the proposed algorithm is equivalent to the sep-CMA-ES if the covariance matrix is restricted to the diagonal matrix, it is equivalent to the original CMA-ES if the matrix is not restricted. Experimental results reveal the class of efficiently solvable functions depending on the model richness of the covariance matrix and the speedup over the CMA-ES.
Type de document :
Communication dans un congrès
T. Friedrich and F. Neumann. Genetic and Evolutionary Computation Conference 2016, Jul 2016, Denver, United States. pp.197-204, Proc. ACM-GECCO'16. 〈10.1145/2908812.2908863〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01306551
Contributeur : Youhei Akimoto <>
Soumis le : lundi 25 avril 2016 - 06:30:14
Dernière modification le : vendredi 17 février 2017 - 16:10:34
Document(s) archivé(s) le : mardi 26 juillet 2016 - 10:40:13

Fichier

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

Identifiants

Citation

Youhei Akimoto, Nikolaus Hansen. Projection-Based Restricted Covariance Matrix Adaptation for High Dimension. T. Friedrich and F. Neumann. Genetic and Evolutionary Computation Conference 2016, Jul 2016, Denver, United States. pp.197-204, Proc. ACM-GECCO'16. 〈10.1145/2908812.2908863〉. 〈hal-01306551v1〉

Partager

Métriques

Consultations de la notice

332

Téléchargements de fichiers

293