收稿日期:2005-12-29基金项目:山东省自然科学基金资助项目(Y2003G01);山东省优秀中青年科学家奖励基金项目(2004BS01004)作者简介:张劲松(1976-),男,山东济南人,博士研究生,主要研究方向为生产调度、智能建模与智能算法.E-mail:pinestudio@sohu.com

　文章编号:1672-3961(2007)01-0047-04基于混沌搜索的混和粒子群优化算法

张劲松1,李歧强1,王朝霞2(1.山东大学　控制科学与工程学院,　山东　济南　250061;2.山东轻工业学院　电子信息与控制工程学院,　山东　济南　250353)

摘要:所提出的算法将粒子群优化算法和混沌算法相结合,既摆脱了算法搜索后期易陷入局部极值点的缺点,同时又保持了前期搜索的快速性.最后通过4个测试函数将该算法与基本粒子群算法进行仿真对比,比较结果表明基于混沌搜索的混和粒子群优化算法在收敛性和稳定性等方面明显优于基本粒子群优化算法.关键词:粒子群优化算法;混沌搜索;混和算法;遍历性;局部极值中图分类号:TP301.6 文献标识码:A

HybridparticleswarmoptimizationalgorithmbasedonthechaossearchZHANGJin-song1,　LIQi-qiang1,　WANGZhao-xia2(1.SchoolofControlScienceandEngineering,　ShandongUniversity,　Jinan250061,　China;2.CollegeofElectronicInformationandControlEngineering,　ShandongInstituteofLightIndustry,　Jinan250353,　China)

Abstract:Ahybridparticleswarmoptimizationalgorithmbasedonthechaossearchisproposed.Itcannotonlyovercomethedisadvantageofeasilygettingintothelocalextremuminthelaterevolutionperiod,butalsokeeptherapidityofthepreviousperiod.Finally,thebasicparticleswarmoptimizationalgorithmiscomparedwiththehybridalgorithm.Theexperimentresultsdemonstratethatthenewalgorithmproposedisbetterthanthebasicparticleswarmoptimizationalgorithmintheaspectsofconvergenceandstability.Keywords:particleswarmoptimizationalgorithm;chaossearch;hybridalgorithm;ergodicity;localextre-mum

0　引言传统的粒子群优化算法(particleswarmoptimiza-tion,PSO)收敛速度快,运算简单,易于实现【1】,可用

于解决大量非线性、不可微和多峰值的复杂问题优化,并已广泛应用于科学和工程领域,如函数优化【2】、神经网络训练【3】、模式分类【4】、模糊系统控

制【5】等.但PSO在进化后期易陷于局部极小点,算法所能达到的精度较差.而混沌搜索具有遍历性、随机性、“规律性”等特点【6】,能在一定范围内按其自身的“规律”不重复地遍历所有状态,在搜索过程中可以避免陷入局部极小点【7】,但当搜索空间大时其效果却不能令人满意【8】.笔者在传统粒子群优化算法的基础上结合混沌搜索的方法,提出一种新的组合优化方法.该算法充分利用粒子群算法运算简单、早期收敛速度快和混沌算法遍历性的特点,在运用粒子群算法进行全局搜索得到局部最优解的基础上,再以该解为中心利用混沌搜索算法进行二次寻优.这样可有效克服传统粒子群算法易陷入局部极小值

　第37卷　第1期Vol.37　No.1 山　东　大　学　学　报　(工　学　版)JOURNALOFSHANDONGUNIVERSITY(ENGINEERINGSCIENCE) 2007年2月　Feb.2007　和混沌算法搜索空间大、收敛缓慢的缺点.1　算法介绍1.1　粒子群算法【9】假设在一个D维的目标搜索空间中,有m个粒子组成一个群落,其中第i个粒子表示为一个D维的向量xi=(xi1,xi2,…,xiD),i=1,2,…,m,即第i个粒子在D维的搜索空间中的位置是xi.换言之,每个粒子的位置就是一个潜在的解.将xi带入一个目标函数就可以计算出其适应值,根据适应值的大小衡量xi的优劣.第i个粒子的“飞翔”速度也是一个D维的向量,记为vi=(vi1,vi2,…,viD).记第i个粒子迄今为止搜索到的最优位置为pi=(pi1,pi2,…,piD),整个粒子群迄今为止搜索到的最优位置为pg=(pg1,pg2,…,pgD).每个粒子的速度和位置按如下公式进行变化(“飞行”):　vid=ωvid+c1r1(pid-xid)+c2r2(pgd-xid),(1)xid=xid+vid.(2)其中,i=1,2,…,m;d=1,2,…,D;ω是非负数,称为惯性因子;学习因子c1和c2是非负常数;r1和r2是介于[0,1]之间的随机数.vid∈[-vmax,vmax],vmax是常数,由用户设定.实验中PSO算法均采用文献【10】所推荐的参数,加速因子c1=c2=1.49,学习因子ω=0.729.迭代中止条件根据具体问题一般选为最大迭代次数或粒子群迄今为止搜索到的最优位置满足预定最小适应度阈值.PSO算法需要用户确定的参数并不多,而且操作简单,故使用比较方便.而且PSO算法的收敛速度快(特别是在进化初期),运算简单、易于实现,没有遗传算法的编解码和杂交、变异等复杂运算,但是它的缺点是易陷入局部极小点,搜索精度不高.1.2　混沌搜索算法首先选择用于载波的混沌变量.选用式(3)所示的Logistic映射.tk+1=μtk(1-tk),k=0,1,2,…;t0∈[0,1].(3)其中μ是控制参量,取μ=4.设0≤x0≤1,n=0,1,2,….不难证明μ=4时系统(3)完全处于混沌状态.利用混沌对初值敏感的特点,赋给式(3)i个微小差异的初值即可得到i个混沌变量.设一类连续对象的优化问题为minf(x),ai≤xi≤bi,i=1,…,n,x=(x1,x2,…,xn).混沌优化方法的基本步骤如下:(1)算法初始化:设置最大迭代次数M,置k=1,对式(3)中的tk,分别赋于n个具有微小差异的初值,则可得到n个轨迹不同的混沌变量ti(k);(2)用混沌变量进行搜索:xi(k)=x＊i+δiti(k)+di,(4)δi,di可根据实际情况而定,x＊i为当前最优解的第

