高级搜索

基于分解和支配关系的超多目标进化算法

赵辉 王天龙 刘衍舟 黄橙 张天骐

引用本文: 赵辉, 王天龙, 刘衍舟, 黄橙, 张天骐. 基于分解和支配关系的超多目标进化算法[J]. 电子与信息学报, doi: 10.11999/JEIT190589 shu
Citation:  Hui ZhAO, Tianlong WANG, Yanzhou LIU, Cheng HUANG, Tianqi ZhANG. Decomposition and Dominance Relation Based Many-objective Evolutionary Algorithm[J]. Journal of Electronics and Information Technology, doi: 10.11999/JEIT190589 shu

基于分解和支配关系的超多目标进化算法

    作者简介: 赵辉: 女,1980年生,教授,博导,研究方向为深空光通信、信号理论与信息处理、信号与图像处理;
    王天龙: 男,1994年生,硕士,研究方向为信号与图像处理、进化计算、多目标优化;
    刘衍舟: 男,1994年生,硕士,研究方向为信号与图像处理;
    黄橙: 男,1993年生,硕士,研究方向为信号与图像处理;
    张天骐: 男,1971年生,教授,博导,研究方向为无线通信的智能信号处理、通信抗干扰和信息对抗
    通讯作者: 赵辉,zhaohui@cqupt.edu.cn
  • 基金项目: 国家自然科学基金(61671095)

摘要: 近年来,超多目标优化问题(MaOPs)成为了进化计算领域的研究热点。然而,在处理各种优化问题中,如何有效地平衡收敛性和多样性仍是一个难题。为了解决上述的问题,该文提出了一种基于分解和支配关系的超多目标进化算法(DdrEA)。首先利用权重向量把整个种群分解为一组子种群,这些子种群将进行协同优化;然后利用角度和角度支配关系计算子种群内每个解的值;最后根据适应度值进行精英选择,即在每个子空间内选取适应度值最小的解作为精英解进入下一代。DdrEA通过与当前较优的NSGA-II/AD, RVEA, MOMBI-II等多个超多目标进化算法进行实验对比,实验结果表明该文算法性能明显优于对比算法,能够有效平衡种群的收敛性和多样性。

