Module cmaes 

The covariance matrix adaptation evolution strategy (CMA-ES).

Each generation draws λ candidates from a normal distribution about a mean m, with an overall step size σ and a covariance C that sets the steps’ shape. The model ranks them; the mean moves to a weighted average of the best μ = ⌊λ/2⌋. The step size grows when successive moves point the same way and shrinks when they cancel (cumulative step-size adaptation), and the covariance learns the directions the good steps took (the rank-one and rank-μ updates). Only the ranking matters, so the strategy is unchanged by any increasing transformation of the output, and by any rotation of the variables once C has adapted.

The algorithm and its default parameters are those of N. Hansen, “The CMA Evolution Strategy: A Tutorial”, arXiv:1604.00772v2 (2023), https://arxiv.org/abs/1604.00772: Appendix A’s summary (Figure 6, eqs. (38) to (47), pp. 28–29) with Table 1’s default parameters (eqs. (48) to (58), p. 31), and with the weights after the μ-th zero, as in the tutorial’s own code (“This code does not implement negative weights, that is, wᵢ = 0 for i > µ in Table 1”, p. 36): the original strategy, not the active one. Equations, for a generation g counted from 0:

yₖ = B D zₖ,  zₖ ~ N(0, I),  xₖ = m + σ yₖ                        (sampling, k = 1 … λ)
⟨y⟩ = Σᵢ wᵢ yᵢ:λ                                                  (the μ best, ranked)
m ← m + c_m σ ⟨y⟩
p_σ ← (1 − c_σ) p_σ + √(c_σ (2 − c_σ) μ_eff) C^(−1/2) ⟨y⟩
σ ← σ exp((c_σ/d_σ) (‖p_σ‖/E‖N(0, I)‖ − 1))
h_σ = 1 if ‖p_σ‖/√(1 − (1 − c_σ)^(2(g+1))) < (1.4 + 2/(n + 1)) E‖N(0, I)‖, else 0
p_c ← (1 − c_c) p_c + h_σ √(c_c (2 − c_c) μ_eff) ⟨y⟩
C ← (1 + c₁ δ(h_σ) − c₁ − c_μ Σwⱼ) C + c₁ p_c p_cᵀ + c_μ Σᵢ wᵢ yᵢ:λ yᵢ:λᵀ

with δ(h_σ) = (1 − h_σ) c_c (2 − c_c) and E‖N(0, I)‖ ≈ √n (1 − 1/(4n) + 1/(21n²)). C = B D² Bᵀ is decomposed every generation, by Jacobi’s method; the tutorial allows putting it off for up to 1/(10 n (c₁ + c_μ)) generations (B.2, p. 33), which is under one for up to about 85 variables at the default population.

Starting point and scaling

The strategy works in each Variable divided by its step. There it starts as the tutorial’s Figure 6 does, with σ = 1, C = I and both paths zero, at the variables’ starts. So a variable in meters and another in kilograms each start with the steps the caller gave them, and the condition number the run stops at is the tutorial’s. This is the tutorial’s advice for variables whose search intervals differ: “a scaling of the variables should be applied” (Figure 6’s footnote, p. 29). Run::covariance is C in these scaled variables.

Bounds

A candidate outside its variables’ bounds is drawn again, from its own stream, until it falls inside: the second of the two methods the tutorial gives for a best point strictly inside the feasible region (“re-sampling any infeasible solution x until it become feasible”, B.5, p. 34). No candidate is repaired onto a bound, which the tutorial advises against. If any one candidate of a generation is still outside after MAX_DRAWS tries, the run ends (Stop::Bounds). The chance that a draw falls inside halves with each variable whose mean sits on a bound, so with many variables near their bounds this comes soon. A best point on a bound is reached only slowly this way; for a bound that binds, leave the variable unbounded on that side and write the bound as a constraint.

Integer variables

