第7章粒子群算法

1、1（Particle Swarm Optimization，PSO）7 粒子群算法粒子群算法2一、背景介绍一、背景介绍问题的提出：问题的提出：3一、背景介绍一、背景介绍思想来源：思想来源：粒子群优化算法粒子群优化算法1987年，年，Reynolds实现了鸟群运动的计实现了鸟群运动的计算机可视化仿真。算机可视化仿真。1990年，动物学家年，动物学家Heppner和和Grenander对动物对动物群体活动规律进行群体活动规律进行研究。研究。Wilson在在20世纪世纪70年代指出：年代指出：“至少在理论上群至少在理论上群体觅食的过程中，群体中的每一个个体都会收益体觅食的过程中，群体中的每一个个体都

2、会收益于所有成员在这个过程中的所发现和累积的经于所有成员在这个过程中的所发现和累积的经验。验。”1995年，年，Eberhart和和Kennedy提提出了粒子群优化算法出了粒子群优化算法4一、背景介绍一、背景介绍算法思路：算法思路： 源于对鸟群捕食的行为研究。粒子群优化算法的基本思想是通过群体中源于对鸟群捕食的行为研究。粒子群优化算法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解。个体之间的协作和信息共享来寻找最优解。 我们可以设想这样的一个场景，一群鸟再随机搜寻食物。这个区域里只我们可以设想这样的一个场景，一群鸟再随机搜寻食物。这个区域里只有一块食物。所有的鸟都不知道食物再哪里，

3、但他们知道目前距离食物还有有一块食物。所有的鸟都不知道食物再哪里，但他们知道目前距离食物还有多远，那么找到食物的最佳策略是什么？多远，那么找到食物的最佳策略是什么？ 1、找寻距离食物最近的鸟之周围区域、找寻距离食物最近的鸟之周围区域 2、根据自己本身飞行的经验判断食物的所在、根据自己本身飞行的经验判断食物的所在 PSO算法就从这种生物种群行为特性中得到启发并用于求解优化问题。算法就从这种生物种群行为特性中得到启发并用于求解优化问题。在在PSO中，每个优化问题的潜在解都可以想象成中，每个优化问题的潜在解都可以想象成d维搜索空间上的一个点，我维搜索空间上的一个点，我们称之为们称之为“粒子粒子”（P

4、article），所有的粒子都有一个被目标函数决定的适应），所有的粒子都有一个被目标函数决定的适应值，每个粒子还有一个速度决定他们飞翔的方向和距离，然后粒子们就追随值，每个粒子还有一个速度决定他们飞翔的方向和距离，然后粒子们就追随当前的最优粒子在解空间中搜索。对鸟群飞行的研究发现。鸟仅仅是追踪它当前的最优粒子在解空间中搜索。对鸟群飞行的研究发现。鸟仅仅是追踪它有限数量的邻居但最终的整体结果是整个鸟群好像在一个中心的控制之下有限数量的邻居但最终的整体结果是整个鸟群好像在一个中心的控制之下.即即复杂的全局行为是由简单规则的相互作用引起的。复杂的全局行为是由简单规则的相互作用引起的。5二、算法介绍二

5、、算法介绍抽象：抽象： 鸟被抽象为没有质量和体积的微粒鸟被抽象为没有质量和体积的微粒( (点点) )，并延伸到，并延伸到N N维空间，粒子维空间，粒子i i在在N N维空间的位置表示为矢量：维空间的位置表示为矢量： Xi Xi= =（x x1 1，x x2 2，x xN N），），飞行速度表示为矢量：飞行速度表示为矢量： Vi Vi= =（v v1 1，v v2 2，v vN N）每个粒子都有一个由目标函数决定的每个粒子都有一个由目标函数决定的适应值适应值，并且知道，并且知道自己到目前为止的最好位置自己到目前为止的最好位置(pbest)(pbest)和和现在的位置现在的位置XiXi这这个可以看

