Numerical Analysis on Optimal Distributions of Solutions for Hypervolume Maximization

In the evolutionary multi-objective optimization (EMO) community, hypervolume (HV) has been frequently used to evaluate the performance of EMO algorithms. The HV is a Pareto compliant indicator which can simultaneously evaluate both the convergence of solutions to the Pareto front and their diversity. No other Pareto compliant indicator is known. In the EMO community, it is implicitly assumed that a set of uniformly distributed solutions over the entire Pareto front including its boundary has the best HV value. This is true for a linear Pareto front of a two-objective problem when a reference point for HV calculation is not too close to the Pareto front. In this paper, we numerically examine this issue for three-objective problems. We perform computational experiments to search for the optimal distribution of a small number of solutions for HV maximization. This is to visually explain the characteristic features of the optimal distribution. Our experimental results clearly show that a set of uniformly distributed solutions is not always optimal for HV maximization. It is also shown that the optimal distribution for HV maximization is often inconsistent with our intuition. For example, a set of ten solutions systematically generated by Das and Dennis method is not optimal.