Differential Evolution

Differential Evolution or DE for short, is a stochastic global search optimization algorithm.

It is a type of evolutionary algorithm and is related to other evolutionary algorithms such as the genetic algorithm. Unlike the genetic algorithm that represents candidate solutions using sequences of bits, Differential Evolution is designed to work with multi-dimensional real-valued candidate solutions for continuous objective functions.

Differential evolution (DE) is arguably one of the most powerful stochastic real-parameter optimization algorithms in current use.

Differential Evolution: A Survey of the State-of-the-Art, 2011.

The algorithm does not make use of gradient information in the search, and as such, is well suited to non-differential nonlinear objective functions.

The algorithm works by maintaining a population of candidate solutions represented as real-valued vectors. New candidate solutions are created by making modified versions of existing solutions that then replace a large portion of the population each iteration of the algorithm.

New candidate solutions are created using a “strategy” that involves selecting a base solution to which a mutation is added, and other candidate solutions from the population from which the amount and type of mutation is calculated, called a difference vector. For example, a strategy may select a best candidate solution as the base and random solutions for the difference vector in the mutation.

DE generates new parameter vectors by adding the weighted difference between two population vectors to a third vector.

Differential Evolution: A Simple and Efficient Heuristic for global Optimization over Continuous Spaces, 1997.

Base solutions are replaced by their children if the children have a better objective function evaluation.

Finally, after we have built up a new group of children, we compare each child with the parent which created it (each parent created a single child). If the child is better than the parent, it replaces the parent in the original population.

— Page 51, Essentials of Metaheuristics, 2011.

Mutation is calculated as the difference between pairs of candidate solutions that results in a difference vector that is then added to the base solution, weighted by a mutation factor hyperparameter set in the range [0,2].

Not all elements of a base solution are mutated. This is controlled via a recombination hyperparameter and is often set to a large value such as 80 percent, meaning most but not all variables in a base solution are replaced. The decision to keep or replace a value in a base solution is determined for each position separately by sampling a probability distribution such as a binomial or exponential.

A standard terminology is used to describe differential strategies with the form:

  • DE/x/y/z

Where DE stands for “differential evolution,” x defines the base solution that is to be mutated, such as “rand” for random or “best” for the best solution in the population. The y stands for the number of difference vectors added to the base solution, such as 1, and z defines the probability distribution for determining if each solution is kept or replaced in the population, such as “bin” for binomial or “exp” for exponential.

The general convention used above is DE/x/y/z, where DE stands for “differential evolution,” x represents a string denoting the base vector to be perturbed, y is the number of difference vectors considered for perturbation of x, and z stands for the type of crossover being used (exp: exponential; bin: binomial).

Differential Evolution: A Survey of the State-of-the-Art, 2011.

The configuration DE/best/1/bin and DE/best/2/bin are popular configurations as they perform well for many objective functions.