2023-06-26 (Mon.)
適当な実行可能空間 (典型的には \(\mathbb R^n\) の部分空間) \(X\) に対して 目的関数
\[f \colon X \to Y\]がある. ここで \(Y\) が目的や指標と呼ばれる値の空間で \(Y \subset \mathbb R^p\) である.
\(i=1,2,\ldots,p\) について \(f\) の第 \(i\) 成分を \(f_i\) と呼ぶことにする. \(f=(f_1, f_2, \ldots, f_p)\) . 同様に \(y \in Y\) の第 \(i\) 成分を \(y_i\) と書く.
最適化問題ではこの値の最小化を目指す. (または最大化であるが一般性を失わず最小化だとしておく.)
\(p=1\) の場合は \(Y\) の値は全順序なので通常の最適化問題になる. しかし多目的最適化では一般に \(p \geq 1\) の場合を考える.
大きく方針は２つある.
1つ目については集約関数の設計次第. これには結局異なる指標 (つまり \(f_i\) と \(f_j\) ) について重みを設定してどちらを優先させるかといったことを決める必要がある. 最終的には通常の最適化問題になる. これについてはここではこれ以上書かない.
2つ目は異なる指標は比較できないということにして無理に順序を付けることをしない. そこではパレート最適化を行うことになる. ここではこちらについて解説する.
\(Y\) の値について順序を定める. ただし前述したように異なる指標（異なる成分）については比較できず, これは半順序になる. 実数の大小比較を \(\le, \leq\) と書くのと同様に \(Y\) の大小比較を \(\prec, \preceq\) と書いて表すことにする.
\(y^1, y^2 \in Y\) についての比較は次のように行う
特に最後の比較不能はいずれかの \(i\) で \(y^1_i \gt y^2_i\) であって, いずれかの \(j\) で \(y^1_j \lt y^2_j\) であることに. 「いくつかの指標では優れているがいくつかの指標では劣っている」ことだと言える.
実行可能空間 \(X\) を \(f\) で写した像を \(f[X]\) と書く. これは \(Y\) の部分空間になっている.
\(f[X]\) のうち, 上の半順序の意味で極小なものを集めてきた集合を パレートフロンティア という.
\[\mathcal F := \{ y \in f[X] \mid \forall y' \in f[X] \setminus \{y\}, y' \not\preceq y \}\]そしてこれに対応する \(X\) の点を パレートセット という.
\[\mathcal S := \{ x \in X \mid f(x) \in \mathcal F \}\]最適化の文脈によっては少し違う次のような意味で使われることもある.
いくつかの有限の点で \(f\) の値が観測されているとする.
\[\Omega = \{ (x_i, y_i) \mid y_i = f(x_i) \}\]この \(\Omega\) の中で極小なものをパレートフロンティアという.
\[\mathcal F := \{ y \in \Omega_y \mid \forall y' \in \Omega_y \setminus \{y\}, y' \not\preceq y \}\]ここで \(\Omega_y\) は \(\{ y_i \mid \exists x, (x,y_i) \in \Omega \}\) のこと. 同様に対応する \(x\) を集めたものをパレートセットという.
ここでは文脈をはっきりさせる場合には前者を \(\mathcal F(f[X])\) , 後者を \(\mathcal F(\Omega)\) と書くことにする.
多目的最適化でもパレート最適化といった場合のゴールは, \(\mathcal F(f[X])\) を, 或いはその中の点を多く獲得することになる.
ただし現実的には \(\mathcal F(f[X])\) の中の点そのものを得ることが可能とは限らない. そこで出来るだけパレートフロンティアに近い点を広く集めることをゴールとすることが多い. そしてその場合には超体積指標 (Hyper-volume Index) でこれを測る.
最小化問題の場合十分に大きい方に点 \(r \in Y\) を取る (最大化問題の場合は小さい方に点を取る). これを参照点と呼ぶ. \(Y\) を
\[Y' = \{ y \in Y \mid y \preceq r \}\]に制限する. ここからは \(Y\) の代わりに \(Y'\) に制限して考える. ここに入らないような点 \(x\) は考慮から除外する.
観測点集合 \(\Omega\) に関するパレートフロンティアを \(F = \mathcal F(\Omega)\) とする. \(F\) と \(r\) で囲まれる次のような領域を考える.
\[\mathcal A = \{ y \in Y \mid \exists f \in F ,~ f \preceq y \preceq r \}\]適当な測度 (普通は面積, 一般に超体積) \(\mu\) でこの \(\mathcal A\) を測る. これを超体積指標 (HVI) という.
\[\mathrm{HVI}(\Omega) = \mu(\mathcal A)\]この値は \(F = \mathcal F(f[X])\) の場合に最大になる. ということで HVI を最大化することがより良いパレートフロンティアを得ることになる.
パレート最適化のために提案されてる手法をいくつかメモ程度に紹介する.
ブラックボックス最適化を行う. \(f\) の中身が分からず, また評価するためのコストが掛かるので出来るだけ少ない試行回数でパレートフロンティアの獲得を目指す.
基本的には進化最適化を行う. その中では観測点集合の中で優劣を付けて良いものからいくつかの点を持っておくことが必要になる. その優劣の付け方として, 次のような関数を使う.
\(y \in Y\) について,
\[d(y; \theta) = \max_i \theta_i y_i + \rho \sum_i \theta_i y_i\]ここで \(\theta \in \mathbb R^p\) は各指標に対する重み. \(\rho\) はハイパーパラメータ. \(d\) は指標ごとに重みを付けた上でのチェビシェフ距離と線形和を \(1 : \rho\) で混ぜたものになってる.
ただし \(\theta\) は毎回測るたびにランダムに取り直す. 結局パレートフロンティアに向かう法線ベクトルが毎回変わるのでパレートフロンティア全体を獲得できることが期待できる.
シチュエーションはやはりブラックボックス最適化. 出来るだけ少ない観測点でパレートフロンティアの獲得を目指す.
ほんとにメモ程度だけ書く.
HVI 自体の増加量を最大化する点を目指せば最小回数でパレートフロンティアが獲得できることが期待できる. 適当な仮定をするが増加量の期待値を最大化するには実は次のことだけで実現できる.
観測点 \(\Omega\) に関するパレートフロンティア \(F\) より良いか悪いかで \(Y\) を二分割する. (ただし比較不能な点も「良い」に入れる.) カーネル密度推定をして, 良い方に入るときの確率密度 \(\ell(x \mid y)\) と悪い方に入る確率密度 \(g(x \mid y)\) を求める. コレの比 \(\ell / g\) を最大化する \(x\) が実は HVI を最もよく増加させる.
中身は遺伝的アルゴリズム. ParEGO と同様で観測点の中で優劣を付けて次の世代を決める必要がある.
大きくは非劣ソートでランク付けをする. 観測点の中でパレートフロンティアなものを Rank1, 次に Rank1 以外の中でパレートフロンティアなものを Rank2, と順に決めてく. この順で上から取ってくのだが, Rank の中でもさらに順位付けをするために混雑度スコアを使う.
混雑度スコアはある点の周辺の点の距離を見る. 距離が近いほど混雑していると見なす. そして NSGA-II では混雑してない点を良いものだとして使う. 混雑してるとは, その周辺の点を過度にサンプリングしているということだから. パレートフロンティアを獲得するために幅広い点からサンプリングする必要がある.