Shenzhen Key Laboratory of Computational Intelligence, Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen, 518005, China
Department of Computer Science and Intelligent Systems, Osaka Prefecture University, Sakai, 5998531, Japan
Evol Comput. 2018 Fall;26(3):411-440. doi: 10.1162/evco_a_00226. Epub 2018 May 22.
The hypervolume indicator has frequently been used for comparing evolutionary multi-objective optimization (EMO) algorithms. A reference point is needed for hypervolume calculation. However, its specification has not been discussed in detail from a viewpoint of fair performance comparison. A slightly worse point than the nadir point is usually used for hypervolume calculation in the EMO community. In this paper, we propose a reference point specification method for fair performance comparison of EMO algorithms. First, we discuss the relation between the reference point specification and the optimal distribution of solutions for hypervolume maximization. It is demonstrated that the optimal distribution of solutions strongly depends on the location of the reference point when a multi-objective problem has an inverted triangular Pareto front. Next, we propose a reference point specification method based on theoretical discussions on the optimal distribution of solutions. The basic idea is to specify the reference point so that a set of well-distributed solutions over the entire linear Pareto front has a large hypervolume and all solutions in such a solution set have similar hypervolume contributions. Then, we examine whether the proposed method can appropriately specify the reference point through computational experiments on various test problems. Finally, we examine the usefulness of the proposed method in a hypervolume-based EMO algorithm. Our discussions and experimental results clearly show that a slightly worse point than the nadir point is not always appropriate for performance comparison of EMO algorithms.
超体积指标常用于比较进化多目标优化（EMO）算法。超体积计算需要参考点。然而，从公平性能比较的角度来看，其规范尚未详细讨论。在 EMO 社区中，通常使用比最劣点略差的点进行超体积计算。在本文中，我们提出了一种 EMO 算法公平性能比较的参考点规范方法。首先，我们讨论了参考点规范与超体积最大化的解最优分布之间的关系。当多目标问题具有倒三角型 Pareto 前沿时，证明了解的最优分布强烈依赖于参考点的位置。接下来，我们提出了一种基于对解最优分布的理论讨论的参考点规范方法。基本思想是指定参考点，以便在整个线性 Pareto 前沿上具有较大超体积的一组分布良好的解，并且此类解集内的所有解具有相似的超体积贡献。然后，我们通过对各种测试问题的计算实验来检查所提出的方法是否可以适当地指定参考点。最后，我们在基于超体积的 EMO 算法中检查了所提出方法的有用性。我们的讨论和实验结果清楚地表明，在 EMO 算法的性能比较中，比最劣点略差的点并不总是合适的。
