The differential evolution (DE)^{[1]} algorithm comes from a class of algorithms based upon evolutionary principles. To start the process, an initial "population" of random vectors {p_{k,0}} is created that all satisfy the parameter constraints. At each iteration (called a "generation") of the process, new vectors are obtained from the previous set using the following concepts::
Mutation. A new vector is formed via a combination of existing vectors of the form where r1, r2 and r3 are randomly chosen integers.
Recombination (also called crossover). A candidate "child" vector is formed by taking some (randomly selected) parameter values directly from the parent P_{G} , and the rest from the differential combination vector v_{G} i.e.,
Selection. A parent vector is replaced with a child vector if the objective function is reduced. Otherwise, additional children are created and tested until either one is found that reduces the objective function or some maximum number of offspring is reached. If no child is more "fit" than the parent, the parent passes to the new generation (if they are not eliminated by the following aging criterion).
Aging. A vector can only "survive" for a limited number of generations, regardless of its "fitness".
In addition to the basic DE algorithm (named DE/rand/l), several schemes are implemented that determine how the subsequent generation is constructed ( r1, r2, r3, and r4 are randomly chosen integers).
Scheme Name | Expression |
---|---|
DE/rand/1 | |
DE/best/1 | |
DE/best/2 | |
DE/rand-to-best/1 |
Analyst exposes several parameters for DE:
- α in the above table. This value determines how many of the potential trial experiments differ from each other. This number is typically between 0.0 and 2.0. It is not recommended to set this value to exactly 1.0 as this reduces the number of different potential experiments. A larger amplification factor increases the probability for escaping a local optimum, but the value of >1.0 can cause the convergence speed to decrease. If one suspects a local optimum has been found the amplification factor should be increased.
- use in the recombination portion of the algorithm. Typical values are between 0.0 and 1.0, but it is not recommended to set it to 1.0 exactly as the risk of permanent stagnation is increased. A larger crossover probability often speeds up convergence.
- λ in the above table. Only used for DE/rand-to-best/l scheme.
- determines the size of the population of a generation. It is expressed in terms of size of population per variable (dimension). So if you are optimizing over 2 parameters, and this values is 5, there will be 10 experiments per iteration. Making this number too small (<3) can significantly reduce the number of potential trial experiments and therefore increase the like hood of stagnation.
- variant of differential evolution. see the above table
^{[1] }R. Storn and K. Price, "Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces." J. Global Optim., 11, 1997, pp. 341-359.
Please send email to awr.support@ni.com if you would like to provide feedback on this article. Please make sure to include the article link in the email.