pso粒子群算法

粒子群优化算法PSOParticleSwarmOptimization姚新正西安电子科技大学[e-mail],Xi’an,China©2005目录背景算法介绍参数分析PSO和其他算法PSO资源和参考文献算法介绍PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个“极值”(pbest,gbest)来更新自己。在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。iiixxV12()()()()iiiiiiVVcrandpbestxcrandgbestx(2)式(1)式iiixxV在式(1)、(2)中，i＝1，2，…，M，M是该群体中粒子的总数人工生命：研究具有某些生命基本特征的人工系统。包括两方面的内容：1、研究如何利用计算技术研究生物现象；2、研究如何利用生物技术研究计算问题。我们关注的是第二点。已有很多源于生物现象的计算技巧，例如神经网络和遗传算法。现在讨论另一种生物系统---社会系统：由简单个体组成的群落和环境及个体之间的相互行为。背景算法介绍PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个“极值”(pbest,gbest)来更新自己。在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。iiixxV12()()()()iiiiiiVVcrandpbestxcrandgbestx(2)式(1)式iiixxV在式(1)、(2)中，i＝1，2，…，M，M是该群体中粒子的总数背景群智能(swarmintelligence)模拟系统利用局部信息从而可以产生不可预测的群行为。我们经常能够看到成群的鸟、鱼或者浮游生物。这些生物的聚集行为有利于它们觅食和逃避捕食者。它们的群落动辄以十、百、千甚至万计，并且经常不存在一个统一的指挥者。它们是如何完成聚集、移动这些功能呢？算法介绍PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个“极值”(pbest,gbest)来更新自己。在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。iiixxV12()()()()iiiiiiVVcrandpbestxcrandgbestx(2)式(1)式iiixxV在式(1)、(2)中，i＝1，2，…，M，M是该群体中粒子的总数Millonas在开发人工生命算法时(1994年)，提出群体智能概念并提出五点原则：1、接近性原则：群体应能够实现简单的时空计算；2、优质性原则：群体能够响应环境要素；3、变化相应原则：群体不应把自己的活动限制在一狭小范围；4、稳定性原则：群体不应每次随环境改变自己的模式；5、适应性原则：群体的模式应在计算代价值得的时候改变。背景算法介绍PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个“极值”(pbest,gbest)来更新自己。在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。iiixxV12()()()()iiiiiiVVcrandpbestxcrandgbestx(2)式(1)式iiixxV在式(1)、(2)中，i＝1，2，…，M，M是该群体中粒子的总数背景社会组织的全局群行为是由群内个体行为以非线性方式出现的。个体间的交互作用在构建群行为中起到重要的作用。从不同的群研究得到不同的应用。最引人注目的是对蚁群和鸟群的研究。其中粒群优化方法就是模拟鸟群的社会行为发展而来。算法介绍PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个“极值”(pbest,gbest)来更新自己。在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。iiixxV12()()()()iiiiiiVVcrandpbestxcrandgbestx(2)式(1)式iiixxV在式(1)、(2)中，i＝1，2，…，M，M是该群体中粒子的总数背景对鸟群行为的模拟：Reynolds、Heppner和Grenader提出鸟群行为的模拟。他们发现，鸟群在行进中会突然同步的改变方向，散开或者聚集等。那么一定有某种潜在的能力或规则保证了这些同步的行为。这些科学家都认为上述行为是基于不可预知的鸟类社会行为中的群体动态学。在这些早期的模型中仅仅依赖个体间距的操作，也就是说，这中同步是鸟群中个体之间努力保持最优的距离的结果。算法介绍PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个“极值”(pbest,gbest)来更新自己。在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。iiixxV12()()()()iiiiiiVVcrandpbestxcrandgbestx(2)式(1)式iiixxV在式(1)、(2)中，i＝1，2，…，M，M是该群体中粒子的总数背景对鱼群行为的研究：生物社会学家E.O.Wilson对鱼群进行了研究。提出：“至少在理论上，鱼群的个体成员能够受益于群体中其他个体在寻找食物的过程中的发现和以前的经验，这种受益超过了个体之间的竞争所带来的利益消耗，不管任何时候食物资源不可预知的分散。”这说明，同种生物之间信息的社会共享能够带来好处。这是PSO的基础。算法介绍PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个“极值”(pbest,gbest)来更新自己。在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。iiixxV12()()()()iiiiiiVVcrandpbestxcrandgbestx(2)式(1)式iiixxV在式(1)、(2)中，i＝1，2，…，M，M是该群体中粒子的总数粒子群优化算法（PSO）是一种进化计算技术（evolutionarycomputation）,由Eberhart博士和kennedy博士于1995年提出(KennedyJ，EberhartR．Particleswarmoptimization．ProceedingsoftheIEEEInternationalConferenceonNeuralNetworks．1995．1942~1948.)。源于对鸟群捕食的行为研究。粒子群优化算法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解．PSO的优势在于简单容易实现并且没有许多参数的调节。目前已被广泛应用于函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用领域。算法介绍算法介绍PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个“极值”(pbest,gbest)来更新自己。在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。iiixxV12()()()()iiiiiiVVcrandpbestxcrandgbestx(2)式(1)式iiixxV在式(1)、(2)中，i＝1，2，…，M，M是该群体中粒子的总数算法介绍设想这样一个场景：一群鸟在随机的搜索食物。在这个区域里只有一块食物，所有的鸟都不知道食物在那。但是它们知道自己当前的位置距离食物还有多远。那么找到食物的最优策略是什么？最简单有效的就是搜寻目前离食物最近的鸟的周围区域。算法介绍算法介绍PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个“极值”(pbest,gbest)来更新自己。在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。iiixxV12()()()()iiiiiiVVcrandpbestxcrandgbestx(2)式(1)式iiixxV在式(1)、(2)中，i＝1，2，…，M，M是该群体中粒子的总数抽象：鸟被抽象为没有质量和体积的微粒(点)，并延伸到N维空间，粒子I在N维空间的位置表示为矢量Xi＝(x1，x2，…，xN)，飞行速度表示为矢量Vi＝(v1，v2，…，vN)．每个粒子都有一个由目标函数决定的适应值(fitnessvalue)，并且知道自己到目前为止发现的最好位置(pbest)和现在的位置Xi．这个可以看作是粒子自己的飞行经验．除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(gbest)(gbest是pbest中的最好值)．这个可以看作是粒子同伴的经验．粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。算法介绍算法介绍PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个“极值”(pbest,gbest)来更新自己。在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。iiixxViiixxV12()()()()iiiiiiVVcrandpbestxcrandgbestx(2)式(1)式在式(1)、(2)中，i＝1，2，…，M，M是该群体中粒子的总数PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个“极值”(pbest,gbest)来更新自己。在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。(1)式(2)式在式(1)、(2)中，i＝1，2，…，M，M是该群体中粒子的总数算法介绍12()()()()iiiiiiVVcrandpbestxcrandgbestxiiixxV算法介绍PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个“极值”(pbest,gbest)来更新自己。在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。iiixxV12()()()()iiiiiiVVcrandpbestxcrandgbestx(2)式(1)式iiixxV在式(1)、(2)中，i＝1，2，…，M，M是该群体中粒子的总数Vi是粒子的速度；pbest和gbest如前定义；rand()是介于（0、1）之间的随机数；Xi是粒子的当前位置。c1和c2是学习因子，通常取c1＝c2＝2在每一维，粒子都有一个最大限制速度Vmax，如果某一维的速度超过设定的Vmax，那么这一维的速度就被限定为Vmax。（Vmax0）以上面两个公式为基础，形成了后来PSO的标准形式算法介绍算法介绍PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个“极值”(pbest,gbest)来更新自己。在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。iiixxV12()()()()iiiiiiVVcrandpbestxcrandgbestx(2)式(1)式iiixxV在式(1)、(2)中，i＝1，2，…，M，M是该群体中粒子的总数算法介绍从社会学的角度来看，公式(1)的第一部分称为记忆项，表示上次速度大小和方向的影响；公式第二部分称为自身认知项，是从当前点指向粒子自身最好点的一个矢量，表示粒子的动作来源于自己经验的部分；公式的第三部分称为群体认知项，是一个从当前点指向种群最好点的矢量，反映了粒子间的协同合作和知识共享。粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。以上面两个公式为基础，形成了后来PSO的标准形式算法介绍PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个“极值”(pbest,gbest)来更新自己。在找到这两个最优值后，粒子通过