一种基于自适应边界约束的高效遗传算法

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 标准数据集上进行实验, 验证本文算法的性能。

1 EP-GTA算法分析

1.1 算法描述

考虑求解如下带约束的函数优化问题:

使其满足不等式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, 结束。

2 系数向量生成算法

在 EP-GTA 算法中, 系数向量 α=(α1, α2, …,αM)T需满足两个约束条件(式(3)和(4))。为了方便讨论, 定义同时满足两个约束条件的 α 为合格系数向量, 记为。目前, 共有两类的生成算法, 一类是 EP-GTA 算法自带的随机穷举算法[6], 另一类是经验概率分布算法[11–12]。由图1 可知, EP-GTA 算法的每一次迭代都需要生成, 然后与多父代染色体线性组合为子代染色体。可见, 的生成效率与EP-GTA 算法的收敛性能有很强的正向关系。

2.1 EP-GTA算法自带的随机穷举法

随机穷举(random exhaustive, RE)算法流程如图2 所示。RE 算法的效率与多父体重组规模(记父体数=M)成反比, EP-GTA 算法利用该方法生成系数向量, 但存在一些问题。本文以 M 为 1～20 为例, 进行100 万次实验, 取平均值后, 得到 RE 算法下 M 取不同值时的效率值, 实验结果见图3。可以观察到,随着 M 值增大, RE 算法的效率值呈指数级下降趋势, 意味着传统的 EP-GTA 算法无法解决 M 取大值时的优化问题。

2.2 经验概率分布算法

经验概率分布 EDBF 算法解决了 RE 算法存在的问题, 算法流程如图4 所示。

不同于 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 算法。

3 基于自适应边界约束的高效遗传算法

3.1 算法描述

为解决 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], 依此类推即生成全部系数向量。

3.2 系数向量生成效率分析

本文算法的系数向量生成效率与M取值的关系如图3 所示。可以清楚地看到, 随着多父体重组规模 M 值增大, 随机穷举算法[6]的效率值骤降, 经验概率分布算法[11–12]的效率值缓慢下降, 而本文算法的效率值稳定在最大值 1。

4 数值实验

4.1 实验设置

为了测试本文算法的高效性, 选择 CEC2017 标准数据集[17]中的 29 个实参数数值优化问题作为测试集, 并选择基于精英保存策略的遗传算法 EPGTA[6]和基于经验概率分布的遗传算法 EDBF[11–12]与本文提出的基于自适应边界约束的遗传算法进行对比, 选择 EP-GTA 找到的最优解、程序运行时间和函数评价次数作为评价指标。

4.2 实验结果

表1 总结当种群规模 N=100, 父代个数 M=15,精英父代个数 K=5, 子代个数 L=1 时, 本文算法和对比算法在 29 个复杂函数上的优化结果。可以看到, 除函数 F21, F22 和 F27 外, 本文算法的收敛精度都优于(或相当于)对比算法。在收敛效率方面,本文算法在 29 个函数上的表现都优于对比算法。

表2～5 分别总结不同的 M 取值情况下(M=10,11, 12, 13, 14, 15, 16), 本文算法和对比算法在函数F1, F10, F20 和 F30 上的优化结果。可以看到, 在不同的参数配置下, 本文算法的表现在 3 个指标上都优于对比算法。当 M 值逐渐增大时, EP-GTA 算法的程序运行时间迅速增加到几十秒, 本文算法的运行时间稳定在 1.5 秒以内; 另外, 相比于 EP-GTA 算法, 虽然 EDBF 算法的程序运行时间增加缓慢, 但大部分在最大迭代次数结束前未能收敛。

5 结论

本文针对遗传算法中合格系数向量的高效生成问题与多父体重组规模的受限问题, 在经验概率分布 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

HUANG Ming1, WANG Longbo2, XIAO Minghong1, FU Yu1, ZUO Zhengkang3,†
1.Guangxi Zhuang Autonomous Region Institute of Geographical Information and Surveying, Liuzhou 545005; 2.Department of Natural Resources, Guangxi Zhuang Autonomous Region, Nanning 530022; 3.College of Mining Engineering Taiyuan University of Technology, Taiyuan 030024; † Corresponding author, E-mail: zuozhengkang@tyut.edu.cn

Abstract According to the lack of method for highly efficiently spawning coefficients for multi-parent recombination in real-encoded genetic algorithm, an efficient genetic algorithm based on adaptive boundary constraint(ABC) is proposed.This method quickly generates coefficient vectors by adaptively scaling the boundary of the subsequent coefficient based on the value of the previous one, allowing for efficient reconstitution under any number of parent recombination scenarios.Experiment results on CEC2017 benchmarks demenstrate that proposed algorithm outperforms EDBF (empirical distribution based framework) a lot in 29 optimization problems.

Key words optimization theory; genetic algorithm; coefficient vector; convergence efficiency; empirical distribution based framework (EDBF); adaptive boundary constraint (ABC)