What is Differential Evolution?

Differential Evolution (DE) is a population-based, stochastic function optimiser using vector differences for perturbing the population. DE often exhibits a compelling performance advantage over conventional genetic algorithms. GAUL's implementation of DE thus offers a powerful method for optimising vectors.

DE was originally proposed by Kenneth Price and Rainer Storn [Storn 1997], and has not been patented. The crucial idea behind DE is the scheme for generating trial parameter vectors that adds the weighted difference between vectors in the population to a selected vector.

Further Information About Differential Evolution

• Differential Evolution Homepage

Differential Evolution Implemented in GAUL

A flexible and efficient implementation of DE is included in GAUL. This is demonstrated in polynomial_de.c. Numerous similar examples are available. These may be used to compare the DE procedure against some of the other search heuristics provided within GAUL.

Using Differential Evolution with GAUL

The "ga_population_set_differentialevolution_parameters()" function must be used to define some properties for the algorithm. The parameters for this function are:

void ga_population_set_differentialevolution_parameters( population *pop,
                                                         const ga_de_strategy_type strategy,
                                                         const ga_de_crossover_type crossover,
                                                         const int num_perturbed,
                                                         const double weighting_min,
                                                         const double weighting_max,
                                                         const double crossover_factor );

"strategy" can take the values "GA_DE_STRATEGY_BEST", "GA_DE_STRATEGY_RAND" or "GA_DE_STRATEGY_RANDTOBEST" and this determines the selection strategy.

"crossover" can take the values "GA_DE_CROSSOVER_BINOMIAL" or "GA_DE_CROSSOVER_EXPONENTIAL" and this determines the crossover strategy.

"num_perturbed" specifies the number of selected solutions for each perturbation. This may take values of 1, 2 or 3 for "GA_DE_STRATEGY_BEST" or "GA_DE_STRATEGY_RAND" and 1 or 2 for "GA_DE_STRATEGY_RANDTOBEST".

"weighting_min" and "weighting_max" correspond to the F parameter (and also the K parameter in some cases) in the original published description of the algorithm. If these share the same value, they relate to the weighting of perturbations exactly as originally described. If these have different values, they impose bounds for a random selection of weighting factor at the beginning of each generation.

"crossover_factor" corresponds to the CR parameter in the original published description of the algorithm. This relates to the proportion of alleles that are perturbed in a selected solution.

The ideal choice of the above parameters is specific to the optimisation problem but in most cases we recommend exponential crossover, the "best" strategy, one perturbed solution, weighting of around 0.5 (a range is usually preferable) and crossover of around 0.8.

References

• Storn, R. and Price, K., "Differential Evolution - a Simple and Efficient Heuristic for Global Optimization over Continuous Spaces", Journal of Global Optimization (1997) 11:341-359.