実務ではいろんなことを最小化したい場合がありますよね。例えば、時間だったり、電気代だったり、人手だったり、、。そんなときに、考えるのは多目的最適化です。その多目的最適化について解法を紹介します。
今、最小化したい 個のコスト関数を
$$ f_1(x), \dots, f_k(x) $$
とし、与えらた制約条件を満たす解の集合(実行可能領域)を とします。
このとき、多目的最適化問題としての求解アプローチは、いろいろありますが、この記事では基本的な3つ紹介します。
- パラメータ法
- 制約化法
- min-max法
1. パラメータ法
はパラメータです。
を大きくすると、対応するコスト関数の
をより小さくした解が、最適解になります。
2. 制約化法
例えば、あるコスト関数 が最も重要である場合、他のコスト関数を制約式に入れてしまいます。
この問題は、
「 以外のコスト関数は、
というパラメータを使用し、
は大きくもここまで」というように、制約化された問題です。
3. min-max法
コスト関数 に優先順位は無く、最大値を最小化したいときに使う方法。例えば、バスの遅延最小化を考えたときに、各バスそれぞれの遅延関数が、
に対応します。
(もし、 が電気代、
が交通費みたいに、全く違うものを比較する場合、スケーリングする必要があります)
最大値を最小化する問題は、このように表現できるが、このままでは最適化ソフトウェアで解けないので、次のように変形します。
全コスト関数を上から抑えた を最小化する問題で、maxが目的関数に入っている問題と同じ最適解を得ることができます。