Differential evolution

From Wikipedia, the free encyclopedia

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

This article or section is written like a personal reflection or essay and may require cleanup.
Please help improve it by rewriting it in an encyclopedic style. (December 2007)

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]

1 History
2 Development
- 2.1 Constraints
3 See also
4 References
5 External links

[edit] 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. A breakthrough happened when Kenneth came up with the idea of using vector differences for perturbing the vector population. Since this seminal idea a lively discussion between Kenneth and Rainer and endless ruminations and computer simulations on both parts yielded many substantial improvements which make DE the versatile and robust tool it is today.

Genetic Annealing, developed by Price, was the beginning for the DE algorithm. The first paper about Genetic Annealing was published in October 1994 issue of Dr. Dobb's Journal. It was a population-based combinatorial algorithm that realizes an annealing criterion via thresholds driven by the average performance of the population. Soon after this development, K. Price was contacted by R.Storn, who was interested in solving the Tchebychev polynomial fitting problem by Genetic Annealing. After some experiments Price modified the algorithm using floating-point instead of bit-string encoding and arithmetic vector operations instead of logical ones. These recasts have changed Genetic Annealing from a combinatorial into a continuous optimizer.

In this way, Price discovers the procedure of differential mutation. Price and Storn detected that differential mutation combined with discrete recombination and pair-wise selection is not in need of an annealing factor. Hence, annealing mechanism had been finally removed and thus obtained algorithm started the era of Differential Evolution.

For the first time Differential Evolution was 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 of 1996, which was held in conjunction with the 1996 IEEE International Conference on Evolutionary Computation. The algorithm won third place on proposed benchmarks.

Inspired by results, Price and Storn write an article for Dr. Dobb's Journal ("Differential Evolution: A simple evolution strategy for fast optimization"), which was published in April 1997. Also, 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 demonstrate the advantages of DE over the other heuristics.^{[citation needed]} Very good results had been shown on a wide variety of benchmarks.

Furthermore, Price presents 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 bests among emulous algorithms. And finally, two years later, in 1999, he summarized the algorithm in the compendium "New Ideas in Optimization".

R. 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.

[edit] Development

As it 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 would be the differential mutation. The initial set of strategies realizing the differential mutation was proposed by R.Storn and K.Price. 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.

[edit] 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.