この記事について
数理最適化をしていると、よく出てくる話が「目的が複数あってどれを優先したらいいかわからない」という話です。
「コストを下げたいけど品質も上げたい」「配送時間を短くしたいけど燃費も良くしたい」みたいな。
これ、一つの目的だけ追えばいいなら普通の最適化問題なのですが、複数の目的を同時に追おうとすると途端に難しくなるんですよね。。。
この記事シリーズでは、そんな多目的最適化について、できるだけ直感的に理解できるように説明していこうと思います。
シリーズは全4記事の予定で、以下の内容を扱います。
| 記事 | 内容 |
|---|---|
| ①（本記事） | 多目的最適化とは？基礎概念 |
| ② | NSGA-IIの説明 |
| ③ | MOEA/Dの説明 |
| ④ | ベンチマーク問題の説明 |
概要：そもそも「多目的」って何が難しいの？
まず、普通の（単目的）最適化を振り返ってみましょう。
例えば「コストを最小化したい」という問題があったとして、答えは基本的に「一番コストが低い解」です。比較が簡単ですよね。
でも「コストを最小化したい、かつ、品質を最大化したい」という問題はどうでしょうか？
コストが低い解がいくつかあったとして、その中で品質が高いものはどれか？を考えると、たいてい 「コストを下げると品質も下がる」というトレードオフが存在します。
これが多目的最適化を難しくする本質です。
多目的最適化問題の定義
多目的最適化問題は、一般的に以下のように定式化されます。
\text{Minimize} \quad \mathbf{f}(\mathbf{x}) = (f_1(\mathbf{x}), f_2(\mathbf{x}), \ldots, f_m(\mathbf{x}))
\text{subject to} \quad \mathbf{x} \in X
ここで、
- $\mathbf{x}$ は決定変数ベクトル
- $X$ は決定変数空間（実行可能領域）
- $f_i(\mathbf{x})$ は $i$ 番目の目的関数
- $m$ は目的関数の数
を示します。
今回は最小化問題として統一しますが、最大化問題も符号を反転させれば最小化に変換できます。
パレート支配（Pareto Dominance）
多目的最適化では「どの解が良い解か？」を判断するために、パレート支配という概念を使います。
定義
2つの解 $\mathbf{x}$, $\mathbf{y}$ があったとき、 $\mathbf{x}$ が $\mathbf{y}$ を支配する（$\mathbf{x} \prec \mathbf{y}$）とは、以下の2条件を同時に満たすことを言います。
\forall i \in \{1, \ldots, m\}: f_i(\mathbf{x}) \leq f_i(\mathbf{y})
\exists j \in \{1, \ldots, m\}: f_j(\mathbf{x}) < f_j(\mathbf{y})
平たく言うと、
- すべての目的関数で $\mathbf{x}$ は $\mathbf{y}$ より悪くない
- 少なくとも1つの目的関数で $\mathbf{x}$ は $\mathbf{y}$ より明確に良い
ということです。
具体例
2目的問題（$f_1$ と $f_2$ を最小化）で考えてみましょう。
| 解 | $f_1$ | $f_2$ | 解説 |
|---|---|---|---|
| A | 1.0 | 3.0 | - |
| B | 2.0 | 2.0 | - |
| C | 1.5 | 4.0 | Aに支配される |
| D | 0.5 | 2.5 | Aを支配する |
- D は A を支配する（$f_1$: 0.5 < 1.0、$f_2$: 2.5 < 3.0 →両方で良い）
- D は B を支配しない（$f_1$: 0.5 < 2.0、$f_2$: 2.5 > 2.0 →$f_2$で悪いのでは？）
Dは$f_2$でBより悪いですよね。なので D は B を支配しません。
「すべての目的で悪くない」という条件を満たしていないのでアウトです。
- A と B は互いに支配しない（$f_1$: AがBより良いが、$f_2$: BがAより良い → トレードオフ）
このようにトレードオフの関係にある解同士は、どちらが「より良い」とは一概に言えないわけです。
パレート最適解（Pareto Optimal Solution）
どの解にも支配されない解のことをパレート最適解と言います。
上の例だと、解 A と B はお互いにトレードオフの関係にあり、どちらが良いとは言い切れません。この場合、AもBも「パレート最適解」の候補となります。
パレート最適解の集合をパレート最適解集合と呼び、その目的関数空間における像をパレートフロント（Pareto Front）と呼びます。
パレートフロントのイメージを図にすると以下のようになります。
上図は2目的問題（$f_1$, $f_2$ を最小化）のパレートフロントのイメージです。
青い曲線がパレートフロントで、赤い点が支配される解（パレートフロントより右上にある解）を示しています。
上図を生成したコードは以下のとおりです。
import numpy as np
import matplotlib.pyplot as plt
plt.rcParams['font.family'] = 'Yu Gothic' # 日本語フォント設定
# 中心(4,4)・半径4の円弧（θ: π→3π/2 で (0,4)→(4,0) の弧）
theta = np.linspace(np.pi, 3 * np.pi / 2, 100)
f1 = 4 + 4 * np.cos(theta)
f2 = 4 + 4 * np.sin(theta)
# 非パレート最適な点（支配される点）：表のA, B, C, D
dominated_f1 = [1.0, 2.0, 1.5, 0.5]
dominated_f2 = [3.0, 2.0, 4.0, 2.5]
fig, ax = plt.subplots(figsize=(6, 5))
ax.plot(f1, f2, 'b-', linewidth=2, label='パレートフロント')
ax.scatter(dominated_f1, dominated_f2, c='red', s=100, label='支配される解', zorder=5)
# 各点にラベルを付ける
for label, x, y in zip(['A', 'B', 'C', 'D'], dominated_f1, dominated_f2):
ax.annotate(label, (x, y), textcoords='offset points', xytext=(8, 4), fontsize=11)
ax.set_xlabel('f₁ (最小化)', fontsize=12) # Unicode下付き文字を使用
ax.set_ylabel('f₂ (最小化)', fontsize=12)
ax.set_title('パレートフロントのイメージ（2目的）')
ax.set_xlim(0, 4.5)
ax.set_ylim(0, 4.5)
ax.legend()
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('pareto_front.png', dpi=150)
plt.show()
上記コードを実行すると、パレートフロント（青線）と支配される解（赤点）の関係がわかるかと思います。
パレートフロントより右上の点はすべて「パレートフロント上のどこかの点に支配される」ということになります。
多目的最適化の目標
単目的最適化では「最良の解を1つ見つける」ことがゴールでしたが、多目的最適化では少し違います。
多目的最適化の目標は 「パレートフロントを近似する多様な解の集合を求めること」 です。
なぜ「1つ」じゃないのかというと、「コストと品質のどちらを重視するか」という最終的な判断は、最適化後に人間（意思決定者）が行うべきだからです。
最適化アルゴリズムはあくまで「トレードオフの全体像」を提示してくれるわけです。
良い多目的最適化アルゴリズムに求められる性質は主に2つあります。
- 収束性（Convergence）：解の集合がパレートフロントに近いこと
- 多様性（Diversity）：解の集合がパレートフロントを広くカバーしていること
この2つを同時に満たすことが難しい、というのが多目的最適化の面白いところです。
なぜ進化型アルゴリズムが使われるのか？
多目的最適化を解く方法としてよく使われるのが 進化型多目的最適化（EMO: Evolutionary Multi-objective Optimization） です。
遺伝的アルゴリズム（GA）などの進化型アルゴリズムが多目的最適化に向いている理由は、一度の実行で複数の解（集団）を扱えるからです。
単目的最適化のように「一番良い解を一つ探す」のではなく、「多様でパレートフロントに近い解の集団を進化させていく」というアプローチが自然に取れまる。
代表的な手法として、
- NSGA-II：非劣解ソートとクラウディングディスタンスを使う手法
- MOEA/D：問題を複数の単目的問題に分解して解く手法
などがあります。次回以降でこれらを詳しく説明していきます。
まとめ
今回は多目的最適化の基礎概念を説明しました。
- 複数の目的を同時に最適化する問題が多目的最適化問題
- パレート支配：全目的で悪くなく少なくとも1目的で良い関係
- どの解にも支配されない解がパレート最適解
- パレート最適解の目的関数空間での像がパレートフロント
- 多目的最適化のゴールはパレートフロントの近似解集合を求めること
次回はNSGA-IIの説明をしていきます。
参考にした記事や本、論文等
- K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-II," IEEE Trans. on Evolutionary Computation, vol. 6, no. 2, pp. 182-197, 2002.
- 多目的最適化 - Wikipedia