融合混沌反学习与蜂群搜索算子的引力搜索算法①

丁知平

(清远职业技术学院 信息技术与创意设计学院,清远 511510)

引言

引力搜索算法(Gravitational Search Algorithm,GSA)[1]是继遗传算法[2]、粒子群算法[3,4]、混合蛙跳算法[5]之后的新的群智能优化算法. GSA算法源于对物理学中万有引力定律进行模拟而提出,它为解决复杂优化问题提供了新的思路和手段. 由于具有结构简单、易于实现、参数较少等优点,GSA算法一经提出便受到众多学者的关注和研究,并取得广泛应用[6-8].

在处理部分复杂、多维优化问题时,典型GSA算法容易陷入局部极值、收敛速度慢等不足. 文献[9]提出将反向学习策略、边界变异等策略引入算法,起到调节算法全局搜索和局部搜索能力的作用,获得了较好的优化能力. 文献[10]利用免疫信息处理机制来改善引力搜索算法的局部优化性能,明显改善了GSA易陷入局部极值的问题. 文献[11]提出一种基于权值的WGSA算法来提高标准GSA算法的性能,使得算法在进化初期搜索能力较强. 上述改进策略仍然受到初始种群的影响,并且,随着优化问题规模和复杂程度不断扩大,这些改进策略均很难在提高算法收敛速度和避免早熟收敛两方面取得平衡.

针对典型引力搜索算法寻优能力不足的问题,本文提出了一种改进的引力搜索算法(GSA with Chaotic Opposition-based Learning and Artificial Bee Colony Operator,CA-GSA)以改善GSA算法的寻优能力. 首先采用混沌反学习的初始化种群以加快算法的全局收敛速度; 然后,在GSA中引入人工蜂群搜索算子对种群进行引导搜索,从而使种群中的个体尽快跳出局部最优点,平衡GSA算法的探索和开发能力,避免种群因个体陷入局部最优而导致早熟收敛的不足. 最后,通过13个基准测试函数进行仿真测试,验证了CAGSA算法的有效性和优越性.

1 引力算法

假设由N个质点组成的种群,其中第i个质点的位置为表示质点i在d维空间的位置,s为优化问题的维数.

依据牛顿引力定理,在d时刻,第i个质点收到第j个质点的作用力F为

则作用在第i个质点的合力为

式中,randj是[0,1]中的一个随机数.

基于牛顿第二定理,质点i在d维的加速度为

在GSA算法的每一次迭代过程中,按式(4)更新质点的速度按式(5)更新质点的位置

GSA是以适应度值为基础的,依据适应度函数fiti给出质点的质量.

2 改进的引力算法

2.1 混沌反学习种群初始化方法

GSA算法开始于初始解,然后朝着改善解的方向进行优化,因此种群初始化方法是算法设计中一项至关重要的环节,其优劣程度会影响算法的收敛速度和解的精度. 在缺乏有关最优解的先验信息时,GSA通常采用随机初始种群. 然而,如果初始解远离最优解,甚至最优解在初始解的对立解的周围,随机初始化的方式将会制约算法的收敛性能. 反向学习策略 (Opposition-Based Learning,OBL)[12]是计算智能领域出现的一种新技术并取得广泛应用,其主要思想是：对一个可行解,同时计算并评估其反向解,从中选择较优的解作为下一代个体. 因此,采用OBL方法进行种群初始化可以改善初始种群的质量. 除此之外,种群初始化尽可能均匀分布在可能的解空间,可以有效地提高寻找最优解的效率. 利用混沌算法的遍历性产生分布均匀的初始种群可以得到质量较好的初始解群[13],进一步提高提高GSA算法寻优的计算效率.

式(6)所示为1维混沌自映射的表达式：

式(6)中,混沌变量xn在其相空间内总会有线性或非线性折叠现象以产生混沌,其中,混沌扰动的幅度为[-1,1],且迭代初值x0≠0,本文方法的初值设置x0=0.255,经过多次混沌迭代,系统输出将遍历整个解空间.

混沌反学习初始化种群算法描述如下所示.

结合二者优势,提出混沌反学习算法来初始化GSA的种群. 基于混沌反向学习初始化方法,按照混沌运动自身规律和特性进行,无疑会比随机种群更优越,因而优化到最优解的可能性也越大. 下面介绍算法具体步骤.

2.2 人工蜂群搜索策略

人工蜂群算法(Artificial Bee Colony Algorithm,ABC)是源于蜜蜂采蜜而提出的智能算法[14,15],ABC算法具有较好的优化性能,这主要得力于该算法具有很强的探索能力. 文献[16]在原始ABC算法的基础上给出了一个新的搜索策略,即

其中,wij是 惯性权值,其大小反映了对候选解xij的依赖程度;xg为最优位置; φij和 φij是[0,1]之间的随机数;Φ1和 Φ2是控制最大步长的加速因子;xkj是随机选择的个体.

