稿混沌蜂群算法

1、混沌蜂群算法摘要 :人工蜂群算法是一种新的模拟蜜蜂采蜜行为的元启发式算法 .本文提出一种新的 ABC 算法，利用混沌映射，提高算法的收敛速度，并防止 ABC 陷入局部最优 .ABC 算法需要使用 的随机数，通过随机数发生器产生 .该算法提出了七个新混沌映射，在基准函数中分析了不 同混沌映射的性能 , 提高了解的质量 .实验表明，所提出的方法能够有效提高解的质量，既能 防止陷入局部最优，又能提高全局搜索能力 .关键字 : 人工蜂群算法 ;全局数值优化 ; 混沌 ;Chaotic bee colony algorithmsAbstract : Artificial bees colony algo

2、rithm is a kind of new simulation behavior of meta heuristic algorithm. New ABC algorithm is proposed in this paper, using the chaos mapping, improves the rate of convergence of the algorithm, and prevent the ABC into a local optimum. ABC algorithm needs to use a random number, generated by random n

3、umber generator. The algorithm puts forward seven new chaos mapping of chaotic mapping in benchmark function analysis of different performance, improves the quality of knowledge. Experimental results show that the proposed method can improve the quality of the solution, which can prevent falls into

4、local optimum, and can improve the global search ability.Keywords: Bee colony algorithm;Chaos;Global numerical optimization引言优化问题可以用传统算法建立模型来处理， 需要几个假设， 但这些假设在许多情况下不 容易验证 . 这些参数的假设（舍入的变量、约束软化等）肯定会影响解的质量 . 如果在优化模 型中需要建立整型或离散的决定变量， 那么显然是不行的， 也就是说，传统优化算法不灵活， 不能更好的解决优化问题 .此外，首先传统的求解策略通常取决于目标函数和约束函数的类型（线

5、性，非线性等） 以及建模问题中使用变量的类型（整形，实型等） . 他们的效率也依赖于解空间的大小、用 于建模的变量、约束的数量和解空间的结构（凸，凹等） . 也就是说，他们不提供通用的解决方案。然而，大部分的优化问题，需要在它的规划策略中制定变量、目标函数和约束函数 的类型 .其次，原始优化算法在解决大规模和高维非线性的问题上，效率很低，迫使研究者 寻找更灵活、 适应性更强、问题和模型独立的通用启发式算法， 这种通用的启发式算法高效、 灵活，它们可以视问题的特定要求，来进行调整修改 .图 1所示的启发式算法的分类 .图 1 启发式算法近年来，基于生物学的群体智能启发式算法已成为许多学者的研究兴

6、趣之一 . 粒子群优 化算法、蚁群优化算法和蜂群算法可以视为群体智能的几个分支领域 . 最近提出的人工蜂群 智能算法（ ABC）受到了蜜蜂智能行为的启发，同时被证明是全局数值优化问题的更好的解 决办法.在许多文献中，混沌映射都具有确定性、遍历性和随机性 . 近年来，用混沌序列代替 伪随机序列并应用于相关程序中， 在许多算法中已经表现出一些有效的好的结果， 它们也 可以与一些启发式优化算法一起使用来表示优化变量 . 由于混沌序列的不可预测性，理论上 讲，混沌序列的选择是合理的 .在本文中，用混沌系统生成的不同序列代替 ABC参数的随机数， 这是一个随机选择的过 程. 为此，我们已提出用不同的混沌

7、映射代替伪随机序列的方法 .通过这种方式， 它可以加强 全局优化，防止陷入局部最优 . 但是，一般情况下，如果他们不遵循均匀分布，很难去估计 哪些通过应用统计测试的混数发生器更好 . 仿真结果表明，应用确定性混沌信号代替随机序 列是提高 ABC性能的一种策略 .本文的其余结构，如下所示：第 1节中回顾了 ABC的相关内容；第 2章介绍了所提出的方法、 混沌蜂群算法，简称 CBCA；s 第 3节介绍了用于提出的方法进行比较的测试函数；第 4节，测 试所提出的方法；第 5节通过基准问题和模拟结果进行对比，得出结论 .1. 人工蜂群算法在标准 ABC算法中人工蜂群包括引领蜂 , 守望蜂和侦查蜂三个组

8、成部分。每个引领蜂有 一个确定的食物源（每个食物源的位置代表优化问题的一个可行解） ，引领蜂的个数与食物 源的个数相等，食物源的花蜜量是由相应解的适应度值来决定的。初始化之后，引领蜂根据 记忆中的局部信息产生一个新的位置并检查新位置的花蜜量。若新位置的花蜜量比原来的 多，则该蜜蜂更新记忆并记住新的位置。所有的引领蜂搜索完之后，将花蜜源信息通过在舞 蹈区跳舞的方式传递给守望蜂。 守望蜂根据引领蜂所找的食物源的花蜜量按概率选择一只引 领蜂并跟随它， 在这只引领蜂所在的食物源附近再重新搜索找到新的位置， 并检查新候选位 置的花蜜量。若新位置优于原来的位置，则更新记忆并记住新的位置。算法的伪代码见图

