Home > Blog > プログラミング > CMA-ES入門: 進化戦略によるブラックボックス最適化

CMA-ES入門: 進化戦略によるブラックボックス最適化

現代のエンジニアリングにおいて、最適な解を見つけ出す「最適化」は常に重要な課題です。しかし、目的関数の内部構造が不明確である、あるいは解析的に勾配を計算できない場合、その問題はブラックボックス最適化（Black-Box Optimization: BBO）として扱われ、解決が困難になります。特に、機械学習におけるハイパーパラメータ最適化（HPO）のように、一度の評価に高い計算コストがかかる実務的な課題では、最小限の試行回数で目的関数の値を改善することが強く求められます。

このような困難なブラックボックス最適化問題に対する強力な確率的最適化手法の一つが、CMA-ES（Covariance Matrix Adaptation Evolution Strategy：共分散行列適応進化戦略）です。CMA-ESは、多変量正規分布から候補解をサンプリングし、解の評価結果のランキングに基づいて分布のパラメーターを適応的に更新していくことで、最適解へと導きます。

CMA-ESの大きな優位性は、そのロバスト性とアフィン不変性にあります。非線形かつ非凸な探索空間において、非分離性や不均一な条件を持つ複雑な問題に対しても、優れた性能を発揮することが知られています。また、探索空間の線形変換に対して性能が一貫しているアフィン不変性という特性は、互いに依存し、スケールが大きく異なる変数（例えば、機械学習のハイパーパラメータ）を同時に扱う際に実用的な利点となります。

本記事では、最先端の最適化手法であるCMA-ESの基礎となる考え方から、様々な応用例、そしてPythonライブラリであるcmaesを用いた実践的な方法までを解説いたします。

CMA-ESの基本

CMA-ESがブラックボックス最適化において強力な性能を発揮する核となるメカニズムは、探索分布を多変量正規分布（Multivariate Gaussian Distribution: MGD）として設定し、その形状を最適化対象に合わせて適応させる点にあります。

CMA-ESは世代を重ねるごとに、平均ベクトル \(\boldsymbol{m}\)、ステップサイズ \(\sigma\)、共分散行列 \(\boldsymbol{C}\) の3つのパラメータで特徴づけられる MGD \(\text{N}(\boldsymbol{m}, \sigma^2 \boldsymbol{C})\) から候補解をサンプリングします。そして、評価結果に応じてこれらのパラメータを更新し、より有望な領域から解が生成されるように学習を進めます。この更新プロセスは、情報幾何学的な視点から導かれたものであり、自然勾配降下法（Natural Gradient Descent）の概念と強く関連しています。これにより、期待される目的関数の評価値を着実に減少させるように設計されています。

CMA-ESの主要な更新メカニズム

1. ランキングベースの更新とロバスト性

CMA-ESの大きな特徴は、個々の解の「実際の評価値」ではなく、評価値のランキングのみに基づいて分布パラメータを更新する点です。この特性により、目的関数のスケールが不均一であったり、評価値にノイズが含まれていたりする場合、さらには目的関数が順序を保つような非線形な変換を受けても、最適化の振る舞いが変化しないロバスト性を実現します。

2. 共分散行列 \(\boldsymbol{C}\) の適応 (CMA)

共分散行列 \(\boldsymbol{C}\) の適応（Covariance Matrix Adaptation: CMA）は、CMA-ESの名称の由来であり、その性能を支える中心的な技術です。 \(\boldsymbol{C}\) は、探索変数間の相関関係と、探索空間の幾何学的な形状を学習します。特に、目的関数が細長い谷のような構造を持つ場合、\(\boldsymbol{C}\) を適切に「歪める」ことで、探索分布を関数の等高線に沿って効率的に適応させ、探索の方向を定めることができます 。

3. 共分散行列の具体的な更新メカニズム

\(\boldsymbol{C}\) の更新は、異なる情報を組み込んだ二つのメカニズム、Rank-\(\mu\) UpdateとRank-One Updateを組み合わせて行われます。

  • Rank-\(\mu\) Update（順位 \(\mu\) 更新）： 評価の良かった上位 \(\mu\) 個の解（親）が生成された方向の情報を集約し、共分散行列の更新に利用します。これは、情報幾何学的な最適化（Information Geometric Optimization: IGO）の枠組みから導出された、分布勾配の推定に基づく更新項であり、多数のサンプルからの情報を効率的に取り込みます。
  • Rank-One Update（順位 1 更新）： 進化経路 \(\boldsymbol{p}_c\) と呼ばれる、過去の世代における分布平均 \(\boldsymbol{m}\) の更新方向を累積した軌跡を利用します。この更新メカニズムにより、\(\boldsymbol{C}\) は進化経路 \(\boldsymbol{p}_c\) の方向に伸長するように学習し、連続する世代間で探索の方向性を整合させることができます。特に、サンプリングサイズが小さい場合に、共分散行列の信頼性の高い推定を助けます。最近の研究（MAP-CMA）では、このRank-One Updateが、事前分布を組み込んだ自然勾配の視点から理論的に再解釈されています。

