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.
