一种元启发式算法: 海岛算法

2019-07-20马吉明苏日建张国良陈浩洋山石姣

郑州大学学报(工学版) 2019年4期

马吉明，张嵩，苏日建，张国良，陈浩洋，山石姣

(郑州轻工业大学计算机与通信工程学院，河南郑州 450001)

0 引言

经过漫长的时间演化，大自然造就了很多奇妙的现象，令人叹为观止的同时也给人们为解决问题带来了无限的启发.人们从各种现象中汲取智慧.例如，根据自然界的生物进化按“适者生存，优胜劣汰”这一规律提出了遗传算法(GA)[1]；受生物免疫系统启发而设计的人工免疫算法(AIS)[2]；受到即兴创作音乐作品的启发而提出的和声搜索算法(HS)[3]；根据金属的退火过程提出模拟退火算法(SA)[4].根据动物的觅食行为，众多学者提出了很多智能算法，包括粒子群算法(PSO)[5]、蚁群算法(ACO)[6]、萤火虫算法(FA)[7]、蝙蝠算法(BA)[8]、狼群算法(WPA)[9]、细菌觅食优化算法(BFA)[10]、布谷鸟算法(CS)[11]、人工鱼算法(AFSA)[12]、蛙跳算法(SFLA)[13]、人工蜂群算法(ABC)[14]、鸡群算法(CSO)[15]、天牛须算法(BAS)[16]等.这样的元启发式算法成为解决许多棘手优化问题的有效方法.由于这些算法都具有某些优点和缺点，很多学者针对其缺点不断进行改进，并应用于合适的领域中[17].因此，从自然界中获取新启发，为解决优化问题等提供新思路仍然具有意义.

笔者根据海岛上植物的生长位置随着海平面的上升及海岛面积的缩小，越来越集中于最高点的现象，提出一种新的元启发式算法，即海岛算法(IA).海岛算法通过不断升高海平面的同时，维持植物总数不变，从而来寻找最佳点位置.通过实验，与已经广泛应用的粒子群算法进行对比.实验表明，相比于粒子群算法，海岛算法在CEC2013函数集上，总体上保持优势.

1 海岛算法

海岛算法是一种新的元启发式算法.海岛算法分为3个阶段：淘汰阶段、海平面上升阶段、平衡阶段.

1.1 淘汰阶段

该阶段是为迭代的海平面上升阶段做准备，主要的任务是根据范围的变化量来产生本次迭代需要淘汰植物的个数.因为至少需要2个植物才能定义海岛的范围，所以淘汰后，未被淘汰的植物个数至少为2，即最大的淘汰个数要小于总量数减2.该阶段的任务由淘汰函数完成.淘汰函数的自变量为范围的变化量，函数值为淘汰个数.当范围变化量比较大时，为了避免陷入局部解，应减少淘汰个数来减小下一次的范围变化量；当范围变化量比较小时，为了加快算法收敛，应增加淘汰个数来增大下一次的范围变化量.故函数满足以下两点要求：

(1)范围变化量为零时，淘汰个数为最大淘汰个数.

(2)淘汰函数为一个递减函数，随着范围变化量的增大，淘汰个数将减小.

采用既满足以上两点要求又较为简单的负指数函数：

fout(h)=[(Am-Al)·e-h]+Al,

(1)

式中：h为范围变化量，由上次迭代中海平面上升阶段产生；Am为最大淘汰个数；Al为最小淘汰个数.

1.2 海平面上升阶段

海平面上升阶段将根据淘汰阶段产生的淘汰个数来提升海平面.海平面的提升表现为海岛范围的缩小.该阶段的主要任务是产生新的海岛范围以及海岛范围变化量.其中，新的海岛范围为接下来的平衡阶段做准备，范围变化量为下次迭代中淘汰阶段做准备.

海岛的新范围由未被淘汰的植物所生长的范围所决定.新范围由每一维度的最大值Xmax和最小值Xmin表示.为了避免由于收敛过快，易陷入局部最优位置，将范围通过公式2和3进行扩展.

(2)

(3)

海岛范围变化量由公式4表示：

(4)

1.3 平衡阶段

平衡阶段的主要任务是在海平面上升的同时，维持植物的总量不变，并根据位置高度进行排序.具体的实现是在海平面上升阶段产生的新范围内，产生A个新植物，替换种群中最差的植物，从而使植物总量不变.

为了加快搜索速度，提高搜索精度，将每一个新植物通过式(5)朝着全局最优植物处移动，然后评估该植物，若优于全局最优植物，则将两者的位置和适应度值进行交换.

x(j,:)=x(j,:)+2·rand(1,D)·

