[4P2-OS-17b] 数理最適化

[4P2-OS-17b-04] 2目的最適化におけるIGD, IGD⁺, R2, NR2を用いた指標に基づく部分集合選択問題に対する動的計画法

〇興呂木 啓祐¹、田邊 遼司¹ (1. 横浜国立大学)

キーワード：2目的最適化、部分集合選択問題、動的計画法

互いにトレードオフの関係にある複数の目的関数を同時に最小化する多目的最適化にて, 指標は得られた非劣点集合の質を定量的に評価する. 代表的な指標に参照点集合を用いる IGD と IGD$^+$, 重みベクトル集合を用いる R2 と NR2 がある. 指標に基づく部分集合選択問題 (indicator-based subset selection problem, ISSP) では, サイズ $n$ の点集合 $P \subset \mathbb{R}^d$ と指標 $\mathcal{I}$ が与えられたとき, $\mathcal{I}$ を最適化するサイズ $k$ の部分集合 $S^* \subset P$ を求める. ISSP は NP 困難な組合せ最適化問題で, 進化的多目的最適化の文脈に現れる. 本論文では $d=2$ の場合において, 実用上妥当な仮定のもとで, IGD, IGD$^+$, R2, NR2 を用いる ISSP を多項式時間で解くアルゴリズムを提案する. 提案手法は実行時間の観点で全探索を大幅に上回る性能を示した.