Differential evolution

Author: Rohit Kumar (rk787) (ChemE 6800 Fall 2024)

Stewards: Nathan Preuss, Wei-Han Chen, Tianqi Xiao, Guoqing Hu

Introduction

Differential Evolution (DE) is a robust and efficient optimization algorithm widely used for solving non-linear, non-differentiable, and multimodal optimization problems. It was first introduced by R. Storn and K. Price in their seminal work on global optimization over continuous spaces , where they described DE as:-

"A new heuristic approach for minimizing possibly nonlinear and non-differentiable continuous-space functions."

A heuristic is any approximation method for a solution to a problem capable of producing satisfactory solutions within tolerable amounts of time when classic methods cannot find an exact answer or work quite slowly. Unlike the Gradient Descent algorithm, the optimization problem does not need to be differentiable.

The key idea is to generate a population of candidate solutions through successive generations using vector differences for deviations. This approach allows DE to adapt its search methodology to the objective function, making it particularly effective for non-linear, non-differentiable, and multimodal optimization problems.

The algorithm is renowned for its simplicity and efficiency. Its primary advantages include:

• Requires minimal parameter tuning.
• High robustness.
• Ability to avoid local optima and converge toward global solutions.

In DE, the currently evolving population of possible solutions is represented as a vector of real-valued numbers. The algorithm attempts to enhance these solutions through a series of iterations built upon three main steps:

• Mutation
• Crossover
• Selection

DE has become highly popular for applications in such fields as engineering design, machine learning, signal processing, and financial modeling. Despite its simplicity, Differential Evolution is competitive against many other optimization techniques, often performing better on challenging problems.

Algorithm Discussion

Differential Evolution operates through three main steps: initialization, mutation, crossover, and selection, as outlined in optimization literature .

Initialization

The initial population is generated randomly within the bounds of the search space: $x_{i,j}\sim U(x_{j}^{\text{min}},x_{j}^{\text{max}})$ where:

• $x_{i,j}$ represents the $j^{\text{th}}$ parameter of the $i^{\text{th}}$ individual.
• $U(a,b)$ is a uniform random distribution.

Mutation

A mutant vector $v_{i}$ is generated by combining three randomly chosen vectors: $v_{i}=x_{r1}+F\cdot (x_{r2}-x_{r3})$ where:

• $F$ is the mutation factor.
• $x_{r1},x_{r2},x_{r3}$ are distinct vectors from the population.

Crossover

A trial vector $u_{i}$ is created by mixing the mutant vector $v_{i}$ and the target vector $x_{i}$: $u_{i,j}={\begin{cases}v_{i,j},&{\text{if }}{\text{rand}}(0,1)\leq CR{\text{ or }}j=j_{\text{rand}},\\x_{i,j},&{\text{otherwise}}.\end{cases}}$ where:

• $CR$ is the crossover probability.
• $j_{\text{rand}}$ is a randomly chosen index.

Selection

The trial vector $u_{i}$ replaces the target vector $x_{i}$ in the population if it yields a better objective function value: $x_{i}={\begin{cases}u_{i},&{\text{if }}f(u_{i})\leq f(x_{i}),\\x_{i},&{\text{otherwise}}.\end{cases}}$

Pseudocode

The pseudocode of Differential Evolution is shown below:

Initialize population P randomly
While termination criterion not met:
    For each individual x_i in P:
        Generate mutant vector v_i
        Perform crossover to create trial vector u_i
        If f(u_i) < f(x_i): Replace x_i with u_i
Return the best solution

The pseudocode presented in this article is adapted from S. Das and P.N. Suganthan's survey on the state-of-the-art in DE .

Numerical Example

We aim to minimize the function $f(x)=x^{2}$, a common benchmark for optimization algorithms . The example uses key principles of DE, including mutation and crossover, as described in foundational texts like R. Storn and K. Price’s work .

Initial Setup

The initial population and fitness values are: $P=\{-7,3,-2,6,8\},\quad f(P)=\{49,9,4,36,64\}$

Iteration 1

Individual 1 ($x=-7$):

• Mutant vector: $v_{1}=3+0.8\cdot (-2-8)=-5$
• Trial vector: ${\textstyle u_{1}=-5}$
• Fitness: $f(u_{1})=25$
• Since $f(u_{1})<f(x_{1})$ ($25<49$), replace $x_{1}$ with $u_{1}$
• Updated value: $x_{1}=-5$

Individual 2 ($x=3$):

• Mutant vector: $v_{2}=-2+0.8\cdot (6-8)=-3.6$
• Trial vector: $u_{2}=3$ (crossover fails)
• Fitness: $f(u_{2})=9$
• No replacement as $f(u_{2})=f(x_{2})$
• Updated value: $x_{2}=3$

Individual 3 ($x=-2$):

• Mutant vector: $v_{3}=6+0.8\cdot (8-(-7))=18$
• Trial vector: $u_{3}=-2$ (crossover fails)
• Fitness: $f(u_{3})=4$
• No replacement as $f(u_{3})=f(x_{3})$
• Updated value: $x_{3}=-2$

Individual 4 ($x=6$):

• Mutant vector: ${\textstyle v_{4}=-7+0.8\cdot (3-(-2))=-3}$
• Trial vector: $u_{4}=-3$
• Fitness: $f(u_{4})=9$
• Since $f(u_{4})<f(x_{4})$ ($9<36$), replace $x_{4}$ with $u_{4}$
• Updated value: $x_{4}=-3$

Individual 5 ($x=8$):

