一种遗传学习人工蜂群算法

杜振鑫，韩德志，刘广钟

(上海海事大学 信息工程学院，上海 201306)

1 引 言

2016年，文献[12]在传统GA交叉算子的基础上，提出了一种新的遗传学习策略(Genetic Learning，GL)，吸收借鉴了现有群体智能进化算法的研究成果及“行为遗传学”原理，综合利用gbest与精英解的信息，与传统GA有明显的不同，在提高了传统GA搜索效率的同时，仍然保持了GA较高的全局搜索能力，为解决这一问题提供了新的思路.

本文将GL策略作为一种通用框架引入人工蜂群算法及其变种的侦察蜂阶段，采用GL策略生成新的食物源代替被抛弃食物源.与简单使用GA交叉算子不同，采用GL策略，可以在利用GA全局搜索特性的同时，利用gbest与较好解加快收敛速度.GA和ABC分属于不同的进化计算分支，具有不同的理论背景和搜索特性.多种文献的研究表明[13]，由于GA的交叉、变异算子没有方向性，因此GA具有较强的全局搜索能力，但也因为缺少精英解的引导而具有较慢的收敛速度.利用GA算法构造出来的新食物源位于问题空间地形图中的不同峰区并且具有较好的多样性，有助于算法跳出局部最优解，GA中的选择操作作用后产生的新食物源位于问题空间中的较好位置，能够为种群的下一步搜索提供较好的指导，避免个体在错误的指导下搜索造成计算资源的浪费和算法效率的低下.一般情况下被抛弃食物源已经处于局部峰区，仅在少数几维上处于劣势，其适应度往往比较优秀，却因陷入局部最优解而无法继续进化.因此，被抛弃食物源与GA结合，可以促进被抛弃食物源快速从一个峰区跳跃到另一个峰区，增强算法的全局搜索能力.而且，GL策略在GA的基础上，综合使用了gbest、被抛弃食物源与其他精英解的信息，在保持GA全局搜索能力的同时，进一步加快了收敛速度，增加了种群多样性，实现了1+1>2的效果.在著名的cec2014函数集上的实验表明，改进算法在寻优精度与收敛速度方面明显优于同类改进算法ABC-GOBL和ABC-CL.同时，改进算法具有较好的普适性，可以作为通用框架嵌入到最新提出的ILABC、ABC_elite等改进人工蜂群算法中，形成更高性能的算法ILABC_GL、ABC_elite_GL.

2 人工蜂群算法

在ABC[1]中，蜂群被分为三种：雇佣蜂、观察蜂和侦察蜂.雇佣蜂搜索食物源，之后将食物源的信息以舞蹈的形式通知观察蜂；观察蜂收到信息后，按照优先选择优秀食物源的原则挑选某个食物源继续开采.若某个食物源的适应度经过limit次未更新，说明这个食物源已没有继续开采的必要，需要抛弃该食物源，该食物源对应的雇佣蜂转变为侦察蜂，随机初始化一个新的食物源代替该食物源，但是为了保持系统的稳定性，每一轮只允许trial值最高的一个食物源初始化.

在ABC算法中，一个食物源代表一个待优化问题的可行解.每个食物源的花蜜数量相应代表待优化问题的适应度，雇佣蜂和观察蜂的数量相等.不失一般性，设待优化问题为求最小值，首先按照公式(1)随机生成SN个初始解(SN等于雇佣蜂或者观察蜂的数量)：

Xi，j=Xmin，j+rand(0，1)(Xmax，j-Xmin，j)

(1)

其中，i=1，2，…SN，j=1，2，…D，D是决策变量的数量，也就是待优化问题的维数，Xmin，j是第j维的下界，Xmax，j是第j维的上界.初始化之后，ABC在下面的三个阶段搜索问题的最优解：

1)雇佣蜂阶段：每个雇佣蜂仅仅与一个食物源相关联，所以在雇佣蜂阶段，雇佣蜂的数量与食物源的数量相等.在该阶段，每只雇佣蜂在相应的食物源Xi处，利用搜索方程随机选择第j维更新，生成一个新的食物源Vi：

Vi，j=Xi，j+φi，j*(Xi，j-Xk，j)

