留言板

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

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

基于搜索偏好知识的复杂多模差分进化算法

陈作汉 曹洁 赵付青 张建林

陈作汉, 曹洁, 赵付青, 张建林. 基于搜索偏好知识的复杂多模差分进化算法[J]. 电子科技大学学报, 2020, 49(6): 875-882. doi: 10.12178/1001-0548.2020153
引用本文: 陈作汉, 曹洁, 赵付青, 张建林. 基于搜索偏好知识的复杂多模差分进化算法[J]. 电子科技大学学报, 2020, 49(6): 875-882. doi: 10.12178/1001-0548.2020153
CHEN Zuo-han, CAO Jie, ZHAO Fu-qing, ZHANG Jian-lin. Complex Multimodal Differential Evolution Algorithm Based on Search Preference Knowledge[J]. Journal of University of Electronic Science and Technology of China, 2020, 49(6): 875-882. doi: 10.12178/1001-0548.2020153
Citation: CHEN Zuo-han, CAO Jie, ZHAO Fu-qing, ZHANG Jian-lin. Complex Multimodal Differential Evolution Algorithm Based on Search Preference Knowledge[J]. Journal of University of Electronic Science and Technology of China, 2020, 49(6): 875-882. doi: 10.12178/1001-0548.2020153

基于搜索偏好知识的复杂多模差分进化算法

doi: 10.12178/1001-0548.2020153
基金项目: 国家自然科学基金(61663023,61763028)
详细信息
    作者简介:

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

    通讯作者: 曹洁,E-mail:caoj@lut.edu.cn
  • 中图分类号: TP18

