粒子群算法

粒子群算法智能优化计算1粒子群算法的基本原理1.1粒子群算法的提出1.2粒子群算法的原理描述2基本粒子群优化算法2.1基本粒子群算法描述2.2参数分析2.3与遗传算法的比较3改进粒子群优化算法3.1离散二进制PSO3.2惯性权重模型3.3收敛因子模型3.4研究现状智能优化计算4粒子群优化算法的应用4.1求解TSP问题4.2其它应用5群智能算法的特点与不足智能优化计算群智能智能优化计算群智能（SwarmIntelligence,SI）人们把群居昆虫的集体行为称作“群智能”（“群体智能”、“群集智能”、“集群智能”等）特点个体的行为很简单，但当它们一起协同工作时，却能够突现出非常复杂（智能）的行为特征。群智能的概念群智能智能优化计算描述群智能作为一种新兴的演化计算技术已成为研究焦点，它与人工生命，特别是进化策略以及遗传算法有着极为特殊的关系。特性指无智能的主体通过合作表现出智能行为的特性，在没有集中控制且不提供全局模型的前提下，为寻找复杂的分布式问题求解方案提供了基础。群智能算法群智能智能优化计算优点灵活性：群体可以适应随时变化的环境；稳健性：即使个体失败，整个群体仍能完成任务；自我组织：活动既不受中央控制，也不受局部监管。典型算法蚁群算法（蚂蚁觅食）粒子群算法（鸟群捕食）人工蜂群算法（蜜蜂采蜜）群智能算法智能优化计算由JamesKenney（社会心理学博士）和RussEberhart（电子工程学博士，~eberhart/）于1995年提出粒子群算法（ParticleSwarmOptimization,PSO）1粒子群算法的基本原理1.1粒子群算法的提出8五年后，在国际上逐步被接受，并有大批不同领域的学者投入该算法相关研究，目前已经成为智能优化领域研究的热门2003年，《控制与决策》第二期刊登国内第一篇PSO论文——综述文章智能优化计算1粒子群算法的基本原理1.1粒子群算法的提出92021/7/22历年发表论文的数目224121618491081003246431123143823280500100015002000250019951996199719981999200020012002200320042005200620072008系列1与微粒群优化相关论文的数目分布102021/7/22相关资源2001年,Kennedy等出版优秀著作《SwarmIntelligence》，对微粒群优化及其应用作了全面而系统的论述。专著1999年首届进化计算会议上微粒群优化算法即被定为会议讨论议题。IEEE群体智能研讨会GeneticandEvolutionaryComputation国际会议会议及其杂志网址，~hux/pso.shtml.EvolutionaryComputation(MITpress)IEEETransactionsonEvolutionaryComputationIEEETransactionsonNeuralNetworkIEEETransactionsonSystems,Man,andCyberneticsPart:A,BSwarmIntelligence智能优化计算源于对鸟群捕食行为的研究，是基于迭代的方法简单易于实现，需要调整的参数相对较少在函数优化、神经网络训练、工业系统优化和模糊系统控制等领域得到了广泛的应用。1粒子群算法的基本原理1.1粒子群算法的提出智能优化计算鸟群：假设一个区域，所有的鸟都不知道食物的位置，但是它们知道当前位置离食物还有多远。PSO算法每个解看作一只鸟，称为“粒子(particle)”，所有的粒子都有一个适应值，每个粒子都有一个速度决定它们的飞翔方向和距离，粒子们追随当前最优粒子在解空间中搜索。1粒子群算法的基本原理1.2粒子群算法的原理描述132021/7/22单个鸟整个鸟群鸟群寻找食物的飞行策略单个微粒由多个微粒组成的微粒群微粒位置和速度的更新策略PSO鸟群行为最大化问题一个微粒代表问题的一个解每个微粒都有一个由被优化函数值决定的适应值每个微粒通过跟踪自身找到的最好位置以及邻域内其它微粒找到的最好位置，完成对整个搜索空间的搜索PSO就是对鸟群或鱼群寻找食物这种群体行为的模拟。智能优化计算PSO算法初始化为一群随机粒子，通过迭代找到最优。每次迭代中，粒子通过跟踪“个体极值（pbest）”和“全局极值(gbest)”来更新自己的位置。1粒子群算法的基本原理1.2粒子群算法的原理描述智能优化计算粒子速度和位置的更新假设在D维搜索空间中，有m个粒子；其中第i个粒子的位置为矢量其飞翔速度也是一个矢量，记为第i个粒子搜索到的最优位置为整个粒子群搜索到的最优位置为第i个粒子的位置和速度更新为：Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid,,2,1;,,2,1)()()()(112112基本粒子群优化算法),,,(21iDiiipppp2.1基本粒子群算法描述),,,(21gbestDgbestgbestgbestpppp),,,(21iDiiixxxx),,,(21iDiiivvvv智能优化计算粒子速度和位置的更新其中，w称为惯性权重，c1和c2为两个正常数，称为加速因子。将vidk限制在一个最大速度vmax内。Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid,,2,1;,,2,1)()()()(112112基本粒子群优化算法2.1基本粒子群算法描述xkvkppgbestxk+1vk+1kkk+1k+1智能优化计算粒子速度和位置的更新Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid,,2,1;,,2,1)()()()(112112基本粒子群优化算法2.1基本粒子群算法描述“惯性部分”，对自身运动状态的信任“认知部分”，对微粒本身的思考，即来源于自己经验的部分“社会部分”，微粒间的信息共享，来源于群体中的其它优秀微粒的经验智能优化计算迭代过程2基本粒子群优化算法2.1基本粒子群算法描述智能优化计算算法流程2基本粒子群优化算法StartInitializeparticleswithrandompositionandvelocityvectors.Foreachparticle’sposition(xi)evaluatefitnessIffitness(xi)betterthanfitness(p)thenp=xiLoopuntilallparticlesexhaustSetbestofpsasgBestUpdateparticlesvelocityandpositionLoopuntilmaxiterStop:givinggBest,optimalsolution.2.1基本粒子群算法描述智能优化计算惯性权重w使粒子保持运动惯性，使其有扩展搜索空间的趋势，有能力探索新的区域。表示微粒对当前自身运动状态的信任，依据自身的速度进行惯性运动。较大的w有利于跳出局部极值，而较小的w有利于算法收敛。2基本粒子群优化算法2.2参数分析Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid,,2,1;,,2,1)()()()(11211212021/7/22惯性权重(续)通过调节w值，可以控制PSO的全局探索和局部开发能力：•w≥1：微粒速度随迭代次数的增加而增加，微粒发散。•0w1：微粒减速，算法的收敛性依靠惯性权重和。•w0：微粒速度随迭代次数的增加而减小，最后趋近0，算法收敛。1c2c实验表明，w=0.7298和时算法具有较好的收敛性能。121.497cc•Eberhart和Shi：w的线性递减策略；•陈贵敏等：开口向下抛物线、开口向上抛物线和指数曲线等3种非线性权值递减策略；•Shi和Eberhart：以当前惯性权重值和当前算法最优值为模糊系统的输入，给出一种惯性权重的模糊控制方法。自适应或动态惯性权重值：222021/7/22惯性权重(续)ixipgpiv22()gicrpxiwv11()iicrpxgipxiipx智能优化计算加速常数c1和c2代表将微粒推向pbest和gbest位置的统计加速项的权重。表示粒子的动作来源于自己经验的部分和其它粒子经验的部分。低的值允许粒子在被拉回之前可以在目标区域外徘徊，而高的值则导致粒子突然冲向或越过目标区域。2基本粒子群优化算法2.2参数分析Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid,,2,1;,,2,1)()()()(11211242021/7/22加速度系数(Accelerationcoefficients)1212(1)()(()())(()())(2a)(1)()(1)(2b)ijijijijgjijijijijvtwvtrptxtrptxtxtxtvtcc：两个加速度系数，又称学习因子，用来控制和对微粒飞行方向的影响。ipgp21,cc120,0:cc每个微粒执行局部搜索；120,0:cc微粒群转化为一个随机爬山法；120:cc微粒逐渐移向和的加权均值；gpip21:cc算法比较适合于单峰优化问题；12:cc算法比较适合于多峰优化问题。252021/7/22自适应或动态加速度系数：1111max2222max(),().fiifiitccccTtccccT11220.5,2.5;2.5,0.5.fificccc实验建议：Ratnaweera等：基于迭代次数对两个加速度系数进行动态调节，其中，随进化代数增加而减小；相反，随进化代数增加而增大。1c2c智能优化计算加速常数c1和c2将c1和c2统一为一个控制参数，φ=c1+c2如果φ很小，微粒群运动轨迹将非常缓慢；如果φ很大，则微粒位置变化非常快；实验表明，当φ=4.1（通常c1=2.0，c2=2.0）时，具有很好的收敛效果。2基本粒子群优化算法2.2参数分析智能优化计算粒子数一般取20～40，对较难或特定类别的问题可以取100～200。最大速度vmax决定粒子在一个循环中最大的移动距离，通常设定为粒子的范围宽度。终止条件最大循环数以及最小错误要求。2基本粒子群优化算法2.2参数分析智能优化计算共性（1）都属于仿生算法；（2）都属于全局优化方法；（3）都属于随机搜索算法；（4）都隐含并行性；（5）根据个体的适配信息进行搜索，因此不受函数约束条件的限制，如连续性、可导性等；（6）对高维复杂问题，往往会遇到早熟收敛和收敛性能差的缺点，都无法保证收敛到最优点。2基本粒子群优化算法2.3与遗传算法的比较智能优化计算差异（1）PSO有记忆，所有粒子都保存较优解的知识，而GA，以前的知识随着种群的改变被改变；（2）PSO中的粒子是一种单向共享信息机制。而GA中的染色体之间相互共享信息，使得整个种群都向最优区域移动；（3）GA需要编码和遗传操作，而PSO没有交叉和变异操作，粒子只是通过内部速度进行更新，因此原理更简单、参数更少、实现更容易。2基本粒子群优化算法2.3与遗传算法的比较智能优化计算用途基本PSO是用来解决连续问题优化的，离散二进制PSO用来解决组合优化问题。运动方程不同粒子的位置只有(0,1)两种状态。速度值越大，则粒子位置取1的可能性越大，反之越小。3改进粒子群优化算法3.1离散二进制PSO维分量。的第是随机矢量dρvvSxelsexthenvSρ