9、2.在初始化步骤后搜索的周期包括三个步骤： 将引领蜂引到食物源并计算其花蜜量； 将守 望蜂引到食物来源并计算出花蜜量；确定侦查蜂，并把它们引到可能的食物源 . 一个食物源 代表着优化问题的一个可行解 . 食物源的花蜜量对应着可行解的质量 . 每个引领蜂再在它当 前的食物源附近区域内确定一个新的食物源，并估算它的花蜜量. 如果新的花蜜量较高，蜜蜂更新记忆并记住新的食物源 . 守望蜂根据引领蜂所找的食物源的花蜜量，按概率选择其中 一只引领蜂，并跟随它 .蜂群的每个侦查蜂都被视为种群的探险者，不能发表任何指导意见，只是负责寻找食物 . 他们负责寻找任何种类的食物源 . 也是由于它们的这种行为，侦查蜂

10、一般是只能找到低成本 和低平均质量的食品源 .偶尔，侦查蜂也可以意外发现丰富的食物源 . 在人工蜂群中， 侦查蜂 能快速发现其中的可行解 . 在 ABC中，引领蜂是选定归类为侦察蜂的来源之一 . 选择是由参数 limit 控制. 如果预定次数的实验没有提高食物源解的质量，那食物源就会被发现它的引领 蜂遗弃，而这个食物源的引领蜂会成为一名侦查蜂 . 释放食物源的试验次数等于 ABC 重要控 制参数的 limit 值. 在强大的搜索过程中勘探和开发过程是平衡的 . 在 ABC算法种，当守望蜂 和引领蜂进行搜索空间的开发过程时， 需要由侦查蜂来控制探索过程 . 这三个步骤不断重复， 直到满足终止条件

11、为止 .图 3中所给的是 ABC算法的流程图 .2. 混沌蜂群算法在复杂模拟现象中，取样、数值分析、决策，尤其是启发式优化算法需要长时间和良好 均匀性的随机序列 .此外，算法非常依赖它的初始条件和参数 . 混沌的本质是随机的、 不可预 测的，它显然也拥有元素的规律 . 在数学上，混沌是一个简单的确定性的随机动力系统，混 沌系统可以看作是随机性的来源 .一种混沌映射是离散动力系统Xk 1 f（Xk）; 0 Xk 1; k = 0, 1, 2,. . 在混沌状态下运行 . 混沌序列 x k： k =0 ，1，2，. . . 可以作为随机编号来生成扩频序列 . 混沌序列被证明可以简单快速的生成和存储

12、，但是对于长序列的存储没有帮助 . 长序列只是 需要几个函数（混沌映射）和几个参数（初始条件） . 此外，通过更改其初始条件可以简单 生成很多不同的序列，并且这些序列都具有确定性和可再生性 .最近，通过了混沌序列，而不是随机序列，并且混沌序列在许多应用程序中已经显 现出一些有效的，好的结果如信息安全、非线性电路、 DNA计算和图像处理 . 由于混沌序列 的不可预测性，理论上讲，混沌序列的选择是合理的 .初始化问题参数图 2.ABC 扫描的伪代码初始化算法参数构建初始引领蜂群解评估每只蜜蜂的适应值i=0 RepeatN=0RepeatK 为 在 i 附近的一个解Y 为-1,1 范围内的一个随机数

13、字产生新的解 （ 食物源位置 ）Ui,j 表示在 Xi,j 附近的引领蜂， 使用下面的公式初始 化算 法和在新迭代的初始化步骤中， ABC随机初始化和限制参数可以调整，但不能改变，这会影 响算法性能的收敛速度 . 本文在 ABC中提供了新的方法，引入具有遍历性、非规范性和随机 属性的混沌映射，来提高全局收敛性，避免陷入局部最优问题.在 ABC中使用混沌序列，可以更容易摆脱局部最优值，比通过原来的 ABC的方法更有效 . 混沌映射所要选择的 （0，1）的 混沌数字，已列于表 1. 新混沌 ABC算法可以分类描述如下：2.1. 混沌 ABC1(CABC1) 原始人工蜂群是由所选定的混沌映射循环迭代

14、直到达到蜂群大小，如图4所示.N 是问题维度； i是种群成员数目； j是的维度； Xi,j 是第i 个成员的第 j 个维度表 1 所运用混沌映射的定义定义名称物流映射Xn 14Xn(1 X n圈映射Xn1X n 1.2高斯映射X n 10,Henon 映射X n 11 1.4Xn2正弦的迭代器X n 1sin( X n )窦映射Xn12.3(Xn )2sin(帐篷映射Xn1Xn /0.7)(0.5/2)sin(2X n ) mod(1)Xn)0.3Xn1Xn0,X n 0.710/3Xn(1 Xn) ，otherwise2.2. 混沌 ABC2(CABC2)在这种算法，如果代表食物源的一个解进

