高级检索

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

基于事件触发的自适应邻域多目标进化算法

    作者简介: 王学武(1972—),男,陕西合阳人,副教授,博士,研究方向为智能优化算法、焊接机器人智能化技术、焊接自动化、系统建模、控制与优化。E-mail:wangxuew@ecust.edu.cn;
  • 中图分类号: TP301

Multi-objective Evolutionary Algorithm with Adaptive Neighborhood Based on Event Triggering

  • CLC number: TP301

  • 摘要: 为提高多目标算法的多样性与分布性,提出了一种基于事件触发的自适应邻域多目标进化算法(MOEA/D-ET)。采用事件触发策略协调全局与局部搜索,利用网格法进行全局寻优,利用自适应邻域MOEA/D进行局部寻优。对固定邻域与自适应邻域进行了对比,结果表明采用自适应邻域能有效地改善解分布不均的问题。通过对ZDT、WFG、DTLZ测试函数的求解,并与4个经典的多目标算法和2个最新的多目标算法进行对比,结果表明本文算法在收敛性和多样性方面具有一定的优越性。
  • 图 FIG. 210.  FIG. 210.

    Figure FIG. 210..  FIG. 210.

    图 1  网格坐标系示意图

    Figure 1.  Schematic diagram of grid coordinate system

    图 2  固定邻域MOEA/D非劣解分布图

    Figure 2.  Distribution of non-inferior solutions of MOEA/D with uniform neighborhood

    图 3  替换策略图

    Figure 3.  Substitution strategy

    图 4  MOEA/D-ET算法流程图

    Figure 4.  Flow chart of MOEA/D-ET algorithm

    图 5  ZDT系列部分测试函数图

    Figure 5.  Part of ZDT series test function diagrams

    图 6  WFG系列部分测试函数图

    Figure 6.  Part of WFG series test function diagrams

    图 7  DTLZ系列部分测试函数图

    Figure 7.  Part of DTLZ series test function diagrams

    图 8  固定邻域与自适应邻域在ZDT1问题测试对比

    Figure 8.  Comparison of fixed neighborhood and adaptive neighborhood in ZDT1 problem

    表 1  ratio对算法性能的影响

    Table 1.  Influence of ratio on algorithm performance

    RatioHVIGD
    0 0.413 563 82 0.061 247 94
    0.1 0.413 801 07 0.058 740 51
    0.25 0.417 128 47 0.050 980 59
    0.4 0.417 036 06 0.050 989 87
    0.55 0.417 216 55 0.051 294 01
    0.7 0.417 024 70 0.051 213 14
    0.85 0.416 445 78 0.050 953 16
    1 0.416 709 45 0.050 874 89
    下载: 导出CSV

    表 2  ZDT、WFG、DTLZ 测试函数

    Table 2.  Dimension of decision space in ZDT, WFG and DTLZ

    Test functionDimTest functionDimTest functionDim
    ZDT110WFG24DTLZ310
    ZDT210WFG36DTLZ410
    ZDT310WFG48DTLZ710
    ZDT410DTLZ15
    WFG14DTLZ210
    下载: 导出CSV

    表 3  7种算法的IGD均值比较结果

    Table 3.  Comparison of the mean value of IGD index for seven algorithms

    Test functionIGDm
    MOEAD-ETMOEADLG_MOPSOCMOPSONSGA-IIPESA-IINSGA-III
    ZDT10.003 715 570.003 979 820.003 827 640.086 324 750.004 636 890.008 455 740.003 899 06
    ZDT20.003 744 610.003 923 000.003 970 280.035 602 160.004 882 860.008 616 840.003 911 19
    ZDT30.004 313 980.009 123 480.004 323 010.021 324 100.005 401 950.011 513 470.004 634 61
    ZDT40.004 044 761.463 519 360.597 366 940.005 302 740.012 410 960.005 027 55
    WFG10.011 123 310.012 338 210.012 051 940.014 524 610.015 311 250.030 162 930.011 606 77
    WFG20.011 992 380.188 362 960.024 074 830.238 982 070.018 833 190.025 221 610.017 578 32
    WFG30.012 911 010.017 590 230.021 746 800.289 475 830.017 673 240.073 513 260.015 380 98
    WFG40.014 192 480.025 496 490.071 955 460.186 981 060.027 729 190.035 101 280.015 121 49
    DTLZ10.023 964 280.396 747 760.025 776 380.024 824 190.018 665 88
    DTLZ20.050 387 420.070 857 710.078 429 550.604 618 340.068 384 270.069 948 570.047 678 63
    DTLZ30.053 210 040.164 133 6332.530 150 90.069 241 370.077 954 630.053 244 17
    DTLZ40.050 359 940.824 777 850.071 080 060.629 567 820.067 764 970.064 835 870.053 244 17
    DTLZ70.059 711 430.505 916 200.004 405 840.078 435 920.201 577 410.059 896 57
    下载: 导出CSV

    表 4  7种算法的IGD方差比较结果

    Table 4.  Comparison of IGD index variance results for seven algorithms

    Test functionIGDstd
    MOEAD-ETMOEADLG_MOPSOCMOPSONSGA-IIPESA-IINSGA-III
    ZDT1 1.09×10−12 8.61×10−8 8.98×10−10 4.602 588×10−3 9.33×10−8 1.52×10−6 1.27×10−9
    ZDT2 2.24×10−12 2.20×10−8 1.49×10−9 1.063 343×10−3 8.01×10−8 1.25×10−6 4.07×10−9
    ZDT3 1.30×10−9 3.28×10−6 2.84×10−8 2.208 32×10−4 6.90×10−8 2.57×10−6 2.37×10−8
    ZDT4 3.12×10−5 7.509 009 26 1.693 658 38×10−1 4.82×10−7 6.01×10−6 1.13×10−6
    WFG1 4.73×10−7 1.85×10−6 8.56×10−6 1.33×10−5 1.65×10−6 5.12×10−5 4.51×10−10
    WFG2 3.08×10−7 2.716 954 1×10−2 1.528 86×10−4 3.708 948×10−3 6.51×10−7 6.07×10−6 3.54×10−7
    WFG3 2.51×10−7 9.20×10−6 2.59×10−6 1.340 170 1×10−2 2.03×10−6 9.180 5×10−4 3.99×10−7
    WFG4 5.80×10−7 1.82×10−6 1.077 16×10−4 7.810 127×10−3 1.44×10−6 5.16×10−5 3.14×10−6
    DTLZ1 6.42×10−6 5.829 207 84×10−1 2.64×10−6 1.66×10−6 1.88×10−6 1.08×10−8
    DTLZ2 2.69×10−7 1.60×10−6 2.66×10−6 1.147 995 4×10−2 6.10×10−6 8.96×10−5 3.54×10−7
    DTLZ3 3.76×10−7 1.624 232 9×10−2 307.322 750 8 6.39×10−6 2.191 03×10−4 4.90×10−7
    DTLZ4 6.06×10−8 3.900 827 3×10−2 8.56×10−6 8.805 34×10−4 5.02×10−6 7.95×10−6 4.90×10−7
    DTLZ7 2.47×10−6 1.018 686 95×10−1 2.01×10−9 2.11×10−5 5.440 768 6×10−2 5.86×10−7
    下载: 导出CSV

    表 5  7种算法的HV均值比较结果

    Table 5.  Comparison of the mean value of HV index for seven algorithms

    Test functionHVm
    MOEAD-ETMOEADLG_MOPSOCMOPSONSGA-IIPESA-IINSGA-III
    ZDT1 0.661 985 1 0.661 637 80 0.661 708 79 0.616 154 17 0.660 845 30 0.656 244 67 0.661 807 2
    ZDT2 0.328 633 3 0.328 213 13 0.328 375 33 0.318 131 22 0.327 465 61 0.323 411 95 0.328 506 3
    ZDT3 0.778 790 1 0.776 610 18 0.778 955 32 0.772 663 76 0.778 475 01 0.774 266 23 0.778 788 2
    ZDT4 0.660 567 2 0.349 675 19 0.185 674 71 0.658 147 06 0.648 814 14 0.658 250 5
    WFG1 5.064 901 9 5.066 913 01 5.010 116 74 4.942 614 60 5.063 471 51 4.987 661 06 5.068 874 7
    WFG2 4.433 683 7 3.688 273 67 4.361 128 40 3.445 526 24 4.400 113 25 4.382 732 77 4.410 978 4
    WFG3 3.937 851 7 3.911 188 83 3.883 048 78 3.073 092 73 3.910 998 48 3.803 525 15 3.920 755 3
    WFG4 1.676 011 0 1.639 360 43 1.449 419 70 1.391 466 84 1.651 902 39 1.621 945 74 1.658 768 5
    DTLZ1 0.096 824 0 0.069 428 06 0.081 745 82 0.096 169 64 0.096 227 52 0.098 906 7
    DTLZ2 0.414 445 3 0.372 417 39 0.340 317 93 0.050 525 19 0.374 346 27 0.375 682 55 0.403 024 6
    DTLZ3 0.409 642 6 0.304 993 50 0.372 442 81 0.377 857 06 0.403 024 6
    DTLZ4 0.415 522 0 0.360 739 92 0.373 226 00 0.083 003 00 0.375 320 02 0.383 752 23 0.400 664 5
    DTLZ7 0.750 644 7 0.588 619 18 0.487 208 47 0.712 307 43 0.677 023 51 0.750 326 4
    下载: 导出CSV

    表 6  4种邻域策略在ZDT1问题上IGD、HV指标对比

    Table 6.  Comparison of IGD and HV indexes for 4 neighborhood strategies on ZDT1 problem

    Neighborhood size IGDm IGDstd HVm
    10 3.868×10−3 2.8×10−2 0.661 53
    50 3.868 58×10−3 3.118×10−12 0.661 502 4
    100 3.867 536×10−3 9.013 2×10−13 0.661 519 38
    Adaptive 3.715 86×10−3 6.961×10−12 0.661 959 9
    下载: 导出CSV
  • [1] COELLO C A C. Evolutionary multi-objective optimization: A historical view of the field[J]. IEEE Computational Intelligence Magazine, 2006, 1(1): 28-36. doi: 10.1109/MCI.2006.1597059
    [2] GIAGKIOZIS I, FLEMING P J. Methods for multi-objective optimization: An analysis[J]. Information Sciences, 2015, 293: 338-350. doi: 10.1016/j.ins.2014.08.071
    [3] ZITZLER E, DEB K, THIELE L. Comparison of multiobjective evolutionary algorithms: Empirical results[J]. Evolutionary Computation, 2000, 8(2): 173-195. doi: 10.1162/106365600568202
    [4] 李笠, 王万良, 徐新黎, 等. 基于网格排序的多目标粒子群优化算法[J]. 计算机研究与发展, 2017, 54(5): 1012-1023. doi: 10.7544/issn1000-1239.2017.20160074
    [5] ZHANG Q, LI H. MOEA/D: A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731. doi: 10.1109/TEVC.2007.892759
    [6] JAIMES A L, COELLO C A C. MRMOGA: A new parallel multi‐objective evolutionary algorithm based on the use of multiple resolutions[J]. Concurrency & Computation Practice & Experience, 2010, 19(4): 397-441.
    [7] LI H, ZHANG Q. Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(2): 284-302. doi: 10.1109/TEVC.2008.925798
    [8] QI Y, MA X, LIU F, et al. MOEA/D with adaptive weight adjustment[J]. Evolutionary Computation, 2014, 22(2): 231-264. doi: 10.1162/EVCO_a_00109
    [9] YUAN Y, XU H, WANG B, et al. Balancing convergenceand diversity in decomposition-based many-objective optimizers[J]. IEEE Transactions on Evolutionary Computation, 2016, 20(2): 180-198. doi: 10.1109/TEVC.2015.2443001
    [10] 毕晓君, 张磊, 肖婧. 基于双种群的约束多目标优化算法[J]. 计算机研究与发展, 2015, 52(12): 2813-2823. doi: 10.7544/issn1000-1239.2015.20148025
    [11] LI K, ZHANG Q, KWONG S, et al. Stable matching-based selection in evolutionary multiobjective optimization[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(6): 909-92. doi: 10.1109/TEVC.2013.2293776
    [12] YANG S, LI M, LIU X, et al. A grid-based evolutionary algorithm for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2013, 17(5): 721-736. doi: 10.1109/TEVC.2012.2227145
    [13] 郑友莲, 樊俊青. 基于密集距离的多目标粒子群优化算法[J]. 湖北大学学报(自然科学版), 2008, 30(2): 141-144. doi: 10.3969/j.issn.1000-2375.2008.02.009
    [14] DEB K. A fast elitist multi-objective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2000, 6(2): 182-197.
    [15] BHARGAV G, VIMAL S, VIVEK P. Multi-objective optimization of vehicle passive suspension system using NSGA-II, SPEA2 and PESA-II[J]. Procedia Technology, 2016, 23: 361-368. doi: 10.1016/j.protcy.2016.03.038
    [16] 王学武, 薛立卡, 顾幸生. 三态协调搜索多目标粒子群优化算法[J]. 控制与决策, 2015, 30(11): 1945-1952.
    [17] YUAN Y, XU H, WANG B. An improved NSGA-III procedure for evolutionary many-objective optimization[C]// Conference on Genetic & Evolutionary Computation. USA: ACM, 2014: 661-667.
    [18] 王学武, 闵永, 顾幸生. 基于密度聚类的多目标粒子群优化算法[J]. 华东理工大学学报(自然科学版), 2019, 45(3): 449-457.
  • [1] 王学武闵永顾幸生 . 基于密度聚类的多目标粒子群优化算法. 华东理工大学学报(自然科学版), 2019, 45(3): 449-457. doi: 10.14135/j.cnki.1006-3080.20180321005
    [2] 王学武魏建斌周昕顾幸生 . 一种基于超体积指标的多目标进化算法. 华东理工大学学报(自然科学版), 2019, 45(): 1-12. doi: 10.14135/j.cnki.1006-3080.20190917001
    [3] 赵灿华侍洪波 . 基于自适应变邻域搜索的大规模电动车辆路径优化. 华东理工大学学报(自然科学版), 2019, 45(): 1-8. doi: 10.14135/j.cnki.1006-3080.20190730001
    [4] 张剑超杜文莉覃水 . 基于新型自适应采样算法的催化重整过程代理模型. 华东理工大学学报(自然科学版), 2019, 45(6): 928-937. doi: 10.14135/j.cnki.1006-3080.20180915001
    [5] 魏梓轩周家乐 . 基于VAE的编码DNA载体阻断事件聚类分析与研究. 华东理工大学学报(自然科学版), 2019, 45(): 1-9. doi: 10.14135/j.cnki.1006-3080.20190424001
    [6] 盛宙颜秉勇周家乐王慧锋 . 基于模糊C均值和SLIC的纳米孔阻断事件的识别与研究. 华东理工大学学报(自然科学版), 2020, 46(1): 100-113. doi: 10.14135/j.cnki.1006-3080.20181206002
    [7] 钱文秀常青向辉康文斌 . 基于深度监督显著目标检测的草莓图像分割. 华东理工大学学报(自然科学版), 2020, 46(1): 114-120. doi: 10.14135/j.cnki.1006-3080.20181205004
    [8] 陈丹丹王薇徐以汎 . 基于降维的全局优化近似解法. 华东理工大学学报(自然科学版), 2019, 45(6): 995-1000. doi: 10.14135/j.cnki.1006-3080.2018071700
    [9] 张雪芹魏一凡 . 基于深度学习的驾驶场景关键目标检测与提取. 华东理工大学学报(自然科学版), 2019, 45(6): 980-988. doi: 10.14135/j.cnki.1006-3080.20181023002
    [10] 黄克骄贺理珀宋兴福于建国 . 响应曲面法优化2-(4-羟基苯氧基)丙酸甲酯结晶工艺. 华东理工大学学报(自然科学版), 2019, 45(3): 374-381. doi: 10.14135/j.cnki.1006-3080.20180425001
    [11] 马恒达袁伟娜徐睿 . 一种组稀疏信道估计中的信号重构优化方法. 华东理工大学学报(自然科学版), 2019, 45(4): 646-651. doi: 10.14135/j.cnki.1006-3080.20180409004
    [12] 陈鹏罗娜 . 基于竞争机制差分进化算法的无分流换热网络优化. 华东理工大学学报(自然科学版), 2019, 45(6): 970-979. doi: 10.14135/j.cnki.1006-3080.20181015004
    [13] 孙京云张琴张雷达赵伟杨辉杭海峰王泽建庄英萍 . 搅拌桨组合与葡萄糖流加工艺相结合的凝胶多糖发酵工艺优化. 华东理工大学学报(自然科学版), 2019, 45(4): 585-592. doi: 10.14135/j.cnki.1006-3080.20180508001
    [14] 黄佳琳张丫丫顾幸生 . 基于改进生物地理学优化算法的分布式装配置换流水车间调度问题. 华东理工大学学报(自然科学版), 2019, 45(): 1-12. doi: 10.14133/j.cnki.1006-3080.20190828001
  • 加载中
图(9)表(6)
计量
  • 文章访问数:  5588
  • HTML全文浏览量:  1472
  • PDF下载量:  18
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-11-20
  • 网络出版日期:  2019-07-18
  • 刊出日期:  2020-02-01

基于事件触发的自适应邻域多目标进化算法

    作者简介:王学武(1972—),男,陕西合阳人,副教授,博士,研究方向为智能优化算法、焊接机器人智能化技术、焊接自动化、系统建模、控制与优化。E-mail:wangxuew@ecust.edu.cn
  • 华东理工大学化工过程先进控制和优化技术教育部重点实验室,上海 200237

摘要: 为提高多目标算法的多样性与分布性,提出了一种基于事件触发的自适应邻域多目标进化算法(MOEA/D-ET)。采用事件触发策略协调全局与局部搜索,利用网格法进行全局寻优,利用自适应邻域MOEA/D进行局部寻优。对固定邻域与自适应邻域进行了对比,结果表明采用自适应邻域能有效地改善解分布不均的问题。通过对ZDT、WFG、DTLZ测试函数的求解,并与4个经典的多目标算法和2个最新的多目标算法进行对比,结果表明本文算法在收敛性和多样性方面具有一定的优越性。

English Abstract

  • 工业生产中经常存在多个目标的优化问题,多目标优化算法为此类问题提供了解决办法,因此多目标进化算法成为近些年的研究热门[1-2]。在对多目标问题进行优化时,主要考虑两个问题[3]:一是解的收敛性;二是解的多样性。

    为了有效地解决上述两个问题,众多学者提供了解决思路。李笠等[4]提出了基于网格排序的多目标粒子群优化算法,利用网格排序的方法对粒子群算法非劣解的储备集进行优化,有效地增强了算法的多样性。Zhang等[5]提出了一种基于分解的多目标粒子群优化算法(MOPSO/D),将基于分解的多目标算法与粒子群结合,利用改进变异算子增强解的多样性,利用储备集的方式对非劣解进行储存。Jaimes等[6]指出采用多种群策略对多目标优化问题进行求解,利用种群间的信息交流,不仅能够提高搜索效率,而且能够增加种群的多样性。Li等[7]提出基于差分进化算法的分解多目标优化算法(MOEA/D-DE),利用差分进化算法收敛速度快、实现简单等特点来改进算法。Qi等[8]提出基于自适应权重调整的分解多目标进化算法(MOEA/D with Adaptive Weight Adjustment,MOEA/D-AWA),采用自适应的方法改变权重,使解在空间上的分布更加均匀。Yuan等[9]提出了基于距离更新策略的分解多目标进化算法(MOEA/D with a Distance-Based Updating Strategy,MOEA/D-DU),采用改进的切比雪夫聚合函数,利用子问题的垂直距离作为指导,提高算法在高维目标中的应用效果。毕晓君等[10]提出了基于双种群的约束多目标优化算法,采用两个种群交流和改进的Harmonic距离对算法进行改进,提高算法优化效果。

    以上算法在逼近真实前沿面上具有较好的效果,但解的多样性不足且在空间上分布不够均匀。为了提高解的多样性,改善解在空间分布不均匀的问题,协调算法搜索过程的收敛性与多样性,本文提出了基于事件触发的自适应邻域多目标进化算法(MOEA/D-ET)。采用事件触发策略协调全局搜索与局部搜索,网格法进行全局搜索为局部搜索作指导,MOEA/D算法进行局部搜索,并且针对解分布不均匀的问题,采用自适应邻域的方法进行改进。

    • 在搜索过程中,MOEA/D-ET算法通过事件触发机制改变种群全局搜索与局部搜索功能,且产生的子代直接与父代比较、替换,不通过储备集的方式,可以在保证算法收敛性与多样性的同时减少计算消耗。

    • 面对多目标问题时[11],通常使用笛卡尔坐标系(Cartesian Coordinate System)。网格法则是将笛卡尔坐标系下的粒子坐标进行网格化,并对每个网格中粒子间的相对距离进行定义。根据粒子间的相对距离以及非支配关系对网格内的粒子进行管理。

      定义1[12] 网格的上下边界:在m个优化目标下,设${f_{\max }}(x)$为当前种群的最大适应度值,${f_{\min }}(x)$为当前种群的最小适应度值,网格的上下边界为${u_{\rm{b}}}$${l_{\rm{b}}}$

      式中,div为网格划分系数。

      根据所建立的网格坐标系,计算所有粒子在网格上的坐标。第i个粒子的网格坐标计算如下:

      其中${G_{ip}}$为网格坐标。求解的坐标进行向下取整操作,则$\left\lfloor {{G_{ip}}} \right\rfloor$为第i个粒子的坐标。

      在网格坐标系下,粒子间的相对距离为两粒子横纵坐标相差之和,例如图1中粒子A、B的相对距离${D_{{\rm{AB}}}}$为4。

      图  1  网格坐标系示意图

      Figure 1.  Schematic diagram of grid coordinate system

      在网格坐标系上,根据各个粒子的非支配关系选择父代。首先选择非支配粒子,若两个不同粒子同为非支配解且在网格坐标系中有相同坐标,如图1中D、E所示,则计算它们的网格坐标点距离(GCPD)[12],计算公式如下:

      选择GCPD较小的作为父代,可以免去计算当前个体对所有其他粒子的距离,大大减少计算量。

    • MOEA/D算法将多目标问题分解成一组若干子目标问题进行求解。考虑的目标为两目标和三目标问题时,采用切比雪夫(Tchebycheff)聚合函数进行求解,描述如下[6]

      其中:$\lambda = ({\lambda _1},{\lambda _2},\cdots,{\lambda _k})$为子问题的权重;${f_i}(x)$为第i个优化目标函数值;${z^*}$为理想参考点。理想参考点的更新公式如下:

      如此可将迭代过程中的历史极小值信息保存下来,使算法收敛速度更快,解的精度得以提高。

      采用切比雪夫法求解多目标问题时,需要利用切比雪夫方法找出子问题$g(x|\lambda ,{z^*})$的最大值。通过改变决策变量$x$,使最大的$g(x|\lambda ,{z^*})$接近理想参考点,则其余子问题也相应接近理想参考点。

    • 在MOEA/D算法中,子代粒子的产生受其父代邻域粒子的影响,邻域的大小对算法有很大的影响。若邻域设置为固定大小会导致解的分布不均匀,尤其是在凹凸性较大的Pareto前沿面。如图2所示,解在前沿面的中心区域分布较密集,边界附近相对稀疏。

      图  2  固定邻域MOEA/D非劣解分布图

      Figure 2.  Distribution of non-inferior solutions of MOEA/D with uniform neighborhood

      若邻域设置过大,在更新过程中,父代与邻域内的其他个体比较次数太多,浪费计算资源。此外,过大的邻域虽然会提升算法的多样性,但同时会产生偏离Pareto前沿的新解,导致种群退化。邻域设置较小,虽然有利于寻找局部最优解,逼近真实Pareto前沿,但无法保证算法的多样性。基于以上分析,对邻域进行自适应调整,自适应调整方式如下:

      其中:邻域最终大小$ T = \left\lfloor T \right\rfloor $$\left\lfloor {} \right\rfloor $为向下取整符号;Generations为总迭代次数;Gene为当前迭代次数;${T_{\max }}$为子问题最大邻域范围,由于MOEA/D算法主要用于局部搜索,所以邻域可以设置相对较小以保证搜索到的解逼近真实前沿面,本文${T_{\max }} = \left\lfloor {\dfrac{{{N}}}{5}} \right\rfloor $${T_{\min }}$为子问题最小邻域范围,本文设置为${T_{\min }} = \left\lfloor {\dfrac{{{N}}}{{10}}} \right\rfloor $N为种群数目。

    • MOEA/D算法将多目标问题分解为多个子目标问题进行求解,Li等[7]阐述了差分进化策略有利于提高MOEA/D算法的性能。采取如下方式进行变异:

      其中:$x{}_i$为当前迭代粒子;${x_{{\rm r}2}},{x_{{\rm r}3}}$为当前种群随机选择的差分向量;F为变异步长;$v_i^t$为通过重组产生的新个体。

      变异步长F的大小对解的精度有很大影响。若F设置较大,每次产生的新个体相对父代变异步长大,算法的多样性增加,局部搜索能力减弱;F设置较小则相反。为了在搜索过程中不至于太快陷入局部最优,本文设置F如下:

      式中:k为缩放系数。通过这种调节方式使搜索分为3个阶段:第一阶段F较大,保证了搜索初期种群的多样性;第二阶段F不断减小,为过渡阶段,保证第三阶段不至于太早陷入局部最优;第三阶段F设置较小,寻找最优解,提高搜索精度。变异策略中交叉概率CR设为1,可提高种群多样性,并且使解具有旋转不变的特性。

    •  定义2 Pareto支配关系:${x_1}$${x_2} \in x$,若${f_i}({x_1}) \leqslant $${f_i}({x_2}),i = 1,2,\cdots,m$且存在$k \in \{ 1,2,\cdots,m\} $,使${f_k}({x_1}) < $${f_k}({x_2}) $,则称${x_1}$支配${x_2}$${x_2}$${x_1}$支配,此时的${x_1}$为非支配解。

      父代与子代混合,根据支配关系进行排序,将非支配解的粒子序号定为1,仅受1个粒子支配的序号为2,依次类推。排列序号靠前的个体根据网格法进行选择,选出与种群大小相同的粒子数。若序号为1的粒子数量小于初始种群大小,则从序号为2的粒子中引入,以此类推。如此选出的种群在空间上分布较为均匀,同时也相对贴近真实Pareto前沿面(PF),可为接下来的局部搜索提供一个较好的指导作用。

    • 通过全局搜索选择的粒子仍存在分布不均匀、不够贴近真实PF的问题,因此还需要进行局部搜索。局部搜索采用MOEA/D算法进行搜索,为了使搜索到的非劣解尽可能贴近真实PF,并且在空间上分布均匀,需要对父代的替换策略进行改进。MOEA/D算法替换策略如下:

      (1)利用自适应方式设置可替换父代的邻域大小。

      (2)计算父代及其邻域的支配关系、拥挤距离。

      (3)通过变异策略方式生成子代。

      (4)子代替换父代邻域内的粒子,替换策略流程图如图3所示。

      图  3  替换策略图

      Figure 3.  Substitution strategy

      图3中,dis(p,o)为父代与邻域其他粒子的总距离,dis(c,o)为子代与邻域其他粒子的总距离,fitness为适应度函数。若邻域内替换的粒子数过少,种群更新缓慢,收敛速度慢;如果替换数量较多,收敛速度快,容易陷入局部最优,计算成本增加。

    • 若全局搜索次数过多,虽然解分布广泛,但无法有效地逼近真实PF。若搜索次数过少,就开始进行局部搜索,会陷入局部最优,并造成不必要的计算消耗。因此设计事件触发机制对全局搜索与局部搜索进行协调与平衡。

      采用更新粒子比率(${\rm{ratio}}$)对全局搜索与局部搜索进行协调与平衡,${\rm{ratio}}$计算公式如下:

      其中:${\rm{num}}\_{\rm{c}}$为全局搜索中更新粒子的数量;N为种群大小;${\rm{num}}$为局部搜索中更新粒子的数量。当更新粒子所占比率较大时,说明所产生的非劣解相距PF较远,或解在空间上分布不均匀。当更新比率较小时,说明解已经逼近PF,此时需要对解的精度与分布性进行提高。

      ratio的大小对算法的分布性与收敛性有一定影响。采用三维测试函数DTLZ2,在10维决策空间情况下,改变ratio的大小对算法HV与IGD指标的影响结果如表1所示。测试指标IGD和HV可以综合评判算法的收敛性与多样性,其中IGD为反转世代距,HV为非支配解集中所有非支配解与参考点围成的超立方体的体积。

      RatioHVIGD
      0 0.413 563 82 0.061 247 94
      0.1 0.413 801 07 0.058 740 51
      0.25 0.417 128 47 0.050 980 59
      0.4 0.417 036 06 0.050 989 87
      0.55 0.417 216 55 0.051 294 01
      0.7 0.417 024 70 0.051 213 14
      0.85 0.416 445 78 0.050 953 16
      1 0.416 709 45 0.050 874 89

      表 1  ratio对算法性能的影响

      Table 1.  Influence of ratio on algorithm performance

      表1可以看出,ratio为0.55时,算法的HV值最大,解分布较广,但此时不够贴近真实PF。ratio为0.25时,IGD值最小,解的分布最贴近真实PF,且此时HV值为次优,说明算法在空间分布上较广。尝试选择ratio>0.55时触发全局搜索,ratio<0.25时触发局部搜索,通过实验得出此时的HV为0.416 098 11,IGD为0.051 974 819,算法效果反而下降。综合分析ratio参数设置为0.25较为合适。

    • (1)初始化:初始化网格大小div,种群大小N,子代更新比率${\rm{ratio}}$,构造权重向量w,初始化种群,迭代次数。

      (2)更新:${\rm{Gene}} = \{ 1,2,\cdots,{\rm{Generations}}\} $,判断${\rm{ratio}}$的大小以及目标数,根据事件触发机制选择触发全局搜索机制或局部搜索机制。

      (3)输出:若算法满足停止条件,则停止并输出Pareto前沿及相应的评价指标值,否则返回步骤(2)继续执行。

      MOEA/D-ET算法流程如图4所示。

      图  4  MOEA/D-ET算法流程图

      Figure 4.  Flow chart of MOEA/D-ET algorithm

    • 为了验证本文算法在求解多目标优化问题上的性能,选取3个系列的测试函数如表2所示。其中ZDT、WFG为二目标测试函数,DTLZ为三目标测试函数,Dim为决策变量空间维数。测试环境为Intel(R) Core(TM) i5-4200H CPU @ 2.80 GHZ。

      Test functionDimTest functionDimTest functionDim
      ZDT110WFG24DTLZ310
      ZDT210WFG36DTLZ410
      ZDT310WFG48DTLZ710
      ZDT410DTLZ15
      WFG14DTLZ210

      表 2  ZDT、WFG、DTLZ 测试函数

      Table 2.  Dimension of decision space in ZDT, WFG and DTLZ

      选择4个经典的多目标算法CMPSO[13]、MOEA/D[5]、NSGA-II[14]、PSEA-II[15]以及2个最新的多目标算法LG_MOPSO[16]、NSGA-III[17]作为对比算法。其中CMPSO为基于密集距离的多目标粒子群优化算法;MOEA/D为基于分解的多目标优化算法;NSGA-II为带精英策略的快速非支配排序遗传算法;PSEA-II为利用遗传算法的机理和基于Pareto包络选择的多目标优化算法;LG_MOPSO为利用聚类选择指导粒子的多目标粒子群算法;NSGA-III为一种基于参考点的非支配排序算法。

    • 在相同条件下对每个算法进行对比,每个算法进行20次独立实验。算法的种群规模均设为100,迭代次数为400。在MOEA/D-ET中,网格大小div在二目标中设置为45,在三目标中设置为20。局部搜索中,子代替换父代个数设置为10,其余参数设置如文中所述,其他算法的参数均参考相应文献。

    • 表3~表5列出了各种算法在IGD均值(IGDm)、IGD方差(IGDstd)、HV均值(HVm)上的实验结果,其中的黑体为最优结果。在IGD均值上,本文算法在13个测试函数中有10个测试函数的均值都要优于CMPSO、MOEA/D、NSGA-II、PSEA-II、LG_MOPSO、NSGA-III。在另外两个测试函数DTLZ1、DTLZ2上,NSGA-III效果最好,在本文算法的测试结果为次优。在DTLZ7测试函数上LG_MOPSO效果最好。IGD方差上,在本文算法在13个测试函数中有9个测试函数的方差都小于其他算法。在ZDT1、ZDT2、ZDT3、WFG4、DTLZ2、DTLZ3测试函数上的方差远远小于CMPSO、MOEA/D、NSGA-II、PSEA-II、LG_MOPSO、NSGA-III。在其他测试问题上,虽然本文算法的IGD方差结果并不是最好,但都达到了10−5,说明算法鲁棒性较好。HV性能指标上,本文算法在13个测试函数中有10个测试函数的测试结果要优于CMPSO、MOEA/D、NSGA-II、PSEA-II、LG_MOPSO、NSGA-III。在ZDT3问题上,LG_MOPSO测试结果最好,在WFG1、DTLZ1问题上,NSGA-III测试结果最好,本文算法表现为次优。这说明虽然通过自适应邻域方式对算法进行了改进,改善了算法在寻优过程中解出现中间区域密集、两端稀疏的问题,但面对边缘凹凸性较大问题时,相较于NSGA-III算法,本文算法在搜索能力上仍需要改进。

      Test functionIGDm
      MOEAD-ETMOEADLG_MOPSOCMOPSONSGA-IIPESA-IINSGA-III
      ZDT10.003 715 570.003 979 820.003 827 640.086 324 750.004 636 890.008 455 740.003 899 06
      ZDT20.003 744 610.003 923 000.003 970 280.035 602 160.004 882 860.008 616 840.003 911 19
      ZDT30.004 313 980.009 123 480.004 323 010.021 324 100.005 401 950.011 513 470.004 634 61
      ZDT40.004 044 761.463 519 360.597 366 940.005 302 740.012 410 960.005 027 55
      WFG10.011 123 310.012 338 210.012 051 940.014 524 610.015 311 250.030 162 930.011 606 77
      WFG20.011 992 380.188 362 960.024 074 830.238 982 070.018 833 190.025 221 610.017 578 32
      WFG30.012 911 010.017 590 230.021 746 800.289 475 830.017 673 240.073 513 260.015 380 98
      WFG40.014 192 480.025 496 490.071 955 460.186 981 060.027 729 190.035 101 280.015 121 49
      DTLZ10.023 964 280.396 747 760.025 776 380.024 824 190.018 665 88
      DTLZ20.050 387 420.070 857 710.078 429 550.604 618 340.068 384 270.069 948 570.047 678 63
      DTLZ30.053 210 040.164 133 6332.530 150 90.069 241 370.077 954 630.053 244 17
      DTLZ40.050 359 940.824 777 850.071 080 060.629 567 820.067 764 970.064 835 870.053 244 17
      DTLZ70.059 711 430.505 916 200.004 405 840.078 435 920.201 577 410.059 896 57

      表 3  7种算法的IGD均值比较结果

      Table 3.  Comparison of the mean value of IGD index for seven algorithms

      Test functionIGDstd
      MOEAD-ETMOEADLG_MOPSOCMOPSONSGA-IIPESA-IINSGA-III
      ZDT1 1.09×10−12 8.61×10−8 8.98×10−10 4.602 588×10−3 9.33×10−8 1.52×10−6 1.27×10−9
      ZDT2 2.24×10−12 2.20×10−8 1.49×10−9 1.063 343×10−3 8.01×10−8 1.25×10−6 4.07×10−9
      ZDT3 1.30×10−9 3.28×10−6 2.84×10−8 2.208 32×10−4 6.90×10−8 2.57×10−6 2.37×10−8
      ZDT4 3.12×10−5 7.509 009 26 1.693 658 38×10−1 4.82×10−7 6.01×10−6 1.13×10−6
      WFG1 4.73×10−7 1.85×10−6 8.56×10−6 1.33×10−5 1.65×10−6 5.12×10−5 4.51×10−10
      WFG2 3.08×10−7 2.716 954 1×10−2 1.528 86×10−4 3.708 948×10−3 6.51×10−7 6.07×10−6 3.54×10−7
      WFG3 2.51×10−7 9.20×10−6 2.59×10−6 1.340 170 1×10−2 2.03×10−6 9.180 5×10−4 3.99×10−7
      WFG4 5.80×10−7 1.82×10−6 1.077 16×10−4 7.810 127×10−3 1.44×10−6 5.16×10−5 3.14×10−6
      DTLZ1 6.42×10−6 5.829 207 84×10−1 2.64×10−6 1.66×10−6 1.88×10−6 1.08×10−8
      DTLZ2 2.69×10−7 1.60×10−6 2.66×10−6 1.147 995 4×10−2 6.10×10−6 8.96×10−5 3.54×10−7
      DTLZ3 3.76×10−7 1.624 232 9×10−2 307.322 750 8 6.39×10−6 2.191 03×10−4 4.90×10−7
      DTLZ4 6.06×10−8 3.900 827 3×10−2 8.56×10−6 8.805 34×10−4 5.02×10−6 7.95×10−6 4.90×10−7
      DTLZ7 2.47×10−6 1.018 686 95×10−1 2.01×10−9 2.11×10−5 5.440 768 6×10−2 5.86×10−7

      表 4  7种算法的IGD方差比较结果

      Table 4.  Comparison of IGD index variance results for seven algorithms

      Test functionHVm
      MOEAD-ETMOEADLG_MOPSOCMOPSONSGA-IIPESA-IINSGA-III
      ZDT1 0.661 985 1 0.661 637 80 0.661 708 79 0.616 154 17 0.660 845 30 0.656 244 67 0.661 807 2
      ZDT2 0.328 633 3 0.328 213 13 0.328 375 33 0.318 131 22 0.327 465 61 0.323 411 95 0.328 506 3
      ZDT3 0.778 790 1 0.776 610 18 0.778 955 32 0.772 663 76 0.778 475 01 0.774 266 23 0.778 788 2
      ZDT4 0.660 567 2 0.349 675 19 0.185 674 71 0.658 147 06 0.648 814 14 0.658 250 5
      WFG1 5.064 901 9 5.066 913 01 5.010 116 74 4.942 614 60 5.063 471 51 4.987 661 06 5.068 874 7
      WFG2 4.433 683 7 3.688 273 67 4.361 128 40 3.445 526 24 4.400 113 25 4.382 732 77 4.410 978 4
      WFG3 3.937 851 7 3.911 188 83 3.883 048 78 3.073 092 73 3.910 998 48 3.803 525 15 3.920 755 3
      WFG4 1.676 011 0 1.639 360 43 1.449 419 70 1.391 466 84 1.651 902 39 1.621 945 74 1.658 768 5
      DTLZ1 0.096 824 0 0.069 428 06 0.081 745 82 0.096 169 64 0.096 227 52 0.098 906 7
      DTLZ2 0.414 445 3 0.372 417 39 0.340 317 93 0.050 525 19 0.374 346 27 0.375 682 55 0.403 024 6
      DTLZ3 0.409 642 6 0.304 993 50 0.372 442 81 0.377 857 06 0.403 024 6
      DTLZ4 0.415 522 0 0.360 739 92 0.373 226 00 0.083 003 00 0.375 320 02 0.383 752 23 0.400 664 5
      DTLZ7 0.750 644 7 0.588 619 18 0.487 208 47 0.712 307 43 0.677 023 51 0.750 326 4

      表 5  7种算法的HV均值比较结果

      Table 5.  Comparison of the mean value of HV index for seven algorithms

      表3~表5可以看出,本文算法在大部分测试函数上都优于CMPSO、MOEA/D、NSGA-II、PSEA-II、LG_MOPSO、NSGA-III,尤其在HV指标上的测试结果较好。虽然对于测试函数ZDT3、WFG1、DTLZ1问题上为次优,但与最优指标仅仅相差10−4~10−2,说明本文算法在空间上分布范围广,多样性较好。在IGD指标上表现出的效果大部分要优于其他算法,在DTLZ7测试问题上,LG_MOPSO算法在IGD均值及方差测试上得到较好的结果,但在HV均值上结果较差,说明该算法在该问题所找出的非劣解空间分布范围有限,而本文算法在IGD均值及方差测试上为次优,但在HV均值上结果最优。综合分析,在DTLZ7问题上,本文算法也要优于LG_MOPSO。NSGA-III算法在WFG1、DTLZ1问题上测试效果较好,但本文算法均为次优且与最优值相差很小,可通过继续深入研究邻域关系提升算法的性能。以上分析表明,本文算法搜索到的非劣解空间分布广,多样性好,在保证解的精度与算法收敛性的同时减少了不必要的计算消耗。

      为了更直观地展示本文算法所获得非支配解的质量和分布情况,绘制非支配解集的分布图与真实PF对比,如图5图6图7所示。图5示出了ZDT系列部分测试函数图,图6示出了WFG系列部分测试图,图7示出了DTLZ系列部分测试函数图。从图中可以看出,本文算法与真实PF吻合度较高,解的分布空间广泛,较好地平衡了求解多目标问题中的收敛性与多样性。

      图  5  ZDT系列部分测试函数图

      Figure 5.  Part of ZDT series test function diagrams

      图  6  WFG系列部分测试函数图

      Figure 6.  Part of WFG series test function diagrams

      图  7  DTLZ系列部分测试函数图

      Figure 7.  Part of DTLZ series test function diagrams

    • 设置固定邻域大小为10、50、100;自适应邻域设置如文中所述。两种邻域方式的种群大小设置为100,迭代次数为400。

      在ZDT1上的测试结果如表6图8所示。从图8(a)(b)(c)可以看出,固定邻域情况下,将邻域大小设置较小、适中、较大,非劣解在空间上的分布依旧存在两端分布稀疏、中心区域分布集中的现象。从图8(d)可以看出,采用自适应邻域策略后,非劣解在空间上的分布更加均匀,改善了固定邻域下非劣解相对集中于中心区域的问题,使解在空间上分布更加均匀。

      Neighborhood size IGDm IGDstd HVm
      10 3.868×10−3 2.8×10−2 0.661 53
      50 3.868 58×10−3 3.118×10−12 0.661 502 4
      100 3.867 536×10−3 9.013 2×10−13 0.661 519 38
      Adaptive 3.715 86×10−3 6.961×10−12 0.661 959 9

      表 6  4种邻域策略在ZDT1问题上IGD、HV指标对比

      Table 6.  Comparison of IGD and HV indexes for 4 neighborhood strategies on ZDT1 problem

      图  8  固定邻域与自适应邻域在ZDT1问题测试对比

      Figure 8.  Comparison of fixed neighborhood and adaptive neighborhood in ZDT1 problem

      表6可以看出,自适应邻域在IGD均值上的表现优于固定邻域,说明采用自适应邻域方式寻找的非劣解更加逼近真实PF。在HV均值上自适应邻域的表现同样优于固定邻域,说明采用自适应邻域方式寻找到的非劣解空间分布广。

    • 本文提出了基于事件触发的自适应邻域多目标进化算法,采用更新粒子比率作为事件触发的条件对全局搜索与局部搜索进行调节。全局搜索主要采用网格法,旨在保证解的多样性的情况下在较短时间逼近真实PF。局部搜索采用自适应邻域MOEA/D方法提高解的精度,使解在空间分布更加均匀。全局搜索与局部搜索产生的非劣解通过事件触发机制相互交流,相互指引,大大提高了算法性能。通过对标准测试函数进行仿真实验,并与6个多目标优化算法进行比较,结果表明本文算法所得出的非劣解在多样性与收敛性上有很大的提升。分析了固定邻域与自适应邻域对算法的影响,通过测试结果可以看出,采用自适应邻域方法在前沿面的逼近与非劣解的分布上都有着很好的效果。接下来会将此算法离散化,应用于焊接机器人[18]轨迹、能耗、变形等参数的多目标优化中。

(9)  表(6) 参考文献 (18) 相关文章 (14)

目录

    /

    返回文章