(2)

其中，φi，j是[-1，1]之间的随机数，j∈{1，2，…，D}是随机选择的一个维，k∈{1，2，…SN}是随机选择的一个食物源，k≠i.发现新的食物源Vi之后，如果Vi的函数值f(Vi)好于f(Xi)，就用Vi替换Xi，否则Xi保持不变.

2)观察蜂阶段：在所有雇佣蜂完成了勘探之后，观察蜂根据接收到的信息随机选择一个食物源，进一步开采.观察蜂按照公式选择食物源：

(3)

其中，fiti是食物源Xi的适应度值，设待优化问题是求最小值，则函数值越小，适应度值越高；SN是雇佣蜂的数量，也等于观察蜂的数量.选择食物源之后，观察蜂用公式搜索新的候选解，跟雇佣蜂阶段一样，采用贪婪选择策略，如果搜索的新的解的适应度更好，则替换掉原食物源，否则原食物源保持不变.

3)侦察蜂阶段：如果一个食物源经过limit次搜索仍然没有成功更新，该食物源被抛弃，该食物源对应的雇佣蜂成为侦察蜂，该侦察蜂按照公式(1)通过初始化被抛弃的食物源代替被抛弃的食物源.

3 遗传学习框架

本文利用GL策略构造新的食物源代替被抛弃食物源，构造过程采用了交叉、变异、选择三个基本遗传算子.交叉算子作用于被抛弃食物源、精英解与gbest，以综合利用三者的信息，增加多样性，同时加快收敛速度.此外，算法继承了传统GA中的均匀变异策略使得产生的新食物源能够覆盖到整个问题的任意区域.进一步的，选择算子以较大概率保证构造的新食物源比被抛弃食物源更好，从而有效牵引整个种群搜索越来越好的区域.

1)交叉算子：对于每个被抛弃的食物源Xi，按照下面的公式产生一个子代sol=[sol1，sol2，…，solD] ：

首先，在当前种群中随机抽取两个食物源，其序号是s1、s2，s1≠s2≠i，令：

(4)

(5)

其中，rd是在[0，1]之间均匀分布的随机数，gbest是当前最优个体.在公式的作用下，如果被抛弃的食物源Xi在Xi、Xs1、Xs2三者中适应度最优(即函数值最小，这里以求最小值为例)，则其后代sol来自Xi与gbest的交叉.否则，如果被抛弃食物源Xi不是三者之中最优的个体，则其子代的第d维来自个体s1、s2中最好的一个个体s的第d维.

公式(5)与传统GA算法的不同之处在于，GA算法随机选择种群中的两个个体进行交叉产生子代，而公式(5)同时采用了竞争策略，子代的第d维，来自i，s1、s2三者中较好的个体的第d维.在这种方式作用下，一个被抛弃食物源倾向于在自身、精英解和gbest之间进行算术交叉，从而产生潜在更优秀的子代sol.否则，如果被抛弃食物源i是当前种群中较差的一个，sol将会有更多的维度来自其余更优秀的精英个体.因此，不同于传统的GA中随机选择种群中的两个个体进行交叉，以上交叉算子同时利用了被抛弃食物源的自身信息、gbest和精英解的信息，在已经发现的优良位置上进行交叉操作，有助于交叉算子更加有效地产生优秀的子代，而且增加了种群多样性.同时，被抛弃食物源、gbest和精英解的引导加快了GA的收敛速度.

2)变异算子：产生子代sol之后，采用变异概率Pm对sol的每一维随机变异，类似于传统GA中的均匀变异策略.对于sol的第d维，产生一个随机数[0，1]之间的随机数rand，若rand

sold=Xmin，d+rand*(Xmax，d-Xmin，d)

(6)

其中，Xmin，d和Xmax，d分别表示搜索空间的第d维的下界和上界(d=1，2，…D).rand是[0，1]之间的随机数.这种变异方式保证了产生的子代能够到达搜索空间的任意位置，从而为个体注入新的基因、防止新食物源的早熟收敛.

