Speeding up Local Search for the Indicator-based Subset Selection Problem by a Candidate List Strategy

  • 2025-03-06 09:06:49
  • Keisuke Korogi, Ryoji Tanabe
  • 0

Abstract

In evolutionary multi-objective optimization, the indicator-based subsetselection problem involves finding a subset of points that maximizes a givenquality indicator. Local search is an effective approach for obtaining ahigh-quality subset in this problem. However, local search requires highcomputational cost, especially as the size of the point set and the number ofobjectives increase. To address this issue, this paper proposes a candidatelist strategy for local search in the indicator-based subset selection problem.In the proposed strategy, each point in a given point set has a candidate list.During search, each point is only eligible to swap with unselected points inits associated candidate list. This restriction drastically reduces the numberof swaps at each iteration of local search. We consider two types of candidatelists: nearest neighbor and random neighbor lists. This paper investigates theeffectiveness of the proposed candidate list strategy on various Pareto fronts.The results show that the proposed strategy with the nearest neighbor list cansignificantly speed up local search on continuous Pareto fronts withoutsignificantly compromising the subset quality. The results also show that thesequential use of the two lists can address the discontinuity of Pareto fronts.

 

Quick Read (beta)

loading the full paper ...