6. 多目的最適化問題 #

6.1. 導入 #

多目的最適化問題とは実行可能領域 \(X\) に対して，目的関数が二つ以上ある次の問題 ¹ ¹多目的最適化問題からの対比として，目的関数が一つの通常の場合を単目的最適化問題ということがある． ² ²\(X\) は各種の制約条件で決まる実行可能領域のため，\(x\in X\) と書くことで，問題に表れる制約条件を集約して記述している．ここでは多目的最適化問題を考える場合に，新たに考える制約条件との区別が容易となるように，この記述としている．である．

(1)#\[\begin{split}& \mathrm{Minimize\colon}~ f(x) = (f_1(x),\ldots,f_p(x)) \\ & \mathrm{Subject~to\colon}~ x\in X = \{x\in\mathbb{R}^n \mid g(x) = (g_1(x),\ldots,g_m(x)) \leq 0\}\end{split}\]

最適化したい事柄が複数あり，それらが互いに関係する場合，どの事柄を優先すべきなのか一つに定まらないため，通常は数理最適化の共通項目として目的関数は一つのみ考える．

実務では必ずしも唯一つの事柄を最適化すればよいという状況 ³ ³純粋に最適化したい指標が複数ある場合の他にも，どの制約条件を優先したいかということも，しばしば多目的最適化に通じるものになる．つまり制約条件に序列があって，それらの充足度合いをスラック変数で表すときに，それらに応じたスラック変数の最小化が序列を考慮したい各制約条件の数だけあるからである．にならないことがある．このような場合を扱うのが多目的最適化問題である．

6.2. 解の種類 #

多目的最適化では，単目的最適化の場合と違って「最適解」が一種類ではないため，まず解の概念を整理する．

6.2.1. 完全最適解 #

多目的最適化ではどの目的関数についても最適であるという 完全最適解 が得られることが理想的ではある．

完全最適解

多目的最適化問題 (1) に対して，次を満たす \(x^*\in X\) を完全最適解という．

(2)#\[f_i(x^*)\leq f_i(x), \, \forall i \in \{1,\ldots,p\}, \, \forall x\in X\]

しかし，完全最適解が存在する問題は実務の中でも単純か，もしくは稀と考えるべきである．多くの場合，「あちらを立てればこちらが立たず」というトレードオフ状態にあるパレート最適な解が複数生じえる．このため解の特色という点で，単目的最適化問題とは違った様相を呈し，要件定義ではトレードオフの扱いをより丁寧に定める必要がある．

6.2.2. パレート最適解 #

目的関数が複数ある場合，それらをすべて同時に最小化するような「最良の解」は存在しないことが多い．例えば「コストを下げたい」と同時に「品質を高めたい」と考えると，「コストを下げれば品質が下がり，品質を上げればコストが上がる」といったトレードオフが生じる．このとき重要になるのがパレート最適という考え方である．

ある解がパレート最適であるとは，「他のどの解を選んでも，ある目的関数を改善しようとすると，別の目的関数が必ず悪化してしまう」という状態をいう．また，そのようなパレート最適解に対応する目的関数値ベクトルの集合を パレートフロント という．以上の用語について，正確な定義を次に記していこう．

パレート最適解

多目的最適化問題 (1) に対して，次を満たす \(x^*\in X\) をパレート最適解という．

(3)#\[\nexists x\in X : \bigwedge_{i=1}^{p} f_i(x)\leq f_i(x^*) \land f(x)\neq f(x^*)\]

弱パレート最適解

多目的最適化問題 (1) に対して，次を満たす \(x^*\in X\) を弱パレート最適解という．

(4)#\[\nexists x\in X : \bigwedge_{i=1}^{p} f_i(x)<f_i(x^*)\]

Tip

（弱）パレート最適解のことを（弱）非劣解，（弱）有効解とも呼ぶ．

パレート最適解は弱パレート最適解である．一方，弱パレート最適解では，ある目的関数を改善し，他の目的関数は据え置くような実行可能解が存在しうる．よって，弱パレート最適解がパレート最適解であるとは限らない．

6.2.3. パレートフロント #