可以看出,新的搜索算子在随机参数和最优位置xg的引导下,在保证探索能力同时能够提高开发能力.当处理复杂优化问题时,GSA算法由于探索能力较弱而致使算法易陷入局部最优点,进一步引导其余个体搜索轨迹向局部最优点靠近而出现早熟现象. 因此,如何提高GSA的探索能力以帮助算法跳出局部最优是改善算法优化性能的关键. 本文结合ABC算法强的探索能力,采用最优候选解xg帮助GSA种群中陷入局部最优的质点快速跳出局部最优,避免算法早熟.

2.3 改进的引力搜索算法

针对典型引力搜索算法寻优能力不足的问题,提出一种改进的GSA(CA-GSA)算法. CA-GSA是在标准GSA算法基础上,引进了混沌反学习和人工蜂群搜索算子,使CA-GSA在继承典型GSA算法出色的搜索能力下兼具上述两种策略的优势,以达到改善GSA算法优化性能的目的. CA-GSA算法的程序执行流程如图1所示. 具体步骤如下：

1) 初始化参数：种群规模N=50、混沌迭代步数K=300、GSA算法的迭代次数NS=1000;

2) 初始化种群：在待优化问题的空间中,采用混沌反学习算法产生N个质点组成的种群;

3) 计算适应度值,更新种群中最优质点xg;

4) 更新数据G(t),best(t),worst(t)和Mi;

7) 按式(5)更新质点的位置;

8) 重复步骤3)到步骤8),直到满足终止条件;9) 输出最优解及最优值,运算结束.

图1 CA-GSA程序流程图

3 仿真实验

为了验证CA-GSA的效果,对表1中13个标准基准函数进行仿真实验. 表1给出了基准函数的搜索空间和最优解,其中f1～f7为单模态函数,主要用来考察算法的执行能力并测试算法的寻优精度;f8～f13是优化领域中公认较难优化的多模态函数,具有大量的局部最优点,它们主要用来检验算法是否具备避免早熟并搜索到全局最优解的能力.

为了说明CA-GSA算法的有效,将CA-GSA与标准GSA、基于人工蜂群搜索算子的GSA(记为AGSA)进行对比研究. 为了比较的公平性,3种算法的迭代次数为1000,种群规模为50. 为有效减少随机干扰的影响,均在相同条件下独立运行30次. 表2记录了3种算法测试基准函数分别在30维和50维情况下的平均收敛次数(C.I)、最优解(Best)、平均最优适应度值(Mean)和标准差(SD)的统计数据. C.I反映了算法的收敛速度,Best和Mean显示了在给定函数评价次数下算法所能达到的精度,SD反映了算法的稳定性.

表1 测试函数

从表2可以看出,无论是解的精度还是收敛速度,A-GSA和CA-GSA算法比标准GSA算法均有很大提高. 仿真结果可以看出,CA-GSA算法几乎在所有基准函数上取得了最好的优化结果. 所有函数的最优值、平均值都等于或非常接近于全局最优值,而且标准差都相当小. 具体地,对于f1、f2、f3、f4、f9、f11,均搜索到了全局最优值. 特别地,当n=50,CA-GSA的优化精度和标准差基本上接近n=30的精度和标准差. 进一步表明了CA-GSA的优化效果、稳定性和鲁棒性并没有随着问题复杂程度的增加而减弱. GSA和A-GSA随着维数的增加,绝大部分的优化效果都呈现下降趋势. 尤其是GSA算法,从表2可以看出,虽然标准GSA算法对大部分基准函数能够优化到较好的结果,但随着问题复杂程度的增加,其稳定性和优化精度下降明显.

相比GSA算法,A-GSA除了在f6和f12函数上性能略逊于标准GSA算法,在其他测试函数上,AGSA优化精度等于或非常接近全局最优值且优于GSA算法. 尤其是f8,GSA无论在30维还是50维,其解均陷入局部最优,而A-GSA算法则能跳出局部最优,获得较为满意的解. 究其原因,是因为A-GSA算法引入了人工蜂群搜索算子,增强了算法的探索能力,进而增加了算法获得全局最优解的能力.

比较A-GSA和CA-GSA的性能,A-GSA和CAGSA的区别在于A-GSA算法中没有采取混沌反学习进行种群初始化. 对于f1、f3、f9、f10、f11,二者虽然都能获得相同的优化结果,但CA-GSA的收敛速度较AGSA的收敛速度更快; 对于其余函数,CA-GSA算法在全局收敛速度和优化精度上均优于A-GSA. 上述表明,混沌反向学习种群初始化方法能够改善GSA算法的寻优能力.

