高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于分解和超平面拟合的进化超多目标优化降维算法

刘海林 肖俊荣

刘海林, 肖俊荣. 基于分解和超平面拟合的进化超多目标优化降维算法[J]. 电子与信息学报, 2022, 44(9): 3289-3298. doi: 10.11999/JEIT210605
引用本文: 刘海林, 肖俊荣. 基于分解和超平面拟合的进化超多目标优化降维算法[J]. 电子与信息学报, 2022, 44(9): 3289-3298. doi: 10.11999/JEIT210605
LIU Hailin, XIAO Junrong. Objective Reduction Algorithm Based on Decomposition and Hyperplane Approximation for Evolutionary Many-Objective Optimization[J]. Journal of Electronics & Information Technology, 2022, 44(9): 3289-3298. doi: 10.11999/JEIT210605
Citation: LIU Hailin, XIAO Junrong. Objective Reduction Algorithm Based on Decomposition and Hyperplane Approximation for Evolutionary Many-Objective Optimization[J]. Journal of Electronics & Information Technology, 2022, 44(9): 3289-3298. doi: 10.11999/JEIT210605

基于分解和超平面拟合的进化超多目标优化降维算法

doi: 10.11999/JEIT210605
基金项目: 国家自然科学基金(62172110),广东省科技计划项目(2021A0505110004, 2020A0505100056)
详细信息
    作者简介:

    刘海林:男,教授,主要研究方向为智能计算、无线网络规划与优化、机器学习

    肖俊荣:男, 硕士生,研究方向为智能计算

    通讯作者:

    刘海林 hlliu@gdut.edu.cn

  • 中图分类号: TP391.4

Objective Reduction Algorithm Based on Decomposition and Hyperplane Approximation for Evolutionary Many-Objective Optimization

