Visualization of the CMA-ES algorithm in a multi-modal function.

# Derandomized Evolution Strategies and Local Learning

### CMA-ES

### Local meta-models

### 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.

Publications

### 2013

- W. M. van Rees, M. Gazzola, and P. Koumoutsakos, “Optimal shapes for anguilliform swimmers at intermediate Reynolds numbers,” J. Fluid Mech., vol. 722, 2013.

[BibTeX] [Abstract] [PDF] [DOI]

We investigate the optimal morphologies for fast and efficient anguilliform swimmers at intermediate Reynolds numbers, by combining an evolution strategy with three-dimensional viscous vortex methods. We show that anguilliform swimmer shapes enable the trapping and subsequent acceleration of regions of fluid transported along the entire body by the midline travelling wave. A sensitivity analysis of the optimal morphological traits identifies that the width thickness in the anterior of the body and the height of the caudal fin are critical factors for both speed and efficiency. The fastest swimmer without a caudal fin, however, still retains 80 % of its speed, showing that the entire body is used to generate thrust. The optimal shapes share several features with naturally occurring morphologies, but their overall appearances differ. This demonstrates that engineered swimmers can outperform biomimetic swimmers for the criteria considered here.

`@article{rees2013a, author = {Wim M. van Rees and Mattia Gazzola and Petros Koumoutsakos}, doi = {10.1017/jfm.2013.157}, journal = {{J. Fluid Mech.}}, month = {apr}, publisher = {Cambridge University Press ({CUP})}, title = {Optimal shapes for anguilliform swimmers at intermediate {R}eynolds numbers}, url = {http://www.cse-lab.ethz.ch/wp-content/papercite-data/pdf/rees2013a.pdf}, volume = {722}, year = {2013} }`

### 2012

- M. Gazzola, V. W. M. Rees, and P. Koumoutsakos, “C-start: optimal start of larval fish,” J. Fluid Mech., vol. 698, p. 5–18, 2012.

[BibTeX] [Abstract] [PDF] [DOI]

We investigate the C-start escape response of larval fish by combining flow simulations using remeshed vortex methods with an evolutionary optimization. We test the hypothesis of the optimality of C-start of larval fish by simulations of larval-shaped, two- and three-dimensional self-propelled swimmers. We optimize for the distance travelled by the swimmer during its initial bout, bounding the shape deformation based on the larval mid-line curvature values observed experimentally. The best motions identified within these bounds are in good agreement with in vivo experiments and show that C-starts do indeed maximize escape distances. Furthermore we found that motions with curvatures beyond the ones experimentally observed for larval fish may result in even larger escape distances. We analyse the flow field and find that the effectiveness of the C-start escape relies on the ability of pronounced C-bent body configurations to trap and accelerate large volumes of fluid, which in turn correlates with large accelerations of the swimmer.

`@article{gazzola2012a, author = {M. Gazzola and W. M. Van Rees and P. Koumoutsakos}, doi = {10.1017/jfm.2011.558}, journal = {{J. Fluid Mech.}}, month = {feb}, pages = {5--18}, publisher = {Cambridge University Press ({CUP})}, title = {C-start: optimal start of larval fish}, url = {http://www.cse-lab.ethz.ch/wp-content/papercite-data/pdf/gazzola2012a.pdf}, volume = {698}, year = {2012} }`

### 2011

- M. Gazzola, O. V. Vasilyev, and P. Koumoutsakos, “Shape optimization for drag reduction in linked bodies using evolution strategies,” Comput. Struct., vol. 89, iss. 11-12, p. 1224–1231, 2011.

[BibTeX] [Abstract] [PDF] [DOI]

