Differential evolution
From Wikipedia, the free encyclopedia
Differential Evolution (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.
The "DE community" has been growing since 1994 - 1996 and ever more researchers are working on and with DE.
DE is a very simple population based, stochastic function minimizer which is very powerful at the same time. DE managed to finish 3rd at the First International Contest on Evolutionary Computation (1st ICEO) which was held in Nagoya, may 1996. DE turned out to be the best genetic type of algorithm for solving the real-valued test function suite of the 1st ICEO (the first two places were given to non-GA type algorithms which are not universally applicable but solved the test-problems faster than DE).
The crucial idea behind DE is a scheme for generating trial parameter vectors. Basically, 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 .
[edit] History
Genetic Annealing developed by K.Price is the beginning for 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. So,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 soon, in December 1997. These papers introduce DE to a large international public and demonstrate the advantages of DE over the other heuristics. 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 containing source codes and many useful links. In 1998 J.Lampinen set up the official bibliography site, which furnishes all materials and also some links on DE dated from 1995 up to 2002. The latest achievements concerning Differential Evolution can be found in the monograph of V.Feoktistov: "Differential Evolution: In Search of Solutions" .
[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 Storn and 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 spontaneously grasped by H.-Y.Fan and J.Lampinen. In 2001, they propose 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 also necessary to note that the percentage of using of novel strategies is quite moderate.
In his research V.Feoktistov continued the development of strategies and proposed the unique conception of a strategy construction. In 2004, this conception was demonstrated by the example of a group of directed strategies. From this point on,there is a unique formula that describes all the strategies and clearly reflects the fundamental principle of DE. The strategies were divided into four groups. Each of the groups is associated with a certain type/behaviour of search: random, directed, local and hybrid. In addition, V.Feoktistov suggested in a combinatorial approach to estimate the potential diversity of a strategy. This approach contributes to the correct strategy's choice. The operation realizing a strategy in the DE algorithm was called differentiation.
Let's now consider a crossover operation. For DE two types of combinatorial crossovers were implemented: binary and exponential ones. The superiority of each crossover over the other can not be uniquely defined. As for a operation, the pair-wise selection, also so-called "greedy" selection or elitist selection, is steadily used in the algorithm.
The next stage was the introduction of mixed variables. In 1999, I.Zelinka and J.Lampinen described a simple and, at the same time, an efficient way of handling imultaneously continuous, integer, and discrete variables. They applied this method to design engineering problems. The obtained results 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.
Now we pass to 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 comprehensive bibliography of constraint methods for evolutionary optimization can be found on the following site .
The question of an algorithm architecture had been untouched during many years. Since the birth of DE, 2-array was generally accepted, that was justified by its easy parallelization. However, most of DE researchers naturally prefer sequential species intuitively believing in its superiority. In 2004, V.Feoktistov revealed this question 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 is well-adapted for parallelization on heterogeneous networks of computers.
Thus, DE has been getting its perfection.
