Differential Evolution › Formula

We need a representation and initialization, a mutation rule, a crossover mask, and a selection rule. The standard DE/rand/1/bin construction below follows Storn and Price (1997). We will distinguish the rule itself from the particular choices made in our implementation.

We start with the object we are manipulating. The population at generation $g$ is an indexed collection of $NP$ real vectors $\mathbf{x}_i^{(g)} \in \mathbb{R}^d$ for $i = 1, \dots, NP$, where $d$ is the number of decision variables and $f(\mathbf{x})$ is the scalar objective we want to minimize.

Before we can mutate anything we need somewhere to start, so the first ingredient is initialization. Drawing each coordinate uniformly inside the box constraints $[l_j, u_j]$ gives

$$x_{i,j}^{(0)} = l_j + \text{rand}_{i,j} \cdot (u_j - l_j), \qquad i = 1, \dots, NP, \quad j = 1, \dots, d$$

where:

• $x_{i,j}^{(0)}$: the $j$-th coordinate of population member $i$ at generation $0$
• $l_j$: lower bound of the box constraint for coordinate $j$
• $u_j$: upper bound of the box constraint for coordinate $j$
• $\text{rand}_{i,j}$: an independent draw from the uniform distribution on $[0,1)$

Uniform initialization uses only the stated box bounds; it does not ensure that every region is sampled. The minimum population size for this variant is $NP=4$, because each target needs three mutually distinct donor indices that also exclude the target.

With a population in hand, the central question is how to generate a new candidate. Gradient descent would answer with $-\nabla f$; simulated annealing would answer with a perturbation whose size we had to choose. DE answers differently: it takes a displacement that the population already contains. For each target $\mathbf{x}_i$, pick three indices $r_1, r_2, r_3$ uniformly at random, mutually distinct and all different from $i$, and form the mutant

$$\mathbf{v}_i^{(g)} = \mathbf{x}_{r_1}^{(g)} + F \left( \mathbf{x}_{r_2}^{(g)} - \mathbf{x}_{r_3}^{(g)} \right)$$

where:

• $\mathbf{v}_i^{(g)}$: the mutant vector for target $i$ at generation $g$
• $\mathbf{x}_{r_1}^{(g)}$: the base vector, a randomly selected population member
• $\mathbf{x}_{r_2}^{(g)}, \mathbf{x}_{r_3}^{(g)}$: two other distinct population members whose difference forms the mutation direction
• $F$: the mutation factor scaling the difference vector

This single line contains the whole idea, so it is worth reading slowly.

The quantity in parentheses is a difference of two population members. In coordinate $j$ it equals $x_{r_2,j} - x_{r_3,j}$, so its sign tells us which of the two members is larger in that coordinate, and its magnitude is how far apart they are. The full vector $\mathbf{d} = \mathbf{x}_{r_2} - \mathbf{x}_{r_3}$ is therefore a displacement from $\mathbf{x}_{r_3}$ to $\mathbf{x}_{r_2}$, a direction together with a length. Multiplying by $F$ rescales that displacement. Adding the scaled displacement to a third member $\mathbf{x}_{r_1}$ places the mutant at the point we would reach by standing at $\mathbf{x}_{r_1}$ and stepping $F$ times the way from $\mathbf{x}_{r_3}$ toward $\mathbf{x}_{r_2}$.

The mutation factor $F$ multiplies the donor difference. Our implementation accepts $0 \le F < 2$ and uses $F=0.7$ in the main comparison. At $F=0$ the mutant is just the base donor. Increasing $F$ lengthens a fixed nonzero difference; it does not guarantee a better proposal. The parameter sweep later tests several values under a fixed budget.

We can quantify self-scaling under an idealized model. Suppose two donor vectors are independent draws from a distribution with mean $\boldsymbol{\mu}$ and covariance $\boldsymbol{\Sigma}$. This assumption is a model for the calculation, not a claim that evolved population members remain independent. The expected difference is zero:

$$\mathbb{E}\left[\mathbf{x}_{r_2} - \mathbf{x}_{r_3}\right] = \mathbb{E}[\mathbf{x}_{r_2}] - \mathbb{E}[\mathbf{x}_{r_3}] = \boldsymbol{\mu} - \boldsymbol{\mu} = \mathbf{0}$$

where:

• $\mathbf{x}_{r_2}, \mathbf{x}_{r_3}$: independent draws from the population distribution
• $\boldsymbol{\mu}$: the mean of that distribution

Thus the idealized difference has zero mean. This describes a displacement around its base donor, not an unbiased estimate of a direction that reduces the objective. Its covariance is:

$$\begin{aligned} \text{Cov}\left(\mathbf{x}_{r_2} - \mathbf{x}_{r_3}\right) &= \text{Cov}(\mathbf{x}_{r_2}) + \text{Cov}(\mathbf{x}_{r_3}) && \text{(independence)} \\ &= \boldsymbol{\Sigma} + \boldsymbol{\Sigma} && \text{(each draw has covariance } \boldsymbol{\Sigma}\text{)} \\ &= 2\boldsymbol{\Sigma} \end{aligned}$$

