环形拓扑遗传学习人工蜂群算法研究*

王贞 李旭飞

摘要：针对人工蜂群算法探索能力强而开发能力较弱的问题，提出一种基于环形拓扑的遗传学习人工蜂群算法。算法中引入环形拓扑遗传学习策略来生成精英个体，可以增加种群多样性，保证算法的探索能力。同时，在搜索方程中利用精英个体和全局最优个体进行搜索引导，可以提高算法的开发能力，加快算法的收敛速度。通过对6个标准测试函数实验，与其他算法比较发现.所提出的算法较其他算法具有较好的优化性能。

关键词：遗传学习;人工蜂群算法;环形拓扑

中图分类号：TP301.6文献标志码：A

0 引言

2005年Karaboga通过模拟蜜蜂群体觅食行为提出了人工蜂群算法（Artificial Bee Co10ny Algorithm，ABC）。自ABC算法提出以来，由于其良好的优化性能，受到学者们的广泛关注，对ABC算法改进及应用进行了大量研究。过去十几年间，尽管ABC算法得到了有效的改进，但仍存在一些挑战。与其他基于种群的算法类似，ABC算法在优化过程中仍然存在收敛性弱的问题。这一问题与算法中的随机搜索方向和随机步长有关，ABC算法具有较强的探索能力，而开发能力较弱。一般而言，算法的探索能力和开发能力是互相对立的，因此为了提高算法的性能，有必要在算法的探索能力和开发能力间寻求平衡。基于以上分析，本论述采用环形拓扑遗传学习机制，以此平衡算法的探索能力和开发能力，提出基于环形拓扑遗传学习的人工蜂群算法（Genetic learning artificial bee co10ny algorithmwith ring topo10gy，ABC-RTGL）。

ABC-RTGL算法中采用遺传学习策略生成精英个体，并在搜索方程中利用精英个体和全局最优个体进行引导，增强算法的开发能力。另一方面，由于环形拓扑可以扩大算法搜索的可行域，在增强算法开发能力的同时，平衡算法探索能力，在算法中引入环形拓扑。通过对测试问题的实验发现，提出的ABC-RTGL算法具有较好的优化性能，是可行的有效算法。

1人工蜂群算法

受蜜蜂群体采蜜行为启发，Karaboga提出一种新的群智能优化算法——人工蜂群算法。该算法中的人工蜂种群设置为三种类型，包括雇佣蜂、跟随蜂和侦查蜂。首先，在雇佣蜂阶段中，雇佣蜂对可行域进行随机搜索来寻找食物源，并将食物源信息传递给在蜂巢中等待搜索食物源的跟随蜂。其次，在跟随蜂阶段中，跟随蜂根据雇佣蜂传递回蜂巢的食物源信息，选择需要进行搜索的食物源进行采蜜。最后，在侦查蜂阶段，如果所有食物源中有已经被开采完蜂蜜的，则该食物源将会被抛弃，同时与之相对应的雇佣蜂将转变为侦查蜂，重新随机搜索新食物源。在算法的整个搜索过程中，食物源对应的是优化问题的候选解，而食物源的质量代表了候选解的优劣。

在ABC算法中，采用随机初始化方式生成初始人工蜂种群，其生成方式如式（1）所示。

x=x+rand（0，1）（x+x）（1）

其中，i=1，…SN，j=1，…，D，SN表示种群数量，D表示问题维数，rand（0，1）为0-1之间的随机数，x和x分别表示个体第j维的上界和下界。

雇佣蜂通过以下搜索方程对候选解进行搜索：

v=x+φ（x-x）（2）

其中，k∈{1，…，SN}是随机选取的不同于i的指标，在生成新的候选解时仅有一个随机选取的解;j∈{1，…，D}是随机选取的指标，这意味着新候选解与旧解之间仅有一维发生了变化。φ是[-1，1]上均匀分布的随机数。

跟随蜂根据一定的概率对雇佣蜂找到的食物源进行选择更新.其按如下方式进行计算：

其中，fit表示第i个食物源的适应值。选择好食物源的跟随蜂同样利用搜索方程（2）对食物源进行搜索。

2 基于环形拓扑的遗传学习人工蜂群算法

通过上述ABC算法的描述，分析出算法具有较强的探索能力，而开发能力较弱，这种结构在一定程度上会影响算法的收敛速度。针对ABC算法的上述问题，本论述引入环形拓扑的遗传学习策略，来平衡算法的探索能力和开发能力，从而提高算法的优化性能。

2.1环形拓扑

由于环形拓扑结构可以增大可能的搜索空间，在算法搜索过程中，能够有效增加算法的种群多样性，增强算法的探索能力。因此，在精英个体生成过程中采用环形拓扑有利于算法维持种群多样性。环形拓扑生成精英个体方式如式（4）所示。

