Differential evolution

The introduction to this article provides insufficient context for those unfamiliar with the subject. Please help improve the article with a good introductory style. (October 2009)

Differential evolution (DE) is a method of mathematical optimization of multidimensional functions and belongs to the class of evolution strategy optimizers. DE finds the global minimum of a multidimensional, multimodal (i.e. exhibiting more than one minimum) function with good probability.

The DE community has been growing since the mid 1990s and today more researchers are working on and with DE.^{[citation needed]}

The crucial idea behind DE is a scheme for generating trial parameter vectors. DE adds the weighted difference between two population vectors to a third vector. This way no separate probability distribution has to be used which makes the scheme completely self-organizing. Further information on DE can be found in.^[1]

History

DE grew out of Kenneth Price's attempts to solve the Chebyshev polynomial fitting problem that had been posed to him by Rainer Storn. Genetic Annealing, developed by Price, was the beginning of development for the DE algorithm. The first paper about Genetic Annealing was published in October 1994 issue of Dr. Dobb's Journal. Genetic Annealing is a population-based combinatorial algorithm that realizes an annealing criterion via thresholds driven by the average performance of the population. Soon after this publication, Price was contacted by Storn, who was interested in solving the Chebyshev polynomial fitting problem by Genetic Annealing. After some experiments Price modified the algorithm to use floating-point instead of bit-string encoding and arithmetic vector operations instead of logical ones. This recasting changed Genetic Annealing from a combinatorial into a continuous optimizer.

In this way, Price discovered a procedure of differential mutation. Price and Storn detected that differential mutation combined with discrete recombination and pair-wise selection did not need an annealing factor. The annealing mechanism was removed and the resulting algorithm started the era of Differential Evolution.

Differential Evolution was first described by Price and Storn in the ICSI technical report ("Differential Evolution – a simple and efficient adaptive scheme for global optimization over continuous spaces, 1995"). One year later, the success of DE was demonstrated at the First International Contest on Evolutionary Optimization in May 1996, which was held in conjunction with the 1996 IEEE International Conference on Evolutionary Computation. The algorithm won third place on the proposed benchmarks.

Inspired by these results, Price and Storn wrote an article for Dr. Dobb's Journal ("Differential Evolution: A simple evolution strategy for fast optimization"), which was published in April 1997. Their article for the Journal of Global Optimization ("Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces") was published in December 1997. These papers introduce DE to a large international public and demonstrated the advantages of DE over certain other heuristics for certain problems (the problems were mainly one or two dimensional or trivially separable into 1-dimensional problems). Very good results had been shown on a wide variety of benchmarks.^{[citation needed]}

Price presented DE at the Second International Contest on Evolutionary Optimization in 1997 (Differential Evolution vs. the Functions of the Second ICEO). There, DE was one of the best among competing algorithms. Two years later, in 1999, he summarized the algorithm in the compendium "New Ideas in Optimization".

Storn had been concentrating on various DE applications and had published his web-site^[2] containing source codes and many useful links. In 1998, J. Lampinen set up the official bibliography site,^[3] which furnishes all materials and also some links on DE dated from 1995 up to 2002.

Development

As was stated in "Differential evolution – A simple and efficient adaptive scheme for global optimization over continuous spaces", the key element distinguishing DE from the other population-based techniques is the differential mutation mechanism. The first attempt to guide the differential mutation was presented by Price, where "semi-directed" mutation was realized by a special pre-selection operation. Later, Price analysed the strategies and noted that the strategy may consist of differential mutation and arithmetic crossover. This, in turn, gives the different dynamic effects of search.

The ideas of "directions" were grasped spontaneously by H.-Y. Fan and J. Lampinen. In 2001, they proposed the alternations of the classical strategy (the first strategy suggested by K. Price) with a triangle mutation scheme and, in 2003, the alternations with a weighted directed strategy, where they used two difference vectors. These methods give some improvements, but it is worth noting that the percentage of using novel strategies is quite moderate.

Subsequently, mixed variables were introduced. In 1999, I. Zelinka and J. Lampinen described a simple and, at the same time, an efficient way of handling simultaneously continuous, integer, and discrete variables. They applied this method to design engineering problems and obtained results that outperformed all the other mixed-variables methods used in engineering design. As a particular case of mixed-variable problems, in 2003, V. Feoktistov implemented DE to the binary-continuous large-scale application in the frame of the ROADEF2003 challenge.

Constraints

In order to handle boundary constraints two solutions can be implemented: (1) re-initialization, and (2) periodic mode (or shifting mechanism).

For other constraints (mostly nonlinear functions) penalty methods are used as well as the modification of selection rules, firstly reported for DE in 2001 by Lampinen (and later, in 2004, by Coello Coello et al.).

The question of an algorithm architecture had been untouched during many years. Since the birth of DE, which originally started out as a 1-array optimizer, 2-array was generally accepted, that was justified by its easy parallelization. In 2004, V. Feoktistov revisited the 1-array version in the comparative study of DE species. It led him to discover an intermediate species: transversal DE. From here, some well-known population-based optimizers (for example, particle swarm optimization and free search) can be easily interpreted by analogy with new DE. Moreover, transversal species are well-adapted for parallelization on heterogeneous networks of computers.

See also

Gaussian adaptation

References

• ^  Book about Differential Evolution by its inventors: Price, Storn, and Lampinen
• ^  New book about Differential Evolution by Feoktistov
• ^  Algorithms' Home Page
• ^  Bibliography on DE from 1995 to 2002

External links

• SwarmOps. Parameter tuning / calibration of DE and other optimization methods using a Meta-Optimization approach. Source-code library is for the ANSI C programming language.
• Global Optimization by Differential Evolution and Particle Swarm Methods: Evaluation on Some Benchmark Functions (webng.com) – FORTRAN 77 Codes for DE optimization with a large number of benchmark problems
• Differential Evolution and Particle Swarm Optimization (webng.com) – Performance Evaluation on Benchmark functions
• List of References on Constraint-Handling Techniques used with Evolutionary Algorithms (cs.cinvestav.mx) – Comprehensive bibliography of constraint methods for evolutionary optimization
• Differential Evolution (MathWorld.wolfram.com)
• A SPICE Circuit Optimizer (sourceforge.net) – Parallel version of the Differential Evolution
• Differential Evolution for Continuous Function Optimization, an algorithm by Kenneth Price and Rainer Storn (icsi.Berkeley.edu)
• A forthcoming special issue on DE organized by IEEE Transactions on Evolutionary Computation
• GenerationZ – A multi-threaded differential evolution library