Derandomized Evolution Strategies and Local Learning

We develop Evolution Strategies (ES) for Optimization coupled with Local Learning models to tackle problems with expensive cost functions. ES are a class Bioinspired optimization  Algorithms  that mimic natural processes to find optimal designs. In the successful translation of the natural evolution process into effcient and robust computer algorithms, model building plays a central role. Local meta-models are used to replace costly evaluations of the objective function by cheap estimates. We investigate and enhance ESs and we apply them to challenging real world problems.

CMA-ES
The derandomized Evolution Strategy (ES) with Covariance Matrix Adaptation (CMA) adapts the complete covariance matrix of the normal mutation (search) distribution.

Sketch of the different steps charcterizing the algorithm

Local meta-models
The effciency of EAs for expensive problems can be improved by incorporating local meta-models of the cost function. We  enhance CMA-ES with a full quadratic local meta-model to improve the convergence speed of the CMA-ES.
 
Main features
  • CMA-ES is as a robust local search strategy
  • CMA-ES outperforms conventional optimization algorithms on problems that are discontinuous, non-differentiable, multi-modal and noisy
  • CMA-ES effciency is improved by the use of local meta-models
  • It was successfully applied to a considerable number of real world problems

Applications

Given its roboustness and efficiency, CMA-ES results particularly suitable to address parameter identification in real world problems. In fact CMA-ES has been successfully applied to applications ranging from virus and pedestrian traffic, to the study of anguilliform swimming.


People: Mattia Gazzola

Funding: ETH Zurich

Publications:
  • van Rees W.M., Gazzola M., Koumoutsakos P., Optimal shapes for anguilliform swimmers at intermediate Reynolds numbers. Journal of Fluid Mechanics, 722, 2013. (pdf)
  • Gazzola M., van Rees W.M., Koumoutsakos P., C-start: optimal start of larval fish. Journal of Fluid Mechanics, 698:5–18, 2012. (Abstract)(http://dx.doi.org/10.1017/jfm.2011.558(this article is featured in the JFM series: Focus on Fluids) (Cover of JFM)
  • Gazzola M., Vasilyev O.V., Koumoutsakos P., Shape optimization for drag reduction in linked bodies using evolution strategies, Computers and Structures, 6649:210, 2011 (Abstract) (pdf
  • Chatelain P., Gazzola M., Kern S., Koumoutsakos P., Optimization of aircraft wake alleviation schemes through an evolution strategy, Lecture Notes in Computer Science, 6649:210, 2011 (Abstract) (pdf)
  • Gazzola M., Burckhardt C.J., Bayati B., Engelke M., Greber U.F., Koumoutsakos P., A Stochastic Model for Microtubule Motors Describes the In Vivo Cytoplasmic Transport of Human Adenovirus, PLoS Computational Biology, 5, 12, e1000623, 2009 (Abstract) (pdf)
  • Fukagata K., Kern S., Chatelain P., Koumoutsakos P., Kasagi N., Evolutionary optimization of an anisotropic compliant surface for turbulent friction drag reduction, J. Turbulence, Vol. 9, N35, 1-17 (2008) (Abstract) (pdf)
  • Kern S., Koumoutsakos P., Eschler K., Optimization of anguiliform swimming, Physics of Fluids (Gallery of Fluid Motion), 19, 091102-1, 2007 (pdf)
  • S. Kern, P. Koumoutsakos, Simulations of optimized anguilliform swimming, J. Experimental Biology, 209, 4841-4857, 2006 (Abstract) (pdf)
  • N. Hansen, An analysis of mutative sigma-self-adaptation on linear fitness functions, Evolutionary Computation, 14, 255-275, 2006 (Abstract) (pdf)
  • N. Hansen, F. Gemperle, A. Auger, P. Koumoutsakos, When Do Heavy-Tail Distributions Help? Lecture Notes in Computer Science, 4193, 62-71, Springer Berlin, 2006 (Abstract) (pdf)
  • S. Kern, N. Hansen, P. Koumoutsakos, Local Meta-models for Optimization Using Evolution Strategies, Lecture Notes in Computer Science, 4193, 939-948, Springer Berlin, 2006 (Abstract) (pdf)
  • S. Kern, S. D. Mueller, N. Hansen, D. Bueche, J. Ocenasek, P. Koumoutsakos, Learning probability distributions in continuous evolutionary algorithms - a comparative review, Natural Computing, 3(1), 77-112, 2004 (Abstract) (pdf)
  • N. Hansen, S. D. Mueller, P. Koumoutsakos, Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES), Evol. Comput., 11(1), 1-18, 2003 (Abstract) (pdf)
  • N. Hansen, A. Ostermeier, Completely derandomized self-adaptation in evolution strategies, Evol. Comput., 9(2), 159-195, 2001 (Abstract) (pdf)