Explain the Differential Evolution method

Question

Can someone please explain the Differential Evolution method? The Wikipedia definition is extremely technical.

A dumbed-down explanation followed by a simple example would be appreciated :)

Answer 1

Here's a simplified description. DE is an optimisation technique which iteratively modifies a population of candidate solutions to make it converge to an optimum of your function.

You first initialise your candidate solutions randomly. Then at each iteration and for each candidate solution x you do the following:

1. you produce a trial vector: v = a + ( b - c ) / 2, where a, b, c are three distinct candidate solutions picked randomly among your population.
2. you randomly swap vector components between x and v to produce v'. At least one component from v must be swapped.
3. you replace x in your population with v' only if it is a better candidate (i.e. it better optimise your function).

(Note that the above algorithm is very simplified; don't code from it, find proper spec. elsewhere instead)

Unfortunately the Wikipedia article lacks illustrations. It is easier to understand with a graphical representation, you'll find some in these slides: http://www-personal.une.edu.au/~jvanderw/DE_1.pdf .

It is similar to genetic algorithm (GA) except that the candidate solutions are not considered as binary strings (chromosome) but (usually) as real vectors. One key aspect of DE is that the mutation step size (see step 1 for the mutation) is dynamic, that is, it adapts to the configuration of your population and will tend to zero when it converges. This makes DE less vulnerable to genetic drift than GA.