权重自适应调整的混沌量子粒子群优化算法

2012年第21卷第8期权重自适应调整的混沌量子粒子群优化算法①李欣然1，靳雁霞21(中北大学电子与计算机科学技术学院,山西太原030051)2(中北大学仪器科学与动态测试教育部重点试验室,山西太原030051)摘要：针对量子粒子群优化算法在处理高维复杂函数收敛速度慢、易陷入局优的问题，利用混沌算子的遍历性提出了基于惯性权重自适应调整的混沌量子粒子群优化算法。新算法首先引入聚焦距离变化率的概念，将惯性因子表示为关于聚焦距离变化率的函数，从而使算法具有动态自适应性;其次，在算法中嵌入有效判断早熟停滞的方法，一旦检索到早熟迹象，根据构造的变异概率对粒子进行变异使粒子跳出局部昀优，从而减少无效迭代。对高维测试函数的实验表明：改进算法的性能优于经典的PSO算法，基于量子行为的PSO算法。关键词：基于量子行为的粒子群优化算法(QPSO)；混沌序列；惯性权重；聚焦距离变化率；变异ChaosQuantumParticleSwarmOptimizationAlgorithmWithSelf-adaptingAdjustmentofInertiaWeightLIXin-Ran1,JINYan-Xia21(CollegeofComputerScienceandTechnology,NorthUniversityofChina,Taiyuan030051,China)2(MinistryofEducationKeyLaboratoryofInstrumentationScienceandDynamicMeasurement,NorthUniversityofChina,Taiyuan030051,China)Abstract：Anovelalgorithmispresentedonthebaseofquantumbehavedparticleswarmoptimization，whichisaimedatresolvingtheproblemofslowconvergencerateinoptimizinghigherdimensionalsophisticatedfunctionsandbeingtrappedintolocalminimaeasily.Chaosalgorithmisincorporatedtotraversethewholesolutionspace.First,rateofclusterfocusdistancechangingwasintroducedinthisnewalgorithmandtheweightwasformulatedasafunctionofthisfactorwhichprovidesthealgorithmwitheffectivedynamicadaptability.Secondly,amethodofeffectivejudgmentofearlystagnationisembeddedinthealgorithm.Oncetheearlymaturityisretrieved,thealgorithmmutatesparticlestojumpoutofthelocaloptimumparticleaccordingtothestructuremutationsoastoreduceinvaliditeration.Experimentsonhigh-dimensiontestfunctionsindicatethattheimprovedalgorithmissuperiortoclassicalPSOalgorithmandquantum-behavedPSOalgorithm.Keywords：Quantum-behavedParticleSwarmOptimization;Chaoticsequence;Inertiaweight;Rateofclusterfocusdistancechanging;Mutation粒子群优化(ParticleSwarmOptimization，PSO)是由Kennedy和Eberhart于1995年提出的一类模拟群体智能行为的优化算法[1]，与遗传算法和蚁群算法相比，PSO有着算法简单，容易实现，并且可调整参数少等特点，因此被广泛地应用于函数优化、神经网络训练、数据挖掘、模糊系统控制以及其他的应用领域。实验发现PSO算法在进化过程中存在早熟收敛和局部寻优能力差等缺点，近年来国内外的许多研究者针对这些缺点作了大量的工作，并提出了各种改进的PSO算法[2]。但这些改进的PSO不同程度地降低了收敛速度。2004年，孙俊等人提出了具有量子行为的粒子群优化算法(Quantum-behavedParticle①基金项目:国家自然科学基金(61004127);中北大学青年基金(2010-12-31)收稿时间:2011-11-06;收到修改稿时间:2012-01-15计算机系统应用)[3]。该算法简单有效，收敛速度快，全局搜索性能远优于PSO。但是与标准的PSO算法以及其他进化算法一样存在早熟的问题。本文在QPSO算法基础上，首先引入文献[4]中提到的Tent映射初始化均匀分布的粒群，提高了初始解的质量；其次，根据文献[5]引入聚焦距离变化率的概念,并根据它对粒子群算法搜索能力的影响,将惯性因子表示为关于聚焦距离变化率的函数，同时为克服早熟收敛引入变异算子，提出了一种权重自适应调整的混沌量子粒子群优化算法(ACQPSO)算法。该算法大大加强算法的搜索多样性，从而减少了寻优需要的进化代数，而且算法增加了停滞判别，使算法能跳出局部昀优，有效去除无效迭代，从而加速收敛。1基于量子行为的PSO算法2004年JunSun等人提出了量子粒子群算法(QPSO)[3]。由于在量子空间中的粒子满足聚集态的性质完全不同，粒子移动时没有确定的轨迹，这使粒子可以在整个可行解空间中进行探索寻找全局昀优解，因而QPSO算法的全局搜索能力远远优于经典的PSO算法。在量子空间中,QPSO算法利用波函数Ψ(x,t)来描述粒子的状态,并通过求解薛定谔方程得到粒子在空间某一点出现的概率密度函数,再通过蒙特卡罗随机模拟得到粒子的位置方程。在QPSO算法中，设种群规模为M，在进化过程中粒子以一定概率取加或减，更新每个粒子的位置，并生成新的粒子群体，由公式(1)至(4)决定：GbestaiPbestaP*)1()(*−+=(1)∑==MiiPbestMmbest1)(1(2)b=1.0-generation/maxgeneration*0.5(3)position=P±b*|mbest-position|*ln(1/μ)(4)其中，Pbest(i)为第i次迭代时粒子的昀佳位置，Gbest为第i次迭代时群体的全局昀佳位置，P为Pbest(i)和Gbest之间的一个随机位置。mbest是粒子群Pbest的中间位置，即平均值；b为惯性权值,是QPSO算法收敛的一个重要参数，在QPSO收敛过程中线性减小；α、μ为0至1之间的随机数，如果产生的μ大于0.5，式(4)取加，否则取减；generation为当前进化代数，maxgeneration为设定的昀大进化代数。2权重自适应调整的混沌量子粒子群优化算法2.1改进初始粒子群的产生混沌序列具有混沌运动的特点，从而有较好的随机性和遍历性。因此本文利用混沌序列这一特点进行粒子群的初始化分布，可大大加强算法的搜索多样性，为找到更优解和加快收敛奠定坚实的基础。目前文献中引用较多的是Logistic映射算子。文献[4]通过比较指出Tent映射比Logistic映射具有更好的遍历均匀性和更快的迭代速度，并经过严格数学推理，论证了Tent映射具有作为优化算法混沌序列的前提条件。其表达式如式(5)所示：⎩⎨⎧≤≤−≤≤=+=121)1(221021KKKKKXXXXX(5)理论研究表明[4]：Tent映射经贝努利移位变换后可以表示成如下形式：mod12XXKK)(1=+(6)因此，根据Tent映射，可按如下步骤在可行域中产生粒子i的混沌点列：Stepl取初值x0(x0应避免落入小周期点内，如4周期(0.20.4.0.8.0.6))，记入标志组s，s(1)=x0，i=j=1。Step2利用式(6)进行迭代，i自增1，产生x序列。Step3如果迭代达到昀大次数，则转向执行Step5;否则，若产生的x序列落入不动点或5周期以内的小循环(如x(i)={0，0.25，0.5，0.75}或者x(i)=x(i-k)，k={0，1，2，3，4}，则转向执行Step4;若产生的序列未出现上述情况，则转向执行Step2。Step4改变迭代初值x(i)=s(j+1)=s(j)+ε，j=j+1返回Step2。Step5程序运行结束，保存产生的x序列。2.2随机惯性权重的构造在PSO和QPSO中，惯性权重ω对算法是否能达到收敛具有重要作用，它使粒子保持运动惯性，ω值大有利于全局搜索，收敛速度快，但是不易得到精确的解；ω值小有利于局部搜索，能得到更为精确的解，但收敛速度慢。我们按照文献[5]的方法定义粒子的昀大聚焦距离MaxDist(式7)、粒子平均聚焦距离MeanDist(式8)。聚焦距离变化率k如式(9)所示。其中m为粒子数,D为每个粒子的维数,Gbest为粒子群目前搜索到的昀优位2012年第21卷第8期置,Pbest(i)为每个粒子目前搜索到的昀优位置。()⎟⎟⎠⎞⎜⎜⎝⎛−=∑==DimiiPbestGbestMaxDist12,,2,1)(max(7)()miPbestGbestMeanDistmiDimi⎟⎟⎠⎞⎜⎜⎝⎛−=∑∑===112,,2,1)(max(8)其中m为粒子数，D为每个粒子的维数，Gbest为粒子群目前搜索到的昀优位置，Pbest(i)为每个粒子目前搜索到的昀优位置。粒子当前聚焦距离变化率定义为MaxDistMeanDistMaxDistk−=(9)当聚焦距离变化率较大时表明粒子的昀大聚焦距离和平均聚焦距离相差较大,此时粒子的全局搜索较差,故应使粒子尽快地进入全局搜索,相反我们就应该提高粒子的局部搜索能力。据此我们可以判断此次的粒子是应该提高其全局搜索能力还是需要提高其局部搜索能力,我们更需要对它的惯性权重进行调整。本文定义惯性权重，如式（10）[8]所示。⎪⎩⎪⎨⎧≤+≤≤++=050ln021050021ln022211.|k|k|,|).|r|(a|k|.,.|r|aa|k|k|,)|.|r|(aω(10)其中a1=0.3，a2=0.2，r为一个[0，1]间均匀分布的随机数。该选择策略即随机地选取ω值，使ω随聚焦距离的变化率自适应地调整。此时，将式(4)改写为如式(11)所示。2.3判断并克服早熟停滞的方法随机惯性权重能够提高解的质量，但不能从根本上克服易陷入局部收敛的缺陷，只是增强了全局搜索的能力。QPSO面对的主要问题是随着优化问题规模的增加，粒子易于落入到局部昀优解，而导致搜索能力的下降。本文利用全局昀大适应值与个体平均昀大适应值的比值来判断是否早熟停滞，根据构造的变异概率对粒子进行变异使粒子克服早熟。设第t代粒子群发现的全局昀大适应值Gbest，个体平均昀大适应值mbest即式(3)。如果Gbest(t+1)优于Gbest(t)或mbest(t+1)优于mbest(t)，则说明粒子群正在向好的方向进化。在算法运行初期，由于粒子之间的差异较大，全局昀大适应值与个体平均昀大适应值之比γ即式(12)一般比较大；当算法接近收敛时，γ趋向于1。因而如果γ长时间接近1但