《多目的計画》のソースを表示

【たもくてきけいかく (multiobjective programming)】

　我々が現実世界において遭遇する意思決定問題には, 複数の評価尺度(目的)があることが多い. このような問題を多基準意思決定問題あるいは多目的意思決定問題と呼ぶ. このような問題の数理計画法としての定式化とその解決方法を考えるのが多目的計画である. 

　$p$ 個の目的関数をもつ多目的計画問題は
　
　
\[ \begin{array}{ll}
        \mbox{minimize} & f(x)=(f_1(x), \ldots , f_p(x))\\
        \mbox{subject to} & x \in X, 
\end{array} \]


という形に定式化される. ここで $X$は実行可能集合であるが, 通常の１目的の数理計画問題と同様, 不等式制約や等式制約で表現されることが多い. 

　通常の数理計画問題(最適化問題)であれば, 実数の大小関係が全順序であることから, 最適解の概念は明瞭であるが, 多目的の場合は一方が良くとも他方が悪くなることが生じるため順序関係が半順序となり, 考察を要する. 基本となるのは, \yougolink{A-E-05}{パレート最適解}{パレート最適解}(単にパレート解または非劣解, 有効解)と呼ばれる解である. 実行可能解 $x^* \in X$ は別の実行可能解 $x \in X$ で


\[ \begin{array}{ll}
        f_i(x) \leq f_i(x^*) & (\forall i=1, \ldots ,p), \\
        f_i(x) < f_i(x^*)    & (\exists i \in \{ 1, \ldots ,p \}), 
\end{array} \]


となるものが存在しないとき, パレート最適解であるといわれる. これを少し弱めた解として弱パレート最適解が, また強めた解として真性パレート最適解がある. さらに, 意思決定の観点からいえば, 最終的に意思決定者にとって最も好ましい解をパレート最適解の中から選ぶことが問題となるが, この解のことを意思決定者の選好解という. 

　通常の数理計画における理論的成果を, 多目的計画の場合に拡張する研究はこれまで多くなされてきている. まずパレート最適解を特徴づける最適性の条件は, キューン・タッカー条件を拡張した形で得られている. また多目的計画に対する双対性や安定性, 感度分析などの研究も進んでいる. ただし, 通常の問題であればその最適値$\min \{ f(x) | x \in X \} $は一意に定まる(厳密には, $\min$ を $\inf$ で置き換え, $\pm \infty$ を許容する場合もある). これに対し多目的のパレート最適解は一意には定まらないのが普通であり, パレート最適値(パレート最適解に対応する目的関数値)全体が一つの集合を与える. したがって, 通常の最適値関数に対応するものとして, いわゆる最適値写像あるいは摂動写像と呼ばれる集合値写像(点対集合写像)を考える必要がある. これらの理論的結果については\cite[1]\cite[3]に詳しい. 

　さて, 意思決定者の選好解を求めるには, 大きく分けて以下に述べる３つのアプローチがある. 

\begin{enumerate}
\item
 パレート最適解のすべて(もしくは十分多く)を求め, それを意思決定者に提示して, 選考解を決定してもらう. 
\item
 意思決定者の選好を表す実数値関数である価値関数(もしくは効用関数)を求め, それを最適化する通常の数理計画問題を解く. 
\item
 コンピュータによるパレート最適解の導出とその解に基づく意思決定者の局所的な選好情報を用いて, 両者の対話を繰り返すことにより, 選好解を求める. 
\end{enumerate}

　まず, 最初のアプローチは特に目的関数の数が少ない(例えば２目的の)場合や, 実行可能解が比較的少数の有限個しか存在しないような場合であれば, 有効となる. 実際にパレート最適解を求めるには, もとの多目的計画問題を何らかのパラメータを含む通常の数理計画問題に変換するスカラー化を行う. この方法として代表的なものは次の３つである. 


\begin{itemize}
\item 加重和最小化: 各目的関数に対する重み$w_i$を用いて, 問題
\[ \begin{array}{ll}
        \mbox{minimize} & \displaystyle \sum _{i=1}^p w_if_i(x)\\
        \mbox{subject to} & x \in X, 
\end{array} \]
を解く. 簡明で分かり易いが, 非凸な問題の場合には欠陥がある. 
\item 基準点からのノルム最小化: 基準点 $\bar{y}=(\bar{y}_1,\ldots ,
 \bar{y}_p)$ からのノルム(すなわち乖離度)を最小にする. すなわち, 問題 
\[ \begin{array}{ll}
        \mbox{minimize} & \parallel f(x)- \bar{y} \parallel\\
        \mbox{subject to} & x \in X, 
\end{array} \]


を解く. ノルムとしては, $l_1$ ノルム(\yougolink{A-E-05}{目標計画}{目標計画}はこの場合に相当する)やチェビシェフノルムなどが考えられる. また実際にはこれを拡張したチェビシェフスカラー化関数を用いたり, 目的関数に重みを導入したりする. 

\item 制約変換法: 一つの目的関数(例えば
 $f_p$)を目的関数として残し, 他の目的関数に対する要求水準 $\varepsilon _1,
 \ldots , \varepsilon _{p-1}$ を用いた問題
\[ \begin{array}{ll}
        \mbox{minimize} & f_p(x)\\
        \mbox{subject to} & f_i (x) \leq \varepsilon _i \; \; (i=1, \ldots , p-1), \;
 \; x \in X, 
\end{array} \]
を解く. 
\end{itemize}


　次に２番目のアプローチの価値関数(効用関数)の同定については, 多属性効用理論がよく知られている. この際大切なことは, 目的関数間の独立性が十分確保されていることである. 詳細については\cite[4]に詳しい. なお, 上に挙げた加重和目的関数やノルム関数を効用関数として想定し, そのパラメータを同定するのも, このアプローチの簡略版と考えられる. 

　最後のアプローチが\yougolink{A-E-05}{対話型解法（多目的計画における）}{対話型解法}とよばれているもので, コンピュータによる候補解の算出と意思決定者による選好情報の提示を交互に繰り返していくことにより, 選好解を探索する. 両者の情報交換の仕方によって, いくつもの方法が考えられているが, 人間が関わっているだけに, ヒューマンフレンドリーな方法であることが望まれる. 現在までに提案された主な対話型解法については\cite[2]に詳しい. 日本語では\cite[3]に希求水準法を中心とした説明がある. 


参考文献

[1] Y. Sawaragi, H. Nakayama and T. Tanino, ''Theory of Multiobjective Optimization'', 
  Academic Press, 1985.

[2] K. M. Miettinen, ''Nonlinear Multiobjective Optimization'', Kluwer Academic, 1999.

[3] 中山弘隆, 谷野哲三,『多目的計画法の理論と応用』, 計測自動制御学会, 1994.
  
[4] 田村坦之, 中村豊, 藤田眞一,『効用分析の数理と応用』, コロナ社, 1997.