Exact hypervolume subset selection through incremental computations

The (environmental) selection procedure in Evolutionary Multiobjective Optimization Algorithms (EMOAs) can be interpreted as a subset selection problem, where the goal is to determine a subset of a given size that maximizes a quality indicator. The hypervolume indicator possesses desirable theoretical properties (e.g. monotonicity properties) that make it well-suited for indicator-based selection, and SMS-EMOA is a good example of this. In such a case, selection is viewed as a Hypervolume Subset Selection Problem (HSSP) that consists of selecting a subset of k points from a set of n points that maximizes the hypervolume indicator. However, apart from SMS-EMOA that considers the case of k=n−1, HSSP-based selection in EMOAs with more than 2 objectives and k<n−1 is solved with approximation (greedy) algorithms. Although a few exact algorithms exist to compute the HSSP for these cases, faster algorithms are required to make its integration in EMOAs practical. This paper proposes a new integer linear programming formulation of the HSSP, named LHSSP, that relies on a decomposition of the dominated region based on the multivariate Empirical Cumulative Distribution Function (ECDF). It is shown that, under this formulation, only part of the dominated region needs to be modeled to obtain an optimal solution to the HSSP. A new algorithm is proposed, named LayersC, which exploits this observation through incremental computations. Experimental studies with 3 objectives show that this algorithm considerably speeds up the computation of the HSSP in comparison to state-of-the-art algorithms, and makes HSSP-based selection in EMOAs amenable.