最適化手法の選択について — 連続最適化を一望する

はじめに — なぜ最適化手法の選び方に悩むのか

最適化と一口に言っても、そこで使われているアルゴリズムは驚くほど多様です。しかし手法ごとに得意な問題の性質は大きく異なり、選択を誤ると膨大な計算時間をかけたわりに大した解が得られない、ということが起こります。

今回は連続変数を対象とした最適化（連続最適化）を例に、「数理最適化」がなぜ限界を迎え、「メタヒューリスティクス」がそれをどう乗り越えてきたのかという流れで、代表的な手法を一望してみます。

数理最適化 — 古典的な数学的アプローチ、ニュートン法を例に

最も古典的なアプローチは、目的関数を数式として明示的に扱い、その勾配ベクトル（一階微分）やヘッセ行列（二階微分）を使って解を更新していく数理最適化です。ニュートン法はその代表例で、現在の点における目的関数を二次関数で近似し、その最小点へ一気に飛ぶという更新を繰り返します。局所的に見れば目的関数はだいたい二次関数で近似できるため、最適解の近くでは二次収束という非常に速い収束を示します。実務ではヘッセ行列を厳密に計算せず勾配ベクトルの履歴から近似する準ニュートン法（BFGS法など）が使われることが多く、scipy.optimize.minimizeのデフォルト系アルゴリズムもこの系譜にあります。

数理最適化の弱点 — 局所最適解とブラックボックス問題

この二次近似に基づく更新は、裏を返せば「今いる場所の周辺」の情報しか見ていないということでもあります。目的関数が多峰性を持つ場合、初期点や途中の経路次第で、大域的な最適解ではなくたまたま近くにあった局所最適解に収束して終わってしまうことが避けられません。これは勾配ベクトルを解析的に計算しているか数値的に近似しているかに関わらず生じる、局所探索であることに起因するより本質的な限界です。

もう一つの弱点は、勾配ベクトルやヘッセ行列を使う以上、目的関数が微分できることを前提としている点です。 CFDのような数値シミュレーションを目的関数に含む問題では、入力（設計変数）と出力（性能値）の関係を数式で書き下すことはできません。有限差分で勾配ベクトルを近似すること自体は可能で、BFGS法のような準ニュートン法もこの形で運用できなくはないのですが、設計変数が増えるほど1ステップあたりに必要な評価回数が線形に増えていくうえ、シミュレーション特有のノイズによって勾配ベクトルの推定自体が不安定になりがちです。

つまり数理最適化には、局所最適解に捕まりやすいという構造的な限界と、ブラックボックスな目的関数への対応コストという実務的な限界の両方があります。次世代の手法として登場したメタヒューリスティクスは、主に前者への解決策として「大域的な探索」という発想を持ち込みつつ、勾配ベクトルを一切使わないことで後者も同時に解消しました。

大域探索でブラックボックスも解く — メタヒューリスティクスの登場

微分情報を一切使わず、目的関数を純粋な入出力関係（ブラックボックス）として扱ったまま最適化する手法として発展してきたのが、メタヒューリスティクスです。焼きなまし法（Simulated Annealing）は金属の焼きなましになぞらえた手法で、温度パラメータを下げながら、悪化する解も一定確率で受け入れることで局所最適解からの脱出を図ります。遺伝的アルゴリズム（GA）は複数の解を「個体群」として同時に保持し、交叉・突然変異を繰り返しながら集団全体を良い解へ進化させていきます。

どちらも目的関数の中身を一切問わないため、CFDのように微分不可能・ノイズを含む問題にもそのまま適用できます。反面、収束にかなりの評価回数を要するため、1回の評価が高コストな問題ではボトルネックになりがちです。この「評価回数をどう減らすか」という課題に取り組んできたのが、以下の2つの最先端手法です。

進化計算の最先端 — CMA-ES（大規模・高次元探索向き）

CMA-ES（Covariance Matrix Adaptation Evolution Strategy）は、GAと同じ進化計算の系譜にありながら、現時点で最も有力とされている手法です。各世代の優良個体の分布から共分散行列を更新し、探索分布そのものを問題の形状に適応させていきます。勾配ベクトルを明示的に使わないにもかかわらず、内部的には目的関数の局所的な曲率を推定しているようなふるまいをするため、GAより少ない評価回数で局所的な絞り込みまで到達できます。個体群ベースの手法である以上、ある程度の評価回数は必要になりますが、その分大規模・高次元の探索に強く、設計変数が数十〜数百に及ぶような問題でも実用的に機能します。

