Supervisors:
Anne Auger,
Nikolaus Hansen
Context
{http://en.wikipedia.org/wiki/Evolution_strategy|
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
Solving packing problems
The objective is to apply CMA-ES to packing problems, see
Packomania. The main steps are
- carefully consider the formulation of the actually used fitness function
- design the experiments
- present and interpret the results
- compare the result obtained with result of other competitive methods
- (optional) write a demo software
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 online tests to falsify them on-the-fly
- the surviving solutions become candidate(s) of a more thorough empirical study
More recently, a rank-based uncertainly measurement has been proposed in the context of CMA-ES
ref.
in terms of rank-correlation coeffients, specifically the Kendall tau.