Documentation/Modules/OptAlgMoCMA

The Elitist Evolution Strategy with Covariance Matrix Adaptation

Summary

This optimization module is an implementation of the elitist Evolution Strategy with Covariance Matrix Adaptation (CMA-ES) for single- and multi-objective optimization (1), however it contains some modifications to the publication.

The algorithm uses one or multiple parents. Each parent generates one or multiple children. The algorithm is elitist: Always the best individuals among all parents and children are selected as parents of the next generation.

This algorithm is designed for continuous variables and can not handle discrete problems. Furthermore, the algorithm is implemented for minimizing a single and multiple objective function(s).

Properties

General

Algorithm	stochastic - deterministic adaptation of the covariance matrix.
Design Variables	Written for continuous variables. No discrete or mixed variables are possible.
Objectives	single- and multi-objective for minimization.
Constraint handling	no
Boundary handling	no
Initialization	Requires at least one of the following: initial solution, initial search region, or bounds.

Connections

Starting at his module	Module requires exactly one connection of type optimization.
Ending at this module	-

Actions

Name	Description
Run	starts the optimization.

Options

The options are currently described in the pop-up help.

Module Description

Initialization

The initial parents are randomly generated within the initial search region (if existing) or otherwise between the bounds.

Optimization

The algorithm contains stochastic processes and operates with a population. Parallelization on the basis of the population size is implemented.

The (mu+lambda)-ES has a population of mu parents and lambda children. The population size depends on the number of objectives and the following values are recommended:

1. mu=1 and lambda >= 1 for single objective optimization.
2. mu=50 and lambda = 1 , for multi-objective optimization (here it is recommended that each parent has only one child).

While evolutionary algorithms typically use the 3 natural inspired operators mutation, recombination and selection, this algorithms uses mutation and selection only.

The selection is elitist: Among all parents and children, the best mu individuals are selected as parents of the next generation.

The mutation is based on a multivariate normal distribution and the mutation distribution is adapted by a deterministic rule: A child x_c is created by mutating the design variables of the parent:

x_c = x_p + z,

where z is a random vector, taken from a normal distribution (i.e. a Gaussian distribution):

z ~ S * N(0,C),

with zero mean and covariance matrix C. The step size S controls the strength and the covariance matrix C the correlation of the mutation. The step size S and the covariance matrix C is adapted by a deterministic rule in order to take into account the convergence of the algorithm towards the minimum. In the beginning of an optimization, the parent may be far from the optimum and large step sizes are preferred. The step size should then decrease while approaching to the minimum.

Usage

... todo

Source Code

ToDo:Link to SVN

References

(1) Igel, C., N. Hansen and S. Roth (2007). Covariance Matrix Adaptation for Multi-objective Optimization. Evolutionary Computation, 15(1), pp.1-28

(2) http://www.lri.fr/~hansen