6、作是粒子自己的飞行经验。除此之外，每个粒个可以看作是粒子自己的飞行经验。除此之外，每个粒子还知道子还知道到目前为止整个群体中所有粒子发现的最好位到目前为止整个群体中所有粒子发现的最好位置置(gbest)(gbest) (gbest (gbest是是pbestpbest中的最好值中的最好值) )这个可以看作这个可以看作是粒子同伴的经验。粒子就是通过自己的经验和同伴中是粒子同伴的经验。粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。最好的经验来决定下一步的运动。6二、算法介绍二、算法介绍PSOPSO初始化为一群随机粒子初始化为一群随机粒子( (随机解随机解) )。然后通过迭代找到最。然

7、后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个优解。在每一次的迭代中，粒子通过跟踪两个“极值极值”(pbes(pbest ,gbest)t ,gbest)来更新自己。来更新自己。在找到这两个最优值后，粒子通过下面的公式来更新自己在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。的速度和位置。7二、算法介绍二、算法介绍Vi 是粒子的速度；是粒子的速度；rand()是介于（是介于（0、1）之间的随机数；）之间的随机数；xi 是粒子的当前位置；是粒子的当前位置；c1和和c2是学习因子，通常取是学习因子，通常取c1 c22；在每一维，粒子都有一个最大限制速度在每一维，粒子都有一

8、个最大限制速度Vmax，如果某一，如果某一维的速度超过设定的维的速度超过设定的Vmax ，那么这一维的速度就被限定，那么这一维的速度就被限定为为Vmax 。（。（ Vmax 0）12() ()() ()iiiiiiVVcrandpbestxcrandgbestxiiixxV(1)(1)(2)(2)i i1 1，2 2，M M。M M是该群体中粒子的总数是该群体中粒子的总数 8二、算法介绍二、算法介绍12() ()() ()iiiiiiVVcrandpbestxcrandgbestx9n 粒子群原理示意图粒子群原理示意图该粒子以前最优位置全局最优粒子当前飞行行为受以前最优位置影响受上一次飞行行为

9、影响受全局最优粒子影响新的飞行食物源10二、算法介绍二、算法介绍12() ()() ()iiiiiiVVcrandpbestxcrandgbestx其中其中非负，称为惯性因子。非负，称为惯性因子。公式公式(2)和和(3)被视为被视为标准标准PSO算法算法。iiixxV(2)(2)（3 3）11二、算法介绍二、算法介绍值较大，全局寻优能力强，局部寻优能力弱；值较大，全局寻优能力强，局部寻优能力弱；值较值较小反之。小反之。 初始时，将初始时，将 取为常数，后来实验发现，动态取为常数，后来实验发现，动态 能够能够获得比固定值更好的寻优结果。动态获得比固定值更好的寻优结果。动态 可以在可以在PSO搜索

10、过程搜索过程中线性变化，也可根据中线性变化，也可根据PSO性能的某个测度函数动态改变。性能的某个测度函数动态改变。 目前，采用较多的是目前，采用较多的是线性递减权值线性递减权值(linearly decreasing weight, LDW)策略。策略。在（在（3 3）式中）式中12() ()() ()iiiiiiVVcrandpbestxcrandgbestx12二、算法介绍二、算法介绍线性递减权值线性递减权值(LDW)( )()()/tiniendkkendGgGG Gk k为最大迭代数，为最大迭代数， g g为当前迭代数，为当前迭代数，iniini为初始惯为初始惯性权值，性权值， end

11、end为迭代至最大数时惯性权值。为迭代至最大数时惯性权值。典型取值典型取值: : ini 0.90.9，endend0.40.4。 的引入使的引入使PSOPSO算法性能有了很大提高，针对不同算法性能有了很大提高，针对不同的搜索问题，可以调整全局和局部搜索能力，也使得的搜索问题，可以调整全局和局部搜索能力，也使得PSPSO O算法能成功的应用于很多实际问题。算法能成功的应用于很多实际问题。（4）13二、算法介绍二、算法介绍算法流程：算法流程：Step1：初始化一群微粒：初始化一群微粒(群体规模为群体规模为M)，包括随机位置和速度；，包括随机位置和速度；Step2：评价每个微粒的适应度；：评价每个