We present results from the shape optimization of linked bodies for drag reduction in simulations of incompressible flow at moderate Reynolds numbers. The optimization relies on the covariance matrix adaptation evolution strategy (CMA-ES) and the flow simulations use vortex methods with the Brinkman penalization to enforce boundary conditions in complex bodies. We exploit the inherent parallelism of CMA-ES, by implementing a multi-host framework which allows for the distribution of the expensive cost function evaluations across parallel architectures, without being limited to one computing facility. This study repeats in silico for the first time Ingo Rechenberg{‘}s pioneering wind tunnel experiments for drag reduction that led to the inception of evolution strategies. The simulations confirm that the results of these experimental studies indicate a flat plate is not the optimal solution for drag reduction in linked bodies. We present the vorticity field of the flow and identify the governing mechanisms for this drag reduction by the slightly corrugated linked plate configuration.

`@article{gazzola2011a, author = {Mattia Gazzola and Oleg V. Vasilyev and Petros Koumoutsakos}, doi = {10.1016/j.compstruc.2010.09.001}, journal = {{Comput. Struct.}}, month = {jun}, number = {11-12}, pages = {1224--1231}, publisher = {Elsevier {BV}}, title = {Shape optimization for drag reduction in linked bodies using evolution strategies}, url = {http://www.cse-lab.ethz.ch/wp-content/papercite-data/pdf/gazzola2011a.pdf}, volume = {89}, year = {2011} }`

- P. Chatelain, M. Gazzola, S. Kern, and P. Koumoutsakos, “Optimization of aircraft wake alleviation schemes through an evolution strategy,” in High performance computing for computational science – VECPAR 2010, Springer, 2011, p. 210–221.

[BibTeX] [Abstract] [PDF] [DOI]

We investigate schemes to accelerate the decay of aircraft trailing vortices. These structures are susceptible to several instabilities that lead to their eventual destruction. We employ an Evolution Strategy to design a lift distribution and a lift perturbation scheme that minimize the wake hazard as proposed in [6]. The performance of a scheme is mea- sured as the reduction of the mean rolling moment that would be induced on a following aircraft; it is computed by means of a Direct Numerical Simulation using a parallel vortex particle code. We find a configuration and a perturbation scheme characterized by an intermediate wavelength {λ} {\sim} 4.64, necessary to trigger medium wavelength instabilities between tail and flap vortices and subsequently amplify long wavelength modes.

`@incollection{chatelain2011a, author = {Philippe Chatelain and Mattia Gazzola and Stefan Kern and Petros Koumoutsakos}, booktitle = {High Performance Computing for Computational Science - {VECPAR} 2010}, doi = {10.1007/978-3-642-19328-6_21}, pages = {210--221}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Optimization of Aircraft Wake Alleviation Schemes through an Evolution Strategy}, url = {http://www.cse-lab.ethz.ch/wp-content/papercite-data/pdf/chatelain2011a.pdf}, year = {2011} }`

### 2009

- M. Gazzola, C. J. Burckhardt, B. Bayati, M. Engelke, U. F. Greber, and P. Koumoutsakos, “A stochastic model for microtubule motors describes the in vivo cytoplasmic transport of human adenovirus,” PLoS Comput. Biol., vol. 5, iss. 12, p. e1000623, 2009.

[BibTeX] [Abstract] [PDF] [DOI]

Cytoplasmic transport of organelles, nucleic acids and proteins on microtubules is usually bidirectional with dynein and kinesin motors mediating the delivery of cargoes in the cytoplasm. Here we combine live cell microscopy, single virus tracking and trajectory segmentation to systematically identify the parameters of a stochastic computational model of cargo transport by molecular motors on microtubules. The model parameters are identified using an evolutionary optimization algorithm to minimize the Kullback-Leibler divergence between the in silico and the in vivo run length and velocity distributions of the viruses on microtubules. The present stochastic model suggests that bidirectional transport of human adenoviruses can be explained without explicit motor coordination. The model enables the prediction of the number of motors active on the viral cargo during microtubule-dependent motions as well as the number of motor binding sites, with the protein hexon as the binding site for the motors.

