Differential Evolution

Evolutionary

Differential Evolution (DE) optimization algorithm.

Algorithm Overview

This module implements the Differential Evolution (DE) algorithm. DE is a population-based metaheuristic optimization algorithm developed by R. Storn and K. Price in 1997. It is simple, robust, and has proven to be effective for a wide range of optimization problems.

DE generates new candidate solutions by combining existing ones according to its simple formulae. For each iteration/generation, new solutions are generated by adding the weighted difference between two solutions to a third solution. If the generated solution has better fitness than the current solution in consideration, it replaces the current solution.

DE is particularly useful for numerical optimization problems that are computationally intensive, non-differentiable, noisy, discontinuous, and multimodal.

Usage

from opt.evolutionary.differential_evolution import DifferentialEvolution
from opt.benchmark.functions import sphere

optimizer = DifferentialEvolution(
    func=sphere,
    lower_bound=-5.12,
    upper_bound=5.12,
    dim=10,
    max_iter=500,
    population_size=50,
)

best_solution, best_fitness = optimizer.search()
print(f"Best solution: {best_solution}")
print(f"Best fitness: {best_fitness:.6e}")

Parameters

Parameter	Type	Default	Description
func	Callable	Required	Objective function to minimize.
lower_bound	float	Required	Lower bound of search space.
upper_bound	float	Required	Upper bound of search space.
dim	int	Required	Problem dimensionality.
population_size	int	100	Number of individuals (NP).
max_iter	int	1000	Maximum iterations.
F	float	0.5	Mutation factor (differential weight).
CR	float	0.7	Crossover probability.
seed	int | None	None	Random seed for reproducibility.
target_precision	float	1e-08	Algorithm-specific parameter
f_opt	float | None	None	Algorithm-specific parameter

Algorithm Metadata

Property	Value
Algorithm Name	Differential Evolution
Acronym	DE
Year Introduced	1997
Authors	Storn, Rainer; Price, Kenneth
Algorithm Class	Evolutionary
Complexity	O(NP * dim) per iteration
Properties	Population-based, Derivative-free, Stochastic
Implementation	Python 3.10+
COCO Compatible	Yes

Mathematical Formulation

Core mutation and crossover equations:

Mutation (DE/rand/1 strategy):

$$v_i=x_{r1}+F\cdot (x_{r2}-x_{r3})$$

Crossover (binomial):