また、探索の全体的なスケールを示すステップサイズ \(\sigma\) は、累積ステップ長適応（Cumulative Step-size Adaptation: CSA）によって独立して制御され、探索が停滞したり発散したりするのを防ぎます。

図1. CMA-ES の解探索（https://en.wikipedia.org/wiki/CMA-ES より引用）

CMA-ESの応用

CMA-ESは、その強力な最適化能力により、非線形、非凸な連続最適化問題において優れた性能を発揮しますが、実務で直面する多様な課題に対応するため、そのコアロジックを維持しつつ、多くの拡張機能が開発されています。特に、Pythonライブラリの cmaes には、これらの最新の研究成果に基づく機能が統合されており、実務的な課題解決に役立っています。

ここでは、実務で遭遇しやすい困難なシナリオと、それに対応するCMA-ESの主要な拡張機能を紹介します。

評価予算が限られたシナリオへの対応（WS-CMA）

ハイパーパラメータ最適化（HPO）など、目的関数の評価に高い計算コストがかかる場合、最適化に許される評価予算が厳しく制限されることが多くあります。標準的なCMA-ESは、共分散行列の適応に\(O(d^2)\)の反復回数を要するため、初期の適応フェーズが長引き、評価回数が少ないシナリオではベイズ最適化などの手法に劣ることがありました。

Warm Starting CMA-ES (WS-CMA) は、この初期適応フェーズを大幅に短縮するために提案されました。

  • 原理と効果:
    • 類似したソースタスクで得られた過去の観測データから、「有望な解が存在する領域の分布」（有望分布）を推定します。
    • この有望分布のパラメータを用いて、ターゲットタスクのCMA-ES探索を初期化（Warm Start）することで、初期の探索を最適解の近くから開始できます。
    • これにより、ベイズ最適化が優位になりがちな少ない評価回数のシナリオでも、WS-CMA-ESはベイズ最適化と同等以上の高速な収束を達成することが実験的に示されています。
図2. 様々なタスクにおける収束性の比較（https://arxiv.org/pdf/2012.06932 より引用）

困難な問題への自動適応（LRA-CMA）

マルチモーダル関数やノイズの多い関数など、困難な問題に対してCMA-ESの性能は、設定されたハイパーパラメータ、特に学習率に大きく左右されます。適切な学習率を事前に見つけるには、非常にコストの高い試行錯誤が必要です。

Learning Rate Adaptation CMA-ES (LRA-CMA) は、この課題に対応するために開発されました。

  • 原理: CMA-ESの学習率（\(\eta\)）をSignal-to-Noise Ratio (SNR) を一定に保つように自動的に調整します。
  • 効果: 探索が難しい状況（低SNR）では\(\eta\)を減らし、容易な状況（高SNR）では\(\eta\)を増やすことで、ハイパーパラメータチューニングなしに、マルチモーダルやノイズの多い問題に対して優れた性能を発揮します。
  • 実装: cmaes ライブラリでは、標準の CMA() クラスを初期化する際に lr_adapt=True を加えるだけで、この自動学習率適応を利用可能です。

混合変数最適化（Mixed-Variable Optimization）

CMA-ESの基本は連続変数最適化ですが、実務では連続変数と離散変数が混在する混合変数最適化が一般的です。

  • カテゴリ変数と整数変数への対応（CatCMA / CatCMAwM）:
    • CatCMA は、連続変数と順序性のないカテゴリ変数（例：アルゴリズムの選択）を同時に最適化するために提案されました。多変量ガウス分布とカテゴリ分布の結合確率分布を探索分布として用い、情報幾何学的な枠組みに基づいてパラメータを更新します。
    • さらに進化した CatCMA with Margin (CatCMAwM) は、連続変数、整数変数、カテゴリ変数の3種類を統合的に扱うフレームワークを提供します。
  • 離散的な点の集合上の最適化（CMA-ES-SoP）:
    • CMA-ES on sets of points (CMA-ES-SoP) は、探索空間が離散的な点の集合から解を選択するような問題に対応します。生成されたサンプルを安全領域内の最も近い点に射影（エンコーディング）することで、離散的な探索空間での最適化を可能にしています。

安全制約を伴う最適化（Safe CMA-ES）

