再始動戦略

CMA-ES は 1 回走らせると局所解に収束して止まる。 多峰性の強い問題では、止まったら条件を変えてやり直すのが標準的な運用になる。

IPOP-CMA-ES#

最も広く使われる方式。Auger と Hansen が 2005 年に提案した。

停止するたびに集団サイズ $\lambda$ を 2 倍にして再始動する。

理屈はこう。$\lambda$ が大きいほど 1 世代で広く見渡すため、 局所解を飛び越えて大域的な構造を捉えやすくなる。一方で $\lambda$ が大きいと 1 世代あたりの評価回数が増える。だから小さい $\lambda$ で速く試し、 駄目なら倍にして粘り強く探す、という順序で評価回数を配分する。

IPOP は Increasing POPulation の略。

BIPOP-CMA-ES#

$\lambda$ を増やす系列と、小さい $\lambda$ のまま初期 $\sigma$ を変えて 何度も試す系列を交互に回す。予算を使い切っていない方の系列を選ぶ。 BBOB ベンチマークで強い結果を出し、以後の比較基準になっている。

停止条件#

再始動には「いつ止めるか」の判定が要る。実装で使われる代表的なもの。

条件	意味
TolX	$\sigma$ と $C$ から決まる探索幅が閾値未満
TolFun	直近の世代で目的関数値がほとんど変わらない
ConditionCov	$C$ の条件数が大きすぎ、数値的に危うい
NoEffectAxis	ある軸方向に動かしても値が変わらない（数値的に潰れている）
EqualFunValues	上位個体の値がすべて同じ

これらは収束したかの判定でもあり、 評価回数を無駄にしないための実務的な工夫でもある。

参考文献#

• Nikolaus Hansen. The CMA Evolution Strategy: A Tutorial. 2016.（実装まで踏み込んだ標準的な解説） https://arxiv.org/abs/1604.00772
• Nikolaus Hansen, Andreas Ostermeier. Completely Derandomized Self-Adaptation in Evolution Strategies. Evolutionary Computation 9(2), 2001.（CMA-ES の原論文） https://doi.org/10.1162/106365601750190398
• CMA-ES 公式サイトと参照実装 pycma https://github.com/CMA-ES/pycma
• Anne Auger, Nikolaus Hansen. A Restart CMA Evolution Strategy With Increasing Population Size. IEEE CEC, 2005.（IPOP-CMA-ES の原論文） https://doi.org/10.1109/CEC.2005.1554902