完全最適解と（弱）パレート最適解との関係を，目的空間の上で視覚的に理解するため，まず目的空間の概念を次に定義する．

目的空間，目的空間上の実行可能集合

多目的最適化問題 (1) に対して，目的関数値ベクトル \(y\) が属する空間を目的空間という．

(5)#\[y = f(x) = (f_1(x),\ldots,f_p(x))\]

そして，目的空間のうち，実行可能解に限定してできる集合 \(Y\) を目的空間上の実行可能集合という．

(6)#\[Y = f(X) = \{y\in\mathbb{R}^p \mid y=f(x), x\in X\}\]

図 6.3 に示す \(f(x)=(f_1(x),f_2(x))\) の場合で，完全最適解，パレート最適解，弱パレート最適解を目的空間で見てみよう．

図の左図，中図，右図の太線部分が，それぞれ完全最適解，パレート最適解，弱パレート最適解に対応する目的関数値の分布の様子を表している．特に，パレート最適解と弱パレート最適解との違いを強調するために，赤色で違いを強調している．

実際，点 \(A_1\) と点 \(A_2\) での目的関数値は次の関係にある．

(7)#\[f_1(A_1) < f_1(A_2) \land f_2(A_1) = f_2(A_2)\]

つまり，点 \(A_2\) から見たとき，目的関数 \(f_2\) の値を改善することはできない．これは，\(f_1(x) < f_1(A_2) \land f_2(x) < f_2(A_2)\) を満たす解 \(x\) が存在しないことを意味している．よって，弱パレート最適になっている．一方で，\(f_1(x) \leq f_1(A_2) \land f_2(x) \leq f_2(A_2) \land f(x) \neq f(A_2)\) を満たす解として点 \(A_1\) が存在している．従って，点 \(A_2\) はパレート最適ではない．このことは，点 \(B_1\) と点 \(B_2\) についても同様である．

さて，この図の場合，完全最適解の場合は一点のみであるが，（弱）パレート最適解は曲線状に分布している ⁴ ⁴非凸の場合には，完全最適解は一点とは限らず，またパレート最適解の分布も連結な曲線状になるとは限らない．．このような解の分布を扱うために，次の用語を定義しよう．

パレート最適解集合，弱パレート最適解集合

多目的最適化問題 (1) のパレート最適解全体からなる集合をパレート最適解集合と呼び，\(X^*(\subset X)\) と表す．同様に，弱パレート最適解全体からなる集合を弱パレート最適解集合と呼び，\(X^*_{\mathrm{weak}}(\subset X)\) と表す．なお，定義から，\(X^*\subset X^*_{\mathrm{weak}}\) が従う．

パレートフロント，弱パレートフロント

多目的最適化問題 (1) のパレート最適解集合を目的空間に写した像 \(Y^*(\subset Y)\) をパレートフロントと呼び，次で表す．

(8)#\[Y^* = f(X^*) = \{f(x^*)\mid x^*\in X^*\}\]

同様に，弱パレート最適解集合を目的空間に写した像 \(Y^*_{\mathrm{weak}}(\subset Y)\) を弱パレートフロントと呼び，次で表す．

(9)#\[Y^*_{\mathrm{weak}} = f(X^*_{\mathrm{weak}}) = \{f(x^*)\mid x^*\in X^*_{\mathrm{weak}}\}\]

なお，定義から，\(Y^*\subset Y^*_{\mathrm{weak}}\) が従う．

注釈

解空間上でみたときのパレート最適解集合 \(X^*\) および弱パレート最適解集合 \(X^*_{\mathrm{weak}}\) と，それらを目的空間へ写した像であるパレートフロント \(Y^*\) および弱パレートフロント \(Y^*_{\mathrm{weak}}\) とは区別される．

また，パレートフロントが特に滑らかな曲線や（超）曲面となるとき，パレートフロントをパレート曲線あるいはパレート（超）曲面と強調して呼ぶことがある．

6.3. 多目的最適化問題へのアプローチ #

多目的最適化問題にアプローチする代表的な方法としては以下が考えられ，それらを状況に応じて使い分けたり，場合によっては臨機応変にさらなる工夫を考えることになる．