为更直观地反映算法的寻优效果,将CA-GSA、A-GSA和标准GSA算法进行比较. 3种算法对测试函数f1、f4、f5、f9、f11、f136个函数在 Dim=30情况下的寻优曲线如图2所示. 图2可以看出,针对单峰测试函数f1、f4、f5,CA-GSA具有较快的收敛速度和更优秀的解的精度; A-GSA算法由于没有采用混沌反学习测量,影响了收敛速度,由于采用了蜂群搜索算子,其优化性能明显强于标准GSA算法. 针对多峰测试函数,由于采用了混沌反学习的初始化种群策略和蜂群搜索算子,CA-GSA算法的优化性能明显优于A-GSA和GSA算法. 综上所述,CA-GSA算法在优化性能上得到了明显改善.

表2 3种优化算法性能比较

4 结论

针对GSA在复杂优化问题中寻优能力的不足的问题,提出了一种融合混沌反学习和人工蜂群搜索算子的引力搜索算法(CA-GSA). CA-GSA的初始种群在保持随机性的前提下,提高了种群的遍历性,进而改善了收敛速度; 同时,人工蜂群搜索算子的引入,平衡了GSA算法探索和开采能力,进一步改善了GSA的优化能力. 通过对13基准测试函数进行仿真测试,验证了CA-GSA算法的有效性和优越性.

图2 3种算法对函数f1、f4、f5、f9、f11、f13(n=30)的优化性能比较

1 Rashedi E,Nezamabadi-pour H,Saryazdi S. GSA：A gravitational search algorithm. Information Sciences,2009,179(13)：2232-2248. [doi：10.1016/j.ins.2009.03.004]

2 Mahmoodabadi MJ,Nemati AR. A novel adaptive genetic algorithm for global optimization of mathematical test functions and real-world problems. Engineering Science and Technology,an International Journal,2016,19(4)：2002-2021. [doi：10.1016/j.jestch.2016.10.012]

3 Garg H. A hybrid PSO-GA algorithm for constrained optimization problems. Applied Mathematics and Computation,2016,274：292-305. [doi：10.1016/j.amc.2015.11.001]

4 付强,葛洪伟,苏树智. 引入萤火虫行为和Levy飞行的粒子群优化算法. 计算机应用,2016,36(12)：3298-3302. [doi：10.11772/j.issn.1001-9081.2016.12.3298]

5 Liu C,Niu PF,Li GQ,et al. Enhanced shuffled frog-leaping algorithm for solving numerical function optimization problems. Journal of Intelligent Manufacturing,2015. [doi：10.1007/s10845-015-1164-z]

6 Xiao JH,Niu YY,Chen P,et al. An improved gravitational search algorithm for green partner selection in virtual enterprises. Neurocomputing,2016,217：103-109. [doi：10.1016/j.neucom.2016.03.092]

7 Zhang AZ,Sun GY,Ren JC,et al. A dynamic neighborhood learning-based gravitational search algorithm. IEEE Transactions on Cybernetics,2016. [doi：10.1109/TCYB.2016.2641986]

8 Niu PF,Liu C,Li PF,et al. Optimized support vector regression model by improved gravitational search algorithm for flatness pattern recognition. Neural Computing and Applications,2015,26(5)：1167-1177. [doi：10.1007/s00521-014-1798-3]

9 张维平,任雪飞,李国强,等. 改进的万有引力搜索算法在函数优化中的应用. 计算机应用,2013,33(5)：1317-1320.

10 杨晶,黎放,狄鹏. 免疫万有引力搜索算法的研究与仿真.兵工学报,2012,33(12)：1533-1538.

11 徐遥,王士同. 引力搜索算法的改进. 计算机工程与应用,2011,47(35)：188-192. [doi：10.3778/j.issn.1002-8331.2011.35.053]

12 Gao WF,Liu SY,Huang LL. Particle swarm optimization with chaotic opposition-based population initialization and stochastic search technique. Communications in Nonlinear Science and Numerical Simulation,2012,17(11)：4316-4327. [doi：10.1016/j.cnsns.2012.03.015]

13 樊友洪,邓韧,李生林,等. 基于混沌遗传算子的人工鱼群算法. 计算机系统应用,2017,26(3)：214-218. [doi：10.15888/j.csa.005664]

14 马卫,孙正兴. 基于精英蜂群搜索策略的人工蜂群算法. 计算 机 应 用,2014,34(8)：2299-2305. [doi：10.11772/j.issn.1001-9081.2014.08.2299]

15 王东云,徐艳平,瞿博阳. 基于改进蜂群算法的机器人路径规划. 计算机系统应用,2017,26(2)：145-150. [doi：10.15888/j.csa.005601]

16 Li GQ,Niu PF,Xiao XJ. Development and investigation of efficient artificial bee colony algorithm for numerical function optimization. Applied Soft Computing,2012,12(1)：320-332. [doi：10.1016/j.asoc.2011.08.040]