留言板

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

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

基于构造学习的差分进化算法求解部分可分优化问题

陈作汉 曹洁 赵付青 张建林

陈作汉, 曹洁, 赵付青, 张建林. 基于构造学习的差分进化算法求解部分可分优化问题[J]. 电子科技大学学报, 2023, 52(3): 413-422. doi: 10.12178/1001-0548.2022082
引用本文: 陈作汉, 曹洁, 赵付青, 张建林. 基于构造学习的差分进化算法求解部分可分优化问题[J]. 电子科技大学学报, 2023, 52(3): 413-422. doi: 10.12178/1001-0548.2022082
CHEN Zuohan, CAO Jie, ZHAO Fuqing, ZHANG Jianlin. A Constructive Learning Differential Evolution Algorithm for Partially Separable Function Optimization Problems[J]. Journal of University of Electronic Science and Technology of China, 2023, 52(3): 413-422. doi: 10.12178/1001-0548.2022082
Citation: CHEN Zuohan, CAO Jie, ZHAO Fuqing, ZHANG Jianlin. A Constructive Learning Differential Evolution Algorithm for Partially Separable Function Optimization Problems[J]. Journal of University of Electronic Science and Technology of China, 2023, 52(3): 413-422. doi: 10.12178/1001-0548.2022082

基于构造学习的差分进化算法求解部分可分优化问题

doi: 10.12178/1001-0548.2022082
基金项目: 国家重点研发计划(2020YFB1713600);国家自然科学基金(62063021)
详细信息
    作者简介:

    陈作汉(1979 − ),男,博士生,主要从事智能优化算法和无线传感网络等方面的研究

    通讯作者: 陈作汉,E-mail:chenzh@lut.edu.cn
  • 中图分类号: TP18