12、微粒的适应度；Step3：对每个微粒，将其适应值与：对每个微粒，将其适应值与其经过的最好位置其经过的最好位置pbest作比较，如作比较，如果较好，则将其作为当前的最好位置果较好，则将其作为当前的最好位置pbest;Step4：对每个微粒，将其适应值与：对每个微粒，将其适应值与其他粒子经过的最好位置其他粒子经过的最好位置gbest作比作比较，如果较好，则将其作为当前的最较，如果较好，则将其作为当前的最好位置好位置gbest;Step5：根据：根据(2)、(3)式调整微粒速度式调整微粒速度和位置；和位置；Step6：未达到结束条件则转：未达到结束条件则转Step2。开始开始初始化粒子群初始化粒子群

13、计算每个粒子的适应度计算每个粒子的适应度根据粒子的适应度更新根据粒子的适应度更新pbest和和gbest根据公式（根据公式（2），（），（3）更新粒子群的速度和位置更新粒子群的速度和位置达到最大迭代次数达到最大迭代次数或满足最小错误标准或满足最小错误标准结束结束YESNO14二、算法介绍二、算法介绍局部和全局最优算法局部和全局最优算法方程方程(2)和和(3)中中pbest和和gbest分别表示微粒群的局部和分别表示微粒群的局部和全局最优位置，当全局最优位置，当C10时，则粒子没有了认知能力，变为时，则粒子没有了认知能力，变为只有社会的模型只有社会的模型(social-only):2() ()i

14、iiiVVcrandgbestx被称为被称为全局全局PSO算法算法.粒子有扩展搜索空间能力，具有较快粒子有扩展搜索空间能力，具有较快收敛速度，由于缺少局部搜索，对于复杂问题比标准收敛速度，由于缺少局部搜索，对于复杂问题比标准PSO 更易陷入局部最优。更易陷入局部最优。（1）全局算法）全局算法15二、算法介绍二、算法介绍（2）局部算法）局部算法 当当C20时，则粒子之间没有社会信息，模型变为只时，则粒子之间没有社会信息，模型变为只有认知有认知(cognition-only)模型：模型：被称为被称为局部局部PSO算法算法。由于个体之间没有信息的交流，整。由于个体之间没有信息的交流，整个群体相当于多

15、个粒子进行盲目的随机搜索，收敛速度慢，个群体相当于多个粒子进行盲目的随机搜索，收敛速度慢，因而得到最优解的可能性小。因而得到最优解的可能性小。1()()iiiiVVcrandpbestx16三、算法举例和仿真三、算法举例和仿真举例：举例： 已知函数已知函数y=f(x1,x2)=x12+x22，其中，其中，-10 x1,x210，用粒，用粒 子群优化算法求解子群优化算法求解y的最小值。的最小值。通过常识，我们可以很容易得看出最小值是通过常识，我们可以很容易得看出最小值是X1=X2=0时取时取到的最小值到的最小值。我们现在用粒子群算法来验证一下。我们现在用粒子群算法来验证一下。17三、算法举例和仿

16、真三、算法举例和仿真步骤步骤1：初始化：初始化设种群大小是设种群大小是N=3；给定惯量权重给定惯量权重=0.5，c1=c2=2；r1，r2 是是0，1区间随机数；区间随机数；假设初始位置和速度分别为：假设初始位置和速度分别为：)8, 7- (x)35()9 , 5- (x)2- , 3- ()5, 8(x)2 , 3(333222111，vpvpvp计算适应函数值，并且得到粒子的历史最优位置和群体的全局最优位置：计算适应函数值，并且得到粒子的历史最优位置和群体的全局最优位置：) 5, 8 () 8, 7(1136449) 8()7(,)9 , 5(10625819) 5(,) 5, 8 (89

17、2564) 5(81332232222211221pBestgBestxpBestfxpBestfxpBestf18三、算法举例和仿真三、算法举例和仿真步骤步骤2：粒子的速度和位置更新。：粒子的速度和位置更新。根据自身的历史最优位置和全局最优位置，更新每个粒子的速度和位置：根据自身的历史最优位置和全局最优位置，更新每个粒子的速度和位置：)4, 5 . 9() 1 , 5 . 1 ()5, 8() 1 , 5 . 1 (10025 . 05 . 10035 . 0)()(11111221111111vxxvxgBestrcxpBestrcvvp)10, 1 . 1 ()8 .10, 1 . 1

