Impacts of Invariance in Search: When CMA-ES and PSO Face Ill-Conditioned and Non-Separable Problems

Nikolaus Hansen 1, 2, 3 Raymond Ros 1 Nikolas Mauny 1 Marc Schoenauer 1, 2 Anne Auger 1
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 : This paper investigates the behavior of PSO (particle swarm optimization) and CMA-ES (covariance matrix adaptation evolution strategy) on ill-conditioned functions. The paper also highlights momentum as important common concept used in both algorithms and reviews important invariance properties. On \emph{separable}, ill-conditioned functions, PSO performs very well and outperforms CMA-ES by a factor of up to five. On the same but rotated functions, the performance of CMA-ES is unchanged, while the performance of PSO declines dramatically: on \emph{non-separable}, ill-conditioned functions we find the search costs (number of function evaluations) of PSO increasing roughly proportional with the condition number and CMA-ES outperforms PSO by orders of magnitude. The strong dependency of PSO on rotations originates from random events that are only independent within the given coordinate system. The CMA-ES adapts the coordinate system where the independent events take place and is rotational invariant. We argue that invariance properties, like rotational invariance, are desirable, because they increase the predictive power of performance results by inducing problem equivalence classes.
Document type :
Journal articles
Applied Soft Computing, Elsevier, 2011, 11, pp.5755-5769. 〈10.1016/j.asoc.2011.03.001〉
Liste complète des métadonnées

Cited literature [30 references]  Display  Hide  Download

https://hal.inria.fr/inria-00583669
Contributor : Nikolaus Hansen <>
Submitted on : Wednesday, April 6, 2011 - 11:40:46 AM
Last modification on : Thursday, February 9, 2017 - 3:29:00 PM
Document(s) archivé(s) le : Thursday, November 8, 2012 - 1:31:04 PM

File

hansen2011impacts.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Nikolaus Hansen, Raymond Ros, Nikolas Mauny, Marc Schoenauer, Anne Auger. Impacts of Invariance in Search: When CMA-ES and PSO Face Ill-Conditioned and Non-Separable Problems. Applied Soft Computing, Elsevier, 2011, 11, pp.5755-5769. 〈10.1016/j.asoc.2011.03.001〉. 〈inria-00583669〉

Share

Metrics

Record views

668

Document downloads

1286