3)选择算子：通过交叉和变异产生的子代sol将在选择操作中与被抛弃食物源Xi竞争，如果找到的sol好于Xi，则提前结束GL过程；否则会重复上述试探过程Tmax次，直到找到比Xi更好的新食物源sol.如果超过规定的Tmax次试探仍然没有找到好于被抛弃食物源Xi的新食物源，则取Tmax次试探过程中生成的最好的一个食物源作为新食物源，避免浪费计算资源.这种机制保证新产生的食物源绝大部分情况下只会随着代数进化而不会发生退化，从而更有利于找到更好的峰区.

4)整体流程：在ABC的每次迭代，对每个满足triali>limit的食物源i，都执行以上试探操作，包括交叉、变异和选择操作，从而构造一个优良的新食物源代替被抛弃食物源，每个被抛弃食物源Xi最多可以试探Tmax次，如果找到更好的食物源则提前退出.注意上述过程是反复试探(try)而非迭代(iteration)，因此每次寻找新的食物源sol都是重新开始，而与上次的试探无关，因为GL策略的目的是快速跳出局部最优解而非精细搜索，采用试探操作可以快速的在不同峰区跳转，寻找更有潜力的峰区以进一步开采，而迭代操作主要围绕某一个固定的峰区搜索.GL策略如图1所示.

