Optimization Without Gradients
A lot of optimization in machine learning relies on gradients: compute how the error changes with each parameter, then take a step downhill. That works when the function is smooth and differentiable. Many real problems are not. The objective might come from a simulation, have discontinuities, be full of local minima, or be a black box that only returns a number for each input.
Differential evolution (DE) was built for continuous problems of that kind. It needs nothing from the objective function except the ability to evaluate it. Rainer Storn and Kenneth Price introduced it in a 1995 technical report and published the full version in the Journal of Global Optimization in 1997. The algorithm is short enough to write in a few dozen lines, and it has remained one of the most competitive methods for continuous black-box optimization since then.
The Core Idea: Difference Vectors
DE keeps a population of candidate solutions, each one a vector of real numbers. What makes it distinctive is how it creates new candidates. Instead of adding random noise drawn from a fixed distribution, as many evolutionary strategies do, it uses the difference between two existing members of the population as the perturbation.
Take three distinct population members, call them a, b and c. The mutant vector is a + F·(b − c), where F is a scaling factor, typically between 0.4 and 1. The difference (b − c) points from one solution to another somewhere in the population, and adding a scaled copy of it to a moves a in that direction.
The effect is that step sizes and directions adapt on their own. Early in the run, the population is spread across the search space, so differences between members are large and the algorithm explores broadly. As the population converges toward a good region, the differences shrink and the steps become fine-grained. If the population stretches out along a narrow valley in the landscape, the difference vectors mostly point along that valley, so the search follows its shape. No explicit step-size schedule is needed.
Crossover and Selection
After mutation, DE mixes the mutant vector with the current population member it is trying to replace, called the target. In the standard binomial crossover, each coordinate of the new trial vector comes from the mutant with probability CR (the crossover rate) and from the target otherwise. One coordinate is always forced to come from the mutant, so the trial is never an exact copy of the target.
Selection is then a one-on-one comparison. If the trial vector is at least as good as the target, it replaces it in the next generation. Otherwise the target survives. This greedy, local form of selection means the population’s best fitness can never get worse, and every member only competes with its own offspring, which helps preserve diversity compared to schemes where the best individuals take over the whole population.
The whole loop is: for each member of the population, build a mutant from three others, cross it with the member, keep whichever is better. Repeat until the evaluation budget runs out.
The Parameters and the Variants
Basic DE has only three parameters: the population size NP, the scale factor F and the crossover rate CR. Storn and Price suggested starting points like NP equal to ten times the number of dimensions, F = 0.5 and CR = 0.9. These work reasonably often but not always. A low CR makes the algorithm change one or two coordinates at a time, which suits separable problems where variables can be optimized independently. A high CR changes many coordinates together, which is necessary when variables interact.
The mutation rule also has variants, written in a naming scheme like DE/x/y/z. DE/rand/1/bin is the classic version above: random base vector, one difference vector, binomial crossover. DE/best/1/bin uses the best member of the population as the base, which converges faster but risks getting stuck early. DE/current-to-best/1 moves each member partly toward the best and partly along a random difference, and DE/rand/2 adds two difference vectors instead of one.
Adaptive DE: JADE, SHADE and L-SHADE
Since good parameter values depend on the problem, much of the research on DE since the mid-2000s has been about making the algorithm tune itself. SaDE, from Qin, Huang and Suganthan (2009), keeps a pool of mutation strategies and learns which ones are producing successful offspring. JADE, from Zhang and Sanderson (2009), introduced the current-to-pbest mutation, which moves toward one of the top p% of solutions instead of the single best, together with an external archive of recently replaced solutions and parameters sampled around values that recently worked.
SHADE, from Ryoji Tanabe and Alex Fukunaga (2013), kept a history of successful F and CR values in a memory and sampled new parameters from it. The following year, the same authors added linear population size reduction: the run starts with a large population for exploration and removes the worst members on a linear schedule until only a handful remain for refinement at the end. That version, L-SHADE, ranked first in the CEC 2014 competition on single-objective real-parameter optimization, and many of the top entries in later CEC competitions, such as jSO, have been built on it.
Constraints, Discrete Variables and Multiple Objectives
Real engineering problems come with constraints: a beam must be strong enough, a circuit must stay under a power budget. DE handles them with the usual tools for evolutionary algorithms, such as penalty functions, or Deb’s feasibility rules, in which a feasible solution always beats an infeasible one and between two infeasible ones, the smaller violation wins.
DE was designed for continuous variables, but integer and mixed variables can be handled by rounding when evaluating a solution, and permutation problems have been attacked with specialized encodings, though other algorithms are usually more natural there. For problems with several conflicting objectives, variants like GDE3 (Kukkonen and Lampinen) combine DE’s mutation with the Pareto-based selection used in multi-objective evolutionary algorithms.
Where DE Is Used
Storn’s early applications included the design of digital filters, and signal processing remains a common use. In power systems, DE has been used for economic load dispatch, deciding how much each generator should produce to meet demand at minimum cost. It shows up in antenna array design, parameter estimation for chemical kinetics and biological models (fitting a system of differential equations to measured data), structural design, and the tuning of controllers.
In machine learning, it is used for hyperparameter tuning and for training small models where gradients are not available or not reliable. In image processing, DE is one of the metaheuristics commonly applied to find thresholds for image segmentation. And because it ships with SciPy as scipy.optimize.differential_evolution, it is often the first global optimizer someone in the Python ecosystem tries.
Strengths and Limits
DE’s advantages are simplicity, few parameters, rotation-invariant mutation (the difference vectors do not favor the coordinate axes, even though standard crossover does), and strong performance on rugged, multimodal continuous landscapes. It parallelizes easily, since the objective evaluations within a generation are independent.
Its main limitation is the one shared by all population-based black-box methods: it needs many function evaluations, often tens of thousands. When each evaluation is a finite-element simulation that takes an hour, that is too expensive, and methods that build a surrogate model of the objective, like Bayesian optimization, are a better fit. On high-dimensional problems with smooth, cheap-to-compute gradients, gradient-based methods will be far more efficient. The no free lunch theorems also apply: no variant of DE is best on every problem, and it is easy to find benchmarks where CMA-ES or particle swarm optimization does better.
Reflection
The key idea in differential evolution is that the population itself stores information about the shape of the search space. The distances and directions between current solutions tell the algorithm how big a step to take and which way to point it. It does not need a separate model of the landscape. After almost thirty years, and thousands of papers about adapting F and CR, the core operator is still the same: take one solution, add the scaled difference between two others, and keep the result only if it is better.
By: Max Johnson B.
Deja una respuesta