1967 年, Bagley[1]首次提出简单遗传算法(simple genetic algorithm, SGA), 之后广泛应用于众多领域, 如 Qos 路由优化[2]、车辆路线优化[3]和选址优化[4]等。1999 年, 郭涛等[5]在 SGA 的基础上提出一类基于子空间搜索(多父体重组)和群体爬山法结合的群体随机搜索算法(Guo Tao algorithm, GTA), 用来求解带不等式约束条件的函数优化问题, 取得很好的效果。2003 年, 吴志健等[6]在文献[5]的基础上构造一种带精英保存策略的算法(GTA based elite preservation, EP-GTA), 能快速找到问题的最优解。但是, 对于多父体重组的系数向量的高效生成方法尚缺乏深入研究。事实上, 合格系数向量的生成效率对 EP-GTA 的性能有很大的影响, 尤其在求解多解优化问题时, 这一问题更加突出[7–8]。后来,EP-GTA 广泛应用于其他演化算法[9–10], 但也存在上述问题。
针对上述问题, 我们之前的研究[11–12]中提出利用经验概率分布(empirical distribution based framework, EDBF)加快 EP-GTA 中合格系数向量的生成算法, 取得较为满意的结果, 并将其应用于全局–局部混合演化算法(global-local mixed evolutionary algorithm, GLME)[7]以及基于域分解的 GLME 算法(GLME based on domain decomposition, GLMEDD)[8]等算法中, 以便改善算法的收敛性能。此外,基于 EDBF 的 EP-GTA 在流行病学[13]、气候学[14–15]和测绘平差[16]等领域也得到成功的应用。
本文在 EDBF 的基础上, 进一步提出基于自适应边界约束(adaptive boundary constraint, ABC)的EP-GTA 算法, 依据前一个系数的值, 自适应缩放后一个系数的边界, 可在任意多的父代重组情形下快速生成系数向量。最后, 在 CEC2017 标准数据集上进行实验, 验证本文算法的性能。
考虑求解如下带约束的函数优化问题:
使其满足不等式gi (X)≤0,i=1,2,…,q 。其中, X=(x1,x2,…,xn)T∈Rn,D={X|Ii≤xi≤Ui,i=1,2,…,n},f(X)为目标函数,记D中的m个点为=(xj1,xj2,…,xjm)T ,j=1,2,…,m, 记它们张成的子空间为
其中, αi 满足条件
定义逻辑函数
用于判断 X1 是否优于 X2。若该逻辑函数的返回值为真, 则 X1 优于 X2; 否则 X2 优于 X1。
算法描述如下。
第 1 步: 在搜索空间 S 中随机产生初始群体P(0)={X1, X2, …, XN} (通常要求它们均匀分布在搜索空间中), t=0。
第 2 步: 按逻辑函数better(X, Y), 将群体 P(t)从好到坏排序, 排序后仍记 P(0)={X1, X2, …, XN},X1 为最好的个体, XN 为最差的个体。
第 3 步: 若 better(Xworst, Xbest)=真, 转第 5 步。
第 4 步: 从 P(t)中选取 K (K≤M)个最好的个体M 表示参与杂交的父代染色体个数(M≤N), 从余下的 N–K 个个体(XK+1, XK+2, …, XN)中随机地选取 M–K 个, 记为
由这 M 个个体张成子空间
其中 αi 满足条件
在子空间 V 中随机取 L 个点, 得到 L 个新的个体, 选取 L 个个体中最好的个体
。若 better(
, Xworst)=真, 则用
取代 Xworst, 并形成新的群体 P(t+1), 否则 P(t+1)=P(t), t=t+1, 转第 2 步。
第 5 步: 输出最好解 Xbest, 结束。
在 EP-GTA 算法中, 系数向量 α=(α1, α2, …,αM)T需满足两个约束条件(式(3)和(4))。为了方便讨论, 定义同时满足两个约束条件的 α 为合格系数向量, 记为。目前, 共有两类
的生成算法, 一类是 EP-GTA 算法自带的随机穷举算法[6], 另一类是经验概率分布算法[11–12]。由图1 可知, EP-GTA 算法的每一次迭代都需要生成
, 然后与多父代染色体线性组合为子代染色体。可见,
的生成效率与EP-GTA 算法的收敛性能有很强的正向关系。
图1 EP-GTA算法流程
Fig.1 Flow chart of EP-GTA algorithm
随机穷举(random exhaustive, RE)算法流程如图2 所示。RE 算法的效率与多父体重组规模(记父体数=M)成反比, EP-GTA 算法利用该方法生成系数向量, 但存在一些问题。本文以 M 为 1~20 为例, 进行100 万次实验, 取平均值后, 得到 RE 算法下 M 取不同值时的效率值, 实验结果见图3。可以观察到,随着 M 值增大, RE 算法的效率值呈指数级下降趋势, 意味着传统的 EP-GTA 算法无法解决 M 取大值时的优化问题。
图2 随机穷举算法(RE)流程
Fig.2 Flow chart of Random exhaustive algorithm (RE)
图3 不同系数向量生成算法的效率值与多父体重组规模M的关系
Fig.3 Relationship between the efficiency values of different coefficient vector generation algorithms and the scale of multi-parent recombination M
经验概率分布 EDBF 算法解决了 RE 算法存在的问题, 算法流程如图4 所示。
图4 经验概率分布算法(EDBF)流程
Fig.4 Flow chart of empirical distribution based algorithm (EDBF)
不同于 RE算法(P1=25%, P2=50%, 为两个固定值), EDBF 算法的 P1 和 P2 为与 M 取值相关的表达式, 如式(8)和(9)所示:
P1 和 P2 的含义分别为系数 αi 落入[–0.5, 0]和[0,1]区间的概率, 即 EDBF 算法依据 M 取值, 自适应改变概率值, 这是 EDBF 优于 RE 算法的重要原因。EDBF 算法的效率与 M 取值的关系如图3 所示。可以清楚地看到, EDBF 优于 RE 算法。
为解决 EDBF 算法的问题, 本文提出自适应边界约束(ABC)算法, 流程如图5 所示。在 ABC 算法中, 系数 αk 的边界由前 k–1 个系数的值决定, 例如α1=0.45, 则 α2 的边界由[–0.5, 1.5]自适应地缩小为[–0.5, 1.05]。假设α2=–0.2, 则α3的边界自适应地扩大为[–0.5, 1.25], 依此类推即生成全部系数向量。
图5 自适应边界约束算法(ABC)
Fig.5 Adaptive boundary constraint algorithm (ABC)
本文算法的系数向量生成效率与M取值的关系如图3 所示。可以清楚地看到, 随着多父体重组规模 M 值增大, 随机穷举算法[6]的效率值骤降, 经验概率分布算法[11–12]的效率值缓慢下降, 而本文算法的效率值稳定在最大值 1。
为了测试本文算法的高效性, 选择 CEC2017 标准数据集[17]中的 29 个实参数数值优化问题作为测试集, 并选择基于精英保存策略的遗传算法 EPGTA[6]和基于经验概率分布的遗传算法 EDBF[11–12]与本文提出的基于自适应边界约束的遗传算法进行对比, 选择 EP-GTA 找到的最优解、程序运行时间和函数评价次数作为评价指标。
表1 总结当种群规模 N=100, 父代个数 M=15,精英父代个数 K=5, 子代个数 L=1 时, 本文算法和对比算法在 29 个复杂函数上的优化结果。可以看到, 除函数 F21, F22 和 F27 外, 本文算法的收敛精度都优于(或相当于)对比算法。在收敛效率方面,本文算法在 29 个函数上的表现都优于对比算法。
表1 实验结果比较
Table 1 Comparison of experimental results
说明: 程序运行 20 次取平均值, 其中 N=25, M=15, K=5, L=1。程序终止条件: 种群多样性<1×10–14; 函数评价次数>100000。粗体数字表示最优结果, 下同。
法算文本23497 19071 20825 100000 100000 100000 100000 22181 100000 100000 65875 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 19072 28959 31397 32223 100000 83310数次[11–12]价法评数函EDBF算100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000[6]法EP-GTA算100000 72294 84851 100000 100000 100000 100000 98251 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000法算文本/s[11–12]间法时行运序EDBF算程[6]法EP-GTA算法算文本解优[11–12]最法的到找EDBF算[6]法EP-GTA算0.102 0.145 0.151 0.476 0.542 0.470 0.449 0.219 0.816 0.471 0.333 0.479 0.509 0.495 0.518 0.600 0.509 0.773 0.617 0.619 0.696 0.529 0.703 0.130 0.234 0.285 0.266 0.812 0.787 1.031 1.092 1.066 0.650 0.758 0.673 0.661 1.120 1.155 0.661 0.679 0.688 0.662 0.663 0.690 0.763 0.686 0.963 0.801 0.791 0.887 0.902 0.898 0.896 0.956 1.021 0.934 0.997 1.135 9.662 9.083 9.386 19.817 6.866 7.047 6.826 9.937 11.401 6.721 6.678 6.799 6.838 6.793 6.796 6.889 6.791 7.136 6.962 6.982 7.172 6.942 6.961 7.111 7.170 7.160 7.014 7.067 7.174 100.0000000000000000 300.0000000000000000 400.0000000000000000 529.6373031027915204 600.0000665638817736 735.4999361400426778 828.7856852424137060 900.0000000000000000 1675.7131869641652884 1100.0000000000000000 1211.3810980688201653 1304.0964102597481542 1412.0585898418844408 1500.0000700262241935 1600.0194331079919721 1730.2838333328525096 1800.2060165965942815 1900.0592870195578143 2004.9747902516674003 2327.0275982679904700 2307.0736472460857840 2603.0067452693792802 2758.9556345172627516 2897.7428694699874541 2900.0000000000009095 3089.0055265186779252 3100.0000000000004547 3142.7798203502870820 3394.6651210511954559 100.0000000016047323 300.0000000000000000 400.0000000000001137 536.1976345448714483 600.0108563344554113 761.2660727717241116 844.4064870557823497 900.0000000002344223 3091.6744020032074332 100.0000000000000000 300.0000000000000568 400.0000000000000000 533.5355492019447183 600.0036402602148655 747.1921460857834063 834.6431158726176136 900.0000000000000000 2621.3758301687057610 2916.3311242854256307 1112.3484738627842034 1106.5054398563056566 1294.0690758296632339 1351.5959128408007928 1311.7369827539141625 1312.5940932034536672 1427.0346349483484119 1423.1517443804546019 1503.3821648663465567 1504.4846887014261938 1801.5498811005509197 1681.5271961795324387 1783.6582697114683924 1814.8829647139423287 1811.8414741229219089 1816.1092099628765482 1904.0612109720505032 1905.8648927890974392 2079.1530425315063439 2102.3574773672607989 2200.0000000004811227 2345.5045615347862622 2306.8869515220089852 2307.2646163386466469 2633.8930283599661379 2639.9538591150635511 2766.4086922663295809 2769.0969412447952891 2898.4897240458521992 2897.7428694699874541 2900.0000000001173248 2900.0000002289734766 3087.7751113391182116 3100.0000000009758878 3100.0000014715201360 3200.7028142514382125 3181.5570654352195561 3395.2935810038438831 3395.6632697029476731 CEC2017 F1 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 F16 F17 F18 F19 F20 F21 F22 F23 F24 F25 F26 F27 F28 F29 F30
表2~5 分别总结不同的 M 取值情况下(M=10,11, 12, 13, 14, 15, 16), 本文算法和对比算法在函数F1, F10, F20 和 F30 上的优化结果。可以看到, 在不同的参数配置下, 本文算法的表现在 3 个指标上都优于对比算法。当 M 值逐渐增大时, EP-GTA 算法的程序运行时间迅速增加到几十秒, 本文算法的运行时间稳定在 1.5 秒以内; 另外, 相比于 EP-GTA 算法, 虽然 EDBF 算法的程序运行时间增加缓慢, 但大部分在最大迭代次数结束前未能收敛。
表2 M 取不同值时F1的实验结果比较
Table 2 Comparison of experimental results for F1 with different values of M
说明: *表示在最大迭代次数结束前收敛。程序运行 20 次取平均值, 其中 N=25, M=10, 11, 12, 13, 14, 15, 16, L=1。程序终止条件: 种群多样性<1×10–14, 函数评价次数>100000。下同。
?
表3 M取不同值时F10的实验结果比较
Table 3 Comparison of experimental results for F10 with different values of M
?
表4 M取不同值时F20的实验结果比较
Table 4 Comparison of experimental results for F20 with different values of M
?
表5 M 取不同值时F30的实验结果比较
Table 5 Comparison of experimental results for F30 with different values of M
?
本文针对遗传算法中合格系数向量的高效生成问题与多父体重组规模的受限问题, 在经验概率分布 EDBF 的基础上, 提出基于自适应边界约束的高效遗传算法。该方法依据前一个系数的值自适应缩放后一个系数的边界, 可在任意多的父代重组情形下快速生成系数向量。该算法加快了系数向量的生成效率, 可以支持任意大规模的多父体重组, 提高收敛精度和收敛效率。在 CEC2017标准数据集上的实验结果表明, 本文算法在 29 个复杂优化问题上的表现都优于经验概率分布算法, 可为遗传算法的更广泛应用提供理论支撑。
[1] Bagley J D.The behavior of adaptive systems which employ genetic and correlation algorithms [R].Ann Arbor: University of Michigan, 1967
[2] 陆昕为, 陈凯渝.基于改进遗传算法的通信网QoS路由优化研究.广西通信技术, 2016(2): 33–36
[3] Thatpannphyu S, Srijuntongsiri G.A binary-coded multi-parent genetic algorithm for shuttle busrouting system in a college campus // 2016 International Conference on Advanced Informatics: Concepts, Theory and Application (ICAICTA).Penang, 2016: 1–5
[4] 张荣辉, 马壮林, 党永乐, 等.基于改进遗传算法的可变信息标志选址优化研究.交通信息与安全,2018, 36(6): 113–122
[5] 郭涛, 康立山, 李艳.一种求解不等式约束下函数优化问题的新算法.武汉大学学报(自然科学版),1999, 45(5): 771–775
[6] 吴志健, 康立山, 邹秀芬.一种解函数优化问题的精英子空间演化算法.计算机应用, 2003, 23(2): 13–15
[7] Wu Zhijian, Kang Lishan, Zou Xiufen.A parallel global-local mixed evolutionary algorithm for multimodal func-tion optimization // Fifth International Conference on Algorithms and Architectures for Parallel Processing.Beijing, 2002: 247–250
[8] Wu Zhijian, Tang Zhilong, Kang Lishan.A parallelglobal-local mixed evolutionary algorithm for multimodal function optimization based on domain decomposition.Wuhan University Journal of Natural Sciences, 2003, 8(1): 253–258
[9] 熊小峰, 尹雅丽, 郭肇禄, 等.精英区域学习的转轴人工蜂群算法.四川大学学报(工程科学版),2016, 48(5): 124–134
[10] 郭肇禄, 吴志健, 汪靖, 等.一种基于精英云变异的差分演化算法.武汉大学学报(理学版), 2013,59(2): 117–122
[11] 左正康, 吴志健, 孙逸渊, 等.利用经验概率密度曲线加快精英多父体杂交算法中系数向量的生成.武汉大学学报(工学版), 2020, 53(8): 728–733
[12] Zuo Z K, Yan L, Ullah S, et al.Empirical distributionbased framework for improving multi-parent crossover algorithms.Soft Computing, 2021, 25(6): 4799–4822
[13] Zuo Z K, Ullah S, Yan L, et al.Trajectory simulation and prediction of COVID-19 via compound natural factor (CNF) model in EDBF algorithm.Earth’s Future, 2021, 9: e2020EF001936
[14] 左正康, 张飞舟, 张玲, 等.基于时空分布式的CMIP5 气候多模式集合优化.北京大学学报(自然科学版), 2020, 56(5): 805–814
[15] Ullah S, Zuo Z K, Yan L, et al.GPM-based multitemporal weighted precipitationanalysis using GPM_IMERGDF product and ASTER DEM in EDBF algorithm.Remote Sensing, 2020, 12(19): no.3162
[16] Zuo Zhengkang, Sun Yiyuan, Zhang Ruihua, et al.Improved genetic algorithm for bundle adjustmentin photogrammetry // 2020 IEEE International Geoscience and Remote Sensing Symposium.Waikoloa, 2020:6957–6960
[17] Awad N, Ali M, Liang J, et al.Problem definitions and evaluation criteria for the CEC 2017 special session and competition on single objective bound constrained real-parameter numerical optimization [R].Singapore:Nanyang Technological University, 2016: 1–34
An Efficient Genetic Algorithm Based on Adaptive Boundary Constraint