邻域搜索策略人工蜂群算法的改进

马航航，沈慧娟

（甘肃广播电视大学 a.信息中心；b.理工农医学院，甘肃 兰州 730030

一、引言

受生物信息启发而发展起来的群智能算法[1]是一类重要的元启发式算法，以其独特的优点和机制逐渐成为求解复杂非线性优化问题的一个热门和重要领域。受到蜜蜂群体觅食行为的启发，2005年，Karaboga提出了一种新的群体智能算法——人工蜂群算法（Artificial Bee Colony，ABC）[2]，文献[3-6]通过一系列的测试函数证明了ABC算法具有比遗传算法（GA）[7]、混合蛙跳算法（SFLA）[8]、差分进化（DE）算法[9]和粒子群（PSO）算法[10]更优秀的收敛性能。然而，ABC算法虽然能够保证一定的全局搜索能力，但是其在精细化搜索能力方面还有待改进。针对此问题，文献[11]基于群体最优个体改变了ABC算法的进化迭代公式，提高了算法的局部搜索能力；文献[12]基于DE算法思想，通过蜜蜂群体对当前最优食物源的精细化搜索，提出了一种新的人工蜂群算法；文献[13]提出一种带共享因子改进的人工蜂群算法，通过调节因子的动态调整使算法在全局搜索和局部搜索方面得到了均衡；文献[14]受到PSO算法的思想启发，使算法的进化过程考虑了当前最优个体的启发信息，增加了算法搜索的倾向性；文献[15]根据自然界生物邻域规则，提出了一种基于邻域最优食物源启发信息的ABC算法（NABC），提高了人工蜂群算法的收敛速度和收敛精度。不同于文献[11-14]只是对群体进化公式的改进，文献[15]在环形结构的基础上，确定食物源邻域半径（算法进化过程中，邻域半径保持不变），基于食物源邻域内最优个体方向信息改进了食物源的进化方法，使算法能够以更大的概率发现更为优秀的食物源。相比文献[11-14]的研究成果，文献[15]提出的邻域搜索策略人工蜂群算法在全局搜索能力和深度搜索能力方面同时得到了提高，算法性能相对更高，然而其迭代进化公式只是利用了邻域最优个体的方向信息进行启发，并没有对邻域最优食物源本身的周围进行搜索，使算法在收敛速度方面仍然具有提升的空间。文献[12]研究表明，通过对蜂群最优食物源的精细化搜索，可以有效提高算法的搜索效率，因此，本文将进一步基于此进化思想，对邻域搜索策略人工蜂群算法的进化公式进行改进（INABC），以期使算法的收敛性能得到进一步改善。

二、领域搜索策略的人工蜂群算法（NABC）

在NABC算法中，蜂群由雇佣蜂、观察蜂和侦察蜂三种蜜蜂构成。雇佣蜂在发现新的食物源时，每一个雇佣蜂每次只能开采一个食物源，同样每一个食物源每次也只能被一只雇佣蜂开采；进一步，雇佣蜂通过与观察蜂对食物源的共享，增加了算法的开采深度，观察蜂则会以更大的概率对更加优秀的食物源进行搜索，在此过程中，蜜源更为丰富的食物源将会有可能吸引多只观察蜂对其开采进化，其也意味着较差的食物源将有可能不会被观察蜂所开采；当一个食物源在连续的limit次都没有被蜂群所进化时，侦察蜂负责丢弃多次没有被进化的食物源并随机产生一个新的食物源，如此能够避免算法陷入局部最优。在算法寻优求解过程中，食物源是对求解问题潜在解的一种描述，蜜源是对该食物源的适应值大小的表示。如果优化问题为一个D维空间求解问题，则食物源集合可表示为

