高级检索

  • ISSN 1006-3080
  • CN 31-1691/TQ
English
downloadPDF
引用本文:
shu
Citation:
shu

一种基于超体积指标的多目标进化算法

  • 华东理工大学化工过程先进控制和优化技术教育部重点实验室，上海 200237

    • 作者简介: 王学武（1972-），男，陕西合阳人，副教授，博士，主要研究方向为智能优化算法、焊接机器人智能化技术、焊接自动化、系统建模、控制与优化。E-mail：wangxuew@ecust.edu.cn;

  • 中图分类号: TP301

Hypervolume-Based Multi-Objective Evolutionary Algorithm

  • Key Laboratory of Advanced Control and Optimization for Chemical Processes, Ministry of Education, East China University of Science and Technology, Shanghai 200237, China

  • CLC number: TP301

  • 摘要: 基于超体积指标的进化算法能够有效地解决多目标优化问题，可以获得收敛性和分布性均较好的解集，但计算复杂度高、程序运行效率低。针对二维和三维的多目标优化问题，提出了一种基于超体积指标的多目标进化算法（MOEA-HV）。利用精确计算种群中个体的独立贡献超体积来指导种群进化，在基于指标的进化算法(IBEA)前对所有种群个体进行非支配排序，提前删除被支配的个体，从而减少个体独立贡献超体积的计算量来提升运行效率，同时与NSGA-Ⅲ算法相结合来优化算法的分布性。实验结果表明，MOEA-HV算法的运行效率更高，且能够获得较好的收敛性和分布性。
    Abstract: Hypervolume-based evolutionary algorithms can effectively solve the multi-objective optimization problem and obtain promising solution sets with fast convergence and uniform distribution. However, this kind of algorithms have higher computational complexity and lower programming efficiency. Aiming at the two-dimensional and three-dimensional multi-objective optimization problems, this paper proposes a hypervolume-based multi-objective evolutionary algorithm (MOEA-HV) so that the individuals’ exclusive hypervolume contributions can be accurately calculated to guide the evolution of the whole population. Before the indicator-based evolutionary algorithm(IBEA) being utilized, the proposed algorithm employs non-dominated sorting among all individuals to delete dominated individuals so that the amount of calculation of the individuals’ exclusive hypervolume contributions can be reduced and the operational efficiency can be improved. Meanwhile, other strategies in NSGA-Ⅲ are utilized to optimize the distribution of the proposed algorithm. It is shown via the experiment results that the proposed MOEA-HV has higher efficiency while maintaining the trade-off between the fast convergence and the uniform distribution.

  • 图 FIG. 486.  FIG. 486.

    Figure FIG. 486..  FIG. 486.

    下载: 全尺寸图片 幻灯片

    图 1  在非支配关系下BHV > AHV > 0

    Figure 1.  BHV > AHV > 0 in non-dominated relationship

    下载: 全尺寸图片 幻灯片

    图 2  在支配关系下BHV > AHV = 0

    Figure 2.  BHV > AHV = 0 in dominated relationship

    下载: 全尺寸图片 幻灯片

    图 3  非支配排序后的解集

    Figure 3.  Solution set after non-dominated sort

    下载: 全尺寸图片 幻灯片

    图 4  乱序下的解集

    Figure 4.  Solution set in chaos

    下载: 全尺寸图片 幻灯片

    图 5  三维情况下个体独立贡献超体积的计算

    Figure 5.  Calculation of the individuals’ exclusive hypervolume contributions in three dimension

    下载: 全尺寸图片 幻灯片

    图 6  MOEA-HV算法在部分测试函数上的Pareto前沿面

    Figure 6.  Pareto fronts of MOEA-HV on some test functions

    下载: 全尺寸图片 幻灯片

    图 7  不同参数$k$对IBEA运行时间、IGDm值和HVm值的影响

    Figure 7.  Influence of different $k$ on runtime, IGDm and HVm of IBEA

    下载: 全尺寸图片 幻灯片

    图 8  非支配排序对IBEA运行时间均值、IGDm值和HVm值的影响

    Figure 8.  Influence of non-dominated sort on runtime, IGDm and HVm of IBEA

    下载: 全尺寸图片 幻灯片

    图 9  NSGA-Ⅲ对IBEA运行时间、IGDm值和HVm值的影响

    Figure 9.  Influence of NSGA-Ⅲ on runtime, IGDm and HVm of NSGA-Ⅲ

    下载: 全尺寸图片 幻灯片

    表 1  各算法运行时间均值

    Table 1.  Mean runtime of each algorithm

    FunctionRuntime/s
    IBEAHypEMO-CMA-ESSMS-EMOANSGA-ⅢMOEA-HV
    ZDT15.805 92.382 7×1022.505 1×1011.037 1×1022.294 83.565 1
    ZDT25.677 52.093 2×1022.030 5×1011.037 1×1022.562 53.794 6
    ZDT36.307 82.180 1×1022.114 8×1011.037 1×1022.476 03.664 3
    ZDT45.921 34.812 4×1025.670 2×1013.082 6×1022.109 93.363 5
    ZDT55.803 11.219 2×1024.012 4×1019.799 1×1012.432 53.764 6
    ZDT66.341 62.758 3×1022.182 9×1011.056 9×1022.132 23.442 4
    DTLZ16.750 31.530 4×1032.123 8×1011.400 5×1022.254 03.193 0
    DTLZ26.557 42.574 3×1032.925 0×1011.764 9×1032.366 43.392 4
    DTLZ36.540 37.428 3×1022.852 4×1017.409 8×1022.315 83.418 9
    DTLZ46.984 51.607 4×1032.712 1×1011.798 2×1033.156 73.647 5
    DTLZ58.936 01.952 2×1033.120 9×1019.536 4×1023.634 64.783 0
    DTLZ67.703 33.425 2×1032.469 5×1019.919 2×1023.865 85.082 8
    DTLZ76.612 41.945 6×1032.041 4×1011.591 3×1032.695 83.815 0
    下载: 导出CSV

    表 2  各算法IGD均值

    Table 2.  Mean IGD of each algorithm

    FunctionIGDm
    IBEAHypEMO-CMA-ESSMS-EMOANSGA-ⅢMOEA-HV
    ZDT14.587 6×10−32.353 4×10−16.216 7×10−33.651 3×10−33.887 9×10−33.887 9×10−3
    ZDT29.304 7×10−32.217 0×10−16.057 1×10−34.320 3×10−33.807 7×10−33.807 2×10−3
    ZDT36.669 7×10−21.988 6×10−18.550 1×10−32.675 5×10−21.192 7×10−22.914 5×10−2
    ZDT41.923 0×10−24.601 2×10−18.874 13.627 3×10−34.112 8×10−34.192 9×10−3
    ZDT52.330 01.782 93.374 9×10−14.727 1×10−14.873 8×10−15.749 2×10−1
    ZDT65.027 5×10−33.070 2×10−34.025 2×10−32.986 3×10−33.002 4×10−33.001 5×10−3
    DTLZ11.705 1×10−11.338 3×10−18.173 33.179 1×10−22.062 4×10−22.061 9×10−2
    DTLZ28.041 8×10−21.337 4×10−11.122 5×10−17.753 1×10−25.447 0×10−25.446 8×10−2
    DTLZ34.726 8×10−13.652 5×10−15.184 0×1018.768 3×10−25.782 4×10−25.777 5×10−2
    DTLZ48.088 1×10−24.716 6×10−11.313 8×10−17.801 5×10−22.897 3×10−15.449 7×10−2
    DTLZ51.707 6×10−21.513 4×10−21.125 8×10−21.609 3×10−21.306 4×10−21.289 6×10−2
    DTLZ62.312 1×10−22.176 0×10−15.023 0×10−21.824 3×10−21.977 2×10−21.894 5×10−2
    DTLZ71.487 3×10−16.986 2×10−11.244 8×10−17.642 8×10−27.594 8×10−27.685 3×10−2
    下载: 导出CSV

    表 3  各算法HV均值

    Table 3.  Mean HV of each algorithm

    FunctionHVm
    IBEAHypEMO-CMA-ESSMS-EMOANSGA-ⅢMOEA-HV
    ZDT17.199 3×10−15.832 3×10−17.173 8×10−17.207 6×10−17.202 9×10−17.203 0×10−1
    ZDT24.434 7×10−12.409 5×10−14.423 6×10−14.453 3×10−14.450 2×10−14.450 3×10−1
    ZDT36.872 6×10−17.219 1×10−15.819 7×10−16.411 1×10−16.015 1×10−16.398 9×10−1
    ZDT47.049 8×10−16.923 3×10−1−7.207 2×10−17.197 1×10−17.190 0×10−1
    ZDT58.170 4×10−18.027 8×10−19.711 4×10−18.200 6×10−18.312 9×10−18.265 4×10−1
    ZDT63.871 2×10−13.889 2×10−13.879 8×10−13.890 0×10−13.889 3×10−13.889 5×10−1
    DTLZ14.637 1×10−16.104 9×10−1−8.149 5×10−18.408 9×10−18.409 6×10−1
    DTLZ25.580 1×10−15.363 0×10−14.208 6×10−15.484 5×10−15.595 8×10−15.596 0×10−1
    DTLZ32.441 0×10−12.736 3×10−1−5.193 2×10−15.403 4×10−15.416 5×10−1
    DTLZ45.574 5×10−13.532 0×10−14.828 1×10−15.481 2×10−14.469 6×10−15.594 2×10−1
    DTLZ51.986 6×10−11.960 3×10−11.943 1×10−11.949 8×10−11.932 6×10−11.938 4×10−1
    DTLZ61.970 0×10−11.102 8×10−11.776 4×10−11.950 7×10−11.899 6×10−11.908 9×10−1
    DTLZ72.695 3×10−12.056 7×10−12.513 7×10−12.725 3×10−12.694 7×10−12.705 0×10−1
    下载: 导出CSV
  • [1] 朱永胜, 王杰, 瞿博阳, 等. 采用基于分解的多目标进化算法的电力环境经济调度[J]. 电网技术, 2014, 38(6): 1 577-1 584.
    [2] MURUGESWARI R, RADHAKRISHNAN S, DEVARAJ D. A multi-objective evolutionary algorithm based QoS routing in wireless mesh networks[J]. Applied Soft Computing, 2016, 40: 517-525. doi: 10.1016/j.asoc.2015.12.007
    [3] 王珊珊, 杜文莉, 陈旭, 等. 基于约束骨干粒子群算法的化工过程动态多目标优化[J]. 华东理工大学学报(自然科学版), 2014, 40(4): 449-457. doi: 10.3969/j.issn.1006-3080.2014.04.008
    [4] RYU N, LIM S, MIN S, et al. Multi-objective optimization of magnetic actuator design using adaptive weight determination scheme[J]. IEEE Transactions on Magnetics, 2017, 53(6): 1-4.
    [5] 陈志旺, 白锌, 杨七, 等. 区间多目标优化中决策空间约束、支配及同序解筛选策略[J]. 自动化学报, 2015, 41(12): 2 115-2 124.
    [6] 郑金华, 李珂, 李密青, 等. 一种基于Hypervolume指标的自适应邻域多目标进化算法[J]. 计算机研究与发展, 2012, 49(2): 312-326.
    [7] 王学武, 夏泽龙, 顾幸生. 基于DMOEA/D-ET算法的焊接机器人多目标路径规划[J]. 华南理工大学学报(自然科学版), 2019, 47(4): 99-106.
    [8] MAC T T, COPOT C, TRAN D T, et al. A hierarchical global path planning approach for mobile robots based on multi-objective particle swarm optimization[J]. Applied Soft Computing, 2017, 59: 68-76. doi: 10.1016/j.asoc.2017.05.012
    [9] BADER J, ZITZLER E. HypE: An algorithm for fast hypervolume-based many-objective optimization[J]. Evolutionary Computation, 2011, 19(1): 45-76. doi: 10.1162/EVCO_a_00009
    [10] ZHOU X, GUO P, CHEN C L P. An algorithm for calculating the hypervolume contribution of a set[C]// World Automation Congress 2012. Mexico: IEEE, 2012: 439-443.
    [11] ZITZLER E, SIMON K. Indicator-based selection in multiobjective search[C]// International Conference on Parallel Problem Solving from Nature. Berlin, Heidelberg: Springer, 2004: 832-842.
    [12] IGEL C, HANSEN N, ROTH S. Covariance matrix adaptation for multi-objective optimization[J]. Evolutionary Computation, 2007, 15(1): 1-28. doi: 10.1162/evco.2007.15.1.1
    [13] BEUME N, NAUJOKS B, EMMERICH M. SMS-EMOA: Multiobjective selection based on dominated hypervolume[J]. European Journal of Operational Research, 2007, 181(3): 1 653-1 669. doi: 10.1016/j.ejor.2006.08.008
    [14] HERNÁNDEZ V A S, SCHUTZE O, WANG H, et al. The set-based hypervolume newton method for bi-objective optimization[J]. IEEE Transactions on Cybernetics, 2020, 50(5): 2 186-2 196.
    [15] DENG J, ZHANG Q. Approximating hypervolume and hypervolume contributions using polar coordinate[J]. IEEE Transactions on Evolutionary Computation, 2019, 23(5): 913-918.
    [16] SHANG K, ISHIBUCHI H, NI X. R2-based hypervolume contribution approximation[J]. IEEE Transactions on Evolutionary Computation, 2020, 24(1): 185-192.
    [17] WHILE L, HINGSTON P, BARONE L, et al. A faster algorithm for calculating hypervolume[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(1): 29-38. doi: 10.1109/TEVC.2005.851275
    [18] BRADSTREET L, WHILE L, BARONE L. A fast many-objective hypervolume algorithm using iterated incremental calculations[C]// 2010 IEEE Congress on Evolutionary Computation. Spain: IEEE, 2010: 1-8.
    [19] FONSECA C M, PAQUETE L, LOPEZ-IBANEZ M. An improved dimension-sweep algorithm for the hypervolume indicator[C]// 2006 IEEE International Conference on Evolutionary Computation. Canada: IEEE, 2006: 1 157-1 163.
    [20] WHILE L, BRADSTREET L, BARONE L. A fast way of calculating exact hypervolumes[J]. IEEE Transactions on Evolutionary Computation, 2012, 16(1): 86-95. doi: 10.1109/TEVC.2010.2077298
    [21] WHILE L, BRADSTREET L. Applying the WFG algorithm to calculate incremental hypervolumes[C]// 2012 IEEE Congress on Evolutionary Computation. Australia: IEEE, 2012: 1-8.
    [22] OVERMARS M H, YAP C K. New upper bounds in Klee’s measure problem[C]//Proceedings 1988 29th Annual Symposium on Foundations of Computer Science. USA: IEEE, 1988: 550-556.
    [23] GAZIT H. New upper bounds in Klee’s measure problem[J]. SIAM Journal on Computing, 1991, 20(6): 1 034-1 045. doi: 10.1137/0220065
    [24] BEUME N. S-metric calculation by considering dominated hypervolume as Klee’s measure problem[J]. Evolutionary Computation, 2009, 17(4): 477-492. doi: 10.1162/evco.2009.17.4.17402
    [25] BEUME N, RUDOLPH G. Faster S-metric calculation by considering dominated hypervolume as Klee’s measure problem[C]// 2nd IASTED International Conference on Computational Intelligence, CI 2006. USA: ACTA Press, 2006: 231-236.
    [26] GUERREIRO A P, FONSECA C M, EMMERICH M T. A fast dimension sweep algorithm for the hypervolume indicator in four dimensions[C]// 24th Canadian Conference on Computational Geometry, CCCG 2012. Canada: Canadian Conference on Computational Geometry, 2012: 77-82.
    [27] WATANABE T, TATSUKAWA T, OYAMA A. On the fast hypervolume calculation method[C]// 2015 IEEE Congress on Evolutionary Computation (CEC). Japan: IEEE, 2015: 965-969.
    [28] RUSSO L M S, FRANCISCO A P. Quick hypervolume[J]. IEEE Transactions on Evolutionary Computation, 2012, 18(4): 481-502.
    [29] LACOUR R, KLAMROTH K, FONSECA C M. A box decomposition algorithm to compute the hypervolume indicator[J]. Computers & Operations Research, 2017, 79: 347-360.
    [30] JIANG S, ZHANG J, ONG Y S, et al. A simple and fast hypervolume indicator-based multiobjective evolutionary algorithm[J]. IEEE Transactions on Cybernetics, 2015, 45(10): 2 202-2 213. doi: 10.1109/TCYB.2014.2367526
    [31] 郑金华, 邹娟. 多目标进化优化[M]. 北京:科学出版社, 2018:175-176.
    [32] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197. doi: 10.1109/4235.996017
    [33] DEB K, JAIN H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach: Part I. Solving problems with box constraints[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(4): 577-601. doi: 10.1109/TEVC.2013.2281535
    [34] YE T, RAN C, ZHANG X, et al. PlatEMO: A matlab platform for evolutionary multi-objective optimization[Educational Forum][J]. IEEE Computational Intelligence Magazine, 2017, 12(4): 73-87.
    [35] BOSMAN P A N, THIERENS D. The balance between proximity and diversity in multiobjective evolutionary algorithms[J]. IEEE Transactions on Evolutionary Computation, 2003, 7(2): 174-188. doi: 10.1109/TEVC.2003.810761
    [36] ZITZLER E, THIELE L. Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach[J]. IEEE Transactions on Evolutionary Computation, 1999, 3(4): 257-271. doi: 10.1109/4235.797969
  • 加载中
WeChat 点击查看大图
图(10)表(3)
计量
  • 文章访问数:  3139
  • HTML全文浏览量:  1719
  • PDF下载量:  100
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-09-17
  • 网络出版日期:  2019-12-26
  • 刊出日期:  2020-12-30

一种基于超体积指标的多目标进化算法

    作者简介:王学武（1972-），男，陕西合阳人，副教授，博士，主要研究方向为智能优化算法、焊接机器人智能化技术、焊接自动化、系统建模、控制与优化。E-mail：wangxuew@ecust.edu.cn
  • 华东理工大学化工过程先进控制和优化技术教育部重点实验室，上海 200237
  • 收稿日期: 2019-09-17
  • 网络出版日期: 2020-12-30

摘要: 基于超体积指标的进化算法能够有效地解决多目标优化问题，可以获得收敛性和分布性均较好的解集，但计算复杂度高、程序运行效率低。针对二维和三维的多目标优化问题，提出了一种基于超体积指标的多目标进化算法（MOEA-HV）。利用精确计算种群中个体的独立贡献超体积来指导种群进化，在基于指标的进化算法(IBEA)前对所有种群个体进行非支配排序，提前删除被支配的个体，从而减少个体独立贡献超体积的计算量来提升运行效率，同时与NSGA-Ⅲ算法相结合来优化算法的分布性。实验结果表明，MOEA-HV算法的运行效率更高，且能够获得较好的收敛性和分布性。

English Abstract

    全文HTML

  • 多目标优化问题通常是指具有多个目标同时具有多个最优解的一类问题，解决这类问题需要同时对相互作用、相互冲突的多个目标进行优化和综合考虑，因此多目标优化已经被广泛应用于电力调度[1]、网络优化[2]、化工过程[3]、结构设计[4]、数据挖掘[5]等领域。

    以焊接机器人路径规划问题为例，衡量焊接路径好坏的指标往往不止一个，通常有路径长度、焊接用时、能量消耗、焊接变形量等，因此可将焊接机器人路径规划问题看作一个多目标优化问题。进化算法是一类模拟生物自然选择与自然进化的随机搜索算法[6]，通过种群迭代来协调局部与全局搜索能力，从而获得收敛性和分布性均较好的解集，能够有效地解决多目标优化问题。王学武等[7]通过将基于分解的多目标进化算法与自适应邻域相结合，以焊接路径长度和能量消耗为优化目标，较好地解决了弧焊机器人路径规划问题。Mac等[8]基于Pareto支配关系提出了改进的多目标粒子群优化算法，以焊接路径长度和路径平滑度为优化目标求解移动机器人路径规划问题，在不同种类的环境中均得到了较好的仿真结果。

    多目标优化算法是解决多目标优化问题的核心，关键在于如何设计算法以获得较好的综合性能，而超体积（Hypervolume，HV）指标是唯一一个在Pareto支配关系上严格单调的度量指标[9]，超体积值越大，对应算法的综合性能越好，因此超体积可以作为归档策略、多样性机制或选择标准来指导算法搜索[10]，从而考虑将评价算法性能的超体积指标整合到算法中来解决多目标优化问题[11]。Bader等[9]提出的HypE算法通过蒙特卡洛模拟来近似精确的超体积，能够大大降低算法的时间复杂度、平衡估计的准确性和算法的计算复杂度。Igel等[12]提出的MO-CMA-ES算法将具有协方差矩阵自适应的精英进化策略与基于非支配排序的多目标选择相结合，实验结果表明基于超体积贡献的s-MO-CMA比基于拥挤距离的c-MO-CMA具有更好的性能。Beume等[13]提出的SMS-EMOA算法采用在每次迭代中只产生和淘汰一个个体的稳态进化策略，在二维和三维的测试问题上表现出较好的综合性能。

    上述基于超体积指标的算法具有计算复杂度高、程序运行效率低的缺点，因此选择有效计算超体积的方法来提升算法的运行效率并且获得较好的综合性能对基于超体积指标的进化算法来说具有重要意义。

    • 1.   相关工作

    • 计算超体积的方法主要分为两类：精确计算和近似估计，这两类方法的共同目的均是要平衡运行效率和计算精度。在近似估计超体积的方法中，Hernández等[14]提出了超体积牛顿方法（HNM），将其与SMS-EMOA结合能够快速有效地解决连续双目标优化问题。Deng等[15]指出精确计算超体积是一个NP-难问题，提出通过极坐标变换降维，与蒙特卡洛模拟方法相比，该方法在对随机点进行排序时更加稳定。Shang等[16]提出了一种基于R2指标的R2-HVC估计方法，通过使用不同的线段来近似超体积贡献值，提高了计算效率和估计精度。在精确计算超体积的方法中，While等[17]提出了将目标进行切片的HSO算法，能够有效计算超体积，在此基础上改进的还有SHSO*[10]、IIHSO[18]和FPL[19]算法。While等[20]通过计算解集上每个点的独立超体积进行迭代，生成许多的被支配点来加速计算，降低了计算复杂度，并通过将IHSO算法中的最佳优先级排队机制和WFG算法中生成许多被支配点来加速计算的方式进行结合，提出了IWFG[21]算法。文献[22-24]将超体积计算问题转换为Klee的度量问题，其最坏情况的时间复杂度为$O\left(n\lg n + \dfrac{{nd}}{2}\lg n\right)$或$O\left(n\lg n + \dfrac{{nd}}{2}\right)$[25]，在四维的超体积计算中时间复杂度降低为$O\left(\dfrac{{nd}}{2}\right)$[26]。

      基于分而治之的思想，FHV算法[27]能够并行计算超体积，处理高维多目标优化问题时非常有效。QHV算法[28]能够降低时间和空间复杂度，获得了较好的算法性能。Lacour等[29]通过将支配区域划分为超矩形来计算超体积指标，提出了超体积盒子分解算法（HBDA），并提出了一种非增量方法和一种增量方法，其时间复杂度分别为$O({n^{\left[\tfrac{{p - 1}}{2}\right] + 1}})$和$O({n^{\left[\tfrac{p}{2}\right] + 1}})$。Jiang等[30]通过删除不相关的解和转移超体积贡献值提出了FV-MOEA算法，大大减少了精确计算超体积的计算量。

      通过超体积指标来指导算法搜索，其HV性能指标普遍较高，但仍然存在运行效率低、分布性不好的缺点，而基于参考点的NSGA-Ⅲ搜索的解分布均匀，因此本文提出了一种基于超体积指标的多目标进化算法（MOEA-HV），针对二维和三维的多目标优化问题，采用分治递归思想的切片法来精确计算超体积，同时在基于指标的进化算法（IBEA）[11]前对所有种群个体进行非支配排序提前删除被支配的个体，从而减少个体独立贡献超体积的计算量，提升运行效率，通过与NSGA-Ⅲ结合来优化算法的分布性。

    2.   MOEA-HV算法

      2.1.   IBEA

    • IBEA主要包括两个部分：一是将超体积指标与适应度评价函数进行结合，计算种群中每个个体的适应度值，公式如下：

      其中：$I(\{ {x^2}\} ,\{ {x^1}\} )$表示计算个体的独立贡献超体积；$k$是一个大于0的比例缩放因子[31]，用于淘汰适应度值小的个体，即在原种群中删除对总的超体积的独立贡献最小的个体，如图1和图2所示（以二维为例）。

      图  1  在非支配关系下BHV > AHV > 0

      Figure 1.  BHV > AHV > 0 in non-dominated relationship

      图  2  在支配关系下BHV > AHV = 0

      Figure 2.  BHV > AHV = 0 in dominated relationship

      在图1、2中，A和B均表示一个个体，H表示计算超体积的参考点，阴影部分AHV和BHV表示个体A和B的独立支配区域面积，其中图1表示个体A和B在互不支配时的独立支配区域面积，图2表示个体B支配个体A时的独立支配区域面积，均有BHV>AHV，因此不论是根据个体的支配关系还是个体对总的超体积的独立贡献，更应该淘汰个体A。事实上，超体积指标在Pareto支配关系上是严格单调的，因此能够作为指导种群进化的有效度量指标[9]。

      重新计算种群中每个个体的适应度值，其更新公式为

      通过二元锦标选择父代进行交配从而产生新的个体，与原种群一起构成新的种群，继续进行迭代。

      IBEA通过将超体积指标和适应度评价方法相结合来指导种群进化，与基于超体积指标的其他典型算法HypE[9]、MO-CMA-ES[12]和SMS-EMOA[13]相比，在保证综合性能最优或次优的前提下，其运行效率是最高的，这也是本文选择IBEA作为算法基础框架的主要原因。

      • 2.2.   NSGA-Ⅲ

    • NSGA-II[32]是基于拥挤度距离建立偏序集来筛选个体指导种群进化，能够有效处理多目标优化问题。NSGA-Ⅲ[33]在NSGA-II的基础上通过使用一组预定义的参考点在临界层选择个体来确保种群良好的分布性，该算法在最坏情况下的时间复杂度为O（N2lgM-2N）或O（N2M）。

      基于参考点方法的NSGA-Ⅲ能够维持种群个体分布的多样性和均匀性，因此将NSGA-Ⅲ整合到IBEA框架中，获得的解能够同时具有良好的收敛性和分布性，使得程序的运行效率更高，同时解也能够均匀分布在整个Pareto前沿面。有两种方法可以将NSGA-Ⅲ和IBEA结合：一是在IBEA运行完成的基础上再运行NSGA-Ⅲ，也就是IBEA先迭代更新完成，获得收敛性较好的种群，然后将获得的种群作为NSGA-Ⅲ的初始种群继续进行迭代优化，以期获得分布性也较好的解；二是先运行NSGA-Ⅲ，然后将获得的分布均匀的种群作为IBEA的初始种群、利用超体积指标指导种群进化来继续对选择过程增压，以期获得综合性能均较好的解。

      本文选择第1种结合方式。因为在基于超体积指标的算法中，IBEA的收敛速度较快，分布性较差，因此重点在于改善IBEA的分布性，在IBEA运行的基础上再运行NSGA-Ⅲ能够实现此目的。而对于第2种方式，先利用NSGA-Ⅲ获得分布性较好的解，然后在此基础上通过IBEA继续进行个体的迭代选择，很可能会破坏之前已经均匀分布的解，反而降低了算法的综合性能。

      • 2.3.   非支配排序

    • IBEA通过计算种群中每个个体的独立贡献超体积及其适应度值淘汰适应度值最小的个体，并依次进行迭代，使得算法最终能获得一个较好的解集，但计算复杂度高，主要原因在于IBEA计算了每个个体的独立贡献超体积。本文的改进之处是先通过Pareto支配关系对个体进行筛选，得到一组非支配解集，然后计算非支配解集中每个个体的独立贡献超体积，淘汰贡献值最小的个体并依次迭代。通过提前删除质量不好的个体而避免计算其独立贡献超体积，能够有效节约个体的超体积计算量，而且减小了计算复杂度，提升运行效率。以二维为例，图3示出了非支配排序后的解集分布情况，很容易计算出每个个体的独立贡献超体积（即面积）。图4示出了经过初始化后产生的种群个体分布情况，处于乱序状态，此时要淘汰独立贡献超体积最小的个体仍然需要计算每个个体的贡献值，浪费了部分计算资源，因此本文考虑在IBEA前引入非支配排序来提升算法的运行效率。

      图  3  非支配排序后的解集

      Figure 3.  Solution set after non-dominated sort

      图  4  乱序下的解集

      Figure 4.  Solution set in chaos

      三维的非支配排序情况与二维类似，但个体独立贡献超体积的计算更加复杂。本文采用切片法来精确计算三维个体的独立贡献超体积，基本思想是计算整个解集的超体积与去除该个体后的超体积之差。具体来说，先利用某一维度（本文选择第一维度）对整个超体积进行切片以达到降维的目的，通过计算切割面的面积与切片在第一维度上的深度的乘积得到整个解集的超体积，然后用同样的方法计算去除该个体后的超体积，两个超体积之差即为三维情况下的个体独立贡献超体积（即体积）。假设解集中有4个个体P1、P2、P3、P4，图5（a）、（b）、（c）和（d）分别示出了整个解集的超体积、经过切片后的子超体积、个体P1和P2的独立贡献超体积。通过精确计算每个个体的独立贡献超体积，淘汰独立贡献超体积最小的个体来指导种群进化。

      图  5  三维情况下个体独立贡献超体积的计算

      Figure 5.  Calculation of the individuals’ exclusive hypervolume contributions in three dimension

      • 2.4.   MOEA-HV算法步骤

    • 通过精确计算种群中个体的独立贡献超体积来指导种群进化，在IBEA前对所有种群个体进行非支配排序并与NSGA-Ⅲ结合，共同组成了MOEA-HV算法。算法步骤如下：

      输入：种群数量、组合迭代次数、参数k、参考点

      输出：Pareto前沿面

      （1）初始化。获得初始种群，并生成参考点。

      （2）非支配排序。对种群进行非支配排序，提前删除被支配的个体，减少超体积的计算量。

      （3）计算非支配排序后种群中每个个体的适应度值，并淘汰适应度值最小的个体。

      （4）选择、交叉、变异，产生新的种群。利用二元锦标法选择最优的两个个体到交配池进行交叉变异，产生新的个体与原种群合并为新的种群。

      （5）嵌入NSGA-Ⅲ。将新得到的种群作为NSGA-Ⅲ的初始种群继续进行迭代，满足迭代要求则停止迭代并输出。

    3.   实验结果及分析

    • 仿真实验使用Lenovo-PC计算机，处理器为Intel(R) Core(TM) i5-4200M CPU @ 2.50 GHz，内存为4.00 GB，操作系统为基于x64处理器的64位操作系统Windows 8.1中文版，软件版本为MATLAB R2018a，程序运行均在PlatEMO[34]平台实现。

      为检验MOEA-HV的运行效率和综合性能，与其他典型的基于超体积的算法IBEA[11]、HypE[9]、MO-CMA-ES[12]、SMS-EMOA[13]以及NSGA-Ⅲ[33]进行对比实验，选择2个目标的ZDT和3个目标的DTLZ系列中具有代表性的典型测试函数ZDT1~ZDT6和DTLZ1~DTLZ7进行实验，通过运行时间评价算法的运行效率，通过IGD[35]和HV[36]指标评价算法的综合性能，其中IGD值越小说明算法的综合性能越好，HV值越大说明算法的综合性能越好，这两个评价指标都能够综合评价算法的收敛性和分布性。设置种群大小为100，迭代次数为500，所有算法在相同条件下独立运行10次，k=0.03。表1~3分别列出了各算法的运行时间、IGD均值（IGDm）和HV均值（HVm），其中黑体数字为最优值。图6示出了MOEA-HV算法在测试函数ZDT2、ZDT3、DTLZ2和DTLZ7上的Pareto前沿面。

      FunctionRuntime/s
      IBEAHypEMO-CMA-ESSMS-EMOANSGA-ⅢMOEA-HV
      ZDT15.805 92.382 7×1022.505 1×1011.037 1×1022.294 83.565 1
      ZDT25.677 52.093 2×1022.030 5×1011.037 1×1022.562 53.794 6
      ZDT36.307 82.180 1×1022.114 8×1011.037 1×1022.476 03.664 3
      ZDT45.921 34.812 4×1025.670 2×1013.082 6×1022.109 93.363 5
      ZDT55.803 11.219 2×1024.012 4×1019.799 1×1012.432 53.764 6
      ZDT66.341 62.758 3×1022.182 9×1011.056 9×1022.132 23.442 4
      DTLZ16.750 31.530 4×1032.123 8×1011.400 5×1022.254 03.193 0
      DTLZ26.557 42.574 3×1032.925 0×1011.764 9×1032.366 43.392 4
      DTLZ36.540 37.428 3×1022.852 4×1017.409 8×1022.315 83.418 9
      DTLZ46.984 51.607 4×1032.712 1×1011.798 2×1033.156 73.647 5
      DTLZ58.936 01.952 2×1033.120 9×1019.536 4×1023.634 64.783 0
      DTLZ67.703 33.425 2×1032.469 5×1019.919 2×1023.865 85.082 8
      DTLZ76.612 41.945 6×1032.041 4×1011.591 3×1032.695 83.815 0

      表 1  各算法运行时间均值

      Table 1.  Mean runtime of each algorithm

      FunctionIGDm
      IBEAHypEMO-CMA-ESSMS-EMOANSGA-ⅢMOEA-HV
      ZDT14.587 6×10−32.353 4×10−16.216 7×10−33.651 3×10−33.887 9×10−33.887 9×10−3
      ZDT29.304 7×10−32.217 0×10−16.057 1×10−34.320 3×10−33.807 7×10−33.807 2×10−3
      ZDT36.669 7×10−21.988 6×10−18.550 1×10−32.675 5×10−21.192 7×10−22.914 5×10−2
      ZDT41.923 0×10−24.601 2×10−18.874 13.627 3×10−34.112 8×10−34.192 9×10−3
      ZDT52.330 01.782 93.374 9×10−14.727 1×10−14.873 8×10−15.749 2×10−1
      ZDT65.027 5×10−33.070 2×10−34.025 2×10−32.986 3×10−33.002 4×10−33.001 5×10−3
      DTLZ11.705 1×10−11.338 3×10−18.173 33.179 1×10−22.062 4×10−22.061 9×10−2
      DTLZ28.041 8×10−21.337 4×10−11.122 5×10−17.753 1×10−25.447 0×10−25.446 8×10−2
      DTLZ34.726 8×10−13.652 5×10−15.184 0×1018.768 3×10−25.782 4×10−25.777 5×10−2
      DTLZ48.088 1×10−24.716 6×10−11.313 8×10−17.801 5×10−22.897 3×10−15.449 7×10−2
      DTLZ51.707 6×10−21.513 4×10−21.125 8×10−21.609 3×10−21.306 4×10−21.289 6×10−2
      DTLZ62.312 1×10−22.176 0×10−15.023 0×10−21.824 3×10−21.977 2×10−21.894 5×10−2
      DTLZ71.487 3×10−16.986 2×10−11.244 8×10−17.642 8×10−27.594 8×10−27.685 3×10−2

      表 2  各算法IGD均值

      Table 2.  Mean IGD of each algorithm

      FunctionHVm
      IBEAHypEMO-CMA-ESSMS-EMOANSGA-ⅢMOEA-HV
      ZDT17.199 3×10−15.832 3×10−17.173 8×10−17.207 6×10−17.202 9×10−17.203 0×10−1
      ZDT24.434 7×10−12.409 5×10−14.423 6×10−14.453 3×10−14.450 2×10−14.450 3×10−1
      ZDT36.872 6×10−17.219 1×10−15.819 7×10−16.411 1×10−16.015 1×10−16.398 9×10−1
      ZDT47.049 8×10−16.923 3×10−1−7.207 2×10−17.197 1×10−17.190 0×10−1
      ZDT58.170 4×10−18.027 8×10−19.711 4×10−18.200 6×10−18.312 9×10−18.265 4×10−1
      ZDT63.871 2×10−13.889 2×10−13.879 8×10−13.890 0×10−13.889 3×10−13.889 5×10−1
      DTLZ14.637 1×10−16.104 9×10−1−8.149 5×10−18.408 9×10−18.409 6×10−1
      DTLZ25.580 1×10−15.363 0×10−14.208 6×10−15.484 5×10−15.595 8×10−15.596 0×10−1
      DTLZ32.441 0×10−12.736 3×10−1−5.193 2×10−15.403 4×10−15.416 5×10−1
      DTLZ45.574 5×10−13.532 0×10−14.828 1×10−15.481 2×10−14.469 6×10−15.594 2×10−1
      DTLZ51.986 6×10−11.960 3×10−11.943 1×10−11.949 8×10−11.932 6×10−11.938 4×10−1
      DTLZ61.970 0×10−11.102 8×10−11.776 4×10−11.950 7×10−11.899 6×10−11.908 9×10−1
      DTLZ72.695 3×10−12.056 7×10−12.513 7×10−12.725 3×10−12.694 7×10−12.705 0×10−1

      表 3  各算法HV均值

      Table 3.  Mean HV of each algorithm

      图  6  MOEA-HV算法在部分测试函数上的Pareto前沿面

      Figure 6.  Pareto fronts of MOEA-HV on some test functions

      从表1中各算法的运行时间均值来看，MOEA-HV的运行效率要远远高于其他基于超体积的典型算法，在IBEA的基础上提升近两倍，但比NSGA-Ⅲ要慢，究其原因在于NSGA-Ⅲ不需要计算超体积，而对于基于超体积的算法来说，不论采用何种策略、何种计算方法，超体积的时间计算成本仍然非常大。对于基于超体积的算法来说，计算复杂度高是制约算法性能最重要的因素，因此MOEA-HV最大的突破就是在保持良好收敛性和分布性的同时能有效降低计算复杂度，节约计算超体积的时间成本，提高算法的运行效率。

      从表2和表3中各算法的IGDm和HVm可以看出，MOEA-HV的收敛性和分布性要明显优于IBEA，同时与NSGA-Ⅲ结合后算法综合性能与NSGA-Ⅲ相比也更优，与其他算法相比能够取得最优或次优的综合性能，且性能稳定。总体来看，MOEA-HV在DTLZ系列测试函数上的性能要优于在ZDT系列测试函数上的性能，因为加入非支配排序和基于参考点的NSGA-Ⅲ算法后，三维解集中的非支配个体要比二维的多，因此MOEA-HV的解集在Pareto前沿面上分布会更加均匀。具体来说，MOEA-HV在测试函数ZDT1、ZDT2、ZDT5、ZDT6和DTLZ1~DTLZ7上的综合性能最优或次优，说明该算法能够较好地处理具有凹性、多模态、偏好的问题，但在测试函数ZDT3、ZDT4上性能表现不佳，算法在处理不连续以及多模态混合问题时尚且有待改进，同时测试函数ZDT5具有欺骗性，导致算法容易陷入局部最优，解的分布性较差，测试函数DTLZ5和DTLZ6具有退化性，比较难收敛，因此测试的所有算法在这两个测试函数上表现的收敛性均较差。与其他基于超体积的典型算法相比，MOEA-HV的运行效率更高，且能够保持较好的收敛性和分布性。

      • 3.1.   参数$k$的影响

    • MOEA-HV算法是基于IBEA的框架，其中，适应度值计算函数中的参数k对算法的综合性能有一定影响，因此有必要对k的选择进行独立的对比实验，选择使算法表现出最好性能的参数值。设置种群大小为100，迭代次数为500，IBEA在相同条件下独立运行10次，参数k分别为0.030、0.035、0.040、0.045、0.050、0.055、0.060，进行7组对比实验，测试函数为ZDT1~ZDT6和DTLZ1~DTLZ7，分别比较不同参数下算法IBEA的运行时间均值、IGDm和HVm，结果如图7所示。

      图  7  不同参数$k$对IBEA运行时间、IGDm值和HVm值的影响

      Figure 7.  Influence of different $k$ on runtime, IGDm and HVm of IBEA

      相同条件下程序的运行时间越短说明算法的运行效率越高。从图7（a）中可以看出参数$k$取0.030时，在ZDT3、DTLZ1~DTLZ4、DTLZ6上能够得到最小值，$k$取0.035时运行时间均值也较短，说明参数设置得较小能够在一定程度上节约算法的时间成本，且对于ZDT系列测试函数来说，运行时间受参数设置影响较小，而对于DTLZ系列测试函数来说，$k$取0.030具有较大优势。从图7（b）可以看出，测试函数ZDT5的分布性较差，不论参数取何值，其IGDm值都远远超过其他测试函数的IGDm值，因此考虑去掉ZDT5测试函数来比较不同参数对算法IGDm值的影响。如图7（c）所示，$k$取0.030时在DTLZ1、DTLZ7上的IGDm值明显小于其他参数的IGDm值，且比较稳定，说明$k$取0.030时算法的解集在Pareto前沿面上分布更加均匀。从图7（d）可以看出k取0.030时，算法在测试函数ZDT3和DTLZ1上的HVm值最大，在其他测试函数上也好于其他参数，且性能稳定，收敛性更好，综上可认为在比较的7个参数中，$k$取0.030时IBEA的运行效率更高，且具有良好的综合性能，因此为了获得最好的算法性能，MOEA-HV中的参数$k$也取为0.030。

      • 3.2.   非支配排序的影响

    • IBEA的计算复杂度高，主要原因是需要计算每个个体的独立贡献超体积，而通过Pareto支配关系对个体进行筛选能够提前删除质量不好的个体从而降低了整个解集中个体的超体积计算量，能够有效提高程序的运行效率。设置种群大小为100，迭代次数为500，在相同条件下独立运行10次，对在IBEA中是否加入非支配排序进行对比实验以探究非支配排序对算法的影响。实验的测试函数为ZDT1~ZDT6和DTLZ1~DTLZ7，分别比较IBEA中是否加入非支配排序的运行时间均值、IGDm值和HVm值，如图8所示，其中NDSort+IBEA(Mean)和NDSort+IBEA(Sd)分别表示算法IBEA加入非支配排序后所获得的平均值以及标准差，而IBEA(Mean)和IBEA(Sd)则表示没有加入非支配排序得到的平均值和标准差。

      图  8  非支配排序对IBEA运行时间均值、IGDm值和HVm值的影响

      Figure 8.  Influence of non-dominated sort on runtime, IGDm and HVm of IBEA

      对于2个目标的ZDT系列测试函数来说，计算的超体积为二维的（即面积），比较简单，使得加入非支配排序程序的算法运行时间与IBEA相近甚至更长。因为加入非支配排序后算法的运行效率更高，但同时算法的程序也更长，导致前者节约的时间与后者所消耗的时间刚好抵消，因此在迭代之后两者的运行时间相近。从图8（a）中可以看出，对于3个目标的DTLZ系列测试函数来说，加入非支配排序后算法的运行时间显著降低，是因为三维的超体积更难计算，经过非支配排序之后能有效删除不好的个体，从而大大减少超体积的计算量。同时，从图8（b）、（c）中可以看出，加入非支配排序后算法的性能更加稳定，且能在一定程度上提高算法的综合性能。

      • 3.3.   NSGA-Ⅲ的影响

    • 将IBEA与NSGA-III结合能明显改善算法的分布性，但关键在于如何结合，本文主要考虑两种结合方式：一是IBEA先迭代更新完成获得收敛性较好的种群，然后将获得的该种群作为NSGA-III的初始种群继续进行迭代优化，以期获得分布性也较好的解（简称IBEA+NSGA-III）；二是先运行NSGA-III，然后将获得分布均匀的种群作为IBEA的初始种群，利用超体积指标进化继续增压选择，以期获得综合性能均较好的解（简称NSGA-III+IBEA）。设置种群大小为100，两种结合方式中IBEA迭代次数均为100，NSGA-III迭代次数均为500，在相同条件下独立运行10次，通过实验分析决定何种方式更有利于整合到MOEA-HV算法中。实验的测试函数为ZDT1~ZDT6和DTLZ1~DTLZ7，分别比较IBEA与两种不同结合方式IBEA+NSGA-III、NSGA-III+IBEA的运行时间均值、IGDm值、HVm值和标准差（Standard deviation，Sd），如图9所示。

      图  9  NSGA-Ⅲ对IBEA运行时间、IGDm值和HVm值的影响

      Figure 9.  Influence of NSGA-Ⅲ on runtime, IGDm and HVm of NSGA-Ⅲ

      从图9（a）中可以看出，与NSGA-III结合后算法的运行时间大幅下降，且IBEA+NSGA-III比其他两者的综合运行时间更短，但从图9（b）的标准差数据来看，NSGA-III+IBEA比IBEA+NSGA-III的运行时间更加稳定，因为算法NSGA-III的运行速度快，且分布性好，所获得的初始种群较好，因此第2种结合方式（NSGA-Ⅲ+IBEA）的运行时间浮动更小、更稳定。图9（c）~（f）表明IBEA+NSGA-III在所有测试函数上的IGDm值最小、HVm值最大，性能最稳定，且在ZDT5、DTLZ1和DTLZ3测试函数上要明显优于NSGA-III+IBEA，因此本文的组合算法选择IBEA+NSGA-III结合方式。

    4.   结　论

    • 针对二维和三维的多目标优化问题，本文提出了一种基于超体积指标的多目标进化算法(MOEA-HV)。利用分治递归思想的切片法精确计算种群中个体的独立贡献超体积来指导种群进化，通过在IBEA前对所有种群个体进行非支配排序提前删除被支配的个体，从而减少个体独立贡献超体积的计算量来提升运行效率，同时通过与NSGA-Ⅲ结合来优化算法的分布性，主要有3点改进之处：（1）设计对比实验选择更好的参数；（2）通过非支配排序提前删除不好的个体，能有效节约计算超体积的时间成本；（3）与NSGA-Ⅲ结合来优化算法的分布性。

      在今后的研究中，考虑将算法MOEA-HV应用于解决焊接机器人多目标路径规划问题和更高维的问题，并会继续研究精确计算和近似估计超体积的方法，更加有效地提升算法的运行效率，同时结合其他的优化策略持续改善算法的综合性能。

图(10)  表(3) 参考文献 (36)

目录

    /

    返回文章

    版权所有：《华东理工大学学报》编辑部

    地址：上海市梅陇路130号华东理工大学研究生楼1015室 邮政编码：200237

    电话：021-64253812 传真：021-64253812 Email：ecustxbb@ecust.edu.cn

    本系统由 北京仁和汇智信息技术有限公司 开发 技术支持： info@rhhz.net