群智能及粒子群优化算法课件.ppt

1、群智能理论及粒子群优化算法Swarm Intelligence Swarm Intelligence (SI)的概念最早由Beni、Hackwood和在分子自动机系统中提出。分子自动机中的主体在一维或二维网格空间中与相邻个体相互作用，从而实现自组织。1999年，Bonabeau、Dorigo和Theraulaz 在他们的著作Swarm Intelligence: From Natural to Artificial Systems中对群智能进行了详细的论述和分析，给出了群智能的一种不严格定义：任何一种由昆虫群体或其它动物社会行为机制而激发设计出的算法或分布式解决问题的策略均属于群智能。 Swa

2、rm Intelligence(续) Swarm可被描述为一些相互作用相邻个体的集合体，蜂群、蚁群、鸟群都是Swarm的典型例子。鱼聚集成群可以有效地逃避捕食者，因为任何一只鱼发现异常都可带动整个鱼群逃避。蚂蚁成群则有利于寻找食物，因为任一只蚂蚁发现食物都可带领蚁群来共同搬运和进食。一只蜜蜂或蚂蚁的行为能力非常有限，它几乎不可能独立存在于自然世界中，而多个蜜蜂或蚂蚁形成的Swarm则具有非常强的生存能力，且这种能力不是通过多个个体之间能力简单叠加所获得的。社会性动物群体所拥有的这种特性能帮助个体很好地适应环境，个体所能获得的信息远比它通过自身感觉器官所取得的多，其根本原因在于个体之间存在着信息

3、交互能力。 Swarm Intelligence(续) 信息的交互过程不仅仅在群体内传播了信息，而且群内个体还能处理信息，并根据所获得的信息（包括环境信息和附近其它个体的信息）改变自身的一些行为模式和规范，这样就使得群体涌现出一些单个个体所不具备的能力和特性，尤其是对环境的适应能力。这种对环境变化所具有适应的能力可以被认为是一种智能（关于适应性与智能之间的关系存在着一些争议，Fogel认为智能就是具备适应的能力），也就是说动物个体通过聚集成群而涌现出了智能。因此，Bonabeau 将SI的定义进一步推广为：无智能或简单智能的主体通过任何形式的聚集协同而表现出智能行为的特性。这里我们关心的不是个

4、体之间的竞争，而是它们之间的协同。 Swarm Intelligence(续) James Kennedy和Russell C.Eberhart在2001年出版了Swarm Intelligence，是群智能发展的一个重要历程碑，因为此时已有一些群智能理论和方法得到了应用。他们不反对Bonabeau关于SI定义，赞同其定义的基本精神，但反对定义中使用“主体”一词。其理由是“主体”所带有自治性和特殊性是许多Swarm的个体所不具备和拥有的，这将大大限制Swarm的定义范围。他们认为暂时无法给出合适的定义，赞同由Mark Millonas（1994）提出的构建一个SI系统所应满足的五条基本原则：

5、Swarm Intelligence(续)1 Proximity Principle: 群内个体具有能执行简单的时间或空间上的评估和计算的能力。2 Quality Principle: 群内个体能对环境（包括群内其它个体）的关键性因素的变化做出响应。 3 Principle of Diverse Response: 群内不同个体对环境中的某一变化所表现出的响应行为具有多样性。 4 Stability Principle: 不是每次环境的变化都会导致整个群体的行为模式的改变。5 Adaptability Principle: 环境所发生的变化中，若出现群体值得付出代价的改变机遇，群体必须能够改变

6、其行为模式。Swarm Intelligence(续) Swarm Intelligence最重要的观点是：Mind is social，也就是认为人的智能是源于社会性的相互作用，文化和认知是人类社会性不可分割的重要部分，这一观点成为了群智能发展的基石。群智能已成为有别于传统人工智能中连接主义和符号主义的一种新的关于智能的描述方法。 群智能的思路，为在没有集中控制且不提供全局模型的前提下寻找复杂的分布式问题求解方案提供了基础。在计算智能领域已取得成功的两种基于SI的优化算法是蚁群算法和粒子群算法。Swarm Intelligence(续) 目前，已有的基于SI的优化算法都是源于对动物社会通过协