Complex Multimodal Differential Evolution Algorithm Based on Search Preference Knowledge

  • 摘要: 针对复杂多模优化问题,提出一种基于搜索偏好知识的差分进化算法PKLSHADE。PKLSHADE将先验搜索偏好知识注入到种群的进化过程,在不同的进化阶段对种群的多样性和集约性区分考虑,进化早期重视差分扰动以增强算法的全局开发能力,进化后期更多围绕当前最优解进行局部精细搜索。同时,基于搜索偏好知识的变异策略能够实现差分进化算法全局开发和局部搜索的自适应平滑过渡,避免两搜索阶段的硬切换。在CEC2017复杂混合多模函数上的实验结果及统计分析表明,PKLSHADE在最优解的精度、算法的稳定性等方面均优于LSHADE、EBLSHADE、jSO及AMECoDEs等近年来的优秀差分进化算法。
  • 图  1  current-to-best/1差分策略

    图  2  不同阶段变异策略对比

    图  3  参数主效应图

    图  4  收敛曲线对比

    图  5  部分函数分布盒图对比

    表  1  PKLSHADE参数水平设置

    参数水平
    123
    ${N_p}$50100200
    $H$51015
    $\mu F$0.20.50.8
    $\mu {C_r}$0.20.50.8
    下载: 导出CSV

    表  2  PKLSHADE参数水平及响应

    参数平均响应
    ${N_p}$$H$$\mu F$$\mu {C_r}$
    5050.20.21.77×104
    50100.50.51.29×104
    50150.80.81.51×104
    10050.50.81.94×104
    100100.80.22.90×104
    100150.20.51.67×104
    20050.80.51.60×104
    200100.20.81.89×104
    200150.50.22.90×104
    下载: 导出CSV

    表  3  PKLSHADE参数平均响应及等级

    水平参数
    ${N_p}$$H$$\mu F$$\mu {C_r}$
    115 24517 67717 78525 252
    221 71220 30620 44815 220
    321 32020 29420 04517 805
    极差6 4662 6292 66310 031
    等级2431
    下载: 导出CSV

    表  4  PKLSHADE与其他对比算法的最优解平均值与标准差

    函数PKLSHADEMeanstdLSHADEMeanstdAMECoDEsMeanstdjSOMeanstdEBLSHADEMeanstd
    ${f_{11}}$8.004 5×10−14.73×10−10.000 0×1000.00×1006.964 7×10−16.72×10−10.000 0×1000.00×1009.5507E-033.02×10−2
    ${f_{12}}$3.059 3×10−12.56×10−12.409 3×1015.05×1011.367 1×1003.45×1001.457 0×10−11.33×10−12.081 4×10−12.40×10−1
    ${f_{13}}$2.318 6×1001.27×1003.386 0×1002.34×1003.664 1×1002.55×1001.451 1×1002.22×1003.874 3×1002.04×100
    ${f_{14}}$8.650 8×10−14.71×10−12.085 1×10−26.47×10−22.070 0×1003.21×1000.000 0×1000.00×1000.000 0×1000.00×100
    ${f_{15}}$1.862 2×10−19.46×10−25.833 1×10−21.51×10−11.028 5×10−11.59×10−14.989 2×10−21.45×10−13.149 7×10−35.53×10−3
    ${f_{16}}$2.068 4×10−11.05×10−13.864 5×10−23.87×10−24.749 7×10−12.72×10−12.419 8×10−12.08×10−11.858 7×10−11.78×10−1
    ${f_{17}}$3.928 6×10−12.84×10−11.056 5×10−26.99×10−31.474 9×1008.34×10−11.381 1×10−29.04×10−31.029 7×10−28.54×10−3
    ${f_{18}}$7.138 7×10−27.60×10−27.862 8×10−21.52×10−11.006 4×10−13.14×10−16.165 5×10−41.62×10−31.280 9×10−12.06×10−1
    ${f_{19}}$2.625 9×10−26.39×10−38.688 5×10−52.75×10−47.704 0×10−26.99×10−20.000 0×1000.00×1006.013 0×10−61.90×10−5
    ${f_{20}}$3.121 7×10−29.87×10−20.000 0×1000.00×1006.243 5×10−21.32×10−16.243 5×10−21.25×10−10.000 0×1000.00×100
    ${f_{21}}$1.000 0×1023.44×10−61.416 5×1025.29×1011.433 9×1025.61×1011.619 4×1025.06×1011.417 1×1025.39×101
    ${f_{22}}$1.563 9×1013.21×1011.000 0×1020.00×1009.030 0×1013.17×1011.000 0×1020.00×1001.000 0×1020.00×100
    ${f_{23}}$2.756 0×1029.69×1013.009 6×1021.57×1003.060 8×1023.86×1003.008 0×1021.23×1003.019 6×1021.75×100
    ${f_{24}}$9.268 3×1012.31×1013.042 5×1027.24×1012.889 3×1029.96×1012.580 6×1021.04×1023.290 2×1023.62×100
    ${f_{25}}$3.978 8×1021.49×10−14.070 0×1021.92×1014.073 0×1021.97×1014.025 1×1021.36×1014.163 6×1022.38×101
    ${f_{26}}$3.000 0×1020.00×1003.000 0×1020.00×1003.000 0×1020.00×1003.000 0×1020.00×1003.000 0×1020.00×100
    ${f_{27}}$3.8875×1023.06×10−13.895 2×1020.00×1003.891 7×1027.16×10−13.894 2×1022.05×10−13.895 2×1020.00×100
    ${f_{28}}$3.0000×1020.00×1003.623 6×1021.31×1023.000 0×1020.00×1003.595 6×1021.19×1024.163 0×1021.50×102
    ${f_{29}}$2.3780×1022.27×1002.309 6×1022.20×1002.378 4×1027.15×1002.309 7×1021.51×1002.296 0×1022.05×100
    ${f_{30}}$3.9450×1026.46×10−38.211 3×1042.58×1053.951 3×1020.00×1003.954 3×1024.01×10−33.993 2×1021.52×101
    下载: 导出CSV

    表  5  Wilcoxon非参数检验

    算法R+RZp-valuea=0.05a=0.1
    LSHADE46144−1.9720.049YesYes
    AMECoDEs9111−2.8970.004YesYes
    jSO6291−0.6860.492NoNo
    EBLSHADE54136−1.6500.099YesYes
    下载: 导出CSV
  • [1] 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
    [2] 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. doi:  10.1016/j.swevo.2016.01.004
    [3] TANABE R, FUKUNAGA A. Success-history based parameter adaptation for differential evolution[C]//IEEE Congress on Evolutionary Computation (CEC 2013). Cancun: IEEE, 2013: 71-78.
    [4] TANABE R, FUKUNAGA A. Improving the search performance of SHADE using linear population size reduction[C]//IEEE Congress on Evolutionary Computation (CEC 2014). Beijing: IEEE, 2014: 1658-1665.
    [5] BREST J, MAUCEC M S, BOSKOVIC B. Single objective real-parameter optimization: Algorithm jSO[C]//IEEE Congress on Evolutionary Computation (CEC 2017). Spain: IEEE, 2017: 1311-1318.
    [6] 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.
    [7] 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.
    [8] HE Xiao-yu, ZHOU Yu-ren. Enhancing the performance of differential evolution with covariance matrix self-adaptation[J]. Applied Soft Computing, 2018, 64(3): 227-243.
    [9] WANG Shi-hao, LI Yu-zhen, YANG Hong-yu. Self-adaptive mutation differential evolution algorithm based on particle swarm optimization[J]. Applied Soft Computing, 2019, 81(8): 1-22.
    [10] ALI I M, ESSAM D, KASMARIK K. A novel design of differential evolution for solving discrete traveling salesman problems[J]. Swarm and Evolutionary Computation, 2020, 52(2): 1-17.
    [11] LIU Z Z, WANG Y, YANG S X, et al. Differential evolution with a two-stage optimization mechanism for numerical optimization[C]//IEEE Congress on Evolutionary Computation (CEC 2016). Vancouver: IEEE, 2016: 3170-3177.
    [12] HU Zhong-bo, XIONG Sheng-wu, SU Qing-hua. Finite Markov chain analysis of classical differential evolution algorithm[J]. Journal of Computational and Applied Mathematics, 2014, 268(11): 121-134.
    [13] 贺毅朝, 王熙照, 刘坤起, 等. 差分演化的收敛性分析与算法改进[J]. 软件学报, 2010, 21(5): 875-885. doi:  10.3724/SP.J.1001.2010.03486

    HE Yi-chao, WANG Xi-zhao, LIU Kun-qi, et al. Convergent analysis and algorithmic improvement of differential evolution[J]. Journal of Software, 2010, 21(5): 875-885. doi:  10.3724/SP.J.1001.2010.03486
    [14] HU Z, XIONG S, SU Q, et al. Sufficient conditions for global convergence of differential evolution algorithm[J]. Journal of Applied Mathematics, 2013(1): 1044-1065.
    [15] 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]. Vancouver: IEEE, 2016.
    [16] ANGELA M D, DANIEL T V. Design and analysis of experiments[M]. Cham: Springer, 2017.
  • [1] 赵庶旭, 张占平, 王小龙, 韩淑梅, 元琳, 张家祯.  基于安全与低能耗的传感云边缘协同优化策略 . 电子科技大学学报, 2023, 52(1): 85-94. doi: 10.12178/1001-0548.2022009
    [2] 陈作汉, 曹洁, 赵付青, 张建林.  基于构造学习的差分进化算法求解部分可分优化问题 . 电子科技大学学报, 2023, 52(3): 413-422. doi: 10.12178/1001-0548.2022082
    [3] 邵爱斌, 杨洋.  致病氨基酸变异预测的新型融合模型 . 电子科技大学学报, 2022, 51(1): 25-31. doi: 10.12178/1001-0548.2021334
    [4] 韩仪, 冯鑫, 周金连, 吴晔, 肖井华.  知识标签网络生成机制研究 . 电子科技大学学报, 2021, 50(2): 294-302. doi: 10.12178/1001-0548.2020084
    [5] 许益贴, 刘红丽, 胡海波.  在线读书社区中的用户阅读偏好及社团发现 . 电子科技大学学报, 2019, 48(6): 939-946. doi: 10.3969/j.issn.1001-0548.2019.06.020
    [6] 张强, 李盼池, 王梅.  基于自适应进化策略的人工蜂群优化算法 . 电子科技大学学报, 2019, 48(4): 560-566. doi: 10.3969/j.issn.1001-0548.2019.04.013
    [7] 范如国, 杨维国, 张应青, 崔迎迎.  社会困境下双重度偏好社团网络合作涌现研究 . 电子科技大学学报, 2018, 47(6): 943-952. doi: 10.3969/j.issn.1001-0548.2018.06.023
    [8] 罗四维, 侯孟书, 牛新征, 吕孟婕.  基于免疫优化策略的副本放置算法 . 电子科技大学学报, 2017, 46(5): 741-746. doi: 10.3969/j.issn.1001-0548.2017.05.017
    [9] 徐增林, 盛泳潘, 贺丽荣, 王雅芳.  知识图谱技术综述 . 电子科技大学学报, 2016, 45(4): 589-606. doi: 10.3969/j.issn.1001-0548.2016.04.012
    [10] 唐东明, 卢显良.  用于网络编码优化的改进量子进化算法 . 电子科技大学学报, 2015, 44(2): 215-220. doi: 10.3969/j.issn.1001-0548.2015.02.010
    [11] 陈卓, 冯钢, 周江.  分层P2P点播系统中优化的带宽资源分配策略 . 电子科技大学学报, 2014, 43(3): 443-449. doi: 10.3969/j.issn.1001-0548.2014.03.022
    [12] 郑文军礻禹.  复杂多散射环境下EM-TRM成像技术应用研究 . 电子科技大学学报, 2013, 42(3): 365-368. doi: 10.3969/j.issn.1001-0548.2013.03.009
    [13] 张磊, 陈俊亮, 孟祥武, 沈筱彦, 郭杰.  基于用户偏好的垂直搜索算法 . 电子科技大学学报, 2010, 39(1): 91-96. doi: 10.3969/j.issn.1001-0548.2010.01.021
    [14] 吴大鹏, 武穆清, 甄岩, 孙兵.  联合竞争窗口和发送调整策略优化WLAN性能 . 电子科技大学学报, 2010, 39(1): 33-36. doi: 10.3969/j.issn.1001-0548.2010.01.008
    [15] 胡建, 李志蜀, 欧鹏, 罗思达.  粒子群优化算法中的分步式策略 . 电子科技大学学报, 2009, 38(3): 435-440. doi: 10.3969/j.issn.1001-0548.2009.03.028
    [16] 聂南, 夏启明, 姚俊峰, 何克清.  面向组件接口的XACML变异测试策略 . 电子科技大学学报, 2009, 38(2): 288-291. doi: 10.3969/j.issn.1001-0548.2009.02.31
    [17] 李瑾坤.  知识作业过程表示方法的研究 . 电子科技大学学报, 2008, 37(5): 769-772.
    [18] 彭舰, 谢川, 廖朝辉.  RBAC授权策略在网格环境中的优化 . 电子科技大学学报, 2008, 37(2): 278-281.
    [19] 张宇, 郭晶, 周激流.  动态变异遗传算法 . 电子科技大学学报, 2002, 31(3): 234-239.
    [20] 李龙澍, 程慧霞.  基于约束对象的知识表示研究 . 电子科技大学学报, 1998, 27(4): 411-415.
  • 加载中
