この記事について
多目的最適化入門シリーズの最後の記事です。今回はベンチマーク問題について説明します。
「NSGA-IIとMOEA/D、どっちが良いアルゴリズムなの？」という疑問が出てきたとき、実際に問題を解いて比較する必要があります。
でも「どんな問題で比較すればいいの？」という話になりますよね。
そこで登場するのがベンチマーク問題（benchmark problem）です。
多目的最適化入門シリーズの他の記事はこちら。
| 記事 | 内容 |
|---|---|
| ① | 多目的最適化とは？基礎概念 |
| ② | NSGA-IIの説明 |
| ③ | MOEA/Dの説明 |
| ④（本記事） | ベンチマーク問題の説明 |
ベンチマーク問題とは？
多目的最適化のベンチマーク問題は、「実際の問題に含まれる困難さの特徴を再現しながら、パレートフロントの形状が既知である人工的な問題」です。
なぜ「パレートフロントが既知」であることが重要かというと、アルゴリズムの結果（近似パレートフロント）と正解（真のパレートフロント）を比較することでアルゴリズムの性能が定量的に評価できるからです。
実問題でアルゴリズムを比較しようとすると
- パレートフロントが未知なので「どれだけ良いか」がわからない
- 実行コストが高い
- 問題設定が固定されてしまう
といった課題があります。ベンチマーク問題はこれらの問題を回避しつつ、アルゴリズムの特性を評価できるよう設計されています。
DTLZ問題群
DTLZ（Deb-Thiele-Laumanns-Zitzler）問題群は、多目的最適化で最もよく使われるベンチマーク問題の一つです。
K. Deb, L. Thiele, M. Laumanns, and E. Zitzler, "Scalable test problems for evolutionary multiobjective optimization," in Evolutionary Multiobjective Optimization: Theoretical Advances and Applications, pp. 105-145, 2005.
DTLZ問題の特徴は、目的数 $m$ と決定変数数 $n$ を自由に変えられるスケーラブルな設計になっていることです。
問題の共通構造
決定変数ベクトルを $\mathbf{x} = (x_1, x_2, \ldots, x_{m-1}, x_m, \ldots, x_n)$ とします。
- $\mathbf{x}_ I = (x_1, \ldots, x_{m-1})$：位置パラメータ（パレートフロント上のどこにいるかを決める）
- $\mathbf{x}_{II} = (vx_m, \ldots, x_n)$：距離パラメータ（パレートフロントからの距離を決める）
すべての決定変数は $[0, 1]$ の範囲を取ります。
DTLZ2
DTLZ問題にもいくつかシリーズがありますが、最も基本的なDTLZ問題です。パレートフロントが超球面の一部となります。
\text{Minimize} \quad f_1(\mathbf{x}) = (1 + g(\mathbf{x}_{II})) \prod_{j=1}^{m-1} \cos\!\left(\frac{\pi x_j}{2}\right)
f_i(\mathbf{x}) = (1 + g(\mathbf{x}_{II})) \prod_{j=1}^{m-i} \cos\!\left(\frac{\pi x_j}{2}\right) \cdot \sin\!\left(\frac{\pi x_{m-i+1}}{2}\right)
\quad (i = 2, \ldots, m)
g(\mathbf{x}_{II}) = \sum_{x_i \in \mathbf{x}_{II}} (x_i - 0.5)^2
$g(\mathbf{x}_{II}) = 0$ のとき（$x_i = 0.5$）パレートフロント上の解となります。
import numpy as np
def dtlz2(x, M):
"""
DTLZ2問題
x: 決定変数ベクトル (長さ M + k - 1, k = 10 が一般的)
M: 目的数
"""
k = len(x) - M + 1 # 距離パラメータの数
x_I = x[:M-1] # 位置パラメータ
x_II = x[M-1:] # 距離パラメータ
# g関数
g = sum((xi - 0.5)**2 for xi in x_II)
# 目的関数の計算
f = []
for i in range(M):
fi = (1 + g)
for j in range(M - 1 - i):
fi *= np.cos(np.pi * x_I[j] / 2)
if i > 0:
fi *= np.sin(np.pi * x_I[M - 1 - i] / 2)
f.append(fi)
return f
# パレートフロントの生成（2目的の場合）
def dtlz2_pareto_front_2d(n_points=100):
"""2目的DTLZ2の真のパレートフロントを生成"""
theta = np.linspace(0, np.pi/2, n_points)
f1 = np.cos(theta)
f2 = np.sin(theta)
return f1, f2
DTLZのスケール問題
DTLZ2の場合、すべての目的関数値の範囲が $[0, 1]$ に統一されています。
しかし現実の問題では、目的関数のスケールがばらばらなことがほとんどです。
DTLZ2だとスケールが揃っているため、「スケールが異なる場合の正規化の問題」を評価できません。
そこで登場するのが、スケールを意図的に変えたバリエーション問題です。
Rescaled DTLZ2（スケール変換DTLZ2）
$i$ 番目の目的関数の値域を $[0, 2i]$ に変えた問題です。
f_i^{\text{rescaled}}(\mathbf{x}) = 2i \cdot f_i(\mathbf{x})
$m$ 目的の場合、各目的関数の値域は $[0, 2], [0, 4], [0, 6], \ldots, [0, 2m]$ となります。
これにより、スケールが異なる状況でアルゴリズムの正規化処理の効果を評価できます。
Deceptive Rescaled DTLZ2（欺瞞的スケールDTLZ2）
さらに欺瞞的な（deceptive）バリエーションです。パレートフロントの真の値域（$g(\mathbf{x}_{II}) = 0$ のとき）と、実行可能領域全体での値域が大きく異なるように設計されています。
f_i^{\text{dec}}(\mathbf{x}) = \begin{cases}
2i \cdot f_i(\mathbf{x}) & (g(\mathbf{x}_{II}) = 0) \\
2i \cdot f_i(\mathbf{x}) \cdot (1 + y_a \cdot g(\mathbf{x}_{II})) & (g(\mathbf{x}_{II}) > 0)
\end{cases}
$y_a = 10$ などの大きな値を使うことで、$g > 0$ の解の目的関数値が非常に大きくなります。
これにより、「実行可能領域全体で推定した目的関数の範囲」と「パレートフロント近傍での目的関数の範囲」が大きく異なるという状況が作られます。
正規化のために使うnadir点（最悪値）の推定が難しくなり、アルゴリズムの正規化処理の頑健性を試すことができます。
ちなみにこのスケール操作は、正規化の影響以外にも別論点で重要なベンチマークとして使われることがありますが、超絶マニアックなのでここでは触れないことにします。
WFG問題群
WFG（Walking Fish Group）問題群は、DTLZよりも多様な特性のパレートフロントを持つベンチマーク問題群です。
S. Huband, P. Hingston, L. Barone, and L. While, "A review of multiobjective test problems and a scalable test problem toolkit," IEEE Trans. on Evolutionary Computation, vol. 10, no. 5, pp. 477-506, 2006.
WFGの特徴
WFG問題群は以下のような多様な特性を持っています。
| 問題 | パレートフロントの形状 | 特徴 |
|---|---|---|
| WFG1 | 混合（Convex + Disc） | 混合形状 |
| WFG2 | 非凸（Non-convex）+ 非連続 | 非連続パレートフロント |
| WFG3 | 線形、退化 | 低次元パレートフロント |
| WFG4 | 凹（Concave） | 多峰性 |
ほかにもWFG5～WFG9までありますが、1～4が良く使われます。
WFG4の構造
WFG問題群の中でよく使われるのが WFG4 です。凹型の球状パレートフロントを持ちます。
WFG4の目的関数の値域は $i$ 番目の目的について $[0, 2i]$ です（3目的なら $[0, 2], [0, 4], [0, 6]$）。
DTLZと違い、目的関数のスケールが最初から異なっているため、正規化なしでは多くのアルゴリズムが正しく機能しません。
性能評価指標：Hypervolume
アルゴリズムで得られた近似パレートフロントの「良さ」をどう測るか？というのも重要な問題です。
代表的な指標が Hypervolume（HV, S-metric とも呼ばれる）です。
Hypervolumeとは
あらかじめ設定した参照点（reference point）$\mathbf{r}$（通常はパレートフロントより悪い点）と、近似パレートフロントの各解で囲まれた体積（超体積）のことです。
\text{HV}(S, \mathbf{r}) = \lambda\!\left(\bigcup_{\mathbf{f} \in S} [\mathbf{f}, \mathbf{r}]\right)
ここで $\lambda$ はルベーグ測度（体積）を示します。
2目的の場合は面積、3目的の場合は体積になります。
HVが大きいほど良い（パレートフロントに近く、かつ多様）アルゴリズムということになります。
import numpy as np
def hypervolume_2d(pareto_front, reference_point):
"""
2目的のHypervolume計算
pareto_front: 近似パレートフロントの点群 [[f1, f2], ...]
reference_point: 参照点 [r1, r2]
"""
# f1でソート
pf = sorted(pareto_front, key=lambda x: x[0])
hv = 0.0
prev_f2 = reference_point[1]
for point in pf:
f1, f2 = point
# 横幅 × 縦幅
hv += (reference_point[0] - f1) * (prev_f2 - f2)
prev_f2 = f2
return hv
# 使用例
pf = [[0.1, 0.9], [0.3, 0.7], [0.5, 0.5], [0.7, 0.3], [0.9, 0.1]]
ref = [1.1, 1.1]
print(f"HV = {hypervolume_2d(pf, ref):.4f}")
HV = 0.6000
Hypervolumeの視覚的なイメージ
それぞれの寄与（0.20 + 0.16 + 0.12 + 0.08 + 0.04）の合計がHV = 0.60になります。一般的には、解が参照点より遠く、かつ広く分布しているほど面積が大きくなります。
HVとIGDの使い分け
Hypervolumeの他によく使われる指標に IGD（Inverted Generational Distance） があります。
\text{IGD}(S, PF^*) = \frac{1}{|PF^*|} \sum_{\mathbf{p} \in PF^*} \min_{\mathbf{s} \in S} d(\mathbf{p}, \mathbf{s})
真のパレートフロント上の各点から、近似パレートフロントの最近傍点までの距離の平均です。IGDは小さいほど良いです。
| 指標 | 計算量 | 特徴 |
|---|---|---|
| HV | 目的数が増えると指数的に増加 | 参照点の設定が必要。多様性と収束性の両方を評価 |
| IGD | $O(\vert PF^*\vert \cdot \vert S\vert)$ | 真のパレートフロントが必要。ベンチマーク問題なら使いやすい |
アルゴリズム比較の実際
DTLZ2・WFG4・Deceptive Rescaled DTLZ2 を使って、MOEA/D・NSGA-IIIの比較を行った研究例を紹介します。
（参考：H. Ishibuchi, K. Doi, and Y. Nojima, "On the effect of normalization in MOEA/D for multi-objective and many-objective optimization," Complex and Intelligent Systems, vol. 3, no. 4, pp. 279-294, 2017.）
目的関数の値域が揃っているDTLZ2では差がほとんど出ませんが、スケールが異なるWFG4・Deceptive Rescaled DTLZ2では正規化の有無でHV値に大きな差が出ます。
| テスト問題 | 目的関数値域 | 正規化なしMOEA/D | 正規化ありMOEA/D |
|---|---|---|---|
| DTLZ2（10目的） | $[0, 1.0]$（統一） | 2.515 | 2.515 |
| WFG4（10目的） | $[0, 2i]$（異なる） | 1.458 | 2.509 |
| Dec. Res. DTLZ2（10目的） | $[0, 1.0]$（パレートフロント周辺のみ） | 2.080 | 2.357 |
※値はHypervolume（大きいほど良い）
この結果を見ると、「スケールが異なる問題では正規化の効果が非常に大きい」ということがわかります。
DTLZ2だけで評価していると正規化の重要性を見落としてしまいますが、WFG4を使うことで問題点が明らかになるわけです。
こういうところがベンチマーク問題を使う意義ですね。
まとめ
今回はベンチマーク問題と評価指標を説明しました。
- ベンチマーク問題：パレートフロントが既知の人工問題でアルゴリズムを定量評価
- DTLZ問題群：スケーラブルで目的数を自由に変えられる。DTLZだけでは正規化問題を見落とす
- WFG問題群：目的関数のスケールが異なり、より現実に近い特性を持つ
- Hypervolume：収束性と多様性を同時に評価できる指標
この4回のシリーズで多目的最適化の基礎から代表的なアルゴリズム・評価方法まで一通り説明できたかと思います。
まだまだ説明が不十分なところもあるかとは思いますが、何かご指摘あれば優しくコメントいただけると幸いです笑
参考にした記事や本、論文等
- K. Deb, L. Thiele, M. Laumanns, and E. Zitzler, "Scalable test problems for evolutionary multiobjective optimization," in Evolutionary Multiobjective Optimization: Theoretical Advances and Applications, pp. 105-145, 2005.
- S. Huband, P. Hingston, L. Barone, and L. While, "A review of multiobjective test problems and a scalable test problem toolkit," IEEE Trans. on Evolutionary Computation, vol. 10, no. 5, pp. 477-506, 2006.
- H. Ishibuchi, K. Doi, and Y. Nojima, "On the effect of normalization in MOEA/D for multi-objective and many-objective optimization," Complex and Intelligent Systems, vol. 3, no. 4, pp. 279-294, 2017.
- K. Doi, R. Imada, Y. Nojima, and H. Ishibuchi, "Use of inverted triangular weight vectors in decomposition-based many-objective algorithms," Lecture Notes in Computer Science 10593: SEAL 2017, pp. 321-333, Springer, November, 2017.