`@article{gazzola2009a, author = {Mattia Gazzola and Christoph J. Burckhardt and Basil Bayati and Martin Engelke and Urs F. Greber and Petros Koumoutsakos}, doi = {10.1371/journal.pcbi.1000623}, editor = {Herbert M. Sauro}, journal = {{PLoS Comput. Biol.}}, month = {dec}, number = {12}, pages = {e1000623}, publisher = {Public Library of Science ({PLoS})}, title = {A Stochastic Model for Microtubule Motors Describes the In Vivo Cytoplasmic Transport of Human Adenovirus}, url = {http://www.cse-lab.ethz.ch/wp-content/papercite-data/pdf/gazzola2009a.pdf}, volume = {5}, year = {2009} }`

### 2008

- K. Fukagata, S. Kern, P. Chatelain, P. Koumoutsakos, and N. Kasagi, “Evolutionary optimization of an anisotropic compliant surface for turbulent friction drag reduction,” J. Turbul., vol. 9, 2008.

[BibTeX] [Abstract] [PDF] [DOI]

Direct numerical simulation (DNS) of the channel {fl}ow with an anisotropic compliant surface is performed in order to investigate its drag reduction effect in a fully developed turbulent {fl}ow. The computational domain is set to be 3{δ} {\texttimes} 2{δ} {\texttimes} 3{δ} , where {δ} is the channel half-width. The surface is passively driven by the pressure and wall-shear stress {fl}uctuations, and the surface velocity provides a boundary condition for the {fl}uid velocity {fi}eld. An evolutionary optimization method (CMA-ES) is used to optimize the parameters of the anisotropic compliant surface. The optimization identi{fi}es several sets of parameters that result in a reduction of the friction drag with a maximum reduction rate of 8%. The primary mechanism for drag reduction is attributed to the decrease of the Reynolds shear stress (RSS) near the wall induced by the kinematics of the surface. The resultant wall motion is a uniform wave traveling downstream. The compliant wall, with the parameters found in the optimization study, is also tested in a computational domain that is doubled in the streamwise direction. The drag, however, is found to increase in the larger computational domain due to excessively large wall-normal velocity {fl}uctuations.

`@article{fukagata2008a, author = {Koji Fukagata and Stefan Kern and Philippe Chatelain and Petros Koumoutsakos and Nobuhide Kasagi}, doi = {10.1080/14685240802441126}, journal = {{J. Turbul.}}, publisher = {Informa {UK} Limited}, title = {Evolutionary optimization of an anisotropic compliant surface for turbulent friction drag reduction}, url = {http://www.cse-lab.ethz.ch/wp-content/papercite-data/pdf/fukagata2008a.pdf}, volume = {9}, year = {2008} }`

### 2007

- S. Kern, P. Koumoutsakos, and K. Eschler, “Optimization of anguilliform swimming,” Phys. Fluids, vol. 19, iss. 9, p. 91102, 2007.

[BibTeX] [PDF] [DOI]`@article{kern2007a, author = {S. Kern and P. Koumoutsakos and Kristina Eschler}, doi = {10.1063/1.2774981}, journal = {{Phys. Fluids}}, month = {sep}, number = {9}, pages = {091102}, publisher = {{AIP} Publishing}, title = {Optimization of anguilliform swimming}, url = {http://www.cse-lab.ethz.ch/wp-content/papercite-data/pdf/kern2007a.pdf}, volume = {19}, year = {2007} }`

### 2006

- S. Kern and P. Koumoutsakos, “Simulations of optimized anguilliform swimming,” J. Exp. Biol., vol. 209, iss. 24, p. 4841–4857, 2006.

[BibTeX] [Abstract] [PDF] [DOI]

