基于粒子群和人工蜂群混合优化的混合优化算法

基于粒子群和人工蜂群混合优化的混合优化算法

干预算法是1995年提出的基于集体智慧的随机进化算法。这是根据鸟群、鱼群和人类社会行为规律提出的。由于算法收敛的速度快、设置参数少、实现简单,近年来受到学术界的广泛重视。现在,PSO在函数优化、神经网络训练、模式分类、模糊系统控制以及其它工程领域都得到了广泛的应用。尽管传统的PSO在低维空间的函数寻优问题上具有求解速度快、质量高的特点,但是一旦函数的维数增加,其优化性能便急剧下降,容易陷入局部极值,导致收敛精度降低和不易收敛到全局最优。人工蜂群算法(ArtificialBeeColony,ABC)是Karaboga于2005年提出的一种基于群体智能的随机优化算法,算法模拟蜜蜂群体的采蜜行为。蜜蜂根据各自的分工进行不同的活动,并实现蜂群信息的共享和交流,从而找到问题的最优解。目前,关于ABC的研究与应用还处于初级阶段,但由于其控制参数少、易于实现、计算简洁等优点,已被越来越多的学者所关注。ABC已成功的应用于解决函数的数值优化、人工神经网络训练、滤波器设计、生产调度、机器人路径规划等工程领域问题。ABC较好的平衡了探索和开采的能力,但是由于进化方式和选择策略的影响,使算法在快速收敛的同时容易陷入局部最优。为了克服PSO和ABC单个算法在求解全局优化问题时容易陷入局部最优的缺陷,本文基于PSO和ABC提出了一种新型的混合优化算法———PSO-ABC。PSOABC基于一种双种群进化策略,其中一个种群中的个体按照PSO操作进化,另一个种群的个体按照ABC操作进化,同时在ABC中按轮盘赌的选择方式选择个体进化所需的随机个体,此外,算法在进化过程中,每隔一定的迭代次数利用一种信息交流机制交流搜寻信息,避免各自种群陷入局部最优。1颗粒群算法和人工蜂群算法1.1平台中的位置粒子群算法是一种基于种群的优化算法,种群称为粒子群,粒子群中的个体称为粒子。设有N个粒子组成一个群体,其中第i个粒子表示为一个D维的向量xi=(xi1,xi2,…,xiD);i=1,2,…,N,即第i个粒子在D维的搜索空间中的位置是xi。第i个粒子的飞行速度也是一个D维的向量,记为vi=(vi1,vi2,…,viD),记第i个粒子迄今为止搜索到的个体极值为pi=(pi1,pi2,…,piD),整个种群迄今为止搜索到的全局极值为pg=(pg1,pg2,…,pgD),粒子群算法采用下列公式对粒子操作。其中,i=1,2,…,N,d=1,2,…,D,w表示惯性权重,c1和c2表示学习因子,r1和r2是上均匀分布的随机数,每一维粒子的速度都被限制在一个最大速度vmax(vmax>0)之间,若vi>vmax时,取vi=vmax;若vi<-vmax时,取vi=-vmax。文献在粒子群算法中引入了线性减小的惯性权重,将(1)式变换为性权重的初始值和终值,I为当前迭代次数,Imax为最大迭代次数。2.1采蜜蜂的搜索方法在人工蜂群算法中,蜂群由采蜜蜂、观察蜂和侦察蜂三个部分组成,每个蜜源的位置代表优化问题的一个可能解,蜜源的收益度(蜜量)对应于问题的适应度(函数值)。首先,人工蜂群算法随机产生初始种群,即N个初始解(N为采蜜蜂的数目也为蜜源数目)。每个解xi(i=1,2,…,N)为一个D维的向量(D为搜索空间的维数)。经过初始化,采蜜蜂、观察蜂和侦察蜂开始进行循环搜索。采蜜蜂记住自己以前的最优解,在采蜜源附近邻域搜索,搜索公式为式(4)中,k∈{1,2,…,N}和j∈{1,2,…,D}是随机选择的下标,并且k≠i,φ是[-1,1]上均匀分布的随机数。随着迭代次数的增加,(xij-xkj)之间的距离缩小,搜索的空间也缩小,即搜索的步长缩小,动态地调整步长有助于算法提高精度,并最终获得最优解。采蜜蜂采用贪婪准则,比较记忆中的最优解和邻域搜索解,当搜索解优于记忆最优解时,替换记忆解;反之,保持不变。所有的采蜜蜂完成搜索过程后,将蜜源信息通过舞蹈区与观察蜂共享。观察蜂据此按与花蜜量相关的概率选择一个蜜源位置,蜜量大的采蜜蜂吸引观察蜂的概率大于蜜量小的采蜜蜂。观察蜂像采蜜蜂那样对记忆中的位置做一定的改变,并检查新位置的花蜜量。若新位置优于记忆中的位置,则用新位置替换原位置;反之,保持不变。一个观察蜂选择某个蜜源的概率为式(5)中fi为第i个解的适应值。假如一个蜜源经过限定的的循环次数limit之后不能被改进,则该蜜源处的采蜜蜂成为侦察蜂,该蜜源位置将会被侦察蜂在解空间内发现的随机新位置代替。假设被放弃的位置为xi,则侦察蜂通过下列公式替换xi3实验2:pso+接触及适应从上节描述中可以看出,PSO和ABC产生新个体的方式不同,因而它们在寻优时的效果也会不同。所以将它们相互融合,提出一种混合优化算法———PSOABC。PSOABC将种群随机地等分为两组,其中一组种群中的个体按照PSO操作进化,现选取文献提出的粒子群算法,个体更新采用式(2)和式(3);另一组种群中的个体按照ABC操作进化,由于在原算法中,新个体由父代个体和另外一个不相同的随机个体组成,这虽有利于保持种群的多样性,但却使得搜索具有一定的盲目性,影响了算法的收敛速度。为加快算法的收敛速度,按轮盘赌的选择方式来选择式(4)中的xk,选择的概率为公式(5)。同时,在进化过程中,每隔一定的迭代次数利用一种信息交流机制交流搜寻信息使信息能够在两个种群中传递,有助于个体避免错误的信息判断而陷入局部最优点。通过对测试函数进行仿真实验,每隔50代进行一次信息交流,信息交流方式如下:1)式(3)中pg用两个种群中的最优个体来替代;2)式(4)中xk从采用PSO操作进化的种群中随机选取;3)信息交流结束,继续下一步操作。Step1设置群体规模N,最大迭代次数Maxgen,限定的的循环次数limit,学习因子c1和c2,惯性权重的初始值w1和终值w2;Step2将群体等分为两个种群,种群1中的个体按照PSO操作进化,种群2中的个体按照ABC操作进化;Step3设置迭代计数器t=0;Step4判断是否满足信息交流条件,若满足则进行信息交流;Step5种群1和种群2分别按式(3)、式(2)和式(4)产生新解,并计算其适应值;Step6更新种群1中的pi和pg;Step7如果种群2中新解的适应值优于xi,则用其替换xi,否则不变;Step8计算xi的适应值,并根据式(4)计算概率qi;Step9观察蜂根据qi选择蜜源,并按式(4)产生新解,如果新解的适应值优于xi,则用其替换xi,否则不变;Step10经过limit次循环后,判断是否有需要丢掉的解,若有,则按式(6)产生满足约束条件的新解;Step11更新迭代计数器t=t+1并记录当前整个群体中最佳个体,如果满足精度要求或进化已达到最大迭代次数,则终止算法,否则转至Step4。4基本粒子群算法的全局搜索性能为了验证改进算法的性能,选择4个测试函数用于优化实验,由于ABC在许多优化问题中都表现出优于PSO,故仅将提出的混合优化算法PSO-ABC与ABC的优化结果进行对比。进行测试时,蜂群群体规模为40。其中,PSOABC的参数设置为ABC的参数设置为limit=1000。4个基准测试函数分别为:2)Rosenbrock函数3)Rastrigin函数4)Griewank函数上述4个测试函数具有不同的特点,可以充分考察算法对不同类型问题的优化性能。它们可以分为单峰函数(f1(x)和f2(x))与多峰函数(f3(x)和f4(x))。f1(x)是较为简单的单峰函数,f2(x)虽是单峰函数,但其全局最优点隐藏于一条狭长的通道中不易获得;f3(x)和f4(x)是复杂的非线性多峰函数,具有许多局部极值点,一般算法较难找到全局最优值,可以用来检验算法的全局搜索性能。四个函数的搜索空间、初始范围和最小值如表1所示。我们采用最优适应值(BestFitness,BF)、最差适应值(WorstFitness,WF)、平均最优适应值(MeanBestFitness,MBF)和标准差(StandardDeviation,SD)来评价算法的性能。其中BF、WF、MBF、SD分别为算法独立运行10次的最优适应值、最差适应值、平均最优适应值和标准差。MBF反映了在给定迭代次数下算法所能达到的精度,SD反映了算法的稳定性和鲁棒性。表2为PSOABC、ABC在上述参数的设置下对4个测试函数分别独立运行10次得到平均最优适应值和标准差。图1—图4分别给出4个测试函数的平均最好适应值进化曲线。由表2可知,对于最简单的函数f1(x),两种算法都很快收敛到最优适应值。由于f1(x)是单峰函数,只有一个最优值,快速收敛到最优值不是问题。然而,如图1所示,PSOABC收敛速度在迭代初期与ABC相差不大,大约1200代以后PSOABC收敛速度远远优于ABC算法。对于经典的复杂优化函数f2(x),由于在取值区间内走势平坦,为算法提供少量信息,要收敛到全局最优点机会微乎其微。从表2可以看出,PSO-ABC性能明显优于ABC算法。在图2中,ABC在进化早期收敛速度很快,但在进化中后期收敛速度明显减慢,而PSOABC在进化过程中始终保持较快的收敛速度。多峰函数Rastrigin、Griewank均是复杂的非线性全局优化问题,主要用来测试算法的全局搜索性能,从表2、图3、图4可以看出,PSOABC的精度和收敛速度均高于ABC。由于这些函数自身的特性,算法很容易陷入局部最优而导致搜索停滞,但PSO-ABC对信息的交流使其尽可能的跳出局部最优,提高了算法的收敛精度。可见,PSOABC具有良好的全局搜索性能和较快的搜索速度。通过以上分析可知,PSOABC不论对单峰函数还是多峰函数,在求解精度、收敛速度以及稳定性和鲁棒性等方面比都要优于ABC,是一种有效的全局优化算法。5混合优化算法将两种或数种算法结合起来产生新的混合优化算法以达到更好的优化