01：fori=1toSN /∗对每个食物源i∗/02： if triali>limit/∗如果食物源i的trial值大于limit，则执行GL策略∗/03： ifiisnotgbest /∗普通个体与gbest分开处理∗/ 04： k=0； /∗k是试探次数计数器∗/05： while(k

图1 GL策略的伪代码

Fig.1 Pseudo-code of the GL strategy

从图1可以看出，与基本ABC不同，在ABC-GL中，所有满足triali>limit的食物源i均执行GL操作(第1行)，而在ABC中每一轮只有一个trial值最大的食物源被初始化，这是因为基本ABC中，被初始化的解质量较低，过多的食物源被初始化，容易引起算法的退化和震荡.如果被抛弃食物源恰好是gbest，则公式(5)中的gbest用随机选择的5个食物源中不同于gbest的一个食物源代替(第25行)；若经过Tmax次试探之后仍未发现更好的解，则gbest保持不变，以保证gbest不退化.

通过在ABC的侦察蜂阶段嵌入GL策略，可以得到ABC-GL算法，其具体步骤如下：

Step1. 初始化：

a.根据公式(1)随机生成含有SN个初始解的种群

b.评价整个种群，FEs=SN；/*FEs代表函数评价次数*/

Step2. 雇佣蜂阶段：

fori=1：SN，do

a.根据公式(2)生成一个候选解Vi

b.评价f(Vi)，FEs=FEs+1

c.若f(Vi)

否则，triali=triali+1；

endfor

Step3. 由公式计算每个食物源Xi的概率pi，t=0，i=1；

Step4. 观察蜂阶段：

whilet<=SN，do /*轮盘赌选择一个食物源开采*/

ifrand(0，1)

a.根据公式(2)，生成一个候选解Vi

b.评价f(Vi)，FEs=FEs+1

c.若f(Vi)

否则，triali=triali+1；

d.t=t+1

endif

i=i+1，若t=SN，置i=1

endwhile

Step5. 观察蜂阶段：

a.记住全局最优解gbest

b.根据图1，执行GL模块

Step6. 若FEs>=Max_FEs，算法终止，输出gbest，

否则，转step 2.

与基本ABC相比，ABC-GL与ABC的区别是在侦察蜂阶段采用GL模块(Step 5的黑体部分)，取代ABC的随机初始化，其他部分与基本ABC相同.GL策略可以作为一种通用框架嵌入到其他改进人工蜂群算法中，只需要将图1中的遗传学习策略替换掉对应算法的侦察蜂阶段即可.例如，将图1嵌入到ABC_elite[16]的侦察蜂阶段，即可得到基于遗传学习框架的增强型算法ABC_elite_GL；将图1中的遗传学习策略嵌入到ILABC[17]可以得到增强的ILABC_GL算法等.

4 实验结果与讨论

4.1 测试函数与参数设置

实验采用cec2014[14]中的1-16号函数，该函数集中的所有函数在基本函数的基础上采用偏移、旋转增加求解难度，具有大量的局部最优点，可以较好的测试算法的综合性能.其中，F1-F3是单峰函数，F4-F16是多峰函数.

表1 四种算法在cec2014函数集上的测试结果Table 1 Experimental results of 4 algorithms on cec2014 test suite

参数设置：SN=30，limit=100，D=30，最大函数评价次数Max_FEs=300000.GL策略新增了两个参数Pm与Tmax，根据实验确定较好的设置是Pm=0.03，Tmax=20.实验在同样条件下重复运行30次.

图2 收敛曲线图Fig.2 Convergence curves

4.2 实验结果与分析

表 1给出了ABC、ABC-GOBL、ABC-CL、ABC-GL四种算法在cec2014中1-16号函数上的实验结果.实验的主要目的是测试本文提出的GL策略是否可以增强ABC算法的性能.mean和std指标分别表示求解结果的均值与标准差.根据表1，ABC-GL算法的求解精度除了f2之外，都好于另外3种算法.图2给出了ABC、ABC-GOBL、ABC-CL、ABC-GL四种算法在函数F1、F6、F9、F16上的收敛曲线图.从图2来看，ABC-GL只在算法开始运行的较短时间收敛速度落后于其他算法，但是很快超过其他算法.这是因为ABC、ABC-GOBL虽然在较短的时间内收敛速度很快，却由于没有充分利用多个精英解的信息，从而导致算法很快陷入局部最优解，ABC-CL虽然利用了多个精英解的信息帮助算法跳出局部最优解，却由于缺少gbest的引导而收敛较慢.从图2中F6、F9、F16上的收敛曲线图来看，ABC-CL、ABC-GL直到算法运行结束，仍然保持进化状态而未停滞，而另外两种算法ABC与ABC-GOBL的曲线图很快变成一条直线.这说明，由于ABC-CL与ABC-GL采用的多个精英引导，不容易陷入局部最优解.同时，由于ABC-GL采用了新颖的GL策略，同时使用gbest与多个精英的信息交叉，因此收敛速度更快，且不容易陷入局部最优解.表1、表2与表3同时给出了Wilcoxon[15]显著性水平0.05的秩和检验结果，+、=、-分别表示应用GL策略的增强算法好于、等于、差于其他对比算法.表1、表2与表3的最后一行给出了Wilcoxon的统计结果.

表2 应用GL策略加强ABC_elite算法性能的实验结果Table 2 Experimetal results to enhance the performance of ABC_elite using GL strategy

表3 应用GL策略加强ILABC算法性能的实验结果Table 3 Experimetal results to enhance the performance of ILABC using GL strategy

GL策略的主要作用是增强其他改进ABC算法的性能.表2给出了应用GL策略增强ABC_elite[16]性能的实验结果，其中，应用遗传学习框架(GL)、综合学习(CL)策略、反向学习(GOBL)策略的ABC_elite分别称为ABC_elite_GL，ABC_elite_CL，ABC_elite_GOBL.从表2来看，在单峰函数f1-f3上，ABC_elite_GL算法的性能优势较小.而在多峰函数f4-f16上，ABC-elite_GL只在函数f6上稍差于ABC_elite_CL，在其余所有多峰函数上都表现出最好的性能.

表3给出了应用GL策略增强ILABC[17]算法的结果.从表3结果来看，除了多峰函数f4、f7上，ILABC_GL没有取得最好结果，在其余所有函数上均取得了最好的结果.表2和表3的结果说明，应用GL策略可以有效增强其他改进人工蜂群算法的性能，加快算法的收敛速度，提高求解精度.

5 结 论

为了加快ABC及其改进算法的收敛速度并提高搜索精度，本文将遗传学习策略作为通用框架引入人工蜂群算法，用于增强这些算法的性能.遗传学习策略较好的平衡了算法的全局搜索与加速收敛之间的矛盾，能够较好的弥补各种改进人工蜂群算法的不足.本文仅提供一种通用框架，而非一种独立算法.实验表明，采用遗传学习策略作为通用框架，可以方便的嵌入各种改进人工蜂群算法，显著提高这些算法的收敛速度，提高其搜索精度.