x={xi=（xi1，xi2，…，xiD）｜i=1，2…，SN}，SN表示食物源个数，雇佣蜂、观察蜂以及食物源的数量保持一致。当雇佣蜂对食物源完成一次开采进化后，观察蜂将会对较为优秀的食物源进行再次开采，在此过程中，观察蜂将会依据轮盘赌规则选择所要依附的食物源，是算法的局部搜索能力的一种体现；如果停滞次数最大的食物源未在连续的limit次内没有被蜂群所进化，侦察蜂将采用随机搜索的方式在全局范围内产生一个新的食物源代替此食物源，从而增加了算法跳出局部最优的能力。NABC算法的详细流程可描述如下：

（1）依据实际问题对蜂群的寻优空间以及对食物源的最大停滞次数limit进行确定，按式（1）对食物源x={xi=（xi1，xi2，…，xiD）｜i=1，2…，SN}随机初始化：

式（1）中，i=1，2…，SN，j=1，2…，D，maxj和minj为搜索空间第j维的上下限，rand（0，1）为（0，1）之间的随机数，其服从均匀分布。

（2）雇佣蜂以式（2）的方式对食物源迭代更新：

图1 xi的邻域最优食物源的选择

在图1中，r表示xi的邻域半径，NABC算法的思想主要体现在算法进化开始时，将所有食物源按照随机的次序排成一个环形结构，并且在寻优过程中此结构始终保持不变。相较标准ABC算法，NABC算法的食物源进化将会受到其自身邻域内最优食物源的引导启发，并且每一个食物源的邻域构成也是不同的，使算法的全局搜索能力能够得以保证。同时，当前最优食物源将会引导其邻域内的非最优食物源向其自身搜索，通过非最优食物源的不断改善，从而使其能够引导其它食物源的进化寻优，为其它食物源提供了当前最优食物源的方向信息，使算法的深度搜索能力同时也能够得到保证。

（3）按照式（3）计算所有食物源的选择概率：

式（3）中，fiti和fitj分别表示第i和第j个食物源的适应值；pi为第i个食物源的选择概率。如果一个食物源的适应值越大，则其被观察蜂选择依附的概率也就越大。

（4）观察蜂采用轮盘赌规则选择一个食物源按式（2）搜索新的食物源。同样，对于观察蜂发现的新食物源依据贪婪规则决定是否对其保留。

（5）判断停滞次数最大的食物源的停滞次数是否大于最大停滞次数limit，如果大于limit，则由侦查蜂在全局空间内随机搜索一个新的食物源代替停滞次数最大的食物源，否则转至步骤（6）。

（6）判断结束条件是否满足，不满足则转步骤（2）继续迭代。

三、领域搜索策略人工蜂群算法的改进（INABC）

在NABC算法中，蜂群在搜索新的食物源时，邻域最优食物源将会为其提供一定的方向信息，启发雇佣蜂和观察蜂朝着邻域最优食物源的方向搜索，如此机制即保证了食物源搜索具有一定的倾向性，同时也避免了蜂群陷入局部最优。然而，NABC算法的邻域机制保证了不同的食物源具有不同的邻域构成，说明通过算法本身的框架结构就可以使其具有较为优秀的全局搜索能力，虽然通过邻域最优食物源的启发，使蜂群的迭代进化在全局和局部搜索能力方面都有所兼顾，但是从算法的整体搜索能力方面分析可以看出，算法的全局搜索能力有较大幅度的提升，但是深度搜索能力方面仍然有所不足。文献[12]研究表明，使蜜蜂群体通过对当前最优食物源的周围进行搜索，可以有效提高算法的寻优深度和寻优速度。受此思想启发，本文结合NABC算法本身的结构特点，特对蜂群的迭代进化方式进行改进，改进后的算法简称INABC。进化方式改进如式（4）所示：