i个分量.计算性能指标f(k)=f(x(k)),x(k)=(x1(k),x2(k),…,xn(k));(3)如果f(k)(4)当k>M时,f＊保持不变,结束;否则令k=

k+1,转步骤(2).将混沌算法用于粒子群算法时,为了防止出现单侧搜索的现象,修改式(4)为

xi(k)=x＊i+2δi[12-ti(k)]+di,

因为2[12-ti(k)]∈[-1,1],所以这样可以在局部最优点附近产生正负两个方向的扰动,有利于扩大搜索范围,摆脱局部极值点.1.3　基于混沌搜索的粒子群算法不难发现,如果粒子群的历史最优粒子位置pg

在较长时间内未发生变化,则粒子群很接近pg,其

速度更新将主要由ωvid来决定,ω<1时速度将越来越小,因此粒子群表现出强烈的“趋同性”,当粒子数较少时,表现在优化性能上就是收敛速度快,但易陷入局部极值点.本文中提出的基于混沌搜索的粒子群优化算法是以基本粒子群优化算法的运算流程作为主体流程,把混沌搜索机制引入其中,以此来增强全局搜索能力,摆脱局部极值点的吸引,同时又不降低收敛速度和搜索精度.其基本的执行过程是先随机产生初始群体,然后开始随机搜索,通过基本的粒子群优化算法(式(1),(2))来产生一组新的个体.当整个粒子群历史最优粒子位置pg连续不变化或变化极小时,在pg为中心的一定范围内进行混沌搜索,将混沌搜索得到的最优解x′作为新的pg继续原粒子群算法的求解.其具体的算法流程如下:(1)初始化参数:学习因子c1和c2,惯性因子

ω,最大迭代次数M,控制参量μ,混沌搜索起始迭代次数T;(2)初始化一群微粒(群体规模为m),包括随机位置和速度;(3)评价每个微粒的目标适应度,确定第i个

　48　山　东　大　学　学　报　(工　学　版)第37卷　粒子迄今为止搜索到的最优位置pi=(pi1,pi2,…,piD),和整个粒子群迄今为止搜索到的最优位置pg=(pg1,pg2,…,pgD);(4)采用式(1),(2)对种群中的粒子进行一次迭代操作,若当前最优个体满足收敛条件或达到最大迭代次数,转步骤(6);(5)如果整个粒子群历史最优粒子位置pg在进行了T次粒子群迭代运算之后不变化或变化极小,则令x＊i=pgi,采用节1.2的混沌搜索算法进行寻优得到最优值x′i,pgi=x′i,转步骤(3)继续下一次粒子群算法,否则直接转步骤(3);(6)进化过程结束,返回全局最优解.2　仿真比较采用下面4个典型测试函数来评价所提出的基于混沌搜索的混和粒子群算法的性能,这些函数具有连续 不连续、凸 非凸、单峰 多峰等特点,经常被国内外学者用于对优化问题的测试.(1)F1=∑2i=1x2i,-5.12≤xi≤5.12,在[-5.12,5.12]区间内有一个全局最小值点(0,0),全局最小值为0.(2)F2=x2-0.4cos(3πx)+2y2-0.6cos(4πy)+1,-10≤x,y≤10,在[-10,10]区间内有一个全局最小值点(0,0),全局最小值为0.

(3)F3=14000(x2+y2)-cos(x)cos(y 2)+1,-600≤x,y≤600,在[-600,600]区间内有一个全局最小值点(0,0),全局最小值为0.

(4)F4=sin2x2+y2-0.5(1+0.001(x2+y2))2+0.5,-100<

x,y<100,在[-100,100]区间内有一个全局最小值点(0,0),全局最小值为0.算法的初始化参数如下:粒子群规模M=20,学习因子C1=C2=1.49,惯性因子ω=0.79,最大迭代次数M=1200,混沌搜索起始迭代次数T=300.用VC++6.0分别编写了基本粒子群算法和基于混沌搜索的混和粒子群算法仿真程序,各连续运行500次,将所得函数全局最小值点、全局最小值的平均值以及全局最小值的标准差作为算法的衡量指标,列于表1进行比较.其中最优解的平均值反映了解的优劣,最优解的标准差反映了算法的稳定性.