嵌入粒子群优化算法的混合人工蜂群算法

杨琳 孔峰

(广西工学院电子信息与控制工程系，广西 柳州 545006)

0 引言

人工蜂群算法(artificial bee colony，ABC)具有控制参数少、计算简洁、实现方便等特点，已成功应用于函数优化等场合［1-3］。该算法在神经网络训练［4］、滤波器设计［5］、网络优化［6］、机器人路径规划［7］、生产调度［8］等工程领域中也取得了很好的优化效果。

与其他智能算法一样，传统ABC算法也存在早熟收敛、后期收敛速度变慢的缺点。本文将粒子群优化算法(particle swarm optimization，PSO)引入到传统ABC算法中，对在预先设定的搜索次数内没有更新的雇佣蜂，在其现有的位置上拓宽一个范围，作为粒子群优化算法的搜索空间重新进行搜索。

经典函数的测试结果表明，改进后的算法在收敛速度和搜索精度上均优于传统ABC算法。

1 人工蜂群算法简介

在传统ABC算法中［9-10］，蜂群的智能模型包括:食物源、雇佣蜂和非雇佣蜂，其中非雇佣蜂由观察蜂和侦察蜂组成。在整个算法迭代过程中，蜂群对食物源的选择遵循下述原则:食物源(解)被选中的概率取决于所含花蜜的数量，花蜜的数量决定了食物源(解)的优劣;雇佣蜂按照“贪婪”选择的方式对搜索到的食物源(解)进行选择;观察蜂按照概率选择食物源(解)。

对于全局优化问题，令:

设搜索空间为 D 维，Xi(xi1，xi2，...，xiD)∈S 表示第i个食物源的位置，求解最优解的具体步骤如下。首先，ABC算法生成含有N个食物源(解)的初始群体，每个解 Xi(i=1，2，...，N)是一个 D 维向量;然后蜜蜂对所有的食物源进行循环搜索，直到找到问题的最优解。

雇佣蜂和观察蜂按照以下公式对食物源进行位置更新:

式中:i∈{1，2，...，N}、j∈{1，2，...，d}为随机数，且i≠k(k为i邻域的一个解);Rij∈［-1，1］为随机数，用于控制xij邻域的生成范围。

观察蜂通过观看雇佣蜂跳摇摆舞的方式来判断食物源的收益率，并按照食物源被选中的概率选择收益率较高的食物源。

收益率通过收益度值表示，选择概率Pi为:

式中:fiti为第i个解的适应度值。

此外，当某个解在预先设定的搜索次数内没有更新时，为了防止该解陷入局部极值，侦查蜂根据式(4)随机产生一个新解来替换该解。

式中:j∈{1，2，…，d}为d维解向量中的某个分量。

2 粒子群优化算法

粒子群优化算法［11-12］(PSO)是模拟鸟群在空间觅食过程中的迁移和群集对优化问题进行求解。

假设在D维空间中有S个粒子，第i个粒子的位置和速度分别为 Xi=(xi1，xi2，...，xiD)和 V=(vi1，vi2，...，viD)。该粒子所经历的历史最好位置为 P=(pi1，pi2，...，piD)，整个种群所经历的最优位置表示为G=(gi1，gi2，...，giD)。

粒子根据以下公式更新其速度和位置:

式中:r1和r2为［0，1］之间的随机数;c1和c2分别为局部加速因子和全局加速因子;w为惯性权重;k为迭代次数。

粒子的速度更新包括3个组成部分:①当前的速度状态，即惯性部分;②个体粒子自身的经验部分，即认知部分;③单个粒子与种群的协同，即社会部分。此外，为使粒子速度不至于过大，通常会设置速度上限Vmax。当Vi＞Vmax时，Vi=Vmax;当 Vi＜-Vmax时，Vi=-Vmax。

3 混合人工蜂群算法

ABC算法和PSO算法均属于群体智能的启发式优化算法。ABC算法具有很高的收敛速度，但对局部信息的考虑欠缺，容易陷入局部极值，后期收敛速度会变慢。而PSO算法具有较强的全局搜索性能，可以较好地探索求解区域。

在ABC算法中，某个解连续迭代的次数达到或者超过搜索次数后，相应的雇佣蜂转为侦查蜂，并重新在整个参数范围内随机搜索寻找。由于没有依据当前解的信息，因此导致新的侦察蜂性能不够优越。

通过结合PSO算法，既考虑了当前的最优情况，又有全局的探索性，使新侦察蜂在一定范围内进行了细致的寻找。此时侦察蜂性能卓著，保证了全局优化的顺利进行。

混合人工蜂群(particle artificial bee colony，PABC)算法具体实现过程如下。

① 初始化种群。随机产生 N个初始解xi(1，2，...，N)，其中个解与雇佣蜂一一对应。

②计算雇佣蜂所对应的食物源收益率，并按照式(1)对食物源的位置进行更新。

③雇佣蜂将食物源的信息传递给观察蜂，观察蜂按照式(3)随机选择食物源，并在该食物源的邻域内搜索新食物源。

④对搜索到的新食物源进行收益率计算。若其值优于旧食物源，则对旧食物源的位置进行更新，并进入步骤⑤;反之继续搜索。

⑤查看是否满足设定的最终条件，若不满足终止条件，则转向步骤③、④;否则，跳出循环，输出最终解。

达到搜索次数上限后，雇佣蜂转为侦查蜂进行粒子群搜索的具体步骤如下。

①根据当前的解定义粒子群的搜索范围;

②设置最大迭代次数Nmax，随机初始化每个粒子的速度和位置;

