📐CMA-ES 정독 노트: 정규분포 하나로 계곡을 내려가는 법

cma-es

optimization

evolution-strategy

storage

미분도, 함수값도 필요 없다 — 순위만으로 헤시안의 역행렬을 배우는 알고리즘의 이론 정리.

Published

August 24, 2026

Covariance Matrix Adaptation Evolution Strategy. 이름이 길지만 하는 일은 하나입니다. 탐색 분포 \mathcal{N}(m, \sigma^2 C) 를 매 세대 조금씩 옮기고, 넓히거나 좁히고, 회전시켜서 목적함수의 골짜기 모양에 맞춰 나갑니다.

이 글은 이론 쪽 정리입니다. 코드를 한 줄씩 쌓아 올리는 실습편은 따로 있습니다 → 👩‍💻CMA-ES 한 걸음씩: pycma로 배우는 진화 전략

표기 기준

수식 표기는 Hansen, “The CMA Evolution Strategy: A Tutorial” (2016) 을 따릅니다. 본문 구성은 Wikipedia: CMA-ES 를 뼈대로 삼았습니다.

먼저 돌려 보기

아래는 2차원 (\mu/\mu_w, \lambda)-CMA-ES를 그대로 구현한 시뮬레이터입니다. 재생을 누르면 매 세대 \lambda 개의 점이 뿌려지고, 초록 타원(C)과 주황 게이지(\sigma)가 지형에 맞춰 변해 갑니다. 수식은 이 장면을 하나씩 해부한 것일 뿐이니, 먼저 눈으로 보고 오는 편이 빠릅니다.

타원이 골짜기 방향으로 눕고 늘어나는 순간이 이 알고리즘의 전부입니다. 조건수가 200인 기울어진 타원체에서, C 는 좌표축과 무관한 비스듬한 방향을 스스로 찾아냅니다. 게이지가 \chi_n 표시 오른쪽에 있으면 \sigma 가 커지고, 왼쪽에 있으면 작아집니다.

01. 미분을 못 구하는 문제가 실제로는 훨씬 많다

CMA-ES는 f(x) 를 계산해 볼 수는 있지만 미분할 수는 없는 연속 최적화 문제를 위한 알고리즘입니다.

풀려는 문제는 이것뿐입니다. \min_{x \in \mathbb{R}^n} f(x). 다만 f 에 대해 아는 게 거의 없습니다. 기울기를 못 구하고, 볼록하지도 않고, 변수마다 스케일이 제멋대로고, 봉우리가 여러 개거나 값에 노이즈가 섞여 있습니다.

로봇 쪽 예를 들면 감이 빠릅니다. 임피던스 제어기 게인 12개를 실기에서 튜닝한다고 해봅시다. 평가 한 번에 30초가 걸리고, “게인을 0.1 올리면 성능이 얼마나 변하는가”의 도함수는 존재하지 않습니다. 손에 남는 건 이 조합이 저 조합보다 나았다는 비교뿐입니다.

CMA-ES가 f 에서 가져가는 정보는 순위뿐

바로 그 지점이 핵심입니다. CMA-ES는 f 의 값 자체를 쓰지 않습니다. \lambda 개의 후보를 평가한 뒤 좋은 순서대로 줄 세우고, 그 순서만 사용합니다. 값이 0.001 과 0.002 든 10^6 과 10^9 든 결과가 같습니다.

이 성질이 공짜로 주는 게 큽니다.

f 대신 \log f 를 최소화해도, f^3 을 최소화해도 알고리즘의 궤적은 완전히 동일합니다 (단조 증가 변환에 대한 불변성).
목적함수를 정규화하려고 애쓸 필요가 없어집니다.
극단적으로는 명시적 f 가 아예 없어도 됩니다. 위키 문서가 드는 예가 스위스식 토너먼트인데, 후보끼리 대전시켜 얻은 승패 순위만으로도 알고리즘은 돌아갑니다.

한 줄로

CMA-ES는 f 를 “측정”하지 않고 “비교” 합니다. 비교만으로 이차 모델(헤시안의 역행렬에 해당하는 것)을 배우는 것이 이 알고리즘의 놀라운 점입니다.

02. 어두운 계곡에 자갈을 뿌리는 사람

알고리즘 전체를 한 문장으로 줄이면, 정규분포 하나를 매 세대 조금씩 고쳐 나가는 것입니다.

안개 낀 계곡에 서 있다고 상상해 보세요. 발밑 지형은 보이지 않고, 손에는 자갈 \lambda 개가 있습니다. 할 수 있는 건 자갈을 던지고, 누군가 “이 자갈이 저 자갈보다 낮은 데 떨어졌다”고 순위를 알려주는 것뿐입니다.

합리적인 사람이라면 이렇게 하겠죠.

좋은 자갈들이 떨어진 쪽으로 몸을 옮긴다. → 분포 평균 m 갱신
좋은 자갈들이 한 방향으로 길게 늘어서 있으면, 다음엔 그 방향으로 길쭉하게 뿌린다. → 공분산 C 갱신
계속 같은 방향으로 전진 중이면 더 멀리 뿌리고, 제자리에서 왔다 갔다 하면 좁게 뿌린다. → 스텝 사이즈 \sigma 갱신

CMA-ES는 이 세 가지 상식을 수식으로 정확하게 옮긴 것입니다. “얼마나 옮길지”, “얼마나 길쭉하게 할지”의 계수들이 무작정 튜닝된 값이 아니라 통계적 근거(최대우도, 자연 그래디언트, 무편향 조건)에서 유도된다는 점이 다를 뿐입니다.

