第6章--粒子群算法基本理论.ppt

1、第6章 粒子群算法基本理论,6.1 粒子群算法的概述 6.1.1 粒子群算法的概念 6.1.2 粒子群算法的发展 6.1.3 粒子群算法的特点 6.1.4 粒子群算法的分类 6.2 粒子群算法的基本原理 6.2.1 生物学机理 6.2.2 传统PSO算法原理 6.2.3 标准PSO算法原理 6.2.4 PSO算法流程 6.2.5 全局和局部最优PSO算法 6.2.6 PSO算法参数分析 6.3 粒子群算法与其他算法的比较 6.3.1 与遗传算法的比较 6.3.2 与蚁群算法的比较 6.4 粒子群算法的应用 6.5 粒子群算法的研究方向,6.1 粒子群算法概述 6.1.1 粒子群算法的概念 粒子

2、群优化算法（Particle Swarm Optimization，简称PSO）又称为粒子群算法、微粒算法，是通过模拟鸟类群体觅食行为而发展起来的一种基于群体协作的随机搜索算法，属于启发式全局优化算法。 粒子群算法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解。,6.1 粒子群算法概述,6.1.2 粒子群算法的发展 萌芽阶段 1986年，人工生命、计算机图形学专家 Craig Reynolds提出了简单的人工生命系统boid模型（解释为bird like object），模拟了鸟类在飞行过程中分离、列队和聚集三种聚群飞行行为，并能感知到周围一定范围内其他boid的飞行信息。boid

3、根据该信息，结合当前自身的飞行状态，在三条简单行为规则的指导下，做出下一步的飞行决策。,6.1 粒子群算法的概述,Craig Reynolds 生于1953年3月15日, 避免碰撞：飞离最近的个体，以避免碰撞； 速度一致：和邻近的个体的平均速度保持一致； 向中心聚集：飞向群体的中心，向邻近个体的平均位置移动。 1990年，生物学家Frank Heppner建立了鸟类模型。一群小鸟为找到合适的栖息地在空中飞行 ，当群体中的一只发现较为合适的栖 息地时，它会毫不犹豫地飞向这个栖 息地，同时也将信息传给周围的小鸟 ，使周围的小鸟快速来到这里，最终 把整个群体吸引到合适的栖息地。,6.1 粒子群算法的

4、概述, 发展阶段 1995年，美国社会心理学家James Kennedy博士和电气工程师Russell Eberhart博士根据对鸟群捕食行为的研究，提出了粒子群算法。分别在日本和澳大利亚召开的两个国际会议上发表了两篇文章，标志着粒子群算法的诞生。 1 Kennedy J，Eberhart R，Particle swarm optimization， Proceeding of the IEEE International Conference on Neural Networks，1995，19421948 2 Eberhart R，Kennedy J，A new optimizer usi

5、ng particle swarm theory，Proceeding of the 6th International Symposium on Micro-Machine and Human Science， 1995，3943,6.1 粒子群算法的概述,社会心理学家 James Kennedy博士,电气工程师 Russell Eberhart博士,1998年，Yuhui Shi和Russell Eberhart在IEEE Congress on Evolution-ary Computation（6973）上发表了题为A modified particle swarm optimizer

6、的学术论文，首次对基本粒子群算法引入惯性权重修正了速度更新公式，修正后的公式已经为大多数研究者所使用。 从1998年开始，进化计算领域的著名会议IEEE CEC（Congress on Evolutionary Computation，国际进化计算会议）开始设置PSO算法的专题讨论，与计算智能相关的重要国际会议PPSN（Parallel Problem Solving from Neture）和GECCO（Gen-etic and Evolutionary Computation Conference）都将PSO算法作为会议主题之一。,6.1 粒子群算法的概述,2001年，由J.Kennedy

7、、 R.C.Eberhart、Yuhui Shi合著的第一本关于PSO的专著Swarm Intelligence在美国旧金山（San Francisco）Morgan Kaufmann Publishers出版。 2003年，第一届群智能研讨会IEEE Swarm Intelligence Symposium在美国的Indianapolis（印第安纳波利斯）召开，此后每年召开一次。 2004年，IEEE Transactions on Evolutionary Compu-tation出版了PSO算法专刊。 PSO算法作为一种新兴智能仿生算法，目前还没有完备的数学理论基础，但作为新兴优化算法已

