Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Differential Evolution › Example

Michael BrenndoerferOctober 29, 20267 min read

Machine Learning from ScratchAll chapters

Part 15 of 15Heuristic and Evolutionary Optimization

Chapter 92Differential Evolution › Example

Reading section 5 of 10 · Example · 7 minSection 5 of 10 · 7 min

Section 5 of 10 · 7 min read

Differential Evolution › ExampleSection view · Sections in this chapter5 / 10 ↓

Sections in this chapter10

Reading tools Definitions, links & notes

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

Notes & comments

Notes & commentsLeave notes and join the discussionSelection toolbarShow comment actions when selecting text. Turn off for the browser menu only.Comment indicatorsShow small counts beside annotated passagesPassage highlightsGently shade annotated text selections

We work through half a generation of DE/rand/1/bin by hand on a two-variable problem with a known answer, so that every step of the machinery above becomes a concrete number. The objective is

f(x, y) = (x - 1)^2 + (y + 2)^2

whose unique minimum is $f = 0$ at $(1, -2)$ . The box is $[-5, 5]^2$ , the mutation factor is $F = 0.8$ , and the crossover rate is $CR = 0.5$ . Our population of four members, with their objective values, is:

\mathbf{x}_1 = (-3,\, 2), \quad \mathbf{x}_2 = (4,\, 1), \quad \mathbf{x}_3 = (0,\, -4), \quad \mathbf{x}_4 = (2,\, 3)

Let us verify one of these values to fix the arithmetic. For $\mathbf{x}_1$ we get $(x-1)^2 = (-3-1)^2 = (-4)^2 = 16$ and $(y+2)^2 = (2+2)^2 = 4^2 = 16$ , so $f(\mathbf{x}_1) = 32$ . Repeating: $f(\mathbf{x}_2) = 3^2 + 3^2 = 18$ , $f(\mathbf{x}_3) = (0-1)^2 + (-4+2)^2 = (-1)^2 + (-2)^2 = 5$ , and $f(\mathbf{x}_4) = 1^2 + 5^2 = 26$ . So the current best is $\mathbf{x}_3$ with $f = 5$ .

Take the first target $i = 1$ and donors $r_1 = 3$ , $r_2 = 4$ , $r_3 = 2$ . The difference vector is

\mathbf{x}_{r_2} - \mathbf{x}_{r_3} = \mathbf{x}_4 - \mathbf{x}_2 = (2 - 4,\ 3 - 1) = (-2,\ 2)

which is a step of two units left and two units up, a displacement the population happens to contain. Scaling by $F = 0.8$ gives $(-1.6,\ 1.6)$ , and adding it to $\mathbf{x}_{r_1} = \mathbf{x}_3 = (0, -4)$ gives the mutant

\mathbf{v}_1 = (0 - 1.6,\ -4 + 1.6) = (-1.6,\ -2.4)

Now crossover with $CR = 0.5$ . Suppose the uniform draws are $\text{rand}_{1,1} = 0.3$ for the $x$ coordinate and $\text{rand}_{1,2} = 0.9$ for the $y$ coordinate, and the forced index is $j_{\text{rand}} = 1$ , the $x$ coordinate. For $x$ : $0.3 \le 0.5$ , so we take the mutant value $-1.6$ (and it would have been forced anyway). For $y$ : $0.9 > 0.5$ and $2 \neq 1$ , so we keep the target value $2$ . The trial is

\mathbf{u}_1 = (-1.6,\ 2), \qquad f(\mathbf{u}_1) = (-1.6 - 1)^2 + (2 + 2)^2 = 6.76 + 16 = 22.76

Since $22.76 \le 32$ , the greedy rule accepts and slot 1 becomes $(-1.6,2)$ . The mutation displacement points left from its base $\mathbf{x}_3=(0,-4)$ to the mutant $(-1.6,-2.4)$ . Relative to the target $\mathbf{x}_1=(-3,2)$ , however, crossover moves $x$ rightward to $-1.6$ and leaves $y=2$ unchanged. The squared $x$ error drops from $16$ to $6.76$ , accounting for the entire cost decrease. A donor-difference direction must be read from its base, not from the target.

Now take the second target $i = 3$ with donors $r_1 = 1$ , $r_2 = 2$ , $r_3 = 4$ , using generation-0 values for all members. The difference vector is now $\mathbf{x}_2 - \mathbf{x}_4 = (4 - 2,\ 1 - 3) = (2, -2)$ , scaled to $(1.6, -1.6)$ , and the mutant is

\mathbf{v}_3 = \mathbf{x}_1 + (1.6,\ -1.6) = (-3 + 1.6,\ 2 - 1.6) = (-1.4,\ 0.4)