Funds: The National Natural Science Foundation of China (62172110), The Program of Science and Technology of Guangdong Province (2021A0505110004, 2020A0505100056)
  • 摘要: 目标降维是研究超多目标优化问题的一个重要方向,它通过恰当的算法设计,能够剔除一些对求解优化问题冗余的目标,达到极大简化优化问题的效果。在超多目标优化降维问题中,前沿界面呈现非线性的情形是最普遍也是最难处理的降维问题。该文提出一种基于分解和超平面拟合的算法(DHA)来处理这类目标降维问题,通过对进化过程中种群的有效分解,使得在几何上非线性分布的非劣解集近似分解为多个近似线性分布的子集,再用系数是稀疏的超平面结合一些扰动项去拟合这些非劣解子集,最后根据该超平面提取出原问题的本质目标集,达到去除冗余目标的效果。为了检验提出算法的有效性,采用DTLZ5(I, m), WFG3(I, m)和MAOP(I, m)作为测试问题集,与代表当今水平的著名算法进行比较。计算机仿真结果表明该文提出的算法无论前沿界面是线性或非线性的情形都具有优异的性能。
  • 图  1  目标均非冗余时超平面拟和种群示意图

    图  2  存在冗余目标时超平面拟合种群示意图

    图  3  用超平面拟合非线性的种群分布的示意图

    图  4  多个平面拟合非线性种群分布示意图

    图  5  DHA对应不同的$ K $, $ \lambda $值在MAOP5(6,10)上的降维成功率曲面图

    图  6  不同种群大小下,DHA在相应问题的降维成功率变化图

    表  1  在线的进化目标降维算法DHA

     输入:多目标优化问题MOP,种群规模$ N $,迭代代数$ G $,PF子集个数$ K $,参数$ \lambda $。
     输出:多目标子集${\boldsymbol{F}}''$。
     主程序:
     步骤1 初试化:初始种群$ {P_0} $,令当前种群$ {P_c}{\text{ = }}{P_0} $,初始目标集${\boldsymbol{F}} = \left\{ { {f_1},\;{f_2},\; \cdots ,\;{f_m} } \right\}$。
     步骤2 采用MOEA对多目标优化问题运行$ G $代(本文采用基于分解的算法MOEA/D-M2M[17]来获取解集),记运行$ G $代后的种群为$ P' $,将
         $ P' $对应在目标空间的取值记为目标矩阵$ {\boldsymbol{A}} $;更新当前种群$ {P_c}{\text{ = }}P' $。根据$ P' $的取值范围调整MOEA/D-M2M的权重向量。
     步骤3 令$ \sigma $=$ {\text{10}} \times \lambda $,将$ {\boldsymbol{A}} $,$ \lambda $,$ K $和$ \sigma $作为输入,调用离线的DHA(表2)进行降维,将提取的目标集合记为$ {\boldsymbol{F'}} $。
     步骤4 将$ {\boldsymbol{F'}} $中的目标作为新的多目标优化问题,以${P_c}$为初始种群,调用进化算法进行求解。将运行$ G $代后种群记为$ P'' $,用$ P'' $组成的目
         标矩阵更新$ {\boldsymbol{A}} $,更新当前种群$ {P_c}{\text{ = }}P'' $。
     步骤5 对$ {\boldsymbol{A}} $调用离线的DHA(表2)进行降维,将提取的多目标子集记为${\boldsymbol{F}}''$,若${\boldsymbol{F}}''$的目标个数少于${\boldsymbol{F}}'$,则返回步骤4,否则输出多目标子
         集${\boldsymbol{F}}''$并结束。
    下载: 导出CSV

    表  2  离线的目标降维算法DHA

     输入:进化$ G $代后的目标矩阵${\boldsymbol{A}}$,参数$ \lambda $,子种群数$ K $。
     输出:多目标子集${\boldsymbol{F}}'$。
     主程序:
     步骤1 根据3.2节给出的分解方法对$ A $进行分解,得到$ K $个子种群对应的目标矩阵,记为${{\boldsymbol{H}}_i}$,$ i = 1,\;2,\; \cdots ,\;K $,再对每个子集独立归一
         化(将各个子种群视为整体)处理。
     步骤2 根据所给的参数$ \lambda $和步骤1得到的$ K $个目标矩阵${{\boldsymbol{H}}_i}$,($ i = 1,\;2,\; \cdots ,\;K $),求解凸优化问题式(3)得到解向量${\boldsymbol{w}}$(本文实验时使用
         cvx凸优化工具包,在软件MATLAB中进行求解)。
     步骤3 令${\boldsymbol{w}} = {\boldsymbol{w}}/{\text{max} }\left( {\boldsymbol{w}} \right)$,对于$ i = 1,\;2,\; \cdots ,\;m $,若$ {w_i} > 0.1 $,则${\boldsymbol{F}}' \cup \left\{ { {f_i} } \right\}$。输出${\boldsymbol{F}}'$。
    下载: 导出CSV

    表  3  降维算法参数表

    算法名称参数取值
    PCSEA[8]$ C $0.8
    greedy $\delta $-MOSS[10]$ \delta $0
    NL-MVU-PCA[1]$ q $$ M - 1 $
    LPCA[14]$ q $$ m - 1 $
    LHA[15]$ \lambda $1
    NLHA[15]$ \lambda $1
    下载: 导出CSV

    表  4  各算法在DTLZ5(I, m), WFG(I, m), MAOP(I, m)问题上的降维成功率

    测试问题LPCANLMVUPCAPCSEAgreedy $ \delta $-MOSSLHANLHADHA
    DTLZ5(2, 5)1.0001.0001.0000.6001.0001.0001.000
    DTLZ5(5, 10)1.0001.0001.0001.0001.0001.0001.000
    DTLZ5(7, 10)1.0000.7500.0001.0000.9501.0001.000
    DTLZ5(2, 20)1.0001.0001.0000.8001.0001.0001.000
    DTLZ5(5, 20)1.0001.0001.0001.0000.9500.9501.000
    DTLZ5(7, 20)1.0000.6500.0001.0000.9000.9500.900
    DTLZ5(2, 50)0.0001.0001.0000.7500.0000.3500.800
    WFG3(2, 15)1.0001.0001.0001.0000.9500.9500.850
    WFG3(5, 15)1.0000.6001.0001.0001.0001.0001.000
    WFG3(7, 15)1.0000.0500.0000.7501.0001.0001.000
    WFG3(2, 20)1.0001.0001.0001.0000.4000.4500.850
    WFG3(5, 20)1.0000.7001.0001.0000.8000.8000.950
    WFG3(7, 20)1.0000.0000.0000.8500.9500.9501.000
    WFG3(2, 25)0.0001.0001.0001.0000.6000.6000.700
    WFG3(5, 25)1.0000.7001.0001.0000.8500.9000.600
    WFG3(7, 25)1.0000.0000.0000.9500.9000.9001.000
    MAOP1(3, 5)0.0001.0001.0000.8501.0001.0001.000
    MAOP2(3, 5)0.0000.0001.0000.4501.0001.0001.000
    MAOP3(4, 10)0.0000.3500.9500.9501.0001.0001.000
    MAOP4(4, 10)0.0000.0000.0000.8500.1000.1000.400
    MAOP5(6, 10)0.0000.0000.0000.9000.5001.0001.000
    MAOP6(6, 10)0.0000.0000.0000.9000.0000.3000.900
    MAOP7(5, 15)0.0000.0000.0000.9000.9001.0001.000
    MAOP8(5, 15)0.0000.0000.0000.9500.0000.7000.850
    下载: 导出CSV

    表  5  各算法在DTLZ5(I, m)、WFG(I, m),MAOP(I, m)问题上的的平均$ {{\boldsymbol{\sigma}} ^ * } $

    测试问题LPCANLMVUPCAPCSEAgreedy $ \delta $-MOSSLHANLHADHA
    DTLZ5(2, 5)1.0001.0001.0000.8501.0001.0001.000
    DTLZ5(5, 10)1.0001.0001.0001.0001.0001.0001.000
    DTLZ5(7, 10)1.0000.7500.0001.0000.9501.0001.000
    DTLZ5(2, 20)1.0001.0001.0000.9891.0001.0001.000
    DTLZ5(5, 20)1.0001.0001.0001.0000.9970.9971.000
    DTLZ5(7, 20)1.0000.6500.0001.0000.9000.9960.986
    DTLZ5(2, 50)0.0001.0001.0000.9940.9550.9720.994
    WFG3(2, 15)1.0001.0001.0001.0000.9960.9960.985
    WFG3(5, 15)1.0000.6001.0001.0001.0001.0001.000
    WFG3(7, 15)1.0000.0500.0000.7501.0001.0001.000
    WFG3(2, 20)1.0001.0001.0001.0000.9670.9690.992
    WFG3(5, 20)1.0000.7001.0001.0000.9870.9870.997
    WFG3(7, 20)1.0000.0000.0000.8500.9960.9961.000
    WFG3(2, 25)0.0001.0001.0001.0000.9800.9800.987
    WFG3(5, 25)1.0000.7001.0001.0000.9930.9950.978
    WFG3(7, 25)1.0000.0000.0000.9500.9940.9941.000
    MAOP1(3, 5)0.0001.0001.0000.9251.0001.0001.000
    MAOP2(3, 5)0.5000.0001.0000.7251.0001.0001.000
    MAOP3(4, 10)0.5290.6500.9750.9921.0001.0001.000
    MAOP4(4, 10)0.0150.0000.9330.9750.9400.9400.960
    MAOP5(6, 10)0.3070.0250.5000.9750.8671.0001.000
    MAOP6(6, 10)0.7150.0960.4630.9840.9560.9740.995
    MAOP7(5, 15)0.1520.1110.4470.9900.9721.0001.000
    MAOP8(5, 15)0.5100.4600.6580.9950.8770.9690.964
    下载: 导出CSV

    表  6  DHA-MOEA/D-M2M与MOEA/D-M2M在各个测试函数独立运行20次的平均IGD值与标准差

    算法DTLZ5(5, 10)DTLZ5(2, 20)DTLZ5(5, 20)MAOP1(3, 5)MAOP3(4, 10)MAOP5(6, 10)
    MOEA/D-M2M2.11E-1(1.1E-2)1.61E-2(1.61E-2)3.09E-1(2.8E-2)6.23E-2(4.2E-3)1.45E-1(5.8E-3)1.56E-1(5.7E-3)
    DHA_MOEA/D-M2M1.74E-1(2.7E-3)2.10E-3(1.1E-3)1.74E-1(3.6E-3)6.36E-2(4.6E-3)1.17E-1(3.6E-3)1.32E-1(6.7E-3)
    下载: 导出CSV
  • [1] SAXENA D K, DURO J A, TIWARI A, et al. Objective reduction in many-objective optimization: Linear and nonlinear algorithms[J]. IEEE Transactions on Evolutionary Computation, 2013, 17(1): 77–99. doi: 10.1109/TEVC.2012.2185847
    [2] 赵辉, 王天龙, 刘衍舟, 等. 基于分解和支配关系的超多目标进化算法[J]. 电子与信息学报, 2020, 42(8): 1975–1981. doi: 10.11999/JEIT190589

    ZHAO Hui, WANG Tianlong, LIU Yanzhou, et al. Decomposition and dominance relation based many-objective evolutionary algorithm[J]. Journal of Electronics &Information Technology, 2020, 42(8): 1975–1981. doi: 10.11999/JEIT190589
    [3] 刘建昌, 李飞, 王洪海, 等. 进化高维多目标优化算法研究综述[J]. 控制与决策, 2018, 33(5): 879–887. doi: 10.13195/j.kzyjc.2017.1442

    LIU Jianchang, LI Fei, WANG Honghai, et al. Survey on evolutionary many-objective optimization algorithms[J]. Control and Decision, 2018, 33(5): 879–887. doi: 10.13195/j.kzyjc.2017.1442
    [4] YUAN Jiawei, LIU Hailin, GU Fangqing, et al. Investigating the properties of indicators and an evolutionary many-objective algorithm using promising regions[J]. IEEE Transactions on Evolutionary Computation, 2021, 25(1): 75–86. doi: 10.1109/TEVC.2020.2999100
    [5] CHEN Lu, WANG Handing, and MA Wenping. Two-stage multi-tasking transform framework for large-scale many-objective optimization problems[J]. Complex & Intelligent Systems, 2021, 7(3): 1499–1513. doi: 10.1007/s40747-021-00273-5
    [6] 毕晓君, 王朝. 一种基于角度惩罚距离的高维多目标进化算法[J]. 电子与信息学报, 2018, 40(2): 314–322. doi: 10.11999/JEIT170454

    BI Xiaojun and WANG Chao. A many-objective evolutionary algorithm based on angle penalized distance[J]. Journal of Electronics &Information Technology, 2018, 40(2): 314–322. doi: 10.11999/JEIT170454
    [7] MA Lianbo, HUANG Min, YANG Shengxiang, et al. An adaptive localized decision variable analysis approach to large-scale multiobjective and many-objective optimization[J]. IEEE Transactions on Cybernetics, 2022, 52(7): 6684–6696.
    [8] SINGH H K, ISAACS A, and RAY T. A pareto corner search evolutionary algorithm and dimensionality reduction in many-objective optimization problems[J]. IEEE Transactions on Evolutionary Computation, 2011, 15(4): 539–556. doi: 10.1109/TEVC.2010.2093579
    [9] CHEUNG Y M, GU Fangqing, and LIU Hailin. Objective extraction for many-objective optimization problems: Algorithm and test problems[J]. IEEE Transactions on Evolutionary Computation, 2016, 20(5): 755–772. doi: 10.1109/TEVC.2016.2519758
    [10] BROCKHOFF D and ZITZLER E. Objective reduction in evolutionary multiobjective optimization: Theory and applications[J]. Evolutionary Computation, 2009, 17(2): 135–166. doi: 10.1162/evco.2009.17.2.135
    [11] YUAN Yuan, ONG Y S, GUPTA A, et al. Objective reduction in many-objective optimization: Evolutionary multiobjective approaches and comprehensive analysis[J]. IEEE Transactions on Evolutionary Computation, 2018, 22(2): 189–210. doi: 10.1109/TEVC.2017.2672668
    [12] QIN Yingjie, ZHENG Jiehui, LI Zhigang, et al. Reduction of non-linear many objectives for coordinated operation of integrated energy systems[J]. International Journal of Electrical Power & Energy Systems, 2020, 117: 105657. doi: 10.1016/j.ijepes.2019.105657
    [13] 陈小红, 李霞, 王娜. 高维多目标优化中基于稀疏特征选择的目标降维方法[J]. 电子学报, 2015, 43(7): 1300–1307. doi: 10.3969/j.issn.0372-2112.2015.07.008

    CHEN Xiaohong, LI Xia, and WANG Na. Objective reduction with sparse feature selection for many objective optimization problem[J]. Acta Electronica Sinica, 2015, 43(7): 1300–1307. doi: 10.3969/j.issn.0372-2112.2015.07.008
    [14] SAXENA D K and DEB K. Non-linear dimensionality reduction procedures for certain large-dimensional multi-objective optimization problems: Employing correntropy and a novel maximum variance unfolding[C]. The 4th International Conference on Evolutionary Multi-Criterion Optimization, Matsushima, Japan, 2007: 772–787.
    [15] LI Yifan, LIU Hailin, and GOODMAN E D. Hyperplane-approximation-based method for many-objective optimization problems with redundant objectives[J]. Evolutionary Computation, 2019, 27(2): 313–344. doi: 10.1162/evco_a_00223
    [16] LIU Hailin, CHEN Lei, ZHANG Qingfu, et al. An evolutionary many-objective optimisation algorithm with adaptive region decomposition[C]. 2016 IEEE Congress on Evolutionary Computation, Vancouver, Canada, 2016: 4763–4769.
    [17] LIU Hailin, GU Fangqing, and ZHANG Qingfu. Decomposition of a multiobjective optimization problem into a number of simple multiobjective subproblems[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(3): 450–455. doi: 10.1109/TEVC.2013.2281533
    [18] BOSMAN P A N and 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
  • 加载中
图(6) / 表(6)
计量
  • 文章访问数:  184
  • HTML全文浏览量:  57
  • PDF下载量:  43
  • 被引次数: 0
出版历程
  • 收稿日期:  2021-06-21
  • 录用日期:  2022-03-10
  • 修回日期:  2022-01-23
  • 网络出版日期:  2022-03-19
  • 刊出日期:  2022-09-19

目录

    /

    返回文章
    返回