8、在诸多领域得到广泛应用。,6.1 粒子群算法的概述,6.1.3 粒子群算法的特点 粒子群算法的优点 粒子群算法依靠粒子速度完成搜索，在迭代进化中只有最优的粒子将信息传递给其他粒子，搜索速度快。 粒子群算法具有记忆性，粒子群体的历史最好位置可以记忆，并传递给其他粒子。 需调整的参数较少，结构简单，易于工程实现。 采用实数编码，直接由问题的解决定，问题解的变量数直接作为粒子的维数。,6.1 粒子群算法的概述, 粒子群算法的缺点 容易陷入局部最优，导致收敛精度低和不易收敛。 不能有效解决离散及组合优化问题。,6.1 粒子群算法的概述,6.1.4 粒子群算法的分类 按照发展历程分类 一般分为传统粒子群

9、算法和标准粒子群算法。前者于1995年提出，后者于1998年改进，两者之差仅为有无惯性权重因子。 根据粒子邻域分类 一般分为全局最优粒子群算法和局部最优粒子群算法，目前主要有两种分类方法。,6.1 粒子群算法的概述,6.2 粒子群算法的基本原理 6.2.1 生物学机理 一群鸟在一个区域里随机搜索食物，所有的鸟都不知道食物在那里。但是他们知道当前位置离食物还有多远，那么找到食物的最优策略就是搜寻目前离食物最近的鸟的周围区域。,6.2 粒子群算法的基本原理,6.2 粒子群算法的基本原理,6.2 粒子群算法的基本原理,6.2 粒子群算法的基本原理,6.2 粒子群算法的基本原理,6.2 粒子群算法的基

10、本原理,粒子群算法PSO中，每个优化问题的解都是搜索空间中的一只鸟，称之为“粒子”。所有的粒子都有一个由被优化函数决定的适应度值（fitness value），每个粒子还有一个速度决定它们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中进行搜索。 PSO初始化为一群随机粒子（随机解），然后通过叠代找到最优解。在每一次叠代中，粒子通过跟踪两个“极值”来更新自己。第一个是粒子本身所找到的最优解，称为个体极值pbest，另一个是整个种群目前找到的最优解，称为全局极值gbest。另外也可以不用整个种群而只用其中一部分相邻的粒子，则这些所有相邻粒子中的极值就是局部极值。,6.2 粒子群算法的基

11、本原理,6.2.2 传统PSO算法原理 鸟被抽象为没有质量和体积的微粒，并延伸到N维空间中。粒子i（i=1，2，M）在N维空间的一些参数设置为 位置表示为： 飞行速度表示为： 每个粒子都有一个由目标函数决定的适应度值，并且知道自己迄今为止发现的最好位置（pbest）和现在的位置，可以看做是粒子自己的飞行经验。 每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置（gbest），可以看做是粒子同伴的经验。 粒子通过自己和同伴的经验决定下一步的运动轨迹。,6.2 粒子群算法的基本原理,PSO初始化为一群随机粒子，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值（pbest、gbes

12、t）来更新自己。在找到这两个最优值后，粒子通过下面的公式更新自己的速度和位置 式中， 分别表示粒子的数量及其维数； 为加速因子或学习因子，一般取正数； 为 之间的随机数。 在迭代中，速度和位置均设定最大值，超过边界值时取边界值。,6.2 粒子群算法的基本原理,在速度更新公式中，第一项称为记忆项，表示上次速度大小和方向的影响；第二项称为自身认知项，是从当前点指向粒子自身最好点的一个项，表示粒子的动作来源于自身的经验；第三项称为群体认知项，是一个从当前点指向种群最好点的项，反映了粒子间的协同合作和知识共享。 总之，粒子的速度更新公式由认知和社会两部分组成，粒子就是通过自身的经验和同伴间最好的经验来

