Differential Evolution

In the last seminar, we discussed Differential Evolution (DE), a population-based search algorithm for global optimization proposed by Price and Storn in 1995 [1]. DE is a type of Evolutionary Algorithm, and it solves, efficiently, optimization functions with real-valued parameters, although there are proposals for integer and binary optimization. The algorithm is similar to an Evolution Strategy (ES). However, and this appears to be DE’s main strength, the algorithm overcomes some of the difficulties that a standard ES is not able to deal with. This is due to its specific mutation operator, which is not only remarkably simple, but also very effective.

As stated in [2], an efficient mutation scheme for real parameter optimization should:

–  Use a zero-mean distribution for generating mutation vectors.

–  Dynamically scale the distribution to suit each parameter.

–  Correlate mutations to ensure rotational invariance.

While ES tries to satisfy these criteria using self-adaptation— and its solution to rotational invariance creates scalability problems —, DE’s core is a simple rule that uses three solutions to generate a new solution, performing a kind of recombination and mutation. By this peculiar linear combination of three vectors, DE’s mutation has zero-mean distribution, dynamically scales the distribution to each parameter and, most of all, it is rotational invariant, i.e., its performance is not affected when the principal axes of a separable function are arbitrarily rotated away from coincidence with coordinate axes, which means that it performs better than standard ES in non-separable functions (i.e., with epistasis). Furthermore, DE is resilient to noise, it is suited for the optimization of non-stationary functions and it is inherently parallel. On the other, and as far as I know, there is still no convergence proof for DE. However, DE works, and it seems to work quite well.

In this page, you may find information about DE, like C and Matlab code, demos and other interesting stuff.

[1] Price and Storn, “Differential Evolution – a simple and efficient adaptive scheme for global optimization over continuous spaces”, ICSI Technical Report, 1995.

[2] “New Ideas in Optimization”, Corne, Dorigo and Glover, eds., 1999.

Esta entrada fue publicada en EA por cfernandes81. Guarda el enlace permanente.

Acerca de cfernandes81

Carlos M. Fernandes was born in Luanda in 1973 and lives in between Lisbon, Portugal, and Granada, Spain. He graduated (Technical University of Lisbon, 1998) in Electrotechnics Engineering and owns a master degree in the same field since 2002 (Technical University of Lisbon). He is currently pursuing a Ph.d. on Bio-inspired Computing. From 2001 to 2005 he was an assistant at Instituto Politécnico de Setúbal. (He is also a photographer and photography teacher.) Bio-inspired Computing is his major field of research: Genetic Algorithms, Estimation of Distribution Algorithms, Ant Colony Optimization, Particle Swarm Optimization and other metaheuristics. He is particularly interested in the hybridization of Bio-inspired Computing techniques with Self-Organization, Self-Organized Criticality Models and diversity maintenance strategies. In the present, Dynamic Optimization Problems are his mains target for applying such techniques. website: www.carlosmfernandes.com email: c.m.fernandes.photo@gmail.com

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s