Fullscreen
Loading...
 
Tao
Print

Proposition des stages autour de CMA-ES - 2011

Stages Master Recherche ou Ecole d'Ingénieurs
Supervisors: Anne Auger , Nikolaus Hansen

Context

Evolution strategies are search or optimization algorithms that search for good solutions in continuous domain search spaces, where good is defined by a given fitness or objective function. Often the fitness function is assumed to be 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 to CMA-ES. More or different topics might be available on request.

What can you learn?

The objective of all our projects is to learn how to address a small, or not so small, scientific question in a scientific way. The typical means for addressing a question are careful thinking, skepticism, a pencil and paper, (basic) math, writing (small) programs, running (small or not so small) computer simulations, careful interpretation of results...and many iterations...

Subjects


Mirroring of proposal solutions

Recently, our group has analyzed the effects of sampling pairwise mirrored solutions around a symmetry point, the distribution mean. This technique resembles the computation of a gradient by central finite differences. The technique can lead to a non-negligible improvement of the convergence rate, see e.g. Brockhoff et al 2010 . Following up these results, we want to investigate the effect of mirroring on the covariance matrix adaptation mechanism. First, possible algorithm variants are considered in the gedankenexperiment. Promising variants will be implemented and empirically investigated under different scenarios.

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

More recently, a rank-based uncertainty (or noise) measurement has been proposed in the context of CMA-ES Hansen et al 2009 . 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 have 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

Prerequisits

  • bacis english knowledge
  • interest in scientific questions
  • basic math and programming skills or talent
  • willingness to learn and improve

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" (this is how we find out you have found this page and read it to the end).


Contributors to this page: hansen and auger .
Page last modified on Wednesday 08 of February, 2012 19:13:21 CET by hansen.