现代优化智能算法-粒子群算法.ppt

现代优化智能算法-粒子群优化算法
PSO算法
粒子群优化算法概述
起源
算法提出
算法描述
算法标准流程
经典问题分析
优缺点
应用领域
研究现状
算法起源-群智能概念
假设你和你的朋友正在寻宝,每个人有个探测器,这个探测器可以知道宝藏到探测器的距离。你们一群人在找,每个人都可以把信息共享出去,就跟打dota时你可以有你队友的视野,你可以知道其他所有人距离宝藏的距离,这样,你看谁离宝藏最近,就向谁靠近,这样会使你发现宝藏的机会变大,而且,这种方法比你单人找要快的多。
这是一个群行为(swarm behavior)的简单实例,群中各个体交互作用,使用一个比单一个体更有效的方法求解全局目标。可以把群(swarm)定义为某种交互作用的组织或Agent之结构集合,在群智能计算研究中,群的个体组织包括蚂蚁,白蚁,蜜蜂,黄蜂,鱼群,鸟群等。在这些群体中,个体在结构上是很简单的,而它们的集体行为却可能变得相当复杂。研究人员发现,蚂蚁在鸟巢和食物之间的运输路线,不管一开始多随机,最后蚂蚁总能找到一条最短路径。
算法起源-粒子群优化概念
粒群优化(particle swarm optimization,PSO)算法是一种基于群体搜索的算法,它建立在模拟鸟群社会的基础上。粒群概念的最初含义是通过图形来模拟鸟群优美和不可预测的舞蹈动作,发现鸟群支配同步飞行和以最佳队形突然改变飞行方向并重新编队的能力。这个概念已经被包含在一个简单有效的优化算法中。
在粒群优化中,被称为“粒子”(particle)的个体通过超维搜索空间“流动”。粒子在搜索空间中的位置变化是以个体成功地超过其他个体的社会心理意向为基础的,因此,群中粒子的变化是受其邻近粒子(个体)的经验或知识影响的。一个粒子的搜索行为受到群中其他粒子的搜索行为的影响。由此可见,粒群优化是一种共生合作算法。
算法起源-模拟鸟群、鱼群
Reynolds、Heppner和Grenader提出鸟群行为的模拟。他们发现,鸟群在行进中会突然同步的改变方向,散开或者聚集等。那么一定有某种潜在的能力或规则保证了这些同步的行为。这些科学家都认为上述行为是基于不可预知的鸟类社会行为中的群体动态学。
在这些早期的模型中仅仅依赖个体间距的操作,也就是说,这中同步是鸟群中个体之间努力保持最优的距离的结果。
。提出:“至少在理论上,鱼群的个体成员能够受益于群体中其他个体在寻找食物的过程中的发现和以前的经验,这种受益超过了个体之间的竞争所带来的利益消耗,不管任何时候食物资源不可预知的分散。”这说明,同种生物之间信息的社会共享能够带来好处。这是PSO的基础。
算法提出 1/2
粒子群优化算法(PSO)putation),。粒子群优化算法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解.
PSO的优势在于简单容易实现并且没有许多参数的调节。目前已被广泛应用于函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用领域。
算法提出 2/2
设想这样一个场景:一群鸟在随机的搜索食物。在这个区域里只有一块食物,所有的鸟都不知道食物在那。但是它们知道自己当前的位置距离食物还有多远。
那么找到食物的最优策略是什么呢?
最简单有效的做法就是搜索目前距离食物最近鸟的周围区域。
算法描述 1/5
模型抽象:
鸟被抽象为没有质量和体积的微粒(点),并延伸到N维空间,粒子I 在N维空间的位置表示为矢量Xi=(x1,x2,…,xN),飞行速度表示为矢量Vi=(v1,v2,…,vN).每个粒子都有一个由目标函数决定的适应值(fitness value),并且知道自己到目前为止发现的最好位置(pbest),每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(gbest)(gbest是pbest中的最好值).。
算法描述 2/5
PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中,粒子通过跟踪两个”极值“(pbest,gbest)来更新自己。
在找到这两个最优值后,粒子通过下面的公式来更新自己的速度和位置。
(1)式
Vi=w×Vi+c1×rand()×(pbesti-xi)+c2×rand()×(gbesti-xi)
(2)式
xi=xi+Vi
在式(1)、(2)中,i=1,2,3...,M,M是该群体中粒子的总数
算法描述 3/5
Vi 是粒子的速度;
pbest和gbest如前