数学建模之粒子群算法省名师优质课获奖课件市赛课一等奖课件.ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,(,粒子群算法课件）,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。谢谢,粒子群算法及其应用介绍,国防科技大学理学院数学系,成礼智,年夏季学期数学建模竞赛讲座,第1页,1,目 录,背景,算法介绍,参数分析,PSO和其它算法,PSO资源和参考文件,第2页,2,算法介绍,群智能(swarm intelligence),模拟系统利用局部信息从而能够产生不可预测群行为。,我们经常能够看到成群鸟、鱼或者浮游生物。这些生物聚集行为有利于它们觅食和逃避捕食者。它们群落动辄以十、百、千甚至万计，而且经常不存在一个统一指挥者。它们是怎样完成聚集、移动这些功效呢,？,第3页,3,算法介绍,Millonas在开发人工生命算法时(1994年)，提出群体智能概念并提出五点标准：,1、靠近性标准：群体应能够实现简单时空计算；,2、优质性标准：群体能够响应环境要素；,3、改变对应标准：群体不应把自己活动限制在一狭 小范围；,4、稳定性标准：群体不应每次随环境改变自己模式；,5、适应性标准：群体模式应在计算代价值得时候改变。,第4页,4,背 景,社会组织全局群行为是由群内个体行,为以非线性方式出现。个体间交互作用,在构建群行为中起到主要作用。,从不一样群研究得到不一样应用。最引,人注目标是对蚁群和鸟群研究。,其中粒群优化方法就是模拟鸟群社会,行为发展而来。,第5页,5,背 景,对鸟群行为模拟：,Reynolds、Heppner和Grenader提出鸟群行为,模拟。他们发觉，鸟群在行进中会突然同时,改变方向，散开或者聚集等。那么一定有某种潜,在能力或规则确保了这些同时行为。这些科,学家都认为上述行为是基于不可预知鸟类社会,行为中群体动态学。,在这些早期模型中仅仅依赖个体间距操,作，也就是说，这中同时是鸟群中个体之间努力,保持最优距离结果。,第6页,6,背 景,对鱼群行为研究：,生物社会学家E.O.Wilson对鱼群进行了研究。,提出：“最少在理论上,，,鱼群个体组员能够,受益于群体中其它个体在寻找食物过程中,发觉和以前经验，这种受益超出了个体之间,竞争所带来利益消耗，不论任何时候食物,资源不可预知分散。”这说明，同种生物之,间信息社会共享能够带来好处。这是PSO,基础。,第7页,7,算法介绍,粒子群优化算法（PSO）是一个进化计算技术,（evolutionary computation）,由Eberhart博士,和kennedy博士于1995年提出(Kennedy J，,Eberhart R,Particle swarm,ptimization,Proceedings of the IEEE,International Conference on Neural,Networks199519421948.)。源于对鸟群捕,食行为研究。粒子群优化算法基本思想是通,过群体中个体之间协作和信息共享来寻找最优解,PSO优势在于简单轻易实现而且没有许多参数,调整。当前已被广泛应用于函数优化、神经网络训,练、含糊系统控制以及其它遗传算法应用领域。,第8页,8,算 法 介 绍,构想这么一个场景：一群鸟在随机搜索食物。,在这个区域里只有一块食物，全部鸟都不知,道食物在那。不过它们知道自己当前位置距离,食物还有多远。,那么找到食物最优策略是什么,？,最简单有效就是搜寻当前离食物最近鸟,周围区域。,第9页,9,算法介绍,第10页,10,抽 象,鸟被抽象为没有质量和体积微粒(点)，并延伸到N维空间，粒子,I,在N维空间位置表示为矢量,Xi,(,x,1，,x,2，,xN,)，飞行速度表示为矢量,Vi,(,v1,，,v2,，v,N,)每个粒子都有一个由目标函数决定适应值(fitness value)，而且知道自己到当前为止发觉最好位置(pbest)和现在位置,Xi,这个能够看作是粒子自己飞行经验除此之外，每个粒子还知道到当前为止整个群体中全部粒子发觉最好位置(gbest)(gbest是pbest中最好值)这个能够看作是粒子同伴经验粒子就是经过自己经验和同伴中最好经验来决定下一步运动。,第11页,11,第12页,12,PSO初始化为一群随机粒子(随机解)。然后经过迭代找到最优解。在每一次迭代中，粒子经过跟踪两个“极值”(pbest,gbest)来更新自己。,在找到这两个最优值后，粒子经过下面公式来更新自己速度和位置。,上面两式中,i,1，2，M，M是该群体中粒子,总数,第13页,13,V,i,是粒子速度；,pbest和gbest如前定义；,rand()是介于（0、1）之间随机数；,X,i,是粒子当前位置。,c1和c2是学习因子，通常取c1 c22,在每一维，粒子都有一个最大限制速度Vmax，假如,某一维速度超出设定Vmax，那么这一维速度,就被限定为Vmax。（Vmax 0）,以上面两个公式为基础，形成了以后PSO,标准形式,第14页,14,从社会学角度来看，公式(1)第一部分称为记忆项，,表示上次速度大小和方向影响，为惯性因子；公式,第二部分称为本身认知项，是从当前点指向粒子本身,最好点一个矢量，表示粒子动作起源于自己经验,部分；公式第三部分称为群体认知项，是一个从,当前点指向种群最好点矢量，反应了粒子间协同,合作和知识共享。粒子就是经过自己经验和同伴中最,好经验来决定下一步运动。,以上面两个公式为基础，形成了以后PSO,标准形式,第15页,15,1998年shi等人在进化计算国际会议上,发表了一篇论文A modified particle swarm,optimizer对前面公式(1)进行了修正。引入,惯性权重因子。,上式称之为标准PSO公式,第16页,16,值较大，全局寻优能力强，局部寻优能力弱；,值较小反之。,初始时，shi将 取为常数，以后试验发觉，动,态 能够取得比固定值更加好寻优结果。动态,能够在PSO搜索过程中线性改变，也可依据PSO,性能某个测度函数动态改变。,当前，采取较多是shi提议线性递减权值,(linearly decreasing weight,LDW)策略。（见word文档）,第17页,17,经典取值,w(max)0.9，w(min)0.4。,上述思想引入使PSO算法性能有了很大提升，,针对不一样搜索问题，能够调整全局和局部搜索,能力，也使得PSO算法能成功应用于很多实际,问题,算法分析与描述（见word文档）,第18页,18,The End！,Bai Bai！,第19页,19,