Supervisors: Anne Auger, Nikolaus Hansen

Context

Evolution strategies are search or optimization methods that search for good solutions in continuous domain search spaces, where good is defined by a given fitness function. Often the fitness function is a black-box, for example simulated by a comparatively complex computer program. Originally inspired by biological evolution almost fifty years ago, evolution strategies have matured and become competitive and comparatively well-understood. The covariance matrix adaptation evolution strategy (CMA-ES) is a modern variant that samples new solutions from a multivariate normal distribution and adapts variances and covariances of this distribution. Many interesting interpretations and justifications of the CMA-ES have been proposed and most recently it has been shown to conduct a natural gradient descent in the distribution space (as opposed to the search space). Furthermore, the CMA-ES has proven to be useful on a wide range of applications such as model calibration and shape optimization. We propose several topics connected the CMA-ES.

Subjects

Injecting solution proposals

The CMA-ES is a carefully designed method that exploits in several steps that the sampled solutions stem from a normal distribution. This is usually an advantage, but can lead to a failure, if solutions from a different distribution are injected in the algorithm. Injecting (good) solutions indeed can be useful in many different contexts. The objective of this work is to identify and understand the mechanisms of failure and find a resolution. The typical steps in this kind of algorithm design task are

• setup of a prototypical, fast to simulate scenario and identification of the problem(s)
• rapid prototyping of possible solutions and of online tests that serve to falsify the solutions on-the-fly
• the surviving solution(s) become candidate(s) of a more thorough empirical study which includes
  • design of test cases
  • design of experiments
  • presentation and interpretation of the results

Reformulation of the rank-based noise measurement of UH-CMA-ES

More recently, a rank-based uncertainly measurement has been proposed in the context of CMA-ES ref. The measurement counts rank changes induced by reevaluation of solutions. This more theoretical task will try to reformulate the algorithm using well-known rank-correlation coeffients, specifically the Kendall tau. For this task both computations have to be deeply understood and formulated within a single algorithm. After the differences has been identified, a second, empirical part, will try to achieve a quantification thereof.

Solving packing problems

The task is to apply CMA-ES to packing problems, see Packomania. The main steps are

• careful consideration of the formulation of the actually used fitness function
• design of the experiments
• presentation and interpretation of the results
• comparison of the result obtained with result of other competitive methods
• (optional) writing a demo software

In case of interest please contact anne.auger {at} lri.fr or nikolaus.hansen {at} lri.fr with the subject line "stage autour de CMA-ES".