7、作解决问题行为的模拟，它主要强调对社会系统中个体之间相互协同作用的模拟。这一点与EC不同，EC是对生物演化中适者生存的模拟。与EC一样的是，SI的目的并不是为了忠实地模拟自然现象，而是利用他们的某些特点去解决实际问题。另一个与EC的相同点是,基于SI的优化算法也是概率搜索算法。Swarm Intelligence(续) 目前，已有的群智能理论和应用研究证明群智能方法是一种能够有效解决大多数优化问题的新方法，更重要是,群智能潜在的并行性和分布式特点为处理大量的以数据库形式存在的数据提供了技术保证。无论是从理论研究还是应用研究的角度分析,群智能理论及应用研究都是具有重要学术意义和现实价值的。Swa

8、rm Intelligence(续) 由于SI的理论依据是源于对生物群落社会性的模拟，因此其相关数学分析还比较薄弱，这就导致了现有研究还存在一些问题。首先，群智能算法的数学理论基础相对薄弱，缺乏具备普遍意义的理论性分析，算法中涉及的各种参数设置一直没有确切的理论依据，通常都是按照经验型方法确定，对具体问题和应用环境的依赖性比较大。其次，同其它的自适应问题处理方法一样，群智能也不具备绝对的可信性，当处理突发事件时,系统的反应可能是不可测的,这在一定程度上增加了其应用风险。另外,群智能与其它各种先进技术(如:神经网络、模糊逻辑、禁忌搜索和支持向量机等) 的融合还不足。 蚁群算法 蚁群算法（Ant

9、Colony Optimization, ACO）由Colorni，Dorigo和Maniezzo在1991年提出，它是通过模拟自然界蚂蚁社会的寻找食物的方式而得出的一种仿生优化算法。自然界种蚁群寻找食物时会派出一些蚂蚁分头在四周游荡，如果一只蚂蚁找到食物，它就返回巢中通知同伴并沿途留下“信息素”（pheromone） 作为蚁群前往食物所在地的标记。 信息素会逐渐挥发，如果两只蚂蚁同时找到同一食物，又采取不同路线回到巢中，那么比较绕弯的一条路上信息素的气味会比较淡，蚁群将倾向于沿另一条更近的路线前往食物所在地。蚁群算法(续) ACO算法设计虚拟的“蚂蚁”，让它们摸索不同路线，并留下会随时间逐渐

10、消失的虚拟“信息素”。根据“信息素较浓的路线更近”的原则，即可选择出最佳路线。 目前，ACO算法已被广泛应用于组合优化问题中，在图着色问题、车间流问题、车辆调度问题、机器人路径规划问题、路由算法设计等领域均取得了良好的效果。也有研究者尝试将ACO算法应用于连续问题的优化中。由于ACO算法具有广泛实用价值，成为了群智能领域第一个取得成功的实例，曾一度成为群智能的代名词，相应理论研究及改进算法近年来层出不穷。 蚁群算法(续)其它群智能优化算法 目前，还有一些不成熟的群智能优化算法，国内值得关注的有以下几种。v2003年李晓磊、邵之江等提出的鱼群算法，它利用自上而下的寻优模式模仿自然界鱼群觅食行为，

11、主要利用鱼的觅食、聚群和追尾行为，构造个体底层行为；通过鱼群中各个体的局部寻优，达到全局最优值在群体中凸现出来的目的。在基本运算中引入鱼群的生存机制、竞争机制以及鱼群的协调机制，提高算法的有效效率。其它群智能优化算法（续） 张玲等则提出了一种“松散的脑袋”群智能模型，采用特殊的随机人工神经网络构建了一种群智能数学模型。每个神经元被看成一个主体，主体之间的通讯连接看成各神经元之间的连接，但连接是随机而不是固定的，即用一个随机连接的神经网络来描述一个群体，这种神经网络来描述一个群体。显然这种神经网络具有群体的智能。 基于群智能的优化算法设计必须遵守简单有效的原则，对于自然现象过于复杂的模拟往往会导

12、致算法不具有推广性和实用价值，许多群智能算法不成功的原因就在于此。 优化问题简介 粒子群算法(particle swarm optimization，PSO)由Kennedy和Eberhart在1995年提出，该算法模拟鸟集群飞行觅食的行为，鸟之间通过集体的协作使群体达到最优目的，是一种基于Swarm Intelligence的优化方法。同遗传算法类似，也是一种基于群体叠代的，但并没有遗传算法用的交叉以及变异，而是粒子在解空间追随最优的粒子进行搜索。PSO的优势在于简单容易实现同时又有深刻的智能背景，既适合科学研究，又特别适合工程应用，并且没有许多参数需要调整。 PSO算法简介 James K

