Paper Info
Title
Two-dimensional subset selection for hypervolume and epsilon-indicator
Abstract
The goal of bi-objective optimization is to find a small set of good compromise solutions. A common problem for bi-objective evolutionary algorithms is the following subset selection problem (SSP): Given n solutions P ⊂ R2 in the objective space, select k solutions P* from P that optimize an indicator function. In the hypervolume SSP we want to select k points P* that maximize the hypervolume indicator IHYP(P*, r) for some reference point r ∈ R2. Similarly, the ε-indicator SSP aims at selecting k~points P* that minimize the ε-indicator Iε(P*,R) for some reference set R ⊂ R2 of size m (which can be R=P). We first present a new algorithm for the hypervolume SSP with runtime O(n (k + log n)). Our second main result is a new algorithm for the ε-indicator SSP with runtime O(n log n + m log m). Both results improve the current state of the art runtimes by a factor of (nearly) $n$ and make the problems tractable for new applications. Preliminary experiments confirm that the theoretical results translate into substantial empirical runtime improvements.
Year
DOI
Venue
2014
10.1145/2576768.2598276
GECCO
Keywords
Field
DocType
measurement,general,epsilon indicator,hypervolume indicator,archiving algorithms,performance
Binary logarithm,Mathematical optimization,Evolutionary algorithm,Indicator function,Artificial intelligence,Time complexity,Small set,Machine learning,Mathematics
Conference
Citations 
PageRank 
References 
26
0.92
11
Authors
3
Name
Order
Citations
PageRank
Karl Bringmann142730.13
Tobias Friedrich245723.56
Patrick Klitzke3281.29