医療や制御システムなど、安全制約が非常に重要となる分野では、安全基準を破る可能性のある解の評価を厳しく抑制しつつ、最適化を進める必要があります。

  • Safe CMA-ES は、この安全最適化のために開発されました。
    • 事前に安全であると評価された初期解と、ガウス過程回帰を用いて安全関数の予測を行い、探索空間における安全な領域を推定します。
    • CMA-ESがサンプリングした候補解が安全領域の外側にある場合、その解を安全領域内の最も近い点に射影することで、安全制約を破る評価を抑制します。
    • これにより、従来の安全最適化手法が安全基準を破る最適化の抑制に苦労していたのに対し、Safe CMA-ESは少ない、あるいはゼロの安全基準を破る最適化で最適解を見つけることに成功しています。

Pythonによる実践

ここからは、Pythonライブラリcmaesを用いて、CMA-ESを実際に動かしてみましょう。このライブラリは、論文著者らによって開発されており、「シンプルさ」と「実用性」を両立する設計思想のもと、本記事で紹介した最新の拡張機能を手軽に利用できる点が大きな魅力です。

セットアップ

まず、cmaesライブラリをインストールします。

$ pip install cmaes

# condaを利用している場合
$ conda install -c conda-forge cmaes

実装例：2次元関数の最適化

cmaesライブラリは、“ask-and-tell” という直感的なインターフェースを採用しています。これは、最適化のサイクルを以下の2つのステップに分離する考え方です。

  1. Ask: 最適化器に次の評価対象となる候補解（パラメータ）を問い合わせる。
  2. Tell: 候補解を目的関数で評価した結果を最適化器に伝える。

このインターフェースにより、ユーザーは評価プロセスを完全に制御でき、複雑なシステムや分散環境にも容易に組み込むことができます。

それでは、簡単な2次元の2次関数を最小化するコードを見ていきましょう。この関数の最小値は点 \((x_1, x_2) = (3, -2)\) で \(0\) となります。

import numpy as np
from cmaes import CMA

# 最適化対象のブラックボックス関数
# 最小値は (x1, x2) = (3, -2) で f(x1, x2) = 0
def quadratic(x1, x2):
    return (x1 - 3) ** 2 + (10 * (x2 + 2)) ** 2

if __name__ == "__main__":
    # 1. オプティマイザの初期化
    # 探索中心の初期値を原点 (0, 0) に、
    # 初期ステップサイズを 1.3 に設定
    optimizer = CMA(mean=np.zeros(2), sigma=1.3)

    print(" g    f(x1,x2)     x1      x2  ")
    print("===  ==========  ======  ======")

    # 2. 最適化の実行
    for generation in range(50):
        solutions = []
        # 世代ごとの個体数 (population_size) だけループ
        for _ in range(optimizer.population_size):
            # Ask: 次の候補解を生成
            x = optimizer.ask()
            # 評価
            value = quadratic(x[0], x[1])
            # 評価結果をリストに追加
            solutions.append((x, value))

            # 途中経過の表示
            print(
                f"{generation:3d}  {value:10.5f}"
                f"  {x[0]:6.2f}  {x[1]:6.2f}"
            )

        # Tell: 評価結果をオプティマイザに伝え、内部状態を更新
        optimizer.tell(solutions)

        # 停止条件のチェック
        if optimizer.should_stop():
            break

このコードの主要なステップは以下の通りです。

  1. オプティマイザの初期化: CMA(mean=np.zeros(2), sigma=1.3) で、2次元問題のオプティマイザを生成します。meanは探索分布の中心の初期値、sigmaは探索の広がりを制御するステップサイズの初期値です。
  2. 最適化ループ: for generation in range(50): のループで、世代を進めながら最適化を実行します。
    • optimizer.ask(): 現在の探索分布（多変量正規分布）から、新しい候補解 x をサンプリングします。
    • quadratic(x[0], x[1]): 得られた候補解 x を目的関数で評価します。
    • optimizer.tell(solutions): 1世代分のすべての候補解とその評価値のペア (x, value) をオプティマイザに渡します。オプティマイザは、この情報（特に評価値のランキング）を基に、次の世代でより有望な領域を探索できるよう、分布の平均 mean、ステップサイズ sigma、そして共分散行列 C を適応的に更新します。

このシンプルなサイクルを繰り返すことで、探索分布は徐々に最適解 (3, -2) の周辺に集まっていきます。

さらに高度な例題

cmaesライブラリには、本記事の「CMA-ESの応用」で紹介した様々な拡張を含む、豊富なサンプルコードが同梱されています。これらのサンプルは、より複雑で実用的な問題にCMA-ESを適用する際のよい出発点となります。