A Constructive Learning Differential Evolution Algorithm for Partially Separable Function Optimization Problems

  • 摘要: 复杂优化问题中决策变量之间的依赖性导致函数适应度地形中存在大量的局部最优解,传统进化算法求解此类问题相对困难。提出一种求解部分可分函数优化问题的构造学习差分进化算法CLSHADE。该算法首先利用差分分组技术将复杂问题解耦划分为多个子问题,降低问题复杂程度;然后基于分组结构设计一种构造学习策略,以一定概率向构造的最优解学习以引导种群的搜索方向,提高算法搜索性能。在CEC 2017部分可分测试函数上的实验结果表明了CLSHADE的有效性。
  • 图  1  算法总体框架

    图  2  参数主效应图

    图  3  Rastrigin’s函数的适应度地形图

    4  10维问题部分函数收敛曲线

    图  5  10维问题部分函数解的分布盒图

    表  1  参数水平设置

    参数水平
    1234
    $ M_{F} $0.30.50.70.9
    ${M_{ {{{{\rm{Cr}}}}} } }$0.30.50.70.9
    $\varphi$0.350.450.550.65
    下载: 导出CSV

    表  2  参数方差分析结果

    SourceSum of
    squares
    Degrees of
    freedom
    Mean SquareF-ratiop-value
    ${M_F}$0.41030.1370.430.7303
    ${M_{ { { {{\rm{Cr}}} } } } }$0.59130.1970.630.6045
    $\varphi $1.54930.5161.640.2033
    ${M_F}*{M_{ { { {{\rm{Cr}}} } } } }$2.78090.3090.980.4771
    ${M_F}*\varphi $2.25990.2510.80.6216
    ${M_{ {{\rm{Cr}}} } }*\varphi$0.78290.8680.280.9760
    Error8.498270.315
    Total16.86963
    下载: 导出CSV

    表  3  Rastrigin’s函数的构造学习数据

    ${{\boldsymbol{X}}_{{{\rm{pbest}}} }}$$ {x_1} $$ {x_2} $$ {x_3} $$ {x_4} $$ {x_5} $$ {x_6} $$F({\boldsymbol{x}})$
    1−43.6726.11−28.75−79.55−38.5171.29535.73
    2−22.06−4.1849.64−13.9319.720.24538.07
    3−32.9418.91−28.04−14.4222.0783.43540.03
    437.8070.86−60.65−26.2349.6712.95541.39
    5−68.07−39.78−27.09−42.7425.8274.39541.48
    623.3683.11−8.96−97.3117.7031.17541.90
    710.4816.7338.6938.4413.00−37.07542.02
    8−21.8118.7827.74−42.74−3.6028.81545.09
    9−87.7360.5716.1541.29−35.96−8.70545.45
    10−40.6398.6572.8531.9734.68−24.68546.14
    11−15.94−33.6524.52−62.09−24.69−22.56547.46
    1224.66−46.4720.06-64.4944.7114.16547.82
    $ {{\boldsymbol{X}}_{{{\rm{lpbest}}} }} $23.3683.1120.06−64.4944.7114.16512.49
    下载: 导出CSV

    表  4  10维问题实验结果

    FuncSHADEMeanstdAMECoDEsMeanstdHS-ESMeanstdEBLSHADEMeanstdCLSHADEMeanstd
    10.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+00
    20.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+00
    30.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+00
    40.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+00
    52.05E+008.06E−017.14E+002.85E+005.66E−017.24E−011.97E+007.83E−017.70E−017.70E−01
    60.00E+000.00E+004.60E−063.42E−060.00E+000.00E+000.00E+000.00E+000.00E+000.00E+00
    71.20E+015.69E−011.65E+012.77E+001.13E+017.82E−011.19E+014.66E−011.06E+011.06E+01
    82.19E+008.45E−016.52E+002.74E+006.83E−017.57E−012.24E+007.92E−011.68E−011.68E−01
    90.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+00
    101.26E+012.38E+011.58E+021.24E+021.13E+021.49E+028.47E+007.94E+004.67E−014.67E−01
    110.00E+000.00E+001.03E+009.58E−011.81E+008.55E+001.20E−038.56E−030.00E+000.00E+00
    121.45E+013.98E+011.25E+013.67E+012.88E+015.94E+012.45E−011.80E−019.52E+009.52E+00
    133.08E+002.31E+004.31E+001.98E+003.32E+002.46E+003.26E+002.29E+003.13E+003.13E+00
    141.93E−021.29E−011.75E+001.38E+005.11E+001.84E+013.08E−031.64E−029.35E−049.35E−04
    155.52E−031.91E−021.20E−013.00E−016.13E−016.26E−016.67E−021.60E−012.53E−022.53E−02
    161.25E−011.65E−016.04E−011.53E+005.10E+003.04E+011.66E−012.11E−017.51E−027.51E−02
    178.89E−031.43E−021.27E+008.30E−011.39E+011.15E+011.63E−024.96E−023.20E−033.20E−03
    187.61E−021.66E−016.05E−022.36E−014.48E−011.85E−017.53E−021.47E−015.40E−025.40E−02
    196.03E−053.30E−043.59E−024.41E−028.79E−014.49E+001.02E−087.31E−084.85E−084.85E−08
    200.00E+000.00E+008.68E−021.94E−011.31E+019.60E+000.00E+000.00E+000.00E+000.00E+00
    下载: 导出CSV

    表  5  30维问题实验结果

    FuncSHADEMeanstdAMECoDEsMeanstdHS-ESMeanstdEBLSHADEMeanstdCLSHADEMeanstd
    10.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+00
    20.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+00
    30.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+00
    45.87E+017.78E−015.89E+011.32E+005.29E+001.20E+015.86E+010.00E+005.86E+010.00E+00
    55.81E+001.16E+002.80E+011.07E+018.29E+003.18E+005.48E+001.23E+002.84E+009.01E−01
    66.71E−104.79E−091.07E−083.72E−080.00E+000.00E+000.00E+000.00E+000.00E+000.00E+00
    73.71E+019.51E−015.63E+019.29E+004.07E+016.57E+003.63E+019.61E−013.47E+016.11E−01
    86.37E+001.17E+002.60E+011.13E+017.96E+002.29E+006.07E+001.44E+003.19E+008.40E−01
    90.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+00
    101.21E+031.85E+021.60E+035.33E+029.90E+023.88E+021.07E+031.56E+025.99E+021.11E+02
    111.67E+012.41E+012.16E+012.41E+011.59E+012.42E+011.93E+012.62E+011.45E+012.22E+01
    129.68E+023.57E+029.47E+023.45E+023.46E+018.72E+018.16E+022.98E+029.32E+022.99E+02
    131.33E+015.19E+002.11E+018.54E+001.53E+014.30E+001.15E+016.46E+001.32E+014.84E+00
    145.88E+008.83E+002.35E+018.05E+001.43E+019.95E+008.92E+009.69E+003.97E+007.28E+00
    151.97E+001.48E+006.31E+003.04E+003.60E+003.28E+001.46E+001.09E+001.24E+009.96E−01
    162.06E+014.03E+004.75E+022.07E+022.38E+021.66E+021.41E+012.98E+002.19E+014.71E+00
    172.37E+016.26E+003.06E+014.55E+013.53E+016.28E+012.19E+015.57E+001.48E+013.04E+00
    181.97E+014.74E+002.59E+016.39E+001.93E+014.96E+001.91E+015.27E+001.85E+016.38E+00
    191.65E+007.67E−014.68E+001.53E+004.06E+002.49E+001.80E+009.36E−011.99E+008.61E−01
    202.17E+015.88E+002.76E+011.98E+011.67E+027.53E+011.81E+016.52E+001.76E+014.30E+00
    下载: 导出CSV

    表  6  Wilcoxon检验结果

    $维$CLSHADE vsR+R−Zp-value$\alpha = 0.1$$\alpha = 0.05$
    10SHADE17.0074.00−1.9920.046YesYes
    AMECoDEs0.00120.00−3.4080.001YesYes
    HS-ES1.00104.00−3.2330.001YesYes
    EBLSHADE26.0079.00−1.6640.096YesYes
    30SHADE11.00125.00−2.9480.003YesYes
    AMECoDEs0.00136.00−3.5160.000YesYes
    HS-ES26.0094.00−1.9310.053YesNo
    EBLSHADE32.0073.00−1.2870.198NoNo
    下载: 导出CSV
  • [1] MA X, LI X, ZHANG Q, et al. A survey on cooperative co-evolutionary algorithms[J]. IEEE Transactions on Evolutionary Computation, 2019, 23(3): 421-441. doi:  10.1109/TEVC.2018.2868770
    [2] LI J Y, ZHAN Z H, WANG H, et al. Data-Driven evolutionary algorithm with perturbation-based ensemble surrogates[J]. IEEE Transactions on Cybernetics, 2021, 51(8): 3925-3937. doi:  10.1109/TCYB.2020.3008280
    [3] LI S, GONG W, YAN X, et al. Parameter estimation of photovoltaic models with memetic adaptive differential evolution[J]. Solar Energy, 2019, 190: 465-474. doi:  10.1016/j.solener.2019.08.022
    [4] STORN R, PRICE K. Differential evolution: A simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization, 1997, 11(4): 341-359. doi:  10.1023/A:1008202821328
    [5] QIN A K, HUANG V L, SUGANTHAN P N. Differential evolution algorithm with strategy adaptation for global numerical optimization[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(2): 398-417. doi:  10.1109/TEVC.2008.927706
    [6] ZHANG J, SANDERSON A C. JADE: Adaptive differential evolution with optional external archive[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(5): 945-958. doi:  10.1109/TEVC.2009.2014613
    [7] TANABE R, FUKUNAGA A. Success-History based parameter adaptation for differential evolution[C]//IEEE Congress on Evolutionary Computation (CEC 2013). [S.l.]: IEEE, 2013: 71-78.
    [8] DAS S, MULLICK S S, SUGANTHAN P N. Recent advances in differential evolution: An updated survey[J]. Swarm and Evolutionary Computation. 2016, 27: 1-30.
    [9] 陈作汉, 曹洁, 赵付青, 等. 基于搜索偏好知识的复杂多模差分进化算法[J]. 电子科技大学学报, 2020, 49(6): 875-882.

    CHEN Z H, CAO J, ZHAO F Q, et al. Complex multimodal differential evolution algorithm based on search preference knowledge[J]. Journal of the University of Electronic Science and Technology of China, 2020, 49(6): 875-882.
    [10] WANG S H, LI Y Z, YANG H Y. Self-Adaptive mutation differential evolution algorithm based on particle swarm optimization[J]. Applied Soft Computing. 2019, 81(8): 1-22.
    [11] OPARA K, JAROSłA W. Comparison of mutation strategies in differential evolution: A probabilistic perspective[J]. Swarm and Evolutionary Computation, 2018, 39: 53-69. doi:  10.1016/j.swevo.2017.12.007
    [12] CHENG R, OMIDVAR M N, GANDOMI A H, et al. Solving incremental optimization problems via cooperative coevolution[J]. IEEE Transactions on Evolutionary Computation, 2019, 23(5): 762-775. doi:  10.1109/TEVC.2018.2883599
    [13] QIANG Y, CHEN W N, GU T, et al. Segment-Based predominant learning swarm optimizer for large-scale optimization[J]. IEEE Transactions on Cybernetics, 2016, 47(9): 1-15.
    [14] OMIDVAR M N, MING Y, YI M, et al. DG2: A faster and more accurate differential grouping for large-scale black-box optimization[J]. IEEE Transactions on Evolutionary Computation, 2019, 21(6): 929-942.
    [15] OMIDVAR M N, LI X, MEI Y, et al. Cooperative co-evolution with differential grouping for large scale optimization[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(3): 378-393. doi:  10.1109/TEVC.2013.2281543
    [16] AWAD N H, ALI M Z, SUGANTHAN P N, et al. Problem definitions and evaluation criteria for the CEC 2017 special session and competition on single objective real-parameter numerical optimization[R]. Singapore: Nanyang Techndogcal University, 2016.
    [17] ANGELA M D, DANIEL T V. Design and analysis of experiments[M]. Cham: Springer, 2017.
    [18] CUI L, LI G, ZHU Z, et al. Adaptive multiple-elites-guided composite differential evolution algorithm with a shift mechanism[J]. Information Sciences, 2018, 422(1): 122-143.
    [19] GENG Z, SHI Y. Hybrid sampling evolution strategy for solving single objective bound constrained problems[C]//IEEE Congress on Evolutionary Computation (CEC 2018). [S.l.]: IEEE, 2018: 1-7.
    [20] MOHAMED A W, HADI A A, JAMBI K M. Novel mutation strategy for enhancing SHADE and LSHADE algorithms for global numerical optimization[J]. Swarm and Evolutionary Computation, 2019, 50(11): 1-14.
  • [1] 高远翔, 罗龙, 孙罡.  基于强化学习的多阶段网络分组路由方法 . 电子科技大学学报, 2022, 51(2): 200-206. doi: 10.12178/1001-0548.2021260
    [2] 王静, 雷珂, 李家仪, 田松涛, 王相隆.  基于非均匀循环编码的分组修复码构造 . 电子科技大学学报, 2022, 51(1): 57-64. doi: 10.12178/1001-0548.2021013
    [3] 王永, 冉珣, 尹恩民, 王利.  满足差分隐私保护的矩阵分解推荐算法 . 电子科技大学学报, 2021, 50(3): 405-413. doi: 10.12178/1001-0548.2020359
    [4] 王静, 孙伟, 何亚锦, 沈克勤, 张鑫楠, 刘向阳.  基于Hadamard矩阵构造部分重复码 . 电子科技大学学报, 2021, 50(2): 173-179. doi: 10.12178/1001-0548.2020028
    [5] 陈作汉, 曹洁, 赵付青, 张建林.  基于搜索偏好知识的复杂多模差分进化算法 . 电子科技大学学报, 2020, 49(6): 875-882. doi: 10.12178/1001-0548.2020153
    [6] 陈伟建, 赵思宇, 邹瑞杰, 张晓宁.  PRESENT密码的差分故障攻击 . 电子科技大学学报, 2019, 48(6): 865-869. doi: 10.3969/j.issn.1001-0548.2019.06.010
    [7] 王永娟, 张诗怡, 王涛, 高杨.  对MIBS分组密码的差分故障攻击 . 电子科技大学学报, 2018, 47(4): 601-605. doi: 10.3969/j.issn.1001-0548.2018.04.020
    [8] 孙萍, 晏明国, 张鸿泽, 黄琦, 周林, 赵苡, 彭富刚, 刘培良.  差分脉冲阳极溶出伏安法检测重金属离子 . 电子科技大学学报, 2017, 46(5): 784-789. doi: 10.3969/j.issn.1001-0548.2017.05.022
    [9] 熊瑾煜, 杨宇翔, 夏畅雄, 陈鲸.  低轨双星定位中雷达信号时频差快速估计算法 . 电子科技大学学报, 2015, 44(3): 326-332. doi: 10.3969/j.issn.1001-0548.2015.03.002
    [10] 孙春辉, 李晖, 杨旸, 朱辉.  PRESENT密码算法的差分电磁攻击研究 . 电子科技大学学报, 2013, 42(3): 344-349. doi: 10.3969/j.issn.1001-0548.2013.03.005
    [11] 陈宗荣.  复合变型Bessel方程的一类边值问题的相似构造算法设计 . 电子科技大学学报, 2012, 41(3): 459-462. doi: 10.3969/j.issn.1001-0548.2012.03.026
    [12] 高洋, 葛建华, 谢大平.  双差分协作传输的误码率性能分析和最佳功率分配 . 电子科技大学学报, 2011, 40(2): 185-191. doi: 10.3969/j.issn.1001-0548.2011.02.005
    [13] 叶笠, 王厚军, 叶芃, 田书林.  容差模拟电路诊断中故障隔离的几何方法 . 电子科技大学学报, 2011, 40(1): 53-57. doi: 10.3969/j.issn.1001-0548.2011.01.010
    [14] 滕云龙, 师奕兵, 郑植.  接收机钟差灰色马尔可夫预测模型研究 . 电子科技大学学报, 2011, 40(2): 242-245. doi: 10.3969/j.issn.1001-0548.2011.02.017
    [15] 董彬虹, 唐诚, 李少谦.  基于状态网格图的差分跳频G函数构造方法研究 . 电子科技大学学报, 2011, 40(4): 497-500.
    [16] 张贤勇, 熊方, 莫智文, 程伟.  程度与精度的逻辑差粗糙集模型 . 电子科技大学学报, 2010, 39(5): 783-787. doi: 10.3969/j.issn.1001-0548.2010.05.028
    [17] 崔梦天, 张世禄, 赵海军.  线性矩阵不等式问题的进化计算解决方法 . 电子科技大学学报, 2005, 34(2): 265-268.
    [18] 杨新勇, 黄圣国.  磁罗盘的罗差分析与验证 . 电子科技大学学报, 2004, 33(5): 547-550.
    [19] 董彬虹, 李少谦, 陈智, 彭守贵.  差分跳频信号最佳接收机设计 . 电子科技大学学报, 2003, 32(5): 530-534.
    [20] 刘华, 胡渝, 刘盛纲.  初级球差激光扫描系统的设计分析 . 电子科技大学学报, 1998, 27(5): 487-490.
  • 加载中
图(7) / 表(6)
计量
  • 文章访问数:  4369
  • HTML全文浏览量:  1330
  • PDF下载量:  80
  • 被引次数: 0
出版历程
  • 收稿日期:  2022-03-21
  • 修回日期:  2022-04-10
  • 录用日期:  2023-01-21
  • 网络出版日期:  2023-05-26
  • 刊出日期:  2023-05-28

基于构造学习的差分进化算法求解部分可分优化问题

doi: 10.12178/1001-0548.2022082
    基金项目:  国家重点研发计划(2020YFB1713600);国家自然科学基金(62063021)
    作者简介:

    陈作汉(1979 − ),男,博士生,主要从事智能优化算法和无线传感网络等方面的研究

    通讯作者: 陈作汉,E-mail:chenzh@lut.edu.cn
  • 中图分类号: TP18

摘要: 复杂优化问题中决策变量之间的依赖性导致函数适应度地形中存在大量的局部最优解,传统进化算法求解此类问题相对困难。提出一种求解部分可分函数优化问题的构造学习差分进化算法CLSHADE。该算法首先利用差分分组技术将复杂问题解耦划分为多个子问题,降低问题复杂程度;然后基于分组结构设计一种构造学习策略,以一定概率向构造的最优解学习以引导种群的搜索方向,提高算法搜索性能。在CEC 2017部分可分测试函数上的实验结果表明了CLSHADE的有效性。

English Abstract

陈作汉, 曹洁, 赵付青, 张建林. 基于构造学习的差分进化算法求解部分可分优化问题[J]. 电子科技大学学报, 2023, 52(3): 413-422. doi: 10.12178/1001-0548.2022082
引用本文: 陈作汉, 曹洁, 赵付青, 张建林. 基于构造学习的差分进化算法求解部分可分优化问题[J]. 电子科技大学学报, 2023, 52(3): 413-422. doi: 10.12178/1001-0548.2022082
CHEN Zuohan, CAO Jie, ZHAO Fuqing, ZHANG Jianlin. A Constructive Learning Differential Evolution Algorithm for Partially Separable Function Optimization Problems[J]. Journal of University of Electronic Science and Technology of China, 2023, 52(3): 413-422. doi: 10.12178/1001-0548.2022082
Citation: CHEN Zuohan, CAO Jie, ZHAO Fuqing, ZHANG Jianlin. A Constructive Learning Differential Evolution Algorithm for Partially Separable Function Optimization Problems[J]. Journal of University of Electronic Science and Technology of China, 2023, 52(3): 413-422. doi: 10.12178/1001-0548.2022082
  • 现代工程实践和生产经营等领域存在大量的复杂优化问题,如流程制造车间过程控制、复杂工业环境生产调度、航空发动机控制及生物学中的基因网络等[1]。这些问题往往具有非线性、多模态、决策变量之间耦合程度高等特点,传统优化方法求解上述问题的表现并不理想。进化算法为解决此类复杂优化问题提供了新的思路[2-3]

    差分进化[4](differential evolution, DE)算法由于原理简单、控制参数少及鲁棒性高等优点,得到了广泛关注。目前,针对DE算法的改进主要集中在3个方面。1) DE参数的自适应策略研究,由于控制参数对算法性能有重要影响,围绕DE的关键参数如缩放因子$F$、交叉概率${\rm{Cr}}$和种群规模${{\rm{NP}}} $等产生了大量的研究结果,如SaDE[5]、JADE[6]及SHADE[7]等。2)从变异策略方面对DE算法进行改进,通过参与变异个体选择、差分扰动项、向最优解学习项等的变化产生了如DE/rand/1、DE/best/1、DE/best/2、DE/rand/2、DE/current-to-best/1等大量有代表性的研究成果[8-9]。3)结合其他算法如PSO[10],CMA-ES[11]等,融入其他算法的优点从种群初始化、个体选择、进化过程等方面提升DE的性能。

    尽管大量DE及其改进算法展现出了良好的性能,然而随着决策变量的增加及决策变量之间存在大量复杂耦合关系,算法的求解性能出现一定程度的下降,甚至部分复杂优化问题的最优解依然没有找到。另一方面,耦合决策变量之间的交互关系没有进行解耦分析以降低问题复杂程度,决策变量间的结构信息也没有得到充分的挖掘和利用,而这些信息往往对降低问题复杂度和指导种群搜索方向有较大帮助[12-13]

    基于以上分析,本文针对决策变量部分可分离复杂优化函数问题,基于“分而治之”思想采用差分分组策略对耦合决策变量进行解耦分组,形成多个没有依赖关系的简单子问题,然后设计一种构造学习策略,利用多个优秀个体的潜在有用信息,以每个子问题的优秀维度组合构造当前种群的最优解,引导种群向构造的最优解学习,提高算法的搜索性能,为解决具有复杂多变量耦合特征的部分可分优化问题提供基于差分进化算法的解决方法。

    • 本文引入差分分组(differential grouping, DG2)[14]策略,基于算法SHADE(success-history based adaptive DE)[7]进行改进,以下分别进行介绍。

    • SHADE算法包含初始化、变异、交叉和选择等步骤。首先在问题的可行域中随机产生${{\rm{NP}}} $$D$维向量构成初始种群:

      $$ {{\boldsymbol{X}}_i} = ({x_1},{x_2}, \cdots {x_D})\;\;\;\;i = 1,2, \cdots ,{\text{NP}} $$ (1)

      变异操作是DE算法的核心操作,目前已有许多经典的变异策略,SHADE算法采用DE/current-to-pbest/1变异策略:

      $$ {\boldsymbol{V}}_i^t = {\boldsymbol{X}}_i^t + F({\boldsymbol{X}}_{{{\rm{pbest}}} }^t - {\boldsymbol{X}}_i^t) + F({\boldsymbol{X}}_{r1}^t - {\boldsymbol{X}}_{r2}^t) $$ (2)

      式中,$t$为当前进化代数;$ {r_1} $$ {r_2} $随机从$[1,{{\rm{NP}}} ]$中选取且与$i$互不相等;$F$为缩放因子;$ {\boldsymbol{X}}_{{{\rm{pbest}}} }^t $随机从${{\rm{NP}}} \times p(p \in [0.11,0.2])$个当前种群的最优解中选取。SHADE采用一个外部存档存储保存部分较差的个体以增加种群的多样性。式(2)表明DE/current-to-pbest/1变异策略包含了差分扰动和向优秀解学习两部分,$ F({\boldsymbol{X}}_{r1}^t - {\boldsymbol{X}}_{r2}^t) $为扰动项,且$ {\boldsymbol{X}}_{r2}^t $从外部存档和当前种群的合集中随机选取。$ F({\boldsymbol{X}}_{{{\rm{pbest}}} }^t - {\boldsymbol{X}}_i^t) $为向当前优秀解学习项。如果变异向量$ V_i^t $超出问题的可行域,则执行以下操作:

      $$ {\boldsymbol{V}}_{i,j}^t = \left\{ {\begin{array}{*{20}{l}} {({x_{j,\min }} + x_{i,j}^t)/2\;\;\;\;\;{{\boldsymbol{V}}}_{i,j}^t < {x_{j,\min }}} \\ {({x_{j,\max }} + x_{i,j}^t)/2\;\;\;\;\;{{\boldsymbol{V}}}_{i,j}^t > {x_{j,\max }}} \end{array}} \right.\; $$ (3)

      交叉操作将变异向量和父代向量进行交叉,形成实验向量:

      $$ {\boldsymbol{U}}_{i,j}^t = \left\{ {\begin{array}{*{20}{c}} {\boldsymbol{V}}_{i,j}^t & j = {j_{{\text{rand}}}} \; {{\rm{or}}} \; {{\rm{rand}}} (0,1) \leqslant {{\rm{Cr}}} \\ {\boldsymbol{X}}_{i,j}^t & {{\rm{otherwise}}} \end{array}} \right. $$ (4)

      式中,$ {{\rm{Cr}}} $是交叉概率;$ {j_{{\rm{rand}}}} $$ \left[ {1,{D} } \right] $之间随机选取。然后从目标向量和实验向量中选择适应度较小(以最小化问题为例)的个体进入下一代种群,如下所示:

      $$ {\boldsymbol{U}}_{i,j}^t = \left\{ {\begin{array}{*{20}{c}} {{\boldsymbol{U}}^t} & f({{\boldsymbol{U}}^t}) \leqslant f({\boldsymbol{X}}_i^t) \\ {\boldsymbol{X}}_i^t & {{\rm{otherwise}}} \end{array}} \right. $$ (5)

      参数控制机制对算法的搜索性能起着至关重要的作用,SHADE采用一种基于成功历史的自适应策略,将进化过程中成功的$H$个缩放因子$F$和交叉概率$ {{\rm{Cr}}} $保存在${M_{{{{\rm{Cr}}}}}}$${M_F}$中以供选择。参数$F$服从柯西分布$C({\mu _F},0.1)$${\mu _F}$的初值为0.5,更新如下:

      $$ {\mu _F} = (1 - c) {\mu _F} + c {\text{mea}}{{\text{n}}_L}({S_F}) $$ (6)

      式中,${S_F}$为子代成功取代父代时参数$F$的集合,$ {\rm{mea}}{{\rm{n}}_L}({S_F}) $为Lehmer均值。类似地,交叉概率$ {{\rm{Cr}}} $服从正态分布$N({\mu _{{{{{\rm{Cr}}}}} }},0.1)$${\mu _{{{{{\rm{Cr}}}}} }}$的初值为0.5,更新如下:

      $$ {\mu _{{{{{\rm{Cr}}}}} }} = (1 - c) {\mu _{{{{{\rm{Cr}}}}} }} + c {{{\rm{mean}}} _A}({S_{ {\rm{Cr}}}}) $$ (7)

      式中,${S_{ {\rm{Cr}}}}$为子代成功取代父代时参数${{\rm{Cr}}}$的集合;${{{\rm{mean}}} _A}({S_{ {\rm{Cr}} }})$为算术平均。

    • 基于“分而治之(divide-and-conquer)”的思想,分组是进化算法解决复杂函数优化问题的一种重要策略,该策略将复杂问题划分为多个相对简单的子问题。有效的分组策略可以解耦多个存在交互关系的决策变量,最小化不同子问题之间的依赖关系[15]

      函数$f({\boldsymbol{X}}):{\mathbb{R}^n} \to \mathbb{R}$是部分可分离问题,当且仅当:

      $$ \begin{split} &\qquad\qquad \mathop {\arg \min }\limits_{({x_1},{x_2}, \cdots ,{x_n})} f({x_1},{x_2}, \cdots {x_n}) = \\ &(\mathop {\arg \min }\limits_{{{\boldsymbol{X}}_1}} f({x_1}, \cdots ), \cdots ,\mathop {\arg \min }\limits_{{{\boldsymbol{X}}_m}} f(, \cdots {x_n})) \end{split} $$ (8)

      式中,${\boldsymbol{X}} = ({x_1},{x_2}, \cdots, {x_n})$$n$维决策向量;${{\boldsymbol{X}}_1}, {{\boldsymbol{X}}_2}, \cdots, {{\boldsymbol{X}}_m}$是向量$ {\boldsymbol{X}} $的不相交子向量,$2 \leqslant m \leqslant n$

      函数$f({\boldsymbol{X}})$满足如下条件则称之为部分加性可分离:

      $$ f({\boldsymbol{X}}) = \sum\limits_{i = 1}^n {{f_i}({x_i})} \;\;\;\;n > 1 $$ (9)

      差分分组方法检测决策变量之间的交互关系,如果存在交互则将其分在一组,否则被分在不同的组,如果一个决策变量与其他所有变量都不存在交互,则该变量为独立变量。分组方法定义如下。

      $f({\boldsymbol{X}})$是部分加性可分离函数,$ \forall a,{b_1},{b_2},{x_p},{x_q} \in \mathbb{R} $$ a,{b_1} \ne {b_2} $$ \delta \in \mathbb{R} $$ \delta \ne 0 $,如果以下式子成立,则${x_p}$${x_q}$存在交互关系,是不可分决策变量。

      $$ {\varDelta _{\delta ,{x_p}}}[f]({\boldsymbol{x}}){|_{{x_p} = a,{x_q} = {b_1}}} \ne {\Delta _{\delta ,{x_p}}}[f]({\boldsymbol{x}}){|_{{x_p} = a,{x_q} = {b_2}}} $$ (10)
      $$ {\varDelta _{\delta ,{x_p}}}[f]({\boldsymbol{x}}) = f( \cdots ,{x_p} + \delta ,\cdots ) - f( \cdots ,{x_p}, \cdots ) $$ (11)

      否则,${x_p}$${x_q}$为可分离决策变量。

    • CLSHADE的核心步骤主要包含3部分:分组、构造学习策略及SHADE。首先对复杂问题通过差分分组检测决策变量间的耦合关系,将原始问题分解为多个相互独立的分组。然后基于母体算法SHADE通过构造学习策略提高其搜索能力。算法总体框架如图1所示。

      图  1  算法总体框架

    • 问题分组策略检查每个决策变量与其他决策变量之间是否存在交互关系,循环上述过程直到完成所有变量之间交互关系的判断,具体如算法1所示。其中$f({\boldsymbol{X}})$为目标函数,$ {x^{{\rm{min}}}} $$ {x^{{\rm{max}}}} $为决策变量上下界,${{\rm{ones}}} (1,D)$函数用于生成$D$维全1向量。

      为判断决策向量的第$i$维和第$j$维是否存在交互,初始化两个决策向量${{\boldsymbol{x}}_1}$${{\boldsymbol{x}}_2}$${{\boldsymbol{x}}_1}$初始化为决策变量下界,${{\boldsymbol{x}}_2}$除第$j$维初始化为上界外,其他维度和${{\boldsymbol{x}}_1}$一样初始化为下界,然后根据式(10)和(11)计算$ {\varDelta _1} $$ {\varDelta _2} $,根据既定阈值$\varepsilon $判断交互关系$ (\varepsilon = {10^{ - 3}}) $,最后输出决策变量分组结果。

      算法1 分组算法DG

      输入:$f({\boldsymbol{X}})$

      输出:分组结果${{\rm{groups}}} $

      初始化:$S \leftarrow \{ 1,2, \cdots ,D\} $,${{\rm{sep}}} \leftarrow \{ \} $,${{\rm{groups}}} \leftarrow \{ \} $

      For $i \in S$ do

       ${{\rm{group}}} \leftarrow \{ i\}$

       For $j \in S \wedge i \ne j$ do

        ${{\boldsymbol{x}}_1} \leftarrow {x^{{\rm{min}}}} \times {{\rm{ones}}} (1,D)$,${{\boldsymbol{x}}_2} \leftarrow {{\boldsymbol{x}}_1}$

        ${{\boldsymbol{x}}_2}(i) \leftarrow {x^{{\rm{max}}}}$,${\varDelta _1} = f({{\boldsymbol{x}}_1} - {{\boldsymbol{x}}_2})$

        ${{\boldsymbol{x}}_1}(j) \leftarrow 0$,${{\boldsymbol{x}}_2}(j) \leftarrow 0$,${\varDelta _2} = f({{\boldsymbol{x}}_1} - {{\boldsymbol{x}}_2})$

         //初始化并根据式(10)~式(11)计算$\varDelta $

        If $\left| {{\varDelta _1} - {\varDelta _2}} \right| > \varepsilon $ then

         ${\text{group}} \leftarrow {{\rm{group}}} \cup \{ j\}$

         //如果相关则放入一组

        End

       End

       $S \leftarrow S - {{\rm{group}}}$ //相关则从$S$中移除

       If ${{\rm{length}}} ({{\rm{group}}} ) = 1$ Then

        $ {{\rm{seps}}} \leftarrow {{\rm{seps}}} \cup {{\rm{group}}} $ //保存独立变量

       Else

        ${{\rm{groups}}} \leftarrow {{\rm{groups}}} \cup {{\rm{group}}}$

        //在${{\rm{groups}}} $中加入新识别的分组

       End

      End

      ${{\rm{groups}}} \leftarrow {{\rm{groups}}} \cup \{ {{\rm{seps}}} \} $//输出结果

    • 变异策略是DE算法的核心操作,DE/best/1、DE/best/2以及SHADE采用的DE/current-to-best/1都向当前种群的优秀解$ {\boldsymbol{X}}_{{{\rm{pbest}}} }^t $学习,利用$ {\boldsymbol{X}}_{{{\rm{pbest}}} }^t $中潜在的有用信息引导种群的搜索。然而,$ {\boldsymbol{X}}_{{{\rm{pbest}}} }^t $有可能存在部分维度优秀,部分维度一般的情况。一个简单的例子,假设给定一个最小化优化函数$ f(x) = {({x_1} - {x_2})^2} + {({x_3} - {x_4})^2} $$ x \in {[0,1]^4} $,基于交互关系决策变量显然可以分为两组$\{ {x_1},{x_2}\} $$\{ {x_3},{x_4}\} $。对于3个$ {\boldsymbol{X}}_{{{\rm{pbest}}} }^t $$(0.8,0.4,0.6,0.4)$$(0.6,0.4,0.8,0.4)$$(0.6,0.4,0.6,0.4)$,前两个解都在部分分组维度上优秀,而第三个解在全部分组维度上优秀,最终最优解为$(0.6,0.4,0.6,0.4)$

      得益于分组结构,构造一个$ {\boldsymbol{X}}_{{{\rm{cpbest}}} }^t $,组合多个个体不同分组维度的优秀信息,具体如下:

      $$ {\boldsymbol{X}}_{{{\rm{cpbest}}} }^t = ({\boldsymbol{X}}_{{{\rm{pbest}}} ,1}^t,{\boldsymbol{X}}_{{{\rm{pbest}}} ,2}^t, \cdots ,{\boldsymbol{X}}_{{{\rm{pbest}}} ,{{m}}}^t) $$ (12)

      式中,$ {\boldsymbol{X}}_{{{\rm{pbest}}} ,{{i}}}^t $为第$i$个分组的优秀解。新的变异策略结合DE/current-to-best/1策略和构造学习策略(constructive learning strategy, CLS),如下所示:

      $$ {\boldsymbol{V}}_i^t = {\boldsymbol{X}}_i^t + {{{{F}}} }({\boldsymbol{X}}_{{{\rm{lpbest}}} }^t - {\boldsymbol{X}}_i^t) + {{{{F}}} }({\boldsymbol{X}}_{r1}^t - {\boldsymbol{X}}_{r2}^t) $$ (13)

      式中,$ {\boldsymbol{X}}_{{{\rm{lpbest}}} }^t $以概率$ {{{{Pc}}} _i} $向构造的$ {\boldsymbol{X}}_{{{\rm{cpbest}}} }^t $学习,如:

      $$ {\boldsymbol{X}}_{{{\rm{lpbest}}} }^t = \left\{ {\begin{array}{*{20}{c}} {\boldsymbol{X}}_{{{\rm{cpbest}}} }^t & {{\rm{rand}}} < {{{{{Pc}}} }_{{{i}}} } \\ {\boldsymbol{X}}_{{{\rm{pbest}}} }^t & {{\rm{rand}}} \geqslant {{{{{Pc}}} }_{{{i}}} } \end{array}} \right. $$ (14)
      $$ {{{{Pc}}} _{{i}}} = 0.05 + \varphi \times \frac{{\left(\exp \left(\dfrac{{10(i - 1)}}{{{{{{\rm{ps}}}}} - 1}}\right)\right)}}{{(\exp (10) - 1)}} $$ (15)

      式(15)为学习概率$ {{{{Pc}}} _{{i}}} $的定义,其中,$ \varphi $为学习因子;${{{{\rm{ps}}}}} $$ {\boldsymbol{X}}_{{{\rm{pbest}}} }^t $的数量;${{\rm{rand}}} $$[0,1]$之间的随机数。可以看出$ {{{{Pc}}} _{{i}}} $单调递增,是考虑到随着进化过程的推进,$ {\boldsymbol{X}}_{{{\rm{cpbest}}} }^t $逐步向问题最优解区域靠近,因此在进化后期比进化前期赋予相对较高的学习概率。考虑到学习因子$ \varphi $对算法性能的影响,因此在本文实验部分和其他重要参数一起进行正交实验分析。构造学习策略具体流程如算法2所示。

      算法2 构造学习策略CLS

      输入:$f({\boldsymbol{X}})$, ${{\rm{groups}}} = \{ {{{\rm{group}}} _1},{{{\rm{group}}} _2}, \cdots ,{{{\rm{group}}} _m}\}$

      输出:$ {{\boldsymbol{X}}_{{{\rm{lpbest}}} }} $

      For $i = 1:{{\rm{ps}}}$ do //构造${{\boldsymbol{X}}_{{{\rm{cpbest}}} ,{\rm{i}}}}$过程

       For $j = 1:m$ do

        $\tau = {{\rm{groups}}} (j)$ //第$j$个分组

        ${{\rm{ind}}} _1^j = \left\lceil {{{\rm{rand}}} (0,1) \times {{\rm{ps}}} } \right\rceil$

        ${{\rm{ind}}} _2^j = \left\lceil {{{\rm{rand}}} (0,1) \times {{\rm{ps}}} } \right\rceil$ //向上取整

        If $f({{\boldsymbol{X}}_{{{\rm{pbest}}} }}({{\rm{ind}}} _1^j)) \leqslant f({{\boldsymbol{X}}_{{{\rm{pbest}}} }}({{\rm{ind}}} _2^j))$

         ${\boldsymbol{X}}_{{{\rm{cpbest}}} ,{\rm{i}}}^\tau = {{\boldsymbol{X}}_{{{\rm{pbest}}} }}({{\rm{ind}}} _1^j)$

        Else

         ${\boldsymbol{X}}_{{{\rm{cpbest}}} ,{\rm{i}}}^\tau = {{\boldsymbol{X}}_{{{\rm{pbest}}} }}({{\rm{ind}}} _2^j)$

        End

       End

      End //基于分组构造最优解

      For $i = 1:{{\rm{ps}}}$ do //${\boldsymbol{X}}_{{{\rm{lpbest}}} ,{{i}}}^t$的生成

       For $j = 1:m$ do

        $\tau = {{\rm{groups}}} (j)$

        If ${{\rm{rand}}} < {{{{Pc}}} _{{i}}}$

         ${\boldsymbol{X}}_{{{\rm{lpbest}}} ,{{i}}}^\tau = {\boldsymbol{X}}_{{{\rm{cpbest}}} ,{{i}}}^\tau$

        Else

         ${\boldsymbol{X}}_{{{\rm{lpbest}}} ,{{i}}}^\tau = {\boldsymbol{X}}_{{{\rm{pbest}}} ,{{i}}}^\tau$

        End

       End

      End //向构造的最优解学习

    • CLSHADE首先采用算法1对问题分组,然后在SHADE算法中使用算法2设计的构造策略迭代寻优,具体流程如算法3所示。

      算法3 CLSHADE

      输入:$f({\boldsymbol{X}})$,维数$D$

      输出:最优解${{\boldsymbol{X}}_{{{\rm{best}}} }}$

      初始化:${{\rm{NP}}} = 18D$; ${{\boldsymbol{X}}^0} = ({\boldsymbol{X}}_1^0,{\boldsymbol{X}}_2^0, \cdots ,{\boldsymbol{X}}_{{{\rm{NP}}} }^0)$; $t = 0$

          $H = 5$; ${M_{{{{{\rm{Cr}}}}} ,{{i}}}} = 0.5$, ${M_{{{F}},{{i}}}} = 0.5$;

      ${{\rm{groups}}} = {{\rm{DG}}} (f({\boldsymbol{X}}),{{\boldsymbol{X}}^0})$ //采用算法1进行分组

      Repeat

        ${S_{{{\rm{CR}}} }} = \phi$, ${S_F} = \phi $

        ${{\boldsymbol{X}}_{{{\rm{lpbest}}} }} = {{\rm{CLS}}} (f({\boldsymbol{X}}),{{\rm{groups}}} )$

          //采用算法2实施构造学习

        For $i = 1:{{\rm{NP}}}$ do

         $k = {{\rm{rand}}} [1,H]$ //从历史存档中随机选择

         ${{{\rm{CR}}} _i} = {{{\rm{rand}}n} _i}({M_{{{\rm{Cr}}} ,{{k}}}},0.1)$

         ${F_i} = {{{\rm{rand}}c} _i}({M_{{{{F}}} ,{{k}}}},0.1)$

         ${p_i} = {{\rm{rand}}} [{p_{\min }},0.2]$

         采用式(13)进行变异操作

         采用式(4)进行交叉操作

         采用式(5)进行选择操作

        End

        更新${M_{{{{{\rm{Cr}}}}} ,{{k}}}}$,${M_{{{{F}}} ,{{k}}}}$

        $t{\text{ + + }}$ //迭代次数递增

      Until 达到算法终止条件

    • 本文实验环境为:Windows 10操作系统;Intel (R) Core (TM) i7-6700 CPU @ 3.40 GHz处理器;8 GB内存;基于MATLAB实现。比较算法的控制参数按照相应文献的建议进行设置。选取CEC 2017[16]标准测试集的变量部分可分函数并在10D、30D上采用相同的评价准则进行实验。经过实验发现CEC 2017标准测试函数${f_1} \sim {f_{20}}$为部分变量部分可分函数,因此选用${f_1} \sim {f_{20}}$作为测试函数。

      CLSHADE算法有3个关键的参数:变异因子${M_F}$、交叉概率${M_{{\rm{Cr}}}}$和学习因子$\varphi $,其初始取值的设定对算法的性能有重要影响,本文采用实验设计方法DOE(design of experiment)[17]分析其对算法性能的影响并最终确定相应的初始取值。表1为每个参数的水平值设置。

      表 1  参数水平设置

      参数水平
      1234
      $ M_{F} $0.30.50.70.9
      ${M_{ {{{{\rm{Cr}}}}} } }$0.30.50.70.9
      $\varphi$0.350.450.550.65

      表1参数的所有可能组合数为$4 \times 4 \times 4=64$,每个参数组合独立运行10次以确保实验具有统计学意义。对实验结果进行多元方差分析(multivariate analysis of variance, MANOVA),结果如表2所示。

      表2可以看出,参数$\varphi $对应的F-ratio最大,即参数$\varphi $对CLSHADE的平均性能影响最大。 由于算法两个参数之间的$p$值大于0.05,所以CLSHADE中两个参数之间没有交互作用。参数主效应图如图2所示,因此选取参数取值组合:${M_F} = 0.3$, ${M_{{{{{\rm{Cr}}}}} }} = 0.5$, $\varphi = 0.45$。其他CLSHADE算法中涉及的所有其他非关键参数都与SHADE保持一致。

      表 2  参数方差分析结果

      SourceSum of
      squares
      Degrees of
      freedom
      Mean SquareF-ratiop-value
      ${M_F}$0.41030.1370.430.7303
      ${M_{ { { {{\rm{Cr}}} } } } }$0.59130.1970.630.6045
      $\varphi $1.54930.5161.640.2033
      ${M_F}*{M_{ { { {{\rm{Cr}}} } } } }$2.78090.3090.980.4771
      ${M_F}*\varphi $2.25990.2510.80.6216
      ${M_{ {{\rm{Cr}}} } }*\varphi$0.78290.8680.280.9760
      Error8.498270.315
      Total16.86963

      表 3  Rastrigin’s函数的构造学习数据

      ${{\boldsymbol{X}}_{{{\rm{pbest}}} }}$$ {x_1} $$ {x_2} $$ {x_3} $$ {x_4} $$ {x_5} $$ {x_6} $$F({\boldsymbol{x}})$
      1−43.6726.11−28.75−79.55−38.5171.29535.73
      2−22.06−4.1849.64−13.9319.720.24538.07
      3−32.9418.91−28.04−14.4222.0783.43540.03
      437.8070.86−60.65−26.2349.6712.95541.39
      5−68.07−39.78−27.09−42.7425.8274.39541.48
      623.3683.11−8.96−97.3117.7031.17541.90
      710.4816.7338.6938.4413.00−37.07542.02
      8−21.8118.7827.74−42.74−3.6028.81545.09
      9−87.7360.5716.1541.29−35.96−8.70545.45
      10−40.6398.6572.8531.9734.68−24.68546.14
      11−15.94−33.6524.52−62.09−24.69−22.56547.46
      1224.66−46.4720.06-64.4944.7114.16547.82
      $ {{\boldsymbol{X}}_{{{\rm{lpbest}}} }} $23.3683.1120.06−64.4944.7114.16512.49

      图  2  参数主效应图

    • 为通过具体函数观察CLSHADE的运行机制,以求解CEC 2017测试集的${F_5}({\boldsymbol{x}})$(shifted and rotated rastrigin’s function)函数为例进行说明。从图3所示Rastrigin’s函数的适应度地形图可以看出,该函数具有多模及多个局部最优等复杂特性。

      CEC 2017对其进行旋转平移定义如下:

      $$ F({\boldsymbol{x}}) = f({\boldsymbol{M}}({\boldsymbol{x}} - {\boldsymbol{o}})) + 500 $$ (16)
      $$ f({\boldsymbol{x}}) = \sum\limits_{i = 1}^D {(x_i^2 - 10\cos (2{\text{π}}{x_i}) + 10)} $$ (17)

      图  3  Rastrigin’s函数的适应度地形图

      $D = 6$为例,其旋转矩阵${\boldsymbol{M}}$和平移向量${\boldsymbol{o}}$分别为:

      $$ {\boldsymbol{M}} = \left( {\begin{array}{*{20}{c}} {0.09}&{0.61}&{0.00}&{0.00}&{0.00}&{0.00} \\ { - 0.54}&{0.68}&{0.00}&{0.00}&{0.00}&{0.00} \\ {0.00}&{0.00}&{0.48}&{0.00}&{0.00}&{0.11} \\ {0.00}&{0.00}&{0.00}&{0.53}&{ - 0.52}&{0.00} \\ {0.00}&{0.00}&{0.00}&{0.43}&{0.85}&{0.00} \\ {0.00}&{0.00}&{ - 0.93}&{0.00}&{0.00}&{0.00} \end{array}} \right) $$ (18)
      $$ {\boldsymbol{o}} = ( \begin{array}{*{20}{c}} { - 17.41}&{56.17}&{ - 31.76}&{ - 56.76}&{16.67}&{79.12} \end{array} ) $$ (19)

      采用算法1进行对Rastrigin’s函数进行分组,共分为3个组,分别是${{{\rm{group}}} _1} = \{ {x_1},{x_2}\} $, ${{{\rm{group}}} _2} = \{ {x_3},{x_6}\} $, ${{{\rm{group}}} _3} = \{ {x_4},{x_5}\} $。采用构造学习策略后$F({\boldsymbol{x}})$的值如表3所示,显然得到了一个更有潜力的优秀解,从而加快了算法的收敛速度,并提高了解的精度。

    • 为验证CLSHADE算法的性能,选取SHADE[7]、AMECoDEs[18]、HS-ES[19]和EBLSHADE[20]作为比较算法。所有实验在每个测试问题上独立运行51次,计算均值和标准差(Meanstd),实验结果如表4(10维)和表5(30维)所示。

      表4列出了10维问题的实验结果,可以看出所有算法在$ {f_1} \sim {f_4}、{f_9} $等5个函数上都找到了相同的最优解,在其余15个函数上CLSHADE有7个函数的结果优于其他算法,3个函数和部分其他算法找到相同的最优解,在其余函数如${f_5}、{f_{13}}$${f_{19}}$上,CLSHADE也与求解性能最优算法的结果没有显著性差异。综上所述,CLSHADE在10维问题上的总体表现优于其他对比算法。

      表 4  10维问题实验结果

      FuncSHADEMeanstdAMECoDEsMeanstdHS-ESMeanstdEBLSHADEMeanstdCLSHADEMeanstd
      10.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+00
      20.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+00
      30.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+00
      40.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+00
      52.05E+008.06E−017.14E+002.85E+005.66E−017.24E−011.97E+007.83E−017.70E−017.70E−01
      60.00E+000.00E+004.60E−063.42E−060.00E+000.00E+000.00E+000.00E+000.00E+000.00E+00
      71.20E+015.69E−011.65E+012.77E+001.13E+017.82E−011.19E+014.66E−011.06E+011.06E+01
      82.19E+008.45E−016.52E+002.74E+006.83E−017.57E−012.24E+007.92E−011.68E−011.68E−01
      90.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+00
      101.26E+012.38E+011.58E+021.24E+021.13E+021.49E+028.47E+007.94E+004.67E−014.67E−01
      110.00E+000.00E+001.03E+009.58E−011.81E+008.55E+001.20E−038.56E−030.00E+000.00E+00
      121.45E+013.98E+011.25E+013.67E+012.88E+015.94E+012.45E−011.80E−019.52E+009.52E+00
      133.08E+002.31E+004.31E+001.98E+003.32E+002.46E+003.26E+002.29E+003.13E+003.13E+00
      141.93E−021.29E−011.75E+001.38E+005.11E+001.84E+013.08E−031.64E−029.35E−049.35E−04
      155.52E−031.91E−021.20E−013.00E−016.13E−016.26E−016.67E−021.60E−012.53E−022.53E−02
      161.25E−011.65E−016.04E−011.53E+005.10E+003.04E+011.66E−012.11E−017.51E−027.51E−02
      178.89E−031.43E−021.27E+008.30E−011.39E+011.15E+011.63E−024.96E−023.20E−033.20E−03
      187.61E−021.66E−016.05E−022.36E−014.48E−011.85E−017.53E−021.47E−015.40E−025.40E−02
      196.03E−053.30E−043.59E−024.41E−028.79E−014.49E+001.02E−087.31E−084.85E−084.85E−08
      200.00E+000.00E+008.68E−021.94E−011.31E+019.60E+000.00E+000.00E+000.00E+000.00E+00

      表5为30维问题的实验结果,所有算法在函数$ {f_1} \sim {f_3} $$ {f_9} $上取得相同的最优解,在$ {f_6} $上CLSHADE和HS-ES、EBLSHADE都获得最优解,在剩余的15个函数中,CLSHADE在10个函数上优于其他算法,3个函数上与表现最优算法接近。总体来说,CLSHADE在30维问题上表现优秀。

      表 5  30维问题实验结果

      FuncSHADEMeanstdAMECoDEsMeanstdHS-ESMeanstdEBLSHADEMeanstdCLSHADEMeanstd
      10.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+00
      20.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+00
      30.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+00
      45.87E+017.78E−015.89E+011.32E+005.29E+001.20E+015.86E+010.00E+005.86E+010.00E+00
      55.81E+001.16E+002.80E+011.07E+018.29E+003.18E+005.48E+001.23E+002.84E+009.01E−01
      66.71E−104.79E−091.07E−083.72E−080.00E+000.00E+000.00E+000.00E+000.00E+000.00E+00
      73.71E+019.51E−015.63E+019.29E+004.07E+016.57E+003.63E+019.61E−013.47E+016.11E−01
      86.37E+001.17E+002.60E+011.13E+017.96E+002.29E+006.07E+001.44E+003.19E+008.40E−01
      90.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+000.00E+00
      101.21E+031.85E+021.60E+035.33E+029.90E+023.88E+021.07E+031.56E+025.99E+021.11E+02
      111.67E+012.41E+012.16E+012.41E+011.59E+012.42E+011.93E+012.62E+011.45E+012.22E+01
      129.68E+023.57E+029.47E+023.45E+023.46E+018.72E+018.16E+022.98E+029.32E+022.99E+02
      131.33E+015.19E+002.11E+018.54E+001.53E+014.30E+001.15E+016.46E+001.32E+014.84E+00
      145.88E+008.83E+002.35E+018.05E+001.43E+019.95E+008.92E+009.69E+003.97E+007.28E+00
      151.97E+001.48E+006.31E+003.04E+003.60E+003.28E+001.46E+001.09E+001.24E+009.96E−01
      162.06E+014.03E+004.75E+022.07E+022.38E+021.66E+021.41E+012.98E+002.19E+014.71E+00
      172.37E+016.26E+003.06E+014.55E+013.53E+016.28E+012.19E+015.57E+001.48E+013.04E+00
      181.97E+014.74E+002.59E+016.39E+001.93E+014.96E+001.91E+015.27E+001.85E+016.38E+00
      191.65E+007.67E−014.68E+001.53E+004.06E+002.49E+001.80E+009.36E−011.99E+008.61E−01
      202.17E+015.88E+002.76E+011.98E+011.67E+027.53E+011.81E+016.52E+001.76E+014.30E+00
    • 为进一步比较和分析所有算法的性能,本文以10维问题为例,通过收敛图观察算法的搜索过程(收敛性),通过盒图考察最优解的分布情况(稳定性),最后用Wilcoxon检验分析算法的统计学特性,结果如图4图5表6所示。

      图4列出了部分函数的收敛图,可以看出CLSHADE算法与其他算法在进化前期与其他算法收敛速度接近。但是随着进化迭代次数的增加,构造的$ {{\boldsymbol{X}}}_{{\rm{cpbest}}}^t $更接近最优解所在的区域,其引导搜索的作用更加明显,因此算法执行后期收敛速度加快并且解的精度也有明显的提升,如图中函数${f_8}$${f_{10}}$${f_{16}}$${f_{19}}$等所示。

      图  4  10维问题部分函数收敛曲线

      图5反映了与图4对应函数各算法最优解的分布情况,可以看出CLSHADE算法在函数${f_7}$${f_8}$${f_{10}}$上具有良好的分布特性,表现优秀;在函数${f_5}$${f_{16}}$${f_{19}}$上与其他优秀算法表现相当,解的分布都比较集中,具有良好的稳定性。

      表6为CLSHADE与其他算法在显著性水平为0.05和0.1下的Wilcoxon非参数检验结果,可以看出在所有10维问题上CLSHADE与其他算法存在显著差异,都优于其他对比算法。在30维问题上,CLSHADE显著优于SHADE和AMECoDEs,当显著水平为0.1时优于HS-ES算法,其他情况下虽然不存在显著性差异,但从$R - $值明显大于$R + $也可以得出CLSHADE优于其他算法。因此,从统计学的角度来说,CLSHADE总体表现优于其他对比算法。

      图  5  10维问题部分函数解的分布盒图

      表 6  Wilcoxon检验结果

      $维$CLSHADE vsR+R−Zp-value$\alpha = 0.1$$\alpha = 0.05$
      10SHADE17.0074.00−1.9920.046YesYes
      AMECoDEs0.00120.00−3.4080.001YesYes
      HS-ES1.00104.00−3.2330.001YesYes
      EBLSHADE26.0079.00−1.6640.096YesYes
      30SHADE11.00125.00−2.9480.003YesYes
      AMECoDEs0.00136.00−3.5160.000YesYes
      HS-ES26.0094.00−1.9310.053YesNo
      EBLSHADE32.0073.00−1.2870.198NoNo
    • 本文提出了一种基于构造学习的差分进化算法求解变量部分可分函数优化问题,采用差分分组技术揭示决策变量的底层交互结构和形成子成分并进行解耦分组;通过构造学习策略利用问题潜在的结构知识构造最优解并向其学习提升算法的寻优性能。在CEC 2017部分可分测试函数上的实验结果表明,本文算法在解的精度、收敛性和稳定性等方面均表现突出。

参考文献 (20)

目录

    /

    返回文章
    返回