多目的最適化(Multi Objective Optimization)について

記事の背景

最適化の研究として，これまで主に単目的最適化問題を学んできましたが，多目的最適化というものが存在し，行動・意思決定において役に立つということを聞くようになったので，記事の執筆を始めました．多目的最適化に関する記事はいくつかあります(例えば，参考１，参考２...など)ので，皆様の読みやすい記事を選択して頂ければと思います．ちなみに，本記事では，用語の定義を説明し，落穂拾いのように一つずつ多目的最適化の特徴を列挙することを，他の記事との差として示せることを目指して記述しています．

記事の目次

本記事は以下のような流れです．
1.多目的最適化問題の定義と用語の説明
2.単目的最適化問題との関係性
3.多目的最適化の主な解法とその概要
4.pythonによる実装例
5.まとめ

1. 多目的最適化問題の定義と用語の説明

本章では，多目的最適化問題を定義し，その中で用いられる用語の説明を行います．以下，著 木村英紀："現代システム科学概論"の記法に従って記述します．

まず，$m$個の関数$f_1(x),f_2(x),\cdots,f_i(x),\cdots,f_m(x)\ (i=1,2,\cdots,m)$が定義されているとします．ただし，$x$は$x\in \mathbb{R}^n$とし，$n>1$のような多変量の場合でも${x}$は太字にはせずに記載します．この下で，多目的最適化問題は次のように定義されます．
$$f_i(x) \rightarrow \mbox{最小化}\ (i=1,\cdots,m) $$
しかし，この目的関数全ての最小化を実現する$x$が存在するとは限らない．
例
以下に示す二つ($m=2$)の目的関数 $f_1(x),f_2(x)$ を考える．

\begin{align}
f_1 & = (x-2)^2\\
f_2 & = (x+2)^2
\end{align}　\tag{1}

決定変数$x$に対して制約がない場合，図や式から明らかな通り，$\underset{x}{\arg \min} f_1(x) =2,\hspace{0.2cm} \underset{x}{\arg \min} f_2(x) =-2 $がそれぞれの目的関数に対する大域的最適解となり，両方の目的関数の最小化を実現する$x$は存在しない．したがって，従来のような何か一つの解(あるいは目的関数として唯一の最小値を与える解の集合)を求めるという問題設定に対応して，多目的最適化における解の良さの定義について検討する必要が出てくる．
これに対する一つの回答は，後の2章で説明する単目的最適化問題への帰着であるが，もう一つの回答は，パレート最適という解の定義を行うことである．本章の残りは，多目的最適化でしばしば見られる，パレート最適，パレートフロント，選好解という用語の説明を行う．

パレート最適
著 木村英紀："現代システム科学概論"によると，パレート最適解は以下のように定義されます．(書籍では不等号の向きが間違っていると思われ，以下には修正した式を記載．)

定義
パレート最適解$x^{\ast}$は，ある$i$に対して，$f_i(x) < f_i(x^{\ast}), f_j(x) \leq f_j(x^{\ast}), j \neq i$となるような$x$が存在しない許容領域内の変数である．

この定義は，直観的に分かりにくいので，式(1)にいくつかの$x$の値を代入して確認してみる．
例1. $x=3$の時：$f_1(3) = 1, f_2(3) = 25$
例2. $x=2$の時：$f_1(2) = 0, f_2(2) = 4$
上記より，$x=3$では，目的関数$f_1(x),f_2(x)$の両方を改善することのできる$x=2$が存在するため，パレート最適解ではない．一方で，$x=2$はパレート最適解である．
※注意：
一般に，$x$について二つの値を代入しただけで一方をパレート最適と判定することはできないが，$x=2$については，$f_1(x)$の最適解であり，$x=2$よりも$f_1(x)$を改善することのできる解は存在しないため，パレート最適であることが言える．

パレート最適解の定義を換言すると，いずれかの目的関数を劣化させないとある目的関数を改善することのできない解の集合と言うことができます．(ただし，最小化問題において，劣化とは目的関数の値が増加すること，改善とは目的関数の値が減少することと本稿では定義します．)　これは，すなわち，目的関数のトレードオフ関係を示す解を列挙することになります．

以下の図は，横軸を$f_1(x)$,縦軸を$f_2(x)$とした場合に様々な$x$を代入していった結果を示しています．最小化問題なので，各軸について原点に近づくほど各目的関数$f_1,f_2$の下で良い解となります．　見慣れている,横軸が$x$,縦軸が$f_1(x)$のような図ではないことにご注意ください．
ここで，黄色い点がパレート最適解として抽出されたものであるのに対し，灰色の点は，両方共の目的関数を改善することのできる$x$が存在することからパレート最適解ではありません．(図を作成したプログラムは文末に記載してあります．)