15、行 limit/2 测试后并没有得到改进，那这个食物源会被它的引领蜂遗弃，且此引领蜂的侦查蜂开始 limit/2 混沌迭代搜索 . Xi,j是第 i 个成 员的第j个维度， Ci,j是对第 i个成员的第 j 个维度通过乱数发生器生成的混沌数 .图5描述了蜜蜂混沌搜索的伪代码 .CI 为 混沌迭代的最大数目图4，由 CABC伪1 代码改变的原始 ABCRepeat 初始化用一第蜜个一蜂混个沌混变沌量变2.3R.e混pRe沌aetp A e B aCt 3(CABC3) 生成C 成混沌 沌搜索迭代产生混沌映射 ABC3.cmi, j 映射回周围半径iu,nj til (i CS)评价新 X i 的

16、适应值，也量 的伪代码就变是量说，c为m防止没有获得改进，由所选的混沌映射 量 cmi ,jr 原始值的范围其中， CS为种群规模大小3. 测试问题以数学函数为基础的基准函数可用于作为衡量和测试优化方法性能的目标函数. 这些基准函数的本质、 复杂性和其他属性可以很容易地从它们的定义中获得， 大多数基准函数高难 度水平的问题也可通过设置参数来调节 . 文献中基准问题可用的一组标准中，有三个重要的 函数，其中之一是单峰的，另外两个是多峰的，它们用来测试所提出方法的效果. 表2显示了所选定的基准函数在实验中所使用的的主要属性 .表 2 性能测试问题， lb 指示下限， ub 指示上限，选择指示最佳点

17、函数编码 函数名性1 Rosenbrock2 Griewangk3 Rastriqin4. 实验仿真与结果定义f1(x)N100(X i 1 Xi12 2 2i2)2 (1 Xi )2单峰f 2(x)N(Xi2 / 4000)i1N X i cos( ) i 1 i多峰f3(x)N10 N(X i2i110 cos(2 X i )多峰选定的三个基准问题通过模拟的 ABC、CABC1和 CABC2的算法解决 . 两个标准用于终止算 法的仿真：达到设置为常数的最大迭代次数，第二个标准是达到最小误差 .100NTsuccessfulNTall2)所有 ABC被初始化都会做出公正的评价包括全局最优 .

18、 为了配合他们的随机属性， 该算法 运行了 100 次. 在这个实验中，最大迭代数被设置为 500，目标不是找到全局的最优值，而 是找出算法的潜力最优值 . 公式 (2) 定义了算法的成功率，已被用于比较不同 ABC算法.NTsuccessful是测试的次数，是在允许的最大迭代次数和条件Qlevel 中找到解的测试次 数. NTall 是所有测试的数目 . Qlevel是停止算法的终止条件，直到超出 Qlevel所限制的终止条件，算法结束.蜂群算法的种群规模选定为 20.ABC的限制参数定为 40. 表3描述了 ABC算法测试功能的成功率.Rosenbrock 函数使用不同的混沌映射后， CA

19、BC算法的成功率如表 4所示.CABC算法某种程度上表现出比 ABC算法的测试函数更好的性能 .尤其是，所有由算法 CABC和2 CABC获3得的结果都比算法 ABC的要好些 .表 3 ABC 算法的测试功能的成功率1.e-5 013751.e-6 01360表 4Rosenbrock ( N2）使用不同的混沌映射的 CABC 算法的成功率物流映射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

20、.e-50661.e-6045表 5Griewangk (N10) 使用不同的混沌映射的 CABC 算法的成功率物流映射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-6 13 15 16表6 Rastrigin (N 10) 使用不同的混沌映射的 CABC算法的成功率物流映射918589691.e-

21、51.e-6圈映射69591.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 算法更好的性能 .特别是，算法 CABC和2

22、 CABC的3 所有结果都比 ABC算法的好 .5. 结论本文通过嵌入不同的混沌映射来适应 ABC算法的参数 . 提出了三种新的混沌 ABC算法，在 基准函数中分析了七个混沌映射 . 实验结果表明这些方法提高了解的质量，这也在一定程度 上避免了陷入局部最优，从而改进了全局搜索能力 . 对ABC算法的性能做了很大改善。文献1 李海生 . 一类基于蜜蜂采集模型的智能算法 J. 计算机与现代化 , 2010,1: 7-11.2 胡中华 ; 赵敏 ; 基于人工蜂群算法的 TSP仿真J; 北京理工大学学报 ;2009 年 11期3 张超群 ; 郑建国 ; 王翔; 蜂群算法研究综述 J; 计算机应用研究

23、;2011 年09期4 王辉; 改进的蜂群算法 J; 计算机工程与设计 ;2011年11期5 毕晓君，王艳娇. 改进人工蜂群算法 J; 哈尔滨工程大学学报 ;2012 ，33（1）： 117-1236 龚纯, 王正林.精通MATLAB最 优化计算M. 北京:电子工业出版社 ,2009.7 Kennedy J,Eberhart R.Particle Swarm OptimizationC/Proceedings of IEEE International Conference onNeural Networks,Perth, Australia,1995:1942- 1948.8 Zhu Guopu,SamK wong.Gbest-guided artificialbee colony algorithm fornumerical function optimizationJ.Applied Mathematics andComputation,2010,217:3166-3173.9 Karaboga D,Basturk B.Artificial bee colony (ABC)optimization algori