13、ennedy received the Ph.D. degree from theUniversity of North Carolina, Chapel Hill, in 1992.He is with the U.S. Department of Labor, Washington,DC. He is a Social Psychologist who has been working with the particle swarm algorithm since 1994. He has published dozens of articles and chapters on parti

14、cle swarms and related topics, in computer science and social science journals and proceedings. He is a coauthor of Swarm Intelligence (San Mateo, CA: Morgan Kaufmann, 2001), with R.C. Eberhart and Y. Shi, now in its third printing.Russell C. Eberhart (M88SM89F01) received the Ph.D. degree in electr

15、ical engineering from Kansas State University, Manhattan.He is the Chair and Professor of Electrical and Computer Engineering, Purdue School of Engineering and Technology, Indiana UniversityPurdue University Indianapolis (IUPUI),Indianapolis, IN. He is coeditor of Neural Network PC Tools(1990),coaut

16、hor of Computational Intelligence PC Tools (1996), coauthor of Swarm Intelligence(2001), Computational Intelligence: Concepts to Implementations(2004). He has published over 120 technical papers.Dr. Eberhart was awarded the IEEE Third Millenium Medal. In 2002, he became a Fellow of the American Inst

17、itute for Medical and Biological Engineering.近年PSO方面文献的数量PSO产生背景之一：复杂适应系统CAS理论的最基本的思想可以概述如下理论的最基本的思想可以概述如下： 我们把系统中的成员称为具有适应性的主体(Adaptive Agent)，简称为主体。所谓具有适应性，就是指它能够与环境以及其它主体进行交流交流，在这种交流的过程中“学习”或“积累经验”，并且根据学到的经验改变自身的结构和行为方式。整个系统的演变或进化，包括新层次的产生，分化和多样性的出现，新的、聚合而成的、更大的主体的出现等等，都是在这个基础上出现的。 复杂适应系统（CAS）续CA

18、S的四个基本特点：的四个基本特点：v首先，首先，主体(Adaptive Agent)是主动的、活的实体； v其次，其次，个体与环境(包括个体之间)的相互影响，相互作用，是系统演变和进化的主要动力；v再次，再次，这种方法不象许多其他的方法那样，把宏观和微观截然分开，而是把它们有机地联系起来；v最后，最后，这种建模方法还引进了随机因素的作用，使它具有更强的描述和表达能力。 PSO产生背景之二:人工生命 人工生命“是来研究具有某些生命基本特征的人工系统。人工生命包括两方面的内容： 研究如何利用计算技术研究生物现象； 研究如何利用生物技术研究计算问题(Nature Computation)。 我们现在

19、关注的是第二部分的内容。现在已经有很多源于生物现象的计算技巧，例如, 人工神经网络是简化的大脑模型. 遗传算法是模拟基因进化过程的。现在我们讨论另一种生物系统：社会系统，更确切地说，是由简单个体组成的群落与环境以及个体之间的互动行为，也可称做群智能。基本PSO算法 粒子群优化算法源于1987年Reynolds对鸟群社会系统boids的仿真研究，boids是一个CAS。在boids中，一群鸟在空中飞行，每个鸟遵守以下三条规则：1）避免与相邻的鸟发生碰撞冲突；2）尽量与自己周围的鸟在速度上保持协调和一致；3）尽量试图向自己所认为的群体中靠近。 仅通过使用这三条规则，boids系统就出现非常逼真的群

20、体聚集行为，鸟成群地在空中飞行，当遇到障碍时它们会分开绕行而过，随后又会重新形成群体。 基本PSO算法（续） Reynolds仅仅将其作为CAS的一个实例作仿真研究，而并未将它用于优化计算中 。 Kennedy和Eberhart在中加入了一个特定点，定义为食物，鸟根据周围鸟的觅食行为来寻找食物。他们的初衷是希望通过这种模型来模拟鸟群寻找食源的现象，然而实验结果却揭示这个仿真模型中蕴涵着很强的优化能力，尤其是在多维空间寻优中。 基本PSO算法(续) PSO中，每个优化问题的解都是搜索空间中的一只鸟。称之为“粒子(Particle)”。所有的粒子都有一个由被优化的函数决定的适应值，每个粒子还有一个

