Differential evolution
From Wikipedia, the free encyclopedia
 |
This article or section reads like an essay and may require cleanup. Please help improve this article by rewriting this article or section in an encyclopedic style. (help, talk) |
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 (mathematics) with good probability.
The "DE community" has been growing since 1994 - 1996 and ever more researchers are working on and with 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
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 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.
[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 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.
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, 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 is well-adapted for parallelization on heterogeneous networks of computers.
Thus, DE has been getting its perfection.
