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.

This entry was posted in EA by cfernandes81. Bookmark the permalink.

About 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s