PSO粒子群算法简介

粒子群优化算法PARTICLESWARMOPTIMIZATION生物启发式算法进化算法人工神经网络粒子群优化算法群体智能优化算法：群体智能优化算法主要模拟了昆虫、兽群、鸟群和鱼群的群集行为，这些群体按照一种合作的方式寻找食物，群体中的每个成员通过学习它自身的经验和其他成员的经验来不断地改变搜索的方向。群体智能优化算法的突出特点就是利用了种群的群体智慧进行协同搜索，从而在解空间内找到最优解。常见的群体智能优化算法主要有如下几类：（1）蚁群算法（AntColonyOptimization，简称ACO）[1992年提出]；（2）粒子群优化算法（ParticleSwarmOptimization，简称PSO）[1995年提出]（简单易于实现，也是目前应用最为广泛的群体智能优化算法）；（3）菌群优化算法（BacterialForagingOptimization，简称BFO）[2002年提出]；（4）蛙跳算法（ShuffledFrogLeadingAlgorithm，简称SFLA）[2003年提出]；（5）人工蜂群算法（ArtificialBeeColonyAlgorithm，简称ABC）[2005年提出]；除了上述几种常见的群体智能算法以外，还有一些并不是广泛应用的群体智能算法，比如萤火虫算法、布谷鸟算法、蝙蝠算法以及磷虾群算法等等。粒子群优化算法是在1995年由Eberhart博士和Kennedy博士一起提出的，它源于对鸟群捕食行为的研究。它的基本核心是利用群体中的个体对信息的共享从而使得整个群体的运动在问题求解空间中产生从无序到有序的演化过程，从而获得问题的最优解。一群鸟进行觅食，而远处有一片玉米地，所有的鸟都不知道玉米地到底在哪里，但是它们知道自己当前的位置距离玉米地有多远。那么找到玉米地的最佳策略，也是最简单有效的策略就是是搜寻目前距离玉米地最近的鸟群的周围区域。PSO就是从这种群体觅食的行为中得到了启示，从而构建的一种优化模型。在PSO中，每个优化问题的解都是搜索空间中的一只鸟，称之为“粒子”，而问题的最优解就对应为鸟群要寻找的“玉米地”。所有的粒子都具有一个位置向量（粒子在解空间的位置）和速度向量（决定下次飞行的方向和速度），并可以根据目标函数来计算当前的所在位置的适应值（fitnessvalue），可以将其理解为距离“玉米地”的距离。在每次的迭代中，种群中的粒子除了根据自身的“经验”（历史位置）进行学习以外，还可以根据种群中最优粒子的“经验”来学习，从而确定下一次迭代时需要如何调整和改变飞行的方向和速度。就这样逐步迭代，最终整个种群的粒子就会逐步趋于最优解。粒子群优化算法求最优解D维空间中，有N个粒子；粒子i位置：xi=(xi1,xi2,…xiD)，将xi代入适应函数f(xi)求适应值；粒子i速度：vi=(vi1,vi2,…viD)粒子i个体经历过的最好位置：pbesti=(pi1,pi2,…piD)种群所经历过的最好位置：gbest=(g1,g2,…gD)粒子i的第d维速度更新公式：粒子i的第d维位置更新公式：—第k次迭代粒子i飞行速度矢量的第d维分量—第k次迭代粒子i位置矢量的第d维分量c1,c2—加速度常数，调节学习最大步长r1,r2—两个随机函数，取值范围[0，1]，以增加搜索随机性w—惯性权重，非负数，调节对解空间的搜索范围kk-111idid1122v=wv()()kkididdidcrpbestxcrgbestx11kkkidididxxvkidvkidx粒子速度更新公式包含三部分：第一部分为粒子先前的速度第二部分为“认知”部分，表示粒子本身的思考，可理解为粒子i当前位置与自己最好位置之间的距离。第三部分为“社会”部分，表示粒子间的信息共享与合作，可理解为粒子i当前位置与群体最好位置之间的距离。kk-111idid1122v=wv()()kkididdidcrpbestxcrgbestx区域最佳解运动向量惯性向量pg全域最佳解算法流程1.Initial：初始化粒子群体（群体规模为n），包括随机位置和速度。2.Evaluation：根据fitnessfunction，评价每个粒子的适应度。3.FindthePbest：对每个粒子，将其当前适应值与其个体历史最佳位置（pbest）对应的适应值做比较，如果当前的适应值更高，则将用当前位置更新历史最佳位置pbest。4.FindtheGbest：对每个粒子，将其当前适应值与全局最佳位置（gbest）对应的适应值做比较，如果当前的适应值更高，则将用当前粒子的位置更新全局最佳位置gbest。5.UpdatetheVelocity：根据公式更新每个粒子的速度与位置。6.如未满足结束条件，则返回步骤2通常算法达到最大迭代次数或者最佳适应度值的增量小于某个给定的阈值时算法停止。粒子群优化算法流程图开始初始化粒子群计算每个粒子的适应度根据适应度更新pbest、gbest，更新粒子位置速度结束noyes达到最大迭代次数或全局最优位置满足最小界限？要点1种群数量m种群数量过小：容易陷入局部最优解种群数量过大：计算量过大，收敛速度较慢失去对粒子本身的速度的记忆社会经验部分前次迭代中自身的速度自我认知部分基本粒子群算法粒子的速度更新主要由三部分组成：惯性因子kvkk-111idid1122v=wv()()kkididdidcrpbestxcrgbestx111()kididcrpbestx122()kdidcrgbestx要点2：权重因子粒子群算法的构成要素-权重因子权重因子：惯性因子、学习因子社会经验部分前次迭代中自身的速度自我认知部分粒子的速度更新主要由三部分组成：kvkk-111idid1122v=wv()()kkididdidcrpbestxcrgbestx111()kididcrpbestx122()kdidcrgbestx学习因子无私型粒子群算法“只有社会，没有自我”迅速丧失群体多样性，易陷入局优而无法跳出．粒子群算法的构成要素-权重因子权重因子：惯性因子、学习因子社会经验部分前次迭代中自身的速度自我认知部分粒子的速度更新主要由三部分组成：kvkk-111idid1122v=wv()()kkididdidcrpbestxcrgbestx111()kididcrpbestx122()kdidcrgbestx自我认知型粒子群算法“只有自我，没有社会”完全没有信息的社会共享，导致算法收敛速度缓慢学习因子粒子群算法的构成要素-权重因子权重因子：惯性因子、学习因子社会经验部分前次迭代中自身的速度自我认知部分粒子的速度更新主要由三部分组成：kvkk-111idid1122v=wv()()kkididdidcrpbestxcrgbestx111()kididcrpbestx122()kdidcrgbestxc1,c2都不为0，称为完全型粒子群算法完全型粒子群算法更容易保持收敛速度和搜索效果的均衡，是较好的选择．要点3：最大速度Vmax的设置但在于维护算法的探索能力与开发能力的平衡．Vm较大时，探索能力增强，作用:Vm较小时，开发能力增强，Vm一般设为每维变量变化范围的10％~20％.但粒子容易飞过最优解．容易陷入局部最优．要点4：邻域的拓扑结构全局粒子群算法和局部粒子群算法．粒子群算法的邻域拓扑结构包括两种，一种是将群体内所有个体都作为粒子的邻域，另一种是只将群体中的部分个体作为粒子的邻域．群体历史最优位置邻域拓扑结构决定由此，将粒子群算法分为粒子群算法的构成要素-邻域的拓扑结构全局粒子群算法1.粒子自己历史最优值2.粒子群体的全局最优值局部粒子群算法1.粒子自己历史最优值2.粒子邻域内粒子的最优值邻域随迭代次数的增加线性变大，最后邻域扩展到整个粒子群。经过实践证明：全局版本的粒子群算法收敛速度快，但是容易陷入局部最优。局部版本的粒子群算法收敛速度慢，但是很难陷入局部最优。需要在两方面做出平衡。粒子群算法存在的问题缺乏严密数学基础收敛性研究参数设置等理论研究较为缺乏依赖经验与实验