こんにちは！ぼりたそです！
今回は多目的最適化について分かりやすく解説します。
当ブログでベイズ最適化についていくつか解説した記事をまとめましたが、基本は一つの目的変数を最適化する単目的最適化に関するものでした。
対して、今回は複数の目的変数（評価指標）を一度に最適化する多目的最適化という手法について分かりやすくご紹介したいと思います。
この記事は以下のポイントでまとめています。
- 多目的最適化とは？
- パレート解について
- 最適化手法
それでは順に解説していきます。
多目的最適化とは？
まずは多目的最適化についてご説明します。
多目的最適化とは複数の目的変数を最適化する手法であり、反対に一つの目的変数を最適化する手法は単目的最適化と呼ばれます。
例えば、ある会社で新製品を立ち上げようとした時に性能1を上げたいけれど、逆にその分、性能2下がってしまうというトレードオフの問題があったとします。
この時、性能1と性能2がちょうどいい具合になるように最適化するのが多目的最適化になります。
また、このちょうどいい具合になる点をパレート解と呼びます。
パレート解について
それではパレート解について詳しくご説明します。
パレート解とは多目的最適化問題において「他の解に優越されない解」のことを指します。
簡単に言えば、完全上位互換を持たない解ということになります。
先ほどの性能Aと性能Bがトレードオフになってしまうという多目的最適化問題を例にパレート解をご説明します。
例えば製法Aで作成した製品の性能が点A、製法Bで作成した製品の性能が点Bの2点があった場合、点Bは点Aの完全上位互換であり、パレート解ということになります。
対して点Aは点Bの下位互換となり、このような解を劣解と呼びます。
また、製法Cにより作成した性能が点Cであった場合、点A, Bに対して性能1では劣りますが、性能2では優れています。よって点Cは完全な上位互換を持たないため、点Aと同じくパレート解になります。
さらに検討を進め、下のようなプロットが描けたとします。この時、パレート解は赤丸で示したプロットとなり、このパレート解の集合をパレートフロントと呼びます。
最適化手法
では、実際に多目的最適化の手法についてどのようなものが存在するかご説明します。
多目的最適化手法としては大きく二つ挙げられます。
- パレートフロントから一つのパレート解を見つける
- パレートフロントを推定する
以下、順に説明していきます。
パレートフロントから一つのパレート解を見つける
まずはパレートフロントから一つのパレート解を見つける手法について説明していきます。
一つのパレート解を見つけるために一般的にはスカラー法という手法を用います。
スカラー法とは複数の目的変数を重み付けした上で足し合わせ、新しくできたスカラー値の目的変数を単目的最適化する手法です。
式で表すと下のようになり、 $ f_i(\mathbf{x}) $ がそれぞれの目的変数で $ w_i $ がその重みになります。
$$ \text{minimize or maximize} \quad F(\mathbf{x}) = \sum_{i=1}^{m} w_i \cdot f_i(\mathbf{x}) $$
この手法のメリットとしてはそれぞれの目的変数の重みを自由に設定することで、自分の目指したいバランスの取れた最適化を実行することができます。
一方でパレート解全てを探索することは難しく、別の手法を使う必要があります。
パレートフロントを推定する
次に全てのパレート解を探索する、つまりパレートフロントを推定する手法についてご説明します。
パレートフロントの推定について説明するにあたりパレート超体積という概念について理解する必要があります。
パレート超体積とはざっくり言ってしまうと、パレート解に囲まれた領域の体積を指します。
最大化したい目的変数が二つの最適化を例に挙げると下のように赤丸で示したパレート解に囲まれた青の領域がパレート超体積になります。
パレートフロントを推定する場合は現状のパレートフロントを改善するような解を見つけるように探索する必要があります。
ではどのようにパレートフロントを改善するかというと、パレート超体積の改善値をスコアリングするような獲得関数を使用することで改善を図っています。
獲得関数とは最適化問題に対して事後分布からスコアリングして次の候補点を決める指標になります。
獲得関数については以前記事でまとめたので興味があれば以下の記事をご参考下さい。
多目的最適化でよく使用されるのがEHVI（Expected Hypervolume Improvement）です。
EHVIはパレート超体積の増分を期待値として最大化する獲得関数です。要するにパレートフロントをどれだけ改善できるかを評価しているということです。
また、HVPI（Hypervolume-based Probability of Improvement）という獲得関数もあり、HVPIはパレート超体積の増分の確率を評価します。EHVIは改善期待値を計算しているので少し指標が異なっています。
これらの獲得関数を使用し、次の候補を決めて探索を繰り返すことでパレートフロントを全て見つけることできるという理論になっています。
実際に実装する場合はPtyhonのライブラリであるGPyOptやOptunaなどを使用して多目的最適化を実行します。
多目的最適化の実行については今後まとめて記事にする予定なので、お待ちいただければと思います。
終わりに
以上が多目的最適化についてのざっくりとした説明になります。実際に最適化問題を解く際はほとんどの場合が多目的最適化になるかと思います。実際に多目的最適化を実行することはなくとも、どのようなアルゴリズムで動いているのかしっかりと理解したいですね。
