Skip to content
検索結果に戻る

進化戦略(CMA-ES)— 共分散行列適応

提唱者
Nikolaus Hansen & Andreas Ostermeier
年
2001
種類
Derivative-free continuous black-box optimizer

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

CMA-ES(Covariance Matrix Adaptation Evolution Strategy)は、2001年にHansenとOstermeierによって導入された、連続的なブラックボックス関数向けの現代的な導関数フリー最適化手法である。これは、多変量正規分布からサンプリングされた候補解の集団を維持し、分布の平均、ステップサイズ、および完全な共分散行列を反復的に更新することで、パラメータ空間のより良い領域へと探索を誘導する。これは連続的なブラックボックス最適化の事実上の標準となり、ニューラルアーキテクチャ探索や強化学習における方策最適化に広く用いられている。

手法の背後にある直感

丘陵地帯の最も低い地点を探しているが、地形は見えず、個々の地点を探索点してその高さを知ることしかできないと想像してほしい。CMA-ESは誘導された群れのように機能する。現在の最良推定値の周りに探索点の雲を落とし、各探索点の良さを測定し、次のラウンドのために雲を再形成する。雲は単純な球体ではなく、改善につながった方向を記憶することで、下降している谷の細長い傾いた形状を学習する。 連続する世代を経て、雲は損失曲面の曲率に沿って狭まり、傾くことで、より単純な手法では行き詰まってしまうような、長く狭い谷をアルゴリズムがナビゲートできるようになる。

歴史学

進化戦略は、生物学的進化に着想を得た集団ベースの最適化手法のファミリとして、1960年代および1970年代に導入された。共分散行列適応メカニズムは、HansenとOstermeierによって開発され、2001年のEvolutionary Computation論文で完全に記述された。この論文では、完全にデランダマイズされた自己適応(成功したステップの履歴から探索地形の完全な二次幾何学的形状を学習すること)が、条件が悪く非分離的な問題において、以前の進化戦略を劇的に上回ることが示された。Hansenの2016年のチュートリアルは、アルゴリズムとその理論的特性を統合し、CMA-ESを連続ブラックボックス最適化ベンチマーキングの標準参照手法とした。

使うべき場面

CMA-ESは、目的関数が連続的で、非凸、多峰性、またはノイズが多い可能性があり、勾配情報が入手不可能または計算コストが高すぎる場合に適切である。理想的な次元範囲は約10から1000パラメータである。10未満の次元ではより単純な手法で十分な場合が多く、1000を超えると共分散行列の二次的なメモリコストが許容できなくなる可能性がある。統計的な意味での最小サンプルサイズ要件はなく、アルゴリズム自体が評価点を生成する。CMA-ESは、ハイパーパラメータチューニング、ニューラルアーキテクチャ探索、強化学習方策最適化、およびシミュレータがブラックボックス出力のみを提供する工学設計問題に自然に適合する。

限界と注意点

  • 次元数に対する二次的なメモリおよび世代ごとの計算コストは、次元削減バリアントなしでは約1000パラメータを超える適用性を制限する。
  • 再起動がない場合、局所最適解に収束する。高度に多峰性の地形では、複数の再起動(IPOP-CMA-ESまたはBIPOP-CMA-ES)が必要である。
  • 離散的または組み合わせ的な探索空間には適していない — この手法は本質的に連続的な実数値ベクトル上で定義されている。

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • 勾配情報を必要としない — ノイズが多い、またはシミュレーションベースのものを含む、あらゆる呼び出し可能な目的関数で機能する。
  • 共分散適応を通じて探索地形の局所的な曲率を学習し、固定探索分布を持つ勾配フリー手法を打ち負かすような、細長く条件の悪い探索空間をナビゲートすることを可能にする。
  • 目的関数の順序保存変換および探索空間の回転に対して不変であり、幅広い問題幾何学的形状に対してロバストである。
  • 中程度から高次元の連続問題(10〜1000パラメータ)に適切であり、単一のチューニング可能なハイパーパラメータ(初期ステップサイズ)を持つ。

応用

  • ニューラルネットワークアーキテクチャや強化学習エージェントを含む、機械学習モデルのハイパーパラメータチューニング。
  • ニューラルアーキテクチャ探索 — 連続緩和を介した離散エンコードされたアーキテクチャパラメータの最適化。
  • 方策が連続ベクトルでパラメータ化されている場合の、強化学習方策最適化。
  • シミュレータ出力のみが入手可能な場合の、空気力学的形状最適化や構造パラメータフィッティングなどの工学設計最適化。
  • 尤度が微分不可能または計算コストが高い場合の、シミュレーションモデルを実験データに適合させる科学モデルキャリブレーション。