왜 굳이 공분산 행렬까지 배우나

변수들이 서로 얽혀 있고(non-separable) 스케일이 다르면(ill-conditioned) 축에 나란한 탐색은 무력합니다. 조건수 10^6 짜리 골짜기에서 등방(isotropic) 정규분포로 샘플링하면, 골짜기를 따라가는 성분은 사실상 뽑히지 않습니다.

C 를 배운다는 것은 문제의 좌표계를 다시 잡는 것과 같습니다. 볼록 이차함수라면 C 는 헤시안의 역행렬 H^{-1} 에 (스칼라 배수까지) 수렴합니다. quasi-Newton 계열이 미분으로 하는 일을, CMA-ES는 순위만으로 해냅니다.

03. 기억해야 할 것은 다섯 개뿐이다

CMA-ES가 세대 사이에 들고 다니는 상태는 정확히 다섯 개입니다.

기호	이름	역할	타입
m	분포 평균	현재의 최선 추정치. 알고리즘이 끝나면 이 값을 답으로 내놓습니다 (보통 best 샘플보다 m 이 더 좋습니다)	\mathbb{R}^n · 벡터
\sigma	스텝 사이즈	분포의 전체 크기를 정하는 스칼라. 수렴 속도를 지배하며, 조기 수렴을 막는 안전장치	\mathbb{R}_+ · 스칼라
C	공분산 행렬	분포의 모양과 방향. 대칭 양정부호. 여기에 문제의 이차 구조가 저장됩니다	\mathbb{R}^{n\times n} · 자유도 n(n{+}1)/2
p_\sigma	등방 진화 경로	최근 이동들을 화이트닝해서 누적한 벡터. 길이를 재서 \sigma 를 조절	\mathbb{R}^n · 초기값 0
p_c	비등방 진화 경로	최근 이동을 그대로 누적한 벡터. C 에 “지금 가고 있는 방향”을 주입	\mathbb{R}^n · 초기값 0

여기서 진화 경로 두 개가 이 알고리즘의 특징입니다. 한 세대의 정보만 보면 잡음이 크지만, 연속된 세대의 이동을 누적하면 방향의 일관성이 드러납니다. 같은 쪽으로 계속 갔다면 경로는 길어지고, 지그재그였다면 짧아집니다. 이 길이 하나로 \sigma 를 조절하고, 이 방향 하나로 C 를 늘립니다.

04. 한 세대에서 일어나는 일

루프는 샘플링 → 정렬 → 다섯 개 상태 갱신, 이 세 덩어리입니다. 그리고 갱신 순서가 정말로 중요합니다.

#	단계	내용
0	\lambda 개 샘플링 & 평가	x_i = m + \sigma y_i,\ y_i \sim \mathcal{N}(0, C). f(x_i) 를 \lambda 번 계산합니다. 이 \lambda 번이 전체 비용의 거의 전부이고, 서로 독립이라 병렬화가 자유롭습니다
1	f 기준 정렬	f(x_{1:\lambda}) \le \cdots \le f(x_{\lambda:\lambda}). 여기서 f 는 역할을 다했습니다. 이후 등장하는 건 인덱스뿐
2	m 갱신 (반드시 먼저)	상위 \mu 개의 가중 평균으로 평균을 옮깁니다. 이동량 (m_{\text{new}} - m_{\text{old}})/\sigma 를 뒤의 네 갱신이 전부 재사용하므로 순서상 첫 번째여야 합니다
3	p_\sigma 갱신	이동량을 C^{-1/2} 로 화이트닝해 누적. 여기서 쓰는 C 는 아직 갱신하지 않은 옛 C 입니다. 그래서 C 갱신보다 앞
4	p_c 갱신	화이트닝 없이 이동량을 그대로 누적. 다만 \sigma 가 폭주 중이면 브레이크(h_\sigma)를 거는데, 그 판정에 방금 계산한 p_\sigma 가 필요합니다
5	C 갱신	rank-one(경로) + rank-\mu(이번 세대 성공 스텝들)의 가중합. 옛 C 는 (1 - c_1 - c_\mu) 만큼 남깁니다
6	\sigma 갱신 (반드시 마지막)	\\|p_\sigma\\| 를 기댓값 \chi_n 과 비교해 지수적으로 키우거나 줄입니다

순서 규칙

m 이 가장 먼저, p_\sigma 가 \sigma 보다 먼저, \sigma 가 가장 마지막. 이유는 단순합니다. C^{-1/2} 는 옛 C 에서 나와야 하고, h_\sigma 판정은 새 p_\sigma 를 필요로 하며, \sigma 갱신은 이번 세대의 다른 계산에 영향을 주면 안 되기 때문입니다.

05. 좌표계를 바꿔서 뽑는다

x_i^{(g+1)} \;=\; \underbrace{m^{(g)}}_{\text{어디서}} \;+\; \underbrace{\sigma^{(g)}}_{\text{얼마나 멀리}}\,\underbrace{y_i}_{\text{어떤 모양으로}},\qquad y_i \sim \mathcal N\!\left(0,\;C^{(g)}\right),\quad i=1,\dots,\lambda

m + \sigma y 라는 분해가 중요합니다. 크기(\sigma)와 모양(C)을 분리했기 때문에 서로 다른 시간 척도로, 서로 다른 규칙으로 학습시킬 수 있습니다.