$$u_{i,j}=\{\begin{array}{ll}{v}_{i,j}& \text{if }\text{rand}(0,1)\le CR\text{ or }j=j_{rand}\\ x_{i,j}& \text{otherwise}\end{array}$$

Selection:

$$x_i^{(g+1)}=\{\begin{array}{ll}{u}_i& \text{if }f(u_i)\le f(x_i^{(g)})\\ x_i^{(g)}& \text{otherwise}\end{array}$$

where:

• $x_i$ is the $i$-th target vector
• $v_i$ is the mutant vector
• $u_i$ is the trial vector
• $F$ is the mutation factor (scaling factor)
• $CR$ is the crossover probability
• $r1,r2,r3$ are distinct random integers from population
• $j_{rand}$ ensures at least one parameter is from mutant vector

Constraint handling:

• Boundary conditions: Clamping to bounds
• Feasibility enforcement: Solutions outside bounds are clipped to boundary values

Hyperparameters

Parameter	Default	BBOB Recommended	Description
population_size	100	10*dim	Number of individuals (NP)
max_iter	1000	10000	Maximum iterations
F (mutation factor)	0.5	0.5-0.8	Differential weight
CR (crossover rate)	0.7	0.7-0.9	Crossover probability

Sensitivity Analysis:

• F: High impact - controls exploration vs exploitation balance
• CR: Medium impact - affects parameter mixing
• Recommended tuning ranges: $F\in [0.4,1.0]$, $CR\in [0.6,0.95]$

COCO/BBOB Benchmark Settings

Search Space:

• Dimensions tested: 2, 3, 5, 10, 20, 40
• Bounds: Function-specific (typically [-5, 5] or [-100, 100])
• Instances: 15 per function (BBOB standard)

Evaluation Budget:

• Budget: $\text{dim}\times 10000$ function evaluations
• Independent runs: 15 (for statistical significance)
• Seeds: 0-14 (reproducibility requirement)

Performance Metrics:

• Target precision: 1e-8 (BBOB default)
• Success rate at precision thresholds: [1e-8, 1e-6, 1e-4, 1e-2]
• Expected Running Time (ERT) tracking

Raises

ValueError: If search space is invalid or function evaluation fails.

Notes

• Modifies self.history if track_history=True
• Uses self.seed for all random number generation
• BBOB: Returns final best solution after max_iter or convergence

Computational Complexity:

• Time per iteration: $O(NP\cdot n)$ where $NP$ is population size, $n$ is dimension
• Space complexity: $O(NP\cdot n)$ for population storage
• BBOB budget usage: Typically uses 40-80% of dim*10000 budget for convergence

BBOB Performance Characteristics:

• Best function classes: Multimodal, Weakly structured, Separable
• Weak function classes: Ill-conditioned problems (compared to CMA-ES)
• Typical success rate at 1e-8 precision: 70-85% (dim=5)
• Expected Running Time (ERT): Competitive, particularly on multimodal functions

Convergence Properties:

• Convergence rate: Linear on unimodal, robust on multimodal
• Local vs Global: Good global search capabilities, balanced exploration/exploitation
• Premature convergence risk: Medium - depends on F and CR settings

Reproducibility:

• Deterministic: Yes - Same seed guarantees same results
• BBOB compliance: seed parameter required for 15 independent runs
• Initialization: Uniform random sampling in [lower_bound, upper_bound]
• RNG usage: numpy.random.default_rng(self.seed) throughout

Implementation Details:

• Parallelization: Not supported in this implementation
• Constraint handling: Clamping to bounds
• Numerical stability: Standard floating-point precision

Known Limitations:

• Performance sensitive to F and CR parameter settings
• May converge slowly on highly ill-conditioned problems
• BBOB known issues: None specific; widely tested and reliable

Version History:

• v0.1.0: Initial implementation
• v0.1.2: Current BBOB-compliant version

References

[1] 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. https://doi.org/10.1023/A:1008202821328

[2] Hansen, N., Auger, A., Ros, R., Mersmann, O., Tušar, T., Brockhoff, D. (2021). "COCO: A platform for comparing continuous optimizers in a black-box setting." Optimization Methods and Software, 36(1), 114-144. https://doi.org/10.1080/10556788.2020.1808977

COCO Data Archive:

• Benchmark results: https://coco-platform.org/testsuites/bbob/data-archive.html
• DE results available in COCO archive (competitive performance across function classes)
• Code repository: https://github.com/Anselmoo/useful-optimizer

Implementation:

• Classic DE/rand/1/bin strategy
• This implementation: Based on [1] with modifications for BBOB compliance

See Also

GeneticAlgorithm: Classical evolutionary algorithm with different operators BBOB Comparison: DE generally faster and more reliable on continuous problems

CMAESAlgorithm: Covariance matrix adaptation strategy BBOB Comparison: CMA-ES often superior on ill-conditioned problems, DE simpler

AbstractOptimizer: Base class for all optimizers opt.benchmark.functions: BBOB-compatible test functions

Related BBOB Algorithm Classes:

• Evolutionary: GeneticAlgorithm, CMAESAlgorithm, EstimationOfDistributionAlgorithm
• Swarm: ParticleSwarm, AntColony
• Gradient: AdamW, SGDMomentum

Benchmark Performance

Interactive fitness landscape of a representative multimodal benchmark function (drag to rotate, scroll to zoom):

Convergence, final-fitness distribution and performance profile on rastrigin (5D), averaged over independent runs (compared against representative baselines):

Related Pages

• Evolutionary Algorithms
• All Algorithms
• Benchmark Functions

---

Source Code

View the implementation: differential_evolution.py