[4P2-OS-17b] OS-17

[4P2-OS-17b-04] Dynamic Programming for the Indicator-based Subset Selection Problem with IGD, IGD⁺, R2, and NR2 in Bi-objective Optimization

〇Keisuke Korogi¹, Ryoji Tanabe¹ (1. Yokohama National University)

Keywords:Bi-objective Optimization, Subset Selection Problem, Dynamic Programming

In multi-objective optimization, quality indicators quantitatively evaluate the quality of non-dominated point sets. Representative quality indicators include IGD, IGD$^+$, R2, and NR2, where IGD and IGD$^+$ use a reference point set, and R2 and NR2 use a weight vector set. In $d$-objective optimization, given a point set $P \subset \mathbb{R}^d$ of size $n$ and a quality indicator $\mathcal{I}$, the indicator-based subset selection problem (ISSP) involves finding a point subset $S^* \subset P$ of size $k$ that optimizes $\mathcal{I}$. The ISSP is an NP-hard combinatorial optimization problem and appears in the context of evolutionary multi-objective optimization. This paper proposes a polynomial-time algorithm for the ISSP with IGD, IGD$^+$, R2, and NR2 in the case $d=2$ under practically reasonable assumptions. The results show that the proposed algorithm is much faster than the brute-force algorithm in terms of computation time.