ファイル名機能概要
bipop_cma.pyBIPOP-CMA-ES（Restarting CMA-ES with Increasing Population Size）アルゴリズムを実装し、Ackley関数を最適化します。集団サイズを大小交互に増加させる再起動戦略を示します。
catcma.py連続変数とカテゴリ変数を持つ混合整数最適化問題にCatCMAを使用する方法を示します。例として混合コンテンツ近接関数を使用します。
catcma_with_margin.py連続、整数、カテゴリ変数を組み合わせた、または個別の問題に対してCatCMAwM（Categorical CMA-ES with Margin）を使用する方法を示します。
cma_sop.pyCMASoP（CMA-ES for Sets of Points）を使用して、一部の変数が離散的な点の集合から選択される最適化問題を解く例です。純粋な離散部分空間と混合連続/離散部分空間の例が含まれます。
cma_with_margin_binary.pyCMAwM（CMA with Margin）を使用して、連続変数とバイナリ変数の混合整数問題を解く例です。
cma_with_margin_integer.pyCMAwMを使用して、連続変数と整数変数の混合整数問題を解く例です。
ellipsoid_function.py標準のCMAオプティマイザを使用して、楕円体ベンチマーク関数を解く基本的な例です。
ipop_cma.pyIPOP-CMA-ES（Restarting CMA-ES with Increasing Population Size）アルゴリズムを実装しています。bipop_cma.pyに似ていますが、Ackley関数を最適化するためのより単純な再起動戦略を持っています。
lra_cma.py多峰性の高いRastrigin関数に対して、学習率適応（lr_adapt=True）を用いたCMAの使用法を示します。
mapcma.pyMAPCMA（Matrix Adaptation Painting CMA-ES）を使用してRosenbrock関数を最適化する方法を示します。
optuna_sampler.pyOptunaハイパーパラメータ最適化フレームワーク内でcmaesをサンプラーとして使用する方法を示します。
quadratic_2d_function.pyCMAを使用して2D二次関数を最適化する簡単な例です。
safecma.py安全制約付きブラックボックス最適化のためのアルゴリズムSafeCMAの例です。単一および複数の安全制約を持つケースを示します。
sep_cma.pySepCMA（Separable CMA-ES）の例です。これは分離可能な目的関数に効率的なCMA-ESの変種で、楕円体関数でテストされています。
ws_cma.pyウォームスタートCMA-ES（WS-CMA-ES）を示します。「ソース」タスクの解を使用して、関連する「ターゲット」タスクの有望な初期分布を作成します。

おわりに

今回は、進化戦略の最先端であるCMA-ESが、ブラックボックス最適化の分野で有効なツールとなっていることを紹介しました。CMA-ESは、非線形や非分離性を持つ困難な問題に対する実証的な成功により、その強力な地位を確立しています。

Pythonライブラリの cmaes は、「シンプルさ」と「実用性」を両立するという設計思想のもと、実務で直面する高度な課題を解決する最新機能を容易に提供しています。

具体的には、以下の拡張機能が利用可能です。

  • LRA-CMA: ハイパーパラメータチューニングなしに、マルチモーダルやノイズの多い問題に対応します。
  • WS-CMA: 転移学習を通じて、評価予算が限られたハイパーパラメータ最適化（HPO）などのタスクを加速します。
  • CatCMAwM: 連続変数、整数変数、カテゴリ変数といった混合変数を統合的に最適化できるフレームワークを提供します。

CMA-ESの基礎的なロジックを理解し、これらの強力な拡張機能 を活用することで、様々な開発プロジェクトにおける最適化の効率と、得られる解の質を大きく向上させることができます。

More Information

関連記事

OpenJij x PyQUBO ではじめるシミュレーテッド・アニーリング入門

組み合わせ最適化問題は、工学、金融、情報科学といった多様な分野において、実用上極めて重要な課題です。しかし、問題が複雑化し、探索すべき解の候補が爆発的に増加するにつれて、従来型の数学的な手法で厳密な最適解を求めることは困 […]

DEAP入門：Pythonによる進化的計算の事始め

近年、深層学習（Deep Learning, DL）や大規模言語モデル（Large Language Models, LLM）といったAIシステムが目覚ましい進化を遂げています。しかし、それに伴い、これらの複雑なモデルの […]

Pythonによる粒子群最適化

数理最適化を応用した最適化問題の解決には、微分不可能な関数にも対応可能なメタヒューリスティック手法が広く利用されています。その中でも、生物の群れ行動を模倣した群知能は、複雑な問題に対して高い適応性を示します。今回は、代表 […]