ON THE BEHAVIOR AND IMPROVEMENTS OF THE HYPERVOLUME-BASED EMOAS

基于超体积的演化多目标优化算法的行为与改进

廖伟多

11849249

硕士

计算机科学与技术

Hisao Ishibuchi

2020-05-30

2020-07-08

哈尔滨工业大学

深圳

In the field of Evolutionary Multi-objective Optimization (EMO), the research on the hypervolume-based EMOAs become more and more active, for that they are intuitive and easy to understand. However, due to the heavy computation load of calculating the exact hypervolume values, some researchers have proposed the hypervolume approximation methods in order to reduce the computation load. Besides, it has been reported that the reference point specification in SMS-EMOA (i.e., one of the hypervolume-based EMOAs) strongly influences the distribution of the solution set on some special shapes of Pareto front of multi-objective optimization problems (MOPs). In this thesis, we further examine the effect of the reference point specification on both the exact hypervolume-based EMOAs (i.e., SMS-EMOA and FV-MOEA) and the hypervolume approximation-based EMOAs (i.e., HypE and R2HCA-EMOA). Not only 3-objective MOPs but also 5-, 8- and 10-objective many-objective optimization problems (MaOPs) are considered. Different shapes of Pareto front (i.e., linear against non-linear and triangular against inverted- triangular) are considered. In our experiments, we show the common behaviors of the hypervolume-based (and hypervolume approximation-based) EMOAs on various MOPs (and MaOPs). The results suggest that the reference point specification is an important issue for the hypervolume-based EMOA design. We also analyse the particular behavior of each EMOA. The poor diversity of solutions by HypE and the insensitivity of the position of the reference point in R2HCA-EMOA are shown and illustrated. Based on the behavioral experiments and analyses, some improvements for hypervolume-based EMOAs are made. First, we propose a weak convergence detection-based dynamic reference point specification mechanism, which shows good performance on both MOPs and MaOPs. Second, we proposed a new direction vector generation mechanism based on uniform mechanism for R2HCA-EMOA. By appropriately choosing the parameter in this mechanism, better performance is obtained than the original uniform mechanism and the state-of-the-art random mechanism (i.e., the mechanism used by the researcher who proposed R2HCA-EMOA).

在演化多目标优化（EMO）领域，基于超体积的演化多目标优化算法（EMOA）的研究变得越来越受到重视，因为它们非常直观并易于理解。但由于计算准确的超体积值的计算有很大的负荷，一些研究人员试图通过近似超体积的方法来降低计算上的负荷。此外，有研究表明对于SMS-EMOA 算法来说，参考点的设置与某些帕雷托前沿是特殊形状的多目标问题（MOP）上获取的解集分布密切相关。本文针对2 个基于超体积的演化多目标优化算法（即SMS-EMOA 和FV-MOEA）和2 个基于超体积近似的演化多目标优化算法（即HypE 和R2HCA-EMOA），实验分析了上述算法在各种不同的测试问题集，不同的参考点设置上的表现，并仔细观察了算法最后生成的解集分布与各指标的数据。我们不仅考虑到有3 个目标的多目标优化问题，还考虑了5 目标、8 目标、甚至是10 目标的超多目标优化问题（MaOP）。我们还考虑了优化问题的帕雷托前沿的不同形状（即非线性与线性和三角形与倒三角形）的影响。在实验中，我们展示了基于超体积(和超体积近似) 的演化多目标优化算法在上述优化问题上的共同行为。结果表明，参考点的设置是基于超体积的演化多目标优化算法设计上的一个重要课题。我们还分析了每个演化多目标优化算法的独有行为。HypE 算法较差的解集多样性以及R2HCA-EMOA算法对于参考点位置的不敏感性在实验中得到了充分的展示和解释。进一步，在实验和对其的分析之后，我们展示了如下算法的改进：第一种是基于弱收敛检测的动态参考点设置机制，优化了在算法中使用推荐参考点设置方法会降低超多目标优化问题的解的多样性的缺点，在多目标优化问题和超多目标优化问题上都表现出良好的性能；第二种是在R2HCA-EMOA 算法中，以均匀生成机制为基础的新的方向向量生成机制，降低了均匀生成机制对参考点位置过于敏感的缺点，通过适当地设置该机制中的参数，应用了这个机制的R2HCA-EMOA 算法获得了优于原先的均匀机制和先进的随机机制（即提出R2HCA-EMOA 的研究者所使用的机制）的性能。

EMO hypervolume approximation reference point specification algorithm improvements

演化多目标优化 超体积估计 参考点 算法改进

英语

联合培养

南方科技大学

Liao WD. ON THE BEHAVIOR AND IMPROVEMENTS OF THE HYPERVOLUME-BASED EMOAS[D]. 深圳. 哈尔滨工业大学,2020.