13、决定下一步的运动轨迹。,6.2 粒子群算法的基本原理,6.2 粒子群算法的基本原理,6.2.3 标准PSO算法原理 1998年，Shi对传统PSO算法进行了修正，引入了惯性权重因子（也称为动量因子），得到 惯性权重因子的值较大，全局寻优能力强，但局部寻优能力弱；否则则反之。一般认为，惯性权重因子用于平衡全局和局部搜索能力，较大的倾向于全局搜索，较小的适用于局部搜索，因此惯性权重因子的取值应随时间逐渐减小。 初始时，Shi将惯性权重因子取为常数，但后来实验发现，动态值能够获得比固定值更好的寻优效果。既可以在搜索过程中线性变化，也可根据某个测度函数动态改变。但目前采用较多的是Shi建议的线性递减权

14、值。,6.2 粒子群算法的基本原理,6.2.4 PSO算法流程 Step1：初始化一群微粒（一般设种群规模为m），包括随机位置和速度。 Step2：评价每个微粒的适应度值。 Step3：将每个微粒的适应度值与其经过的最好位置pbest进行比较，如果较好则将其作为当前的最好位置pbest。 Step4：将每个微粒的适应度值与种群的最好位置gbest进行比较，如果较好则将其作为种群的最好位置gbest。 Step5：根据速度和位置公式调整粒子的飞行速度和所处位置。 Step6：判断是否达到结束条件，若未达到转到Step2。,6.2 粒子群算法的基本原理,6.2 粒子群算法的基本原理,6.2.5 全

15、局和局部最优PSO算法 目前关于全局和局部最优PSO算法的概念主要有两种。 概念一 全局最优PSO算法 在速度更新公式 中，pbest和gbest分别表示粒子群的局部和全局最优位置。当 时，粒子没有认知能力，变为只有社会的模型 称为全局最优PSO算法。,6.2 粒子群算法的基本原理,对于全局最优PSO算法，搜索空间能力强，缺少局部搜索，因此收敛速度较快，但对于复杂问题易陷入局部最优。 局部最优PSO算法 当 时，粒子间没有交流，即没有社会信息，只有自身的认知能力，变为认知模型 称为局部最优PSO算法。 对于局部最优PSO算法，由于个体之间没有信息交流，整个群体相当于多个粒子进行盲目的随机搜索，

16、因此收敛速度较慢，得到最优解的可能性较小。,6.2 粒子群算法的基本原理, 概念二 全局和局部最优主要考虑其邻域范围。 如果每个粒子的邻域是整个种群，其社会网络的拓扑结构为星状（即通信中的网孔型拓扑结构），任意两个粒子间均有联系，使得速度更新公式中的社会成分反映了种群中所有粒子的信息，即gbest是种群迄今为止发现的最好位置，则称为全局最优PSO算法。 如果每个粒子的邻域是其相邻的两个粒子，其社会网络的拓扑结构为环状。使得更新公式中的社会成分仅代表邻居之间的信息传递，反映了局部的环境知识，即gbest是几个粒子迄今为止发现的最好位置，则称为局部最优PSO算法。,6.2 粒子群算法的基本原理,目

17、前，PSO算法中的全局和局部最优PSO算法一般按此定义理解。,6.2 粒子群算法的基本原理,6.2.6 PSO算法参数分析 PSO算法中，参数设置主要有群体规模m、粒子维数及范围、惯性因子 、学习因子 、最大速率 和终止条件等。 群体规模 种群规模m一般取2040，对于大部分10个粒子即可获得满意效果，对于比较复杂的优化问题可以取到100200。 惯性因子 惯性因子 使粒子保持运动惯性，具有扩展搜索空间的能力。当 较大时，具有较强的全局搜索能力； 较小时具有较强的局部搜索能力。当 时，速度只取决于当前位置和历史最好位置，速度本身没有记忆性。,6.2 粒子群算法的基本原理,6.2 粒子群算法的基