실제 구현은 C 를 고유분해해서 씁니다.

C = B\,D^2\,B^{\!\top},\qquad x_i = m + \sigma\,B\,D\,z_i,\quad z_i\sim\mathcal N(0,I)

B 는 고유벡터를 모은 회전 행렬, D 는 각 주축의 표준편차를 담은 대각 행렬. 등방 잡음 z 를 D 로 늘이고 B 로 돌린 것이 y 입니다. C^{-1/2} = B D^{-1} B^\top 도 여기서 바로 얻습니다.

이 식을 반대로 읽으면 더 재미있습니다. 양변에 (\sigma B D)^{-1} 를 곱하면, C 를 학습하는 것은 문제 공간을 선형 변환해서 등방 문제로 만드는 것과 정확히 같은 일입니다. Hansen이 이를 “adaptive encoding” 이라 부르며 일반화한 이유입니다. 원래 문제가 조건수 10^6 짜리 길쭉한 골짜기라도, 인코딩된 공간에서는 동그란 구가 됩니다.

비용 참고

고유분해는 O(n^3) 이라 매 세대 하면 비쌉니다. 그래서 실제 구현은 약 \lambda / (c_1 + c_\mu) / n / 10 번의 평가마다 한 번씩만 분해해서 평균 O(n^2) 로 맞춥니다. 위키에 실린 purecmaes.m 의 eigeneval 로직이 이 부분입니다.

06. 좋은 것들의 가중 평균

m^{(g+1)}=\sum_{i=1}^{\mu} w_i\,x_{i:\lambda}^{(g+1)},\qquad \sum_{i=1}^{\mu} w_i = 1,\quad w_1\ge w_2\ge\cdots\ge w_\mu>0

x_{i:\lambda} 는 f 기준 i 번째로 좋은 샘플. 보통 \mu = \lfloor \lambda/2 \rfloor 이고 w_i \propto \ln(\mu + \tfrac12) - \ln i 입니다.

왜 최고 하나만 쓰지 않을까요. 평가에는 노이즈가 있고, 하나의 표본은 방향 추정이 불안정하기 때문입니다. 여러 개를 평균 내면 분산이 줄지만, 대신 나쁜 표본이 섞여 편향이 생깁니다. 로그 가중치는 그 사이의 절충안입니다.

\mu_{\text{eff}}: 실질적으로 몇 개를 쓴 셈인가

\mu_{\text{eff}} \;=\; \frac{\left(\sum_i w_i\right)^2}{\sum_i w_i^{2}} \;=\; \frac{1}{\sum_i w_i^{2}} \;\in\; [1,\ \mu]

“분산 유효 선택 질량” (variance effective selection mass). 모든 가중치가 같으면 \mu, 하나에 몰빵하면 1. 이후 거의 모든 계수(c_\sigma, c_c, c_1, c_\mu, d_\sigma)에 등장하는 값입니다.

\mu_{\text{eff}} 가 크다는 것은 평균 추정이 그만큼 신뢰할 만하다는 뜻이고, 그러면 학습률을 더 크게 잡아도 됩니다. 기본 설정은 \mu_{\text{eff}} \approx \lambda/4 정도가 되게 잡혀 있습니다.

07. 성공한 방향들의 PCA를 계속 갱신한다

C 갱신은 세 항의 합입니다. 옛 C 를 유지하는 항, 진화 경로에서 오는 rank-one 항, 이번 세대에서 오는 rank-\mu 항.

C^{(g+1)}=\underbrace{\left(1-c_1-c_\mu\right)C^{(g)}}_{\text{기억}} +\underbrace{c_1\left(p_c^{(g+1)}p_c^{(g+1)\top}+\delta(h_\sigma)\,c_c(2-c_c)\,C^{(g)}\right)}_{\text{rank-one}} +\underbrace{c_\mu\sum_{i=1}^{\mu}w_i\,y_{i:\lambda}\,y_{i:\lambda}^{\top}}_{\text{rank-}\mu}

여기서 y_{i:\lambda} = (x_{i:\lambda}^{(g+1)} - m^{(g)})/\sigma^{(g)} 는 옛 평균 기준의 스텝입니다 (새 평균이 아닙니다). \delta(h_\sigma) = 1 - h_\sigma 이며, 브레이크가 걸렸을 때 잃어버린 분산을 조금 메워 줍니다.

rank-\mu 항: 이번 세대의 성공 방향을 그대로 학습

\sum_i w_i\, y y^\top 는 성공한 스텝들의 (평균을 0으로 고정한) 가중 공분산 추정치입니다. 성공 스텝이 특정 방향으로 몰려 있으면 그 방향의 분산이 커집니다. 성공한 탐색 방향들에 대해 매 세대 주성분 분석을 하고, 모든 주축을 그대로 유지하는 것과 같습니다.

여기서 짚어야 할 미묘한 차이가 있습니다. CMA는 “좋은 해의 위치”가 아니라 “좋은 스텝”의 우도를 높입니다. Cross-Entropy Method나 EDA 계열은 선택된 점들의 위치로 공분산을 추정하는데, 그러면 분포가 계속 줄어드는 쪽으로만 갑니다. 스텝을 학습하면 유리한 방향으로 분산을 키울 수 있습니다.

rank-one 항: 부호가 사라지는 문제를 푼다