使い方

使い方

1

アルゴリズムは、初期解ベクトルと初期ステップサイズ(sigma)でシードされる。共分散行列は、完全な球形の探索雲である単位行列から始まる。集団サイズは通常、4 + floor(3 * ln(dimension)) のように設定される。

2

各世代で、現在の多変量正規分布から候補解の集団がサンプリングされる。この分布は平均ベクトル、ステップサイズ、共分散行列によって定義される。分布が多変量正規分布であるため、サンプルは現在の最良推定値と探索空間の学習された形状の両方を反映する。

3

各候補解は目的関数に渡され、適応度スコアを受け取る。勾配情報は必要なく、サンプリングされた各点でのスカラー目的値のみが必要である。これにより、CMA-ESはノイズが多く、微分不可能で、シミュレーションベースの目的にも適している。

4

平均は、よりランクの高い解に向かって移動する。共分散行列とステップサイズは、ランク1とランクμの2つの相補的な適応パスを用いて更新され、次の世代で良い改善をもたらした方向がより可能性が高くなるようにする。これが、CMA-ESが地形の局所的な幾何学的形状を学習する中核メカニズムである。

5

アルゴリズムは、最大関数評価回数、平均またはステップサイズの変化に対する許容誤差、または共分散行列の退化が検出されたという停止基準が満たされるまで、サンプリング–評価–更新サイクルを繰り返す。すべての世代で見つかった最良の解が返される。

よくある落とし穴

  • 初期ステップサイズを小さすぎると探索が狭い近傍に閉じ込められ探索が妨げられ、大きすぎると初期世代が無駄に最適値から離れた場所で評価されてしまう。一般的な経験則として、最適値が開始点の約3シグマ内に入るようにsigmaを設定する。
  • 非常に低次元の問題(5パラメータ未満)にCMA-ESを適用することは通常無駄である — より単純なグリッドサーチやNelder-Meadで十分であり、CMA-ESの集団オーバーヘッドは利点をもたらさない。
  • 多峰性の地形に対して単一のCMA-ESインスタンスを実行すると、大域的最適解を見逃すリスクがある。地形が高度に多峰性であることがわかっている場合は、マルチスタートまたは集団ベースの再起動戦略(IPOP/BIPOP)を使用する。
  • 再起動検証なしで返された最良解を真の大域的最適解と見なすことは一般的な間違いである — 目的関数が高度に非凸である場合は、常に複数の独立した実行で確認すること。

よくある質問

CMA-ESは単純な遺伝的アルゴリズムとどのように異なるか?

古典的な遺伝的アルゴリズムは、集団を維持し、固定された演算子で交叉と突然変異を適用する。CMA-ESは代わりに、集団を多変量正規分布からのサンプリングとしてモデル化し、どの解が成功したかに基づいてその分布(平均、ステップサイズ、完全な共分散行列)を継続的に適応させる。これにより、CMA-ESは損失地形の形状を学習し、固定演算子を持つ遺伝的アルゴリズムよりもはるかに効率的に相関のある、条件の悪い空間をナビゲートできる。

CMA-ESは大域的最適解を見つけることを保証するか?

いいえ。CMA-ESは局所探索手法であり、単一の実行が局所最適解に収束する可能性がある。多峰性の地形では、探索空間のカバレッジを改善するために、複数の独立した再起動(おそらく集団サイズを増やす(IPOP-CMA-ES))が推奨される。

設定すべき最も重要なハイパーパラメータは何か?

初期ステップサイズsigmaは、最も影響力のある単一のハイパーパラメータである。良い経験則は、期待される最適値が開始点の約3シグマ内に入るように設定することである。集団サイズと最大評価回数は二次的な制御であり、デフォルトの集団サイズ式(4 + floor(3 * ln(dimension)))は実際にはうまく機能する。

CMA-ESはノイズの多い目的関数を扱えるか?

はい。CMA-ESは集団のランク順情報のみを使用し、絶対関数値は使用しないため、ノイズに対して比較的ロバストである。評価が非常にノイズが多い場合は、集団サイズを増やすか、候補ごとに複数の評価を平均することで、ロバスト性をさらに向上させることができる。

関連する手法

参考文献

  1. Hansen, N. & Ostermeier, A. (2001). Completely Derandomized Self-Adaptation in Evolutionary Strategies. Evolutionary Computation, 9(2), 159-195.

    DOI 文献を開く
    コピーしました。
  2. Hansen, N. (2016). The CMA Evolution Strategy: A Tutorial. arXiv:1604.00772.

    出版物の文献を開く
    コピーしました。