《粒子群优化算法PPT.ppt》由会员分享，可在线阅读，更多相关《粒子群优化算法PPT.ppt（40页珍藏版）》请在三一办公上搜索。
1、,目录,CONTENT,算法简介,ALGORITHM INTRODUCTION,01,粒子群算法,设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢？最简单有效的就是搜寻目前离食物最近的鸟的周围区域。,PSO产生背景之一:CAS 我们把系统中的成员称为具有适应性的主体(Adaptive Agent)，简称为主体。所谓具有适应性，就是指它能够与环境以及其它主体进行交流，在这种交流的过程中“学习”或“积累经验”，并且根据学到的经验改变自身的结构和行为方式。整个系统的演变或进化，包括新层次
2、的产生，分化和多样性的出现，新的、聚合而成的、更大的主体的出现等等，都是在这个基础上出现的。即CAS（复杂适应系统）理论的最基本思想,CAS的四个基本特点：首先，主体(Adaptive Agent)是主动的、活的实体；其次，个体与环境(包括个体之间)的相互影响，相互作用，是系统演变和进化的主要动力；再次，这种方法不象许多其他的方法那样，把宏观和微观截然分开，而是把它们有机地联系起来；最后，这种建模方法还引进了随机因素的作用，使它具有更强的描述和表达能力。,PSO产生背景之二：人工生命 研究具有某些生命基本特征的人工系统。包括两方面的内容：1、研究如何利用计算技术研究生物现象；2、研究如何利用生
3、物技术研究计算问题。我们关注的是第二点。已有很多源于生物现象的计算技巧，例如神经网络和遗传算法。现在讨论另一种生物系统-社会系统：由简单个体组成的群落和环境及个体之间的相互行为。Millonas在开发人工生命算法时(1994年)，提出群体智能概念并提出五点原则：1、接近性原则：群体应能够实现简单的时空计算；2、优质性原则：群体能够响应环境要素；3、变化相应原则：群体不应把自己的活动限制在一狭小范围；4、稳定性原则：群体不应每次随环境改变自己的模式；5、适应性原则：群体的模式应在计算代价值得的时候改变。,社会组织的全局群行为是由群内个体行为以非线性方式出现的。个体间的交互作用在构建群行为中起到重
4、要的作用。从不同的群研究得到不同的应用。最引人注目的是对蚁群和鸟群的研究。其中粒群优化方法就是模拟鸟群的社会行为发展而来。对鸟群行为的模拟：Reynolds、Heppner和Grenader提出鸟群行为的模拟。他们发现，鸟群在行进中会突然同步的改变方向，散开或者聚集等。那么一定有某种潜在的能力或规则保证了这些同步的行为。这些科学家都认为上述行为是基于不可预知的鸟类社会行为中的群体动态学。在这些早期的模型中仅仅依赖个体间距的操作，也就是说，这种同步是鸟群中个体之间努力保持最优的距离的结果。,PSO（粒子群优化算法（Particle Swarm Optimization），缩写为 PSO）从这种模
5、型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitness value)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。PSO 初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己。第一个就是粒子本身所找到的最优解，这个解叫做个体极值pBest。另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部
6、极值。,PSO是近年来由J.Kennedy和R.C.Eberhart等 开发的一种新的进化算法(Evolutionary Algorithm-EA)。PSO 算法属于进化算法的一种，和模拟退火算法相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的“交叉”(Crossover)和“变异”(Mutation)操作，它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。粒子群算法是一种并行算法。,算法原理,ALGORITHM PRINCIPL
7、E,02,抽象 鸟被抽象为没有质量和体积的微粒(点)，并延伸到N维空间，粒子I 在N维空间的位置表示为矢量Xi(x1，x2，xN)，飞行速度表示为矢量Vi(v1，v2，vN)每个粒子都有一个由目标函数决定的适应值(fitness value)，并且知道自己到目前为止发现的最好位置(pbest)和现在的位置Xi这个可以看作是粒子自己的飞行经验除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(gbest)(gbest是pbest中的最好值)这个可以看作是粒子同伴的经验粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。,PSO初始化为一群随机粒子(随机解)。然后通过迭代找
8、到最优解。在每一次的迭代中，粒子通过跟踪两个“极值”(pbest,gbest)来更新自己。在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。,(1)式,(2)式,在式(1)、(2)中，i1，2，M，M是该群体中粒子的总数,Vi 是粒子的速度；pbest和gbest如前定义；rand()是介于（0、1）之间的随机数；Xi 是粒子的当前位置。c1和c2是学习因子，通常取c1 c22在每一维，粒子都有一个最大限制速度Vmax，如果某一维的速度超过设定的Vmax，那么这一维的速度就被限定为Vmax。（Vmax 0）以上面两个公式为基础，形成了后来PSO 的标准形式,从社会学的角度来看，公
9、式(1)的第一部分称为记忆项，表示上次速度大小和方向的影响；公式第二部分称为自身认知项，是从当前点指向粒子自身最好点的一个矢量，表示粒子的动作来源于自己经验的部分；公式的第三部分称为群体认知项，是一个从当前点指向种群最好点的矢量，反映了粒子间的协同合作和知识共享。粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。以上面两个公式为基础，形成了后来PSO 的标准形式,标准PSO算法的流程：Step1:初始化一群微粒(群体规模为m)，包括随机位置和速度；Step2:评价每个微粒的适应度；Step3:对每个微粒，将其适应值与其经过的最好位置pbest作比较，如果较好，则将其作为当前的最好位置
10、pbest;Step4:对每个微粒，将其适应值与其经过的最好位置gbest作比较，如果较好，则将其作为当前的最好位置gbest;Step5:根据(2)、(3)式调整微粒速度和位置；Step6：未达到结束条件则转Step2。,1998年shi等人在进化计算的国际会议上发表了一篇论文A modified particle swarmoptimizer对前面的公式(1)进行了修正。引入惯性权重因子。,（3）式,非负，称为惯性因子。公式(2)和(3)被视为标准pso算法。,迭代终止条件根据具体问题一般选为最大迭代次数Gk或(和)微粒群迄今为止搜索到的最优位置满足预定最小适应阈值,方程(2)和(3)中p
11、best和gbest分别表示微粒群的局部和全局最优位置，当C10时，则粒子没有了认知能力，变为只有社会的模型(social-only):被称为全局PSO算法.粒子有扩展搜索空间的能力，具有较快的收敛速度，但由于缺少局部搜索，对于复杂问题比标准PSO 更易陷入局部最优。,当C20时，则粒子之间没有社会信息，模型变为只有认知(cognition-only)模型：被称为局部PSO算法。由于个体之间没有信息的交流，整个群体相当于多个粒子进行盲目的随机搜索，收敛速度慢，因而得到最优解的可能性小。,参数有：群体规模m，惯性因子，学习因子c1和c2最大速度Vmax，迭代次数Gk。群体规模m 一般取2040，
12、对较难或特定类别的问题可以取到100200。最大速度Vmax决定当前位置与最好位置之间的区域的分辨率(或精度)。如果太快，则粒子有可能越过极小点;如果太慢，则粒子不能在局部极小点之外进行足够的探索，会陷入到局部极值区域内。这种限制可以达到防止计算溢出、决定问题空间搜索的粒度的目的。,权重因子 包括惯性因子 和学习因子c1和c2。使粒子保持着运动惯性，使其具有扩展搜索空间的趋势，有能力探索新的区域。C1和c2代表将每个粒子推向Pbest和gbest位置的统计加速项的权值。较低的值允许粒子在被拉回之前可以在目标区域外徘徊，较高的值导致粒子突然地冲向或越过目标区域。,参数设置如果令c1c20，粒子将
13、一直以当前速度的飞行，直到边界。很难找到最优解。如果 0，则速度只取决于当前位置和历史最好位置，速度本身没有记忆性。假设一个粒子处在全局最好位置，它将保持静止，其他粒子则飞向它的最好位置和全局最好位置的加权中心。粒子将收缩到当前全局最好位置。在加上第一部分后，粒子有扩展搜索空间的趋势，这也使得w的作用表现为针对不同的搜索问题，调整算法的全局和局部搜索能力的平衡。较大时，具有较强的全局搜索能力；较小时，具有较强的局部搜索能力。,通常设c1c22。Suganthan的实验表明：c1和c2为常数时可以得到较好的解，但不一定必须等于2。Clerc引入收敛(constriction factor)K来保
14、证收敛性。,其中,通常取 为4.1,则K0.729.实验表明，与使用惯性权重的PSO算法相比，使用收敛因子的PSO有更快的收敛速度。其实只要恰当的选取 和c1、c2，两种算法是一样的。因此使用收敛因子的PSO可以看作使用惯性权重PSO的特例。恰当的选取算法的参数值可以改善算法的性能。,基本PSO是用于实值连续空间，然而许多实际问题是组合优化问题，因而提出离散形式的PSO。速度和位置更新式为：,else,then,PSO和其他算法,OTHERS,03,遗传算法和PSO的比较,共性:(1)都属于仿生算法。(2)都属于全局优化方法。(3)都属于随机搜索算法。(4)都隐含并行性。(5)根据个体的适配信
15、息进行搜索，因此不受函数 约束条件的限制，如连续性、可导性等。(6)对高维复杂问题，往往会遇到早熟收敛和收敛 性能差的缺点，都无法保证收敛到最优点。,差异：(1)PSO有记忆，好的解的知识所有粒子都保 存，而GA以前的知识随着种群的改变被改变。(2)PSO中的粒子仅仅通过当前搜索到最优点进行共享信息，所以很大程度上这是一种单共享项信息机制。而GA中，染色体之间相互共享信息，使得整个种群都向最优区域移动。(3)GA的编码技术和遗传操作比较简单，而PSO相对于GA，没有交叉和变异操作，粒子只是通过内部速度进行更新，因此原理更简单、参数更少、实现更容易。,PSO和ANN,GA可以用来研究ANN的三个
16、方面：网络连接权重、网络结构、学习算法。优势在于可处理传统方法不能处理的问题，例如不可导的节点传递函数或没有梯度信息。缺点:在某些问题上性能不是特别好；网络权重的编码和遗传算子的选择有时较麻烦。已有利用PSO来进行神经网络训练。研究表明PSO是一种很有潜力的神经网络算法。速度较快且有较好的结果。且没有遗传算法碰到的问题。,蚁群算法,蚁群算法（Ant Colony Optimization,ACO）由Colorni，Dorigo和Maniezzo在1991年提出，它是通过模拟自然界蚂蚁社会的寻找食物的方式而得出的一种仿生优化算法。自然界种蚁群寻找食物时会派出一些蚂蚁分头在四周游荡，如果一只蚂蚁找
17、到食物，它就返回巢中通知同伴并沿途留下“信息素”（pheromone）作为蚁群前往食物所在地的标记。信息素会逐渐挥发，如果两只蚂蚁同时找到同一食物，又采取不同路线回到巢中，那么比较绕弯的一条路上信息素的气味会比较淡，蚁群将倾向于沿另一条更近的路线前往食物所在地。,ACO算法设计虚拟的“蚂蚁”，让它们摸索不同路线，并留下会随时间逐渐消失的虚拟“信息素”。根据“信息素较浓的路线更近”的原则，即可选择出最佳路线。目前，ACO算法已被广泛应用于组合优化问题中，在图着色问题、车间流问题、车辆调度问题、机器人路径规划问题、路由算法设计等领域均取得了良好的效果。也有研究者尝试将ACO算法应用于连续问题的优化
18、中。由于ACO算法具有广泛实用价值，成为了群智能领域第一个取得成功的实例，曾一度成为群智能的代名词，相应理论研究及改进算法近年来层出不穷。,蚁群算法,其它群智能优化算法,目前，还有一些不成熟的群智能优化算法，国内值得关注的有以下几种。2003年李晓磊、邵之江等提出的鱼群算法，它利用自上而下的寻优模式模仿自然界鱼群觅食行为，主要利用鱼的觅食、聚群和追尾行为，构造个体底层行为；通过鱼群中各个体的局部寻优，达到全局最优值在群体中凸现出来的目的。在基本运算中引入鱼群的生存机制、竞争机制以及鱼群的协调机制，提高算法的有效效率。,张玲等则提出了一种“松散的脑袋”群智能模型，采用特殊的随机人工神经网络构建了
19、一种群智能数学模型。每个神经元被看成一个主体，主体之间的通讯连接看成各神经元之间的连接，但连接是随机而不是固定的，即用一个随机连接的神经网络来描述一个群体，这种神经网络来描述一个群体。显然这种神经网络具有群体的智能。基于群智能的优化算法设计必须遵守简单有效的原则，对于自然现象过于复杂的模拟往往会导致算法不具有推广性和实用价值，许多群智能算法不成功的原因就在于此。,其它群智能优化算法,代码演示,PROGRAM SHOW,04,maxgen=200;%进化次数sizepop=200;%种群规模c1=1.49445;c2=1.49445;,for i=1:sizepop pop(i,:)=2.*ab
20、s(rands(1,par_num);v(i,:)=1.*rands(1,par_num);fitness(i)=fun2(pop(i,:);%适应度值end,vmax=1;%粒子最大更新速度vmin=-1;%粒子最小更新速度popmax=20;%种群popmin=-5;par_num=3,bestfitness bestindex=min(fitness);zbest=pop(bestindex,:);%全局最佳gbest=pop;%个体最佳fitnessgbest=fitness;%个体最佳适应度fitnesszbest=bestfitness;%全局最佳适应度,初始粒子和速度,寻找最佳适
21、应度,参数设置,for i=1:maxgen for j=1:sizepop v(j,:)=v(j,:)+c1*rand*(gbest(j,:)-pop(j,:)+c2*rand*(zbest-pop(j,:);%速度 v(j,find(v(j,:)vmax)=vmax;v(j,find(v(j,:)popmax)=popmax;pop(j,find(pop(j,:)0.8%自适应度 k=ceil(par_num*rand);pop(j,k)=rand;end,if 1.0*pop(j,1)-1.0*pop(j,2)+1.0*pop(j,3)=20 if 3*pop(j,1)+2*pop(j,
22、2)+4*pop(j,3)=42 if 3*pop(j,1)+2pop(j,2)=30 fitness(j)=fun2(pop(j,:);%适应度 end end end if fitness(j)fitnessgbest(j)gbest(j,:)=pop(j,:);fitnessgbest(j)=fitness(j);%个体最优 end if fitness(j)fitnesszbest zbest=pop(j,:);fitnesszbest=fitness(j);%全局最优 end end yy(i)=fitnesszbest;end,迭代寻优,zbest=10.6709 14.9474-5.0000,y=-5*x(1)-4*x(2)-6*x(3),目标函数,约束条件,x(1)-x(2)+x(3)203*x(1)+2*x(2)+4*x(3)423*x(1)+2*x(2)30 x(1)0,x(2)0,x(3)0,
