粒子群算法简介优缺点及其应用

2021-4-30 1 粒 子 群 算 法 2021-4-30 2 粒子群算法的研究背景粒子群算法(Particle Swarm Optimization，简称PSO)，是一种基于群体智能的进化计算方法。PSO由Kennedy和Eberhart博士于1995年提出。粒子群算法源于复杂适应系统（Complex Adaptive System,CAS）。CAS理论于1994年正式提出，CAS中的成员称为主体。比如研究鸟群系统，每个鸟在这个系统中就称为主体。主体有适应性，它能够与环境及其他的主体进行交流，并且根据交流的过程“学习”或“积累经验”改变自身结构与行为。整个系统的演变或进化包括：新层次的产生（小鸟的出生）；分化和多样性的出现（鸟群中的鸟分成许多小的群）；新的主题的出现（鸟寻找食物过程中，不断发现新的食物）。 2021-4-30 3 PSO的基本概念源于对鸟群捕食行为的研究：一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有鸟都不知道食物在哪里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢?最简单有效的就是搜寻目前离食物最近的鸟的周围区域。粒子群算法的基本原理 2021-4-30 4 PSO算法就从这种生物种群行为特性中得到启发并用于求解优化问题。在PSO中，把一个优化问题看作是在空中觅食的鸟群，那么“食物”就是优化问题的最优解，而在空中飞行的每一只觅食的“鸟”就是PSO算法中在解空间中进行搜索的一个“粒子”(Particle)。“群”(Swarm)的概念来自于人工生命，满足人工生命的五个基本原则。因此PSO算法也可看作是对简化了的社会模型的模拟，这其中最重要的是社会群体中的信息共享机制，这是推动算法的主要机制。 2021-4-30 5 粒子在搜索空间中以一定的速度飞行，这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整。所有的粒子都有一个被目标函数决定的适应值(fitness value)，这个适应值用于评价粒子的“好坏”程度。每个粒子知道自己到目前为止发现的最好位置(particle best，记为pbest)和当前的位置，pbest就是粒子本身找到的最优解，这个可以看作是粒子自己的飞行经验。除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(global best，记为gbest)，gbest是在pbest中的最好值，即是全局最优解，这个可以看作是整个群体的经验。 2021-4-30 6 每个粒子使用下列信息改变自己的当前位置： (1)当前位置； (2)当前速度； (3)当前位置与自己最好位置之间的距离； (4)当前位置与群体最好位置之间的距离。 2021-4-30 7 用随机解初始化一群随机粒子，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己：一个是粒子本身所找到的最好解，即个体极值(pbest)，另一个极值是整个粒子群中所有粒子在历代搜索过程中所达到的最优解(gbest)即全局极值。找到这两个最好解后，接下来是PSO中最重要的“加速”过程，每个粒子不断地改变其在解空间中的速度，以尽可能地朝pbest和gbest所指向的区域“飞”去。粒子群算法的基本思想 2021-4-30 8 假设在一个N维空间进行搜索，粒子i的信息可用两个N维向量来表示：第i个粒子的位置可表示为 速度为 在找到两个最优解后，粒子即可根据下式来更新自己的速度和位置：粒子群优化算法的一般数学模型 11 kidkidkid vxx )()( 22111 kidkdkkidkidkkidkid xGbestrandcxPbestrandcvv ：是粒子i在第k次迭代中第d维的速度； ：是粒子i在第k次迭代中第d维的当前位置；kidvkidx TiNiii xxxx, 21 TiNiii vvvv, 21 (1)(2) 2021-4-30 9 i=1，2，3，M：种群大小。c1和c2：学习因子，或称加速系数，合适的c1和c2既可加快收敛又不易陷入局部最优。rand1和rand2：是介于0,1之间的随机数。 是粒子i在第d维的个体极值点的位置； 是整个种群在第d维的全局极值点的位置。 kidPbest kdGbest最大速度vmax：决定了问题空间搜索的力度，粒子的每一维速度vid都会被限制在vdmax，+vdmax 之间，假设搜索空间的第d维定义为区间xdmax，+xdmax ，则通常vdmax=kxdmax ， 0.1k1.0，每一维都用相同的设置方法。 2021-4-30 10 公式(1)主要通过三部分来计算粒子i更新的速度：粒子i前一时刻的速度 ；粒子当前位置与自己历史最好位置之间的距离 ；粒子当前位置与群体最好位置之间的距离 。粒子通过公式(2)计算新位置的坐标。kidv )( kidkid xPbest )( kidkd xGbest 更新公式的意义 2021-4-30 11 式(1)的第一部分称为动量部分，表示粒子对当前自身运动状态的信任，为粒子提供了一个必要动量，使其依据自身速度进行惯性运动；第二部分称为个体认知部分，代表了粒子自身的思考行为，鼓励粒子飞向自身曾经发现的最优位置；第三部分称为社会认知部分，表示粒子间的信息共享与合作，它引导粒子飞向粒子群中的最优位置。公式(1)的第一项对应多样化(diversification)的特点，第二项、第三项对应于搜索过程的集中化(intensification)特点，这三项之间的相互平衡和制约决定了算法的主要性能。 2021-4-30 12 参数意义(1)粒子的长度N：问题解空间的维数。(2)粒子种群大小M：粒子种群大小的选择视具体问题而定，但是一般设置粒子数为20-50。对于大部分的问题10个粒子已经可以取得很好的结果，不过对于比较难的问题或者特定类型的问题，粒子的数量可以取到100或200。另外，粒子数目越多，算法搜索的空间范围就越大，也就更容易发现全局最优解。当然，算法运行的时间也较长。(3)加速常数c 1和 c2：分别调节向Pbest和Gbest方向飞行的最大步长，决定粒子个体经验和群体经验对粒子运行轨迹的影响，反映粒子群之间的信息交流。如果c1=0，则粒子只有群体经验，它的收敛速度较快，但容易陷入局部最优； 2021-4-30 13 如果c2 = 0，则粒子没有群体共享信息，一个规模为M的群体等价于运行了M个各行其是的粒子，得到解的几率非常小，因此一般设置c1 = c2 。这样，个体经验和群体经验就有了相同重要的影响力，使得最后的最优解更精确。改变这些常数会改变系统的“张力”，较低的c1 和 c2值使得粒子徘徊在远离目标的区域，较高的c1 和 c2值产生陡峭的运动或越过目标区域。Shi和Eberhart建议，为了平衡随机因素的作用，一般情况下设置c1 c2，大部分算法都采用这个建议。 2021-4-30 14 (4)粒子的最大速度vmax ：粒子的速度在空间中的每一维上都有一个最大速度限制值vdmax ，用来对粒子的速度进行钳制，使速度控制在范围vdmax，vdmax 内，这决定问题空间搜索的力度，该值一般由用户自己设定。vmax是一个非常重要的参数，如果该值太大，则粒子们也许会飞过优秀区域；另一方面如果该值太小，则粒子们可能无法对局部最优区域以外的区域进行充分的探测。实际上，它们可能会陷入局部最优，而无法移动足够远的距离跳出局部最优达到空间中更佳的位置。(5) rand 1和rand2是介于0,1之间的随机数，增加了粒子飞行的随机性。(6)迭代终止条件：一般设为最大迭代次数Tmax、计算精度或最优解的最大停滞步数t。 2021-4-30 15 算法流程 2021-4-30 16 程序伪代码For each particleInitialize particleEndDoFor each particleCalculate fitness valueIf the fitness value is better than the best fitness value (pbest) in historyset current value as the new pbest EndChoose the particle with the best fitness value of all the particles as the gbestFor each particleCalculate particle velocity according equation (1) Update particle position according equation (2) EndWhile maximum iterations or minimum error criteria is not attained 2021-4-30 17 PSO的各种改进算法 PSO收敛速度快，特别是在算法的早期，但也存在着精度较低，易发散等缺点。若加速系数、最大速度等参数太大，粒子群可能错过最优解，算法不收敛；而在收敛的情况下，由于所有的粒子都向最优解的方向飞去，所以粒子趋向同一化（失去了多样性），使得后期收敛速度明显变慢，同时算法收敛到一定精度时，无法继续优化，所能达到的精度也不高。因此很多学者都致力于提高PSO算法的性能。 2021-4-30 18 惯性权重法（Inertia Weight）惯性权重法是由Shi等提出的，其速度更新公式为： )()( 22111 kidkdkkidkidkkidkid xGbestrandcxPbestrandcvv 为非负数，称为惯性因子，惯性权重，是控制速度的权重 如果没有公式(1)的第一部分，PSO的搜索过程是一个通过迭代搜索空间逐渐收缩的过程，展现出一种局部搜索(exploitation)能力；反之，如果增加了第一部分，粒子就有能力扩展搜索空间，展现出一种全局搜索(exploration)的能力。在搜索过程中，全局搜索能力与局部搜索能力的平衡对于算法的成功起着至关重要的作用。引入一个惯性权重到公式(1)， 是与前一次速度有关的一个比例因子，较大的可以加强PSO的全局探测能力，而较小的能加强局部搜索能力，也就是这个执行了全局搜索和局部搜索之间的平衡角色。(3) 2021-4-30 19 (1)线性调整的策略允许的最大速度vmax实际上作为一个约束，控制PSO能够具有的最大全局搜索能力。如果vmax较小，那么最大的全局搜索能力将被限制，不论惯性权重的大小，PSO只支持局部搜索；如果设置vmax较大，那么PSO通过选择 ，有一个可供很多选择的搜索能力范围。由此可以看出，允许的最大速度间接地影响全局搜索能力，而惯性权重直接影响全局搜索能力，所以希望找到一个非常好的惯性权重来达到全局搜索和局部搜索之间的平衡。 类似于人的“原动力”，如果原动力比较大，当达到某个目标的时候，会继续向前实现更高的目标：如果原动力较小，到达某个目标就停滞。 2021-4-30 20 Shi和Eberhart提出了一种随着算法迭代次数的增加惯性权重线性下降的方法。惯性权重的计算公式如下：max minmax max nkk max和min分别表示权重的最大及最小值，kn为当前迭代次数，kmax表示最大迭代次数。文献试验了将设置为从0.9到0.4的线性下降，使得PSO在开始时探索较大的区域，较快地定位最优解的大致位置，随着逐渐减小，粒子速度减慢，开始精细的局部搜索。该方法使PSO更好地控制exploration和exploitation能力，加快了收敛速度，提高了算法的性能，称之为权重线性下降的粒子群算法，简记为LDW(Linearly Decreasing Inertia Weight)。 2021-4-30 21 (2)模糊调整的策略 PSO搜索过程是一个非线性的复杂过程，让线性下降的方法并不能正确反映真实的搜索过程。因而，Shi等提出用模糊推理机来动态地调整惯性权重的技术。即构造一个2输入、1输出的模糊推理机来动态地修改惯性因子。模糊推理机的两个输入分别是当前值，以及规范化后的当前最好性能评价值(The Normalized Current Best Performance Evaluation，NCBPE)；而输出是的增量。CBPE (The Current Best Performance Evaluation，CBPE) 是PSO迄今为止发现的最好候选解的性能测度。由于不同的优化问题有不同的性能评价值范围，所以为了让该模糊系统有广泛的适用性，通常使用标准化的CBPE (NCBPE)。 2021-4-30 22 假定优化问题为最小化问题，则规范化后的评价值其中，CBPEmax和CBPEmin分别是CBPE可能取值的上下限，其值根据具体问题而定，且需事先得知或者可估计，这使得模糊自适应策略的实现较为困难，无法广泛使用，但其与线性减小策略相比，具有更好的性能。minmax minCBPECBPE CBPECBPENCBPE 2021-4-30 23 粒子群算法的优缺点分析lPSO算法没有交叉和变异运算，依靠粒子速度完成搜索，并且在迭代进化中只有最优的粒子把信息传递给其它粒子，搜索速度快；lPSO算法具有记忆性，粒子群体的历史最好位置可以记忆并传递给其它粒子；l需调整的参数较少，结构简单，易于工程实现；l采用实数编码，直接由问题的解决定，问题解的变量数直接作为粒子的维数。（1）粒子群算法的优点 2021-4-30 24 （2）粒子群算法的缺点l缺乏速度的动态调节，容易陷入局部最优，导致收敛精度低和不易收敛；l不能有效解决离散及组合优化问题；l不能有效求解一些非直角坐标系描述问题，如有关能量场或场内粒子运动规律的求解问题(这些求解空间的边界大部分是基于极坐标、球坐标或柱坐标的)；l参数控制，对于不同的问题，如何选择合适的参数来达到最优效果。 2021-4-30 25 粒子群算法的应用范围1.函数优化 PSO算法最初被应用于函数优化，但后来的学者经过研究发现，粒子群算法在解决一些经典的函数优化问题，甚至一些非线性函数时也展示出了良好的性能。粒子群优化算法已提出就受到了广泛的关注，各种粒子群算法应用研究的成果不断涌现，它的应用领域已从最初的函数优化和神经网络的训练扩展到更加开阔的领域，有力地促进了粒子群优化算法的研究。目前粒子群优化算法的主要应用在如下几个方面： 2021-4-30 26 2.神经网络训练 将PSO算法用于神经网络训练也取得了良好的效果，研究表明，PSO是一种很有潜力的神经网络训练算法，如用于市区环境状况的分析和预测等取得了较高的成功率。3.工程领域应用 很多工程中的实际问题，本质上都是优化问题，因此PSO算法自然就可以应用到实际的工程问题来，将PSO肃反和BP神经网络算法相结合训练神经网络已用于对电动汽车燃料电池组充电情况的模拟。粒子群优化算法和其它进化算法那一样，可以解决几乎所有的优化问题，或是可以转化为优化问题来求解。4.用于随机优化问题的求解：比如随机雪球车辆路径问题，随机规划问题等。5.用于最优控制问题的求解，如求解城市环路交通协调控制系统。 2021-4-30 27 粒子群算法的发展趋势1.算法基理的数学基础研究。PSO在实际应用中被证明是有效的，但目前还没有给出收敛性、收敛速度估计等方面的数学证明，已有的工作还远远不够；2.将各种先进理论引入到PSO。各种先进理论的引入，首先可以研究性能良好的新型粒子群拓扑结构。不同的粒子群邻居拓扑结构是对不同类型社会的模拟，研究不同拓扑结构的适用范围，对算法推广和使用有重要意义；其次可以优化PSO的参数及其选择。参数的选择分别关系到粒子速度的3个部分：惯性部分、社会部分和自身部分在搜索中的作用。如何选择、优化和调整参数，使得算法既能避免早熟又能比较快速地收敛，对工程实践有着重要意义； 2021-4-30 28 3.与其它智能优化算法的融合。将PSO和其它优化算法进行融合，主要考虑如何将PSO的优点和其它智能优化算法的优点相结合，取长补短，构造出有特色、有实用价值的混合算法；4. PSO的扩展应用。目前PSO的多数研究是针对直角坐标系统描述的系统、离散系统和单一优化系统，而实际系统中，很多系统是非直角坐标系统描述的系统、离散系统、组合优化的系统，目前在这些系统中应用PSO算法可供参考的研究还较少，广泛地开拓PSO在这些领域的应用不仅具有实际意义，同时对深化研究PSO也非常有意义。 2021-4-30 29 一个求函数极值的例子