图(5) / 表(5)
计量
  • 文章访问数:  4784
  • HTML全文浏览量:  1267
  • PDF下载量:  92
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-03-24
  • 修回日期:  2020-07-15
  • 网络出版日期:  2020-11-25
  • 刊出日期:  2020-11-23

基于搜索偏好知识的复杂多模差分进化算法

doi: 10.12178/1001-0548.2020153
    基金项目:  国家自然科学基金(61663023,61763028)
    作者简介:

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

    通讯作者: 曹洁,E-mail:caoj@lut.edu.cn
  • 中图分类号: TP18

摘要: 针对复杂多模优化问题,提出一种基于搜索偏好知识的差分进化算法PKLSHADE。PKLSHADE将先验搜索偏好知识注入到种群的进化过程,在不同的进化阶段对种群的多样性和集约性区分考虑,进化早期重视差分扰动以增强算法的全局开发能力,进化后期更多围绕当前最优解进行局部精细搜索。同时,基于搜索偏好知识的变异策略能够实现差分进化算法全局开发和局部搜索的自适应平滑过渡,避免两搜索阶段的硬切换。在CEC2017复杂混合多模函数上的实验结果及统计分析表明,PKLSHADE在最优解的精度、算法的稳定性等方面均优于LSHADE、EBLSHADE、jSO及AMECoDEs等近年来的优秀差分进化算法。

English Abstract