The hydrodynamics of anguilliform swimming motions was investigated using three-dimensional simulations of the fluid flow past a self-propelled body. The motion of the body is not specified a priori, but is instead obtained through an evolutionary algorithm used to optimize the swimming efficiency and the burst swimming speed. The results of the present simulations support the hypothesis that anguilliform swimmers modify their kinematics according to different objectives and provide a quantitative analysis of the swimming motion and the forces experienced by the body. The kinematics of burst swimming is characterized by the large amplitude of the tail undulations while the anterior part of the body remains straight. In contrast, during efficient swimming behavior significant lateral undulation occurs along the entire length of the body. In turn, during burst swimming, the majority of the thrust is generated at the tail, whereas in the efficient swimming mode, in addition to the tail, the middle of the body contributes significantly to the thrust. The burst swimming velocity is 42% higher and the propulsive efficiency is 15% lower than the respective values during efficient swimming. The wake, for both swimming modes, consists largely of a double row of vortex rings with an axis aligned with the swimming direction. The vortex rings are responsible for producing lateral jets of fluid, which has been documented in prior experimental studies. We note that the primary wake vortices are qualitatively similar in both swimming modes except that the wake vortex rings are stronger and relatively more elongated in the fast swimming mode. The present results provide quantitative information of three-dimensional fluid-body interactions that may complement related experimental studies. In addition they enable a detailed quantitative analysis, which may be difficult to obtain experimentally, of the different swimming modes linking the kinematics of the motion with the forces acting on the self-propelled body. Finally, the optimization procedure helps to identify, in a systematic fashion, links between swimming motion and biological function.

`@article{kern2006b, author = {S. Kern and P. Koumoutsakos}, doi = {10.1242/jeb.02526}, journal = {{J. Exp. Biol.}}, month = {dec}, number = {24}, pages = {4841--4857}, publisher = {The Company of Biologists}, title = {Simulations of optimized anguilliform swimming}, url = {http://www.cse-lab.ethz.ch/wp-content/papercite-data/pdf/kern2006b.pdf}, volume = {209}, year = {2006} }`

- N. Hansen, “An analysis of mutative Σ-self-adaptation on linear fitness functions,” Evol. Comput., vol. 14, iss. 3, p. 255–275, 2006.

[BibTeX] [Abstract] [PDF] [DOI]

This paper investigates sigma-self-adaptation for real valued evolutionary algorithms on linear fitness functions. We identify the step-size logarithm log sigma as a key quantity to understand strategy behavior. Knowing the bias of mutation, recombination, and selection on log sigma is sufficient to explain sigma-dynamics and strategy behavior in many cases, even from previously reported results on non-linear and/or noisy fitness functions. On a linear fitness function, if intermediate multi-recombination is applied on the object parameters, the i-th best and the i-th worst individual have the same sigma-distribution. Consequently, the correlation between fitness and step-size sigma is zero. Assuming additionally that sigma-changes due to mutation and recombination are unbiased, then sigma-self-adaptation enlarges sigma if and only if mu < lambda/2, given (mu, lambda)-truncation selection. Experiments show the relevance of the given assumptions.

`@article{hansen2006a, author = {Nikolaus Hansen}, doi = {10.1162/evco.2006.14.3.255}, journal = {{Evol. Comput.}}, month = {sep}, number = {3}, pages = {255--275}, publisher = {{MIT} Press - Journals}, title = {An Analysis of Mutative -Self-Adaptation on Linear Fitness Functions}, url = {http://www.cse-lab.ethz.ch/wp-content/papercite-data/pdf/hansen2006a.pdf}, volume = {14}, year = {2006} }`

### 2004

- S. Kern, S. D. Müller, N. Hansen, D. Büche, J. Ocenasek, and P. Koumoutsakos, “Learning probability distributions in continuous evolutionary algorithms – a comparative review,” Nat. Comput., vol. 3, iss. 1, p. 77–112, 2004.

[BibTeX] [Abstract] [PDF] [DOI]

We present a comparative review of Evolutionary Algorithms that generate new population members by sampling a probability distribution constructed during the optimization process. We present a unifying formulation for five such algorithms that enables us to characterize them based on the parametrization of the probability distribution, the learning methodology, and the use of historical information. The algorithms are evaluated on a number of test functions in order to assess their relative strengths and weaknesses. This comparative review helps to identify areas of applicability for the algorithms and to guide future algorithmic developments.