18、()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)()(22222222211222vxxvxgBestrcxpBestrcvvp对于越界位置需要进行合法性调整对于越界位置需要进行合法性调整19)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)()(33333223311333vxxvxgBestrcxpBestrcvvp

19、三、算法举例和仿真三、算法举例和仿真20步骤步骤3：评估粒子的适应度函数值：评估粒子的适应度函数值更新粒子的历史最优位置和全局最优位置：更新粒子的历史最优位置和全局最优位置：三、算法举例和仿真三、算法举例和仿真)7 . 1, 5 . 3()7 . 1, 5 . 3(14.1511314.1589. 225.12)7 . 1()5 . 3()10, 1 . 1 (21.10110621.10110021. 1101 . 1)5, 8(898925.1061625.90)4(5 . 933*33322*322*22222*211122*1pBestgBestxpBestffffxpBestffff

20、pBestfff21三、算法举例和仿真三、算法举例和仿真步骤步骤4：如果满足结束条件，则输出全局最优结果并结束程：如果满足结束条件，则输出全局最优结果并结束程序，否则，转向步骤序，否则，转向步骤2继续执行。继续执行。这里我们将结束条件定为迭代次数，取迭代次数为这里我们将结束条件定为迭代次数，取迭代次数为100。按。按以上步骤进行计算，通过以上步骤进行计算，通过MATLAB的仿真，可以看到仿真图：的仿真，可以看到仿真图：22三、算法举例和仿真三、算法举例和仿真24四、算法改进方向和研究状况四、算法改进方向和研究状况优点：优点： （1）PSO算法没有交叉和变异运算，依靠粒子速度完成搜索，且算法没有

21、交叉和变异运算，依靠粒子速度完成搜索，且迭代进化中只有最优粒子把信息传递给其他粒子；迭代进化中只有最优粒子把信息传递给其他粒子； （2）PSO算法具有记忆性，粒子群体的历史最好位置可以记忆并算法具有记忆性，粒子群体的历史最好位置可以记忆并传递给其他粒子；传递给其他粒子； （3）需调整的参数少，结构简单，易于工程实现。）需调整的参数少，结构简单，易于工程实现。缺点：缺点： （1）容易陷入局部最优，导致收敛精度低和不易收敛；）容易陷入局部最优，导致收敛精度低和不易收敛； （2）不能有效解决离散及组合优化问题；）不能有效解决离散及组合优化问题； （3）不能有效求解一些非直角坐标系描述问题。）不能有效

22、求解一些非直角坐标系描述问题。优缺点分析：优缺点分析：25针对针对PSO算法存在的缺陷，目前对于算法的研究方向可以集中在以算法存在的缺陷，目前对于算法的研究方向可以集中在以下几个方向：下几个方向：1、算法理论研究、算法理论研究2、算法参数研究、算法参数研究3、拓扑结构研究、拓扑结构研究4、混合算法研究、混合算法研究四、算法改进方向和研究状况四、算法改进方向和研究状况5、离散版本改进、离散版本改进261、算法理论研究算法理论研究指的是对粒子群优化算法进行理论分指的是对粒子群优化算法进行理论分析，从数学推导上证明算法具有收敛析，从数学推导上证明算法具有收敛性，能够有保证算法求解到全局最优解性，能够

23、有保证算法求解到全局最优解。Clerc引入收敛因子引入收敛因子(constriction factor) K来保证收敛性。来保证收敛性。12()()()()iiiiiiVK Vrandpbestxrandgbestx其中：其中：1222,4.24K 四、算法改进方向和研究状况四、算法改进方向和研究状况272、算法参数研究算法参数研究PSO具有惯量权重具有惯量权重、加速系数、加速系数c1、c2，最大速度最大速度，种群规模等。参数分析试图通过研究这些参数对，种群规模等。参数分析试图通过研究这些参数对算法全局搜索能力和局部搜索能力的影像，找到更好算法全局搜索能力和局部搜索能力的影像，找到更好的参数配

24、置或者自适应调擦参方案，提高算法性能。的参数配置或者自适应调擦参方案，提高算法性能。参数分析：参数分析：权重因子权重因子：包括惯性因子：包括惯性因子和学习因子和学习因子c1c1和和c2c2。使粒子保持着运动惯性，使粒子保持着运动惯性，使其具有扩展搜索空间的趋势，有能力探索新的区域。使其具有扩展搜索空间的趋势，有能力探索新的区域。 c1 c1和和c2c2使粒子具有自我总结和向群体中优秀个体学习的能力，从而使粒子具有自我总结和向群体中优秀个体学习的能力，从而向群体内或邻域内最近点靠近，通常取为向群体内或邻域内最近点靠近，通常取为2，也可以相等，取值范围，也可以相等，取值范围0到到4。代表代表每个粒

25、子推向每个粒子推向pbestpbest和和gbestgbest位置的统计加速项的权值。较低的值允位置的统计加速项的权值。较低的值允许粒子在被拉回之前可以在目标区域外徘徊，较高的值导致粒子突然地冲许粒子在被拉回之前可以在目标区域外徘徊，较高的值导致粒子突然地冲向或越过目标区域。向或越过目标区域。 的作用表现为针对不同的搜索问题，调整算法的全局和局部搜索的作用表现为针对不同的搜索问题，调整算法的全局和局部搜索能力的平衡。能力的平衡。 较大时，具有较强的全局搜索能力；较大时，具有较强的全局搜索能力； 较小时，具有较较小时，具有较强的局部搜索能力。强的局部搜索能力。四、算法改进方向和研究状况四、算法改

26、进方向和研究状况28四、算法改进方向和研究状况四、算法改进方向和研究状况最大速度最大速度决定当前位置与最好位置之间的区域的分辨决定当前位置与最好位置之间的区域的分辨率率(或精度或精度)。如果太快，则粒子有可能越过极小点；如果太慢，。如果太快，则粒子有可能越过极小点；如果太慢，则粒子不能在局部极小点之外进行足够的探索，会陷入到局则粒子不能在局部极小点之外进行足够的探索，会陷入到局部极值区域内。这种限制可以达到防止计算溢出、决定问题部极值区域内。这种限制可以达到防止计算溢出、决定问题空间搜索的粒度的目的。空间搜索的粒度的目的。参数分析：参数分析：293、拓扑结构研究、拓扑结构研究PSO有全局版本和

27、局部版本之分，它们的不同之处在于有全局版本和局部版本之分，它们的不同之处在于更新速度的时候采用整个种群最优的粒子作为样本还是更新速度的时候采用整个种群最优的粒子作为样本还是局部邻居中最优的粒子作为样本。不同的拓扑结构会影局部邻居中最优的粒子作为样本。不同的拓扑结构会影像算法局部搜索和全局搜索的能力。像算法局部搜索和全局搜索的能力。全局版本：全局版本：星型结构星型结构局部版本：局部版本：环形结构环形结构齿形结构齿形结构金字塔形结构金字塔形结构冯诺依曼结构冯诺依曼结构逐步增长法逐步增长法Suganthan 1999最小距离法最小距离法Hu和和Eberhart 2002重新组合法重新组合法Liang和和Suganthan 2005随机选择发随机选择发Kennedy等人等人 2006社会趋同法社会趋同法Kennedy 2000Fully InformedMendes等人等人 2004广泛学习策略广泛学习策略Liang等人等人 2006静态拓扑结构静态拓扑结构动态拓扑结构动态拓扑结构其他拓扑结构其他拓扑结构四、算法改进方向和研究状况四、算法改进方向和研究状况304、混合算法研究、混合算法研究PSO自身收