用語解説 第87回テーマ: 多目的最適化問題

2020/10/01

池上 貴志 (東京農工大学)

1. 最適化問題

制約条件を満足する解(実行可能解)の中から最適解を探す問題を最適化問題という。何をもって最適とするか評価する(数値で表す)ための関数を目的関数といい,目的関数が最大あるいは最小となる解を求める問題である。一般にn 個の変数(決定変数)で決まる目的関数は,次式で書ける。

例えば設備導入費や,発電燃料費などを最小化する問題や,身近な例では,交通機関の経路検索などで最安経路を探索する問題では,コストが目的関数となる。

2. 多目的最適化問題

燃料費も下げたいがCO2 排出量も少なくしたい,あるいは,最安経路が良いが最短時間で到着したい,という場合など,意思決定をする際の目的は必ずしも1 つとは限らない。このとき,どちらの目的も同時に最適となる解が見つかればよいが,トレードオフの関係にあることも多い。トレードオフの関係にある複数の目的関数のもとで最適解を求める問題を「多目的最適化問題(multi-objective optimization problem)」といい,目的関数は(2)式のように複数となる。

多目的最適化では,1 つの最適解を決めることはできないため,図1(目的関数2 つを最小化する例)のように実行可能解のうち,他の目的関数の値を悪化させない限り改善できない状態にある解の集合を求める。この解をパレート最適解(Pareto optimal solution)という。


図1 実行可能解とパレート最適解

パレート最適解を求める方法の1 つとして,(3)式のように各目的関数に重みを付けて足し合わせ,単目的最適化問題に帰着して最適解を求め,重みを変えて繰り返すことで複数のパレート最適解を得るという方法がある。

 

【電気学会論文誌B,138巻,6号,2018に掲載】