rank-\mu 만으로는 놓치는 정보가 있습니다. 외적 y y^\top 는 y 와 -y 를 구분하지 못합니다. 한 세대만 보면 “이 축이 중요하다”는 알 수 있어도 “그 축의 어느 쪽으로 가고 있다”는 알 수 없습니다.

그림 코드 보기

import numpy as np
import matplotlib.pyplot as plt

plt.rcParams["font.family"] = "Noto Sans CJK KR"   # 한글 라벨용
plt.rcParams["axes.unicode_minus"] = False

fig, ax = plt.subplots(1, 2, figsize=(8.6, 3.4), dpi=100)

# (a) 부호 소실
y = np.array([1.0, 0.6])
for s, c in [(1, "tab:blue"), (-1, "tab:red")]:
    ax[0].annotate("", xy=s*y, xytext=(0, 0),
                   arrowprops=dict(arrowstyle="->", lw=2, color=c))
ax[0].text(*(y*1.12), "$+y$", color="tab:blue")
ax[0].text(*(-y*1.3), "$-y$", color="tab:red")
ax[0].set_title("rank-$\\mu$ 단독: 부호 소실")
ax[0].set_xlim(-1.6, 1.6); ax[0].set_ylim(-1.2, 1.2)

# (b) 경로 누적
steps = np.array([[0.7, 0.45], [0.8, 0.5], [0.75, 0.4]])
p = np.zeros(2)
for s in steps:
    ax[1].annotate("", xy=p+s, xytext=p,
                   arrowprops=dict(arrowstyle="->", lw=1.5, color="gray"))
    p = p + s
ax[1].annotate("", xy=p, xytext=(0, 0),
               arrowprops=dict(arrowstyle="->", lw=2.5, color="tab:orange"))
ax[1].text(p[0]*0.5, p[1]*0.5 - 0.32, "$p_c$", color="tab:orange", fontsize=12)
ax[1].set_title("진화 경로: 방향 누적")
ax[1].set_xlim(-0.3, 2.7); ax[1].set_ylim(-0.6, 1.8)

for a in ax:
    a.set_aspect("equal"); a.axhline(0, lw=.5, c="k"); a.axvline(0, lw=.5, c="k")
    a.set_xticks([]); a.set_yticks([])
plt.tight_layout(); plt.show()

Figure 1: 왼쪽: 한 세대의 외적은 방향의 부호를 잃습니다 (yy^\top = (-y)(-y)^\top). 오른쪽: 경로 p_c 는 연속 이동을 누적하므로 일관된 방향일 때만 길어지고, 그 p_c p_c^\top 가 C 를 그 방향으로 크게 늘립니다.

p_c^{(g+1)}=(1-c_c)\,p_c^{(g)}+h_\sigma\sqrt{c_c(2-c_c)\,\mu_{\text{eff}}}\;\frac{m^{(g+1)}-m^{(g)}}{\sigma^{(g)}}

1/c_c 가 경로의 기억 길이(약 n 세대). \sqrt{c_c(2-c_c)\mu_{\text{eff}}} 계수는 “중립 선택 하에서 p_c \sim \mathcal{N}(0, C) 를 유지하라” 는 무편향 조건에서 유일하게 결정됩니다. 임의로 고른 상수가 아닙니다.

덕분에 rank-one 항은 \lambda 가 작아도 (심지어 \lambda=4 라도) 여러 세대에 걸쳐 방향 정보를 쌓아 유리한 방향의 분산을 훨씬 빠르게 키울 수 있습니다. 반면 rank-\mu 는 \lambda 가 클 때 한 세대 안에서 많은 정보를 가져옵니다. 둘은 \lambda 에 대해 상보적이고, 그래서 둘 다 있습니다.

h_\sigma: \sigma 가 폭주할 때 거는 브레이크

h_\sigma=\mathbb 1\!\left[\ \frac{\|p_\sigma^{(g+1)}\|}{\sqrt{1-(1-c_\sigma)^{2(g+1)}}}\;<\;\left(1.4+\frac{2}{n+1}\right)\mathbb E\|\mathcal N(0,I)\|\ \right]

보통은 1입니다. \sigma 가 급격히 커지는 국면(초기 등)에서만 0이 되어 p_c 누적을 잠깐 멈춥니다. \sigma 가 커지는 중에는 이동량이 과대평가되어 C 가 잘못 늘어나기 때문입니다.

학습률이 왜 그렇게 작은가

c_1 \approx 2/n^2, c_\mu \approx \mu_{\text{eff}}/n^2 입니다. C 에는 n(n{+}1)/2 개의 자유도가 있으니, 그것을 신뢰성 있게 추정하려면 최소 O(n^2) 세대가 필요합니다. 학습률이 1/n^2 스케일인 것은 그 정보량 예산을 그대로 반영한 결과입니다. CMA-ES가 수백 차원 이상에서 느려지는 근본 원인이 여기 있습니다. (그래서 대각 근사인 sep-CMA-ES, 저랭크 근사인 VD-CMA / LM-CMA 같은 변형이 나왔습니다.)

Active CMA

요즘 기본값은 나쁜 샘플에 음수 가중치를 주는 active CMA입니다. 하위 \lambda - \mu 개가 놓인 방향은 분산을 적극적으로 줄입니다. 정보 하나를 더 쓰는 셈이라 실제로 꽤 빨라집니다. 단, C 의 양정부호성을 지키기 위한 추가 조건이 붙습니다.

08. 걸어온 길이 얼마나 곧은가

