Differential Evolution

Differential Evolution(DE) is a population based algorithm whereby new points are created by taking a random member of the population, performing a “crossover” on it with a “partner”, and replacing it in the population if the result is better than the original.

The Mutation Partner #

The partner for crossover is generated as follows. Suppose we have chosen x for crossover.

1. Pick a, b, c randomly from the population distinct from each other and distinct from x
2. Let v = a + F(b - c) where 0<F<1, note that F is not a function v is the partner for x That is, for each i = 1..n, v_i = a_i +F(b_i - c_i)

Crossover #

To cross x with v

for i = 1 to n
      if(random < CR)
             yi = vi
      else
             yi = xi

CR is a crossover bias typically 0.5

Algorithm #

1. Pick a random population
2. Pick a random number x from the population
3. Pick a,b,c from population distinct from each other and x
4. v = a + F( b - c)
5. Crossover x and v with rate CR to form y
6. If y better than x, it replaces x in the population
7. Go to 2

Parameters #

Population size between 5 and 10 times the size of n
F is between 0 and 2
CR is between 0.5 and 0.9 (biased towards mutant)