粒子群算法(优化算法)毕业设计毕设论文(包括源代码实验数据-截图-很全面的)

I毕业论文题目粒子群算法及其参数设置专业信息与计算科学班级计算061学号3060811007学生xx指导教师徐小平2010年II粒子群优化算法及其参数设置专业：信息与计算科学学生：xx指导教师：徐小平摘要粒子群优化是一种新兴的基于群体智能的启发式全局搜索算法，粒子群优化算法通过粒子间的竞争和协作以实现在复杂搜索空间中寻找全局最优点。它具有易理解、易实现、全局搜索能力强等特点，倍受科学与工程领域的广泛关注，已经成为发展最快的智能优化算法之一。论文介绍了粒子群优化算法的基本原理，分析了其特点。论文中围绕粒子群优化算法的原理、特点、参数设置与应用等方面进行全面综述，重点利用单因子方差分析方法，分析了粒群优化算法中的惯性权值，加速因子的设置对算法基本性能的影响，给出算法中的经验参数设置。最后对其未来的研究提出了一些建议及研究方向的展望。关键词：粒子群优化算法；参数；方差分析；最优解IIIParticleswarmoptimizationalgorithmanditsparametersetSpeciality:InformationandComputingScienceStudent:RenKanAdvisor:XuXiaopingAbstractParticleswarmoptimizationisanemergingglobalbasedonswarmintelligenceheuristicsearchalgorithm,particleswarmoptimizationalgorithmcompetitionandcollaborationbetweenparticlestoachieveincomplexsearchspacetofindtheglobaloptimum.Ithaseasytounderstand,easytoachieve,thecharacteristicsofstrongglobalsearchability,andhasneverwidefieldofscienceandengineeringconcern,hasbecomethefastestgrowingoneoftheintelligentoptimizationalgorithms.Thispaperintroducestheparticleswarmoptimizationbasicprinciples,andanalyzesitsfeatures.Paperaroundtheparticleswarmoptimizationprinciples,characteristics,parameterssettingsandapplicationstoconductathoroughreview,focusingonasinglefactoranalysisofvariance,analysisoftheparticleswarmoptimizationalgorithmintheinertiaweight,accelerationfactorsettingthebasicpropertiesofthealgorithmtheimpactoftheexperienceofthealgorithmgivenparametersetting.Finally,itsfutureresearchedandprospectsareproposed.Keyword：Particleswarmoptimization;Parameter;Varianceanalysis;OptimalsolutionIV目录11.引言1.1研究背景和课题意义“人工生命”是来研究具有某些生命基本特征的人工系统。人工生命包括两方面的内容：1、研究如何利用计算技术研究生物现象。2、研究如何利用生物技术研究计算问题。现在已经有很多源于生物现象的计算技巧。例如，人工神经网络是简化的大脑模型。遗传算法是模拟基因进化过程的。现在我们讨论另一种生物系统-社会系统。也可称做“群智能”(swarmintelligence)。这些模拟系统利用局部信息从而可能产生不可预测的群体行为。粒子群优化算法(PSO)也是起源对简单社会系统的模拟。最初设想是模拟鸟群觅食的过程。但后来发现PSO是一种很好的优化工具。优化是科学研究、工程技术和经济管理等领域的重要研究课题。粒子群优化算法[1](简称PSO)是由Kennedy和Eberhart通过对鸟群、鱼群和人类社会某些行为的观察研究，于1995年提出的一种新颖的进化算法。虽然PSO算法发展迅速并取得了可观的研究成果,但其理论基础仍相对薄弱，尤其是算法基本模型中的参数设置和优化问题还缺乏成熟的理论论证和研究。鉴于PSO的发展历史尚短，它在理论基础与应用推广上都还存在一些缺陷，有待解决。本文通过对PSO算法的步骤的归纳、特点的分析，利用统计中的方差分析，通过抽样实验方法，论证了该算法中关键参数因子:惯性权值、加速因子对算法整体性能的影响效果，并提出了参数设置的指导原则，给出了关键参数设置，为PSO算法的推广与改进提供了思路。1.2参数的影响标准粒子群算法中主要的参数变量为（惯性权值），，（加速因子），w1c2c，本文重点对参数，，做数据统计实验。包括不变的情况下通过maxvw1c2cw，变化找出加速因子对算法的影响。还有保持，不变对分别取不同值1c2c1c2cw分析其对算法结果影响。21.3应用领域近年来，PSO快速发展，在众多领域得到了广泛应用。本文将应用研究分典型理论问题研究和实际工业应用两大类。典型理论问题包括：组合优化、约束优化、多目标优化、动态系统优化等。实际工业应用有：电力系统、滤波器、自动控制、数据聚类、模式识别与图像处理、化工、机械、通信、机器人、经济、生物信息、医学、任务分配、TSP等等。1.4电子资源身处信息和网络时代的我们是幸运的，丰富的电子资源能让我们受益匪浅。如果想较快地对PSO有一个比较全面的了解，借助网络空间的电子资源无疑是不二之选。对一些初学者而言，哪里能下载得到PSO的源程序，是他们很关心的话题；即使对一些资深的读者，为了验证自己提出的新算法或改进算法，如果能找到高级别国际期刊或会议上最近提出的算法源程序，那也是事半功倍的美事。这里介绍当今PSO研究领域较有影响的一个网址：MauriceClerc博士(Maurice.Clerc@WriteMe.com)的PSO主页：http://clerc.maurice.free.fr/pso/该主页主要介绍MauriceClerc博士带领的PSO研究小组的研究成果。除了从中可以得到他们近几年公开发表的相关文献和源代码，还可以下载一些未公开发表的文章。这些未公开发表的文章往往是MauriceClerc博士的一些设想，而且在不断更新，如“Backtorandomtopology”、“Initialisationsforparticleswarmoptimization”、“SomeideasaboutPSO”等等，对PSO研究人员很有启发。1.5主要工作论文内容介绍了基本粒子群算法，用matlab实现标准粒子群算法算法，对两个不同类型函数做具体分析，然后对其参数（惯性权值），，（加速因子）w1c2c测试。分别对其利用单因子方差分析法，说明不同参数水平对算法速率性能的影响。并且通过公式计算准确判断参数对算法影响。最后说明粒子群优化算法在实际中的应用以及对未来展望，最后总结了算法的优缺点，附录里面附有测试程序和测试函数。32.基本粒子群算法2.1粒子群算法思想的起源粒子群优化(ParticleSwarmOptimization,PSO)算法[1]是Kennedy和Eberhart受人工生命研究结果的启发、通过模拟鸟群觅食过程中的迁徙和群聚行为而提出的一种基于群体智能的全局随机搜索算法，1995年IEEE国际神经网络学术会议发表了题为“ParticleSwarmOptimization”的论文，标志着PSO算法诞生(注：国内也有很多学者译为“微粒群优化”)。它与其他进化算法一样，也是基于“种群”和“进化”的概念，通过个体间的协作与竞争，实现复杂空间最优解的搜索；同时，PSO又不像其他进化算法那样对个体进行交叉、变异、选择等进化算子操作，而是将群体(swarm)中的个体看作是在D维搜索空间中没有质量和体积的粒子(particle)，每个粒子以一定的速度在解空间运动，并向自身历史最佳位置pbest和邻域历史最佳位置聚pbest集，实现对候选解的进化。PSO算法具有很好的生物社会背景[2]而易理解、参数少而易实现，对非线性、多峰问题均具有较强的全局搜索能力，在科学研究与工程实践中得到了广泛关注[3-10]。自然界中各种生物体均具有一定的群体行为，而人工生命的主要研究领域之一是探索自然界生物的群体行为，从而在计算机上构建其群体模型。自然界中的鸟群和鱼群的群体行为一直是科学家的研究兴趣，生物学家CraigReynolds在1987年提出了一个非常有影响的鸟群聚集模型[7]，在他的仿真中，每一个个体遵循：(1)避免与邻域个体相冲撞；(2)匹配邻域个体的速度；(3)飞向鸟群中心，且整个群体飞向目标。仿真中仅利用上面三条简单的规则，就可以非常接近的模拟出鸟群飞行的现象。1990年，生物学家FrankHeppner也提出了鸟类模型[8]，它的不同之处在于：鸟类被吸引飞到栖息地。在仿真中，一开始每一只鸟都没有特定的飞行目标，只是使用简单的规则确定自己的飞行方向和飞行速度（每一只鸟都试图留在鸟群中而又不相互碰撞），当有一只鸟飞到栖息地时，它周围的鸟也会跟着飞向栖息地，这样，整个鸟群都会落在栖息地。1995年，美国社会心理学家JamesKennedy和电气工程师RussellEberhart共同提出了粒子群算法，其基本思想是受对鸟类群体行为进行建模与仿真的研究结果4的启发。他们的模型和仿真算法主要对FrankHeppner的模型进行了修正，以使粒子飞向解空间并在最好解处降落。Kennedy在他的书中描述了粒子群算法思想的起源。自20世纪30年代以来，社会心理学的发展揭示：我们都是鱼群或鸟群聚集行为的遵循者。在人们的不断交互过程中，由于相互的影响和模仿，他们总会变得更相似，结果就形成了和文明。人类的自然行为和鱼群及鸟群并不类似，而人类在高维认知空间中的思维轨迹却与之非常类似。思维背后的社会现象远比鱼群和鸟群聚集过程中的优美动作复杂的多：首先，思维发生在信念空间，其维数远远高于3；其次，当两种思想在认知空间会聚于同一点时，我们称其一致，而不是发生冲突。2.2算法原理PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的潜在解都是搜索空间中的一只鸟，称之为粒子。所有的粒子都有一个由被优化的函数决定的适值(fitnessvalue)，每个粒子还有一个速度决定它们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索[1]。PSO初始化为一群随机粒子(随机解)，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己；第一个就是粒子本身所找到的最优解，这个解称为个体极值；另一个极值是整个种群目前找到的最优解，这个极值是全局极值。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。假设在一个维的目标搜索空间中，有个粒子组成一个群落，其中第个粒DNi子表示为一个维的向量D，。),,,(21iDiiixxxXNi,,2,1第个粒子的“飞行”速度也是一个维的向量，记为iD，。),,21iiDiivvvV，（3,2,1i第个粒子迄今为止搜索到的最优位置称为个体极值，记为i，。),,,(21iDiibestppppNi,,2,1整个粒子群迄今为止搜索到的最优位置为全局极值，记为),,,(21gDggbestpppg5在找到这两个最优值时，粒子根据如下的公式(2.1)和(2.2)来更新自己的速度和位置[12]：(2.1))(2211idgdididididxprcxprcvwv(2.2)idididvxx其中：和为学习因子，也称加速常数(accelerationconstant)，和为[0，1]1c2c1r2r范围内的均匀随机数。式(2.1)右边由三部分组成，第一部分为“惯性(inertia)”或“动量(momentum)”部分，反映了粒子的运动“习惯(habit)”，代表粒子有维持自己先前速度的趋势；第二部分为“认知(cognition)”部分，反映了粒子对自身历史经验的记忆(memory)或回忆(remembrance)，代表粒子有向自身历史最佳位置逼近的趋势；第三部分为“社会(social)”部分，反映了粒子间协同合作与知识共享的群体历史经验，代表粒子有向群体或邻域历史最佳位置逼近的趋势，根据经验，通常。。是粒子的速度，，是常数，221ccDi,,2,1idv],[maxmaxvvvidmaxv由用户设定用来限制粒子的速度。和是介于之间的随机数[2][5]。1r2r]1,0[2.3基本粒子群算法流程算法的流程如下：①初始化粒子群，包括群体规模，每个粒子的位置和速度NixiV②计算每个粒子的适应度值；][iFit③对每个粒子，用它的适应度值和个体极值比较，如果][iFit）（ipbest，则用替换掉；)(][ipiFbestit][iFit）（ibestp④对每个粒子，用它的适应度值和全局极值比较，如果][iFitbestg则用替；)(][ipiFbestit][iFitbestg⑤根据公式（2.1），（2.2）更新粒子的速度和位置；ivix⑥如果满足结束条件(误差足够好或到达最大循环次数)退出，否则返回②。6输出结果根据方程(2.2)对粒子的位置进行进化根据方程(2.1)对粒子的速度进行进化求出整个群体的全局最优值求出每个粒子的个体最优计算每个粒子的适应值初始化每个粒子的速度和位置是否满足结束条件是否开始图2.1.PSO算法流程图2.4特点1、式(2.1)中第1部分可理解为粒子先前的速度或惯性；第2部份可理解为粒子的“认知”行为，表示粒子本身的思考能力；第3部分可理解为粒子的“社会”行为，表示粒子之间的信息共享与相互合作。公式(2.2)表示了粒子在求解空间中，由于相互影响导致的运动位置调整。整个求解过程中，惯性权重、加速因子w1c和和最大速度共同维护粒子对全局和局部搜索能力的平衡。2cmaxv72、粒子群优化算法初期，其解群随进化代数表现了更强的随机性，正是由于其产生了下一代解群的较大的随机性，以及每代所有解的“信息”的共享性和各个解的“自我素质”的提高。3、PSO的一个优势就是采用实数编码，不需要像遗传算法一样采用二进制编码(或者采用针对实数的遗传操作)。例如对于问题求解，粒子232221xxxf可以直接编码为，而适应度函数就是。),,(321xxx)(xf4、粒子具有“记忆”的特性，它们通过“自我”学习和向“他人”),,(321xxx学习，使其下一代解有针对性的从“先辈”那里继承更多的信息，从而能在较短的时间内找到最优解。5、与遗传算法相比，粒子群优化算法的信息共享机制是很不同的:在遗传算法中，染色体互相共享信息，所以整个种群的移动是比较均匀的向最优区域移动;在粒子群优化算法中，信息流动是单向的，即只有将信息给其他的粒子，这使bestg得整个搜索更新过程跟随当前解。2.5带惯性权重的粒子群算法探索是偏离原来的寻优轨迹去寻找一个更好的解，探索能力是一个算法的全局搜索能力。开发是利用一个好的解，继续原来的寻优轨迹去搜索更好的解，它是算法的局部搜索能力。如何确定局部搜索能力和全局搜索能力的比例，对一个问题的求解过程很重要。1998年，YuhuiShi[9]提出了带有惯性权重的改进粒子群算法。其进化过程为：（2.3）))()()(())()()(()()1(2211txtptrctxtptrctwvtvijgiijijijij（2.4）)1()()1(tvtxtxijijij在式(2.1)中，第一部分表示粒子先前的速度，用于保证算法的全局收敛性能；第二部分、第三部分则是使算法具有局部收敛能力。可以看出，式（2.3)中惯性权重表示在多大程度上保留原来的速度。较大，全局收敛能力强，局部收敛能ww力弱；较小，局部收敛能力强，全局收敛能力弱。w当时，式(2.3)与式(2.1)完全一样，表明带惯性权重的粒子群算法是基本1w粒子群算法的扩展。实验结果表明，在之间时，PSO算法有更快的收w]2.18.0[8敛速度，而当时，算法则易陷入局部极值。2.1w2.7粒子群算法的研究现状在算法的理论研究方面。目前PSO算法还没有成熟的理论分析，少部分研究者对算法的收敛性进行了分析，大部分研究者在算法的结构和性能改善方面进行研究，包括参数分析，拓扑结构，粒子多样性保持，算法融合和性能比较等。PSO由于有简单、易于实现、设置参数少、无需梯度信息等特点，其在连续非线性优化问题和组合优化问题中都表现出良好的效果。93.粒子群优化算法的改进策略由于PSO中粒子向自身历史最佳位置和邻域或群体历史最佳位置聚集，形成粒子种群的快速趋同效应，容易出现陷入局部极值、早熟收敛或停滞现象[12-14]。同时，PSO的性能也依赖于算法参数[15]。为了克服上述不足，各国研究人员相继提出了各种改进措施。本文将这些改进分为4类：粒子群初始化、邻域拓扑、参数选择和混合策略。3.1粒子群初始化研究表明，粒子群初始化对算法性能产生一定影响[16]。为了初始种群尽可能均匀覆盖整个搜索空间，提高全局搜索能力，Richard和Ventura[17]提出了基于centroidalvoronoitessellations(CVTs)的种群初始化方法；薛明志等人[18]采用正交设计方法对种群进行初始化；Campana等人[19]将标准PSO迭代公式改写成线性动态系统，并基于此研究粒子群的初始位置，使它们具有正交的运动轨迹；文献[16]认为均匀分布随机数进行初始化实现容易但尤其对高维空间效果差，并另外比较了3种初始化分布方法。3.2邻域拓扑根据粒子邻域是否为整个群体，PSO分为全局模型和局部模型[20]。gbestgbest对于模型，每个粒子与整个群体的其他粒子进行信息交换，并有向所有粒子gbest中的历史最佳位置移动的趋势。Kennedy[21]指出，模型虽然具有较快的收敛gbest速度，但更容易陷入局部极值。为了克服全局模型的缺点，研究人员采用每gbest个粒子仅在一定的邻域内进行信息交换，提出各种局部模型[21,]。根据现有的gbest研究成果，本文将邻域分为空间邻域(spatialneighborhood)、性能空间(performancespace)邻域和社会关系邻域(sociometricneighborhood)。空间邻域直接在搜索空间按粒子间的距离(如欧式距离)进行划分，如Suganthan[23]引入一个时变的欧式空间邻域算子：在搜索初始阶段，将邻域定义为每个粒子自身；随着迭代次数的增加，10将邻域范围逐渐扩展到整个种群。性能空间指根据性能指标(如适应度、目标函数值)划分的邻域，如文献[24]采用适应度距离比值(fitness-distance-ratio)来选择粒子的相邻粒子。社会关系邻域通常按粒子存储阵列的索引编号进行划分[25]，这也是研究最多的一种划分手段，主要有[21]：环形拓扑(ringorcircletopology)、轮形拓扑(wheeltopology)或星形拓扑(startopology)、塔形拓扑(pyramidtopology)、冯－诺以曼拓扑(VonNeumanntopology)以及随机拓扑(randomtopology)等。针对不同的优化问题，这些拓扑的性能表现各异；但总的来说，随机拓扑往往对大多数问题能表现出较好的性能，其次是冯－诺以曼拓扑[22]。M.Clerc[25]对随机拓扑进行了进一步分析，并在2006年版和2007年版的标准PSO[23]中采用了随机拓扑。此外，文献[21]提出动态社会关系拓扑(Dynamicsociometry)，初始阶段粒子采用环形拓扑(ring-typetopology)，随着迭代次数的增加，逐渐增加粒子间连接，最后形成星形拓扑(star-typetopology)。此外，还有其它一些主要对群体进行划分的邻域结构(本文暂称“宏观邻域”；则上述邻域称为“微观邻域”)。文献[19]引入了子种群，子种群间通过繁殖(Breeding)实现信息交流。Kennedy[20]提出了社会趋同(Stereotyping)模型，使用簇分析将整个粒子群划分为多个簇，然后用簇中心代替带收缩因子PSO中的粒子历史最佳位置或群体历史最佳位置。X.Li[21]根据粒子相似性动态地将粒子群体按种类划分为多个子种群，再以每个子种群的最佳个体作为每个粒子的邻域最佳位置。StefanJanson等人[22]提出等级PSO(hierarchicalparticleswarmoptimizer,HPSO)，采用动态等级树作为邻域结构，历史最佳位置更优的粒子处于上层，每个粒子的速度由自身历史最佳位置和等级树中处于该粒子上一个节点的粒子的历史最佳位置决定。文献[13]采用主－仆模型(master–slavermodel)，其中包含一个主群体，多个仆群体，仆群体进行独立的搜索，主群体在仆群体提供的最佳位置基础上开展搜索。文献[14]将小生境(niche)技术引入到PSO中，提出了小生境PSO(NichingParticleSwarmOptimizer)。文献[15]采用多群体进行解的搜索。文献[14]则每间隔一定代数将整个群体随机地重新划分，提出动态多群体PSO。在标准的PSO算法中，所有粒子仅仅向自身和邻域的历史最佳位置聚集，而没有向邻域内其他个体(即使这些个体很优秀)学习，造成信息资源的浪费，甚至因此而陷入局部极值；考虑到此因素，Kennedy等人[17]提出了全信息粒子群(fullyinformedparticleswarm,FIPS)，在FIPS中，每个粒子除了自身和邻域最佳历史位置外，还学习邻域内其他粒子的成功经验。上述粒子间学习是在整个维空间中构造邻域进行的，这样当搜索空间维数D较高时往往容易遭受“维数灾(curseofdimensionality)”的困扰[14]。基于这方面的考11虑，VandenBergh等人[18]提出了协作PSO(CooperativePSO)算法，其基本思路就是采用协作行为，利用多个群体分别在目标搜索空间中的不同维度上进行搜索，也就是一个优化解由多个独立群体协作完成，每个群体只负责优化这个解矢量部分维上的分量。Baskar和Suganthan[19]提出一种类似的协作PSO，称为并发PSO(concurrentPSO，CONPSO)，它采用两个群体并发地优化一个解矢量。近来，El-Abd等人[20]结合文献[18,19]的技术，提出了等级协作PSO(hierarchalcooperativePSO)。无论是粒子群在D-维的搜索还是多个粒子群在不同维上的协作搜索，其目的都是为了每个粒子能够找到有利于快速收敛到全局最优解的学习对象。J.Liang等人[4]提出了一种既可以进行D-维空间搜索、又能在不同维上选择不同学习对象的新的学习策略，称为全面学习PSO(ComprehensiveLearningParticleSwarmOptimizer，CLPSO)。与传统PSO只向自身历史最佳位置和邻域历史最佳位置学习不同，CLPSO的每个粒子都随机地向自身或其它粒子学习，并且其每一维可以向不同的粒子学习；该学习策略使得每个粒子拥有更多的学习对象，可以在更大的潜在空间飞行，从而有利于全局搜索。CLPSO的速度更新公式为：（3.1））（1),()1()()(txjprtwvtvijjfijiji其中为加速因子，为[0,1]内的均匀随机数，表示粒子在第维的学r)(jfii习对象，它通过下面的策略决定：产生[0,1]内的均匀随机数，如果该随机数大于j为粒子预先给定的学习概率，则学习对象为自身历史最佳位置；否则，从种iipc群内随机选取两个个体，按锦标赛选择(tournamentselection)策略选出两者中最好的历史最佳位置作为学习对象。同时，为了确保粒子尽可能向好的对象学习而不把时间浪费在较差的对象上，上述学习对象选择过程设定一个更新间隔代数(refreshinggap)，在此期间的学习对象保持上次选择的学习对象不变。以上的各种邻域结构，无论是微观拓扑还是宏观邻域，也无论是在整个搜索空间进行信息交流还是以空间的不同维分量为单位协作搜索，都不主动改变邻域状态，而只是在给定的邻域内进行学习交流，本文称之为PSO的被动局部模型。还有一类局部模型就是主动改变粒子邻域空间，避免碰撞和拥挤，本文称之为PSO的主动局部模型。Blackwell等人[3]将粒子分为自然粒子和带电粒子，当带电粒子过于接近时产生斥力，使之分开以提高粒子多样性；Løvbjerg等人为每个粒子引入与相邻粒子距离成反比的自组织危险度(self-organizedcriticality)指标，距离越近则12危险度越高，当达到一定阈值后，对该粒子进行重新初始化或推开一定距离降低危险度，达到提高群体多样性的目的；文献[15]提出一种带空间粒子扩展的PSO，为每个粒子赋一半径，以检测两个粒子是否会碰撞，并采取随机弹离、实际物理弹离、简单的速度—直线弹离等措施将其分开。3.3混合策略混合策略混合PSO就是将其它进化算法或传统优化算法或其它技术应用到PSO中，用于提高粒子多样性、增强粒子的全局探索能力，或者提高局部开发能力、增强收敛速度与精度。这种结合的途径通常有两种：一是利用其它优化技术自适应调整收缩因子/惯性权值、加速常数等；二是将PSO与其它进化算法操作算子或其它技术结合。文献[16]将蚂蚁算法与PSO结合用于求解离散优化问题；Robinson等人[17]和Juang[18]将GA与PSO结合分别用于天线优化设计和递归神经网络设计；文献[19]将种群动态划分成多个子种群，再对不同的子种群利用PSO或GA或爬山法进行独立进化；Naka等人[10]将GA中的选择操作引入到PSO中，按一定选择率复制较优个体；Angeline[11]则将锦标赛选择引入PSO算法，根据个体当前位置的适应度，将每一个个体与其它若干个个体相比较，然后依据比较结果对整个群体进行排序，用粒子群中最好一半的当前位置和速度替换最差一半的位置和速度，同时保留每个个体所记忆的个体最好位置；El-Dib等人[12]对粒子位置和速度进行交叉操作；Higashi[13]将高斯变异引入到PSO中；Miranda等人[14]则使用了变异、选择和繁殖多种操作同时自适应确定速度更新公式中的邻域最佳位置以及惯性权值和加速常数；Zhang等人[8]利用差分进化(DE)操作选择速度更新公式中的粒子最佳位置；而Kannan等人[18]则利用DE来优化PSO的惯性权值和加速常数。此外，其它一些搜索技术与PSO结合以提高算法的局部搜索能力，如文献[9]提出一种基于PSO和Levenberg-Marquardt的混合方法;文献[10]将PSO与单纯形法相结合；文献将PSO与序贯二次规划相结合；文献[12]将模拟退火与PSO结合；文献[13]将禁忌技术与PSO结合；文献[8]将爬山法与PSO结合；文献[15]将PSO与拟牛顿法结合。还有作者引入其它一些机制，以改进PSO的性能。文献[6]根据耗散结构的自组织性，提出一种耗散粒子群优化算法(dissipativePSO)。该算法通过附加噪声持续为粒子群引入负熵(negativeentropy)，使得系统处于远离平衡态的状态，又由于群体中存在内在的非线性相互作用，从而形成自组织耗散结构，使粒子群能够“持续进化”，抑制早熟停滞。文献[7]将自然进化过程中的群体灭绝现象引入PSO，在微粒的位置和速度更新之后，按照一个预先定义的灭绝间隔重新初始化所有微粒的13速度。文献[8]通过模拟自然界的被动聚集(PassiveCongregation)行为修改速度更新公式，实现种群内信息充分共享，防止了微粒因缺乏足够的信息而判断失误所导致陷入局部极小。文献[9]将引力场模型引入到PSO。此外，还有其它一些混合PSO：1）高斯PSO：由于传统PSO往往是在全局和局部最佳位置的中间进行搜索，搜索能力和收敛性能严重依赖加速常数和惯性权值的设置，为了克服该不足，Secrest等人[10]将高斯函数引入PSO算法中，用于引导粒子的运动；GPSO不再需要惯性权值，而加速常数由服从高斯分布的随机数产生。2）拉伸PSO(StretchingPSO,SPSO)：SPSO将所谓的拉伸技术(stretchingtechnique)[11]以及偏转和排斥技术应用到PSO中，对目标函数进行变换，限制粒子向已经发现的局部最小解运动，从而利于粒子有更多的机会找到全局最优解[4,6]。混沌粒子群优化：混沌是自然界一种看似杂乱、其实暗含内在规律性的常见非线性现象，具有随机性、遍历性和规律性特点。文献[3]利用混沌运动的遍历性以粒子群的历史最佳位置为基础产生混沌序列，并将此序列中的最优位置随机替代粒子群中的某个粒子的位置，提出混沌PSO(chaosparticleswarmoptimization,CPSO)。除此之外，文献[4]利用惯性权值自适应于目标函数值的自适应PSO进行全局搜索、利用混沌局部搜索对最佳位置进行局部搜索，提出一种PSO与混沌搜索相结合的混沌PSO；文献[15]则利用混沌序列确定PSO的参数(惯性权值和加速常数);文献[9]提出一种不含随机参数、基于确定性混沌Hopfield神经网络群的粒子群模型。3）免疫粒子群优化：生物免疫系统是一个高度鲁棒性、分布性、自适应性并具有强大识别能力、学习和记忆能力的非线性系统。文献[6]将免疫系统的免疫信息处理机制(抗体多样性、免疫记忆、免疫自我调节等)引入到PSO中，分别提出了基于疫苗接种的免疫PSO和基于免疫记忆的免疫PSO。4）量子粒子群优化：文献[9]采用量子个体提出离散PSO；文献[9]则基于量子行为更新粒子位置。5）卡尔曼PSO：文献[9]利用Kalman滤波更新粒子位置。主成分PSO：文献[10]结合主成分分析技术，粒子不仅按照传统算法在维的xn空间飞行，而且还在维的z空间同步飞行。m)(nm144.参数设置4.1对参数的仿真研究PSO的参数主要包括最大速度、两个加速常数和惯性常数或收缩因等。a)最大速度的选择：如式(2.1)所示的粒子速度是一个随机变量，由粒子位置更新公式(2.2)产生的运动轨迹是不可控的，使得粒子在问题空间循环跳动[3,6]。为了抑制这种无规律的跳动，速度往往被限制在内。增大，有利于maxmax,vvmaxv全局探索(globalexploration)；减小，则有利于局部开发(localexploitation)[3]。maxv但是过高，粒子运动轨迹可能失去规律性，甚至越过最优解所在区域，导致算maxv法难以收敛而陷入停滞状态；相反太小，粒子运动步长太短，算法可能陷入局maxv部极值[16]。的选择通常凭经验给定，并一般设定为问题空间的[3]。maxv%2010此外，文献[17]提出了的动态调节方法以改善算法性能；而文献[48]提出了自适maxv应于群体最佳和最差适应度值的选择方法。maxvb)加速常数的选择：式(1)中的加速常数和分别用于控制粒子指向自身或2c2c邻域最佳位置的运动。文献[20]建议，并通常取。0.421cc221ccRatnaweera等人[13]则提出自适应时变调整策略，即随着进化代数从2.5线性递减1c至0.5，随着进化代数从0.5线性递增至2.5。与传统PSO取正数加速常数不同，Riget2c和Vesterstrom[11]提出一种增加种群多样性的粒子群算法，根据群体多样性指标调整加速常数的正负号，动态地改变“吸引”(Attractive)和“扩散”(Repulsive)状态，以改善算法过早收敛问题。c)惯性权值或收缩因子的选择：当PSO的速度更新公式采用式(1)时，即使maxv和两个加速因子选择合适，粒子仍然可能飞出问题空间，甚至趋于无穷大，发生群体“爆炸(explosion)”现象[12]。有两种方法控制这种现象：惯性常数(inertiaconstant)[3]和收缩因子(constrictionfactor)[12]。带惯性常数PSO的速度更新公式如下：15（4.1））（）（txptrctxprctwvtvijijijijijij)(12211其中为惯性常数。文献[8]建议随着更新代数的增加从0.9线性递减至0.4。近来，文献[15]通过采用随机近似理论(stochasticapproximationtheory)分析PSO的动态行为，提出了一种随更新代数递减至0的取值策略，以提高算法的搜索能力。带收缩因子PSO由Clerc和Kennedy[12]提出，其最简单形式[20]的速度更新公式如下：（4.2））（）（txptrctxprctxvtvijijijijijij)(12211其中，；通常从而，4222x0.421cc1.4729.0x。49445.121cc11122{()(虽然惯性权值PSO和收缩因子PSO对典型测试函数表现出各自的优势[16]，但由于惯性常数方法通常采用惯性权值随更新代数增加而递减的策略，算法后期由于惯性权值过小，会失去探索新区域的能力，而收缩因子方法则不存在此不足[18]。4.2测试仿真函数例1.函数对于适应度函数fitness对其参数，，做出不同方1012)(iixxfw1c3c式的比较已测试其对函数结果影响。（1）当，，。22111cc5.12212cc2.1w当惯性权值不变的情况下对取不同的值1.5和2。21ccc程序（1）运行结果为：16图4.1粒子群位置初始化17图4.2粒子群速度初始化18图4.3迭代结果对比最优点坐标（1）：[0.4524297787188780.3206402722335760.521629692208334-0.037721251936116-0.587907547759961-0.1973278417335740.059472309970162-0.105031512919075-0.0601922850823510.840740574648050]最优点坐标（2）：[-0.295863893648182-0.2285647707143950.2444637647641200.475115714243873-0.330571564292149-0.153811057636018-0.262874734324870-0.134696331837768-0.2494665729826100.248526708588574]适应度值（1）为：1.690633278729210适应度值（2）为：0.769455496424646（2）当于对比（加速因子与正常情况22111cc2.1,2,02212wcc01c对比）且运行程序（2）得如下结果：19图4.4初始化速度20图4.5初始化速度21图4.6迭代结果对比最优点坐标（1）：[-0.3010825215869390.1301769032181110.149468203209848-0.002964214272033-0.101420705756867-0.123775878581260-0.8885734634490870.5052800930566710.707421391133458-0.243136586226299]最优点坐标（2）：[-0.541610401047606-0.107148776434457-0.0666708508191500.669477968063575-0.3491862818737420.6051846160962950.051863122302620-0.1010897103560640.4069777400183770.009764111144065]适应度值（1）为：1.759984065528661适应度值（2）为：1.424283049626009（3）当于对比（加速因子与2.1,22111wcc2.1,0,22212wcc02c正常情况对比）的结果为：22图4.7初始化位置23图4.8初速度位置24图4.9迭代结果对比最优点坐标（1）：[0.032596367547015-0.2534472340138280.220174027850755-0.184050929120391-0.0605262339435040.325089660099637-0.5051840513724270.0812617710854950.495050821497124-0.194148350056426]最优点坐标（2）：[-1.0999753001654430.2134718912296380.2308389883056510.620982109338000-0.0227591916135780.1361519821695030.5958364183180900.0595455559956470.132504460404116-0.344875728471985]适应度值（1）为：0.801579381651326适应度值（2）为：2.208540081759679（4）当，分别对其取值，，，。21cc21ww1.11c22c2.11w5.12w分析结果如下：25图4.10初始化位置26图4.11初始化速度27图4.12迭代结果对比最优点坐标（1）：[-0.0696191598414670.488557857942322-0.5878773688024220.577000714765126-0.255019353943860-0.326212573465861-0.630693562346744-0.3606521754196480.1049979808214610.624967732306244]最优坐标（2）：[0.360645808223021-0.4627131794648680.1721574459924160.1611652105173130.158416597461891-0.8055693450320970.640951653807223-0.3093217108105120.5192092190497600.010556466456078]适应度值（1）为：2.022968351158053适应度值（2）为：1.850007680165146（5）对，对分别取，对比其迭代影响221cc2.11w02w28图4.13初始化位置29图4.14初速度位置30图4.15迭代结果最优点坐标（1）：[0.1483329967286800.464843694691154-0.3795598378264700.6562683313167660.1040110571254700.550631814306402-0.069905771435114-0.607186822378544-0.0443851312618000.060375755047727最优坐标（2）：[-0.0784963116352740.0534506581067480.0409780143483050.0704479365658370.034324881708865-0.1897858788686860.032804423901163-0.0385802664597850.2212479508660890.061389486373012]适应度值（1）为：1.506027752348302适应度值（2）为：108141522528168（6）标准粒子群算法无参数对比，221cc2.1w31图4.16粒子群位置初始化32图4.17粒子群初始化速度33图4.18迭代结果在以上仿真中，我们5个实验实数的选择分别对，，不同情况做出对比1c2cw得出结论：惯性权重的不同取值对PSO的影响w试验表明权值将影响PSO的全局与局部搜优能力，值较大，全局搜优能ww力强，局部搜优能力弱;反之，则局部搜优能力增强，而全局搜优能力减弱。线性惯性权的引入使PSO可以调节算法的全局与局部搜优能力，但，还有两个缺点:其一，迭代初期局部搜索能力较弱，即使初始粒子已接近于全局最优点，也往往错过;其二，在迭代后期，则因全局搜索能力变弱，而易陷入局部极值。时，05.1w粒子群优化算法的搜索效率和搜索精度高。实验结果:按照方差分析选择适应的参数设置水平，能够获得稳健和高效的优化效果。4.3应用单因子方差分析参数对结果影响按照方差分析选择适应的参数设置水平，能够获得稳健和高效的优化效果。关键参数设置如下:粒子种群大小N:较小的群能充分探索解空间，避免了过多的适应值评估和计算时间。一般取[20-40]，对于大部分的问题，10个粒子已经足够取得好的结果，对于比较难的问题或者特定类别的问题，粒子数可以取到100，200。34粒子的长度(空间维数):这是由优化问题决定，就是问题解的长度。粒子的坐标D范围:由优化问题决定，每一维可以设定不同的范围。决定粒子在一个循环中maxv最大的移动距离，通常设为粒子的范围宽度。学习因子：和通常等于2，不1c2c过文献中也有其它的取值，一般，且范围在0和4之间。终止条件:按最大循21cc环数及最小偏差要求，这个终止条件由具体问题确定。例如，最小错误可以设定为1个错误分类，最大循环数设定为2000。惯性权值:控制着速度前一变化ww量对当前变化量的影响，如果较大，则影响较大，能够搜索以前所未能达到的w区域，整个算法的全局搜索能力加强，有利于跳出局部极小点；而值较小，则w前一动量项的影响较小，主要是在当前解的附近搜索，局部搜索能力较强，有利于算法收敛。研究表明，让惯性权值随着叠代次数的增加在1.4到0之间逐步减少可以取得较好的效果。4.4对参数的理论分析方差分析是分析试验数据的一种方法。利用此方法亦可分析算法中同一参数的不同水平或者不同参数的各个水平对算法性能影响的差异性，从而探究不同参数设置范围与算法系统性能之间的潜在关系。单因子方差分析是通过观察一个因子的量值变化，分析这个因子变化对整个试验的影响程度。利用这种方法可考查PSO中和这两个关键的参数因子各自对算法性能的影响。在试验中影响指标2c2c的因素称为因子，因子所处的状态，所取的等级称为因子水平。本文采取相等的试验次数进行方差分析。首先，假定因子有个水平，在每种水平下，做次Amk试验，在每次试验后可得一试验值，记做它表示在第个水平下的第个试验值ijxij;，如表1所示，在考察因子对试验结果的影响程度时，mi,,2,1kj,,2,1A把因子的个水平看成是个正态总体，因此可设AmmA,,,A,A21m，，。其中，，是因子的),(~2iijaNXmi,,2,1kj,,2,1iiaiA第水平所引起的差异。因此检验因子的各水平之间是否有显著的差异，相当iiAA于判断公式(4.2)：或(3)利用公式(4.1)2101Haa：0H2101m：35表述的平方和分解公式可将总的离差平方和进行分解，从而将因子水平不同而TS造成的结果差异与随机因素影响而造成的结果差异从量值上区分开来。，（4.3）ASeSSTmikjijxx112T)(S其中，mikjmiiijxxkxx11122)()(Se，，mikjijxx112)(Sekjijixkx11mikjijmiixmxmx11111总离差平方和是所有观察值与其总平均值之差的平方和，是描述全部TSijxx数据离散程度的数量指标。由于是服从正态分布的随机量，当公式(4.2)成立ijx时是独立同分布。同正态分布的随机变ijx量，则有公式(4.3)是服从的分布:1mkfT2x（4.4）2112T2)(Smikjiijxx是观察值与组内平均值之差的平方和，也就是组内平均和，它反映了Seijxix组内(同一水平下)样本的随机波动，其自由度为，是组内平均值与mmkfeix总平均值之差的平方和，即组间平方和。它在一定程度上反映了因子各个水平不同而引起的差异，其自由度为。平方和分解公式说明观察值关于其总平1mfA均值之的差异是由组内平方和组间平方和组成的。因此，公式(4.4)表示的和ASeS之间的比值F就是反映了两种差异所占的比重。36（4.5）)1(1kmSmSFeAF越大说明因子各水平不同引起的差异越显著，所以统计量可用来检验各因F子的影响效应。惯性权值、加速常数和的不同设置水平，每个设置水平进w1c2c行10次测试，通过单因子方差分析，说明不同参数水平对算法速率性能—迭代次数和算法优化性能———近似最优解的影响能力，能够获得比较一致的迭代次数均值，且在此范围内进行更细致的单因子方差分析进一步证明较小的惯性权值能够提高算法速率。在需要较高计算速率的应用中，可适当减小惯性权值。针对本程序（适应函数）令，1012)(iixxf122cc做单因子方差分析，判断因子对程序的影响。运4.1,2.1,8.0,4.04321wwww行程序（6），在此基础作5次试验的结果。第一组实验对应的迭代次数为43，适应值为0.04313373835813710.4w第一组实验对应的迭代次数为20，适应值为0.97844195585803110.8w第一组实验对应的迭代次数为9，适应值为1.70478036788648211.2w第一组实验对应的迭代次数为7，适应值为3.16543790083279011.4w第二组实验对应的迭代次数为45，适应值为0.11622358656896510.4w第二组实验对应的迭代次数为132，适应值为0.02479191087239210.8w第二组实验对应的迭代次数为8，适应值为1.43401435578352911.2w第二组实验对应的迭代次数为7，适应值为4.10930440631323311.4w第三组实验对应的迭代次数为47，适应值为0.02810186655278510.4w第三组实验对应的迭代次数为80，适应值为0.97844195585803110.8w37第三组实验对应的迭代次数为8，适应值为1.70478036788648211.2w第三组实验对应的迭代次数为9，适应值为4.10930440631323311.4w第四组实验对应的迭代次数为44，适应值为0.00420631434839010.4w第四组实验对应的迭代次数为85，适应值为0.00283337859758910.8w第四组实验对应的迭代次数为12，适应值为1.14771865060261811.2w第四组实验对应的迭代次数为9，适应值为1.22516117150981111.4w第五组实验对应的迭代次数为30，适应值为0.00295919953058510.4w第五组实验对应的迭代次数为120，适应值为0.00359362173235310.8w第五组实验对应的迭代次数为10，适应值为2.31908567597636011.2w第五组实验对应的迭代次数为25，适应值为0.57732268903171911.4w现在讨论单因子方差分析，设有4水平在水平A4321,,,AAAA)5,4,3,2,1(JAJ下进行5次试验，检验假设（）。05.043210:H不全相等。43211,,,:H解：现在，，。4s54321nnnn20n38水平