式（4）中，所有参数代表的意义同式（2）。将式（4）与式（2）对比可以看出，INABC算法将使雇佣蜂和观察蜂始终在邻域最优食物源周围进行搜索，有效提升了算法的精细化搜索能力和寻优速度，而NABC算法只是通过邻域最优食物源提供了方向信息，两者具有一定的区别，同时，不同食物源具有不同的邻域构成，如此将使INABC算法的全局和局部搜索能力方面同时得到提升。IN⁃ABC算法的详细流程如下所述：

（1）采用式（1）所示方法对食物源初始化，并对最大停滞次数limit和算法的邻域半径r赋初值；

（2）将所有食物源按照随机的次序排成一个环形结构；

（3）雇佣蜂搜索的伪代码：

（5）侦察蜂寻找停滞次数最大的食物源，如果其停滞次数大于limit，则通过随机搜索的方法搜索一个新的食物源代替此食物源，否则转至步骤（6）。

（6）判断结束条件是否满足，不满足则转步骤（3）继续进化迭代。

四、实验测试

为了分析INABC算法的收敛性能，本文采用文献[11-15]中的8个60维的测试函数对INABC算法进行实验分析，各函数的表达式、寻优空间以及理论最优值如表1所示。

同时，为了验证INABC算法的性能优势，选择NABC算法进行性能对比，关于INABC算法和NABC算法的参数设置保持一致，食物源个数SN=100，limit=0.6×SN×D，D为具体问题的搜索维度，邻域半径r=30。

设定全局迭代次数G=5000为两种算法搜索的结束条件，所有实验均在内存为4G，处理器In⁃tel（R）Core i5-3750 3.40GHz计算机上，采用VC++6.0实现。为了使实验结果更具客观性，使算法对每一个函数的寻优求解独立运行30次，以30次实验结果的平均值和方差作为标准进行对比，对比结果如表2所示。

从以上结果可以看出，在优化f4和f6时，IN⁃ABC算法和NABC算法同时获得了理论最优解，而对其它函数优化时，INABC算法获得了比NABC算法更优秀的结果，而且在优化f3时，IN⁃ABC算法获得了理论最优解，NABC算法却没有获得最优解，说明INABC算法优势较为明显。这是因为INABC算法在进化计算时，雇佣蜂和观察蜂对食物源进化时，总是能够在其邻域内最优食物源的周围附近进行搜索，迅速使食物源的质量得到了提高，并且由于当前最优食物源对其邻域内非最优食物源质量的改善，这些被改善的食物源将会逐步引导其它食物源在其周围附近进行搜索寻优，如此机制将使算法的寻优速度和寻优能力同时得到保证。同时由于各食物源的邻域构成是不同的，避免了群体全部收敛于某一局部最优解，另外，结合侦查蜂的随机搜索，使算法收敛效率得到提升的同时，算法的全局寻优能力仍然能够得到保证。为了比较两种算法对各函数寻优求解时的收敛速度，两种算法对各函数30次的平均收敛过程如图2所示。

表1 测试函数

表2 两种算法的实验结果对比

图2 两种算法对各函数30次收敛的平均过程

从两种算法对各函数的平均收敛过程可以看出，随着算法迭代次数的变化，INABC算法总能够以较快的速度发现比NABC算法更好的解，这是因为INABC算法在邻域内最优食物源的周围搜索，迅速使食物源的解的质量得到了改善，并且算法的精细化搜索能力也得到了明显的提升，从而使算法的寻优效率更高，对比结果说明，本文提出的进化策略相比NABC算法更加高效。

五、结论

针对NABC算法在深度搜索能力方面存在的不足，本文通过对该算法的迭代进化公式进行改进，提出了INABC算法，使观察蜂和雇佣蜂总是能够在邻域最优食物源附近进行搜索，使食物源的质量迅速得到了提升，有效改善了算法的深度搜索能力和精细化搜索能力。为了对比说明IN⁃ABC算法的性能优势，采用常用的7个60维测试函数进行实验分析，分析结果显示本文对算法的改进是有效的，INABC算法在函数优化时具有比NABC算法更高的收敛效率。