Differential Evolution
Rainer Storn and Kenneth Price introduced the Differential Evolution algorithm (DE) in 1995 as a very simple population based, stochastic function minimizer [1] . The authors designed this algorithm with the aim of fulfilling four requirements:
- It should have the ability to deal with non-differentiable, non-linear and multimodal functions. Thus the algorithm was designed to be a stochastic direct search method.
- A parallelizable algorithm was desired. Consequently, they developed a population based algorithm where the perturbation of each chromosome could be applied independently.
- They wanted it to be easy to use and with few control parameters. Therefore, they designed a self-organizing algorithm that employs information from the population to alter the search space.
- An algorithm with good convergence properties was necessary. This requirement has been fulfilled as is demonstrated by the large number of publications that use the DE with successful results.
The DE algorithm begins the search process by creating a random population of N chromosomes. The basic strategy employed consists in the generation of new chromosome vectors according to the following steps:
- Mutation: for each target vector of the population, a new chromosome named trial vector is generated by adding the weighted difference of two randomly chosen chromosome vectors to a third one, hereafter the base vector. The parameter F is a real and constant factor which scale the influence of the set of pairs of solutions selected to calculate the mutation value.
- Crossover: a recombination or crossover operator could be applied to the trial vector in order to increase the diversity of the population. The behavior of this operator consists in choosing some genes from the target vector and some from the trial vector. Parameter CR regulates the execution of this operator, controlling the influence of the target over the generation of the offspring. Higher values for CR imply less influence of the target.
- Selection: after the application of the mutation and crossover operator, the trial vector is compared to the target vector using a greedy criterion. If the trial vector yields a better objective function value than the target vector, then the trial vector replaces the target one in the population. Otherwise, the target vector remains in the population.
The DE algorithm bases its behavior on the self-adaptation of the mutation operator, which uses information about the distribution of the population in the search space in order to obtain a new population. There is no control on the step sizes, because they depend on the location of the selected individuals.
The DE version commented above is the original one and it is also known as DE/rand/1/bin, where rand indicates that the base vector is randomly chosen from the population, the number 1 indicates that one difference vector is used and bin is the crossover strategy, in this case, binomial strategy. Many other variants of the DE algorithm may be found in the literature with different mutation and crossover strategies and with more than one difference vector. For example, some mutation strategies are best, current-to-best, current-to-rand, etc. [2] . In terms of crossover, the exponential crossover operator has provided successful results and in [3] the authors present two more variants.
In the JEAF framework the mutation and crossover strategies implemented are the ones indicated in this class diagram.
The simple schema of the Differential Evolution allows the development of different versions. In JEAF, the following differential evolution variants are implemented:
- JADE, a self adaptive differential evolution [4] .
- A multimodal differential evolution variant [5] .
Here, there is several configuration examples files for the different variants of the DE algorithm implemented in JEAF:
- A configuration file for the canonical version of the DE algorithm DE/rand/1/bin
- A configuration file of the JADE variant
- A configuration file for the multimodal variant
- Differential Evolution Homepage - www.icsi.berkeley.edu/~storn/code.htm