where:

• $\mathbf{x}_{r_2}, \mathbf{x}_{r_3}$: independent draws from the population distribution
• $\boldsymbol{\Sigma}$: the covariance matrix of that distribution

Under this independent-draw model, coordinate $j$ of the scaled difference has standard deviation $F\sqrt{2}\,\sigma_j$, where $\sigma_j$ is the distribution standard deviation. This is not exactly twice the empirical covariance of a fixed finite donor pool sampled without replacement. For a pool of $m$ eligible vectors with covariance computed using divisor $m$, the difference covariance is $2m/(m-1)$ times that covariance. The model explains why population spread influences step size without promising contraction or improvement.

In matrix notation the same generation can be written compactly. Let $X^{(g)}$ be the $NP \times d$ matrix whose $i$-th row is $\mathbf{x}_i^{(g)\top}$, and let $\pi_1, \pi_2, \pi_3$ be index vectors of length $NP$ that encode, row by row, which members were drawn as donors:

$$V^{(g)} = X^{(g)}[\pi_1] + F \left( X^{(g)}[\pi_2] - X^{(g)}[\pi_3] \right)$$

Here $X[\pi]$ selects rows. For each target row, its three selected donor indices must be distinct and exclude that target. With scalar $F$, the expression is an ordinary scalar-matrix product. It describes a whole generation compactly; our teaching implementation uses a loop over targets while freezing the donor population. SciPy also supports a mutation interval that samples one $F$ per generation, as discussed below.

The geometry can be checked on explicit donor coordinates. The dashed arrow shows the unscaled difference; the solid arrow attaches its scaled copy to the base donor. A later crossover chooses coordinates from the mutant and target, so a trial can be a corner of their axis-aligned rectangle rather than a point on the line segment joining them.

Donor sampling without replacement and exclusion of the target are defining conditions of this variant. DE/rand/1/bin names a random base donor, one difference vector, and binomial crossover. Other strategies change these ingredients; their performance must be checked on the intended problem rather than inferred from the name.

A mutant contains donor-derived values in every coordinate. Binomial crossover chooses between those values and the target values, coordinate by coordinate. It does not inspect which coordinate choices improve the objective; only the completed trial is evaluated:

$$u_{i,j}^{(g)} = \begin{cases} v_{i,j}^{(g)}, & \text{if } \text{rand}_{i,j} < CR \ \text{ or } \ j = j_{\text{rand}} \\ x_{i,j}^{(g)}, & \text{otherwise} \end{cases}$$

where:

• $u_{i,j}^{(g)}$: the $j$-th coordinate of the trial vector for target $i$
• $v_{i,j}^{(g)}$: the $j$-th coordinate of the mutant vector
• $x_{i,j}^{(g)}$: the $j$-th coordinate of the target vector
• $\text{rand}_{i,j}$: an independent draw from the uniform distribution on $[0,1)$
• $CR$: the crossover rate in $[0,1]$
• $j_{\text{rand}}$: a uniformly drawn index from $\{1, \dots, d\}$ that is always inherited from the mutant

For a non-forced coordinate, $CR$ is its probability of being selected from the mutant. At $CR=1$ every coordinate is selected from the mutant; at $CR=0$ exactly the forced coordinate is selected. The forced index is drawn independently and uniformly for each target.

The forced coordinate guarantees donor inheritance, not numerical novelty. If target and mutant coordinates coincide, or repair maps them to the same values, the trial can equal its target. Duplicate trials still consume evaluations. The random-threshold and forced-index events can overlap: their union probability for one coordinate is $CR+(1-CR)/d$. Equivalently, the forced coordinate contributes one selected entry, and the other $d-1$ coordinates each contribute $CR$ in expectation:

$$\mathbb{E}\left[\sum_{j=1}^{d} M_{i,j}\right] = (d-1)\,CR + 1 = 1 + (d-1)\,CR$$

Here $M_{i,j}$ is one when the mask selects the mutant coordinate and zero otherwise. For $d=5$, the expected selected counts are $4.6$ at $CR=0.9$ and $1.4$ at $CR=0.1$. These count selected entries, not accidental numerical equalities. For $d>1$, a smaller $CR$ selects fewer mutant coordinates in expectation. At $d=1$, the forced coordinate keeps the selected count at one for every $CR$. Coordinate dependence alone does not supply a universal best setting.

In matrix form, let $M^{(g)}$ be the $NP \times d$ zero-one mask with $M_{i,j} = 1$ when coordinate $j$ of row $i$ is inherited from the mutant, including the forced column. Then

$$U^{(g)} = M^{(g)} \odot V^{(g)} + \left(\mathbf{1} - M^{(g)}\right) \odot X^{(g)}$$