加重方式
付順方式
制約方式
平準化方式

これらは複数の目的関数を単一の目的関数に変換して，パレート最適解との関連を議論する手法であることから，スカラー化手法 とよばれる．

注釈

数理最適化問題として定式化せずに，遺伝的アルゴリズム，粒子群最適化，シミュレーテッドアニーリングなどの各種のメタヒューリスティクス手法で問題解決することも，手段の一つではある．

6.3.1. 加重方式 #

複数ある目的関数から次の重み付き線形和を作って，これを最小化する問題としてアプローチが考えられる．

(10)#\[f(x;\mu) = \sum_{k=1}^{p} \mu_k f_k(x)\]

この方法は手軽ではあるものの，重み \(\{\mu_k\}_{k=1}^p\) の設定方法が難しい．各目的関数の重要度に明白な優劣がある場合には有用である．重み係数法，加重和最小化法など，様々な別称がある．

目的空間で重み付き線形和 \(f(x;\mu)\) を見ると，次の性質を視覚的に確認することができる．

重みをすべて正に取れば，重み付き線形和 \(f(x;\mu)\) の最適解は，元の多目的最適化問題 (1) のパレート最適解となる．一方，重みの一部を \(0\) に許すと，得られるのは弱パレート最適解にとどまることがある．
元の多目的最適化問題 (1) が凸であれば，重みを調整することで，目的空間上のパレートフロントに沿ってパレート最適解を選び出すことができる．

図 6.5 に示す \(f(x)=(f_1(x),f_2(x))\) の場合で，上記の性質を目的空間で見てみよう．

図に示した赤線は，目的空間における重み付き線形和 \(f(x;\mu)\) の等高線である．目的空間上の実行可能集合 \(Y\) が凸集合であれば，傾きに相当している重みを調整することで，どのパレート最適解も選び出せることを見て取れる．一方で，非凸集合の場合には，パレートフロントに凹んだ部分が生じ，重みを調整しても到達できないパレート最適解が現れることがある．つまり，重み付き線形和の等高線をどのように傾けても，その凹み部分には接しない．図ではこのことを赤色の破線で示している．従って，そこにあるパレート最適解は加重方式では得られないことがある．よって，加重方式は実装が容易である一方，問題の凸性に依存して表現できるパレート最適解に限界がある．

6.3.2. 付順方式（辞書式最適化）#

今仮に目的関数が \(f_1\) と \(f_2\) の二つがあったとして，それらの重要度は \(f_2\) よりも \(f_1\) の方が重要であったとしよう．

するとこのときは次の二つの最適化問題を順に求解すれば，重要度を考慮したパレート最適解が得られる．

(11)#\[\begin{split}& \mathrm{Minimize\colon}~ f_1(x) \\ & \mathrm{Subject~to\colon}~ x\in X\end{split}\]

(12)#\[\begin{split}& \mathrm{Minimize\colon}~ f_2(x) \\ & \mathrm{Subject~to\colon}~ x\in X, \\ & f_1(x_1^*) \geq f_1(x)\end{split}\]

ここで \(x_1^*\) は一回目の \(f_1\) の最適化に対する最適解である．

このようにすると二回目の求解では，重要度が高い目的関数 \(f_1\) の最小値を悪化させない範囲で，目的関数 \(f_2\) の最適化を図っていることになる．

図 6.7 に示す目的空間の例であれば，一回目の求解で弱パレートフロント上の点 \(A\) での結果が得られ，二回目の求解で点 \(A^*\) での結果が得られることになる．同様に，点 \(B\to B^*\) については，\(f_2\to f_1\) の順序で求解した場合に相当している．

以上に述べたことは一般に \(p\) 個ある目的関数のそれぞれについて，重要度の序列がもし決まっていれば，同様のことを適宜行うことで，その序列に従ったパレート最適解が得られることになる．

例えば上記の例でさらに \(f_3\) という目的関数が三番目に重要であれば，先に続けて三回目に次の最適化問題を求解すればよい．

