6. 多目的最適化問題 #

6.1. 導入 #

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

(1)#\[\begin{split}& \mathrm{Minimize\colon}~ (f_1(x),\ldots,f_n(x)) \\ & \mathrm{subject~to\colon}~ x\in \Omega\end{split}\]

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

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

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

完全最適解

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

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

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

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

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

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

注釈

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

6.2. 加重方式 #

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

(3)#\[f(x;\mu) := \sum_{k=1}^{n} \mu_k f_k(x)\]

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

6.3. 付順方式 #

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

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

(4)#\[\begin{split}& \mathrm{Minimize\colon}~ f_1(x) \\ & \mathrm{subject~to\colon}~ x\in \Omega\end{split}\]

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

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

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

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

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

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

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

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

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

6.4. 制約方式 #

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

(7)#\[\begin{split}& \mathrm{Minimize\colon}~ f_j \\ & \mathrm{subject~to\colon}~ x\in \Omega, \\ & f_k(x) \leq \varepsilon_k,\, \forall k\in\{1,\ldots,j-1,j+1,\ldots,n\}\end{split}\]

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

6.5. 平準化方式 #

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

(8)#\[\begin{split}& \mathrm{Minimize\colon}~ y \\ & \mathrm{subject~to\colon}~ x\in \Omega, \\ & f_k(x) \leq y,\, \forall k\in\{1,\ldots,n\}\end{split}\]

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

(9)#\[\min_{x\in \Omega} \max_{k\in \{1,\ldots,n\}} f_k(x)\]

各目的関数はこの意味の下で公平な最適化がなされているとも考えられ，平準化の一つの表現になっている．

例えば，各目的関数を原点からの Euclid 空間上の様々な方向への距離と定義すれば，この最適化は同心球状に徐々に半径 \(y\) を減らすような最適化に対応している．

平準化方式 (8) は極端な不公平を回避しているという点では表現できている．しかし最大値に選ばれなかった他の目的関数は「遊んでいる」状態になり，パレート最適な解が保証されているわけではないことに注意する．

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

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 に近い値をとっていることを素朴には期待するところである．しかし遊んでいるため，そうはなっていない．

平準化方式はより一般的には，加重方式と関連させた次の最適化問題を考えることもよくある．

(10)#\[\begin{split}& \mathrm{Minimize\colon}~ y \\ & \mathrm{subject~to\colon}~ x\in \Omega, \\ & \mu_k f_k(x) \leq y,\, \forall k\in\{1,\ldots,n\}\end{split}\]

多目的最適化問題

目次

6. 多目的最適化問題#

6.1. 導入#

6.2. 加重方式#

6.3. 付順方式#

6.4. 制約方式#

6.5. 平準化方式#

6. 多目的最適化問題 #

6.1. 導入 #

6.2. 加重方式 #

6.3. 付順方式 #

6.4. 制約方式 #

6.5. 平準化方式 #