CMA-ES
- Covariance Matrix Adaptation Evolution Strategy
- CMA-ES only needs a score for each candidate answer, and it looks for the lowest score. It does not need a gradient, the slope that shows which way the score goes down.
- It draws candidates, called samples, at random from a normal distribution \(\mathcal{N}(m, \sigma^2 C)\), so most of them land near the center. Each round, called a generation, it draws \(\lambda\) samples, ranks them by score, and uses the best ones to set up the next round.
- \(m\) is the center of the search. The step size \(\sigma\) sets how far the samples spread. The matrix \(C\) sets the shape: which directions spread more.
- Example: the smallest circle containing all points
- Find the smallest circle that contains six points. Each sample is a possible center \((x, y)\), so there are two numbers to find: \(n = 2\).
-
From a center \((x, y)\), the circle must reach the farthest of the six points \(p_i\). So the distance to that farthest point is the radius, and it is also the score \(f\).
\[ f(x, y) = \max_i \, \lVert (x, y) - p_i \rVert \]
- In Fig. 1, blue arrows point to the samples we keep, and a thicker arrow means more weight. The red line is the path of the center.
How it evolves
-
How \(m\) is calculated
- Without the 0.5, rank 3 would get \(\ln(3/3)=0\), so it would get no weight.
- Give each rank a log score, \(\ln\!\left(\frac{3.5}{\text{rank}}\right)\). Divide each log score by the sum of all three, so the weights add up to 1.
- Multiply each kept sample by its weight and add them up. The result is the new center \(m\).
Rank Log score Weight -
How \(C\) and \(\sigma\) change
The dashed ellipse in Fig. 1 shows where most samples land. A few can land outside it. \(C\) can stretch or turn the ellipse. \(\sigma\) only scales it, so the ellipse gets bigger or smaller but keeps its shape. The example below uses simple numbers to show how \(C\) changes.
-
Learn from the best samples
Say the old center is \(m_{\text{old}}=(0,0)\) and \(\sigma=1\). The three best samples, from best to third, are \(s_1=(2,0)\), \(s_2=(0,2)\), and \(s_3=(-2,0)\). To keep the numbers easy, give them weights of \(0.5\), \(0.25\), and \(0.25\). Draw an arrow from the old center to each sample, then divide it by \(\sigma\) to get \(d_i\). Since \(\sigma=1\), the arrows do not change. \[ \begin{aligned} d_1 &= \frac{s_1 - m_{\text{old}}}{\sigma} = (2,0)-(0,0) = \begin{pmatrix}2\\0\end{pmatrix} \\[0.5em] d_2 &= \frac{s_2 - m_{\text{old}}}{\sigma} = (0,2)-(0,0) = \begin{pmatrix}0\\2\end{pmatrix} \\[0.5em] d_3 &= \frac{s_3 - m_{\text{old}}}{\sigma} = (-2,0)-(0,0) = \begin{pmatrix}-2\\0\end{pmatrix} \end{aligned} \] To turn an arrow into a spread, multiply it as a column by itself as a row, \(d_i d_i^\top\). The result is a 2×2 matrix that spreads along the arrow's line. For \(d_1=(2,0)\), the top-left number is \(2^2=4\) and the rest are zero, so it spreads only sideways. \(d_3\) points left but gives the same matrix, because \((-2)^2=4\). \(d_2\) points up, so its \(4\) goes to the bottom right. In Fig. 2, each arrow is drawn \(\sqrt{w_i}\) times as long. The column and the row each carry one \(\sqrt{w_i}\), and \(\sqrt{w_i}\times\sqrt{w_i}=w_i\), so each matrix gets its weight.\[ \begin{aligned} S &= 0.5 d_1 d_1^\top + 0.25 d_2 d_2^\top + 0.25 d_3 d_3^\top \\[0.5em] &= \begin{pmatrix}2&0\\0&0\end{pmatrix} + \begin{pmatrix}0&0\\0&1\end{pmatrix} + \begin{pmatrix}1&0\\0&0\end{pmatrix} \\[0.5em] &= \begin{pmatrix}3&0\\0&1\end{pmatrix} \end{aligned} \]Weighted samples How much should \(S\) affect \(C\)? That depends on how many samples really count, called the effective sample count \(\mu_{\text{eff}}\). It is 1 divided by the sum of the squared weights. With three equal weights it would be exactly 3. Here the best sample counts more, so it is about 2.67.
\[ \begin{aligned} \mu_{\text{eff}} &= \frac{1}{\vphantom{\rule{0pt}{1.3em}}w_1^2+w_2^2+w_3^2} \\[0.5em] &= \frac{1}{\vphantom{\rule{0pt}{1.3em}}0.5^2+0.25^2+0.25^2} \approx 2.67 \end{aligned} \]CMA-ES sets two rates with the default formulas below. They use \(n\), the number of values we choose, and \(\mu_{\text{eff}}\). \(c_\mu\) sets how much \(S\) affects \(C\). \(c_1\) sets how much the record of center moves affects \(C\). That record comes in the next step.
\[ \begin{aligned} c_1 &= \frac{2}{\vphantom{\rule{0pt}{1.3em}}(n+1.3)^2+\mu_{\text{eff}}} \\[0.5em] c_\mu &= \min\left( 1-c_1,\, \frac{2(\mu_{\text{eff}}-2+1/\mu_{\text{eff}})} {\vphantom{\rule{0pt}{1.3em}}(n+2)^2+\mu_{\text{eff}}} \right) \end{aligned} \]Put in \(n=2\) and \(\mu_{\text{eff}}=2.67\). \(\min\) takes the smaller of its two values. The fraction gives \(0.11\), which is smaller than \(1-c_1\approx0.85\), so \(c_\mu=0.11\).
\[ \begin{aligned} c_1 &= \frac{2}{\vphantom{\rule{0pt}{1.3em}}(2+1.3)^2+2.67} \approx 0.15 \\[0.5em] c_\mu &= \frac{2(2.67-2+1/2.67)}{\vphantom{\rule{0pt}{1.3em}}(2+2)^2+2.67} \approx 0.11 \end{aligned} \]Round the rates to two decimal places. \(S\) gets \(0.11\), and \(0.15\) is kept for the center moves in the next step. The old spread \(C_{\text{old}}=I\), the circle we start with, keeps the rest: \(1-0.15-0.11=0.74\).
\[ C_{\text{samples}} = 0.74 I + 0.11 S = \begin{pmatrix}1.07&0\\0&0.85\end{pmatrix} \]Wider and shorter -
Learn from center moves
The weighted average of the three samples is the new center, so the center moves from \((0,0)\) to \((0.5,0.5)\). Dividing by \(\sigma=1\) leaves this move the same. CMA-ES keeps a running record of center moves, the vector \(p_c\). In this example, the old record is \((1,1)\). Keep half of it and add the latest move. \[ p_{c,\text{new}} = 0.5\begin{pmatrix}1\\1\end{pmatrix} + \begin{pmatrix}0.5\\0.5\end{pmatrix} = \begin{pmatrix}1\\1\end{pmatrix} \] \(p_c\), the orange arrow, points up and right. As before, column times row gives a matrix, here all ones. Multiply it by \(c_1=0.15\) and add it to \(C_{\text{samples}}\). This tilts the ellipse toward the way the center keeps moving.\[ \begin{aligned} C_{\text{new}} &= C_{\text{samples}} + 0.15 \begin{pmatrix}1&1\\1&1\end{pmatrix} \\ &= \begin{pmatrix}1.22&0.15\\0.15&1\end{pmatrix} \end{aligned} \]Tilt from moves -
Change size (\(\sigma\))
For \(\sigma\), CMA-ES keeps a second record of center moves. Each round, it keeps part of the old record and adds the latest move, measured against the old spread. Moves in the same direction add up. Moves that turn back partly cancel.
In Fig. 5, the old record (blue) is 1.034 long and points right. The latest move (orange) is 1.398 long. If it also points right, the total length is \(L\approx 2.43\) (top). If it points left, \(L\approx 0.36\) (bottom).
Compare \(L\) with 1.25, the length we would expect if the moves were random in 2D: \(r = L/1.25\). If \(r\) is above 1, the center keeps going one way, so the steps are too small and \(\sigma\) grows. If \(r\) is below 1, the moves cancel, so the steps are too big and \(\sigma\) shrinks. This example uses an update rate of 0.289. The dashed circles show the old size.
\[ \begin{aligned} r &= L/1.25 \\[0.5em] \sigma_{\text{new}} &= \sigma_{\text{old}}\,e^{0.289(r-1)} \\[0.5em] L=2.43 &\;\Rightarrow\; \sigma_{\text{new}}\approx 1.31\sigma_{\text{old}} \\ L=0.36 &\;\Rightarrow\; \sigma_{\text{new}}\approx 0.81\sigma_{\text{old}} \end{aligned} \]σ × 1.31 / σ × 0.81
-
Learn from the best samples
References:
- Nikolaus Hansen, The CMA Evolution Strategy: A Tutorial
- Nikolaus Hansen and Andreas Ostermeier, Completely Derandomized Self-Adaptation in Evolution Strategies
- Anne Auger and Nikolaus Hansen, A Restart CMA Evolution Strategy With Increasing Population Size
- pycma
- Smallest-circle problem