(13)#\[\begin{split}& \mathrm{Minimize\colon}~ f_3(x) \\ & \mathrm{Subject~to\colon}~ x\in X, \\ & f_1(x_2^*) \geq f_1(x), \\ & f_2(x_2^*) \geq f_2(x)\end{split}\]

ここで \(x_2^*\) は二回目の求解で得られた最適化である．

こうして述べた手法は加重方式と違って，明示的に優先度合いを指定できる点で優れているが，やや実装が複雑になることと，そもそも考慮したい序列の数だけ求解しなければならない点を考慮する必要がある．

特徴	加重方式	付順方式
難点	重みの決め方に経験を要する．	モデル記述がやや複雑になる．
求解数	一回	複数回
納得性	複数の目的関数が絡むため，説明がし辛いことがある．	優先順序に従った結果と簡潔明瞭に説明できる．

6.3.2.1. 例 #

多目的最適化の例として，PySIMPLE ドキュメント | 多目的最適化にある次を考えてみよう．

(14)#\[\begin{split}&\mathrm{Minimize\colon}~ f(x,y,z) = (x+y,y+z,z+x) \\ &\mathrm{Subject~to\colon}~ \\ &x\leq 2, \\ &y\leq 2, \\ &z\leq 2, \\ &x+y+z\geq 4\end{split}\]

まず，目的空間を求めてみよう．今の場合には，\(u=x+y,v=y+z,w=z+x\) と変数変換し，変数間の制約式に代入することで，目的空間上での実行可能集合 \(Y\) を定める次の一連の不等式を求めればよい．

(15)#\[\begin{split}u + v - w &\leq 4, \\ v + w - u &\leq 4, \\ w + u - v &\leq 4, \\ u + v + w &\geq 8\end{split}\]

これにより，四面体領域（単体）としての実行可能集合 \(Y\) が得られたことになる．このように，線形な制約式は，線形な目的関数によって，再び線形な不等式に写像されるため，凸性が保存されることになる．

次に，この多目的最適化問題 (14) を次の手続きに従った付順方式で求解したとしよう．

目的関数に \(x + y\) を設定して求解 (\(x=1, y=1, z=2\))
問題に制約「\(x + y \leq 2(=目的関数値)\)」を追加
目的関数に \(y + z\) を設定して求解 (\(x=2, y=0, z=2\))
問題に制約「\(y + z \leq 2(=目的関数値)\)」を追加
目的関数に \(z + x\) を設定して求解 (\(x=2, y=0, z=2\))

以上によって，最終的に，目的空間の点 \((2,2,4)\) が得られることになる．

この様子をプロットすると，次のとおりである．

6.3.3. 制約方式（制約変換法，\(\varepsilon\) 制約法）#

多目的最適化問題 (1) に対して，最も優先したい目的関数が一つあって，それを \(f_j\) としよう．このとき次の単目的最適化問題を解くことを制約方式という．

(16)#\[\begin{split}& \mathrm{Minimize\colon}~ f_j \\ & \mathrm{Subject~to\colon}~ x\in X, \\ & f_k(x) \leq \varepsilon_k,\, \forall k\in\{1,\ldots,j-1,j+1,\ldots,p\}\end{split}\]

ここで \(\varepsilon_k\) は手で与える定数で，特別視している目的関数 \(f_j\) の最小化によって，他の目的関数が悪化する可能性を制約として押さえつける程度を指定するものである．こうして与える上限制約を \(\varepsilon\) 制約と呼び，\(\varepsilon\) は各目的関数値の要求水準としての役割を果たす．

図 6.9 に示す目的空間を例に考えてみよう．

図の例でいえば，赤線の部分がパレートフロントである．実務上は，このパレートフロントの中から，意思決定者がどの目的を重視するかに応じて解を選択することになる．仮に，\(f_2\) を主目的として最小化し，\(f_1\) に対して要求水準 \(f_1(x)\leq \varepsilon\) を課すとしよう．このとき，\(\varepsilon\) として \(f_1\) を単目的で解いたときの最適値 \(f_1(x^*)\) を採用すれば，付順方式と同じ点 \(A\to A^*\) の求解結果が得られることになる．このため，制約方式は付順方式をより一般化した方式とみることもできる．

