Skip to content
Tutorials Center
My learning

Topics

Lesson 24 of 36 ยท Swarm and Other Metaheuristics

Differential Evolution

Learn differential evolution, a powerful evolutionary optimizer for real-valued problems. Build DE/rand/1/bin from scratch, tune F and CR, and use scipy.optimize.

Differential evolution (DE), invented by Storn and Price in 1995, is an evolutionary algorithm built for real-valued parameters. It looks like a GA (a population, mutation, crossover, selection) but its mutation is unusual: instead of adding random noise, it adds the difference between two other population members to a third. The population thus supplies its own step size. When the population is spread out, steps are big; as it converges, steps automatically shrink.

DE has only three parameters, is very robust, and wins many benchmarks against fancier methods. If you must optimize a few dozen real numbers and have no gradient, DE is one of the first things to try.

One generation of DE/rand/1/bin

The name says the strategy: rand base vector, 1 difference vector, binomial crossover. For every target vector x_i in the population:

  1. Mutation. Pick three distinct other individuals a, b, c. Build the donor v = a + F * (b - c). F (the scale factor) is usually between 0.4 and 1.
  2. Crossover. Make a trial vector u: for each dimension, take the gene from v with probability CR, else from x_i. Force at least one gene to come from v.
  3. Selection. If u is at least as good as x_i, it replaces x_i. Otherwise x_i stays.
flowchart LR
    A["a"] --> D["donor v = a + F*(b - c)"]
    B["b"] --> D
    C["c"] --> D
    D --> U["trial u: mix of v and x_i (CR)"]
    X["target x_i"] --> U
    U --> S{"u better than x_i?"}
    S -- yes --> N["u replaces x_i"]
    S -- no --> K["x_i stays"]

Selection is one-to-one: a child only competes with its own parent.

That last point is important. Because each child fights only its parent, DE never loses its best solution and the population improves monotonically, without a separate elitism step.

DE from scratch

We use the Ackley function, a flat-ish plateau with a deep hole at the origin, whose global minimum is 0.

Python Differential evolution on the Ackley function

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Watch the printed spread: it falls as the population converges, and the mutation steps F * (b - c) shrink with it. DE has self-adapting step sizes without any extra code.

The three parameters

  • Population size NP: about 5 to 10 times the number of dimensions is a good start. DE needs at least 4 members for the mutation to work.
  • Scale factor F: large F (0.8 to 1) explores, small F (0.4 to 0.5) refines. If the algorithm stalls, try raising it.
  • Crossover rate CR: large CR (0.9) changes many genes at once and suits problems where genes interact. Small CR (0.1) changes few genes and suits problems where each parameter can be tuned independently (separable problems).

Strategy variants

DE has a shorthand DE/base/n/crossover:

  • DE/rand/1/bin: the classic, robust and explorative.
  • DE/best/1/bin: the donor is best + F * (b - c). Converges faster, but can get stuck in a local minimum.
  • DE/current-to-best/1: pulls each vector partly toward the best while keeping a random difference. A good middle ground.
  • DE/rand/2/bin: two difference vectors, more exploration.

Modern self-adaptive variants (JADE, SHADE, L-SHADE) learn F and CR during the run and top competitions, but the basic version is already strong.

Using SciPy's DE

You rarely need to write DE yourself. scipy.optimize.differential_evolution provides a well-tested version. It takes the function and a list of (low, high) bounds, and supports constraints, a polishing step with a local optimizer, and several strategies.

Python scipy.optimize.differential_evolution

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Rosenbrock's narrow, curved valley is a classic hard case. All three strategies get the same budget (maxiter), so compare the final value f: the greedier best1bin and currenttobest1bin converge faster here, while rand1bin is slower but more robust on multimodal problems.

DE versus GA versus PSO

DE works directly on real vectors and is very hard to beat for continuous problems with up to a few hundred variables. It is less natural for permutations or trees, where a GA is better, and PSO may be faster on very smooth functions. A sensible workflow is to run all of them on a cheap version of your problem and keep the winner.

Common mistakes

  • Choosing a, b, c that include the target. They must be distinct from x_i and from each other.
  • No bounds handling. Donors can leave the box; clip them or reflect them back.
  • Population too small. With NP = 10 for 30 dimensions the difference vectors cover too few directions.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How does differential evolution create a mutant (donor) vector?

    v = a + F * (b - c).
  2. 2. In DE, who does a trial vector compete with in the selection step?

    One-to-one selection means the population never gets worse.
  3. 3. For a separable problem (each parameter can be tuned on its own), which CR is usually better?

    A small CR changes a few genes at a time, which suits independent parameters.
  4. 4. Why does DE not need a separate step-size parameter that shrinks over time?

    When members are close together, b - c is small, so steps shrink automatically.

Summary

  • DE builds donors as a + F * (b - c), then mixes them with the target by binomial crossover.
  • Selection is one-to-one, so the population never gets worse.
  • Three parameters: population size, F and CR.
  • rand/1/bin is robust; best strategies converge faster but risk local minima.
  • scipy.optimize.differential_evolution is a ready-made, tested implementation.

Next: Simulated Annealing and Hill Climbing