Efficient computation of two-dimensional solution sets maximizing the epsilon-indicator

The majority of empirical comparisons of multi-objective evolutionary algorithms (MOEAs) are performed on synthetic benchmark functions. One of the advantages of synthetic test functions is the a-priori knowledge of the optimal Pareto front. This allows measuring the proximity to the optimal front for the solution sets returned by the different MOEAs. Such a comparison is only meaningful if the cardinality of all solution sets is bounded by some fixed k. In order to compare MOEAs to the theoretical optimum achievable with k solutions, we determine best possible ε-indicator values achievable with solution sets of size k, up to an error of δ. We present a new algorithm with runtime O(k · log² (δ⁻¹)), which is an exponential improvement regarding the dependence on the error δ compared to all previous work. We show mathematical correctness of our algorithm and determine optimal solution sets for sets of cardinality k ∊ {2,3,4,5,10, 20,50,100,1000} for the well known test suits DTLZ, ZDT, WFG and LZ09 up to error δ = 10⁻²⁵.