CSA(cumulative step-size adaptation)의 아이디어는 한 줄입니다. 연속된 이동이 서로 직교하도록 \sigma 를 맞춰라.

왜 직교인지 그림으로 보면 명확합니다.

그림 코드 보기

cases = [
    ("$\\sigma$ 가 너무 크다", np.array([[1.4, .9], [-1.2, -.5], [1.3, .8], [-1.1, -.7]]),
     "경로 짧음 → $\\sigma\\downarrow$"),
    ("$\\sigma$ 가 적절하다",  np.array([[1.0, .3], [.2, .9], [.9, -.2], [-.1, .9]]),
     "$\\|p_\\sigma\\|\\approx\\chi_n$ → 유지"),
    ("$\\sigma$ 가 너무 작다", np.array([[.55, .35], [.5, .4], [.55, .3], [.5, .38]]),
     "경로 김 → $\\sigma\\uparrow$"),
]

fig, ax = plt.subplots(1, 3, figsize=(8.8, 2.9), dpi=100)
for a, (title, steps, note) in zip(ax, cases):
    p = np.zeros(2)
    for s in steps:
        a.annotate("", xy=p+s, xytext=p,
                   arrowprops=dict(arrowstyle="->", lw=1.3, color="gray"))
        p = p + s
    a.annotate("", xy=p, xytext=(0, 0),
               arrowprops=dict(arrowstyle="->", lw=2.5, color="tab:orange"))
    a.set_title(title, fontsize=11)
    a.set_xlabel(note, fontsize=10)
    pts = np.vstack([np.zeros((1, 2)), np.cumsum(steps, axis=0)])
    c0, half = pts.mean(0), 1.6          # 세 패널의 축 크기를 동일하게
    a.set_aspect("equal")
    a.set_xlim(c0[0] - half, c0[0] + half); a.set_ylim(c0[1] - half, c0[1] + half)
    a.set_xticks([]); a.set_yticks([])
    a.axhline(0, lw=.5, c="k"); a.axvline(0, lw=.5, c="k")
plt.tight_layout(); plt.show()

Figure 2: 회색은 세대별 이동, 주황은 그 합(진화 경로). 스텝이 너무 크면 목표를 지나쳐 되돌아오느라 합이 짧아지고, 너무 작으면 같은 방향만 반복해 합이 길어집니다.

p_\sigma^{(g+1)}=(1-c_\sigma)\,p_\sigma^{(g)}+\sqrt{c_\sigma(2-c_\sigma)\,\mu_{\text{eff}}}\;\;{C^{(g)}}^{-1/2}\,\frac{m^{(g+1)}-m^{(g)}}{\sigma^{(g)}}

p_c 와 딱 하나 다릅니다. C^{-1/2} 를 곱하는 화이트닝. 분포의 모양을 지워서 등방 좌표로 옮기는 조작입니다.

화이트닝이 왜 필요한가. 길이를 재서 판단하려면 기준값이 있어야 하기 때문입니다. 화이트닝을 거치면 “선택이 무작위일 때” p_\sigma 는 정확히 \mathcal{N}(0, I) 를 따릅니다. 그러면 그 길이의 기댓값을 알 수 있습니다.

\mathbb E\|\mathcal N(0,I)\| \;=\; \chi_n \;\approx\; \sqrt n\left(1-\frac{1}{4n}+\frac{1}{21n^{2}}\right)

\sigma^{(g+1)}=\sigma^{(g)}\exp\!\left(\frac{c_\sigma}{d_\sigma}\left(\frac{\|p_\sigma^{(g+1)}\|}{\chi_n}-1\right)\right)

지수 함수라 \sigma 는 항상 양수이고, 곱셈적으로 변합니다. 괄호 안이 0이면 \sigma 그대로. d_\sigma \approx 1 는 감쇠 계수로, 한 번에 너무 크게 바꾸는 것을 막습니다.

이 조절이 성공하면 결과적으로 연속 이동이 C^{-1} 에 대해 켤레(conjugate) 관계가 됩니다. 실용적으로 중요한 건 두 가지 효과입니다. 조기 수렴을 막고(\sigma 가 필요 이상으로 빨리 줄어들지 않음), 동시에 최적점 근처에서는 선형(로그 선형) 수렴을 허용합니다(\sigma 가 거리에 비례해 줄어듦).

\sigma 와 C 의 역할 분담

\sigma 와 C 가 왜 분리되어 있는지 여기서 드러납니다. C 는 O(n^2) 세대가 걸리는 느린 학습이고, \sigma 는 매 세대 반응하는 빠른 조절입니다. C 가 아직 문제 모양을 못 배운 초기에도 \sigma 는 즉시 반응해 알고리즘을 살려 둡니다.

09. 사용자가 건드릴 파라미터는 사실상 두 개

CMA-ES는 quasi-parameter-free 로 불립니다. 초기값 m^{(0)} 과 초기 \sigma^{(0)} 만 정하면 됩니다. 나머지는 n 과 \mu_{\text{eff}} 만으로 결정됩니다.