(x(1,:)-x(j,:)),

(5)

式中：x(j,:)为在新范围内产生的第j个新植物位置；x(1,:)为全局最优位置；D为维度；2为参数，使移动后的位置在当前位置向最优位置方向上以2倍的距离均匀分布.

移动和评估完所有新植物后，所有植物根据适应度值进行排序.在程序中，测试函数的适应度值即为植物的位置高度，当按照从大到小排序时，即求解测试函数最大值；当按照从小到大排序时，即求解测试函数最小值.3个阶段相互依存，关系如图1所示.每一次的迭代包含该3个阶段.

图1 3个阶段关系图Fig.1 Three-stage relationship

1.4 算法流程

基本海岛算法的步骤如下.

步骤1 参数初始化：设最大评估次数E，海岛的维度D，淘汰个数的最大最小值分别为Am，Al，范围变化量h，植物总量N，植物的生长位置为xi(i=1,2,…,N)，海岛范围Xmax,Xmin.

步骤2 进入淘汰阶段，根据式(1)生成淘汰个数.

步骤3 进入海平面上升阶段，记录上次迭代的海岛范围，产生新的海岛范围，根据式(2)和(3)，对新范围进行扩展，根据式(4)产生海岛范围变化量h.

步骤4 进入平衡阶段，在新的海岛范围内根据淘汰个数产生新植物，并对植物种群中最差的植物进行淘汰.

步骤5 每一个新植物向最优植物处移动，求解新植物的适应度值，若优于最优植物，则进行交换，最后对所有植物进行排序.

步骤6 若达到终止条件，输出结果，终止算法.否则，转入步骤2，进入下一次的迭代.

算法伪代码如下所示.

输入：初始化N、Al、Am、h、D、E，

Xmax=100·ones(1,D)，Xmin=-100·ones(1,D),

x=ones(N,1)·Xmin+ones(N,1)·(Xmax-Xmin)·rand(N,D);

获取每一个植物对应的适应度值，并排序

输出：最优值位置x(1,:)，最优值适应度值fit(1)

1：while(结束条件)

2：淘汰阶段

3：根据式(1)生成淘汰个数；

4：海平面上升阶段

6：Xmax=max(x(1:N-taotai,:));

7：Xmin=min(x(1:N-taotai,:));

8：对新的海岛范围使用式(2)和式(3)进行扩展；

9：根据式(4)产生范围变化量；

10：平衡阶段

11：在新范围内产生A个新植物，替换最差的A个植物；

12： forj=N-A+1:N；

13：根据式(5)进行移动；

14： if(达到最大评估次数)

15：输出结果，算法结束

16： else

17：fit(j)=Fun(x(j,:)); 评估次数加一;

18：判断是否优于最优植物，是则进行交换

19： end

20： end

21： [fit,index]=sort(fit);x=x(index,:);

22：end

2 算法分析及对比

2.1 算法分析

相比于粒子群算法、蝙蝠算法、蜂群算法等，海岛算法在每次的迭代中，并未对每一个植物进行位置的更新和评估，而是只更新最差的植物，个数为淘汰阶段产生的淘汰个数.这样不仅可以在每一次迭代中减少计算量，而且也保留了相对较好的位置信息，其信息将在接下来多次的迭代中被利用，直到该位置被淘汰.因此，算法对每一个位置信息都有着充分的利用.这也是海岛算法能体现优越性的关键原因.

当求解的函数存在连续梯度很小或很大区域，即存在连续平坦或有尖锐峰或谷的区域，如图2所示，将不适合算法的求解.

图2 不利情况Fig.2 Unfavorable situation

由于搜索范围内存在很大的平坦区域，新增的植物位于平坦区域的概率很高，因此，海平面上升阶段，海岛的范围变化不大，甚至为0，不利于算法的收敛.但通过淘汰阶段产生更多的淘汰个数，最终使其跳出局部解.最极端的情况下，只保留2个植物，其余全部淘汰.据此，也可以预测出，该算法不适合求解具有众多尖锐的峰，且峰周围区域较为平坦的函数.典型函数如f8函数.

在求解函数的整个求解区域内，梯度相对适中，即没有连续平坦和尖锐峰或谷的区域，如图3所示，将适合算法的求解.

图3 有利情况Fig.3 Favorable situation

在该搜索区域范围内，新增的植物更易处于不同的高度，这将有利于算法往最优位置处收敛.典型函数如f1函数.

