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

本文来自中国月期刊网（），请到月期刊网进行查询。改进的人工蜂群算法在多目标参数优化中的应用王耀光1，王振林2，李迅波2摘要：本文在Pareto非支配集的基础上提出改进蜂群适应度算法操作，对蜂群算法产生的每一个个体进行局部搜索。为了提高算法的搜索率，采用精英选择加快多个目标的并行搜索。实验结果表明该方法与蜂群算法相比能快速地收敛于Pareto最优解。关键词:多目标优化，蜂群算法，Pareto最优解1引言多目标优化是实际中广泛存在的NP求解难问题。通常问题的最优解不是单个解，而是多个解，并且各个解之间的结果是不可比较的。近年来出现了许多优秀的多目标有优化算法，比如遗传算法、鱼群算法、粒子群算法以及其改进的算法[1-5]。但是这些算法还是存在收敛慢、容易陷入局部最优解等问题，有待进一步改进。为了优化多变量、多模态数据函数，Karaboga在2005年首次提出采用人工蜂群(ABC)算法来描述该问题[6]。该算法是模拟蜜蜂群觅食的智能算法，根据各自分工进行不同的活动，实现蜜蜂群信息的交流个体共享，从而找到问题的最优解。函数优化结果表明该算法比遗传算法、粒子群算法、微分进化算法具有更好的优化性能。2多目标人工蜂群算法2.1多目标优化问题考虑如下多目标优化问题：12min()((),(),,())mfxfxfxfx，（1）s.t.[,].xab，其中，决策向量SNxR,即12(,,,)SNxxxx，目标向量()mfxR。多目标优化中，各个目标通常是相互制约的，一个目标得以优化，往往是牺牲其它目标的性能为代价，为了对多目标问题进行优化本文采用基于Pareto的人工蜂群算法进行求解。Pareto最优解集中的解是彼此不可比较的，解集中的解数量越多，分布越广泛，决策者的选择空间越大，越能对实际多目标问题进行合理求解。2.2个体适应度本文来自中国月期刊网（），请到月期刊网进行查询。本文采用双倍排序和自适应密度法，对个体的适应度赋值，首先根据Pareto的支配关系，对群体中的每一个个体排序，再根据周围的拥挤情况计算适应度密度值，最后综合确定适应度。其方法如下：1）计算群体Q中每个个体i的排序()Ri(){|,}RijjQjiiQ（2）其中，符号表示Pareto支配关系，即上式表示当前群体Q中支配个体i的个数。2）个体i的排序()Ri：,()()()jQijRiRiRjiQ（3）上式表明个体i的排序数()Ri等于个体i的伪排序数与支配个体i的所有个体的伪排序数之和。（3）根据种群的规模SN将目标空间划分成eeeknnn个网格，en表示每维目标空间的网格数，设kSN的整数部分为a，小数部分为r则010earnar（4）将每个个体所在的网格区域的个体数作为给个体的密度值。（4）个体适应度值：1exp(()*())ifitRii（5）式中，()Ri表示个体i的排序号，()i表示个体i的密度值。2．3基于Pareto的人工蜂群算法在ABC算法中，人工蜂群由采蜜蜂、观察蜂和侦察蜂三部分组成。蜜源的位置代表优化问题的可能解，蜜源的花蜜量代表相应解的质量或适应度。采蜜蜂的数量和解的数量相等。首先ABC算法随机产生SN个初始解（SN为采蜜蜂数量）。每个解(1,2)ixiSN是一个D维的向量，D是优化参数的个数。经过初始化后，蜂群的位置（解）随着采蜜蜂、观察蜂和侦察蜂搜索开始循环。采蜜蜂根据记忆中的局部信息调整其位置并检查新蜜源的花蜜量。如果新位置的花蜜量比原来的多，则蜜蜂记住新的位置忘记旧的位置，否则保留旧的位置。在所有采蜜蜂完成本文来自中国月期刊网（），请到月期刊网进行查询。搜索过程后，它们将在舞蹈区与观察蜂分享蜜源的花蜜信息和位置信息。观察蜂据此按与花蜜量相关的概率选择一个蜜源位置,像采蜜蜂那样根据记忆中的位置做一定的调整,并检查新候选位置的花蜜量。如果新位置的花蜜量优于旧位置的花蜜量则忘掉旧的位置记住新位置。主要算法步骤如下：1、初始化种群的数量；2、循环搜索；3、将采蜜蜂放置到蜜源位置；4、根据观察蜂的记忆将其放置到蜜源位置；5、放出侦察蜂到搜索区域寻找新的蜜源；6、记住搜索过程中最好的蜜源位置；7、循环搜索直到满足要求。本文利用Pareto最优概念，将优于某个体的个体适应度值作为该个体的适应度值，一个观察蜂选择蜜源的概率取决于蜜源的概率值ip，其计算如下：1iiSNnnfitpfit（6）其中，ifit是第个体i的适应值，SN是采蜜蜂数量（或蜜源数量）。为了从记忆中就得蜜源位置产生一个新的蜜源位置，ABC算法采用如下表达式：()ijijijijkjvxxx，（7）这里{1,2,)kSN,{1,2,,}jD是随机选择的下标，且ki；是在[-1,1]之间的随机数；它控制ijx领域内新的蜜源的产生并代表蜜蜂对两个可视范围内两个蜜源位置的比较，从（7）式中可以看出随着ijx与kjx之间的差距缩小，对位置ijx的扰动就越小，因此在解空间内随着最优解得逼近，步长将相应地减少。在人工蜂群算法中，如果一个蜜源位置经过限定次数的循环后仍然不能被改进，那么该蜜源处的采蜜蜂成为侦察蜂，该蜜源位置将被解空间内随机产生的一个位置所代替。设放弃的蜜源位置是ix，则侦察蜂发现新蜜源并替换ix的操作如下：minmaxmin[0,1]()jjjjixxrandxx，（8）式中，{1,2,,}jD。本文来自中国月期刊网（），请到月期刊网进行查询。2.4精英选择精英选择的思想源于遗传算法的精英策略。精英策略就是在算法的迭代过程中，从上一代保留优秀的潜在解至下一代的过程，简单地从上一代中直接拷贝相应的解至下一代是常用的方法。从遗传算法的整个选择策略来看，精英选择是群体收敛到优化问题最优解的一种基本保障。如果下一代群体的最佳个体适应值小于当前群体最佳个体的适应值，则将当前群体最佳个体或者适应值大于下一代最佳个体适应值的多个个体直接复制到下一代，随机替代或替代最差的下一代群体中的相应数量的个体。为了提高多目标解的质量和算法的收敛速度，本文提出基于精英选择的蜂群算法求解多目标优化问题，其方法如下：每个单目标问题所生成的个体集合称为子种群，所有子种群的结合称为多目标种群，各个但目标的子种群规模是相同的，另外建立一个精英种群来保存Pareto最优解。在每生成新一代多目标种群后都将根据下列定义对精英种群中的个体进行更新，保证精英种群中的解都是目前意义上的Pareto最优解。定义1称[,]xab是多目标优化问题的Pareto最优解，如果不存在[,]yab，使得()()1,2,iifyfxim，，且至少有一个严格不等式成立[7]。基于上述思想，利用精英选择思想改进人工蜂群算法可以加快算法的搜索速度和有效地找到精确解。该算法的基本步骤如下：（1）初始化种群：给定采蜜蜂的数量0n，观察蜂的数量1n，随机生成01SNnn个解；评价初始种群，从中选出0n个构成初始蜜源位置（解）；（2）确定放弃蜜源的位置，如果存在该蜜源，则该处的采蜜蜂变为侦察蜂，根据（8）式随机生成的蜜源替换该蜜源；（3）采用（7）式寻找一个新的蜜源位置，并计算该位置的适应度，如果新位置优于原来的位置，则用新位置替换掉原来的位置，否则保留原来的位置；（4）根据式（2）和（3）对蜜源位置排序；（5）根据（6）式，观察蜂选择一个新的蜜源位置，并根据(7)式产生一个新的蜜源。（6）根据排序的适应度从群体的中选择loop+1（loop循环的次数）个蜜源位置，利用精英选择思想评价该位置是否优于观察蜂所选位置，是则替换所选位置；（7）记住搜索过程中的最优蜜源位置（解）；（8）判断是否满足终止条件，否则转向步骤（2），否则停止计算。3实验验证本文来自中国月期刊网（），请到月期刊网进行查询。为了验证本文提出的方法的有效性以及ABC算法改进前后性能的比较，采用参考文献[8]的测试函数。（1）Sphere函数niixxf12)(-100ix100是一个连续、单峰的凸函数，函数全局最小点为0，即12,,0,0,,0optnxxxx.（2）Rastrigin函数)10)2cos(10()(12iniixxxf-5.12ix5.12全局最优点为0，优化结果：12,,,0,0,,0optnxxxx（3）Rosenbrock函数2122111001niiiifxxxx-10ix10全局最优点为0，优化结果为12,,,1,1,,1optnxxxx.在改进前后的ABC算法中，最大循环次数为2000。为了统计算法收敛的平均误差和均值，每个测试函数均做30次实验。每次循环运算的时候观察蜂和采蜜蜂均为50%的种群数量。表1~3为不同种群数量的蜂群算法改进前后对比结果表1：Sphere函数测试结果Tab.1TestresultsofSpherefunctionSphere函数种群数10种群数30种群数50改进前本文方法改进前本文方法改进前本文方法Mean0.0007503161.85669E-065.57868E-101.04213e-0132.2408E-154.45573E-17Std0.0008556951.39426E-057.79432E-102.83441E-153.54077E-152.89256E-17表2：Rastrigin函数测试结果Tab.2TestresultsofRastriginfunctionRastrigin函数种群数10种群数30种群数50改进前本文方法改进前本文方法改进前本文方法Mean2.482413.316530.5246120.2413520.0080271.07643E-06Std2.3732.974761.863010.973050.043591.47197e-005表3：Rosenbrock函数测试结果Tab.3TestresultsofRosenbrockfunction本文来自中国月期刊网（），请到月期刊网进行查询。Rosenbrock函数种群数10种群数30种群数50改进前本文方法改进前本文方法改进前本文方法Mean0.9218060.1805210.0985692610.0164600.0337302350．0039679Std0.5746718440.1396300.0965415460.0208420.0239928510.010462从表中可以看出改进前后算法的收敛速度得到了很大的提高，在种群数量较少的情况下本文的方法没有多大的优势，但随着种群数量的增加本文的算法越趋近最优解。4结束语本文提出了一种改进蜂群适应度算法，该算法将精英选择方法嵌入到迭代过程中，保证精英种群中的解都是目前意义上的Pareto最优解。文章最后通过3种基本测试函数加以验证，结果表明本文的算法在种群数较大的情况下明显优于改进前人工蜂群算法。参考文献[1]MichalewiczZ,SchoenauerM.Evolutionaryalgorithmsforconstrainedpaprameteroptimizationproblems[J].EvolutionaryCompution,1996,4(1):1-32.[2]FARZIS.Efficientjobschedulingingridcomputingwithmodifiedartificialfishswarmalgorithm[J].InternationalJournalofComputerTheoryandEngineering,2009,1(1):13-18.[3]宋松柏,蔡焕杰,康艳.约束优化问题的遗传算法求解[