第6章-粒子群优化算法

第6章粒子群优化算法Contents算法简介1基本流程2改进研究3相关应用4参数设置526.1粒子群优化算法简介粒子群优化算法是什么？粒子群优化算法（ParticleSwarmOptimization，PSO）是进化计算的一个分支，是一种模拟自然界的生物活动的随机搜索算法。粒子群优化算法的思想来源是怎样的？它由谁提出的？PSO模拟了自然界鸟群捕食和鱼群捕食的过程。通过群体中的协作寻找到问题的全局最优解。它是1995年由美国学者Eberhart和Kennedy提出的，现在已经广泛应用于各种工程领域的优化问题之中。36.1.1思想来源生物界现象群体行为群体迁徙生物觅食……社会心理学群体智慧个体认知社会影响……粒子群优化算法人工生命鸟群觅食鱼群学习群理论46.1.2基本原理鸟群觅食现象•鸟群•觅食空间•飞行速度•所在位置•个体认知与群体协作•找到食物粒子群优化算法•搜索空间的一组有效解•问题的搜索空间•解的速度向量•解的位置向量•速度与位置的更新•找到全局最优解鸟群觅食现象粒子群优化算法类比关系56.1.2基本原理鸟群觅食现象粒子群优化算法66.2粒子群优化算法的基本流程基本流程速度与位置更新公式速度与位置更新示意图算法流程图和伪代码应用举例函数最小化问题算法的执行步骤示意图7粒子的个体速度与位置更新公式更新速度自身速度个体认知社会引导1122()()ddddddddiiiiivvcrpBestxcrgBestxdddiiixxv8速度与位置更新示意图x1x2P1P2P3gBest9速度与位置更新示意图x2x1P3P1P2PB210速度与位置更新示意图x2P1P3x1P2经过若干次迭代之后11PSO算法流程图和伪代码开始随机初始化每个粒子评估每个粒子并得到全局最优更新每个粒子的速度和位置评估每个粒子的函数适应值结束否是满足结束条件更新群体的全局最优位置更新每个粒子历史最优位置//功能：粒子群优化算法伪代码//说明：本例以求问题最小值为目标//参数：N为群体规模procedurePSOforeachparticleiInitializevelocityViandpositionXiforparticleiEvaluateparticleiandsetpBesti=XiendforgBest=min{pBesti}whilenotstopfori=1toNUpdatethevelocityandpositionofparticleiEvaluateparticleiiffit(Xi)fit(pBesti)pBesti=Xi;iffit(pBesti)fit(gBest)gBest=pBesti;endforendwhileprintgBestendprocedure126.2.2应用举例例6.1已知函数，其中，用粒子群优化算法求解y的最小值。221212(,)yfxxxx1210,10xx13运行步骤221118(5)642589(8,5)fpBestx22222(5)92581106(5,9)fpBestx22333(7)(8)4964113(7,8)fpBestx1(8,5)gBestpBest步骤1：初始化。假设种群大小是N=3；在搜索空间中随机初始化每个解的速度和位置，计算适应函数值，并且得到粒子的历史最优位置和群体的全局最优位置。)8,7()3,5(333xvp)9,5()2,3(222xvp)5,8()2,3(111xvp步骤2：粒子的速度和位置更新。根据自身的历史最优位置和全局的最优位置，更新每个粒子的速度和位置。w是惯量权重，一般取[0,1]区间的数，这里假设为0.5c1和c2为加速系数，通常取固定值2.0r1和r2是[0,1]区间的随机数对于越界的位置，需要进行合法性调整注意！)4,5.9()1,5.1()5,8()1,5.1(10025.05.10035.0)()(11111221111111vxxvxgBestrcxpBestrcvvp)10,1.1()8.10,1.1()8.1,1.6()9,5()8.1,1.6(8.1)9)5((1.020)2(5.01.6))5(8(3.020)3(5.0)()(11122222211222vxxvxgBestrcxpBestrcvvp)7.1,5.3()3.6,5.3()8,7()3.6,5.3(3.6))8()5((8.02035.05.3))7(8(05.02055.0)()(11133223311333vxxvxgBestrcxpBestrcvvp步骤4：如果满足结束条件，则输出全局最优结果并结束程序，否则，转向步骤2继续执行。步骤3：评估粒子的适应度函数值。更新粒子的历史最优位置和全局的最优位置。*22119.5(4)90.2516106.2589ff*22221.1101.21100101.21106ff*2233(3.5)(1.7)12.252.8915.14113ff*2222101.21(1.1,10)ffXpBest*333315.14(3.5,1.7)ffpBestx3(3.5,1.7)gBestpBest1189(8,5)fpBest＝14221118(5)642589(8,5)fpBestx22222(5)92581106(5,9)fpBestx22333(7)(8)4964113(7,8)fpBestx1(8,5)gBestpBest步骤1：初始化。假设种群大小是N=3；在搜索空间中随机初始化每个解的速度和位置，计算适应函数值，并且得到粒子的历史最优位置和群体的全局最优位置。步骤2：粒子的速度和位置更新。根据自身的历史最优位置和全局的最优位置，更新每个粒子的速度和位置。w是惯量权重，一般取[0,1]区间的数，这里假设为0.5c1和c2为加速系数，通常取固定值2.0r1和r2是[0,1]区间的随机数步骤3：评估粒子的适应度函数值。更新粒子的历史最优位置和全局的最优位置。*22119.5(4)90.2516106.2589ff*22221.1101.21100101.21106ff*2233(3.5)(1.7)12.252.8915.14113ff*2222101.21(1.1,10)ffXpBest*333315.14(3.5,1.7)ffpBestx3(3.5,1.7)gBestpBest1189(8,5)fpBest＝步骤4：如果满足结束条件，则输出全局最优结果并结束程序，否则，转向步骤2继续执行。对于越界的位置，需要进行合法性调整注意！)4,5.9()1,5.1()5,8()1,5.1(10025.05.10035.0)()(11111221111111vxxvxgBestrcxpBestrcvvp)10,1.1()8.10,1.1()8.1,1.6()9,5()8.1,1.6(8.1)9)5((1.020)2(5.01.6))5(8(3.020)3(5.0)()(11122222211222vxxvxgBestrcxpBestrcvvp)7.1,5.3()3.6,5.3()8,7()3.6,5.3(3.6))8()5((8.02035.05.3))7(8(05.02055.0)()(11133223311333vxxvxgBestrcxpBestrcvvp)8,7()3,5(333xvp)9,5()2,3(222xvp)5,8()2,3(111xvp156.3粒子群优化算法的改进研究PSO研究热点与方向算法理论研究混合算法研究算法参数研究拓扑结构研究算法应用研究16与PSO相关的重要学术期刊与国际会议重要学术期刊IEEETransactionsonEvolutionaryComputationIEEETransactionsonSystems,ManandCyberneticsIEEETransactionson……MachineLearningEvolutionaryComputation……17与PSO相关的重要学术期刊与国际会议重要国际会议IEEECongressonEvolutionaryComputation(CEC)IEEEInternationalConferenceonSystems,Man,andCybernetics(SMC)ACMGeneticandEvolutionaryComputationConference(GECCO)InternationalConferenceonAntColonyOptimizationandSwarmIntelligence(ANTS)InternationalConferenceonSimulatedEvolutionAndLearning(SEAL)……186.3.1理论研究改进2006Kadirkamanathan等人2006年在动态环境中对PSO的行为进行研究，由静态分析深入到了动态分析2003Trelea2003年指出PSO最终最终稳定地收敛于空间中的某一个点，但不能保证是全局最优点2002Clerc&Kennedy2002年设计了一个称为压缩因子的参数。在使用了此参数之后，PSO能够更快地收敛2006F.vandenBergh等人2006年对PSO的飞行轨迹进行了跟踪，深入到了动态的系统分析和收敛性研究196.3.2拓扑结构改进静态拓扑结构全局版本：星型结构局部版本：环形结构齿形结构金字塔结构冯诺依曼结构……动态拓扑结构逐步增长法Suganthan1999最小距离法Hu&Eberhart2002重新组合法Liang&Suganthan2005随机选择法Kennedy等人2006……其它拓扑结构社会趋同法Kennedy2000FullyInformedMendes等人2004广泛学习策略Liang等人2006……20几种典型的拓扑结构示意图(a)星型结构(b)环型结构(c)齿型结构(d)冯诺依曼结构全局版本PSO和局部版本PSO在收敛特点：1.GPSO由于其很高的连接度，往往具有比LPSO更快的收敛速度。但是，快速的收敛也让GPSO付出了多样性迅速降低的代价2.LPSO由于具有更好的多样性，因此一般不容易落入局部最优，在处理多峰问题上具有更好的性能在解决具体问题的时候，可以遵循以下一些规律：(A)邻域较小的拓扑结构在处理复杂的、多峰值的问题上具有优势，例如环型结构的LPSO(B)随着邻域的扩大，算法的收敛速度将会加快，这对简单的、单峰值的问题非常的有利，例如GPSO在这些问题上就表现很好216.3.3混合算法改进混合其它技术的改进单纯形技术函数延伸技术混沌技术量子技术协同技术小生境技术物种形成技术……混合其它搜索算法的改进结合模拟退火算法结合人工免疫算法结合差分进化算法