もう一つの系譜 — 応答曲面法とは

CMA-ESが進化計算（個体群を世代ごとに更新していく系譜）の延長線上にあるのに対し、もう一つ別の系譜として実験計画法（DOE）から発展してきたのが応答曲面法（Response Surface Methodology, RSM）です。化学プロセスの収率最適化のように、内部機構が数式で書き下せないブラックボックスな現象を対象にしている点はメタヒューリスティクスと同じですが、アプローチはまったく異なります。まずDOEに基づいて少数の実験点（評価点）を効率よく配置し、そこで得られた入出力の組から目的関数の形状を2次多項式などの単純なモデルで近似します。この近似曲面（応答曲面）さえ手に入れば、以降の最適化は実際の実験やシミュレーションを繰り返す代わりに、この安価な近似モデル上で行えます。つまり「評価コストの高い現象そのもの」を直接探索するのではなく、「その挙動を模した安価な代理モデル（サロゲートモデル）」を経由して最適化するという発想です。

ただし古典的なRSMが近似に使う2次多項式は表現力に限界があり、強い非線形性や多峰性を持つ現象にはそのままでは向きません。また各実験点における予測の不確実性を扱う仕組みも持たないため、次にどこを追加で評価すべきかは経験や直感に頼る部分が大きくなります。

応答曲面法の現代版 — ベイズ最適化（小規模・低次元探索向き）

ベイズ最適化は、この応答曲面法の考え方をガウス過程で現代化したものだと捉えられます。曲面のモデル化を多項式からガウス過程に置き換えることで表現力と不確実性の定量化を両立し、獲得関数（探索と活用のバランスを取る指標）によって次に評価すべき点を機械的に決められるようにしました。 1回のCFD実行に何時間もかかるような、評価回数を極限まで絞りたい問題で真価を発揮する手法で、数十回程度の評価で実用的な解にたどり着けることも珍しくありません。ただしサロゲートモデルの学習コストが次元数に対して急激に増大するため、CMA-ESとは逆に、設計変数が少ない小規模・低次元の問題に向いた手法だと言えます。

選択の軸を整理する

ここまでの手法を、選択の際に効いてくる軸で整理すると次のようになります。

手法	目的関数へのアクセス	必要な評価回数	得意な次元数	探索の性質
ニュートン法・準ニュートン法	数式・微分が必要	少ない	高次元も可	局所
焼きなまし法	ブラックボックスでよい	多い	低〜中次元	大域
遺伝的アルゴリズム	ブラックボックスでよい	非常に多い	低〜中次元	大域
CMA-ES	ブラックボックスでよい	中程度	大規模・高次元	大域寄り
応答曲面法（古典）	ブラックボックスでよい	少ない	低次元	大域（曲面近似）
ベイズ最適化	ブラックボックスでよい	非常に少ない	小規模・低次元	大域

実務でどう使い分けているか

実際の設計最適化では、まず目的関数が数式としてアクセスできるか、それともシミュレーションのようなブラックボックスかが最初の分岐点になります。数式でアクセスでき微分も取れるなら、収束の速いニュートン系の手法を選ばない理由はありません。ブラックボックスであれば、次に設計変数の規模と評価回数の予算を見ます。設計変数が数十を超えるような大規模問題で、ある程度の評価回数を確保できるならCMA-ES、逆に1回の評価が非常に高コストで評価回数を数十回程度に絞りたい小規模問題ならベイズ最適化、という具合です。

こうした単純な当てはめだけでなく、序盤はGAやCMA-ESで大域的に探索し、有望な領域が絞り込めてきたら準ニュートン法で局所的に詰める、という2段階の戦略を組むこともあります。手法ごとの得意・不得意を理解した上で、問題の性質やフェーズに応じて組み替えられることが、最適化を実務で使いこなす上での鍵だと考えています。

おわりに

連続最適化のアルゴリズムに「唯一の正解」はなく、目的関数がブラックボックスかどうか、多峰性によって局所最適解に捕まるリスクがあるかどうか、そして評価コストと次元数のバランスに照らして初めて、どの手法が向いているかが見えてきます。流行りの手法を単体で覚えるよりも、こうした軸に沿って手法群を地図として持っておくことが、初見の問題に対しても適切な手法選択を素早く行える力につながると感じています。