An integer variable (Variable::integer) is drawn as a real number like the others, and the model is given the whole number nearest the draw, clamped to its bounds (Variable::encode); the update learns from the real draws. Left at that, the spread in an integer variable would shrink until every draw gave the same whole number and that variable stopped moving, wherever it was. CMA-ES with margin (R. Hamano, S. Saito, M. Nomura and S. Shirakawa, “CMA-ES with Margin: Lower-Bounding Marginal Probability for Mixed-Integer Black-Box Optimization”, GECCO 2022, https://arxiv.org/abs/2205.13482, §4 and Algorithm 1, pp. 5–6 and 10) prevents it: after each update it keeps at least a chance α = 1/(n λ) that a draw lands on another value, by moving the mean towards a threshold or by stretching that variable’s draws by a factor A (Run::margin_scale):

xₖ = m + σ S A yₖ                                    (S the steps, A diagonal, 1 if continuous)
s = σ A S √C_jj                                       (variable j's spread)
at an end value, threshold ℓ:  m ← ℓ + sign(m − ℓ) min(|m − ℓ|, Φ⁻¹(1 − α) s)      eq. (13)
inside, thresholds ℓ₋ < m ≤ ℓ₊:
  p₋ = Φ((ℓ₋ − m)/s),  p₊ = Φ((m − ℓ₊)/s),  p₀ = 1 − p₋ − p₊                  eqs. (17)–(19)
  p′ = max(α/2, p),  p″ = p′ + (1 − p′₋ − p′₊ − p₀)(p′ − α/2)/(p′₋ + p′₊ + p₀ − 3α/2)
  χ = Φ⁻¹(1 − p″):  m ← (ℓ₋ χ₊ + ℓ₊ χ₋)/(χ₋ + χ₊),  A ← (ℓ₊ − ℓ₋)/((χ₋ + χ₊) σ S √C_jj)   (24)

The thresholds lie halfway between neighbouring whole numbers; the mean, σ and C are the updated ones and A the old one in s. The paths and C never see the correction. An integer variable’s draws are never redrawn for its bounds, which its encoding enforces. The paper’s α is the default here; its Figure 4 (p. 7) finds the method works across a range about it. Φ is the standard normal distribution function.

Constraints

Other constraints go through Run::tell_constrained, which ranks candidates by Deb’s feasibility rules (Evaluation): any candidate that keeps every constraint ranks ahead of any that doesn’t, and those that don’t rank by how far they break them. Infeasible candidates are evaluated and ranked, not drawn again, so the distribution can sit across a constraint’s edge and close in on a minimum that lies on it.

Stopping

A run stops at the first of: a target value reached (Stop::Target), the evaluations used up (Stop::Evaluations), the distribution’s spread and its evolution path below a tolerance in every variable (Stop::TolX), the best values of the last 10 + ⌈30 n/λ⌉ generations and every value of the last one all within a tolerance (Stop::TolFun), the covariance’s condition number above 10¹⁴ or a step or candidate that has overflowed (Stop::Condition), or a candidate that can’t be drawn inside the bounds (Stop::Bounds). These are the tutorial’s TolX, TolFun and ConditionCov (B.3, pp. 33–34), with its suggested 10⁻¹² for both tolerances, TolX’s taken in the scaled variables, so as a fraction of each one’s step. Its NoEffectAxis, NoEffectCoord, Stagnation and TolXUp tests are left out: a run that diverges ends at Stop::Condition, or at the evaluation cap.

A run with no finite value

If every candidate so far has given +∞ (every flight failed, say), the run goes on, ranking them in their order, and its Optimum’s value is +∞. Check Optimum::value before using the point; under constraints, check Optimum::violation too, which is above zero if no candidate kept them all.

Structs

Cmaes

The optimizer’s settings: the variables, the population, and when to stop. It serializes as its fields, and reads back through the same checks as Cmaes::new and its with_ methods.

Optimum

What a run found.

Parameters

The strategy’s parameters for n variables and population λ: the tutorial’s Table 1 with the negative weights set to zero. Run::parameters gives a run’s; they serialize, but aren’t read back, as nothing takes them in.

Run

A run in progress: its distribution, the current generation’s candidates, and the best point so far.

Enums

Stop

Why a run stopped.

Constants

MAX_CONDITION

The covariance’s largest condition number before a run stops: its axes’ lengths then differ by 10⁷, about where rounding in f64 starts to blur the shortest.

MAX_DRAWS

The most times one candidate is drawn again to fall inside the bounds.

MAX_POPULATION

The largest population a run takes.