where:

• $U^{(g)}$: the $NP \times d$ matrix of trial vectors
• $M^{(g)}$: the $NP \times d$ binary mask selecting mutant coordinates
• $V^{(g)}$: the $NP \times d$ matrix of mutant vectors
• $X^{(g)}$: the $NP \times d$ matrix of target vectors
• $\odot$: elementwise (Hadamard) product
• $\mathbf{1}$: the all-ones matrix, so $\mathbf{1} - M^{(g)}$ selects the target coordinates

Writing it this way makes clear that crossover is a selection of entries, not an arithmetic blend: no new coordinate values are created, only copied.

Selection is then greedy and one-to-one. Each trial competes only with its own target:

$$\mathbf{x}_i^{(g+1)} = \begin{cases} \mathbf{u}_i^{(g)}, & \text{if } f\!\left(\mathbf{u}_i^{(g)}\right) \le f\!\left(\mathbf{x}_i^{(g)}\right) \\ \mathbf{x}_i^{(g)}, & \text{otherwise} \end{cases}$$

where:

• $\mathbf{x}_i^{(g+1)}$: the target vector for slot $i$ at the next generation
• $\mathbf{u}_i^{(g)}$: the trial vector for slot $i$
• $\mathbf{x}_i^{(g)}$: the current target vector
• $f$: the objective function to minimize

This rule compares a trial only with its own target. Our <= convention accepts ties; a strictly worse trial is discarded. For a fixed deterministic objective, every retained slot value is non-increasing, so the population minimum is non-increasing too. This property does not ensure diversity or a global optimum.

In a deferred generation, every donor and target comes from generation $g$, and the accepted replacements are installed together. Our code freezes that population explicitly. An immediate variant allows later proposals in a sweep to use earlier replacements. With fixed update order and random-number stream either can be reproducible, but the trajectories can differ; there is no general faster-convergence guarantee.

Initialization respects the box, but a mutant can leave it. This can happen even for $F<1$, depending on the base and donor difference. We will clip mutants before crossover; other choices change the proposal distribution:

• Clipping maps a coordinate to $\min(u_j,\max(l_j,v_j))$. It enforces its interval but can concentrate proposals on the boundaries. It does not enforce coupled non-box constraints.
• Reflection sends a lower-bound violation to $2l_j-v_j$ or an upper-bound violation to $2u_j-v_j$. Large overshoots need repeated reflection or an equivalent folding rule.
• Reinitialization samples a violating coordinate again inside its interval, discarding that coordinate's differential step. These are different search choices, not interchangeable guarantees.

For non-box constraints, a penalty, a repair procedure, or a feasible reparametrization needs its own validation. A penalty alone does not certify feasibility. Count every objective evaluation performed while repairing or comparing candidates, and validate every reported solution against the original constraints.

Our comparison stops at a fixed candidate-evaluation budget. Population spread, changes in the incumbent, or a generation limit can also be stopping rules without knowing the optimum. A tolerance on objective spread measures agreement among current candidates; it is not a test of distance to the global optimum. Every stopping rule and its evaluation cost should be reported.

For a fixed deterministic objective, let $b^{(g)}=\min_i f(\mathbf{x}_i^{(g)})$. Each selected slot either retains its old value or takes a value no larger, so $f(\mathbf{x}_i^{(g+1)})\le f(\mathbf{x}_i^{(g)})$ and therefore $b^{(g+1)}\le b^{(g)}$. An archived minimum over all evaluated candidates is also non-increasing. Neither statement implies strict progress; with noisy evaluations it applies to the stored observations, not necessarily to true expected costs.

The mutation operator is translation and rotation equivariant: if we rotate every population member by an orthogonal matrix $Q$, the mutant rotates by $Q$ as well, because

$$Q\mathbf{x}_{r_1} + F(Q\mathbf{x}_{r_2} - Q\mathbf{x}_{r_3}) = Q\left(\mathbf{x}_{r_1} + F(\mathbf{x}_{r_2} - \mathbf{x}_{r_3})\right)$$

Binomial crossover is not rotation equivariant because it chooses entries in a fixed coordinate basis. Diagonal affine changes of units are different: for $\mathbf{x}=\mathbf{a}+S\mathbf{z}$ with diagonal $S$ having positive entries, mutation gives $\mathbf{a}+S[\mathbf{z}_{r_1}+F(\mathbf{z}_{r_2}-\mathbf{z}_{r_3})]$. The same crossover mask commutes with this coordinate-wise transformation. With matching bounds, initialization, and arithmetic, this preserves the transformed search; it does not imply rotation invariance or immunity to numerical tolerances.

These update rules provide no finite-budget global-optimum guarantee. A small spread can explain short mutation steps, but the population may have contracted in the wrong basin. We do not assume a geometric convergence rate or identify this mechanism with an annealing theorem.