そして，要求水準 \(\varepsilon\) として，最適値以外に設定することで，パレートフロント上の中間的な点 \(C\) のような解を選ぶこともできる．例えば，\(f_1\) の値は \(4\) までなら意思決定上許容できるならば，要求水準として \(\varepsilon=4\) を採用すればよく，中間的な点 \(C\) のような解を得ることもできる．このような解は，単一の目的だけを極端に追い込んだ解よりも，実務上の説明や合意形成がしやすいことがある．この意味で制約方式は，特定の目的関数を主として最適化しつつ，他の目的関数については「どこまでなら許容するか」を明示的にモデルへ反映できる手法である．

6.3.4. 平準化方式 #

多目的最適化問題 (1) に対して次の問題変形を考えよう．

(17)#\[\begin{split}& \mathrm{Minimize\colon}~ y \\ & \mathrm{Subject~to\colon}~ x\in X, \\ & f_k(x) \leq y,\, \forall k\in\{1,\ldots,p\}\end{split}\]

このように目的関数の最大値を意味する新たな変数 \(y\) を導入することで，次の最大値 ⁵ ⁵\(\infty\)-ノルムの別称が Tchebyshev ノルムであることに因んで，ここで考えた \(f_{\infty}(x)=\max_{k\in \{1,\ldots,p\}} f_k(x)\) を Tchebyshev スカラー化関数ともいう．の最小化を表現できる (最大値最小化問題への帰着)．このことから平準化方式は単にミニマックス方式ともいう．

(18)#\[\min_{x\in X} \max_{k\in \{1,\ldots,p\}} f_k(x)\]

目的空間でみれば，この方式は「最も悪い目的関数値」をできるだけ引き下げるように働く．よって，極端に大きい目的関数値が生じることを避けたい場合には，自然な定式化であり，平準化の一つの表現になっている．但し，この方式が直接に表しているのは最大値の抑制であり，すべての目的関数値を均等に揃えることではない．

最大値に選ばれなかった他の目的関数は「遊んでいる」状態になり，パレート最適な解が保証されているわけではないことに注意する．実際，最適解において \(y\) を規定していない目的関数は，さらに改善できても変数 \(y\) の値を変えないため，最適化上は非アクティブになることがある．このため，得られた解がパレート最適解ではなく，弱パレート最適解にとどまる場合がある．

必要であれば，まず \(y\) を最小化した後，その最適値を固定して他の目的関数をさらに最小化することで，このような改善余地を詰めることができる．

6.3.4.1. 例 #

次の定式化があったとしよう．

PySIMPLE Sample Code

from pysimple import Problem, Parameter, Variable, Element

p = Problem(type=min)
k = Element(value=[1,2,3,4])
L = Parameter(index=k)
L[k] = 10*k
x = Variable(index=k)
y = Variable()
p += y
p += x[k] <= y
p += x[k] >= L[k]
p.solve()

print('\n[Print]')
print(x.val)

上記を実行すると次の結果を得る．

Result

[Print]
x[1].val=25.00000000050604
x[2].val=30.00000000050604
x[3].val=35.00000000050604
x[4].val=40.00000000050604

これは x[1] から x[4] を目的関数とした場合には， x[4] が最も最小化しがたい目的関数になっており， 40 で他の目的関数の最小化は止まることになる．

このとき，他の目的関数はもっと小さくできるのに，その意図は定式化には含まれていないので，遊んでいることになる．またもし平準化とは「偏りをなくすこと」「均等にすること」を意図している場合には， x[1] から x[4] はどれも 40 に近い値をとっていることを素朴には期待するところである．しかし遊んでいるため，そうはなっていない．

ところで，平準化方式でいう単純な最大値最小化では，各目的関数の重要度や尺度の違いを反映できないことがある．このため，加重方式と関連させて，各目的関数の寄与を調整した次の最適化問題を考えることもよくある．

(19)#\[\begin{split}& \mathrm{Minimize\colon}~ y \\ & \mathrm{Subject~to\colon}~ x\in X, \\ & \mu_k f_k(x) \leq y,\, \forall k\in\{1,\ldots,p\}\end{split}\]

多目的最適化問題

目次