粒子群优化算法PPT

智能控制课题报告粒子群优化算法ParticleSwarmOptimization目录CONTENT算法简介ALGORITHMINTRODUCTION01算法原理ALGORITHMPRINCIPLE02PSO和其他算法OTHERS03程序演示PROGRAMSHOW04算法简介ALGORITHMINTRODUCTION01粒子群算法设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢？最简单有效的就是搜寻目前离食物最近的鸟的周围区域。算法介绍01算法介绍01PSO产生背景之一:CAS我们把系统中的成员称为具有适应性的主体(AdaptiveAgent)，简称为主体。所谓具有适应性，就是指它能够与环境以及其它主体进行交流，在这种交流的过程中“学习”或“积累经验”，并且根据学到的经验改变自身的结构和行为方式。整个系统的演变或进化，包括新层次的产生，分化和多样性的出现，新的、聚合而成的、更大的主体的出现等等，都是在这个基础上出现的。即CAS（复杂适应系统）理论的最基本思想算法介绍01CAS的四个基本特点：首先，主体(AdaptiveAgent)是主动的、活的实体；其次，个体与环境(包括个体之间)的相互影响，相互作用，是系统演变和进化的主要动力；再次，这种方法不象许多其他的方法那样，把宏观和微观截然分开，而是把它们有机地联系起来；最后，这种建模方法还引进了随机因素的作用，使它具有更强的描述和表达能力。算法介绍01PSO产生背景之二：人工生命研究具有某些生命基本特征的人工系统。包括两方面的内容：1、研究如何利用计算技术研究生物现象；2、研究如何利用生物技术研究计算问题。我们关注的是第二点。已有很多源于生物现象的计算技巧，例如神经网络和遗传算法。现在讨论另一种生物系统---社会系统：由简单个体组成的群落和环境及个体之间的相互行为。Millonas在开发人工生命算法时(1994年)，提出群体智能概念并提出五点原则：1、接近性原则：群体应能够实现简单的时空计算；2、优质性原则：群体能够响应环境要素；3、变化相应原则：群体不应把自己的活动限制在一狭小范围；4、稳定性原则：群体不应每次随环境改变自己的模式；5、适应性原则：群体的模式应在计算代价值得的时候改变。算法介绍01社会组织的全局群行为是由群内个体行为以非线性方式出现的。个体间的交互作用在构建群行为中起到重要的作用。从不同的群研究得到不同的应用。最引人注目的是对蚁群和鸟群的研究。其中粒群优化方法就是模拟鸟群的社会行为发展而来。对鸟群行为的模拟：Reynolds、Heppner和Grenader提出鸟群行为的模拟。他们发现，鸟群在行进中会突然同步的改变方向，散开或者聚集等。那么一定有某种潜在的能力或规则保证了这些同步的行为。这些科学家都认为上述行为是基于不可预知的鸟类社会行为中的群体动态学。在这些早期的模型中仅仅依赖个体间距的操作，也就是说，这种同步是鸟群中个体之间努力保持最优的距离的结果。算法介绍01PSO（粒子群优化算法（ParticleSwarmOptimization），缩写为PSO）从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitnessvalue)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己。第一个就是粒子本身所找到的最优解，这个解叫做个体极值pBest。另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。算法介绍01PSO是近年来由J.Kennedy和R.C.Eberhart等开发的一种新的进化算法(EvolutionaryAlgorithm-EA)。PSO算法属于进化算法的一种，和模拟退火算法相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的“交叉”(Crossover)和“变异”(Mutation)操作，它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。粒子群算法是一种并行算法。算法原理ALGORITHMPRINCIPLE02抽象鸟被抽象为没有质量和体积的微粒(点)，并延伸到N维空间，粒子I在N维空间的位置表示为矢量Xi＝(x1，x2，…，xN)，飞行速度表示为矢量Vi＝(v1，v2，…，vN)．每个粒子都有一个由目标函数决定的适应值(fitnessvalue)，并且知道自己到目前为止发现的最好位置(pbest)和现在的位置Xi．这个可以看作是粒子自己的飞行经验．除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(gbest)(gbest是pbest中的最好值)．这个可以看作是粒子同伴的经验．粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。算法原理02PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个“极值”(pbest,gbest)来更新自己。在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。(1)式(2)式在式(1)、(2)中，i＝1，2，…，M，M是该群体中粒子的总数算法原理02Vi是粒子的速度；pbest和gbest如前定义；rand()是介于（0、1）之间的随机数；Xi是粒子的当前位置。c1和c2是学习因子，通常取c1＝c2＝2在每一维，粒子都有一个最大限制速度Vmax，如果某一维的速度超过设定的Vmax，那么这一维的速度就被限定为Vmax。（Vmax0）以上面两个公式为基础，形成了后来PSO的标准形式算法原理02从社会学的角度来看，公式(1)的第一部分称为记忆项，表示上次速度大小和方向的影响；公式第二部分称为自身认知项，是从当前点指向粒子自身最好点的一个矢量，表示粒子的动作来源于自己经验的部分；公式的第三部分称为群体认知项，是一个从当前点指向种群最好点的矢量，反映了粒子间的协同合作和知识共享。粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。以上面两个公式为基础，形成了后来PSO的标准形式算法原理02标准PSO算法的流程：Step1:初始化一群微粒(群体规模为m)，包括随机位置和速度；Step2:评价每个微粒的适应度；Step3:对每个微粒，将其适应值与其经过的最好位置pbest作比较，如果较好，则将其作为当前的最好位置pbest;Step4:对每个微粒，将其适应值与其经过的最好位置gbest作比较，如果较好，则将其作为当前的最好位置gbest;Step5:根据(2)、(3)式调整微粒速度和位置；Step6：未达到结束条件则转Step2。算法原理021998年shi等人在进化计算的国际会议上发表了一篇论文《Amodifiedparticleswarmoptimizer》对前面的公式(1)进行了修正。引入惯性权重因子。（3）式非负，称为惯性因子。公式(2)和(3)被视为标准pso算法。算法原理02算法原理02算法原理02迭代终止条件根据具体问题一般选为最大迭代次数Gk或(和)微粒群迄今为止搜索到的最优位置满足预定最小适应阈值算法原理02方程(2)和(3)中pbest和gbest分别表示微粒群的局部和全局最优位置，当C1＝0时，则粒子没有了认知能力，变为只有社会的模型(social-only):被称为全局PSO算法.粒子有扩展搜索空间的能力，具有较快的收敛速度，但由于缺少局部搜索，对于复杂问题比标准PSO更易陷入局部最优。算法原理02当C2＝0时，则粒子之间没有社会信息，模型变为只有认知(cognition-only)模型：被称为局部PSO算法。由于个体之间没有信息的交流，整个群体相当于多个粒子进行盲目的随机搜索，收敛速度慢，因而得到最优解的可能性小。算法原理02参数有：群体规模m，惯性因子，学习因子c1和c2最大速度Vmax，迭代次数Gk。群体规模m一般取20～40，对较难或特定类别的问题可以取到100～200。最大速度Vmax决定当前位置与最好位置之间的区域的分辨率(或精度)。如果太快，则粒子有可能越过极小点;如果太慢，则粒子不能在局部极小点之外进行足够的探索，会陷入到局部极值区域内。这种限制可以达到防止计算溢出、决定问题空间搜索的粒度的目的。算法原理02权重因子包括惯性因子和学习因子c1和c2。使粒子保持着运动惯性，使其具有扩展搜索空间的趋势，有能力探索新的区域。C1和c2代表将每个粒子推向Pbest和gbest位置的统计加速项的权值。较低的值允许粒子在被拉回之前可以在目标区域外徘徊，较高的值导致粒子突然地冲向或越过目标区域。算法原理02参数设置如果令c1＝c2＝0，粒子将一直以当前速度的飞行，直到边界。很难找到最优解。如果＝0，则速度只取决于当前位置和历史最好位置，速度本身没有记忆性。假设一个粒子处在全局最好位置，它将保持静止，其他粒子则飞向它的最好位置和全局最好位置的加权中心。粒子将收缩到当前全局最好位置。在加上第一部分后，粒子有扩展搜索空间的趋势，这也使得w的作用表现为针对不同的搜索问题，调整算法的全局和局部搜索能力的平衡。较大时，具有较强的全局搜索能力；较小时，具有较强的局部搜索能力。算法原理02通常设c1＝c2＝2。Suganthan的实验表明：c1和c2为常数时可以得到较好的解，但不一定必须等于2。Clerc引入收敛(constrictionfactor)K来保证收敛性。其中算法原理02通常取为4.1,则K＝0.729.实验表明，与使用惯性权重的PSO算法相比，使用收敛因子的PSO有更快的收敛速度。其实只要恰当的选取和c1、c2，两种算法是一样的。因此使用收敛因子的PSO可以看作使用惯性权重PSO的特例。恰当的选取算法的参数值可以改善算法的性能。算法原理02基本PSO是用于实值连续空间，然而许多实际问题是组合优化问题，因而提出离散形式的PSO。速度和位置更新式为：elsethen算法原理02PSO和其他算法OTHERS03PSO和其他算法02遗传算法和PSO的比较共性:(1)都属于仿生算法。(2)都属于全局优化方法。(3)都属于随机搜索算法。(4)都隐含并行性。(5)根据个体的适配信息进行搜索，因此不受函数约束条件的限制，如连续性、可导性等。(6)对高维复杂问题，往往会遇到早熟收敛和收敛性能差的缺点，都无法保证收敛到最优点。差异：(1)PSO有记忆，好的解的知识所有粒子都保存，而GA以前的知识随着种群的改变被改变。(2)PSO中的粒子仅仅通过当前搜索到最优点进行共享信息，所以很大程度上这是一种单共享项信息机制。而GA中，染色体之间相互共享信息，使得整个种群都向最优区域移动。(3)GA的编码技术和遗传操作比较简单，而PSO相对于GA，没有交叉和变异操作，粒子只是通过内部速度进行更新，因此原理更简单、参数更少、实现更容易。选题背景02PSO和ANNGA可以用来研究ANN的三个方面：网络连接权重、网络结构、学习算法。优势在于可处理传统方法不能处理的问题，例如不可导的节点传递函数或没有梯度信息。缺点:在某些问题上性能不是特别好；网络权重的编码和遗传算子的选择有时较麻烦。已有利用PSO来进行神经网络训练。研究表明PSO是一种很有潜力的神经网络算法。速度较快且有较好的结果。且没有遗传算法碰到的问题。PSO和其他算法02选题背景02蚁群算法蚁群算法（AntColonyOptimization,ACO）由Colorni，Dorigo和Maniezzo在1991年提出，它是通过模拟自然界蚂蚁社会的寻