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