粒子群算法

ParticleSwarmOptimization2011/03粒子群算法IntroductionDiscoveryofParticleSwarmOptimization(PSO)PSO概述PSO算法PSO算法实例与应用OutlineParticleSwarmOptimization03//08AIcourseSwarmIntelligenceParticleSwarmOptimization向大自然学习遗传算法(GA)物竞天择，设计染色体编码，根据适应值函数进行染色体选择、交叉和变异操作，优化求解人工神经网络算法(ANN)模仿生物神经元，透过神经元的信息传递、训练学习、联想，优化求解模拟退火算法(SA)模模仿金属物质退火过程03//08AIcourseAI发展史ParticleSwarmOptimizationGeneticAlgorithmTabuSearch195319911975AntsSystemParticleSwarmOptimization1995SwarmIntelligence1989SimulatedAnnealing1969ExpertSystem03//08AIcourse最优化算法ParticleSwarmOptimization解决最优化问题的方法传统搜索方法保证能找到最优解HeuristicSearch不能保证找到最优解03//08AIcourseCooperationexampleParticleSwarmOptimization03/08AIcourseDiscoveryofParticleSwarmOptimization探索粒子群优化算法Inventor(1)[e-mail]03//08AIcourseInventor(2)[e-mail]03/08AIcoursePSO概述ParticleSwarmOptimization起源生物学家对鸟(鱼)群捕食的行为研究社会行为(Social-OnlyModel)个体认知(Cognition-OnlyModel)03/08AIcourse鸟群(鱼群)行为ParticleSwarmOptimization03/08AIcourse鸟群(鱼群)行为ParticleSwarmOptimization粒子群特性03/08AIcoursePSO概述ParticleSwarmOptimization每个寻优的问题解都被想象成一只鸟(鱼)，称为Particle每个Particle都有记忆能力所有的Particle都通过FitnessFunction来判断目前的位置之好坏每个Particle通过VelocityFunction来决定移动的距离与方向03/08AIcoursePSO算法流程ParticleSwarmOptimizationInitializeEvaluationFindthePbestFindtheGbestUpdatethePosition回到Evaluation继续执行，直到符合终止条件为止03/08AIcoursePSO算法流程ParticleSwarmOptimizationInitial将群族初始化，以随机的方式求出每一Particle之初始位置与速度03/08AIcoursePSO算法流程ParticleSwarmOptimizationEvaluation根据FitnessFunction计算出其FitnessValue以作为判断每一Particle之好坏22100100iiiMinimizeftxtyt22100100iiiMaximizeftxtyt03/08AIcoursePSO演算法流程ParticleSwarmOptimizationFindthePbest找出每个Particle到目前为止的搜寻过程中最优解，这个最优解我们称为PbestPastBestSolution03/08AIcoursePSO算法流程ParticleSwarmOptimizationFindtheGbest找出所有Particle到目前为止所搜寻到的全体最优解，此最优解我们称之为GbestGlobalBestSolutionPastBestSolution03/08AIcoursePSO算法流程ParticleSwarmOptimizationUpdatethePosition根据VelocityFunction更新每个Particle的移动方向与速度回到Evaluation继续执行，直到符合终止条件为止03/08AIcoursePSO流程图ParticleSwarmOptimization开始设定参数产生初始族群计算适应度更新速度和位置产生新族群满足停止条件结束NoYes03/08AIcoursePSOVelocityFunctionParticleSwarmOptimizationCognition-OnlyModelPSOVelocityFunctionSocial-OnlyModel||+03/08AIcoursePSOVelocityFunctionParticleSwarmOptimizationCognition-OnlyModel1()ididididVVCrandPXtVid：第i个particle(有d个维度)的速度Pid：每个particle到目前为止所出现的最佳位置Xid：每个particle目前的所在位置C1：学习常数rand()：0~1之間的随机数03/08AIcoursePSOVelocityFunctionParticleSwarmOptimizationSocial-OnlyModel2()ididgdidVVCrandPXtVid：第i个particle(有d个维度)的速度Pgd：所有particle到目前为止所出现的最佳位置Xid：每个particle目前的所在位置C2：学习常数rand()：0~1之间的随机数03/08AIcoursePSOVelocityFunctionParticleSwarmOptimizationPSOVelocityFunction12()()ididididgdidVwVCrandPXtCrandPXtVid：第i个particle(有d个维度)的速度Pid：每个particle到目前为止所出现的最佳位置Pgd：所有particle到目前为止所出现的最佳位置Xid：每个particle目前的所在位置C1,C2：学习常数w：惯性权重rand()：0~1之间的随机数03/08AIcourse區域最佳解全域最佳解運動向量慣性向量PSOVelocityFunctionParticleSwarmOptimization12X=X,X,...,Xiiiid12V=V,V,...,Viiiid动能向量理论StudyFactor12(1)()()()()()()()ididididgdidttttvwvcrandpxcrandpx(1)()()iiitttxxvHereIam!ThebestpositionofteamMybestpositionxpgpiv03/08AIcoursePSOPseudoCodeParticleSwarmOptimizationI)Foreachparticle:InitializeparticleII)Do:a)Foreachparticle:1)Calculatefitnessvalue2)Ifthefitnessvalueisbetterthanthebestfitnessvalue(Pbest)inhistory3)SetcurrentvalueasthenewPbestEndb)Foreachparticle:1)Findintheparticleneighborhood,theparticlewiththebestfitness2)Calculateparticlevelocityaccordingtothevelocityfunction3)UpdateparticlepositionaccordingtothepositionfunctionEndWhilemaximumiterationsorminimumerrorcriteriaisnotattained03/08AIcourse粒子群最优化ParticleSwarmOptimizationx,y,zallocation,,Maxfxyzxzy123123123,,23fxyzxyzf(3,3,1)=14f(2,1,2)=7f(1,3,3)=8解集合坐标系表示法03/08AIcourse2维例子粒子群最优化ParticleSwarmOptimizationNote合理解集合目前最优解个体最优解全域区域03/08AIcoursePSO举例ParticleSwarmOptimization03/08AIcoursePSO举例ParticleSwarmOptimizationGriewankRastriginRosenbrock03/08AIcoursePSO举例（见程序演示）ParticleSwarmOptimization30DfunctionPSOEvolutionaryalgo.Griewank0.0039440.4033Rastrigin82.9561846.4689Rosenbrock50.1938771610.359Bestresultafter40000evaluationsOptimum=0,Dimension=3003/08AIcourse粒子群算法的改进ParticleSwarmOptimization03/08AIcourse1997年Kennedy和Eberhart提出了二进制PSO算法1998年Shi和Eberhart引入了惯性权重w，并提出动态调整惯性权重以平衡收敛的全局性和收敛速度，该算法被称为标准PSO算法1999年Clerc引入收缩因子以保证算法的收敛性1999年Angeline将进化计算中的选择概念引入到PSO算法中Lovbjerg等人将进化计算中的复制、交叉等机制应用于PSO算法1999年Suganthan在标准PSO算法中引入了空间邻域的概念，将处于同一个空间领域的粒子构成一个子粒子群分别进行进化，并随着进化动态地改变选择阈值以保证群体的多样性1999年Kennedy引入邻域拓扑的概念来调整邻域的动态选择，并引入社会信念将空间邻域与邻域拓扑中地环拓扑相结合以增加邻域间地信息交流，提高群体的多样性2001年Lovbjerg等人将遗传算法中的子群体概念引入PSO算法中，同时引入繁殖算子以进行子群体的信息交流粒子群算法的改进ParticleSwarmOptimization03/08AIcourse主要改进方面对基本粒子群算法更新公式的改进基于遗传思想对粒子群算法的改进利用小生境思想对粒子群算法的改进对基本粒子群算法更新公式的改进ParticleSwarmOptimization03/08AIcourse带有惯性权重的改进惯性权重设计当w＝1时，公式与前面相同，从而表明带惯性权重的粒子群算法是基本粒子群算法的扩展。建议w的取值范围为[0，1.4]，但实验结果表明当w取[0.8，1.2]时，算法收敛速度更快，而当w1.2时，算法则较多地陷入局部极值。线性惯性权重法(MaxNumbe