③按照粒子群搜索方式更新粒子的个体最优值和全局历史最优值;

④判断是否达到迭代次数，如果没有转入步骤②，否则进入步骤⑤;

⑤用新食物源的位置更新原食物源的位置。

4 算法性能分析

为了验证PABC算法的有效性，本文将PABC算法与基本ABC算法进行试验比较。在仿真试验中选取了3个经典测试函数进行测试。

Sphere函数是一个单模态函数，没有局部极值，只有全局极值，主要用来测试函数的寻优精度和算法的执行能力。Griewank函数是一个复杂的非线性多模态函数，具有很多的局部极小值，通常一般算法都很难找到全局最优解，用来测试算法的全局搜索性能和避免早熟的能力。Rosenbrock函数是一个典型的复杂优化问题，在取值空间内走势平坦，全局最优点恰好处于抛物线的波谷中，几乎不可能收敛到全局最优点。一般情况下，Rosenbrock函数主要用来测试算法的收敛速度和执行能力。测试函数表达式、搜索空间和理论全局最优解如 表1所示。

表1 3个标准测试函数Tab.1 Three of the benchmark test functions

本文在固定的迭代次数下，通过采用比较测试函数的平均值、方差、最优值和最差值的方式对各算法进行评价。

算法参数设置如下:种群规模设置为100、雇佣蜂和观察蜂各为50、测试函数的维数分别为50维和100维、迭代次数为1000。

在PABC算法中，PSO算法参数设置如下:种群规模为24、最大迭代次数为50、局部加速因子c1和全局加速因子c2各为2.0、惯性因子 w为0.8。对每个测试函数连续运行20次，求其平均值。

各函数在不同维数下的平均值、方差、最差值和最优值的比较如表2、表3所示。

表2 测试函数的仿真结果比较(50维)Tab.2 Comparison of the simulation results of benchmark functions(50 dimensions)

表3 测试函数的仿真结果比较(100维)Tab.3 Comparison of the simulation results of benchmark functions(100 dimensions)

Sphere、Griewank和Rosenbrock这3个标准测试函 数的平均适应度曲线如图1～图3所示。

图1 Sphere函数的进化代数曲线Fig.1 The evolution algebra curves of Sphere function

5 结束语

针对人工蜂群算法易陷入局部极值和全局搜索性能不依赖于局部信息的问题，本文结合粒子群优化算法所具有的高效全局搜索性能，提出了基于粒子群优化算法的混合人工蜂群算法(PABC)［13-16］。改进的算法对陷入局部极值的个体使用粒子群搜索策略进行处理，使算法快速跳出局部最优，有效地减少了无用的迭代。试验结果表明，PABC算法不但保持了基本ABC算法的运算特点，而且成功地解决了基本ABC算法易陷入局部收敛的问题。改进后的算法具有较强的全局收敛性，且优化能力显著提高。

［1］Karaboga D.Technical Report-TR06［R］.Kayseri:Erciyes Universy，Engineering Faculty，Computer Engineering Department，2005.

［2］Karaboga D，Basturk B.A powerful and efficient algorithm for numerical function optimization:artificial bee colony(ABC)algorithm［J］.Journal of Global Optimization，2007，39(3):459-471.

［3］Karaboga D，Basturk B.On the performance of artificial bee colony(ABC)algorithm［J］.Applied Soft Computing，2008，8(1):687-697.

［4］Karaboga D，Akayb B，Ozturk C.Artificial bee colony(ABC)optimization algorithm for training feed-forward neural network［C］//Proc of Modeling Decisions for Artificial Intelligence Conference，Berlin:Spring-Verlag，2007:318-319.

［5］Karaboga D.A new design method based on artificial bee colony algorithm for digital IIR filters［J］.Journal of the Franklin Institute，2009，346(4):328-348.

［6］Srinivasa R R，Narasimham S V L，Rama L J.Optimization of distribution network configuration for loss reduction using artificial bee colony algorithm［J］.International Journal of Electrical Power and Energy Systems Engineering，2008，10(2):709-715.

［7］胡中华，赵敏.基于人工蜂群算法的机器人路径规划［J］.电焊机，2009，39(4):93-96.

［8］李端明，程八一.基于人工蜂群算法求解不同尺寸工件单机批调度问题［J］.四川大学学报:自然科学版，2009，46(3):657-662.

［9］Karaboga D，Basturk B，Ozturk C.Artificial bee colony(ABC)optimization algorithm for solving constrained optimization［C］//Foundations of Fuzzy Logic and Soft Computing，2007:789-798.

［10］罗钧，樊鹏程.基于遗传交叉因子的改进蜂群优化算法［J］.计算机应用研究，2009，26(10):3716-3717.

［11］Kennedy J，Eberhart R.Particle swarm optimization［C］//Conf on Neural Networks，Perth，Australia，1995:1942-1948.

［12］Eberhart R，Kennedy J.A new optimizer using particle swarm theory［C］//Porceeding of the Sixth International Symposium on Micro Machine and Human Science，Nagoya，Japan，1995:39-43.

［13］郑伟，刘静，曾建潮.人工蜂群算法及其在组合优化中的应用研究［J］.太原科技大学学报:自然科学版，2010，31(6):467-470.

［14］胡中华，赵敏.基于人工蜂群算法的TSP仿真［J］.北京理工大学学报:工学版，2009，29(11):978-981.

［15］杨进，马良.蜂群优化算法在车辆路径问题中的应用［J］.计算机工程与应用，2010，46(5):214-216.

［16］肖永豪，余卫宇.基于蜂群算法的图像边缘检测［J］.计算机应用研究，2010，27(7):2748-2749.