기호	기본값	의미
\lambda	4 + \lfloor 3\ln n \rfloor	세대당 샘플 수. 작으면 국소적, 크면 전역적 탐색. 유일하게 조절할 만한 값
\mu	\lfloor \lambda/2 \rfloor	재조합에 쓰는 상위 개수
w_i	\propto \ln(\mu + \tfrac12) - \ln i	정규화 후 합이 1이 되는 로그 감소 가중치
\mu_{\text{eff}}	1 / \sum_i w_i^2	유효 표본 수, 대략 \lambda/4
c_\sigma	(\mu_{\text{eff}}+2)/(n+\mu_{\text{eff}}+5)	p_\sigma 누적률. 기억 길이 \approx n/3 세대
d_\sigma	1 + 2\max\!\big(0, \sqrt{(\mu_{\text{eff}}-1)/(n+1)} - 1\big) + c_\sigma	\sigma 변화 감쇠, 보통 1 근처
c_c	(4 + \mu_{\text{eff}}/n)/(n + 4 + 2\mu_{\text{eff}}/n)	p_c 누적률. 기억 길이 \approx n 세대
c_1	2/((n+1.3)^2 + \mu_{\text{eff}})	rank-one 학습률
c_\mu	\min\!\big(1-c_1,\ 2(\mu_{\text{eff}}-2+1/\mu_{\text{eff}})/((n+2)^2 + \mu_{\text{eff}})\big)	rank-\mu 학습률. 1-c_1 를 넘지 않아야 함
\chi_n	\sqrt n\,(1 - 1/(4n) + 1/(21n^2))	\\|\mathcal{N}(0,I)\\| 의 기댓값

\lambda 를 두 배씩 키우며 재시작하는 IPOP-CMA-ES 는 다봉 함수에서 표준적인 전략입니다. 작은 \lambda 로 빠르게 국소 탐색을 시도하고, 실패하면 점점 전역적인 탐색으로 넘어갑니다.

10. 세 갈래의 이론적 근거

① 최대우도 관점

평균 갱신은 로그 우도를 최대화합니다.

m^{(g+1)}=\arg\max_{m}\ \sum_{i=1}^{\mu} w_i\,\log p_{\mathcal N}\!\left(x_{i:\lambda}^{(g+1)}\;\middle|\;m\right)

흥미롭게도 이 최대화 결과는 공분산 행렬이 무엇이든 동일합니다 (좌표별 최대화가 스케일에 무관하고, 회전에 대해서도 등가이기 때문).

rank-\mu 항 역시 c_\mu = 1,\ c_1 = 0 으로 두면 성공 스텝들의 최대우도 공분산 추정치가 됩니다. 즉 CMA의 두 갱신은 EM 알고리즘과 닮은 점진적 우도 상승입니다. 다만 CMA는 “좋은 점”이 아니라 “좋은 스텝”의 우도를 올린다는 점이 EDA/CEM과 갈리는 지점입니다.

② 자연 그래디언트 관점

Akimoto 등(2010)과 Glasmachers 등(2010)이 독립적으로 발견한 결과입니다. 분포 파라미터 \theta = (m, C) 에 대한 기대 목적값의 자연 그래디언트를 몬테카를로로 근사하면, CMA-ES의 갱신식이 그대로 나옵니다.

\widetilde\nabla_\theta\,\mathbb E_\theta[f] \;=\; F_\theta^{-1}\,\nabla_\theta\,\mathbb E_\theta[f],\qquad F_\theta=\text{Fisher information}

피셔 정보 행렬의 역을 곱하면 그래디언트가 파라미터화 방식에 무관해집니다. C 를 그대로 쓰든 Cholesky 인자를 쓰든 같은 방향이 나온다는 뜻입니다.

c_1 = 0,\ c_\sigma = 0 (rank-one과 스텝 사이즈 제어를 끔)으로 두면 CMA-ES는 Natural Evolution Strategies(NES) 의 한 인스턴스가 됩니다. 거꾸로 말하면 CMA-ES는 NES에 진화 경로 두 개를 더한 것입니다.

Ollivier 등(2017)은 로그 가중치 w_i 가 어디서 오는지도 밝혔습니다. 이 가중치는 f(x) 의 CDF를 순서통계량에서 추정한 값에 고정된 감소 변환을 합성한 것의 일치추정량입니다. 그래서 알고리즘이 f 값의 분포에 전혀 의존하지 않게 됩니다.

③ 불변성

불변성은 “이 함수에서 잘 되면 저 함수 클래스 전체에서 잘 된다” 는 보장이라 실증 결과의 일반화 가능성을 높입니다. CMA-ES는 세 가지를 갖습니다.

목적값의 단조 변환 불변 — f 와 g \circ f (g 는 순증가)에서 동일하게 동작. 순위만 쓰기 때문에 자명합니다.
스케일 불변 — f(x) 와 f(x/\alpha) 가 동일 (초기값을 그에 맞춰 잡으면).
탐색 공간의 회전 불변 — 직교 변환 R 에 대해 f(Rx) 에서 동일. 더 일반적으로 초기 C 를 맞추면 임의의 선형 변환에 대해서도 불변.

세 번째가 특히 귀합니다. 대부분의 최적화 알고리즘은 좌표축에 특권을 부여하는데(좌표별 탐색, 대각 근사 등), 그런 알고리즘은 문제를 회전시키면 성능이 무너집니다. 같은 불변성을 가진 대표적 대안은 Nelder-Mead 정도입니다.

결과적으로 C 가 배우는 것

f(x)=\tfrac12 (x-x^*)^\top H (x-x^*) \quad\Longrightarrow\quad C \;\propto\; H^{-1}

스칼라 배수와 작은 요동을 무시하면 성립합니다. g 가 순증가일 때 g(f(x)) 에서도 마찬가지입니다. 미분 없이 유사 뉴턴법을 하는 셈입니다.

