优化问题一直是计算机科学、人工智能和工程实践等多个领域研究的热点问题.研究学者受到自然界动物群体行为方式的启发,提出多种智能优化算法,如粒子群优化(particle swarm optimization,PSO)算法[1],蚁群优化(ant colony optimization,ACO)算法[2],差分进化(differential evolution,DE)算法[3],萤火虫算法(firefly algorithm, FA)[4],蝙蝠算法(bat algorithm, BA)[5], 灰狼优化(grey wolf optimization,GWO)算法[6]等,为复杂函数优化求解问题提供了强有力的工具,充分证明了智能优化算法强大的优化性能.
鲸鱼优化算法(whale optimization algorithm, WOA)[7]是澳大利亚学者于2016年提出的一种启发式算法,通过模拟海洋中鲸鱼群觅食行为来实现对目标函数优化求解.WOA具有操作简单、需要设置的参数少、寻优性能强等优点, 但也存在收敛精度低、容易陷入局部最优的缺陷.针对这些不足,国内外很多学者对其进行改进,如郭振洲等[8]提出一种WOAWC算法,选取柯西逆累积分布函数对鲸鱼个体进行变异,利用自适应权重提高算法搜索能力;龙文等[9]提出一种IWOA,通过对立学习策略初始化种群,利用非线性收敛因子增强算法的探索能力,最后利用最优个体变异操作,使得算法在解决大规模优化问题中表现出较强的寻优性能;王坚浩等[10]提出一种CWOA,引入混沌搜素策略,使得算法的收敛精度和鲁棒性有了很大提升;张永等[11]提出一种MWOA,通过分段Logistic混沌映射的方法进行种群初始化,利用非线性自适应权重平衡局部和全局寻优能力;黄清宝等[12]提出一种CPWOA,根据余弦曲线变化规律来控制参数,同时加入同步余弦惯性权值和最优鲸鱼个体变异的思想.目前WOA已成功应用于训练神经网络中的多层感知器[13]、电力系统[14]和径向配电网电容器的最佳选址[15]等多个领域.但是WOA在处理更加复杂的优化问题时,无法根据当前计算结果调整参数, 得到的解具有随机性.同时, WOA在迭代后期, 群体中其他鲸鱼均向种群中最优鲸鱼个体靠拢,这就导致种群的多样性缺失,使算法陷入局部最优解.
针对WOA所存在的不足,本文提出了基于自适应调整权重和搜索策略的鲸鱼优化算法(adaptive adjustment of weights and search strategies-based whale optimization algorithm,AWOA),利用动态惯性权重,在算法迭代初期,因种群个体比较分散,可以赋予较大的权重值,加快算法的全局搜索能力;在迭代后期,算法可以根据当前种群中个体的分布情况,自适应地改变权值的大小,使其在最优解周围精细搜索、加快收敛速度.同时利用自适应调整搜索策略,使得算法在迭代前期能以较大的概率在全局范围内随机产生一组解,增加种群的多样性,使其具有更强的全局搜索能力.利用13个基准测试函数、5个大规模测试函数和5个固定维测试函数对该算法进行仿真,结果表明,本文提出的AWOA在求解高维度目标函数和较高精度的优化问题时,表现出较强的寻优能力.
1 鲸鱼优化算法座头鲸是一类群居动物,由于它们只能捕食成群的小型鱼虾,因此进化出一种独特的觅食方式,即泡泡网觅食方式.根据座头鲸这种独特的狩猎行为,Seyedali等[7]于2016年模拟其群体行为方式,提出了鲸鱼优化算法,该算法主要分为两部分,一部分为泡泡网觅食,另一部分为随机搜索.
1.1 泡泡网觅食座头鲸觅食行为示意图如图 1所示,从图中可以看出,鲸鱼通过包围猎物和螺旋更新位置实现局部寻优的目的.WOA中,搜索空间中的每只鲸鱼的位置代表一个解.假设当前种群中最接近目标函数值的个体为最优鲸鱼的位置, 通过全局最优解的位置信息,群体中其他鲸鱼个体均向最优鲸鱼位置包围来更新其自身位置.鲸鱼包围猎物行为如式(1)所示:
(1) |
式中:D=|C·X*(t)-X(t)|; t为当前迭代次数;X*表示全局最优鲸鱼位置向量;X表示当前鲸鱼位置向量;A, C为矩阵系数,A=2a·r1-a,C=2·r2,r1, r2为[0, 1]之间的随机数;a=2-2t/tmax,tmax表示最大迭代次数.
在螺旋更新位置时,首先计算当前位置与最优鲸鱼个体之间的距离,然后通过螺旋运动方式游向最优个体,这个阶段的数学模型表示如下:
(2) |
式中:D′p=|X*(t)-X(t)|;b为常数,用于限定螺旋的形状;l是[-1, 1]之间的随机数.
鲸鱼通过螺旋形游向猎物的同时又以收缩包围的方式靠近猎物,此行为即为泡泡网觅食行为.在WOA中,当|A|<1时,鲸鱼在包围圈内寻优,进行局部最优搜索,以概率0.5实行包围猎物行为和螺旋更新行为,其数学模型如下:
(3) |
式中,p为[0, 1]之间的随机数.
1.2 随机搜索|A|≥1时,鲸鱼在收缩包围圈外寻优,进行随机搜索.算法在当前鲸鱼种群中随机选取一个鲸鱼个体作为全局最优解,种群中其他鲸鱼向其聚拢.通过这种方式更新种群的位置,增强了鲸鱼种群的多样性,算法的全局搜索能力得到增强,其数学模型公式如下:
(4) |
式中,D′=|C·Xrand-X|,Xrand表示随机选取的鲸鱼位置向量.
2 鲸鱼优化算法的改进 2.1 自适应调整权重惯性权重作为鲸鱼优化算法中一个重要的参数,对目标函数的优化求解起到了很大的作用.合适的权重值对算法寻优能力的提升有很大帮助.由于WOA在优化求解的过程中, 线性的惯性权重调整策略若选择不合适,将影响算法的收敛速度.因此,本文提出了一种根据当前鲸鱼种群分布情况来自适应改变权值的大小, 公式如下:
(5) |
式中:ng表示当前种群的迭代次数;xiupper和xilower分别为变量xi的上界和下界;Piworst和Pibest分别为当前鲸鱼种群中最差鲸鱼的位置向量和最优鲸鱼的位置向量;d1和d2是两个常数.因此,当前鲸鱼个体自适应调整权重收缩包围更新位置和自适应调整权重螺旋更新位置公式如下:
(6) |
(7) |
在引入自适应调整权重搜索策略后, 算法可以根据当前鲸鱼种群的分布情况自适应地改变权值的大小.在算法迭代初期,若鲸鱼种群陷入局部最优解,并且最优解和最差解差别不大时,d2·(xiupper-xilower)/ng的值并不受种群分布情况的影响,这部分的设计依然可以得到较大的权重值w,避免了算法在迭代初期就陷入小范围搜索的缺陷;随着鲸鱼种群迭代次数的增加,d2·(xiupper-xilower)/ng的值会逐渐变小,其对权重w的影响减小,若此时算法并未得到最优解,d1·(Piworst-Pibest)的设计就可以对权重值w起到主导作用,可以使算法以较大的步长寻优.这样设计自适应调整权重w的好处在于,其值由两部分决定,前半部分对种群迭代次数过大时起主要调节作用, 后半部分对种群陷入局部最优时起主要调节作用.权重w前后两部分会根据当前种群位置的变化情况而发生变化, 不拘于某种固定的形式, 具有很强的自适应性.
2.2 自适应调整搜索策略为防止算法陷入局部最优,随机搜索阶段,个体根据概率阈值Q来选取随机搜索的更新方式,概率阈值定义为
(8) |
式中:f表示当前鲸鱼种群的平均适应度值; fmin为当前鲸鱼种群中最好的适应度值;fmax为当前鲸鱼种群中最差的适应度值.对于每个鲸鱼个体,以一个[0, 1]之间的随机数q与计算出的概率阈值Q进行数值比较.若q<Q,随机选取的鲸鱼个体Xrand根据式(9)更新其位置,其他鲸鱼个体位置不变; 否则,其他鲸鱼个体根据式(4)更新其位置.这样设计使得算法在迭代前期能以较大的概率在全局范围内随机产生一组解,避免鲸鱼因聚集在一起而导致种群多样性的缺失, 增强了算法的全局搜索能力.
(9) |
式中:r为[0, 1]之间的随机数; Xmin, Xmax分别为变量Xrand取值的最小值和最大值.
2.3 AWOA流程图及步骤综上所述,本文提出的AWOA执行过程中的流程图如图 2所示,具体说明如下:
步骤1 参数初始化.设置种群规模为N,最大迭代次数tmax; 设置参数d1, d2;
步骤2 种群初始化.随机生成初始解,计算个体适应度{F(Xi), i=1, 2, …, N},并记录全局最优解;
步骤3 根据式(5)和式(8)计算权重w和概率阈值Q; 更新参数A, C, l, p和q;
步骤4 如果p≥0.5,根据式(7)更新当前鲸鱼位置;
步骤5 如果p<0.5并且|A|≤1,根据式(6)更新当前鲸鱼位置;
步骤6 如果p<0.5,|A|>1并且q<Q,根据式(9)更新当前鲸鱼位置;否则根据式(4)更新当前鲸鱼位置;
步骤7 判断算法是否满足终止条件,若是,则输出最优解;否则返回步骤3.
3 仿真对比与分析 3.1 测试函数与性能指标选取的测试函数为文献[7]中的13个标准测试函数(F1(x)~F13(x)); 另外,为验证AWOA的可行性,本文选取5个典型的复杂高维函数(n=200, 500, 1 000和1 500维)和5个固定维多峰函数(n=2,4维)进行对比仿真.测试函数如表 1和表 2所示.
选取平均值、标准差和成功率3个性能指标(运行30次)来分析算法的优化性能.
3.2 仿真结果分析仿真在Inter(R) Core(TM) CUP:i7-4510U, 4GB内存,2.00 GHz主频的计算机上运行,程序采用MATLAB 2015a编程实现.
通过比较AWOA与标准WOA[7], WOAWC[8], IWOA[9], CWOA[10], CPWOA[12]的仿真结果来验证AWOA的寻优能力.因CPWOA算法在文献[12]中已经和其他算法(象群优化(EHO)算法[16]、灰狼优化(GWO)算法[6]、正余弦算法[17](SCA)等)做了仿真对比,且CPWOA在收敛速度与精度上优于这些算法.因此,这里不再将AWOA与其他优化算法作比较.
经过反复多次仿真,对AWOA算法的最优参数设置如下:常数b=1,d1=1×10-4,d2=1×10-4.标准WOA,IWOA,WOAWC,CWOA和CPWOA中的其他参数均按照其对应参考文献设置.表 3给出了6种算法对13个标准测试函数(F1(x)~F13(x),n=30维)的仿真结果,其中标准WOA的结果来源于文献[7],IWOA的结果来源于文献[9].表 4为6种算法对5个高维测试函数(n=200, 500, 1 000,1 500维)的仿真数据.表 5为6种算法对5个固定维测试函数(n=2,4维)的仿真数据比较.仿真中最好的结果以黑色加粗字体表示.
由表 3中的仿真数据可知,AWOA和CPWOA在测试函数F1(x), F2(x), F3(x), F4(x), F9(x)和F11(x)上均可以收敛到理论最优值0, 表现出较好的寻优能力.AWOA除在测试函数F6(x)上的搜索结果差于IWOA外,在其他测试函数上均优于标准WOA, IWAO, WOAWC, CWOA和CPWOA,表明AWOA具有更强的寻优性能和稳定性.
由表 4中的仿真数据可知,针对高维函数的优化问题,AWOA对目标函数的求解精度和寻优成功率上总体要优于其他5种算法的仿真结果.对于测试函数f1(x),6种算法在n=200, n=500, n=1 000和n=1 500维时的收敛成功率均可达到100%,但CWOA均可以收敛到理论最优值0,表现出更强的寻优能力和稳定性.然而AWOA对于测试函数f4(x)在n=200, n=500, n=1 000和n=1 500维下的寻优成功率分别为100%, 96.67%, 73.33%, 80.00%,而其他5种算法最好的收敛成功率为20.00%.这说明AWOA在求解大规模优化问题时显示出较强寻优能力和鲁棒性.
由表 5的仿真数据可知,AWOA对于5个固定维测试函数的仿真结果在平均值上均优于其他5种算法.对于测试函数f10(x),除IWOA外其他5种算法均能收敛到理论最优值-1,CWOA的标准差更小,具有更强的稳定性.但是,对于测试函数f8(x)和f9(x),AWOA也能收敛到理论最优值,其求解结果明显优于其他5种算法.
为了便于观察AWOA的寻优性能,图 3给出了6种算法在不同维度下测试函数的仿真曲线.由图 3可以看出,相较于其他5种算法,本文提出的AWOA在收敛精度和收敛速度方面更具有优势.
本文介绍了WOA的基本原理,针对其收敛精度低和容易陷入局部最优的缺陷,提出了一种基于自适应调整权重和搜索策略的AWOA.AWOA可以根据当前鲸鱼种群的分布情况自适应地改变权值的大小, 并且选择不同的搜素策略来更新位置,以平衡算法全局搜索和局部搜索能力.
通过对WOA的13个标准测试函数、5个高维测试函数和5个固定维测试函数的数值仿真,结果表明,本文提出的AWOA在收敛精度和收敛速度方面总体上要优于标准WOA, WOAWC, IWOA, CWOA和CPWOA.对于求解有约束的实际工程应用问题是下一步研究的主要内容.
[1] |
Kennedy J, Eberhart R.Particle swarm optimization[C]//Proceeding of the IEEE International Conference on Neural Networks.Perth, 1995: 1942-1948.
|
[2] |
Dorigo M, Maniezzo V, Colorni A. Ant system:optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B:Cybernetics, 1996, 26(1): 29-41. DOI:10.1109/3477.484436 |
[3] |
Biswas S, Kundu S, Das S. Inducing niching behavior in differential evolution through local information sharing[J]. IEEE Transactions on Evolutionary Computation, 2015, 19(2): 246-263. DOI:10.1109/TEVC.2014.2313659 |
[4] |
Yang X S. Firefly algorithm, stochastic test functions and design optimization[J]. International Journal of Bio-Inspired Computation, 2010, 2(2): 78-84. DOI:10.1504/IJBIC.2010.032124 |
[5] |
Yang X S.A new metaheuristic bat-inspired algorithm[C]//Nature Inspired Cooperative Strategies for Optimization.Berlin: Springer, 2010: 65-74.
|
[6] |
Mirjalili S, Mirjalili S M, Lewis A. Grey wolf optimizer[J]. Advances in Engineering Software, 2014, 69(7): 46-61. |
[7] |
Seyedali M, Andrew L. The whale optimization algorithm[J]. Advances in Engineering Software, 2016, 95: 51-67. DOI:10.1016/j.advengsoft.2016.01.008 |
[8] |
郭振洲, 王平, 马云峰, 等. 基于自适应权重和柯西变异的鲸鱼优化算法[J]. 微电子学与计算机, 2017, 34(9): 20-25. (Guo Zhen-zhou, Wang Ping, Ma Yun-feng, et al. Whale optimization algorithm based on adaptive weight and Cauchy mutation[J]. Microelectronics & Computer, 2017, 34(9): 20-25.) |
[9] |
龙文, 蔡绍洪, 焦建军, 等. 求解大规模优化问题的改进鲸鱼优化算法[J]. 系统工程理论与实践, 2017, 37(11): 2983-2994. (Long Wen, Cai Shao-hong, Jiao Jian-jun, et al. Improved whale optimization algorithm for large scale optimization problem[J]. System Engineering—Theory & Practice, 2017, 37(11): 2983-2994. DOI:10.12011/1000-6788(2017)11-2983-12) |
[10] |
王坚浩, 张亮, 史超, 等. 基于混沌搜索策略的鲸鱼优化算法[J]. 控制与决策, 2019, 34(9): 1893-1900. (Wang Jian-hao, Zhang Liang, Shi Chao, et al. Whale optimization algorithm based on chaotic search strategy[J]. Control and Decision, 2019, 34(9): 1893-1900.) |
[11] |
张永, 陈锋. 一种改进的鲸鱼优化算法[J]. 计算工程, 2018, 44(3): 208-213. (Zhang Yong, Chen Feng. A modified whale optimization algorithm[J]. Computer Engineering, 2018, 44(3): 208-213.) |
[12] |
黄清宝, 李俊兴, 宋春宁, 等.基于余弦控制因子和多项式变异的鲸鱼优化算法[EB/OL]. (2018-11-13)[2018-12-03]. https://doi.org/10.13195/j.kzyjc.2018.0463. (Huang Qing-bao, Li Jun-xing, Song Chun-ning, et al.Whale optimization algorithm based on cosine control factor and polynomial mutation[EB/OL]. (2018-11-13)[2018-12-03]. https://doi.org/10.13195/j.kzyjc.2018.0463. ) |
[13] |
Jangir P, Trivedi I N, Bhesdadiya R H, et al. Training multi-layer perception in neural network using whale optimization algorithm[J]. Indian Journal of Science and Technology, 2016, 9(19): 28-36. |
[14] |
Khaled M, Samir S, Abdelghani B. Whale optimization algorithm based optimal reactive power dispatch:a case study of the Algerian power system[J]. Electric Power Systems Research, 2018, 163: 696-705. DOI:10.1016/j.epsr.2017.09.001 |
[15] |
Prakash D B, Lakshminarayana C. Optimal siting of capacitors in radial distribution network using whale optimization algorithm[J]. Alexandria Engineering Journal, 2017, 56(4): 499-509. DOI:10.1016/j.aej.2016.10.002 |
[16] |
Wang G G, Suash D, Gao X Z, et al. A new metaheuristic optimisation algorithm motivated by elephant herding behaviour[J]. International Journal of Bio-Inspired Computation, 2016, 8(6): 394-409. DOI:10.1504/IJBIC.2016.081335 |
[17] |
Mirjalili S. SCA:a sine cosine algorithm for solving optimization problems[J]. Knowledge-Based Systems, 2016, 96: 120-133. DOI:10.1016/j.knosys.2015.12.022 |