基于变异机制的人工蜂群算法.docVIP

基于变异机制的人工蜂群算法 　　摘要：针对人工蜂群算法存在的收敛速度慢、易陷入局部最优的缺点，利用变异方法来取代传统的选择模型。对4个标准测试函数的仿真表明本文提出的随机选择算法不仅能延长算法的收敛速度还能在算法的精度上有着明显的提高，改进后的性能明显优于人工蜂群算法。 　　关键词：人工蜂群算法；变异；收敛速度 　　中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2013）33-7575-02 　　Karaboga于2005年基于蜜蜂采蜜的高效方式提出了用于解决函数优化问题的人工蜂群算法（artificial bee colony algorithm，ABC）[1]，这是一种群体智能化算法并与经典的遗传算法（GA）、蚁群算法（ACO）和粒子群算法（PSO）等进行了比较，确定了ABC在函数优化方面无与伦比的优越性。该算法具有较强的灵活性和鲁棒性且已得到全局最优解。然而作为一种新兴的算法，它的相关研究还不是很成熟[2]，虽然文献[5]采用混沌有哪些信誉好的足球投注网站策略来自适应的调整有哪些信誉好的足球投注网站空间，文献[6]使用boltzmann选择方式进行蜜源的选择，文献[7]通过引入遗传交叉因子增加了种群多样性并依此来改变原蜜源的结构，都在一定程度上降低了算法陷入局部最优的可能，但也不得不受算法的时间精度限制。为此，该文通过深入研究提出了一种新的基于变异机制的人工蜂群算法来有效解决上述问题，并用了几个标准测试函数加以测试。 　　1 人工蜂群算法 　　ABC模拟实际蜜蜂高效的采蜜机制来处理函数优化问题，将人工蜂群分为3类：引领蜂、跟随蜂和侦查蜂，前两种蜜蜂用于蜜源的开采，而侦查蜂为避免蜜源种类的过少[3]而不断的寻找新的蜜源并替代原来不需要或者说已经使用过的蜜源。每个食物源代表一个待求问题的解而该食物源花蜜的多少代表这个解的优劣程度。待找最优蜜源的过程如下：随机产生2N个位置，通过简单的选择选取较优异的N个作为蜜源的位置，引领蜂找到这些蜜源并标记他们记，然后在这些标记蜜源附近按式（1）有哪些信誉好的足球投注网站新蜜源： 　　[Vij=xij+Rij（xij+xkj）] （1） 　　式中：[Vij]为新蜜源的位置，[xij]为已标记过蜜源的第[i]维位置，[xkj]为随机选择的不等于[i]的已标记过蜜源的第[j]维位置，[Rij]为[-1，1]间的随机数。根据前后蜜源的花蜜数量选择较优的蜜源替代初始标记的蜜源，并继续在标记蜜源附近用（1）式有哪些信誉好的足球投注网站新蜜源，并与初始标记蜜源比较，按照上述的方法反复循环迭代，直到达到算法的终止条件。 　　2 基于随机选择的人工蜂群算法 　　众所周知ABC的优化效果较好，但由于算法本身选择方式的局限性使其算法容易陷入局部最优，在迭代的进程中【4】每代的最差解都必定会参与到新解的产生之中从而直接影响了算法的收敛速度且易使算法发生早熟。为此，该文在最差蜜源的选择和对算法的早熟方面做了比较好的改进[5]。 　　2.1 最差蜜源的替换 　　在ABC迭代的过程中，由于每代的最差蜜源按（1）式进行交叉操作而产生新的蜜源，但是最差蜜源却几乎不可能对产生的最优蜜源做出贡献[6]，这就影响了算法的收敛速度。因此可用一个新的蜜源代替最差蜜源取消最差蜜源的破话作用。为此采取如下公式进行代替： 　　[Vij=xij*（c+d）+xkj（1-c-d）] （2） 　　式中：[Vij]为新蜜源的位置，[xij]为最差蜜源的第[j]维位置，[xkj]为随机选择的不等于[i]的最差蜜源的第[j]维位置，[c]和[d]为[0，1]间的随机数。在原来公式的基础上又增加了一个随机数【6】，使得蜜源在相互交换时的变化更大，从而大大的增加了蜜源变异的可能。 　　2.2 对算法早熟的解决 　　由于ABC采用轮盘赌的选择策略，就不可避免的会早熟和陷入局部最优，为解决这个问题，该文在随机选择的基础上又引入了变异的思想[7]。 　　1）变异机制的引入 　　虽然ABC在优化问题上的运用方面取得了较好的效果，但易陷入局部最优。为有效解决这个问题而引入变异【8】的思想。 ABC之所以会早熟就是因为在当前蜜源中找不到比此蜜源较优的蜜源，而陷入局部最优并过早收敛。为了能找到较优的蜜源可以引入若干新的蜜源以替代原来被有哪些信誉好的足球投注网站过的蜜源；即改变整个蜜源的结构。伪代码如下： 　　if （Fitness（n）—Fitness（n-1）==0 i++； end 　　if（ilimit） 把原蜜源中最差的10%蜜源替换掉同时 i清零End 　　适应度函数Fitness（n）【8】为所有蜜源的Fitness（n）的平均值。 　　2）变异时替换蜜源的量的大小和limit的值 　　文中算法产生变异时选择替换的蜜源数是整个种群的10% ，limit的值为50，具体还要由具体实验来决