陈作汉, 曹洁, 赵付青, 张建林. 基于搜索偏好知识的复杂多模差分进化算法[J]. 电子科技大学学报, 2020, 49(6): 875-882. doi: 10.12178/1001-0548.2020153
引用本文: 陈作汉, 曹洁, 赵付青, 张建林. 基于搜索偏好知识的复杂多模差分进化算法[J]. 电子科技大学学报, 2020, 49(6): 875-882. doi: 10.12178/1001-0548.2020153
CHEN Zuo-han, CAO Jie, ZHAO Fu-qing, ZHANG Jian-lin. Complex Multimodal Differential Evolution Algorithm Based on Search Preference Knowledge[J]. Journal of University of Electronic Science and Technology of China, 2020, 49(6): 875-882. doi: 10.12178/1001-0548.2020153
Citation: CHEN Zuo-han, CAO Jie, ZHAO Fu-qing, ZHANG Jian-lin. Complex Multimodal Differential Evolution Algorithm Based on Search Preference Knowledge[J]. Journal of University of Electronic Science and Technology of China, 2020, 49(6): 875-882. doi: 10.12178/1001-0548.2020153
  • 差分进化算法(DE)[1]是一种基于种群的进化算法,算法利用种群个体之间的差分信息形成扰动实现变异,通过父、子代个体适应度竞争选择新一代个体,经过差分变异、交叉和选择等操作迭代寻优。具有实现简单、控制参数较少和高效等优点,广泛应用于各领域。

    为提升标准DE算法的优化性能,国内外学者对其进行了大量研究和改进[2]。这些改进可以分为两个方面,一方面是在DE算法的内在运行机制上进行改进,如SHADE[3]、LSHADE[4]、jSO[5]、EBLSHADE[6]、AMECoDEs[7]等。这些研究从DE算法控制参数的自适应、变异策略和种群个体保优选择等方面进行改进。另一方面,与其他优秀算法结合,利用其他算法的优点从初始种群质量、变异策略等方面提升标准DE算法的寻优性能[8-10]

    尽管DE算法已经被学者广泛研究,但依然缺乏对问题隐性知识的考虑,存在容易陷入局部最优,出现早熟收敛或找不到全局最优解,求解复杂多模问题比较困难等情况。

    文献[11]的研究表明DE算法在进化的不同阶段,有必要采取不同的开发(exploitation)和探测(exploration)策略,对于全局开发和局部搜索给予不同的重视程度。此类算法通过设置一个阈值切换全局开发和局部搜索两个阶段,取得了一定的效果。然而,DE算法的进化过程从全局开发到局部搜索是一个复杂渐进过程,与具体优化问题的解空间特征及规模等密切相关,确定一个合理的阈值比较困难。另一方面,一个阈值是否适用于众多不同的优化问题也值得商榷,此外新增一个待定参数,也增加了算法的复杂性和不确定性。

    本文针对复杂多模函数优化问题,提出一种基于搜索偏好知识的DE算法,将搜索偏好知识注入到种群的演化过程,在不同进化时期,对种群的分散性和集约性给予不同的重视程度。在进化初期,更重视差分扰动加强算法的全局开发能力,进化后期重视当前最优解,在当前最优解附近进行局部搜索。通过全局开发和局部搜索的自适应平滑切换平衡全局开发和局部搜索。

    • DE算法是一种群体智能优化算法,首先在解的取值范围内采用实数编码随机产生一定数量的初始种群,然后经过差分变异、交叉和选择操作生成新一代种群,直到达到预设最大迭代次数或求解精度则终止迭代。

      1) 初始化

      设种群规模为${N_p}$,问题的维数为D,初始化表示如下:

      $$ {{{X}}^0} = (x_{\rm{1}}^{\rm{0}},x_{\rm{2}}^{\rm{0}}, \cdots ,x_{{N_p}}^{\rm{0}}) $$ (1)
      $$ {{x}}_i^0 = (x_{i,1}^0,x_{i,2}^0, \cdots ,x_{i,D}^0)\;\;\;i \in \{ 1,2, \cdots {N_p}\} $$ (2)
      $$x_{i,j}^0 = {x_{\min,j}} + {\rm{rand}}[0,1]({x_{\max,j}} - {x_{\min,j}})$$ (3)

      式中,${{{X}}^0}$是初始种群;${{x}}_i^0$是种群的个体;${\rm{rand}}[0,1]$是0~1之间的随机数;${x_{\max,j}}$${x_{\min,j}}$是上下界。

      2) 差分变异

      差分变异操作是DE算法最显著的特征,通过种群个体间的差分项作用于其他个体得到变异向量,根据变异向量生成方法的不同,形成了多种变异策略,部分具有代表性的变异策略如下:

      DE/rand/1:

      $$ {{V}}_i^t = {{X}}_{r1}^t + F({{X}}_{r2}^t - {{X}}_{r3}^t) $$ (4)

      DE/best/1:

      $$ {{V}}_i^t = {{X}}_{{\rm{best}}}^t + F({{X}}_{r1}^t - {{X}}_{r2}^t) $$ (5)

      DE/current-to-best/1:

      $$ {{V}}_i^t = {{X}}_i^t + F({{X}}_{{\rm{best}}}^t - {{X}}_i^t) + F({{X}}_{r1}^t - {{X}}_{r2}^t) $$ (6)

      DE/rand/2:

      $$ {{V}}_i^t = {{X}}_{{\rm{best}}}^t + F({{X}}_{r1}^t - {{X}}_{r2}^t) + F({{X}}_{r3}^t - {{X}}_{r4}^t) $$ (7)

      DE/best/1:

      $$ {{V}}_i^t = {{X}}_{r1}^t + F({{X}}_{r2}^t - {{X}}_{r3}^t) + F({{X}}_{r4}^t - {{X}}_{r5}^t) $$ (8)

      式中,${r_1},{r_2},{r_3},{r_4},{r_5}$随机从$[1{\rm{,}}N_p]$中选取且与$i$互不相等;$F$为差分项缩放因子;${{X}}_{{\rm{best}}}^t$为第$t$代的最优解。

      3) 交叉

      差分变异向量与目标向量进行交叉操作生成实验向量。DE算法常见的交叉方式有二项式交叉和指数交叉。二项式交叉过程如下:

      $${{U}}_{i,j}^t = \left\{ \begin{aligned} & {{V}}_{i,j}^t \;\;\; j = {j_{{\rm{rand}}}} {\text{或}} {\rm{rand}}(0,1) \leqslant {C_r}\\ & {{X}}_{i,j}^t \;\;\;\;\;\;\; {\text{其他}} \end{aligned} \right.$$ (9)

      式中,${C_r}$是交叉概率;${j_{{\rm{rand}}}}$$[1{{,D}}]$之间随机选取;交叉过程保证${{U}}_{i,j}^t$至少有一个分量由${{V}}_{i,j}^t$贡献。

      4) 选择

      选择操作从目标向量(父代)与实验向量(子代)之间根据适应度值选择优秀个体进入下一代。

      $${{U}}_{i,j}^t = \left\{ \begin{aligned} & {{{U}}^t}\;\;\;\;f({{{U}}^t}) \leqslant f({{X}}_i^t)\\ & {{X}}_i^t\;\;\;\;\;\;\;{\text{其他}} \end{aligned} \right.$$ (10)

      对于最小化问题,如果新的实验向量的适应度函数值小于或等于目标向量的适应度值,则代表实验向量更优,选其进入下一代。

      不同的差分变异操作具有不同寻优机理,如LSHADE采用的current-to-best/1差分变异策略,在整个进化过程,差分项${{X}}_{r1}^t - {{X}}_{r2}^t$始终与向当前最优解学习项${{X}}_{{\rm{best}}}^t - {{X}}_i^t$保持同等权重F,如图1所示。

      除DE/current-to-best/1外,DE/rand/2和DE/best/2的变异策略类似,都对差分项和向当前最优解学习项给予同一权重因子F,即算法在运行全周期对解空间的全局开发和在最优解附近小范围内搜索一直同等重视。更为合理的选择尤其是对于多模优化问题,应该在进化前期更重视解空间的大范围开发,尽量全面探测解空间,进化后期则主要在已找到的最优解附近进行精细搜索,加快算法收敛。

      图  1  current-to-best/1差分策略

    • 为了更好地平衡DE算法的全局开发和局部探索能力,本文在LSHADE算法的基础上提出一种基于搜索偏好知识的算法PKLSHADE(preference- knowledge-based LSHADE),采用当前评价次数与总评价次数比例权重实现全局开发到局部搜索的自适应平滑切换,并在理论上对算法的收敛性进行分析和证明。最后,基于CEC 2017标准测试集上的复杂混合多模函数对算法的效果进行仿真实验验证。

    • 为使算法在进化初期加大全局开发能力,增大扰动以全面探测解空间,进化后期减少扰动,在已找到的最优解附近精细搜索加快算法收敛,设计新的差分变异策略如下:

      $${{V}}_i^t = {{X}}_i^t + \omega F({{X}}_{{\rm{best}}}^t - {{X}}_i^t) + (1 - \omega )F({{X}}_{r1}^t - {{X}}_{r2}^t)$$ (11)
      $$\omega = {\rm{0}}{\rm{.2}} + {\rm{0}}{\rm{.8}} \times \frac{{{\rm{nfes}}}}{{{\rm{max\_nfes}}}}$$ (12)

      式中,${\rm{nfes}}$是当前评价次数;${\rm{max\_nfes}}$为最大评价次数;ω为前期权重因子。

      在算法运行的前期权重因子$\omega $较小,差分变异算子差分项${{X}}_{r1}^t - {{X}}_{r2}^t$在变异中贡献较大,即扰动大,可以引导算法在较大范围内探测,如图2a所示。进化后期$\omega $逐渐增大,${{X}}_{{\rm{best}}}^t - {{X}}_i^t$项的权重变大,意味着差分扰动变小,个体在当前最优解附近进行小范围的局部搜索,如图2b所示。

      根据式(11),${{V}}_i^t$的结果由${{X}}_i^t$$F({{X}}_{{\rm{best}}}^t - {{X}}_i^t)$$F({{X}}_{r1}^t - {{X}}_{r2}^t)$3项构成,与DE/current-to-best/1策略的组成相同,而当$\omega $较小时,本文的变异策略又与DE/rand/1策略接近。由此可见,本文的差分变异策略兼有DE/rand/1和DE/current-to-best/1的特点。

      图  2  不同阶段变异策略对比

    • PKLSHADE算法基本流程和LSHADE一致,主要步骤如下:

      1) 初始化,设置种群规模Np,问题维数D,交叉率Cr,最大评价次数max_nfes,在取值范围内根据式(3)随机生成初始种群${X^0}$

      2) 变异,随机选择${{X}}_i^t$${{X}}_{r1}^t$${{X}}_{r2}^t$,根据式(11)进行变异;

      3) 交叉,采用式(9)进行交叉操作;

      4) 选择,采用式(10)进行选择操作;

      5) 终止判断,若${\rm{nfes}} < {\rm{max\_nfes}}$则返回步骤2)继续循环,否则结束循环,输出结果。

    • DE算法收敛性的方法有基于Markov链[12]、随机泛函分析理论[13]和无群乘积理论[14]等。下面以Markov链相关理论分析PKLSHADE算法的收敛性。

      差分进化的迭代搜索过程包括差分变异、交叉、选择3个算子,这3个算子是相互独立的随机过程,可被认为是随机映射。

      $S = {R^D}$为被搜索的解空间,${S^{{N_p}}}$为决策空间,$f$为适应度函数。

      定义 1 差分变异算子:PKLSHADE随机从${S^{{N_p}}}$中选取${{{X}}_i}$${{{X}}_{r1}}$${{{X}}_{r2}}$,根据式(11)产生${{{V}}_i}$,是随机映射,记作:

      $${T_m}:{S^{{N_p}}} \to S$$

      其概率分布为:

      $$ \begin{split} &\qquad\qquad P\{ {T_m}({{X}}) = {{{V}}_i}\} = \\ & \sum {P(T_m^1({{X}}) = \{ {{{X}}_{r{\rm{1}}}}{\rm{,}}{{{X}}_{r{\rm{2}}}},{{{X}}_i},{{{X}}_{{\rm{best}}}}\} ) \times } \\ &\;\; P(T_m^2({{{X}}_{r{\rm{1}}}},{{{X}}_{r{\rm{2}}}},{{{X}}_i},{{{X}}_{{\rm{best}}}}) = {{{V}}_i}) = \\ & \sum {P(T_m^1({{X}}) = \{ {{{X}}_{r{\rm{1}}}},{{{X}}_{r{\rm{2}}}},{{{X}}_i},{{{X}}_{{\rm{best}}}}\} )} \end{split} $$ (13)

      式中,${{{X}}_{r{\rm{1}}}},{{{X}}_{r{\rm{2}}}},{{{X}}_i},{{{X}}_{{\rm{best}}}} \in {S^4}$

      定义 2 交叉算子:交叉过程根据式(9)由${{{V}}_i}$${{{X}}_i}$采用二项交叉产生新个体,属于随机映射,记作:

      $${T_c}:{S^2} \to S$$

      其概率分布为:

      $$ P\{ {T_c}({{{X}}_i},{{{V}}_i}) = {{{U}}_i}\} = \left\{ \begin{array}{l} 0\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{{{U}}_i} = {{{X}}_i}\\ mC_D^kC_r^k{(1 - {C_r})^{D - k}}\;\;{\text{其他}}\\ C_r^N + 1/{N_p}\;\;\;\;\;\;\;{{{U}}_i} = {{{V}}_i} \end{array} \right. $$ (14)

      式中,$1 < k < D$为发生交叉的元素个数;$m$为交叉后产生的新个体数。

      定义 3 选择算子:原目标向量${{{X}}_i}$和新实验向量${{{U}}_i}$进行贪婪选择,记作:

      $${T_s}:{S^2} \to S$$

      选择算子选择适应度更小的个体进入下一代种群,种群保留新个体${{{U}}_i}$的概率为:

      $$P\{ {T_c}({{{X}}_i},{{{U}}_i}) = {{{U}}_i}\} = \left\{ \begin{aligned} & 0\;\;\;\;\;\;\;f({{{U}}_i}) \leqslant f({{{X}}_i})\\ & 1\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\text{其他}} \end{aligned} \right.$$ (15)

      选择算子确保进化过程保留优秀解,该过程不可逆。由此,PKLSHADE进化过程记作:

      $$ \begin{split} &\qquad\qquad\qquad {{X}}(t + {\rm{1}}) = \\ & \{ {{{X}}_i}(t + 1) = {T_s}{T_c}{T_m}({{X}}(t)),i = 1,2, \cdots ,{N_p}\} \end{split} $$ (16)

      定理 1 PKLSHADE算法进化过程中,由于采用贪婪选择策略,种群个体适应度迭代序列单调非递增,即$F({{X}}(t + 1) \leqslant F({{X}}(t))$,显然进化方向单调。

      证明:

      1) Markov性:PKLSHADE新一代个体的产生过程包括差分变异${T_s}$、交叉${T_c}$与选择${T_m}$3个环节,表示如下:

      $${{X}}(t + {\rm{1}}) = T({{X}}(t)) = {T_s}{T_c}{T_m}({{X}}(t))$$ (17)

      根据式(13)~(15),${T_m}$${T_c}$${T_s}$都与迭代次数$t$无关,只与${{X}}(t)$相关,即第$t + {\rm{1}}$代种群状态只和第$t$代种群相关,与第$t$代种群之前种群的状态无关,是Markov链。

      2) 齐次性:因为PKLSHADE算法的差分变异、交叉与选择环节均与迭代次数$t$无关,故其$k$步转移概率$P_{ij}^k = P\{ {{X}}(t + k) = j|{{X}}(t) = i\} $$t$无关,即PKLSHADE算法种群迭代过程满足齐次性,证毕。

      PKLSHADE算法的转移概率为:

      $$ \begin{split} &\qquad\qquad\;\; P\{ T{({{X}}(t))_i} = {{X}}(t + 1)\} = \\ & \sum {\sum {\sum {P\{ {T_m}({{X}}(t)) = \{ {{{X}}_{r{\rm{1}}}},{{{X}}_{r{\rm{2}}}},{{{X}}_i},{{{X}}_{{\rm{best}}}}\} \} } } } \times \\ &\qquad\;\;\;\qquad\;\; P\{ {T_c}({{{X}}_i}(t),{{{V}}_i}) = {{{U}}_i}\} \times \\ &\quad\qquad\;\; P\{ {T_s}({{{X}}_i}(t),{{{U}}_i}) = {{{X}}_i}(t + 1)\} = \\ &\;\;\;\quad\qquad \prod\limits_{i = 1}^{{N_p}} {P\{ T{{({{X}}(t))}_{_i}} = {{{X}}_i}(t + 1)\} } \end{split} $$ (18)

      $\forall {{X}}(t) \in {S^{{N_p}}}$,$\exists {\rm{\{ }}{{{X}}_{r{\rm{1}}}},{{{X}}_{r{\rm{2}}}},{{{X}}_i},{{{X}}_{{\rm{best}}}}{\rm{\} }} \in {S^{{N_p}}}$,${{{V}}_i},{{{U}}_i}\! \in \! {S^{{N_p}}}$,显然:

      $$\begin{aligned} & P\{ {T_m}({{X}}(t)) = \{ {{{X}}_{r{\rm{1}}}},{{{X}}_{r{\rm{2}}}},{{{X}}_i},{{{X}}_{{\rm{best}}}}\} > 0\\ &\qquad\;\; P\{ {T_c}({{{X}}_i}(t),{{{V}}_i}) = {{{U}}_i}\} > 0\\ &\;\;\; P\{ {T_s}({{{X}}_i}(t),{{{U}}_i}) = {{{X}}_i}(t + 1)\} > 0 \end{aligned}$$

      因此,转移概率$P\{ T{({{X}}(t))_i} = {{X}}(t + 1)\} > 0$,假设PKLSHADE算法Markov链种群序列的转移概率记作$P\{ {{X}},{{Y}}\} = P\{ {{X}}(t + 1) = {{Y}}{\rm{|}}{{X}}(t) = {{X}}\} $,则有如下定理:

      定理 2 PKLSHADE种群序列$\{ {{X}}(t),t = 0,1, 2, \cdots \} $以概率1收敛于解空间内全局最优解集${E^*}$的子集$E_\delta ^* = \{ {{Y}} = ({y_1},{y_2}, \cdots ,{y_{{N_p}}}),{y_i} \in {E^*}\} $,即:

      $$\mathop {{\rm{lim}}}\limits_{n \to \infty } P\{ {{X}}(t) \in E_\delta ^*{\rm{|}}{{X}}(0) = {{{X}}_0}\} = {\rm{1}}$$

      证明:假设${{{X}}^*}$$f(x)$的唯一全局最优解,由式(13)和式(14)可得:

      1) 如果$ {{X}},{{Y}} \in E_\delta ^*$,则$P\{ {{X}},{{Y}}\} > 0$$P\{ {{Y}},{{X}}\} > 0$,即两状态互通${{X}} \leftrightarrow {{Y}}$

      2) 如果$ {{X}} \in E_\delta ^*$,而${\kern 1pt} {{Y}} \notin E_\delta ^*$,则$P\{ {{X}},{{Y}}\} = 0$,即${{X}}\not \leftrightarrow {{Y}}$

      因此,$E_\delta ^*$为正常返的非周期不可约闭集。对于任意初始解,存在极限分布:

      $$\mathop {{\rm{lim}}}\limits_{n \to \infty } P\{ {{X}}(t) = {{Y}}|{{X}}(0) = {{{X}}_{\rm{0}}}\} = \left\{ \begin{array}{l} \pi ({{Y}})\;\;\;{{Y}} \in E_\delta ^*\\ 0\;\;\;\;\;\;\;{{Y}} \in E_\delta ^* \end{array} \right.$$

      ${{X}}(t)$必然会进入$E_\delta ^*$内,且满足某一极限概率分布$\pi ({{Y}})$,所以$\mathop {{\rm{lim}}}\limits_{n \to \infty } P\{ {{X}}(t) \in E_\delta ^*{\rm{|}}{{X}}(0) = {{{X}}_{\rm{0}}}\} = 1$,证毕。

    • 为了评估PKLSHADE算法的性能,实验选用CEC2017[15]标准测试集的复杂混合多模函数${f_{11}}\sim {f_{30}}$进行验证。其中${f_{11}}\sim {f_{20}}$为混合函数(hybrid function), ${f_{21}}\sim {f_{30}}$为复合函数(composition function)。函数维数D取10,所有算法在所选测试函数上独立运行51次。

    • 本文算法基于LSHADE算法,有4个参数分别是${N_p}$$H$$\mu F$$\mu {C_r}$,关于参数的说明详见文献[4]。选择合理的参数初值,对于算法的性能具有重要影响,本文采用DOE(design of experiment)[16]方法进行分析。每个参数设置3个水平值,如表1所示。

      表 1  PKLSHADE参数水平设置

      参数水平
      123
      ${N_p}$50100200
      $H$51015
      $\mu F$0.20.50.8
      $\mu {C_r}$0.20.50.8

      根据正交表${L_9}({3^4})$对每组参数组合独立运行30次,算法所得平均性能作为响应值,结果如表2所示。

      表 2  PKLSHADE参数水平及响应

      参数平均响应
      ${N_p}$$H$$\mu F$$\mu {C_r}$
      5050.20.21.77×104
      50100.50.51.29×104
      50150.80.81.51×104
      10050.50.81.94×104
      100100.80.22.90×104
      100150.20.51.67×104
      20050.80.51.60×104
      200100.20.81.89×104
      200150.50.22.90×104

      通过表2可以计算得到各参数在每一水平值下的平均响应值并得到参数主效应图,然后根据极差确定4个参数对算法影响等级排序。表3的等级排序结果说明参数$\mu {C_r}$对算法影响最大,然后依次是${N_p}$$\mu F$$H$对算法性能的影响相对最小。

      表 3  PKLSHADE参数平均响应及等级

      水平参数
      ${N_p}$$H$$\mu F$$\mu {C_r}$
      115 24517 67717 78525 252
      221 71220 30620 44815 220
      321 32020 29420 04517 805
      极差6 4662 6292 66310 031
      等级2431

      根据图3可见,PKLSHADE算法的最佳参数组合是${N_p} = 50$$H = 5$$\,\mu F = 0.2$$\,\mu {C_r} = 0.5$

      图  3  参数主效应图

    • 对比算法选用目前具有代表性的种群线性下降及参数自适应的LSHADE算法、自适应多精英引导的AMECoDEs算法、LSHADE算法的改进算法jSO和EBLSHADE,以上算法采用current-to-best/1、current-to-pbest-w/1、current-to-ord-pbest/1和current- to-nbest/1和current-to-pbest/1等优秀的变异策略。

      表4是本文算法与对比算法51次独立运行所得平均结果,包括最优解的平均值(Mean)和标准差(std)。

      表4可以看出所有算法在${f_{{\rm{26}}}}$函数上均找到相同的最优解。LSHADE与jSO算法在${f_{{\rm{11}}}}$函数上、jSO与EBLSHADE算法在${f_{{\rm{14}}}}$函数上、LSHADE与EBLSHADE算法在${f_{{\rm{20}}}}$函数上、PKLSHADE与AMECoDEs算法在${f_{{\rm{28}}}}$函数上都找到相同的最优解。在其余15个函数中,PKLSHADE在7个函数上(${f_{{\rm{21}}}}\sim {f_{{\rm{25}}}}$${f_{{\rm{27}}}}$${f_{{\rm{30}}}}$)都优于其他对比算法;而LSHADE、AMECoDEs、jSO和EBLSHADE算法分别有1、0、4和3个函数优于其他算法。

      如果将所有算法找到最优解的函数个数(包括共同取得最优解的情况)进行统计,在全部20个函数中,PKLSHADE、LSHADE、AMECoDEs、jSO和EBLSHADE算法分别有9、4、2、7和6个函数找到相对最优解,PKLSHADE依然有一定的优势。

      分析表4还可以发现,PKLSHADE算法在复合函数${f_{{\rm{21}}}}\sim {f_{{\rm{30}}}}$上优势明显,在混合函数${f_{{\rm{11}}}}\sim {f_{{\rm{20}}}}$上虽然表现不是最好,但与其他对比算法没有显著性差异,部分结果依然优于除得到最优解算法以外的其它算法,如${f_{{\rm{13}}}}$${f_{{\rm{18}}}}$${f_{{\rm{20}}}}$,仅在${f_{{\rm{15}}}}$函数上与AMECoDEs算法的最优解接近,劣于其他算法。

      表 4  PKLSHADE与其他对比算法的最优解平均值与标准差

      函数PKLSHADEMeanstdLSHADEMeanstdAMECoDEsMeanstdjSOMeanstdEBLSHADEMeanstd
      ${f_{11}}$8.004 5×10−14.73×10−10.000 0×1000.00×1006.964 7×10−16.72×10−10.000 0×1000.00×1009.5507E-033.02×10−2
      ${f_{12}}$3.059 3×10−12.56×10−12.409 3×1015.05×1011.367 1×1003.45×1001.457 0×10−11.33×10−12.081 4×10−12.40×10−1
      ${f_{13}}$2.318 6×1001.27×1003.386 0×1002.34×1003.664 1×1002.55×1001.451 1×1002.22×1003.874 3×1002.04×100
      ${f_{14}}$8.650 8×10−14.71×10−12.085 1×10−26.47×10−22.070 0×1003.21×1000.000 0×1000.00×1000.000 0×1000.00×100
      ${f_{15}}$1.862 2×10−19.46×10−25.833 1×10−21.51×10−11.028 5×10−11.59×10−14.989 2×10−21.45×10−13.149 7×10−35.53×10−3
      ${f_{16}}$2.068 4×10−11.05×10−13.864 5×10−23.87×10−24.749 7×10−12.72×10−12.419 8×10−12.08×10−11.858 7×10−11.78×10−1
      ${f_{17}}$3.928 6×10−12.84×10−11.056 5×10−26.99×10−31.474 9×1008.34×10−11.381 1×10−29.04×10−31.029 7×10−28.54×10−3
      ${f_{18}}$7.138 7×10−27.60×10−27.862 8×10−21.52×10−11.006 4×10−13.14×10−16.165 5×10−41.62×10−31.280 9×10−12.06×10−1
      ${f_{19}}$2.625 9×10−26.39×10−38.688 5×10−52.75×10−47.704 0×10−26.99×10−20.000 0×1000.00×1006.013 0×10−61.90×10−5
      ${f_{20}}$3.121 7×10−29.87×10−20.000 0×1000.00×1006.243 5×10−21.32×10−16.243 5×10−21.25×10−10.000 0×1000.00×100
      ${f_{21}}$1.000 0×1023.44×10−61.416 5×1025.29×1011.433 9×1025.61×1011.619 4×1025.06×1011.417 1×1025.39×101
      ${f_{22}}$1.563 9×1013.21×1011.000 0×1020.00×1009.030 0×1013.17×1011.000 0×1020.00×1001.000 0×1020.00×100
      ${f_{23}}$2.756 0×1029.69×1013.009 6×1021.57×1003.060 8×1023.86×1003.008 0×1021.23×1003.019 6×1021.75×100
      ${f_{24}}$9.268 3×1012.31×1013.042 5×1027.24×1012.889 3×1029.96×1012.580 6×1021.04×1023.290 2×1023.62×100
      ${f_{25}}$3.978 8×1021.49×10−14.070 0×1021.92×1014.073 0×1021.97×1014.025 1×1021.36×1014.163 6×1022.38×101
      ${f_{26}}$3.000 0×1020.00×1003.000 0×1020.00×1003.000 0×1020.00×1003.000 0×1020.00×1003.000 0×1020.00×100
      ${f_{27}}$3.8875×1023.06×10−13.895 2×1020.00×1003.891 7×1027.16×10−13.894 2×1022.05×10−13.895 2×1020.00×100
      ${f_{28}}$3.0000×1020.00×1003.623 6×1021.31×1023.000 0×1020.00×1003.595 6×1021.19×1024.163 0×1021.50×102
      ${f_{29}}$2.3780×1022.27×1002.309 6×1022.20×1002.378 4×1027.15×1002.309 7×1021.51×1002.296 0×1022.05×100
      ${f_{30}}$3.9450×1026.46×10−38.211 3×1042.58×1053.951 3×1020.00×1003.954 3×1024.01×10−33.993 2×1021.52×101

      图4给出了统一评价次数下PKLSHADE与其他算法在收敛性方面部分函数的对比,其中nfes是评价次数,Error values是所有算法获得的最优解与标准测试函数已知最优解之间的误差值,该值越小,说明算法的搜索性能越好。可以看出,PKLSHADE算法具有较好的收敛性,在函数${f_{{\rm{21}}}}$${f_{{\rm{22}}}}$上解的精度和收敛速度均表现突出。对于函数${f_{{\rm{12}}}}$${f_{{\rm{14}}}}$,虽然由于前期重视全局开发使得收敛效果弱于其它算法,但在进化后期更重视局部搜索机制的作用下,收敛精度能够迅速追平甚至超过其他算法。在函数${f_{{\rm{13}}}}$${f_{{\rm{25}}}}$上PKLSHADE与其他算法接近。

      图  4  收敛曲线对比

      图5是PKLSHADE算法与其他对比算法运行分布特性的盒图对比,包含反映寻优结果的最大值、最小值、中位值等分布信息。可以看出除${f_{{\rm{22}}}}$函数外,PKLSHADE算法在函数${f_{{\rm{12}}}}$${f_{{\rm{21}}}}$${f_{{\rm{25}}}}$上均具有最窄的分布,有很好的稳定性;在函数${f_{{\rm{13}}}}$${f_{{\rm{14}}}}$上也有较好的分布特性,接近最优对比算法的结果。

      为进一步验证PKLSHADE算法的优势,对所有算法的优化结果进行Wilcoxon非参数假设检验分析,显著性水平$a$取0.05和0.1,对应置信度区间95%和90%。结果如表5所示。其中,Z是非参数检验中的统计量,p-value是置信度值。从表5可以看出PKLSHADE算法相对LSHADE、AMECoDEs和EBLSHADE存在显著性差异,明显优于上述3个算法;与jSO算法相比虽然没有显著性差异,即PKLSHADE与jSO算法的搜索性能相当,但由对应R−的值91大于R+的值62可知在所有20个测试函数上,PKLSHADE的总体寻优效果依然优于jSO算法。

      图  5  部分函数分布盒图对比

      表 5  Wilcoxon非参数检验

      算法R+RZp-valuea=0.05a=0.1
      LSHADE46144−1.9720.049YesYes
      AMECoDEs9111−2.8970.004YesYes
      jSO6291−0.6860.492NoNo
      EBLSHADE54136−1.6500.099YesYes
    • 本文提出了一种基于搜索知识偏好的差分进化算法,在进化的初期重视差分扰动以便在更大范围内探测解空间,搜索更多潜在的最优解所在区域,进化后期则在前期所得最优解的引导下,更重视局部小范围搜索,以获得精度更高的解并加快算法收敛,提出的算法能够在全局开发和局部搜索之间平滑过渡,能够很好地平衡二者的关系。

      同时,本文还基于Markov理论对提出算法的收敛性进行理论分析和证明,并通过DOE实验设计方法分析算法最优参数组合。在CEC 2017复杂混合多模函数上的实验表明,本文算法在求解精度、收敛性及稳定性等方面都有一定提升。

参考文献 (16)

目录

    /

    返回文章
    返回