パレートフロント
パレートフロントとは，パレート最適解の集合により形成される線あるいは高次元であれば面(必ずしも連続にはならないと思うので，正しい説明ではない気がしますが...)のことを指す．

選好解
多目的最適化問題をパレート最適性の定義の下で解いた結果得られるパレートフロントの中から，ユーザが良いと思って選んだ解のこと．(この選び方は特に決まっておらず，各目的関数の値を見ながら関係各位と相談することが多い様子．)

2. 単目的最適化問題との関係性

本章では，1章で説明したパレート最適の定義に基づく多目的最適化問題の解と，単目的最適化問題による解との関係性を考えてみる．まず，単目的最適化問題について簡単に説明する．
単目的最適化問題
単目的最適化問題とは，以下の最適化問題を解くことである．
$$ \underset{x}{\min} \sum_{i=1}^{m}w_if_i(x), w_i \geq 0　\tag{2}$$
式(2)の目的関数からわかる通り，多目的最適化問題における目的関数(式(1))に対して重みづけ$w_i$をかけることによって一つの指標に統合し，解を評価する．この重み$w_i$は各目的関数の優先度を示しており，最小化を優先したい目的関数に対して大きな値を持つ$w_i$をかけるようにユーザが設計することができる．$w_i$の絶対的な値に特に意味はなく，$w_i$と$w_j(i \neq j)$の相対的な値が重要であることに注意する(どの目的関数を優先するのかを決定することが重みづけの意味)．また，$w_i$を負の値にしてしまうと，その目的関数に対して最小化ではなく最大化してしまうため，$w_i \geq 0$の制約が付されている．

では，多目的最適化と単目的最適化のそれぞれの解の関係性について考えてみる．例によって目的関数が二つ($m=2$)の場合(式(1))で考える．重みについて相対的な値が重要であることから，$w=\frac{w_1}{w_2}$と置いて話を進める(割り算を行っているので，$w_2 \neq 0$という条件が課されることに注意)．この重みの値の置き換えによって，目的関数の値としては変わるが，解$x$は変わらないので以下の式が成り立つ．
$$ \underset{x}{\arg \min}\ w_1f_1(x)+w_2f_2(x) = \underset{x}{\arg \min}\ w\ f_1(x)+f_2(x), w_1 \geq 0,\ w_2> 0,w \geq 0 \tag{3}$$
また，式(1)で定義した$f_1 = (x-2)^2, f_2 = (x+2)^2$はそれぞれ凸関数であるので，その(正の値で重みづけした)和も凸関数になる．したがって，式(3)の目的関数の答えは，最適性1次の条件を考えれば十分であり，最適解$x^{\ast}$は以下のように$w$の関数として表現される．
$$x^{\ast} = 2\ \frac{w-1}{w+1}\hspace{0.5cm} \because \frac{\partial}{\partial x} (wf_1(x)+f_2(x)) = 0 $$
いくつかの$w$に対して，最適解$x^{\ast}$および対応する$f_1(x^{\ast}),f_2(x^{\ast})$の値を計算してみる．

$w$	$x^{\ast}$	$f_1$と$f_2$の値
0	-2	$f_1(x^{\ast})=16$, $f_2(x^{\ast})=0$
1	0	$f_1(x^{\ast})=4$, $f_2(x^{\ast})=4$
1000	2	$f_1(x^{\ast})=0$, $f_2(x^{\ast})=16$

では，単目的最適化と多目的最適化の関係性について考える．そもそも，最適化問題における目的関数が異なるので，異なる解が出てくるわけですが，各々の目的関数の最適化は考えているはずなので何かしらの関係性はあるはずである．
まず，$wf_1(x)+f_2(x) = z$と置いてみる．すると，$f_2(x) = -wf_1(x) + z$となる．目的は$z$の最小化であり，これは$f_1-f_2$で張られる空間内のパレートフロントに対して，最小となる切片を求める問題と等価である．

図を用いて説明すると，以下のような形です．赤色接線は$w\simeq 0$の時の，緑色接線は$w\simeq 1$の時の，青色接線は$w\simeq 1000$　(数値計算上∞はできないので，仮置きの値)の時の結果を表しています．各図中の赤い星印は各$w:0,1,1000 $に対応する$x^{\ast}$によって決まる$f_1,f_2$の値(先に書いた表を参照ください)をプロットしたものです．