21、速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索. PSO 初始化为一群随机粒子。然后通过叠代找到最优解。在每一次叠代中，粒子通过跟踪两个极值来更新自己。第一个就是粒子本身所找到的最优解。这个解叫做个体极值pBest. 另一个极值是整个种群目前找到的最优解。这个极值是全局极值gBest。另外,也可以不用整个种群而只是用其中一部分的邻居。基本PSO算法(续) PSO算法数学表示如下： 设搜索空间为D维，总粒子数为n。第i个粒子位置表示为向量Xi=( xi1, xi2, xiD )；第i个粒子 “飞行”历史中的过去最优位置（即该位置对应解最优）为Pi=( pi1,pi2,

22、piD )，其中第g个粒子的过去最优位置Pg为所有Pi ( i=1, ,n)中的最优；第i个粒子的位置变化率（速度）为向量Vi=(vi1, vi2, viD)。每个粒子的位置按如下公式进行变化（“飞行”）：基本PSO算法(续)12(1)( )( )( )( )( )( )( )ididididgdidvtwvtcrandptxtcrandptxt(1 )()(1 )11idididxtxtvtindD（1）（2）其中，C1,C2为正常数，称为加速因子；rand( )为0，1之间的随机数；w称惯性因子，w较大适于对解空间进行大范围探查(exploration)，w较小适于进行小范围开挖(expl

23、oitation)。第d（1dD）维的位置变化范围为-XMAXd , XMAXd，速度变化范围为-VMAXd , VMAXd，迭代中若位置和速度超过边界范围则取边界值。 基本PSO算法(续) 粒子群初始位置和速度随机产生，然后按公式(1)(2)进行迭代，直至找到满意的解。目前，常用的粒子群算法将全体粒子群(Global)分成若干个有部分粒子重叠的相邻子群，每个粒子根据子群(Local)内历史最优Pl调整位置，即公式(2)中Pgd换为Pld。 PSO与与EC的异同的异同 首先，PSO和EC所模拟的自然随机系统不一样。EC是模拟生物系统进化过程，其最基本单位是基因，它在生物体的每一代之间传播；而P

24、SO模拟的是社会系统的变化，其最基本单位是“敏因”（Meme），这一词由Dawkin在The Selfish Gene一书中提出，它是指思想文化传播中的基本单位，个体在社会中会根据环境来改变自身的思想，Meme的传播途径是在个体与个体之间，在实际人类社会中它还可以在人脑与书本之间、人脑与计算机、计算机与计算机之间传播。 PSO与与EC的异同（续）的异同（续） 其次，EC中强调“适者生存”，不好的个体在竞争中被淘汰；PSO强调“协同合作”，不好的个体通过学习向好的方向转变，不好的个体被保留还可以增强群体的多样性。EC中最好的个体通过产生更多的后代来传播自己的基因，而PSO中的最佳个体通过吸引其它

25、个体向它靠近来传播自己的敏因。PSO与与EC的异同（续）的异同（续） 再次，EC中的上一代到下一代转移概率只与上一代的状态相关，而与历史无关，它的个体只包含当前信息，其群体的信息变化过程是一个Markov链过程；而PSO中的个体除了有着位置和速度外，还有着过去的历史信息（pBest、gBest），也就是具有记忆能力，上一代到下一代转移概率不仅与上一代的状态相关，而且与过去的历史相关，如果仅从群体的位置及速度信息来看，群体的信息变化过程不是一个Markov链过程。 PSO与与EC的异同（续）的异同（续） 最后，EC的迭代由选择、变异和交叉重组操作组成，而PSO的迭代中的操作是“飞行”。在某种程度

26、上看，PSO的操作中隐含了选择、变异和交叉重组操作，gBest和pBest的更新可以类似一种弱选择；而粒子位置更新则类似于3个父代：Xi、gBest和pBest的之间重组，其中还包含了变异的成分。PSO中所隐含的变异是有偏好的，而并非通常的完全随机变异，这与最近对实际生物系统变异行为的新研究成果相符。PSO与与EC的异同（续）的异同（续） EC和PSO所分别模拟的两个伟大的自然随机系统：Evolution和Mind之间存在着显著的差异，尽管它们都是基于群体的，都是由其中的随机成分带来创新，但其本质是不同的，因此不能将PSO简单地归类于EC中。 Particle Swarm研究热点 IEEE T

