最適化アルゴリズム設定の選び方ガイドライン

このページでは、問題に適した最適化アルゴリズムを選ぶための考え方を、フローチャートの形で紹介します。

適したサンプラーは問題の性質によって変わるため、ここで提供する情報はあくまで参考資料です。最初の選択を適切に行うための指標として活用してください。最適化を進めるなかで問題の性質が見えてくることも多いので、途中で手法を切り替えたほうが早く判断がつく場合もあります。

フローチャート

以下では、まず「とにかく最適化したい」場合を扱い、次に制約条件の有無で分けて手法を絞り込みます。最後に、最適化ではなく設計空間そのものを把握したい場合を扱います。

とにかく最適化したい

とにかく最適化を試したい場合は、AUTO Sampler を選択してください。 AUTO Sampler は問題の特性に応じて適切なサンプラーを自動選択するため、どの手法を選ぶか迷っている場合の出発点として適しています。初めて Tunny を使う場合も、まずはこの AUTO Sampler から試すことをお勧めします。

graph TD
    A[とにかく最適化したい] -->|はい| B[AUTO Sampler]

制約なしの最適化

制約条件がない場合は、以下のフローチャートを参考にサンプラーを選択できます。分岐の基準になっているのは、目的関数の数と試行回数の 2 つです。

graph TD
    A[目的関数の数] -->|1| B[試行回数]
    A -->|≤3| C[試行回数]
    A -->|3≤| D[NSGA-III or MOEA/D]
    B -->|≤300| E[HEBO]
    B -->|≤1000| F[GP:Optuna]
    B -->|≤10000| G[CMA-ES or INGO]
    C -->|≤300| H[GP:Optuna]
    C -->|≤1000| I[TPE]
    C -->|≤10000| J[NSGA-II]

試行回数で分岐しているのは、手法によって 1 試行あたりの計算コストが大きく異なるためです。たとえば GP は、それまでの観測すべてを使ってサロゲートモデルを作り直すため、試行回数が増えるほど 1 試行にかかる時間が長くなっていきます。そのため、試行回数を多く取れる場合は、TPE や NSGA-II、CMA-ES といった試行を重ねることを前提とした手法が候補になります。

目的関数の数が多い場合に NSGA-III や MOEA/D を挙げているのは、NSGA-III が参照点を使って高次元の目的空間でも多様性を維持し、MOEA/D が多目的問題を単目的のサブ問題に分解して扱うためです。

制約ありの最適化

制約条件がある場合は対応している手法が限られるため、使用できるサンプラーの数は少なくなります。

graph TD
    A[目的関数の数] -->|1| B[試行回数]
    A -->|≤3| C[試行回数]
    A -->|3≤| D[NSGA-III]
    B -->|≤500| E[GP:Optuna]
    B -->|≤1000| F[C-TPE]
    C -->|≤300| G[GP:Optuna]
    C -->|≤1000| H[TPE]
    C -->|≤10000| I[NSGA-II]

制約なしの場合と見比べると、HEBO や CMA-ES が候補から外れています。また単目的の分岐では、TPE に代わって制約違反を目的関数とともに明示的にモデル化する C-TPE が挙がっています。どの手法が制約に対応しているかは、対応サンプラーのページの表にまとめてあります。上のフローチャートから外れた条件で選ぶ場合は、そちらもあわせて確認してください。

設計空間の探索

Tunny では、最適化を行わずに設計空間を把握するためのサンプリングも実行できます。

設計空間の探索とは、変数のさまざまな組み合わせを試すことで、現在設定している変数の組み合わせによって目的関数がどの程度変化するか、またどの変数が目的関数に影響を与えるかを確認することを意味します。

最適化で手元に残るのは基本的に最良の解だけであり、どの変数がどの程度効いているかまでは見えてきません。設計空間を先に把握しておくことで、変数の範囲の設定が適切かどうかを判断でき、そのあとの最適化も進めやすくなります。 Tunny のダッシュボードと組み合わせることで、設計空間を効率的に把握できます。

graph TD
    A[低差異性が必要か？] -->|はい| B[QMC]
    A -->|いいえ| C[全結果が必要か？]
    C -->|はい| D[BruteForce]
    C -->|いいえ| E[Random]

ここでいう低差異性とは、サンプリングした点が一箇所に密集せず、適度な間隔で散らばる性質のことです。少ない試行回数で空間全体を偏りなく見たい場合は、この性質を持つ QMC が適しています。一方 BruteForce は、離散変数のすべての組み合わせを評価することで結果を漏れなく残せます。ですが計算コストは変数の数に対して指数関数的に増えるため、現実的なのは探索空間が小さい場合にかぎられます。それぞれの違いについては、技術情報の Random & QMC のページで詳しく紹介しています。