2.2 遗传学习策略

为了平衡算法的探索能力和开发能力，在原始ABC算法中加入遗传学习策略。该策略主要通过引人遗传算法的交叉、变异和选择操作来生成能够引导算法搜索的有效精英个体。具体策略如下算法2。

算法2：遗传学习策略

Step 1：对个体o进行交叉操作。随机选择个体x，计算其目标函数值fit。若fitk，则按环形拓扑式（4）生成个体o，否则将随机个体x赋给个体o。

Step 2：对个体o进行变异操作。若随机数小于变异概率，则对个体o按初始化方式随机生成。

Step 3：对个体o进行选择操作。估计个体o的目标函数值，若其目标函数值小于当前精英个体e的目标函数值，则利用o对e进行替换。

Step 4：若o的目标函数值小于当前全局最优解的目标函数值，则对当前全局最优解进行更新。

Step 5：若e违背更新代数超过s，则利用轮盘赌选择在当前局部最优解中进行重新选择生成。判定是否所有精英个体都已更新，若更新完成，则返回精英种群和当前全局最优解，否则返回Step l。

通过对原始ABC算法的搜索方程分析，发现该搜索方程具有较强的探索能力，而开发能力较弱。因此，受Lin等学者启发，对ABC算法的原始搜索方程进行如下改进。

其中，k∈{1，…，SN}是随机选取的不同于i的指标，j∈{1，…，D}是随机选取的指标，φ是[-1，1]止均匀分布的随机数，φ是[0，1.5]上均匀分布的随机数。搜索方程中e表示由遗传学习策略生成的第i个精英个体的第j维，y是当前全局最优解的第j维。由此可以看出，搜索方程（5）包含两个学习项，其一是遗传学习项可以增强算法的探索能力;其二是全局学习项，可以增强算法的开发能力。

2.3 基于环形拓扑的遗传学习人工蜂群算法

结合上述的环形拓扑和遗传学习策略，构建了基于环形拓扑的遗传学习人工蜂群算法（Genetic learningartificial bee co10ny algorithm with ring topo10gy，ABC-RTGL），具体算法流程如下算法3。

算法3：ABC-RTGL算法

Step 1：初始化。在搜索空間中利用初始化方程（1）随机生成SN个初始个体组成初始化种群。计算初始种群目标函数值和适应值。记录当前最优解和最优值。

Step 2：雇佣蜂阶段。利用算法2生成精英个体，并用搜索方程（5）生成新的个体，计算新个体的目标函数值和适应值。若新个体的目标函数值优于旧个体，则用新个体替换种群中的旧个体，否则不替换。

Step 3：跟随蜂阶段。对种群中的每个个体利用式（3）计算选择概率，并利用轮盘赌选择对跟随蜂需要更新的个体进行选择。利用算法2生成精英个体，并用搜索方程（5）生成新的个体，计算新个体的目标函数值和适应值。若新个体的目标函数值优于旧个体，则用新个体替换种群中的旧个体，否则不替换。

Step 4：侦查蜂阶段。若种群中存在个体未被更新次数超过上限limit时，利用式（1）随机生成一个新个体对该个体进行替换。

Step 5：记录当前最优解和最优值。若达到终止条件，则结束搜索，返回最优解和最优值，否则，返回Step 2。

3 数值实验

为了检验ABC-RTGL算法的优化性能，本节中将对6个标准測试函数进行测试实验，测试维数D=30，最优值均为0，具体特征见表1所列。实验中种群数量SN为100，limit为200，最大循环代数MaxCycle对应1000，算法独立运行25次。

表2给出了实验结果，包括均值和标准差。同时，在表中给出5%置信水平下Wilcoxon统计测试结果，在表中以“+、=、-”分别表示ABC-RTGL算法优于、相同、劣于其他算法结果。实验结果中较好值均由黑体标出。表2所列，ABC-RTGL算法几乎在所有测试问题上的优化结果都要比原始ABC算法和GABC算法要好。

图1给出了测试问题的收敛曲线图来进一步展现ABC-RTGL算法的优化性能。从图中可以看出，ABC-RTGL算法的收敛速度较ABC算法和GABC算法更快。以上实验结果说明，ABC-RTGL算法不论在搜索最优解的质量方面还是在鲁棒性方面，都比ABC算法和GABC算法更好。

4 结束语

为了更好的求解全局优化问题，本论述给出一种基于环形拓扑遗传学习的人工蜂群算法。由于ABC算法注重探索能力而开发能力较弱，因此引入遗传学习策略来增强算法的开发能力。另一方面，为了平衡探索能力和开发能力，引入了环形拓扑来生成部分精英个体。通过与其他算法在测试问题上的比较结果可以看出，ABC-RTGL算法具有较好的寻优性和鲁棒性。