二稿混沌蜂群算法

二稿混沌蜂群算法混沌蜂群算法摘要:人工蜂群算法是一种新的模拟蜜蜂采蜜行为的元启发式算法.本文提出一种新的ABC算法，利用混沌映射，提高算法的收敛速度，并防止ABC陷入局部最优.ABC算法需要使用的随机数，通过随机数发生器产生.该算法提出了七个新混沌映射，在基准函数中分析了不同混沌映射的性能,提高了解的质量.实验表明，所提出的方法能够有效提高解的质量，既能防止陷入局部最优，又能提高全局搜索能力.关键字:人工蜂群算法;全局数值优化;混沌;ChaoticbeecolonyalgorithmsAbstract:Artificialbeescolonyalgorithmisakindofnewsimulationbehaviorofmetaheuristicalgorithm.NewABCalgorithmisproposedinthispaper,usingthechaosmapping,improvestherateofconvergenceofthealgorithm,andpreventtheABCintoalocaloptimum.ABCalgorithmneedstousearandomnumber,generatedbyrandomnumbergenerator.Thealgorithmputsforwardsevennewchaosmappingofchaoticmappinginbenchmarkfunctionanalysisofdifferentperformance,improvesthequalityofknowledge.Experimentalresultsshowthattheproposedmethodcanimprovethequalityofthesolution,whichcanpreventfallsintolocaloptimum,andcanimprovetheglobalsearchability.Keywords:Beecolonyalgorithm;Chaos;Globalnumericaloptimization引言优化问题可以用传统算法建立模型来处理，需要几个假设，但这些假设在许多情况下不容易验证.这些参数的假设（舍入的变量、约束软化等）肯定会影响解的质量.如果在优化模型中需要建立整型或离散的决定变量，那么显然是不行的，也就是说，传统优化算法不灵活，不能更好的解决优化问题.此外，首先传统的求解策略通常取决于目标函数和约束函数的类型（线性，在许多文献中，混沌映射都具有确定性、遍历性和随机性.近年来，用混沌序列代替伪随机序列并应用于相关程序中，在许多算法中已经表现出一些有效的﹑好的结果，它们也可以与一些启发式优化算法一起使用来表示优化变量.由于混沌序列的不可预测性，理论上讲，混沌序列的选择是合理的.在本文中，用混沌系统生成的不同序列代替ABC参数的随机数，这是一个随机选择的过程.为此，我们已提出用不同的混沌映射代替伪随机序列的方法.通过这种方式，它可以加强全局优化，防止陷入局部最优.但是，一般情况下，如果他们不遵循均匀分布，很难去估计哪些通过应用统计测试的混数发生器更好.仿真结果表明，应用确定性混沌信号代替随机序列是提高ABC性能的一种策略.本文的其余结构，如下所示：第1节中回顾了ABC的相关内容；第2章介绍了所提出的方法、混沌蜂群算法，简称CBCAs；第3节介绍了用于提出的方法进行比较的测试函数；第4节，测试所提出的方法；第5节通过基准问题和模拟结果进行对比，得出结论.1.人工蜂群算法在标准ABC算法中人工蜂群包括引领蜂,守望蜂和侦查蜂三个组成部分。每个引领蜂有一个确定的食物源（每个食物源的位置代表优化问题的一个可行解），引领蜂的个数与食物源的个数相等，食物源的花蜜量是由相应解的适应度值来决定的。初始化之后，引领蜂根据记忆中的局部信息产生一个新的位置并检查新位置的花蜜量。若新位置的花蜜量比原来的多，则该蜜蜂更新记忆并记住新的位置。所有的引领蜂搜索完之后，将花蜜源信息通过在舞蹈区跳舞的方式传递给守望蜂。守望蜂根据引领蜂所找的食物源的花蜜量按概率选择一只引领蜂并跟随它，在这只引领蜂所在的食物源附近再重新搜索找到新的位置，并检查新候选位置的花蜜量。若新位置优于原来的位置，则更新记忆并记住新的位置。算法的伪代码见图2.在初始化步骤后搜索的周期包括三个步骤：将引领蜂引到食物源并计算其花蜜量；将守望蜂引到食物来源并计算出花蜜量；确定侦查蜂，并把它们引到可能的食物源.一个食物源代表着优化问题的一个可行解.食物源的花蜜量对应着可行解的质量.每个引领蜂再在它当前的食物源附近区域内确定一个新的食物源，并估算它的花蜜量.如果新的花蜜量较高，蜜蜂更新记忆并记住新的食物源.守望蜂根据引领蜂所找的食物源的花蜜量，按概率选择其中一只引领蜂，并跟随它.蜂群的每个侦查蜂都被视为种群的探险者，不能发表任何指导意见，只是负责寻找食物.他们负责寻找任何种类的食物源.也是由于它们的这种行为，侦查蜂一般是只能找到低成本和低平均质量的食品源.偶尔，侦查蜂也可以意外发现丰富的食物源.在人工蜂群中，侦查蜂能快速发现其中的可行解.在ABC中，引领蜂是选定归类为侦察蜂的来源之一.选择是由参数limit控制.如果预定次数的实验没有提高食物源解的质量，那食物源就会被发现它的引领蜂遗弃，而这个食物源的引领蜂会成为一名侦查蜂.释放食物源的试验次数等于ABC重要控制参数的limit值.在强大的搜索过程中勘探和开发过程是平衡的.在ABC算法种，当守望蜂和引领蜂进行搜索空间的开发过程时，需要由侦查蜂来控制探索过程.这三个步骤不断重复，直到满足终止条件为止.图3中所给的是ABC算法的流程图.2.混沌蜂群算法在复杂模拟现象中，取样、数值分析、决策，尤其是启发式优化算法需要长时间和良好均匀性的随机序列.此外，算法非常依赖它的初始条件和参数.混沌的本质是随机的、不可预测的，它显然也拥有元素的规律.在数学上，混沌是一个简单的确定性的随机动力系统，混沌系统可以看作是随机性的来源.一种混沌映射是离散动力系统;;k=0,1,2,..在混沌状态下运行.混沌序列{xk：k=0，1，2，...｝可以作为随机编号来生成扩频序列.混沌序列被证明可以简单快速的生成和存储，但是对于长序列的存储没有帮助.长序列只是需要几个函数（混沌映射）和几个参数（初始条件）.此外，通过更改其初始条件可以简单生成很多不同的序列，并且这些序列都具有确定性和可再生性.最近，通过了混沌序列，而不是随机序列，并且混沌序列在许多应用程序中已经显现出一些有效的，好的结果如信息安全、非线性电路、DNA计算和图像处理.由于混沌序列的不可预测性，理论上讲，混沌序列的选择是合理的.——初始化问题参数—初始化算法参数—构建初始引领蜂群解—评估每只蜜蜂的适应值—i=0—Repeat—N=0—RepeatK为在i附近的一个解Y为[-1,1]范围内的一个随机数字—产生新的解(食物源位置)Ui,j表示在Xi,j附近的引领蜂，使用下面的公式—在X和UI中应用邻域选择过程—一只引领蜂选取食物源依赖于一个相关于食物源的概率值Pi，由下面表达式计算:—守望蜂根据引领蜂所找的食物源的花蜜量按概率Pi对引领蜂Xi来进行评估For所有守望蜂Do为引领蜂在Xi和Ui中适用贪婪的选择过程Iffit(BestOnlooker)<fit(Employed)用守望蜂解代替引领蜂解EndIfEndDoIffit(BestFeasibleOnlooker)<fit(Best)找到最佳可行的守望蜂，替换最佳解决方案EndIfn=n+1Until(n=引领蜂数量)如果存在，确定被遗弃的解（食物源），并用一个新的随机产生的解Xi取代，此处的引领蜂成为侦查蜂，用下面公式—侦查蜂只有一个.如果侦查蜂的解比引领蜂的解更好，引领蜂的解将被替换为侦查蜂的解.否则其他引领蜂的解就会没有任何变化地被转到下一个周期—Until(i=最大迭代数)图2.ABC扫描的伪代码确定到邻居食品的位置放置的旁观者蜂确定到邻居食品的位置放置的旁观者蜂为旁观蜂选择一个食物来源计算花蜜量初始化算法和问题参数找到废弃食物源记忆最佳食物源位置是计算花蜜量是否所有守望蜂被放于食物源处确定将引领蜂放置在新食物源位置找到用尽食物源的新位置是否满足终止条件最终的食物位置否是确定将守望蜂放置在相邻食物源位置不为守望蜂选择一个食物源图3.ABC算法的流程图在新迭代的初始化步骤中，ABC随机初始化和限制参数可以调整，但不能改变，这会影响算法性能的收敛速度.本文在ABC中提供了新的方法，引入具有遍历性、非规范性和随机属性的混沌映射，来提高全局收敛性，避免陷入局部最优问题.在ABC中使用混沌序列，可以更容易摆脱局部最优值，比通过原来的ABC的方法更有效.混沌映射所要选择的(0，1)的混沌数字，已列于表1.新混沌ABC算法可以分类描述如下：2.1.混沌ABC1(CABC1)原始人工蜂群是由所选定的混沌映射循环迭代直到达到蜂群大小，如图4所示.N是问题维度；i是种群成员数目；j是的维度；Xi,j是第i个成员的第j个维度表1所运用混沌映射的定义名称定义物流映射圈映射高斯映射Henon映射正弦的迭代器窦映射帐篷映射,，2.2.混沌ABC2(CABC2)在这种算法，如果代表食物源的一个解进行limit/2测试后并没有得到改进，那这个食物源会被它的引领蜂遗弃，且此引领蜂的侦查蜂开始limit/2混沌迭代搜索.是第个成员的第j个维度，是对第个成员的第个维度通过乱数发生器生成的混沌数.图5描述了蜜蜂混沌搜索的伪代码.CI为CI为混沌迭代的最大数目Repeat随机初始化第一个混沌变量Repeat根据选定的映射生成混沌变量其中，CS为种群规模大小图4，由CABC1伪代码改变的原始ABC初始化用于搜索的第一个混沌变量初始化用于搜索的第一个混沌变量Repeat生成循环访问选定的映射的混沌变量映射回周围半径r原始值的范围评价新的适应值如果找到更好的方法，用更好的方法代替有关的维度，转换到另一种维度图5，蜜蜂混沌搜索的伪代码2.3.混沌ABC3(CABC3)CABC1和CABC2相结合产生，也就是说，为防止没有获得改进，由所选的混沌映射、混沌搜索迭代产生混沌映射ABC3.3.测试问题以数学函数为基础的基准函数可用于作为衡量和测试优化方法性能的目标函数.这些基准函数的本质、复杂性和其他属性可以很容易地从它们的定义中获得，大多数基准函数高难度水平的问题也可通过设置参数来调节.文献中基准问题可用的一组标准中，有三个重要的函数，其中之一是单峰的，另外两个是多峰的，它们用来测试所提出方法的效果.表2显示了所选定的基准函数在实验中所使用的的主要属性.表2性能测试问题，lb指示下限，ub指示上限，选择指示最佳点函数编码函数名定义属性1Rosenbrock单峰2Griewangk多峰3Rastriqin多峰4.实验仿真与结果选定的三个基准问题通过模拟的ABC、CABC1和CABC2的算法解决.两个标准用于终止算法的仿真：达到设置为常数的最大迭代次数，第二个标准是达到最小误差.所有ABC被初始化都会做出公正的评价包括全局最优.为了配合他们的随机属性，该算法运行了100次.在这个实验中，最大迭代数被设置为500，目标不是找到全局的最优值，而是找出算法的潜力最优值.公式(2)定义了算法的成功率，已被用于比较不同ABC算法.（2）是测试的次数，是在允许的最大迭代次数和条件中找到解的测试次数.是所有测试的数目.是停止算法的终止条件，直到超出所限制的终止条件，算法结束.蜂群算法的种群规模选定为20.ABC的限制参数定为40.表3描述了ABC算法测试功能的成功率.Rosenbrock函数使用不同的混沌映射后，CABC算法的成功率如表4所示.CABC算法某种程度上表现出比ABC算法的测试函数更好的性能.尤其是，所有由算法CABC2和CABC3获得的结果都比算法ABC的要好些.表3ABC算法的测试功能的成功率1.e-5013751.e-601360表4使用不同的混沌映射的算法的成功率物流映射1.e-50661.e-6044圈映射1.e-51541.e-6144高斯映射1.e-51671.e-6156Henon映射1.e-52451.e-6133正弦的迭代器1.e-50441.e-6023窦映射1.e-50651.e-6055帐篷映射1.e-50661.e-6045表5使用不同的混沌映射的算法的成功率物流映射1.e-51626251.e-6102322圈映射1.e-51418171.e-6141617高斯映射1.e-51826231.e-682321Henon映射1.e-51828281.e-6132126正弦的迭代器1.e-51925231.e-6141820窦映射1.e-51628271.e-681919帐篷映射1.e-51723231.e-6131516表6使用不同的混沌映射的算法的成功率物流映射1.e-56991891.e-6598569圈映射1.e-56890881.e-6618481高斯映射1.e-57695911.e-6588482Henon映射1.e-56589891.e-6468286正弦的迭代器1.e-57288891.e-6707986窦映射1.e-52692921.e-6258186帐篷映射1.e-57288871.e-6567979为Griewangk和Rastrigin函数使用不同的混沌映射的CABC算法的成功率分别如表5和表6所示.类似于测试函数Rosenbrock所获得的结果，CABC算法在某种程度上表现出具有比ABC算法更好的性能.特别是，算法CABC2和CABC3的所有结果都比ABC算法的好.5.结论本文通过嵌入不同的混沌映射来适应ABC算法的参数.提出了三种新的混沌ABC算法，在基准函数中分析了七个混沌映射.实验结果表明这些方法提高了解的质量，这也在一定程度上避免了陷入局部最优，从而改进了全局搜索能力.对ABC算法的性能做了很大改善。文献[1]李海生.一类基于蜜蜂采集模型的智能算法[J].计算机与现代化,2010,1:7-11.[2]胡中华;赵敏;基于人工蜂群算法的TSP仿真[J];北京理工大学学报;2009年11期[3]张超群;郑建国;王翔;;蜂群算法研究综述[J];计算机应用研究;2011年09期[4]王辉;改进的蜂群算法[J];计算机工程与设计;2011年11期[5]毕晓君，王艳娇.改进人工蜂群算法[J];哈尔滨工程大学学报;2012，33（1）：117-123[6]龚纯,王正林.《精通MATLAB最优化计算》[M].北京:电子工业出版社,2009.[7]KennedyJ,EberhartR.ParticleSwarmOptimization[C]//ProceedingsofIEEEInternationalConferenceonNeuralNetworks,Perth,Australia,1995:1942-1948.[8]ZhuGuopu,SamKwo