27、RANSACTION ON EVOLUTIONARY COMPUTION于2004年出版了第3卷：SPECIAL ISSUE ON PSO。Russell C.Eberhart, Yuhui Shi在卷首语中指出了当前PSO研究的几个主要方向及热点：1。算法分析；2。粒子群拓扑结构；3。参数选择与优化；4。与其他演化计算的融合；5。应用。粒子运动轨迹的分析 为了便于分析和表达，首先将问题空间简化为一维的，分别用 、 表示式（2.5）中的 和 ，仅研究粒子群中的某一个粒子i的运动过程，并暂时先假设pBest、gBest在粒子i运动过程中不变，于是可得粒子i运动的状态方程组（3.1）和（3.2），

28、这将是本节分析和讨论的对象。 （3.1） （3.2） 121()crand2()crand12(1)( )( )( )iiiigiv twv tpx tpx t(1)( )(1)iiix tx tv t粒子运动轨迹的分析（续） 将式（3.1）和（3.2）递推可得到： （3.4） （3.6） 由上可知，粒子的速度和位置变化过程均是二阶差分方程，本节将对它们做分析。12(2)(1)(1)( )0iv twv twv t1212(2)(1)(1)( )iiiigx twx twx tpp粒子运动轨迹的分析（续） 对（3.4）做Z变换，由Routh判据，二阶线性系统稳定的充分必要条件是特征方程各项系数

29、均为正值，于是可得到差分方程（3.4）稳定的条件为（取某一个条件等号时系统系统等幅周期振荡，速度不趋于无穷大，此处可认为临界稳定） （3.14）121022ww粒子运动轨迹的分析（续） 当满足（3.14）中条件均取严格不等号时，由Z变换的终值定理可得： （3.15） 也就是在不考虑随机量且pBest、gBest位置不变的假设下，当满足（3.14）中严格不等于条件时，单个粒子的速度将趋向0。 1( )lim(1)( )0iizv tzVz粒子运动轨迹的分析（续） 同理，对（3.6）做Z变换，由Routh判据，可得到差分方程（3.6）稳定的条件为： （3.25）121022ww粒子运动轨迹的分析（

30、续） 当满足条件（3.25），由Z变换的终值定理可得： （3.26） 这说明，在不考虑随机量且pBest、gBest位置不变的假设下，当满足式（3.25）中条件时，单个粒子的位置将趋向 12112( )lim(1)( )igiizppx tzXz1212igpp粒子运动轨迹的分析（续） 本文以上分析方法所得到的结果（3.25）式与文献9所得的最终结果（2.8）式不一致，图3.1给出两种不同约束条件所得到的范围，细斜线左上方的灰色区域为本文所得到的单个粒子可收敛区域，而文献9中（2.8）式所对应的仅是粗实线上所有的点，显然本文约束条件（3.25）式所得的范围比文献9的范围大很多，并包含了文献9的

31、范围，而文献9约束条件（2.8）式的表达要比式（3.25）复杂些。粒子运动轨迹的分析（续）图3.1 两种不同约束条件得到的范围 粒子运动轨迹的分析（续） pBest、gBest分别代表粒子的“自身经验”和“社会经验”，粒子通过它们和群体实现协同合作，因此其变化是不可忽视的。这个系统的输入的变化过程是未知的，而且与粒子本身的运动过程还存在着弱反馈关系，那么式（3.26）所给出的粒子最终位置是否仅是一种理想状态的结果呢？ 当pBest、gBest发生变化时，粒子的位置是否能跟踪上是不肯定的。粒子运动轨迹的分析（续） pBest和gBest的变化过程符合如下式（3.27）（3.28）的规律： （3.

32、27） （3.28） 都是递减的，而且当优化问题的值空间有限且存在全局最优值时候，它们存在下界。 ( )( )( )(1)( )( )( )iiiiiiip tif f x tf p tp tx tif f x tf p t( )()( )(1)()( )ggggp tif f GNewOptiumf p tp tGNewOptium if f GNewOptiumf p t( ),( )igf p tf p tinf( )inf( )()igt nt nf p tf p tf GobalOptium粒子运动轨迹的分析（续） 若f(x)不是2.2.3节（NFL定理）中所说的欺骗函数和随机函数，

