3.8.14. 多目的最適化

多目的最適化問題とは目的関数が複数存在する数理最適化問題のことです． 複数の目的関数を同時に最適とする解(完全最適解)が存在するとは限らず，また目的関数も複数とることができないため， 工夫が必要となります．

PySIMPLE では目的関数に添字が残っていたり，複数の目的関数を設定するとエラーとなります．:

>>> p = Problem()
>>> i = Element(value=[1,2], name='i')
>>> x = Variable(index=i, name='x')
>>> p += x[i]  # 添字が残っている
pysimple.error.SimpleError: objective cannot be defined with index
>>> p += x[1]  # 目的関数(1 つ目)
>>> p += x[2]  # 目的関数(2 つ目)
pysimple.error.SimpleError: objective can only be assigned once

多目的最適化の例として，制約 x≦2，y≦2，z≦2，x+y+z≧4 の元で， x + y，y + z，z + x のそれぞれを最小化したいとします． このとき目的関数をどのように設定したらよいでしょうか．:

x = Variable(ub=2)
y = Variable(ub=2)
z = Variable(ub=2)

p = Problem()
p += x + y + z >= 4
p += ?, '目的関数'

多目的最適化を実現する方法の 1 つは，多段階で最適化を行うというものです． これを汎用的に実装したものが以下となります．:

objs = x + y, y + z, z + x
for obj in objs:
    p += obj
    p.solve()
    Printf('x: {:.1f} y: {:.1f} z: {:.1f}', x.val, y.val, z.val)
    p += obj <= p.objective.val + 1e-5

上記のモデルでは次のようなステップで求解を行っております．

  1. 目的関数に x + y を設定して求解 (x=1, y=1, z=2)

  2. 問題に制約「x + y ≦ 2(=目的関数値)」を追加

  3. 目的関数に y + z を設定して求解 (x=2, y=0, z=2)

  4. 問題に制約「y + z ≦ 2(=目的関数値)」を追加

  5. 目的関数に z + x を設定して求解 (x=2, y=0, z=2)

今回のモデルでは，ステップ 1 でいわゆる「パレート最適」となっており，最適解が複数存在しています． また，この方法の場合，目的関数の設定順序によって最終的な解が変わる可能性がある点に注意しましょう．

多目的最適化を実現する別の方法は，目的関数ごとに重みをつけて同時に扱う方法です． これを実装したものが以下となります．:

for w1, w2 in (1, 1), (1, 2), (2, 1):
    p += (x + y) + w1*(y + z) + w2*(z + x)
    p.solve()
    Printf('x: {:.1f} y: {:.1f} z: {:.1f}', x.val, y.val, z.val)

重み w1, w2 の値によって変数の値は次のようになりました．

  • w1=1, w2=1 のとき x=1.3, y=1.3, z=1.3

  • w1=1, w2=2 のとき x=1, y=2, z=1

  • w1=2, w2=1 のとき x=2, y=1, z=1

今回は重みによって変数の値が変わる様子を確かめるために複数求解を行いましたが， 重みが決まっている場合は必要ありません． 一方で，この重みの決め方が難しいのですが，重みは目的関数ごとのトレードオフ割合と考えることができます．

例えば，目的関数が「コスト(万円) + w*移動距離(km)」だった場合， w=1 の場合は「コスト 1 万円の削減」と「移動距離 1km の短縮」を同価値に， w=10 の場合は「コスト 10 万円の削減」と「移動距離 1km の短縮」を同価値に考えていることになります． 単位が異なる目的関数を同時に考える場合は取りうる範囲に十分注意する必要があり，必要に応じて正規化を施します．