- DE on Dr.Dobb's. An introductory article by Kenneth Price and Rainer Storn. It's old (1997) but very clear
- DE on Wikipedia
- DE homepage. Many implementations and further references.
- Explain the Differential Evolution methodExplain the Differential Evolution method
Create a population of N agents with random weights
While (Brendan hasn't stopped the program and
population diversity is greater than a given threshold)
randomly select Agent_b
randomly select Agent_i (i <> b)
randomly select Agent_j (j <> i and j <> b)
randomly select Agent_k (k <> j and k <> i and k <> b)
Agent_m = Agent_i + F (Agent_j - Agent_k)
Agent_child = crossover(Agent_b, Agent_m)
if (fitness(Agent_child) > fitness(Agent_baseAgent_b)
replace Agent_baseAgent_b with Agent_child
The official page of DE has implementations in many languages (also Java).
I would expect "crossover" to average out the parent function weightings, but how does the variation arise?
In DE there's a "blend" of mutation and crossover.
(in the picture Agent_j = Xa, Agent_k = Xb, Agent_i = Xc. DE's mutation scheme, crossover not shown)
Traditional Evolutionary Strategies mutated vectors by adding zero-mean Gaussian noise to them but, to remain efficient, the mutation scheme had to adjust the standard deviation of the Gaussian noise to suit each parameter (this is also a function of time).
DE use a vector differential Xa - Xb, in place of Gaussian noise, to "perturb" another vector Xc:
Xc_ = Xc + F * (Xa - Xb)
F (differential weight) is a user-supplied scaling factor in the [0.1, 1.2] range.
This form of mutation (with population derived-noise) ensures that the search space is efficiently searched in each dimension.
For example, if the population becomes compact in one dimension, but remains widely dispersed along another, the differentials sampled from it will be small in one dimension yet large in the other. Whatever the case, step sizes will be comparable to the breadth of the region they are being used to search, even as these regions expand and contract during the course of evolution.
(from Dr.Dobb's Journal # 264 April 1997 pg. 22, "Differential Evolution" by K. Price and R. Storn)
Xc_ (Agent_m in the pseudo-code) is used to produce a trial vector via crossover with a random individual (Xi below, Agent_b in the pseudo-code):
Xt = crossover(Xi, Xc_)
The crossover operator produces an offspring by a series of binomial experiments: in this way it's established which parent contributes which trial vector parameter.
The best between Xt and Xi (Agent_child and Agent_b) survives.
Create a population of N agents with random weights
While (Brendan hasn't stopped the program and
population diversity is greater than a given threshold)
randomly select Agent_b
randomly select Agent_i (i <> b)
randomly select Agent_j (j <> i and j <> b)
randomly select Agent_k (k <> j and k <> i and k <> b)
Agent_m = Agent_i + F (Agent_j - Agent_k)
Agent_child = crossover(Agent_b, Agent_m)
if (fitness(Agent_child) > fitness(Agent_base)
replace Agent_base with Agent_child
The official page of DE has implementations in many languages (also Java).
Create a population of N agents with random weights
While (Brendan hasn't stopped the program and
population diversity is greater than a given threshold)
randomly select Agent_b
randomly select Agent_i (i <> b)
randomly select Agent_j (j <> i and j <> b)
randomly select Agent_k (k <> j and k <> i and k <> b)
Agent_m = Agent_i + F (Agent_j - Agent_k)
Agent_child = crossover(Agent_b, Agent_m)
if (fitness(Agent_child) > fitness(Agent_b)
replace Agent_b with Agent_child
The official page of DE has implementations in many languages (also Java).
I would expect "crossover" to average out the parent function weightings, but how does the variation arise?
In DE there's a "blend" of mutation and crossover.
(in the picture Agent_j = Xa, Agent_k = Xb, Agent_i = Xc. DE's mutation scheme, crossover not shown)
Traditional Evolutionary Strategies mutated vectors by adding zero-mean Gaussian noise to them but, to remain efficient, the mutation scheme had to adjust the standard deviation of the Gaussian noise to suit each parameter (this is also a function of time).
DE use a vector differential Xa - Xb, in place of Gaussian noise, to "perturb" another vector Xc:
Xc_ = Xc + F * (Xa - Xb)
F (differential weight) is a user-supplied scaling factor in the [0.1, 1.2] range.
This form of mutation (with population derived-noise) ensures that the search space is efficiently searched in each dimension.
For example, if the population becomes compact in one dimension, but remains widely dispersed along another, the differentials sampled from it will be small in one dimension yet large in the other. Whatever the case, step sizes will be comparable to the breadth of the region they are being used to search, even as these regions expand and contract during the course of evolution.
(from Dr.Dobb's Journal # 264 April 1997 pg. 22, "Differential Evolution" by K. Price and R. Storn)
Xc_ (Agent_m in the pseudo-code) is used to produce a trial vector via crossover with a random individual (Xi below, Agent_b in the pseudo-code):
Xt = crossover(Xi, Xc_)
The crossover operator produces an offspring by a series of binomial experiments: in this way it's established which parent contributes which trial vector parameter.
The best between Xt and Xi (Agent_child and Agent_b) survives.