基于错位突变策略的改进人工蜂群算法

《基于错位突变策略的改进人工蜂群算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于错位突变策略的改进人工蜂群算法蒋成1，汪继文2，邱剑锋1（1.安徽大学计算机科学与技术学院；2.安徽大学计算智能与信号处理教育部重点实验室,安徽合肥230601）摘要：人工蜂群算法是一种模拟蜜蜂觅食行为的群智能优化算法，具有较好的全局搜索能力，但收敛速度较慢且容易陷入局部最优.针对其不足之处,提出了一种基于错位突变策略的人工蜂群算法（DMABC）.该算法在搜索蜜源的时候运用错位突变策略增强种群多样性，并使用排序选择机制和新的比较机制防止过早收敛.通过对几个标准测试函数的实验表明，改进算法具有更快的收敛速度，优化精度更高.

2、.jyqkli[6]将人工蜂群算法应用于旅行商问题中.Ozturk[7]等使用了人工蜂群算法解决无线传感器网络的动态部署问题.胡中华等[8]实现了将人工蜂群算法应用于机器人路径规划问题.肖永豪等[9]提出了一种基于蜂群算法的图像边缘检测方法.然而随着对人工蜂群算法研究的深入，人们发现该算法同样存在着缺点：算法收敛速度较慢，且容易陷入局部最优.针对这些缺点，国内外的学者们相继提出了改进的人工蜂群算法.丁海军等[10]基于Boltzmann选择机制提出了一种改进的人工蜂群算法用来优化多变量函数.暴励等[11]结合差分进化算法提出

3、了一种新的双种群差分蜂群算法.Lee等[12]在人工蜂群算法中引入群体多样性的机制，根据群体多样性的门槛值选择采用不同的搜索公式.Alam等[13]提出了一种基于指数分布的自适应变异步长机制的人工蜂群算法，动态控制搜索过程中的探索和开发能力.在人工蜂群算法中，全局搜索和局部开采的平衡是决定算法性能好坏的关键.本文在基本人工蜂群算法的基础上，借鉴差分进化算法的突变算子，提出了一种新型的错位突变策略，应用于蜜蜂的搜索过程中，以提高种群的多样性.同时，还用排序选择机制代替了原来的轮盘赌选择机制来防止算法的过早收敛.为了测试改进算法

4、的性能，本文用了几个标准测试函数来做实验.实验结果表明，改进算法的性能优于基本人工蜂群算法.2基本人工蜂群算法Karaboga提出的基本人工蜂群算法将蜜蜂分为三类：引领蜂、跟随蜂和观察蜂.蜂群在一个D维的空间中寻找蜜源，这里的D是在算法开始时人为设定的，在函数优化问题中D就等于目标函数的变量数.一个蜜源对应目标函数的一个可行解.在算法中，蜜源用它在D维空间的位置向量表示.例如，第i个蜜源用i表示，i=(xi1,xi2,…,xiD)，向量中每个分量的取值范围由目标函数的解空间决定.寻找最优蜜源，在本文中也就是寻找一组能让目标函

5、数取得最小值的可行解.蜂群分成两半，一半是引领蜂，一半是跟随蜂.引领蜂和蜜源一一对应，每个引领蜂的位置就是一个蜜源的位置.因此，在程序中，引领蜂的数目、跟随蜂的数目和蜜源的数目都相等，设为SN,则种群的规模也就是2*SN.SN也是一个需要人工设定的参数.整个算法是一个循环算法.每次循环的开始，引领蜂会在各自对应的蜜源周围进行搜索.搜索的公式如下：其中，?渍(i,j)是-1到1的随机数，k是引领蜂随机选择的一个邻近蜜源，作为扰动项，增强全局搜索能力.引领蜂搜索的时候只改变位置向量的一个分量，这个要被改变的分量也是随机选择出来的

6、.通过(2)式得到一个新的蜜源位置后，引领蜂会对新蜜源进行评估，计算出适应度值与旧蜜源比较.适应度的计算公式如下：fi是用第i个蜜源的位置向量作为可行解计算出来的目标函数值.从(3)式可以看出，目标函数值越小，该蜜源的适应度值就越大.引领蜂经过比较后，如果新蜜源的适应度值大于旧蜜源，则更新蜜源的位置；反之，则保留旧蜜源.跟随蜂则通过轮盘赌机制选择蜜源进行搜索.适应度值越高的蜜源会有更大概率被跟随蜂选中从而得到更新.跟随蜂的搜索方程与引领蜂相同.轮盘赌的选择概率使用下面的公式计算出来的：由于人工蜂群算法有陷入局部最优的可能，因

7、此算法中设置了侦察蜂的操作来跳出局部最优.当一个蜜源经过很多次循环仍无法得到更新，那么该蜜源对应的引领蜂就会转化为侦察蜂，舍弃旧蜜源，在搜索空间内随机生成一个新的蜜源.侦察蜂的搜索公式如下：lj和uj分别是搜索空间的下界和上界，rand(0,1)是0到1的随机值.侦察蜂操作的触发条件是有蜜源的停滞次数达到了限定值，姑且将这个限定值设为limit.limit的值是需要人工设定的.大量的实验表明，limit的设定会影响到算法的效果，定值太小会减缓收敛速度，定值太大又起不到跳出局部最优的效果.后来研究者们发现，将limit的值设为

8、SN*D可以得到不错的实验效果，因此本文中limit的值也是SN*D.除此之外，还有一个最大循环次数需要人工设定，这是算法的终止条件.3基于错位突变策略的人工蜂群算法基本人工蜂群算法在搜索蜜源的时候，由于其搜索方向是随机的，因此具有较好的全局搜索能力.但正因为它的搜索完全随机，没有任何启发