실습편에서 직접 확인

이 C \propto H^{-1} 은 말로만 그럴듯한 게 아니라 숫자로 바로 찍힙니다. 조건수 10^4 짜리 이차함수에 밑바닥 구현 CMA-ES를 돌려 학습된 C 의 대각을 H^{-1} 과 비교하는 실험이 실습편 3.3절에 있습니다.

11. 얼마나 빠르고, 언제 지는가

수렴 속도

경험적으로 최적점 근처에서 로그 선형 수렴을 보입니다. 매 세대 최적점까지의 거리가 일정 비율 c 로 줄어듭니다.

\frac1g\ln\frac{\|m^{(g)}-x^*\|}{\|m^{(0)}-x^*\|}\ \longrightarrow\ -c\ <\ 0,\qquad c \approx \mathcal O\!\left(\frac{\mu_{\text{eff}}}{n}\right)

\lambda 가 n 보다 크게 크지 않다는 가정 하에서. n 과 \mu_{\text{eff}} 에 대한 이 선형 의존성은 순위 기반 직접 탐색에서 기대할 수 있는 최선입니다. 다만 엄밀한 수렴 증명은 아직 없습니다.

BBOB-2009 벤치마크에서 31개 알고리즘과 비교했을 때 CMA-ES가 종합 1위였고, 특히 “어려운 함수”와 고차원에서 강했습니다.

지는 경우 (알아 두면 시간을 아낍니다)

상황	더 나은 선택
n < 10	Nelder-Mead, 또는 크리깅 기반 대리모델(베이지안 최적화)
변수 간 상호작용 없음 (separable)	차분 진화(DE), sep-CMA-ES. 특히 다봉이거나 고차원일 때
매끈하고 조건수 낮은 볼록 이차	BFGS, NEWUOA, SLSQP가 10배 이상 빠름
예산이 10\cdot n 번 평가 이하	NEWUOA, MCS 같은 대리모델/신뢰영역 방법
n 이 수천 이상	sep-CMA-ES, VD-CMA, LM-CMA (C 를 저차원 근사)

반대로 비분리적이면서 조건수가 나쁘거나, 지형이 울퉁불퉁하거나, 10^2 \cdot n 번 이상 평가가 필요한 문제라면 CMA-ES가 대체로 우위입니다. separable 함수에서의 열세는 특히 큰 편이라, 문제가 완전히 분리 가능하다는 걸 안다면 다른 도구를 쓰는 게 낫습니다.

변형들

(1+1)-CMA-ES — 세대당 한 개만 샘플링, 더 좋으면 평균을 옮김. Gaussian adaptation과 가까움
Active CMA — 나쁜 샘플에 음수 가중치. 현재 사실상 기본값
MO-CMA-ES — 다목적 최적화 확장
IPOP / BIPOP — \lambda 를 키우며 재시작, 다봉 함수 대응
NES 계열 — 진화 경로를 쓰지 않고(c_1 = 0,\ c_\sigma = 0) 공분산 대신 Cholesky 인자를 직접 갱신

12. 실제로 돌릴 때

파이썬 표준 구현은 Hansen 본인이 관리하는 pycma 입니다. ask-tell 인터페이스라 평가 루프를 직접 통제할 수 있고, 그래서 병렬화나 실기 실험과 붙이기 쉽습니다.

# pip install cma
import cma, numpy as np

def objective(x):
    # 시뮬레이터/실기 평가. 미분 필요 없음
    return float(np.sum(100*(x[1:] - x[:-1]**2)**2 + (1 - x[:-1])**2))

x0     = np.zeros(12)      # 초기 추정치 m0
sigma0 = 0.3               # 탐색 구간 폭의 1/4 정도

es = cma.CMAEvolutionStrategy(x0, sigma0, {
    'popsize': 12,        # λ. 다봉이면 키운다
    'bounds': [-5, 5],
    'maxfevals': 20000,
    'seed': 0,
})

while not es.stop():
    X = es.ask()                          # λ개 후보 (병렬 평가 가능)
    F = [objective(x) for x in X]
    es.tell(X, F)                         # 순위만 사용된다
    es.logger.add(); es.disp()

print(es.result.xbest, es.result.fbest)

초기값을 정하는 규칙

변수를 반드시 정규화하세요. 초기 C = I 이므로, 모든 변수가 비슷한 스케일이어야 시작이 유리합니다. 게인 하나가 [0, 1] 이고 다른 하나가 [0, 5000] 이면 각각을 [0, 1] 로 매핑해서 넣습니다. CMA가 결국 스케일을 배우긴 하지만, 배우는 데 O(n^2) 세대를 쓰게 됩니다.
\sigma_0 는 “최적값이 있을 법한 구간 폭의 1/4 \sim 1/3”. 너무 작으면 국소 최적에 갇히고, 너무 크면 초반을 낭비합니다.
\lambda 는 다봉성에 대한 유일한 손잡이입니다. 기본값으로 국소 최적에 빠지면 \lambda 를 2배씩 키워 재시작합니다.
노이즈가 있으면 평가를 여러 번 평균하거나 pycma의 noise handling 옵션을 켭니다. 순위만 쓰기 때문에 노이즈에 비교적 강하지만, 순위 자체가 뒤집힐 정도면 얘기가 다릅니다.

강화학습·로보틱스 맥락에서의 위치