結局，この章で何が言いたいかというと，パレートフロントが凸集合であれば，パレートフロントは単目的関数の重み$w$を$0<w<\infty$で動かした場合の解を全て列挙したものということです．一方で，パレートフロントが非凸集合である場合には，単目的関数の重みを操作して得られる解の集合がパレートフロントと同値になるかは不明です．(多分一致しない)

単目的最適化の解を全て列挙してくれるのであれば，確かに意思決定において価値があるように思います．

3. 多目的最適化の主な解法とその概要

本章では，多目的最適化問題の主な解法について紹介します．アルゴリズムの詳細な説明は他の記事に譲ることとして，割愛しますが，どのような解法があるのか，どのような方針で解くのか　程度の概要は述べておきたいと思います．
多目的最適化問題の解は複数存在し，厳密にその集合を求めることは難しいため，基本的に数値解法に頼ります．私が調べた限りでは粒子群最適化(PSO)や遺伝的アルゴリズム(GA)をベースにしたアルゴリズムが提案されているようでした．以下に，簡単にそれらのアルゴリズムの最適化方針を記載します．

手法名	説明	多目的最適化用に改修されたアルゴリズム
PSO(Particle Swarm Optimization)	複数の粒子を最適化するエージェントとみなし，全体で情報共有しながら最適化を行う	MOPSO
GA(Genetic Algorithm)	決定変数を遺伝子構造に見立て，世代を経るごとに交叉・淘汰を繰り返して最適化を行う	MOGA,NSGA,SPEA,NPGA

※PSOについては，以前に解説記事を書きましたので，ご参考いただければと思います．
ご参考：https://qiita.com/opticont/items/04a5b4ff41483966987f

4. pythonによる実装例

本記事に添付した画像を生成するプログラムを添付します．https://watlab-blog.com/2021/12/26/platypus-opt-nsga2/#Platypusに記載されているwatさんのコードを流用させていただき，私は目的関数やラベルを変更しただけですので，実装の詳細が気になる方はそちらのページをご確認ください．

from platypus import *
from matplotlib import pyplot as plt
 
# 目的関数
def objective(vars):
    x = vars[0]
    f1 = (x-2) ** 2 
    f2 = (x+2) ** 2 
    return [f1, f2]
 
# 最適化計算を実行する関数
def optimization(n_var, n_obj, vars, n_run):
    # 設計変数と目的関数の数を設定
    problem = Problem(n_var, n_obj)
 
    # 最適化問題に最小化を設定
    problem.directions[:] = Problem.MINIMIZE
 
    # 設計変数と目的関数を設定
    problem.types[:] = vars
    problem.function = objective
 
    # 最適化アルゴリズムを設定して計算を実行する
    algorithm = NSGAII(problem)
    algorithm.run(n_run)
 
    return algorithm
 
# 変数を設定する
var1 = Real(-5., 5.)
vars = [var1]
 
# 最適化計算を実行する
algorithm = optimization(n_var=len(vars), n_obj=2, vars=vars, n_run=100)
 
# ここからグラフ描画
# フォントの種類とサイズを設定する。
plt.rcParams['font.size'] = 14
plt.rcParams['font.family'] = 'Times New Roman'
 
# グラフの入れ物を用意する。
fig = plt.figure(figsize=(6, 5))
ax1 = fig.add_subplot(111)
 
# 軸のラベルを設定する。
ax1.set_xlabel('$f_1(x)$')
ax1.set_ylabel('$f_2(x)$')
 
# 最適化結果から実現可能解をプロットする。
obj1 = []
obj2 = []
for solution in algorithm.result:
    obj1.append(solution.objectives[0])
    obj2.append(solution.objectives[1])
ax1.scatter(obj1, obj2, color='gray', edgecolor='gray', label='Trial', alpha=0.5)
 
# パレート解をプロットする。
n_dominated = nondominated(algorithm.result)    # 非劣解を抽出する
obj1 = []
obj2 = []
for solution in n_dominated:
    obj1.append(solution.objectives[0])
    obj2.append(solution.objectives[1])
ax1.scatter(obj1, obj2, color='yellow', edgecolor='black', label='Pareto front')
ax1.legend()
 
# グラフを表示する。
plt.show()
plt.close()

5. まとめ　

本稿では，多目的最適化問題におけるパレート最適の定義やその意味，特徴について紹介し，プログラムを記述してその挙動を確認しました．個人的には，2章で示した内容について，図を用いて幾何的に解釈できたことが楽しかったです．パレート最適解は，ある解の周りにも良い解が存在するのかを調べる(ロバスト性の確認)時に使えそうな気がしました．