• Mutant vector: $v_{5}=3+0.8\cdot (-7-(-2))=-1$
• Trial vector: $u_{5}=-1$
• Fitness: $f(u_{5})=1$
• Since $f(u_{5})<f(x_{5})$ ($1<64$), replace $x_{5}$ with $u_{5}$
• Updated value: $x_{5}=-1$

After the first iteration, the updated population is: $P=\{-5,3,-2,-3,-1\},\quad f(P)=\{25,9,4,9,1\}$

Iterations 2–5

The process is repeated for four more iterations. For each individual, the mutant vector, trial vector, and fitness are calculated. Individuals in the population are replaced whenever $f(u_{i})<f(x_{i})$. Over successive iterations, the population evolves toward the minimum.

Final Population

After five iterations, the population converges to: $P=\{0,0,0,0,0\},\quad f(P)=\{0,0,0,0,0\}$

Visualization

The progression of the population during the Differential Evolution process is illustrated in the figures below. Each figure shows the distribution of the population at a specific iteration, demonstrating how the algorithm converges toward the global minimum of the function $f(x)=x^{2}$.

Figure 1: Initial population distribution before any iterations. View Figure 1: Initial population distribution before any iterations.

Figure 2: Population after the first iteration, showing improvement toward the global minimum. View Figure 2: Population after the first iteration, showing improvement toward the global minimum.

Figure 3: Population after the second iteration, with further refinement of solutions. View Figure 3: Population after the second iteration, with further refinement of solutions.

Figure 4: Population after the fourth iteration, nearing convergence. View Figure 4: Population after the fourth iteration, nearing convergence.

Figure 5: Final population converging to the global minimum at $x=0$. View Figure 5: Final population converging to the global minimum at $x=0$.

Applications

Differential Evolution has been applied across various domains, including:

• Engineering Design: Applications include minimizing the weight of tension/compression springs, following the approaches outlined by R. Storn and K. Price .
• Water Resource Management: Optimization strategies for reservoirs, as seen in recent research .
• Machine Learning: Parameter optimization for neural networks .
• Medical Applications: DE’s effectiveness in radiotherapy optimization is discussed in Abbass (2002) .

Software Tools

Several software libraries and frameworks have integrated Differential Evolution into their core optimization processes:

• ALGLIB: A powerful library in C++, C#, and Java, capable of solving complex constrained and unconstrained optimization problems.
• DEAP (Distributed Evolutionary Algorithms in Python): A Python framework for rapid prototyping and testing of evolutionary algorithms, including DE.
• ECJ: An open-source evolutionary computation system implemented in Java, supporting a variety of algorithms, including DE.
• MOEA Framework: A Java library dedicated to multi-objective optimization, offering robust DE implementations.

Differential Evolution’s adaptability and effectiveness have made it an indispensable tool for tackling challenging optimization problems across these diverse domains.

Conclusion

Differential Evolution’s ability to handle a wide range of optimization problems has made it a preferred tool in various domains . Despite its strengths, opportunities for improvement exist, including faster convergence and hybrid models .

Throughout its application in engineering design, water resource management, machine learning, and medical fields, DE has demonstrated its effectiveness in solving complex and constrained problems. Its capacity for global convergence and minimal parameter tuning requirements further enhance its appeal for real-world problems.

Despite its strengths, there are areas for future research and improvement:

• Enhancing the convergence speed of the algorithm.
• Developing hybrid approaches by combining DE with other optimization techniques.
• Extending its application to emerging domains such as quantum computing and autonomous systems.
• Improving parameter tuning methods and software implementations to make DE more accessible and efficient for practitioners.

In summary, Differential Evolution continues to be a reliable and powerful tool for solving challenging optimization problems and holds promise for further advancements in both methodology and applications.

References

Below is a list of references used to support the content in this article:

1. R.J. Vanderbei, Linear Programming: Foundations and Extensions. Springer, 2008. Available at: SpringerLink.
2. S. Boyd, L. Vandenberghe, Convex Optimization. Cambridge University Press, 2009. Available at: Stanford University.
3. J. Nocedal, S.J. Wright, Numerical Optimization. Springer, 1999. Available at: SpringerLink.
4. J. Birge, F. Louveaux, Introduction to Stochastic Programming. Springer, 2011. Available at: SpringerLink.
5. A. Ben-Tal, L.E. Ghaoui, A. Nemirovski, Robust Optimization. Princeton University Press, 2009. Available at: Georgia Institute of Technology.
6. L.A. Wolsey, Integer Programming. Wiley, 1998.
7. L.T. Biegler, I.E. Grossmann, A.W. Westerberg, Systematic Methods of Chemical Process Design. Prentice Hall Press, 1997.
8. L.T. Biegler, Nonlinear Programming: Concepts, Algorithms and Applications to Chemical Engineering. SIAM, 2010.
9. T.F. Edgar, D.M. Himmelblau, L.S. Lasdon, Optimization of Chemical Processes. McGraw-Hill, 2001.
10. T. Hastie, R. Tibshirani, J. Friedman, The Elements of Statistical Learning. Springer, 2009. Available at: Stanford University.
11. K. Murphy, Machine Learning: A Probabilistic Perspective. MIT Press, 2012.

Additional references for application examples:

• S. Das, P.N. Suganthan, "Differential Evolution: A Survey of the State-of-the-Art," IEEE Transactions on Evolutionary Computation, vol. 15, no. 1, pp. 4-31, 2011.
• R. Storn, K. Price, "Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces," Journal of Global Optimization, vol. 11, pp. 341-359, 1997.
• A. Abbass, "An Evolutionary Artificial Neural Networks Approach for Breast Cancer Diagnosis," Artificial Intelligence in Medicine, vol. 25, no. 3, pp. 265-281, 2002.