粒子群算法课件

2022/10/301粒子群算法2022/10/231粒子群算法12022/10/302粒子群算法的研究背景粒子群算法(ParticleSwarmOptimization，简称PSO)，是一种基于群体智能的进化计算方法。PSO由Kennedy和Eberhart博士于1995年提出。PSO一经提出，由于算法简单，容易实现，立刻引起了进化计算领域学者们的广泛关注，形成一个研究热点，目前已广泛应用于函数优化、神经网络训练、模式分类、模糊控制等领域，取得了较好的效果。目前PSO算法已被“国际进化计算会议”(IEEEInternationalConferencesonEvolutionaryComputation,CEC)列为一个讨论的专题。2022/10/232粒子群算法的研究背景粒子群算法(Par22022/10/303PSO的基本概念源于对鸟群捕食行为的研究：一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有鸟都不知道食物在哪里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢?最简单有效的就是搜寻目前离食物最近的鸟的周围区域。粒子群算法的基本原理2022/10/233PSO的基本概念源于对鸟群捕食行为的研32022/10/304PSO算法就从这种生物种群行为特性中得到启发并用于求解优化问题。在PSO中，把一个优化问题看作是在空中觅食的鸟群，那么“食物”就是优化问题的最优解，而在空中飞行的每一只觅食的“鸟”就是PSO算法中在解空间中进行搜索的一个“粒子”(Particle)。“群”(Swarm)的概念来自于人工生命，满足人工生命的五个基本原则。因此PSO算法也可看作是对简化了的社会模型的模拟，这其中最重要的是社会群体中的信息共享机制，这是推动算法的主要机制。2022/10/234PSO算法就从这种生物种群行为特性中得42022/10/305粒子在搜索空间中以一定的速度飞行，这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整。所有的粒子都有一个被目标函数决定的适应值(fitness

value)，这个适应值用于评价粒子的“好坏”程度。每个粒子知道自己到目前为止发现的最好位置(particlebest，记为pbest)和当前的位置，pbest就是粒子本身找到的最优解，这个可以看作是粒子自己的飞行经验。除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(globalbest，记为gbest)，gbest是在pbest中的最好值，即是全局最优解，这个可以看作是整个群体的经验。2022/10/235粒子在搜索空间中以一定的速度飞行，这个52022/10/306每个粒子使用下列信息改变自己的当前位置：

(1)当前位置；

(2)当前速度；

(3)当前位置与自己最好位置之间的距离；

(4)当前位置与群体最好位置之间的距离。2022/10/236每个粒子使用下列信息改变自己的当前位置62022/10/307用随机解初始化一群随机粒子，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己：一个是粒子本身所找到的最好解，即个体极值(pbest)，另一个极值是整个粒子群中所有粒子在历代搜索过程中所达到的最优解(gbest)即全局极值。找到这两个最好解后，接下来是PSO中最重要的“加速”过程，每个粒子不断地改变其在解空间中的速度，以尽可能地朝pbest和gbest所指向的区域“飞”去。粒子群算法的基本思想2022/10/237用随机解初始化一群随机粒子，然后通过迭72022/10/308假设在一个N维空间进行搜索，粒子i的信息可用两个N维向量来表示：第i个粒子的位置可表示为速度为在找到两个最优解后，粒子即可根据下式来更新自己的速度和位置：粒子群优化算法的一般数学模型

：是粒子i在第k次迭代中第d维的速度；：是粒子i在第k次迭代中第d维的当前位置；(1)(2)2022/10/238假设在一个N维空间进行搜索，粒子i的信82022/10/309i=1，2，3…，M：种群大小。c1和c2：学习因子，或称加速系数，合适的c1和c2既可加快收敛又不易陷入局部最优。rand1和rand2：是介于［0,1］之间的随机数。是粒子i在第d维的个体极值点的位置；是整个种群在第d维的全局极值点的位置。最大速度vmax：决定了问题空间搜索的力度，粒子的每一维速度vid都会被限制在[－vdmax，+vdmax]之间，假设搜索空间的第d维定义为区间[－xdmax，+xdmax]

，则通常vdmax=kxdmax

，0.1k1.0，每一维都用相同的设置方法。2022/10/239i=1，2，3…，M：种群大小。最大速92022/10/3010公式(1)主要通过三部分来计算粒子i更新的速度：粒子i前一时刻的速度；粒子当前位置与自己历史最好位置之间的距离；粒子当前位置与群体最好位置之间的距离。粒子通过公式(2)计算新位置的坐标。更新公式的意义2022/10/2310公式(1)主要通过三部分来计算粒子i102022/10/3011

式(1)的第一部分称为动量部分，表示粒子对当前自身运动状态的信任，为粒子提供了一个必要动量，使其依据自身速度进行惯性运动；第二部分称为个体认知部分，代表了粒子自身的思考行为，鼓励粒子飞向自身曾经发现的最优位置；第三部分称为社会认知部分，表示粒子间的信息共享与合作，它引导粒子飞向粒子群中的最优位置。公式(1)的第一项对应多样化(diversification)的特点，第二项、第三项对应于搜索过程的集中化(intensification)特点，这三项之间的相互平衡和制约决定了算法的主要性能。2022/10/2311式(1)的第一部分称为动量部分，表112022/10/3012参数意义(1)粒子的长度N：问题解空间的维数。(2)粒子种群大小M：粒子种群大小的选择视具体问题而定，但是一般设置粒子数为20-50。对于大部分的问题10个粒子已经可以取得很好的结果，不过对于比较难的问题或者特定类型的问题，粒子的数量可以取到100或200。另外，粒子数目越多，算法搜索的空间范围就越大，也就更容易发现全局最优解。当然，算法运行的时间也较长。(3)加速常数c1和c2：分别调节向Pbest和Gbest方向飞行的最大步长，决定粒子个体经验和群体经验对粒子运行轨迹的影响，反映粒子群之间的信息交流。如果c1=0，则粒子只有群体经验，它的收敛速度较快，但容易陷入局部最优；2022/10/2312参数意义(1)粒子的长度N：问题解空122022/10/3013如果c2=0，则粒子没有群体共享信息，一个规模为M的群体等价于运行了M个各行其是的粒子，得到解的几率非常小，因此一般设置c1=c2

。这样，个体经验和群体经验就有了相同重要的影响力，使得最后的最优解更精确。改变这些常数会改变系统的“张力”，较低的c1

和c2值使得粒子徘徊在远离目标的区域，较高的c1

和c2值产生陡峭的运动或越过目标区域。Shi和Eberhart建议，为了平衡随机因素的作用，一般情况下设置c1

＝c2，大部分算法都采用这个建议。2022/10/2313如果c2=0，则粒子没有群体共享132022/10/3014(4)粒子的最大速度vmax

：粒子的速度在空间中的每一维上都有一个最大速度限制值vdmax

，用来对粒子的速度进行钳制，使速度控制在范围[－vdmax，＋vdmax]内，这决定问题空间搜索的力度，该值一般由用户自己设定。vmax是一个非常重要的参数，如果该值太大，则粒子们也许会飞过优秀区域；另一方面如果该值太小，则粒子们可能无法对局部最优区域以外的区域进行充分的探测。实际上，它们可能会陷入局部最优，而无法移动足够远的距离跳出局部最优达到空间中更佳的位置。(5)rand1和rand2是介于［0,1］之间的随机数，增加了粒子飞行的随机性。(6)迭代终止条件：一般设为最大迭代次数Tmax、计算精度或最优解的最大停滞步数△t。2022/10/2314(4)粒子的最大速度vmax：粒142022/10/3015算法流程2022/10/2315算法流程152022/10/3016程序伪代码Foreachparticle—InitializeparticleEndDo—Foreachparticle——Calculatefitnessvalue——Ifthefitnessvalueisbetterthanthebestfitnessvalue(pbest)inhistory——setcurrentvalueasthenewpbest—End—Choosetheparticlewiththebestfitnessvalueofalltheparticlesasthegbest—Foreachparticle——Calculateparticlevelocityaccordingequation(1)——Updateparticlepositionaccordingequation(2)—EndWhilemaximumiterationsorminimumerrorcriteriaisnotattained2022/10/2316程序伪代码Foreachpart162022/10/3017PSO的各种改进算法PSO收敛速度快，特别是在算法的早期，但也存在着精度较低，易发散等缺点。若加速系数、最大速度等参数太大，粒子群可能错过最优解，算法不收敛；而在收敛的情况下，由于所有的粒子都向最优解的方向飞去，所以粒子趋向同一化（失去了多样性），使得后期收敛速度明显变慢，同时算法收敛到一定精度时，无法继续优化，所能达到的精度也不高。因此很多学者都致力于提高PSO算法的性能。2022/10/2317PSO的各种改进算法PSO收敛速度172022/10/3018惯性权重法（InertiaWeight）惯性权重法是由Shi等提出的，其速度更新公式为：为非负数，称为惯性因子，惯性权重，是控制速度的权重如果没有公式(1)的第一部分，PSO的搜索过程是一个通过迭代搜索空间逐渐收缩的过程，展现出一种局部搜索((exploitation)能力；反之，如果增加了第一部分，粒子就有能力扩展搜索空间，展现出一种全局搜索(exploration)的能力。在搜索过程中，全局搜索能力与局部搜索能力的平衡对于算法的成功起着至关重要的作用。引入一个惯性权重到公式(1)，是与前一次速度有关的一个比例因子，较大的可以加强PSO的全局探测能力，而较小的能加强局部搜索能力，也就是这个执行了全局搜索和局部搜索之间的平衡角色。(3)2022/10/2318惯性权重法（InertiaWeig182022/10/3019(1)线性调整的策略允许的最大速度vmax实际上作为一个约束，控制PSO能够具有的最大全局搜索能力。如果vmax较小，那么最大的全局搜索能力将被限制，不论惯性权重的大小，PSO只支持局部搜索；如果设置vmax较大，那么PSO通过选择

，有一个可供很多选择的搜索能力范围。由此可以看出，允许的最大速度间接地影响全局搜索能力，而惯性权重直接影响全局搜索能力，所以希望找到一个非常好的惯性权重来达到全局搜索和局部搜索之间的平衡。

类似于人的“原动力”，如果原动力比较大，当达到某个目标的时候，会继续向前实现更高的目标：如果原动力较小，到达某个目标就停滞。2022/10/2319(1)线性调整的策略192022/10/3020Shi和Eberhart提出了一种随着算法迭代次数的增加惯性权重线性下降的方法。惯性权重的计算公式如下：max和min分别表示权重的最大及最小值，kn为当前迭代次数，kmax表示最大迭代次数。文献试验了将设置为从0.9到0.4的线性下降，使得PSO在开始时探索较大的区域，较快地定位最优解的大致位置，随着逐渐减小，粒子速度减慢，开始精细的局部搜索。该方法使PSO更好地控制exploration和exploitation能力，加快了收敛速度，提高了算法的性能，称之为权重线性下降的粒子群算法，简记为LDW(LinearlyDecreasingInertiaWeight)。2022/10/2320Shi和Eberhart提出了一种随202022/10/3021(2)模糊调整的策略

PSO搜索过程是一个非线性的复杂过程，让线性下降的方法并不能正确反映真实的搜索过程。因而，Shi等提出用模糊推理机来动态地调整惯性权重的技术。即构造一个2输入、1输出的模糊推理机来动态地修改惯性因子。模糊推理机的两个输入分别是当前值，以及规范化后的当前最好性能评价值(TheNormalizedCurrentBestPerformanceEvaluation，NCBPE)；而输出是的增量。CBPE(TheCurrentBestPerformanceEvaluation，CBPE)是PSO迄今为止发现的最好候选解的性能测度。由于不同的优化问题有不同的性能评价值范围，所以为了让该模糊系统有广泛的适用性，通常使用标准化的CBPE(NCBPE)。2022/10/2321(2)模糊调整的策略212022/10/3022假定优化问题为最小化问题，则规范化后的评价值其中，CBPEmax和CBPEmin分别是CBPE可能取值的上下限，其值根据具体问题而定，且需事先得知或者可估计，这使得模糊自适应策略的实现较为困难，无法广泛使用，但其与线性减小策略相比，具有更好的性能。2022/10/2322假定优化问题为最小化问题，则规范化后222022/10/3023收敛因子法（ConstrictionFactor）粒子群优化算法起源于模拟社会系统，算法本身缺乏坚实的数学基础。1999年Clerk对算法进行数学研究证明，采用收缩因子能够确保算法的收敛，该方法简记为CFM(ConstrictionFactorModel)。通常将设为4.1(c1=c2=2.05)，则k=0.729，将k代入，与(3)对应，则相当于

=0.729,cl=c2=0.7292.05=1.49445。在算法早期的实验和应用中，认为当采用收缩因子模型时vmax参数无足轻重，后来的研究表明将其限定为xmax，可以取得更好的优化结果。(4)2022/10/2323收敛因子法（Constriction232022/10/3024惯性权重线性下降算法(LDW)是为了提高算法的收敛性能，平衡收敛的全局性和收敛速度，在多峰函数上效果显著；收缩因子模型(CEM)为了保证算法的收敛性，同时使得速度的限制放松，在单峰函数上效果优于LDW。但两种算法在高维复杂问题寻优时仍然存在早熟收敛、收敛精度比较低的缺点。2022/10/2324惯性权重线性下降算法(LDW)是为了242022/10/3025粒子群算法2022/10/231粒子群算法252022/10/3026粒子群算法的研究背景粒子群算法(ParticleSwarmOptimization，简称PSO)，是一种基于群体智能的进化计算方法。PSO由Kennedy和Eberhart博士于1995年提出。PSO一经提出，由于算法简单，容易实现，立刻引起了进化计算领域学者们的广泛关注，形成一个研究热点，目前已广泛应用于函数优化、神经网络训练、模式分类、模糊控制等领域，取得了较好的效果。目前PSO算法已被“国际进化计算会议”(IEEEInternationalConferencesonEvolutionaryComputation,CEC)列为一个讨论的专题。2022/10/232粒子群算法的研究背景粒子群算法(Par262022/10/3027PSO的基本概念源于对鸟群捕食行为的研究：一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有鸟都不知道食物在哪里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢?最简单有效的就是搜寻目前离食物最近的鸟的周围区域。粒子群算法的基本原理2022/10/233PSO的基本概念源于对鸟群捕食行为的研272022/10/3028PSO算法就从这种生物种群行为特性中得到启发并用于求解优化问题。在PSO中，把一个优化问题看作是在空中觅食的鸟群，那么“食物”就是优化问题的最优解，而在空中飞行的每一只觅食的“鸟”就是PSO算法中在解空间中进行搜索的一个“粒子”(Particle)。“群”(Swarm)的概念来自于人工生命，满足人工生命的五个基本原则。因此PSO算法也可看作是对简化了的社会模型的模拟，这其中最重要的是社会群体中的信息共享机制，这是推动算法的主要机制。2022/10/234PSO算法就从这种生物种群行为特性中得282022/10/3029粒子在搜索空间中以一定的速度飞行，这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整。所有的粒子都有一个被目标函数决定的适应值(fitness

value)，这个适应值用于评价粒子的“好坏”程度。每个粒子知道自己到目前为止发现的最好位置(particlebest，记为pbest)和当前的位置，pbest就是粒子本身找到的最优解，这个可以看作是粒子自己的飞行经验。除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(globalbest，记为gbest)，gbest是在pbest中的最好值，即是全局最优解，这个可以看作是整个群体的经验。2022/10/235粒子在搜索空间中以一定的速度飞行，这个292022/10/3030每个粒子使用下列信息改变自己的当前位置：

(1)当前位置；

(2)当前速度；

(3)当前位置与自己最好位置之间的距离；

(4)当前位置与群体最好位置之间的距离。2022/10/236每个粒子使用下列信息改变自己的当前位置302022/10/3031用随机解初始化一群随机粒子，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己：一个是粒子本身所找到的最好解，即个体极值(pbest)，另一个极值是整个粒子群中所有粒子在历代搜索过程中所达到的最优解(gbest)即全局极值。找到这两个最好解后，接下来是PSO中最重要的“加速”过程，每个粒子不断地改变其在解空间中的速度，以尽可能地朝pbest和gbest所指向的区域“飞”去。粒子群算法的基本思想2022/10/237用随机解初始化一群随机粒子，然后通过迭312022/10/3032假设在一个N维空间进行搜索，粒子i的信息可用两个N维向量来表示：第i个粒子的位置可表示为速度为在找到两个最优解后，粒子即可根据下式来更新自己的速度和位置：粒子群优化算法的一般数学模型

：是粒子i在第k次迭代中第d维的速度；：是粒子i在第k次迭代中第d维的当前位置；(1)(2)2022/10/238假设在一个N维空间进行搜索，粒子i的信322022/10/3033i=1，2，3…，M：种群大小。c1和c2：学习因子，或称加速系数，合适的c1和c2既可加快收敛又不易陷入局部最优。rand1和rand2：是介于［0,1］之间的随机数。是粒子i在第d维的个体极值点的位置；是整个种群在第d维的全局极值点的位置。最大速度vmax：决定了问题空间搜索的力度，粒子的每一维速度vid都会被限制在[－vdmax，+vdmax]之间，假设搜索空间的第d维定义为区间[－xdmax，+xdmax]

，则通常vdmax=kxdmax

，0.1k1.0，每一维都用相同的设置方法。2022/10/239i=1，2，3…，M：种群大小。最大速332022/10/3034公式(1)主要通过三部分来计算粒子i更新的速度：粒子i前一时刻的速度；粒子当前位置与自己历史最好位置之间的距离；粒子当前位置与群体最好位置之间的距离。粒子通过公式(2)计算新位置的坐标。更新公式的意义2022/10/2310公式(1)主要通过三部分来计算粒子i342022/10/3035

式(1)的第一部分称为动量部分，表示粒子对当前自身运动状态的信任，为粒子提供了一个必要动量，使其依据自身速度进行惯性运动；第二部分称为个体认知部分，代表了粒子自身的思考行为，鼓励粒子飞向自身曾经发现的最优位置；第三部分称为社会认知部分，表示粒子间的信息共享与合作，它引导粒子飞向粒子群中的最优位置。公式(1)的第一项对应多样化(diversification)的特点，第二项、第三项对应于搜索过程的集中化(intensification)特点，这三项之间的相互平衡和制约决定了算法的主要性能。2022/10/2311式(1)的第一部分称为动量部分，表352022/10/3036参数意义(1)粒子的长度N：问题解空间的维数。(2)粒子种群大小M：粒子种群大小的选择视具体问题而定，但是一般设置粒子数为20-50。对于大部分的问题10个粒子已经可以取得很好的结果，不过对于比较难的问题或者特定类型的问题，粒子的数量可以取到100或200。另外，粒子数目越多，算法搜索的空间范围就越大，也就更容易发现全局最优解。当然，算法运行的时间也较长。(3)加速常数c1和c2：分别调节向Pbest和Gbest方向飞行的最大步长，决定粒子个体经验和群体经验对粒子运行轨迹的影响，反映粒子群之间的信息交流。如果c1=0，则粒子只有群体经验，它的收敛速度较快，但容易陷入局部最优；2022/10/2312参数意义(1)粒子的长度N：问题解空362022/10/3037如果c2=0，则粒子没有群体共享信息，一个规模为M的群体等价于运行了M个各行其是的粒子，得到解的几率非常小，因此一般设置c1=c2

。这样，个体经验和群体经验就有了相同重要的影响力，使得最后的最优解更精确。改变这些常数会改变系统的“张力”，较低的c1

和c2值使得粒子徘徊在远离目标的区域，较高的c1

和c2值产生陡峭的运动或越过目标区域。Shi和Eberhart建议，为了平衡随机因素的作用，一般情况下设置c1

＝c2，大部分算法都采用这个建议。2022/10/2313如果c2=0，则粒子没有群体共享372022/10/3038(4)粒子的最大速度vmax

：粒子的速度在空间中的每一维上都有一个最大速度限制值vdmax

，用来对粒子的速度进行钳制，使速度控制在范围[－vdmax，＋vdmax]内，这决定问题空间搜索的力度，该值一般由用户自己设定。vmax是一个非常重要的参数，如果该值太大，则粒子们也许会飞过优秀区域；另一方面如果该值太小，则粒子们可能无法对局部最优区域以外的区域进行充分的探测。实际上，它们可能会陷入局部最优，而无法移动足够远的距离跳出局部最优达到空间中更佳的位置。(5)rand1和rand2是介于［0,1］之间的随机数，增加了粒子飞行的随机性。(6)迭代终止条件：一般设为最大迭代次数Tmax、计算精度或最优解的最大停滞步数△t。2022/10/2314(4)粒子的最大速度vmax：粒382022/10/3039算法流程2022/10/2315算法流程392022/10/3040程序伪代码Foreachparticle—InitializeparticleEndDo—Foreachparticle——Calculatefitnessvalue——Ifthefitnessvalueisbetterthanthebestfitnessvalue(pbest)inhistory——setcurrentvalueasthenewpbest—End—Choosetheparticlewiththebestfitnessvalueofalltheparticlesasthegbest—Foreachparticle——Calculateparticlevelocityaccordingequation(1)——Updateparticlepositionaccordingequation(2)—EndWhilemaximumiterationsorminimumerrorcriteriaisnotattained2022/10/2316程序伪代码Foreachpart402022/10/3041PSO的各种改进算法PSO收敛速度快，特别是在算法的早期，但也存在着精度较低，易发散等缺点。若加速系数、最大速度等参数太大，粒子群可能错过最优解，算法不收敛；而在收敛的情况下，由于所有的粒子都向最优解的方向飞去，所以粒子趋向同一化（失去了多样性），使得后期收敛速度明显变慢，同时算法收敛到一定精度时，无法继续优化，所能达到的精度也不高。因此很多学者都致力于提高PSO算法的性能。2022/10/2317PSO的各种改进算法PSO收敛速度412022/10/3042惯性权重法（InertiaWeight）惯性权重法是由Shi等提出的，其速度更新公式为：为非负数，称为惯性因子，惯性权重，是控制速度的权重如果没有公式(1)的第一部分，PSO的搜索过程是一个通过迭代搜索空间逐渐收缩的过程，展现出一种局部搜索((exploitation)能力；反之，如果增加了第一部分，粒子就有能力扩展搜索空间，展现出一种全局搜索(exploration)的能力。在搜索过程中，全局搜索能力与局部搜索能力的平衡对于算法的成功起着至关重要的作用。引入一个惯性权重到公式(1)，是与前一次速度有关的一个比例因子，较大的可以加强PSO的全局探测能力，而较小的能加强局部搜索能力，也就是这个执行了全局搜索和局部搜索之间的平衡角色。(3)2022/10/2318惯性权重法（InertiaWeig422022/10/3043(1)线性调整的策略允许的最大速度vmax实际上作为一个约束，控制PSO能够具有的最大全局搜索能力。如果vmax较小，那么最大的全局搜索能力将被限制，不论惯性权重的大小，PSO只支持局部搜索；如果设置vmax较大，那么PSO通过选择

，有一个可供很多选择的搜索能力范围。由此可以看出，允许的最大速度间接地影响全局搜索能力，而惯性权重直接影响全局搜索能力，所以希望找到一个非常好的惯性权重来达到全局搜索和局部搜索之间的平衡。

类似于人的“原动力”，如果原动力比较大，当达到某个目标的时候，会继续向前实现更高的目标：如果原动力较小，到达某个目标就停滞。2022/10/2319(1)线性调整的策略432022/10/3044Shi和Eberhart提出了一种随着算法迭代次数的增加惯性权重线性下降的方法。惯性权重的计算公式如下：max和min分别表示权重的最大及最小值，kn为当前迭代次数，kmax表示最大迭代次数。文