改进的人工蜂群算法在多目标参数优化中的应用

改进的人工蜂群算法在多目标参数优化中的应用
王耀光，王振林2，李迅波2
摘要：本文在Pareto非支配集的基础上提出改进蜂群适应度算法操作，对蜂群算法产生的每一个个体进行局部搜索。为了提高算法的搜索率，采用精英选择加快多个目标的并行搜索。实验结果表明该方法与蜂群算法相比能快速地收敛于Pareto最优解。
关键词:多目标优化，蜂群算法，Pareto最优解
1引言
多目标优化是实际中广泛存在的NP求解难问题。通常问题的最优解不是单个解，而是多个解，并且各个解之间的结果是不可比较的。近年来出现了许多优秀的多目标有优化算法，比如遗传算法、鱼群算法、粒子群算法以及其改进的算法[1-5]。但是这些算法还是存在收敛慢、容易陷入局部最优解等问题，有待进一步改进。
为了优化多变量、多模态数据函数，Karaboga在2005年首次提出采用人工蜂群(ABC)算法来描述该问题[6]。该算法是模拟蜜蜂群觅食的智能算法，根据各自分工进行不同的活动，实现蜜蜂群信息的交流个体共享，从而找到问题的最优解。函数优化结果表明该算法比遗传算法、粒子群算法、微分进化算法具有更好的优化性能。
2 多目标人工蜂群算法
2.1多目标优化问题

2.2 个体适应度
本文采用双倍排序和自适应密度法，对个体的适应度赋值，首先根据Pareto的支配关系，对群体中的每一个个体排序，再根据周围的拥挤情况计算适应度密度值，最后综合确定适应度。其方法如下：

2．3基于Pareto的人工蜂群算法
在ABC算法中，人工蜂群由采蜜蜂、观察蜂和侦察蜂三部分组成。蜜源的位置代表优化问题的可能解，蜜源的花蜜量代表相应解的质量或适应度。采蜜蜂的数量和解的数量相等。首先ABC算法随机产生个初始解（SN为采蜜蜂数量）。每个解是一个维的向量，是优化参数的个数。经过初始化后，蜂群的位置（解）随着采蜜蜂、观察蜂和侦察蜂搜索开始循环。采蜜蜂根据记忆中的局部信息调整其位置并检查新蜜源的花蜜量。如果新位置的花蜜量比原来的多，则蜜蜂记住新的位置忘记旧的位置，否则保留旧的位置。在所有采蜜蜂完成搜索过程后，它们将在舞蹈区与观察蜂分享蜜源的花蜜信息和位置信息。观察蜂据此按与花蜜量相关的概率选择一个蜜源位置,像采蜜蜂那样根据记忆中的位置做一定的调整,并检查新候选位置的花蜜量。如果新位置的花蜜量优于旧位置的花蜜量则忘掉旧的位置记住新位置。
主要算法步骤如下：
1、初始化种群的数量；
2、循环搜索；
3、将采蜜蜂放置到蜜源位置；
4、根据观察蜂的记忆将其放置到蜜源位置；
5、放出侦察蜂到搜索区域寻找新的蜜源；
6、记住搜索过程中最好的蜜源位置；
7、循环搜索直到满足要求。
本文利用Pareto最优概念，将优于某个体的个体适应度值作为该个体的适应度值，一个观察蜂选择蜜源的概率取决于蜜源的概率值，其计算如下：

2.4 精英选择
精英选择的思想源于遗传算法的精英策略。精英策略就是在算法的迭代过程中，从上一代保留优秀的潜在解至下一代的过程，简单地从上一代中直接拷贝相应的解至下一代是常用的方法。从遗传算法的整个选择策略来看，精英选择是群体收敛到优化问题最优解的一种基本保障。如果下一代群体的最佳个体适应值小于当前群体最佳个体的适应值，则将当前群体最佳个体或者适应值大于下一代最佳个体适应值的多个个体直接复制到下一代，随机替代或替代最差的下一代群体中的相应数量的个体。为了提高多目标解的质量和算法的收敛速度，本文提出基于精英选择的蜂群算法求解多目标优化问题，其方法如下：
每个单目标问题所生成的个体集合称为子种群，所有子种群的结合称为多目标种群，各个但目标的子种群规模是相同的，另外建立一个精英种群来保存Pareto最优解。在每生成新一代多目标种群后都将根据下列定义对精英种群中的个体进行更新，保证精英种群中的解都是目前意义上的Pareto最优解。

源位置，利用精英选择思想评价该位置是否优于观察蜂所选位置，是则替换所选位置；
（7）记住搜索过程中的最优蜜源位置（解）；
（8）判断是否满足终止条件，否则转向步骤（2），否则停止计算。

3 实验验证
为了验证本文提出的方法的有效性以及ABC算法改进前后性能的比较，采用参考文献[8]的测试函数。

在改进前后的ABC算法中，最大循环次数为2000。为了统计算法收敛的平均误差和均值，每个测试函数均做30次实验。每次循环运算的时候观察蜂和采蜜蜂均为50%的种群数量。表1~3为不同种群数量的蜂群算法改进前后对比结果

从表中可以看出改进前后算法的收敛速度得到了很大的提高，在种群数量较少的情况下本文的方法没有多大的优势，但随着种群数量的增加本文的算法越趋近最优解。
4 结束语
本文提出了一种改进蜂群适应度算法，该算法将精英选择方法嵌入到迭代过程中，保证精英种群中的解都是目前意义上的Pareto最优解。文章最后通过3种基本测试函数加以验证，结果表明本文的算法在种群数较大的情况下明显优于改进前人工蜂群算法。
参考文献
[1] Michalewicz Z, Schoenauer M. Evolutionary algorithms for constrained paprameter optimization problems[J] .Evolutionary Compution, 1996, 4(1):1-32 .
[2] FARZI S. Efficient job scheduling in grid computing with modified artificial fish swarm algorithm [J]. International Journal of Computer Theory and Engineering, 2009, 1(1):13-18.
[3] 宋松柏,蔡焕杰,康艳. 约束优化问题的遗传算法求解[J]. 西北农林科技大学学报(自然科学版), 2005,(01):150-154.
[4] 余廷芳,彭春华. 遗传粒子群混合算法在电厂机组负荷组合优化中的应用[J]. 电力自动化设备, 2010,(10) :22-26
[5] 徐刚,杨玉群,黄先玖. 一种非线性权重的自适应粒子群优化算法[J]. 计算机工程与应用, 2010,(35):49-51
[6] Karaboga D．A idea based on bee swarm for numerical optimization [R]．Technical report-TR06，Erciyes University， Engineering Faculty，Computer Engineering Department，2005.
[7] 李纬, 张兴华. 一种改进的基于pareto解的多目标粒子群算法[J].计算机仿真, 2010,(5):96-99.
[8] Dorgo M. The ants system: optimization by a colony of cooperating agents [J]. IEEE Transaction on System. Man and Cybernetics Part B，1996，26(l):29.