With draws $\text{rand}_{3,1} = 0.2$ and $\text{rand}_{3,2} = 0.8$ and forced index $j_{\text{rand}} = 1$ , the $x$ coordinate is inherited from the mutant ( $0.2 \le 0.5$ ) and the $y$ coordinate is kept from the target ( $0.8 > 0.5$ ), giving $\mathbf{u}_3 = (-1.4, -4)$ . Its value is

f(\mathbf{u}_3) = (-1.4 - 1)^2 + (-4 + 2)^2 = 5.76 + 4 = 9.76

and $9.76 > 5 = f(\mathbf{x}_3)$ , so the trial is discarded and $\mathbf{x}_3$ survives unchanged. This is the greedy rule doing its job: the rejected trial $\mathbf{u}_3 = (-1.4,-4)$ has $f = 9.76$ , whereas $\mathbf{x}_3 = (0,-4)$ has $f = 5$ ; the trial's inherited $x$ coordinate of $-1.4$ is farther from the optimum $x = 1$ than the target's $x = 0$ , so changing $x$ alone left the trial worse than the target.

Both trials cost an objective evaluation, including the rejected trial. A rejection means this completed crossover trial was worse than its target; it does not isolate the mutation direction as the cause. Both hand calculations use generation-0 donors, including the old value of slot 1 after its replacement has been proposed. That is the deferred convention.

We can check the arithmetic with a helper that takes explicit donor vectors, uniform draws, and the forced-coordinate index. We compute the four initial objective values and two trial values once, then reuse those values for display and plotting. These six hand-example candidate evaluations are separate from the later Rastrigin search budgets.

PythonIn [5]
CollapseExpanddef f_example(X):
    """Vectorized objective f(x, y) = (x - 1)^2 + (y + 2)^2 for a 2D array of points."""
    X = np.atleast_2d(X)
    return (X[:, 0] - 1.0) ** 2 + (X[:, 1] + 2.0) ** 2


def de_trial_manual(target, r1, r2, r3, F, CR, j_rand, rand):
    """One DE/rand/1/bin trial with all randomness supplied by the caller (1-based j_rand)."""
    mutant = r1 + F * (r2 - r3)
    mask = rand < CR
    mask[j_rand - 1] = True
    trial = np.where(mask, mutant, target)
    return mutant, mask, trial


pop0 = np.array(
    [
        [-3.0, 2.0],  # x1
        [4.0, 1.0],  # x2
        [0.0, -4.0],  # x3
        [2.0, 3.0],
    ]
)  # x4
f0 = f_example(pop0)
F, CR = 0.8, 0.5

v1, m1, u1 = de_trial_manual(
    pop0[0], pop0[2], pop0[3], pop0[1], F, CR, 1, np.array([0.3, 0.9])
)
v3, m3, u3 = de_trial_manual(
    pop0[2], pop0[0], pop0[1], pop0[3], F, CR, 1, np.array([0.2, 0.8])
)
trial_values = f_example(np.vstack([u1, u3]))
accepted_values = trial_values <= f0[[0, 2]]

ConsoleOut [6]
CollapseExpandobjective values of generation 0: [32. 18.  5. 26.]

target i=1
  mutant      : [-1.6 -2.4]
  mask        : [ True False]
  trial       : [-1.6  2. ]
  f(trial)    : 22.7600   f(target) = 32.0000   -> accept

target i=3
  mutant      : [-1.4  0.4]
  mask        : [ True False]
  trial       : [-1.4 -4. ]
  f(trial)    : 9.7600   f(target) = 5.0000   -> reject

The displayed values match the hand calculation: the first trial $(-1.6,2)$ has cost $22.76$ and is accepted against $32$ ; the second trial $(-1.4,-4)$ has cost $9.76$ and is rejected against $5$ . If values disagree, check the arithmetic, formulas, indexing, and code together. Agreement on these two updates is a focused consistency check, not a proof for every input. The masks show which coordinates are selected from the mutant.

The printed values already give us the coordinates of both updates; plotting them makes the selection outcome visible. The fixed example uses hand-supplied random draws, so every point is the deterministic result of the hand-chosen donors and crossover draws.

The preparation cell collects the existing targets, mutants, trials, and stored selection outcomes for plotting. It introduces no new random draws or objective evaluations.

VisualizationOut [8]
CollapseExpand

Plot of two hand-worked DE updates, each connecting a circle-marked target to a diamond-marked mutant with an arrow, with square-marked trial points colored to show which update was accepted and which was rejected. — Hand-worked DE/rand/1/bin updates for targets i=1 and i=3 on the quadratic example. Arrows associate each target with its corresponding mutant; they do not draw the base-to-mutant displacement. Circles mark current targets, diamonds mark mutants, and squares mark trials. The primary-colored square is accepted and the muted square is rejected.

Comments

Add to the conversation

A question, a correction, or an example from your own work.

No comments yet. Be the first to share your thoughts!

Comments

Add to the conversation

Stay up to date