English

    1. [1]

      ZHOU Aimin, QU Boyang, LI Hui, et al. Multiobjective evolutionary algorithms: A survey of the state of the art[J]. Swarm and Evolutionary Computation, 2011, 1(1): 32–49. doi: 10.1016/j.swevo.2011.03.001

    2. [2]

      赖文星, 邓忠民, 张鑫杰. 基于多目标优化NSGA2改进算法的结构动力学模型确认[J]. 计算力学学报, 2018, 35(6): 669–674. doi: 10.7511/jslx20170828004
      LAI Wenxing, DENG Zhongmin, and ZHANG Xinjie. Structural dynamics model validation based on NSGA2 improved algorithm[J]. Chinese Journal of Computational Mechanics, 2018, 35(6): 669–674. doi: 10.7511/jslx20170828004

    3. [3]

      LI Bingdong, LI Jinlong, TANG Ke, et al. Many-objective evolutionary algorithms: A survey[J]. ACM Computing Surveys, 2015, 48(1): 1–35. doi: 10.1145/2792984

    4. [4]

      HE Zhenan, YEN G G, and ZHANG Jun. Fuzzy-based Pareto optimality for many-objective evolutionary algorithms[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(2): 269–285. doi: 10.1109/TEVC.2013.2258025

    5. [5]

      YANG Shengxiang, LI Miqing, LIU Xiaohui, 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

    6. [6]

      ZHANG Qingfu and LI Hui. 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

    7. [7]

      郑金华, 喻果, 贾月. 基于权重迭代的偏好多目标分解算法解决参考点对算法影响的研究[J]. 电子学报, 2016, 44(1): 67–76. doi: 10.3969/j.issn.0372-2112.2016.01.011
      ZHENG Jinhua, YU Guo, and JIA Yue. Research on MOEA/D based on user-preference and alternate weight to solve the effect of reference point on multi-objective algorithms[J]. Acta Electronica Sinica, 2016, 44(1): 67–76. doi: 10.3969/j.issn.0372-2112.2016.01.011

    8. [8]

      BADER J and 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

    9. [9]

      CHENG Ran, JIN Yaochu, OLHOFER M, et al. A reference vector guided evolutionary algorithm for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2016, 20(5): 773–791. doi: 10.1109/TEVC.2016.2519378

    10. [10]

      ASAFUDDOULA M, SINGH H K, and RAY T. An enhanced decomposition-based evolutionary algorithm with adaptive reference vectors[J]. IEEE Transactions on Cybernetics, 2018, 48(8): 2321–2334. doi: 10.1109/TCYB.2017.2737519

    11. [11]

      LIU Yuan, ZHU Ningbo, LI Kenli, et al. An angle dominance criterion for evolutionary many-objective optimization[J]. Information Sciences, 2020, 509: 376–399. doi: 10.1016/J.INS.2018.12.078

    12. [12]

      HUBAND S, HINGSTON P, BARONE L, et al. A review of multiobjective test problems and a scalable test problem toolkit[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(5): 477–506. doi: 10.1109/TEVC.2005.861417

    13. [13]

      DEB K, THIELE L, LAUMANNS M, et al. Scalable test problems for evolutionary multiobjective optimization[M]. ABRAHAM A, JAIN L, and GOLDBERG R. Evolutionary Multiobjective Optimization. London: Springer, 2005: 105–145. doi: 10.1007/1-84628-137-7_6.

    14. [14]

      HERNÁNDEZ GÓMEZ R and COELLO COELLO C A. Improved metaheuristic based on the r2 indicator for many-objective optimization[C]. Proceedings of 2015 Annual Conference on Genetic and Evolutionary Computation. New York, USA: ACM, 2015: 679–686. doi: 10.1145/2739480.2754776.

    15. [15]

      DEB K. Multi-objective optimisation using evolutionary algorithms: An introduction[M]. WANG L H, NG A H C, and DEB K. Multi-Objective Evolutionary Optimisation for Product Design and Manufacturing. London: Springer, 2011: 3–34. doi: 10.1007/978-0-85729-652-8_1.

    16. [16]

      DEB K and GOYAL M. A combined genetic adaptive search (GeneAS) for engineering design[J]. Journal of Computer Science and Informatics, 1996, 26: 30–45.

    17. [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

    1. [1]

      毕晓君, 张倩. 基于分解的多目标进化算法的异构无线网络业务接入控制. 电子与信息学报,

    2. [2]

      毕晓君, 王朝. 一种基于角度惩罚距离的高维多目标进化算法. 电子与信息学报,

    3. [3]

      许川佩, 陈家栋, 万春霆. 基于云模型进化算法的硅通孔数量受约束的3D NoC测试规划研究. 电子与信息学报,

    4. [4]

      郁滨, 刘子清. ZigBee网络容忍恶意攻击的安全定位算法. 电子与信息学报,

    5. [5]

      骆剑平, 李霞, 陈泯融. 基于改进混合蛙跳算法的CVRP求解. 电子与信息学报,

    6. [6]

      王灿如, 田辉, 苗杰. 基于多目标进化的终端聚合选择算法研究. 电子与信息学报,

    7. [7]

      基于Hankel矩阵分解的天波超视距雷达机动目标检测算法. 电子与信息学报,

    8. [8]

      李阳阳, 焦李成. 量子免疫克隆多目标优化算法. 电子与信息学报,

    9. [9]

      金杉, 金志刚. 基于量子狼群进化的多目标汇聚节点覆盖算法. 电子与信息学报,

    10. [10]

      赵凤, 张咪咪, 刘汉强. 区域信息驱动的多目标进化半监督模糊聚类图像分割算法. 电子与信息学报,

    11. [11]

      丛琳, 焦李成, 沙宇恒. 正交免疫克隆粒子群多目标优化算法. 电子与信息学报,

    12. [12]

      赵春晖, 许云龙, 黄辉. 基于LU分解的稀疏目标定位算法. 电子与信息学报,

    13. [13]

      汪凯仁. 树形分解FFT算法. 电子与信息学报,

    14. [14]

      陈志坤, 杜康, 彭冬亮, 朱新挺. 基于混合三角变异差分进化算法的平面稀疏阵列约束优化. 电子与信息学报,

    15. [15]

      姚敏立, 王旭健, 张峰干, 戴定成. 基于动态参数差分进化算法的多约束稀布矩形面阵优化. 电子与信息学报,

    16. [16]

      毕晓君, 张磊. 基于自适应截断策略的约束多目标优化算法. 电子与信息学报,

    17. [17]

      刘焕淋, 李瑞艳, 孔德谦, 陈勇. 基于多目标遗传算法优化弹性光网络的多路径保护机制. 电子与信息学报,

    18. [18]

      肖乐意, 欧阳红林, 范朝冬. 基于记忆分子动理论优化算法的多目标截面投影Otsu图像分割. 电子与信息学报,

    19. [19]

      李斌, 钟润添, 肖金超, 庄镇泉. 一种基于边缘分布估计的多目标优化算法. 电子与信息学报,

    20. [20]

      吕增威, 魏振春, 韩江洪, 孙仁浩, 夏成凯. 基于多目标优化的无线传感器网络移动充电及数据收集算法. 电子与信息学报,

  • 图 1  两个目标下的角度支配准则

    图 2  各算法在15目标WFG1问题上获得的结果

    图 3  各算法在10目标WFG9问题上获得的结果

    表 1  DdrEA算法框架

     Input: N (种群规模)
     Output: P (最终种群)
     1 $V = \operatorname{UniformReferenceVector} (N)$;
     2 $P = \operatorname{RandomInitialize} (N)$;
     3  while 终止条件未满足 do
     4   ${\rm{Pool}} = \operatorname{bianryTournament} (P)$;
     5   $O = \operatorname{Variation} ({\rm{Pool}})$;
     6   $P = \operatorname{EnvironmentalSelection} (P \cup O,V,N)$;
     7  end while
    下载: 导出CSV

    表 2  环境选择算法框架

     Input: P (合并后的种群), V (参考向量);
     Output: Q (下一代种群);
     1 /*目标值标准化*/
     2 ${f_i}\;(p) = \frac{{{f_i}(p) - z_i^{{\rm{id}}}}}{{z_i^{{\rm{na}}} - z_i^{{\rm{id}}}}},\forall p \in P$;
     3 /*种群分解*/
     4 for $i = 1\;{\rm{to }}\left| P \right|$ do
     5  for $j = 1\;{\rm{to }}N$ do
     6   ${\theta _{i,j}} = \arccos \frac{{{f_i}\;(p) \cdot {v_j}}}{{\left\| {{f_i}\;(p)} \right\|}}$;
     7  end for
     8 end for
     9 for $i = 1\;{\rm{to }}\left| P \right|$ do
     10   $r = \arg \min {\theta _{i,j}},j \in \{ 1,2, ··· ,N\} $;
     11   ${\overline P _k} = {\overline P _k} \cup \{ {I_r}\} $;
     12 end for
     13 /*精英选择*/
     14 非支配排序获得每个解的AD等级;
     15 for $i = 1\;{\rm{to }}N$ do
     16  for $j = 1\;{\rm{to }}\left| {\overline {{P_k}} } \right|$ do
     17   ${\rm{fi}}{{\rm{t}}_{i,j}} = F_i^p + {\theta _{i,j}}$;
     18  end for
     19 end for
     20 for $i = 1\;{\rm{to }}N$ do
     21  $r = \arg \min {\rm{fi}}{{\rm{t}}_{i,j}}$
     22  $Q = Q \cup \{ {I_r}\} $
     23 end for
    下载: 导出CSV

    表 3  各算法在WFG测试集上独立运行30次的HV均值和标准差

    测试问题MDdrEANSGA-II/ADRVEAMOMBI-II
    WFG159.7500e-1 (3.88e-3)9.7759e-1 (1.72e-3) +9.9722e-1 (5.54e-4) +9.4668e-1 (5.46e-2) =
    109.9821e-1 (4.94e-4)9.9849e-1 (1.57e-4) +9.9768e-1 (5.30e-4) –9.9990e-1 (6.65e-5) +
    159.9960e-1 (2.23e-4)9.9977e-1 (5.94e-5) +9.9546e-1 (1.65e-2) –9.9900e-1 (9.15e-4) –
    WFG259.5980e-1 (4.39e-3)9.8390e-1 (6.84e-4) +9.9385e-1 (1.19e-3) +9.9432e-1 (2.64e-3) +
    109.9548e-1 (1.94e-3)9.9819e-1 (3.42e-4) +9.8944e-1 (2.64e-3) –9.9459e-1 (4.80e-3) =
    159.9516e-1 (3.28e-3)9.9854e-1 (4.21e-4) +9.7143e-1 (6.37e-3) –9.4784e-1 (4.42e-2) –
    WFG352.1343e-1 (1.95e-2)2.4953e-1 (4.42e-3) +1.5392e-1 (2.34e-2) –9.1612e-2 (1.14e-3) –
    109.2805e-2 (1.72e-2)7.7407e-2 (1.47e-2) –0.0000e+0 (0.00e+0) –8.8033e-2 (1.38e-2) =
    158.3502e-4 (3.18e-3)5.6841e-4 (2.97e-3) =0.0000e+0 (0.00e+0) =0.0000e+0 (0.00e+0) =
    WFG457.9321e-1 (6.31e-4)6.4860e-1 (1.20e-3) –7.9120e-1 (6.98e-4) –7.9039e-1 (7.50e-3) =
    109.6871e-1 (4.54e-4)8.3306e-1 (1.02e-3) –9.5997e-1 (2.21e-3) –9.2583e-1 (5.33e-2) –
    159.8842e-1 (4.27e-3)9.0197e-1 (2.24e-3) –9.7572e-1 (3.32e-3) –6.5742e-1 (6.09e-2) –
    WFG557.4375e-1 (4.53e-4)5.9898e-1 (9.69e-4) –7.4385e-1 (3.78e-4) =7.1661e-1 (1.18e-2) –
    109.0472e-1 (2.50e-4)7.6876e-1 (7.00e-4) –9.0333e-1 (3.03e-4) –8.2511e-1 (1.49e-2) –
    159.1756e-1 (2.50e-4)8.2982e-1 (1.15e-3) –9.1591e-1 (2.52e-4) –3.0980e-1 (1.03e-1) –
    WFG657.2159e-1 (1.32e-2)5.8627e-1 (1.86e-2) –7.2535e-1 (1.44e-2) =7.2502e-1 (2.91e-2) =
    108.8790e-1 (1.79e-2)7.4225e-1 (2.01e-2) –8.7718e-1 (1.67e-2) –8.6054e-1 (5.34e-2) –
    158.9955e-1 (2.46e-2)7.9363e-1 (2.38e-2) –7.2363e-1 (8.04e-2) –6.2650e-1 (5.72e-2) –
    WFG757.9404e-1 (5.38e-4)6.4353e-1 (1.20e-3) –7.8991e-1 (5.70e-4) –7.8952e-1 (8.36e-3) –
    109.6965e-1 (2.60e-4)8.2831e-1 (4.30e-3) –9.5835e-1 (1.80e-3) –9.6818e-1 (3.92e-3) =
    159.9072e-1 (9.04e-4)8.9903e-1 (1.10e-3) –9.8234e-1 (5.24e-3) –7.5033e-1 (8.01e-2) –
    WFG856.8107e-1 (1.14e-3)4.6230e-1 (5.93e-3) –6.7438e-1 (2.36e-3) –3.1772e-1 (6.41e-3) –
    108.7577e-1 (6.90e-3)6.0416e-1 (6.06e-2) –8.3098e-1 (8.86e-2) =6.4422e-1 (1.85e-2) –
    158.9925e-1 (1.56e-3)7.6855e-1 (6.04e-2) –7.7368e-1 (1.23e-1) –5.1932e-1 (7.33e-2) –
    WFG957.4084e-1 (4.55e-2)6.3546e-1 (3.05e-3) –7.5200e-1 (5.64e-3) =5.5025e-1 (5.88e-2) –
    109.0376e-1 (4.59e-2)8.1230e-1 (7.64e-3) –8.8746e-1 (3.28e-2) –8.0514e-1 (1.40e-2) –
    159.1408e-1 (3.94e-2)8.4483e-1 (3.67e-2) –8.3486e-1 (5.14e-2) –2.6009e-1 (3.09e-2) –
    $ + \;/\; - \;/\; = $7/19/12/20/52/18/7
    下载: 导出CSV

    表 4  各算法在DTLZ测试集上独立运行30次的HV均值和标准差

    测试问题MDdrEANSGA-II/ADRVEAMOMBI-II
    DTLZ158.4928e-1 (4.56e-2)9.0703e-1 (4.42e-3) +9.7490e-1 (1.72e-4) +9.7461e-1 (2.59e-4) +
    109.8958e-1 (5.26e-3)9.8084e-1 (1.48e-3) –9.9968e-1 (1.73e-5) +9.6198e-1 (3.15e-2) –
    159.1625e-1 (6.21e-2)9.9583e-1 (3.87e-4) +9.9990e-1 (4.62e-5) +9.0337e-1 (3.90e-2) –
    DTLZ257.9489e-1 (2.85e-4)7.1691e-1 (5.66e-3) –7.9479e-1 (3.56e-4) =7.9449e-1 (5.39e-4) –
    109.7092e-1 (2.45e-4)9.0347e-1 (4.42e-3) –9.6974e-1 (1.49e-4) –9.7085e-1 (2.13e-4) =
    159.9160e-1 (1.05e-4)9.5411e-1 (3.00e-3) –9.9109e-1 (2.99e-4) –8.8008e-1 (6.31e-2) –
    DTLZ356.2295e-1 (4.78e-2)7.1455e-1 (7.51e-3) =7.9246e-1 (2.06e-3) +7.9042e-1 (2.58e-3) +
    108.8458e-1 (2.77e-2)8.9986e-1 (5.59e-3) =9.6952e-1 (3.56e-4) +8.2910e-1 (9.36e-2) –
    157.0985e-1 (5.92e-2)9.4928e-1 (5.01e-3) +9.9072e-1 (2.96e-4) +5.5538e-1 (5.08e-2) –
    DTLZ457.9479e-1 (4.40e-4)7.2830e-1 (5.61e-3) –7.8505e-1 (2.91e-2) =7.8426e-1 (2.85e-2) –
    109.7157e-1 (2.23e-4)9.1475e-1 (4.07e-3) –9.6980e-1 (1.53e-4) –9.7226e-1 (2.24e-3) +
    159.9206e-1 (1.14e-4)9.6070e-1 (2.35e-3) –9.9076e-1 (1.18e-3) –9.9044e-1 (1.51e-3) –
    DTLZ551.0799e-1 (3.39e-3)1.2935e-1 (3.74e-4) +1.0483e-1 (2.04e-3) –9.0959e-2 (2.73e-4) –
    109.1644e-2 (1.16e-3)1.0062e-1 (2.77e-4) +9.0893e-2 (1.10e-4) –9.1359e-2 (7.19e-4) =
    159.1168e-2 (3.89e-4)9.4858e-2 (3.18e-4) +9.0648e-2 (3.24e-3) =9.1206e-2 (3.78e-4) =
    DTLZ651.0371e-1 (5.39e-3)1.2924e-1 (2.68e-4) +1.0340e-1 (1.29e-2) =9.0959e-2 (2.53e-4) –
    109.1619e-2 (8.82e-4)1.0053e-1 (2.70e-4) +9.1873e-2 (8.07e-4) =9.2808e-2 (1.11e-3) +
    159.1147e-2 (5.02e-4)9.4877e-2 (2.90e-4) +8.7721e-2 (1.72e-2) =9.1664e-2 (5.93e-4) +
    DTLZ752.4710e-1 (5.77e-3)2.3300e-1 (4.51e-3) –2.0265e-1 (3.05e-3) –2.4292e-1 (5.42e-3) –
    101.9578e-1 (2.23e-3)1.9180e-1 (3.40e-3) –1.4878e-1 (2.05e-2) –1.5877e-1 (1.00e-2) –
    151.6487e-1 (4.21e-3)1.5882e-1 (5.21e-3) –5.8918e-2 (5.77e-2) –1.2108e-1 (1.74e-3) –
    $ + \;/\; - \;/\; = $9/10/26/9/65/13/3
    下载: 导出CSV
  • 加载中
图(3)表(4)
计量
  • PDF下载量:  4
  • 文章访问数:  202
  • HTML全文浏览量:  43
文章相关
  • 通讯作者:  赵辉, zhaohui@cqupt.edu.cn
  • 收稿日期:  2019-08-05
  • 录用日期:  2020-02-13
  • 网络出版日期:  2020-03-25
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章