CMA-ES는 정책 파라미터 수가 수백 개 이하일 때 실전적입니다. 그 이상 차원에서는 C 학습 비용(O(n^2) 세대, O(n^2) 메모리) 때문에 대각/저랭크 변형이나 OpenAI ES 같은 등방 방법, 또는 그래디언트 기반 RL이 유리해집니다.

대신 이런 자리에서는 강력합니다.

제어기 게인·임피던스 파라미터 튜닝 — 차원이 10~50, 평가가 비싸고 미분 불가한 전형적인 상황
리워드 가중치 탐색 — 리워드 항 계수를 CMA-ES로 찾고, 안쪽 루프는 PPO/SAC로 학습하는 이중 루프 구성
sim-to-real 시스템 식별 — 실기 로그와 시뮬레이션 궤적의 차이를 최소화하도록 마찰·강성·지연 파라미터를 피팅. 목적함수가 시뮬레이터를 통과하므로 미분이 없는 경우가 많습니다
궤적 최적화의 초기해 탐색 — 비볼록 접촉 문제에서 지역해에 덜 민감한 출발점 찾기
정책 파라미터의 저차원 잠재공간 탐색 — DMP/ProMP 계수처럼 파라미터 수가 작은 표현 위에서의 직접 정책 탐색

PPO 같은 방법과의 대비를 한 줄로 말하면, 그래디언트 RL은 한 궤적 안의 시간 구조를 이용해 크레딧을 할당하고, CMA-ES는 그것을 포기하는 대신 미분 가능성과 마르코프 가정을 요구하지 않습니다. 평가 한 번이 비싸고 파라미터가 적을수록 CMA-ES 쪽이 유리해집니다.

13. 이해했는지 확인하는 일곱 문항

답을 먼저 떠올린 뒤 펼쳐 보세요.

f 의 값 대신 순위만 쓰면 어떤 이득이 생기나?

f 를 단조 증가 변환해도 알고리즘이 동일하게 동작합니다. 목적함수 스케일링/정규화가 불필요해지고, f 값이 아예 없고 승패 순위만 있는 문제(토너먼트, 사람의 선호 비교)에도 그대로 적용됩니다. 노이즈에도 상대적으로 강해집니다.

rank-\mu 항만 있으면 무엇이 부족한가?

외적 y y^\top 가 y 와 -y 를 구분하지 못하므로 진행 방향의 부호 정보가 사라집니다. 또 \lambda 가 작으면 한 세대에서 얻는 정보량이 부족합니다. 진화 경로 p_c 가 여러 세대의 이동을 누적해 이 두 문제를 동시에 해결합니다.

p_\sigma 에는 C^{-1/2} 를 곱하는데 p_c 에는 곱하지 않는다. 왜?

p_\sigma 는 길이를 절대 기준(\chi_n)과 비교해야 하므로 분포 모양을 지운 등방 좌표로 옮겨야 합니다. 반면 p_c 는 원래 공간에서의 방향을 그대로 C 에 주입하는 것이 목적이라 변환하면 안 됩니다.

\sigma 갱신은 왜 지수 함수인가?

\sigma 는 양수여야 하고, 변화가 곱셈적(scale-invariant)이어야 하기 때문입니다. \exp 를 쓰면 \sigma 가 0 이하로 내려갈 수 없고, “20% 증가”가 \sigma 의 절대 크기와 무관하게 같은 의미를 가집니다.

C 의 학습률이 1/n^2 스케일인 근본 이유는?

C 에는 n(n{+}1)/2 개의 자유도가 있고, 세대당 얻는 정보는 O(\mu_{\text{eff}}) 개의 스텝뿐입니다. 그 정보량 예산에 맞춰 학습률을 잡은 결과이며, 동시에 CMA-ES가 고차원에서 느려지는 이유이기도 합니다.

회전 불변성이 왜 중요한 성질인가?

좌표축에 특권을 두는 알고리즘은 문제가 회전(변수들이 서로 얽힘)하면 성능이 급락합니다. 회전 불변이면 “이 함수에서 잘 됐다”는 실험 결과를 그 함수의 모든 회전판으로 일반화할 수 있어, 벤치마크 결과의 의미가 훨씬 강해집니다.

사용자가 정해야 하는 값은 무엇이고, 어떻게 정하나?

m^{(0)}, \sigma^{(0)}, 그리고 선택적으로 \lambda 와 종료 조건. \sigma^{(0)} 은 최적값이 있을 법한 구간 폭의 1/4 \sim 1/3, 변수는 미리 비슷한 스케일로 정규화, \lambda 는 다봉일수록 크게(재시작마다 2배).

Reference

Hansen, N. (2016). The CMA Evolution Strategy: A Tutorial — 이 문서의 수식 표기 기준. 가장 완전한 단일 문서
Hansen, N. & Ostermeier, A. (2001). Completely Derandomized Self-Adaptation in Evolution Strategies. Evolutionary Computation 9(2), 159–195 — 원 논문
Ollivier, Arnold, Auger, Hansen (2017). Information-Geometric Optimization Algorithms. JMLR 18(18) — 가중치와 불변성의 통합적 유도
Akimoto et al. (2010) / Glasmachers et al. (2010) — 자연 그래디언트 해석과 NES와의 관계
github.com/CMA-ES/pycma — 참조 구현
en.wikipedia.org/wiki/CMA-ES — 본문 구성 근거
실습편: 👩‍💻CMA-ES 한 걸음씩: pycma로 배우는 진화 전략