基于混沌局部搜索算子的人工蜂群算法.doc

基于混沌局部搜索算子的人工蜂群算法摘要:在求解函数优化问题时，为了提升人工蜂群算法局部搜索能力，提出了一种新颖的混沌蜂群算法。新算法设计了一种混沌局部搜索算子，并将其嵌入蜂群算法框架中；该算子不仅能够实现在最优食物源周围局部搜索，还能够随着进化代数增加使搜索范围不断缩小。仿真实验结果表明,与人工蜂群算法相比，新算法在rosenbrock函数上，求解精度和收敛速度明显占优；此外新算法在多模函数griewank和rastrigin上，收敛速度明显占优。关键词:优化；混沌；人工蜂群算法；局部搜索artificial bee colony algorithm based on chaos local search operatorwang xiang1*, li zhi.yong2, xu guo.yi3, wang yan4(1. school of civil engineering, zhengzhou institute of aeronautical industry management, zhengzhou henan 450015, china;2. department of mathematics and physics, zhengzhou institute of aeronautical industry management, zhengzhou henan 450015, china;3. school of accounting, zhengzhou institute of aeronautical industry management, zhengzhou henan 450015, china;4. department of computer science and application, zhengzhou institute of aeronautical industry management, zhengzhou henan 450015, chinaabstract:in order to improve the ability of artificial bee colony algotithm at exploitation, a novel chaos-artificial bee colony algorithm is proposed for continuous function optimization problems. a new chaotic local search operator is embedded in the framework of the new algorithm. the new operator, whose search radius shrinks with the evolution generation, can do the local search around the best food source. the simulation results show that: compared with those of artificial bee colony algorithm, the solution quality and the convergence speed of the new algorithm are better for rosenbrock and the convergence speed of the new algorithm is better for griewank and rastrigin.in order to improve the ability of artificial bee colony (abc) algorithm at exploitation, a new chaos artificial bee colony (ch.abc) algorithm was proposed for continuous function optimization problems. a new chaotic local search operator was embedded in the framework of the new algorithm. the new operator, whose search radius shrinks with the evolution generation, can do the local search around the best food source. the simulation results show that: compared with those of abc algorithm, the solution quality and the convergence speed of the new algorithm are better for rosenbrock and the convergence speed of the new algorithm is better for griewank and rastrigin.key words:optimization; chaos; artificial bee colony (abc) algorithm; chaos artificial bee colony (ch.abc) algorithm; local search0 引言2005年提出的人工蜂群1-4 (artificial bee colony, abc)算法是一种新颖的群智能算法，它具有全局寻优能力强的特点，故被广泛应用于无约束优化问题5-8以及离散优化问题9。近来，文献5-8都指出，求解函数优化问题时，abc算法存在全局探索能力强、局部开采能力差的缺陷，尤其是针对rosenbrock函数求解能力较差。为了增强abc算法的局部搜索能力，本文利用混沌序列的随机性、遍历性和规律性，设计了一种混沌局部搜索算子，并将其嵌入蜂群算法框架中，从而提出了新颖的混沌蜂群（chaos artificial bee colony，ch.abc）算法。针对5个标准benchmark函数的仿真实验结果表明，新算法增强了abc算法的局部搜索能力，进而在一定程度上提升了求解质量。1 混沌蜂群算法本文设计了一种新颖的ch.abc算法，其基本思想是利用混沌序列的随机性、遍历性和规律性，设计了一种混沌搜索算子，实现了在当前最优解周围进行局部搜索的目的，进而增强了abc算法的开采能力。1.1 混沌蜂群算法的步骤新设计的ch.abc算法具体的实现步骤如下。步骤1 食物源初始化。随机生成初始食物源种群的相关信息。步骤2 雇佣蜂阶段。雇佣蜂在每个食物源周围进行搜索。步骤3 观察蜂选择食物源概率的计算。根据每个食物源的适应度，计算其被观察蜂选中的概率。步骤4 观察蜂阶段。根据每个食物源被选中的概率，观察蜂选择相应的食物源，进而在其周围进行搜索。步骤5 混沌局部搜索。首先，根据适应度函数选出最优食物源；其次，在最优食物源周围，利用混沌局部搜索算子进行局部搜索。步骤6 侦察蜂阶段。针对陷入局部最优的食物源，随机生成新位置替换原食物源位置。步骤7 判断是否满足给定的结束条件，若满足，则结束；否则，跳到步骤 2继续执行。需要特别指出的是，与abc算法相比，ch.abc算法只是增加了一个步骤5，目的是针对最优食物源进行进一步的勘探，从而加速算法收敛。1.2 混沌蜂群算法的详细解释以下是ch.abc算法每个步骤的详细解释，其中假定求解最小化问题；问题规模为d；种群大小为sn，食物源数目、雇佣蜂数目和观察蜂数目都为sn/2。1.2.1 食物源初始化新算法的食物源初始化包含初始化食物源种群和初始化食物源标识两项基本操作：由图1可知，5个函数的收敛曲线可以分成两类：第一类是rosenbrock、griewank和rastrigin的收敛曲线；第二类是sphere和ackley的收敛曲线。第一类中，ch.abc算法最终的最优解优于abc算法，而且其收敛速度较快，这表示混沌局部搜索算子对算法有明显改进。第二类中，两算法最优解相差较小。其进化过程分成两个阶段：初始阶段ch.abc算法收敛速度较快；进化后期，ch.abc算法与abc算法的收敛曲线基本重合。这种现象表示混沌局部搜索算子在初始阶段对算法有明显改进，在后期新算子基本不起作用。2.5 参数敏感性分析本部分利用了方差分析法（analysis of variance, anova）探讨算法的参数敏感性，其基本原理是比较不同参数设置条件下实验结果的均值是否存在显著性差异，其原假设是所有参数设置下实验结果均值相等，备择假设是至少存在一个参数设置其实验结果均值与其他不同。在anova分析中，显著性水平设置为0.05。此外，还利用了均值分析法（analysis of mean, anom）寻找算法的最优参数。与abc算法相比，ch.abc算法只是多了混沌序列长度k一个参数；此外，由于abc算法的其他参数敏感性在文献2中有过详细论述，故这里只讨论参数k的敏感性。为了不增加算法的时间复杂度，参数k设置成一个与种群大小sn线性相关的变量，具体设置k=0, sn/4, sn/2, sn, 2sn, 4sn=0, 10, 20, 40, 80, 1606个不同水平，同时保持其他参数与2.2节完全相同，此外每组实验独立运行30次。anom通过比较不同参数下实验结果的均值与所有实验结果的均值，最终确定算法参数的等级。表5展示了在不同k参数设置下anom分析的结果。由表5实验结果可知，k=0或80实验结果都存在不理想的情况，同时考虑到k越大算法的时间复杂度也越高，故k=10、20或40是比较合理的参数设置。2.6 讨论本部分根据5个测试函数实验结果的统计特性以及收敛曲线的特征，主要讨论两个特殊的现象。现象1 在图1中，针对所有函数，在进化过程的初始阶段，ch.abc算法的收敛速度都是高于abc算法的。这种现象是合理的，它主要基于以下三个原因：1）每次迭代的时候，ch.abc算法针对abc算法得出的当前最优解，利用混沌局部搜索算子继续寻优，故最优解肯定会有所改进；2）由进化算法的特点可知，初始阶段时，当前最优解可提升的空间较大，故混沌局部搜索算子对于算法的改进是明显的；3）由式（8）和（9）可知，混沌局部搜索算子初始阶段搜索范围较大，后期搜索范围较小，故初始阶段改进是明显的。现象2 针对griewank和rastrigin函数，在图1中ch.abc算法的收敛速度快于abc算法，且其最终结果优于abc算法；与此同时，在表4中，ch.abc算法的均值和标准差也都明显优于abc算法；然而，在表4中，两算法实验结果的t检验却不显著，即两算法实验结果在统计意义上不存在显著性差异。这个现象可以通过两算法30次实验最优解的分布的箱型图进行解释。由图2可知，ch.abc算法的30次实验的最优解比较集中；与之相比，abc算法大部分解的分布情况与ch.abc算法相同，同时也存在一些距离中位数较远的奇异点。例如griewank函数28次实验结果较为集中，同时也存在两个局部最优解，分别是0.099和0.0075，这两个局部最优解使得abc算法的均值和标准差都明显落后于ch.abc算法；与此同时，由于剩下28次实验结果的分布情况与ch.abc算法非常接近，故两算法实验结果的t检验并不显著。这说明，引入混沌局部搜索算子使得ch.abc算法不至于过早地陷入局部极值点，从而保证了求解质量。3 结语本文设计了一种新颖的混沌局部搜索算子，并将其用于改进abc算法，进而提出了ch.abc算法。针对5个标准benchmark函数的仿真实验证明了以下结论：1）在3个函数上，ch.abc算法求解质量有了明显提升；2）在进化初始阶段，无论是收敛速度还是求解质量，ch.abc算法都明显优于abc算法；3）ch.abc算法可以有效避免过早陷入局部极值现象的发生。参考文献:1karaboga d, basturk b. a powerful and efficient algorithm for numerical function optimization: artificial bee colony (abc) algorithmj. journal of global optimization, 2007, 39(3): 459-471.2karaboga d, basturk b. on the performan