Differential evolution
In
DE is used for multidimensional real-valued
DE optimizes a problem by maintaining a population of candidate solutions and creating new candidate solutions by combining existing ones according to its simple formulae, and then keeping whichever candidate solution has the best score or fitness on the optimization problem at hand. In this way, the optimization problem is treated as a black box that merely provides a measure of quality given a candidate solution and the gradient is therefore not needed.
Storn and Price introduced Differential Evolution in 1995.
Algorithm
A basic variant of the DE algorithm works by having a population of
Formally, let be the fitness function which must be minimized (note that maximization can be performed by considering the function instead). The function takes a candidate solution as argument in the form of a
Let designate a candidate solution (agent) in the population. The basic DE algorithm can then be described as follows:
- Choose the parameters , , and .
- is the population size, i.e. the number of candidate agents or "parents"; a typical setting is 10.
- The parameter is called the crossover probability and the parameter is called the differential weight. Typical settings are and .
- Optimization performance may be greatly impacted by these choices; see below.
- Initialize all agents with random positions in the search-space.
- Until a termination criterion is met (e.g. number of iterations performed, or adequate fitness reached), repeat the following:
- For each agent in the population do:
- Pick three agents , and from the population at random, they must be distinct from each other as well as from agent . ( is called the "base" vector.)
- Pick a random index where is the dimensionality of the problem being optimized.
- Compute the agent's potentially new position as follows:
- For each , pick a uniformly distributed random number
- If or then set otherwise set . (Index position is replaced for certain.)
- If then replace the agent in the population with the improved or equal candidate solution .
- For each agent in the population do:
- Pick the agent from the population that has the best fitness and return it as the best found candidate solution.
Parameter selection
The choice of DE parameters , and can have a large impact on optimization performance. Selecting the DE parameters that yield good performance has therefore been the subject of much research.
Constraint handling
Differential evolution can be utilized for constrained optimization as well. A common method involves modifying the target function to include a penalty for any violation of constraints, expressed as: . Here, represents either a constraint violation (an L1 penalty) or the square of a constraint violation (an L2 penalty).
This method, however, has certain drawbacks. One significant challenge is the appropriate selection of the penalty coefficient . If is set too low, it may not effectively enforce constraints. Conversely, if it's too high, it can greatly slow down or even halt the convergence process. Despite these challenges, this approach remains widely used due to its simplicity and because it doesn't require altering the differential evolution algorithm itself.
There are alternative strategies, such as projecting onto a feasible set or reducing dimensionality, which can be used for box-constrained or linearly constrained cases. However, in the context of general nonlinear constraints, the most reliable methods typically involve penalty functions.
Variants
Variants of the DE algorithm are continually being developed in an effort to improve optimization performance. Many different schemes for performing crossover and mutation of agents are possible in the basic algorithm given above, see e.g.[4]
See also
References
- ^
Rocca, P.; Oliveri, G.; Massa, A. (2011). "Differential Evolution as Applied to Electromagnetics". IEEE Antennas and Propagation Magazine. 53 (1): 38–49. S2CID 27555808.
- ^ Storn, Rainer; Price, Kenneth (1995). "Differential evolution—a simple and efficient scheme for global optimization over continuous spaces" (PDF). International Computer Science Institute. TR (95). Berkeley: International Computer Science Institute: TR-95-012. Retrieved 3 April 2024.
- ^
Storn, R.; Price, K. (1997). "Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces". Journal of Global Optimization. 11 (4): 341–359. S2CID 5297867.
- ^ a b c
Storn, R. (1996). "On the usage of differential evolution for function optimization". Biennial Conference of the North American Fuzzy Information Processing Society (NAFIPS). pp. 519–523. S2CID 16576915.
- ^ a b
Price, K.; Storn, R.M.; Lampinen, J.A. (2005). Differential Evolution: A Practical Approach to Global Optimization. Springer. ISBN 978-3-540-20950-8.
- ^
Feoktistov, V. (2006). Differential Evolution: In Search of Solutions. Springer. ISBN 978-0-387-36895-5.
- ^ G. C. Onwubolu and B V Babu, "New Optimization Techniques in Engineering". Retrieved 17 September 2016.
- ^
Chakraborty, U.K., ed. (2008), Advances in Differential Evolution, Springer, ISBN 978-3-540-68827-3
- ^ S. Das and P. N. Suganthan, "Differential Evolution: A Survey of the State-of-the-art", IEEE Trans. on Evolutionary Computation, Vol. 15, No. 1, pp. 4-31, Feb. 2011, DOI: 10.1109/TEVC.2010.2059031.
- ^ S. Das, S. S. Mullick, P. N. Suganthan, "Recent Advances in Differential Evolution - An Updated Survey," Swarm and Evolutionary Computation, doi:10.1016/j.swevo.2016.01.004, 2016.
- ^ Liu, J.; Lampinen, J. (2002). "On setting the control parameter of the differential evolution method". Proceedings of the 8th International Conference on Soft Computing (MENDEL). Brno, Czech Republic. pp. 11–18.
- ^ Zaharie, D. (2002). "Critical values for the control parameters of differential evolution algorithms". Proceedings of the 8th International Conference on Soft Computing (MENDEL). Brno, Czech Republic. pp. 62–67.