`@article{kern2004a, author = {Stefan Kern and Sibylle D. M{\"u}ller and Nikolaus Hansen and Dirk B{\"u}che and Jiri Ocenasek and Petros Koumoutsakos}, doi = {10.1023/b:naco.0000023416.59689.4e}, journal = {{Nat. Comput.}}, number = {1}, pages = {77--112}, publisher = {Springer Nature}, title = {Learning probability distributions in continuous evolutionary algorithms {\textendash} a comparative review}, url = {http://www.cse-lab.ethz.ch/wp-content/papercite-data/pdf/kern2004a.pdf}, volume = {3}, year = {2004} }`

### 2003

- N. Hansen, S. D. Müller, and P. Koumoutsakos, “Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES),” Evol. Comput., vol. 11, iss. 1, p. 1–18, 2003.

[BibTeX] [Abstract] [PDF] [DOI]

This paper presents a novel evolutionary optimization strategy based on the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). This new approach is intended to reduce the number of generations required for convergence to the optimum. Reducing the number of generations, i.e., the time complexity of the algorithm, is important if a large population size is desired: (1) to reduce the effect of noise; (2) to improve global search properties; and (3) to implement the algorithm on (highly) parallel machines. Our method results in a highly parallel algorithm which scales favorably with large numbers of processors. This is accomplished by efficiently incorporating the available information from a large population, thus significantly reducing the number of generations needed to adapt the covariance matrix. The original version of the CMA-ES was designed to reliably adapt the covariance matrix in small populations but it cannot exploit large populations efficiently. Our modifications scale up the efficiency to population sizes of up to 10n, where n is the problem dimension. This method has been applied to a large number of test problems, demonstrating that in many cases the CMA-ES can be advanced from quadratic to linear time complexity.

`@article{hansen2003a, author = {Nikolaus Hansen and Sibylle D. M{\"u}ller and Petros Koumoutsakos}, doi = {10.1162/106365603321828970}, journal = {{Evol. Comput.}}, month = {mar}, number = {1}, pages = {1--18}, publisher = {{MIT} Press - Journals}, title = {Reducing the Time Complexity of the Derandomized Evolution Strategy with Covariance Matrix Adaptation ({CMA}-{ES})}, url = {http://www.cse-lab.ethz.ch/wp-content/papercite-data/pdf/hansen2003a.pdf}, volume = {11}, year = {2003} }`

### 2001

- N. Hansen and A. Ostermeier, “Completely derandomized self-adaptation in evolution strategies,” Evol. Comput., vol. 9, iss. 2, p. 159–195, 2001.

[BibTeX] [Abstract] [PDF] [DOI]

This paper puts forward two useful methods for self-adaptation of the mutation distribution – the concepts of derandomization and cumulation. Principle shortcomings of the concept of mutative strategy parameter control and two levels of derandomization are reviewed. Basic demands on the self-adaptation of arbitrary (normal) mutation distributions are developed. Applying arbitrary, normal Mutation distributions is equivalent to applying a general, linear problem encoding. The underlying objective of mutative strategy parameter control is roughly to favor previously selected mutation steps in the future. If this objective is pursued rigorously, a completely derandomized self-adaptation scheme results, which adapts arbitrary normal mutation distributions. This scheme, called covariance matrix adaptation (CMA), meets the previously stated demands. It can still be considerably improved by cumulation – utilizing an evolution path rather than single search steps. Simulations on various test functions reveal local and global search properties of the evolution strategy with and without covariance matrix adaptation. Their performances are comparable only on perfectly scaled functions. On badly scaled, nonseparable functions usually a speed up factor of several orders of magnitude is observed. On moderately mis-scaled functions a speed up factor of three to ten can be expected.

`@article{hansen2001a, author = {Nikolaus Hansen and Andreas Ostermeier}, doi = {10.1162/106365601750190398}, journal = {{Evol. Comput.}}, month = {jun}, number = {2}, pages = {159--195}, publisher = {{MIT} Press - Journals}, title = {Completely Derandomized Self-Adaptation in Evolution Strategies}, url = {http://www.cse-lab.ethz.ch/wp-content/papercite-data/pdf/hansen2001a.pdf}, volume = {9}, year = {2001} }`