Hypervolume-Optimal $μ$-Distributions on Line/Plane-based Pareto Fronts in Three Dimensions
This work provides theoretical insights for researchers in evolutionary multi-objective optimization, but it is incremental as it extends known results from two to three dimensions.
The paper investigates the distribution of solutions that maximize hypervolume on line- and plane-based Pareto fronts in three dimensions, finding that uniform distributions are not always optimal and depend on the front's structure, with results showing local optimality for plane-based fronts under a specific selection scheme.
Hypervolume is widely used in the evolutionary multi-objective optimization (EMO) field to evaluate the quality of a solution set. For a solution set with $μ$ solutions on a Pareto front, a larger hypervolume means a better solution set. Investigating the distribution of the solution set with the largest hypervolume is an important topic in EMO, which is the so-called hypervolume optimal $μ$-distribution. Theoretical results have shown that the $μ$ solutions are uniformly distributed on a linear Pareto front in two dimensions. However, the $μ$ solutions are not always uniformly distributed on a single-line Pareto front in three dimensions. They are only uniform when the single-line Pareto front has one constant objective. In this paper, we further investigate the hypervolume optimal $μ$-distribution in three dimensions. We consider the line- and plane-based Pareto fronts. For the line-based Pareto fronts, we extend the single-line Pareto front to two-line and three-line Pareto fronts, where each line has one constant objective. For the plane-based Pareto fronts, the linear triangular and inverted triangular Pareto fronts are considered. First, we show that the $μ$ solutions are not always uniformly distributed on the line-based Pareto fronts. The uniformity depends on how the lines are combined. Then, we show that a uniform solution set on the plane-based Pareto front is not always optimal for hypervolume maximization. It is locally optimal with respect to a $(μ+1)$ selection scheme. Our results can help researchers in the community to better understand and utilize the hypervolume indicator.