粒子群算法完整版.ppt

粒子群优化算法 PSO算法简介 粒子群算法(particle swarm optimization，PSO)由Kennedy和Eberhart在1995年提出，该算法模拟鸟集群飞行觅食的行为，鸟之间通过集体的协作使群体达到最优目的，是一种基于Swarm Intelligence的优化方法。同遗传算法类似，也是一种基于群体叠代的，但并没有遗传算法用的交叉以及变异，而是粒子在解空间追随最优的粒子进行搜索。PSO的优势在于简单容易实现同时又有深刻的智能背景，既适合科学研究，又特别适合工程应用，并且没有许多参数需要调整。 基本PSO算法 粒子群优化算法源于1987年Reynolds对鸟群社会系统boids的仿真研究，boids是一个CAS （Complex Adaptive System (CAS) ） 。在boids中，一群鸟在空中飞行，每个鸟遵守以下三条规则： 1）避免与相邻的鸟发生碰撞冲突； 2）尽量与自己周围的鸟在速度上保持协调和一致； 3）尽量试图向自己所认为的群体中靠近。 仅通过使用这三条规则，boids系统就出现非常逼真的群体聚集行为，鸟成群地在空中飞行，当遇到障碍时它们会分开绕行而过，随后又会重新形成群体。 起源 生物社会学家对鸟群。 原理 我们可以设想这样一个场景，一群鸟在某区域随机搜寻食物。该区域只有一块食物。所有的鸟都不知道食物在哪里，但它们知道目前距离食物还有多远，那么找到食物的最佳策略是什么呢？最简单的方法就是找寻距离食物最近的鸟周围区域及根据自己飞行的经验判断食物的所在。 近年PSO方面文献的数量 PSO产生背景之一：复杂适应系统 CAS理论的最基本的思想可以概述如下： 我们把系统中的成员称为具有适应性的主体(Adaptive Agent)，简称为主体。所谓具有适应性，就是指它能够与环境以及其它主体进行交流，在这种交流的过程中“学习”或“积累经验”，并且根据学到的经验改变自身的结构和行为方式。整个系统的演变或进化，包括新层次的产生，分化和多样性的出现，新的、聚合而成的、更大的主体的出现等等，都是在这个基础上出现的。 复杂适应系统 CAS的四个基本特点： 首先，主体(Adaptive Agent)是主动的、活的实体； 其次，个体与环境(包括个体之间)的相互影响，相互作用，是系统演变和进化的主要动力； 再次，这种方法不象许多其他的方法那样，把宏观和微观截然分开，而是把它们有机地联系起来； 最后，这种建模方法还引进了随机因素的作用，使它具有更强的描述和表达能力。 PSO产生背景之二:人工生命 人工生命“是来研究具有某些生命基本特征的人工系统。人工生命包括两方面的内容： ① 研究如何利用计算技术研究生物现象； ② 研究如何利用生物技术研究计算问题(Nature Computation)。 我们现在关注的是第二部分的内容。现在已经有很多源于生物现象的计算技巧，例如, 人工神经网络是简化的大脑模型. 遗传算法是模拟基因进化过程的。现在我们讨论另一种生物系统：社会系统，更确切地说，是由简单个体组成的群落与环境以及个体之间的互动行为，也可称做群智能。 鸟群觅食行为 特点 分散式搜寻 具有记忆性 容易实现 适合在连续范围内搜索 算法介绍 每个寻优的问题解都被想像成一只鸟，称为“Particle”。 所有的Particle 都有一个fitness function 以判断目前的位置好坏， 每一个Particle必须赋予记忆功能，能记住所搜寻到的最佳位置。 每一个Particle 还有一个速度以决定飞行的距离和方向。 粒子群优化算法求最优解 PSO 向量示意图 算法流程 Initial： 将族群初始化，以随机的方式求出每一Particle 的初始位置与速度。 Evaluation： 根据fitness function 计算出其fitness value 以作为判断每一Particle的好坏。 Fine the Pbest： 找出每一Particle 到目前为止的搜寻过程中最佳解，这个最佳解称为Pbest。 Fine the Gbest： 找出所有Particle 到目前为止所搜寻到的整体最佳解，此最佳解称为Gbest。 Update the Velocity： 根据式(1) 与式(2) 更新每一Particle之速度与位置。 回到步骤2. 继续执行，直到获得一个令人满意的结果或符合终止条件。 基本粒子群优化算法流程图 Schwefels function 搜尋過程－最初狀態 搜尋過程－經過5代 搜尋過程－經過10代 搜尋過程－經過15代 搜尋過程－經過20代 搜尋過程－經過25代 搜