18、本原理, 学习因子 学习因子 代表每个粒子向个体和全局最优位置靠拢的程度，一般取在04之间取值，大多取为 。 最大速率 最大速率 决定当前位置与最好位置之间的区域分辨率（精度）。如果太快，粒子有可能越过极小点；若果太慢，又有可能陷入局部极值区域。因此应适中。 粒子的维数 粒子维数由优化问题决定，就是问题解的长度。 粒子的范围 粒子范围也是由优化问题决定，每一维可以设定不同的范围。,6.2 粒子群算法的基本原理,6.2 粒子群算法的基本原理, 终止条件 终止条件由最大循环数或最小错误要求决定。,6.3 粒子群算法与其他算法的比较,6.3 粒子群算法与其他算法的比较 6.3.1 与遗传算法的比较

19、相同点 都属于仿生算法。PSO算法主要模拟鸟类觅食、认知等社会行为；GA算法主要借用生物进化中“适者生存”的规律。 都属全局优化方法。在解空间都随机产生初始种群，算法在全局解空间进行搜索，且将搜索重点集中在性能高的部分。 都属随机搜索算法。,6.3 粒子群算法与其他算法的比较, 隐含并行性。搜索过程都是从问题解的一个集合开始的，而不是从单个个体开始，具有隐含并行搜索特性，从而减小了陷入局部极小的可能性。 根据个体的适配信息进行搜索，因此不受函数约束条件的限制，如连续性、可导性等。 对高维复杂问题，往往会遇到早熟收敛和收敛性能差的缺点，都无法保证收敛到最优点。 不同点 PSO算法具有记忆功能，好

20、的解的知识所有粒子都保存；而GA算法中，以前的知识随着种群的改变而被破坏。,6.3 粒子群算法与其他算法的比较, PSO算法中，粒子仅仅通过当前搜索到的最优点进行共享信息，所以很大程度上这是一种单项信息共享机制。而GA算法中，染色体之间相互共享信息，使得整个种群都向最优区域移动。 GA算法的编码技术和遗传操作比较简单，而PSO算法没有交叉和变异操作，粒子只是通过内部速度进行更新，因此原理更简单、参数更少、实现更容易。 在收敛性方面，GA算法己经有了较成熟的收敛性分析方法，并且可对收敛速度进行估计。而PSO算法这方面的研究还比较薄弱。尽管己有简化确定性版本的收敛性分析，但将确定性向随机性的转化尚

21、需进一步研究。,6.3 粒子群算法与其他算法的比较, 在应用方面，PSO算法主要用于连续问题，包括神经网络训练和函数优化等，而GA算法除了连续问题之外，还可用于离散问题。 6.3.2 与蚁群算法（ACO）的比较 相同点 都属于仿生算法。PSO算法和ACO算法主要模拟觅食、认知等社会行为而提出。 都属全局优化方法。算法在全局的解空间进行搜索，且将搜索重点集中在性能高的部分。 都属随机搜索算法。 都具有记忆功能，好的解的知识所有粒子都保存。,6.3 粒子群算法与其他算法的比较, 隐含并行性。搜索过程是从问题解的一个集合开始的，而不是从单个个体开始，具有隐含并行搜索特性，从而减小了陷入局部极小的可能

22、性。并且由于这种并行性，易在并行计算机上实现，以提高算法性能和效率。 根据个体的适配信息进行搜索，因此不受函数约束条件的限制，如连续性、可导性等。 对高维复杂问题，往往会遇到早熟收敛和收敛性能差的缺点，都无法保证收敛到最优。 不同点 PSO算法是一种单项信息共享机制。而ACO算法中，每个个体只能感知局部的信息，不能直接使用全局信息。,6.3 粒子群算法与其他算法的比较, PSO算法相对于ACO算法，粒子只是通过内部速度进行更新，因此原理更简单、参数更少、实现更容易。 在收敛性方面，ACO算法己经有了较成熟的收敛性分析方法，并且可对收敛速度进行估计;而PSO算法这方面的研究还比较薄弱。尽管已经有简化确定性版本的收敛性分析，但将确定性向随机性的转化尚需进一步研究。 在应用方面，PSO算法主要应