33、而是第三类函数，而且f(pi(t),f(Pg(t)的变化pi(t),pg(t)与的变化之间存在着类似梯度信息的规律。那么当搜索时间无限时， f(pi(t),f(Pg(t)和pi(t),pg(t)在粒子群搜索的初期过程中会变化比较剧烈，随后pi(t),pg(t)将逐步逼近某个值，而f(pi(t), f(Pg(t)也将趋于稳定或停滞，因此系统后期的输入pi(t),pg(t)可以被看作是一个阶跃函数，在不考虑随机成分的情况下系统的输出将能够跟踪上 1212()()igp tp t 粒子运动轨迹的分析（续） 粒子群在多数实际寻优过程中无论是找到了最优解或是陷入某个局部最优解，还是算法停滞，整个过程中的

34、gBest变化将会逐步减小，最终趋于停止，pBest将逐步趋向gBest。因此当搜索时间无限时，所有粒子的位置将逐步靠近并停止于 处。1212( )( )( )iggp tp tp t粒子运动轨迹的分析（续） 在随机启发式优化算法中随机量的作用是非常重要的，正是随机量所带来的不确定性给整个粒子群带来了多样性和创新。去掉随机量后，单个粒子的运动过程成为了一个二阶线性系统，使得分析变得比较简单，但这个便于分析的假设条件使得以上对粒子运动行为的分析具有很大的局限性。下面将进一步讨论随机量对粒子运动行为的影响。粒子运动轨迹的分析（续） 为便于分析，式（3.22）中初始值取 ，并对也取Z变换可得到： （

35、3.30） 不考虑 与 之间存在的弱反馈关系，式（3.30）所对应的系统如图3.8所示。 (0)(1)0iixx12212( )( )( )(1)(1)igizP zPzXzzw zwz( ),( )igP z P z( )iXz粒子运动轨迹的分析（续）粒子运动轨迹的分析（续） 由仿真实例可以看出，当PSO参数不满足式（3.25）的条件时，粒子的运动轨迹也可能收敛到 ；而当PSO参数满足式（3.25）的条件时，粒子的运动轨迹却不一定能保证收敛到一个固定位置。显然，随机性的存在使得粒子运动轨迹是否收敛到一个固定点并不完全遵照式（3.25）所给出的规律。 1212( )( )igp tp t粒子运

36、动轨迹的分析（续） 实验研究发现，粒子群中粒子运动轨迹收敛到固定点的概率与参数选择存在着密切关系。当参数不满足式（3.25）所给出条件时，绝大多数粒子的运动轨迹都是不收敛到一个固定点的，除了一些特例，例如粒子群中某个粒子找到全局最优解，且当前速度为0，则该粒子运动轨迹肯定收敛。当参数满足式（3.25）所给出条件时，参数越接近条件的边界粒子运动轨迹收敛的几率越小，反之越大。一般而言，w越大不收敛的概率越大，c1、c2越大不收敛的概率越大，其中w的影响更大些。 另外，粒子运动轨迹不收敛到固定点时，其振荡幅值与参数选择也存在着密切关系。当参数不满足式（3.25）时，振荡幅值很大，甚至发散；满足式（3

37、.25）时，振荡幅值要小许多，且振荡的幅值在一定范围内，在某种意义上粒子处于广义稳定状态，这样的状态对粒子群的搜索是有益的。其中w越大振荡幅值越大，c1、c2越大振荡幅值越大，其中的影响更大些。 粒子运动轨迹的分析（续） 粒子群中的粒子运动轨迹处于发散振荡状态显然是对算法收敛无益的，而处于幅值有限的振荡状态对算法是有非常重要的作用。粒子运动轨迹振荡幅值很大时可以看作是算法的开拓能力强，而当粒子轨迹振荡幅值较小时则是开掘能力强。是否能通过PSO参数的选择来调整粒子运动轨迹的振荡幅值呢？ 粒子运动轨迹的分析（续）粒子运动轨迹的分析（续） 若PSO参数一直满足条件（3.25）,则粒子运动轨迹振荡的幅

38、值是有限的。这个二阶振荡环节的阻尼系数为： （3.32） 二阶振荡系统的阻尼系数越小，系统振荡的幅值越大。式（3.32）表明，尽管存在随机量，但通过选择和调节PSO参数还是可以对粒子的振荡幅值实现控制的。 12121() 22ww粒子运动轨迹的分析（续） 以上讨论说明，条件（3.25）还是非常有意义的。针对优化问题的特点，通过式（3.25）和（3.32）可以选择合理的PSO参数，调整粒子运动轨迹的振荡幅值使得粒子群的开拓能力和开掘能力均能得到兼顾，从而可提高算法的成功率。另外，还可以在运算过程中动态地改变参数，使得粒子的运动的振荡幅度由大到小，在搜索的前期粒子更多地体现开拓能力，而后期粒子更多

39、地发挥开掘能力。因此，式（3.25）和（3.32）是有重要价值的，有助于实际应用PSO算法参数择和使用的理论公式和条件。 粒子运动轨迹的分析（续）PSO算法收敛性分析 随机算法收敛的标准随机算法收敛的标准 对于优化问题 ，有随机优化算法D，第k次迭代的结果XK，下一次迭代的结果为 ，其中 是算法D这次迭代中曾经搜索过的解。 条件条件H1： ，且若 ，则有 。 条件H1可保证随机算法的正确性，其目的是希望能保证优化算法的解的适应度值是非递增的。, fA(,)Dk+1kxx(,)()fDfxxA(,)()fDfxPSO算法收敛性分析(续)条件条件H2：对 ，有： 。 其中 为算法第k次迭代的结果在

40、集合B上的概率测度。算法满足条件H2意味着，A中任意满足 的子集B，算法D连续无穷次未搜索到A中点的几率为0。因为 ，那么满足条件的算法连续无穷次搜索不到近似全局最优点的概率为0。条件条件H3：对 ， 为紧集，且 ， 和 ，有：,. .0s t vBAB0(1 )0kkuB ku B 0vB,MRA0Ax0|( )()ff0LAxxx0 (0,1 . .s tk 0Lx( ,),)( ,)( ,)kudist DdistD,M,M,MRRRxxxPSO算法收敛性分析(续) 定理定理3.1（算法全局收敛）：（算法全局收敛）：假设f是可测度的，可行解空间A是Rn上可测度的子集，算法D满足条件(H1

41、)(H2)， 是算法D产生数列，则有： 定理定理3.2（算法局部收敛）（算法局部收敛）：假设f是可测度的，可行解空间A是Rn上可测度的子集，算法满足条件(H1)(H3)， 是算法D产生数列，则有：0kkxlim1kPk,MRx0kkxlim1kPk,MRxPSO算法收敛性分析(续) 定义定义3.1（粒子状态和粒子状态空间）（粒子状态和粒子状态空间） 粒子的位置x，速度v以及历史最佳位置p（pBest）构成粒子的状态O=(x,v,p)，简称粒子，其中x,p在可行解集A中，且x,pA,在速度范围vmin,vmax内。所有可能的粒子状态的集合构成粒子状态空间 简称粒子空间。 定义定义3.2（粒子群状

42、态和粒子群状态空间）（粒子群状态和粒子群状态空间）粒子群中所有N个粒子的状态的集合称为粒子群状态，简称粒子群 。所有可能的粒子群状态的集合构成粒子群状态空间 。 minmax( , ,) |,()( ),Ox v px pfpf xvvvOA12(,)NSO OO12(,),(1)NiSO OOOiNSOPSO算法收敛性分析(续)定义定义3.3（粒子群等价）（粒子群等价） 对于 ，记 ，其中 表示事件A的示性函数， 表示粒子群状态中包含粒子状态的数目。若有两个粒子群 ，对于 ，若有 ，则称S1和S2等价，记作 。定理定理3.3 “”是S上的等价关系。 ,SOSS1( ,)()NiOiS OOA

43、( , )S O1, 2S S SOO( 1,)( 2,)S OSOPSO算法收敛性分析(续)v定义定义3.4（粒子群状态等价类）（粒子群状态等价类）由等价关系“”在S上诱导的粒子群状态等价类记作L=/S，简称粒子群等价类。 v定理定理3.4 等价关系“”在S上诱导的等价类划分L=/S的个数为： | 1| 1(|1)!()! (|1)!NNLCNOOOOPSO算法收敛性分析(续)v定理定理3.13 在数字计算机实现的标准PSO算法中，粒子群状态序列 是有限齐次Markov链。v定理定理3.14 在数字计算机实现的标准PSO算法中，粒子群等价类状态序列 是有限齐次Markov链。 ( );0S

44、t t ( );0L t t PSO算法收敛性分析(续)v定义定义3.19（最优粒子状态集）（最优粒子状态集） 设优化问题 的全局最优解为 ，定义粒子最优状态集 。v定义定义3.20（最优粒子群状态集）（最优粒子群状态集） 设优化问题 的全局最优解为 ，定义最优粒子群状态集 。 , fA*g*( , , )| ( )( ),Ox v pf pf gOMO, fA*g12( , , ,)|,1NiSOOOOi N GMPSO算法收敛性分析(续)v定理定理 3.17 PSO算法中，对粒子群状态序列 而言，最优粒子群状态集合G是状态空间S上的一个闭集。v定理定理3.19 当 时，状态空间S中至少存在

45、一个G之外的闭集，即 ( );0S t t GS, BS BG BGPSO算法的收敛性分析（续）SGBPSO算法收敛性分析(续)v定理定理3.20 当 时，PSO算法是无法保证全局收敛的。v定理定理 3.21当 时，PSO算法是无法保证局部收敛的。 尽管PSO算法是无法保证收敛的，但这并不意味着PSO算法的性能不好。本节研究结果的意义首先可用于指导算法的改进。同时，本节所提出的方法更是为PSO算法的理论分析和研究提供了一种新的思路，可在此基础上对PSO算法的进一步的理论研究。 GSGSPSO理论分析的其它可能方法理论分析的其它可能方法 目前，能对PSO算法进行理论分析的有效数学手段还很少，本文

46、了提出的两个新的分析手段，在微观上采用差分方程，在宏观上采用Markov链。除此之外，是否还存在其它的分析方法和手段呢？根据对其它随机算法讨论和分析的经验以及PSO算法的特点，下面对其它可能的分析方法和手段作简单的讨论。 随机过程中的其它方法随机过程中的其它方法 本文采用了随机过程中的Markov链方法对PSO算法做分析。但如果独立分析粒子群的位置转换序列，它显然不是一个Markov链，是否可以采用随机过程中的其它方法直接对进行分析呢？例如，可以把粒子的运动看成一个随机变量，它的变化都有着一定的确定性，也存在着一定的不确定性，能否用熵或相对熵来描述粒子运动离散分布的不确定性的大小，从而对算法的

47、收敛率做分析呢？随机过程中的其它可能方法（续）随机过程中的其它可能方法（续） 另外，就PSO算法迭代的随机过程而言，总是希望这个过程在期望值意义下越来越好，这自然应当是一个下鞅序列，因此可利用鞅收敛定理就可对算法的收敛性进行分析。同时也可以看到，要保证算法的收敛，有两个参数很重要：一个是过程进入满意解之后下一步脱离满意解的可能性；另一个是未进入满意解时下一步仍不能进入满意解的可能性。利用这种方法得到结果可能直观而且简练，也许对如何改进PSO算法会有重要指导意义。 基于混沌动力学理论基于混沌动力学理论 一个好的PSO系统既非稳定态也非混沌态，而是一种处于两者之间临界态的自组织复杂系统。从系统工程

48、的角度而言，PSO应该是一个连续的非线性动态系统，因此将复杂系统的研究方法，将混沌理论中的非线性动力学引入PSO的分析和改进研究应该是非常有前途的。 基于混沌动力学理论（续）基于混沌动力学理论（续） 此类分析方法能充分体现PSO系统中粒子间的相互作用的意义和随机性的价值。但如何采用混沌动力学理论来描述粒子群系统也存在一些困难，如何定义PSO系统中的吸引子、轨道、分叉和稳定性等概念都是要解决的问题。另外，非线性系统的稳定性只能针对某个解来谈的，而不能一般地讨论系统的稳定性，而且系统的稳定性与优化算法的收敛性之间存在什么样的关系也是未知的，因此如何通过这类方法来分析算法的收敛性和性能是目前是未知的

49、。 二维图元约束布局优化 A total number of n circular dishes with uniform thickness and mass distribution will be located on a circular bearing plate with a radius R as shown in Fig. 1. Suppose ri and mi (iI) are the radius and mass of the i th dish, respectively. Fig.1. Schematic Layout Pattern The basic probl

50、em is to find the position of each dish so that all the dishes can highly concentrate to the center of the bearing plate while the following conditions exist. (a) No overlap exists between any two dishes. (b) No dish protrudes out of the bearing plate. (c) The static equilibrium error of the whole s