由于植物随机分布在搜索范围内，在算法初期，搜索范围较大，仅通过范围的缩小来使算法收敛，相较于单个粒子根据其他信息寻找最优位置的算法如粒子群优化算法，收敛速度慢，但将新植物向最优植物处移动，大大提高了算法的收敛速度，而通过对新范围的扩展，使算法又尽可能避免因收敛过快而陷入局部最优位置；在算法后期，随着搜索范围逐渐缩小，整个种群在一个小范围内寻找最优位置，加速了收敛速度，从而达到更好的精度.海岛算法是整个种群通过淘汰方式逐渐缩小搜索范围来寻找最优区域，相较于单个粒子寻找最优位置的算法，具有更强的鲁棒性.

若取每次迭代的平均评估次数为(Am+Al)/2，则公式及排序操作的次数为2E/(Am+Al)，与最大评估次数成线性关系，故算法的计算复杂度为O(n).

2.2 算法对比

有些元启发式算法在新粒子生成方式上，基于粒子的当前位置，根据其他信息调整步长及方向进行移动来生成新粒子，一般都具有惯性权重系数.如粒子群算法利用个体认知和社会认知信息，蝙蝠算法利用回声定位信息.在收敛方式上，这些信息调整的步长和方向将会引导种群收敛于最优值.

有些元启发式算法在新粒子生成方式上，是在整个搜索区域内，通过应用某种策略来产生新粒子.如遗传算法通过选择、交叉和变异3种算子来产生新粒子，人工蜂群算法通过侦察蜂随机搜索、采蜜蜂采蜜、观察蜂跟随3种方式来产生新粒子.在收敛方式上，遗传算法采用适者生存的原则，人工蜂群算法采用贪婪准则来更新差粒子，通过不断更新差粒子来实现种群朝着最优值收敛.很多元启发式算法从某种程度上讲，都是通过迭代，不断地生成新粒子和更新差粒子，使种群朝着最优值收敛.

IA算法在新粒子生成和收敛方式上与上述两种不同.新粒子采用最简单的随机搜索策略生成于不断缩小的搜索范围内，通过更新最差个体使搜索范围缩小，再通过不断缩小搜索范围来使算法收敛.

3 实验仿真分析

3.1 实验设计

为了验证本文海岛算法的性能，通过解决CEC2013测试集中测试函数来分析所提算法的性能.CEC2013测试集中包含28个函数，其中f1～f5为单峰函数，f6～f20为多模态函数，f21～f28为组合函数，搜索范围均为[-100,100].如表1所示.

实验环境是在Windows 10系统Matlab R2014a软件，CPU为i5-3470 3.20 GHz，RAM为4 GB.

海岛算法的参数设置如表2所示.

为了体现算法的优越性，在相同的条件下，与已经被广泛使用的粒子群算法进行对比.两个算法的种群大小一致.粒子群算法的社会认知系数为1.5，个体认知系数为1.5，惯性权重系数为0.8.

表1 测试函数Tab.1 Test function

表2 参数设置Tab.2 Parameter settings

针对每一个函数，两个算法分别在搜索维度为10、30和50上独立运行51次，并将计算结果进行对比分析.由于海岛算法每次迭代中，对测试函数的评估次数无法确定，故通过比较相同的评估次数下计算结果的精度，来比较算法的性能.

3.2 实验结果及分析

两个算法分别在搜索维度为10、30和50上，分别对测试函数评估100 000、300 000、500 000次.将51次中所得最优误差值、最差误差值、中间误差值、平均误差值和其标准差作为算法精度和鲁棒性的衡量指标，如果小于10-8，则认为0.10维运行结果如表3～4所示，20维和30维运行结果如图4～5所示.

表3 10维f1～f7Tab. 3 10 dimensional f1～f7

图4 30维运行结果Fig.4 Operation results of 30 dimensional

图5 50维运行结果Fig.5 Operation results of 50 dimensional

f8函数是指数函数叠加上适度放大的余弦而得到的连续性测试函数，其特征是一个几乎平坦的区域由余弦波调制形成一个个孔或峰，从而使曲面起伏不平，有着较为平坦的区域和陡峭的峰，同样有此特点的函数还有f2、f3、f4函数.f14、f15、f16、f22和f23有非常密集的陡峭的峰和谷形成的众多局部最优位置，从对算法的分析中可知，海岛算法并不适用于求解具有此类特点的函数.

在51次独立运行的结果中，28个函数中有5个函数f2、f3、f8、f15、f16，在10、30、50维度上均差于PSO算法，f4、f14、f22和f23在30、50维度上均差于PSO算法.其余函数在3个维度中均优于PSO算法，验证了算法的分析及算法的有效性.从总体上看，海岛算法在CEC2013函数集中的大部分函数中表现优异，相同条件下海岛算法的精度和鲁棒性普遍优于已被广泛应用的粒子群算法.