粒子群优化算法概述

. 计算机辅助工艺课程作业计算机辅助工艺课程作业 学学 生：赵生：赵 华华 琳琳 学学 号号: s308070072: s308070072 时时 间：间：0909 年年 6 6 月月 粒子群优化算法概述粒子群优化算法概述 0.0.前前言言 优化是科学研究、 工程技术和经济管理等领域的重要研究工具。 它所研究的问题是讨论 在众多的方案中寻找最优方案。 例如，工程设计中怎样选择设计参数， 使设计方案既满足设 计要求又能降低成本；资源分配中，怎样分配有限资源，使分配方案既能满足各方面的基本 要求，又能获得好的经济效益。在人类活动的各个领域中，诸如此类，不胜枚举。优化这一 技术，正是为这些问题的解决，提供理论基础和求解方法，它是一门应用广泛、实用性很强 的科学。 近十余年来， 粒子群优化算法作为群体智能算法的一个重要分支得到了广泛深入的 研究， 在路径规划等许多领域都有应用。 本文主要结合现阶段的研究概况对粒子群优化算法 进行初步介绍。 1.1.粒子群优化算法的基本原理粒子群优化算法的基本原理 1.11.1 粒子群优化算法的起源粒子群优化算法的起源 粒子群优化（PSO）算法是由 Kennedy 和 Eberhart 于 1995 年用计算机模拟鸟群觅食这 [1][2] 一简单的社会行为时，受到启发，简化之后而提出的。 设想这样一个场景：一群鸟随机的分布在一个区域中， 在这个区域里只有一块食物。 所 有的鸟都不知道食物在哪里。 但是他们知道当前的位置离食物还有多远。 那么找到食物的最 优策略是什么呢。 最简单有效的方法就是追寻自己视野中目前离食物最近的鸟。 如果把食物 当作最优点， 而把鸟离食物的距离当作函数的适应度， 那么鸟寻觅食物的过程就可以当作一 个函数寻优的过程。 鱼群和鸟群的社会行为一直引起科学家的兴趣。 他们以特殊的方式移动、 同步，不会相互碰撞，整体行为看上去非常优美。 生物学家 CargiReynolds 提出了一个非常 有影响的鸟群聚集模型。 在他的模拟模型 boids 中，每一个个体遵循：避免与邻域个体相冲 撞、 匹配邻域个体的速度、 试图飞向感知到的鸟群中心这三条规则形成简单的非集中控制算 法驱动鸟群的聚集， 在一系列模拟实验中突现出了非常接近现实鸟群聚集行为的现象。 该结 果显示了在空中回旋的鸟组成轮廓清晰的群体， 以及遇到障碍物时鸟群的分裂和再度汇合过 程。由此受到启发，经过简化提出了粒子群优化算法。 1.21.2 粒子群优化算法的原理粒子群优化算法的原理 在粒子群优化算法中， 每个优化问题的潜在解都是搜索空间中的一只鸟， 称之为 “粒子” 。 所有的粒子都有一个由被优化的函数决定的适应值， 每个粒子还有一个速度决定他们飞翔的 方向和距离。 然后粒子们就追随当前的最优粒子在解空间中搜索。 优化开始时先初始化为一 群随机粒子（随机解） 。然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极 值来更新自己。第一个极值就是整个种群目前找到的最优解。 这个极值是全局极值。 另外也 可以不用整个种群而只是用其中一部分作为粒子的邻居， 那么在所有邻居中的极值就是局部 极值。第二个极值是粒子本身所找到的最优解， 称为个体极值。这是因为粒子仅仅通过跟踪 全局极值或者局部极值来更新位置， 不可能总是获得较好的解。 这样在优化过程中，粒子在 追随全局极值或局部极值的同时追随个体极值则圆满的解决了这个问题。 这就是粒子群优化 算法的原理。 在算法开始时， 随机初始化粒子的位置和速度构成初始种群， 初始种群在解空间中为均 匀分布。其中第 i 个粒子在 n 维解空间的位置和速度可分别表示为 Xi=（xi1,xi2,…,xid）和 Vi=（vi1,vi2,…,vid） ，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值 来更新自己的速度和位置。 一个极值是粒子本身到目前为止所找到的最优解， 这个极值称为 个体极值 Pbi=（Pbi1,Pbi2,…,Pbid） 。另一个极值是该粒子的邻域到目前为止找到的最优解， . 这个极值称为整个邻域的最优粒子 Nbesti=(Nbesti1,Nbesti2,…,Nbestid)。粒子根据如下的 式(2-1)和式(2-2)来更新自己的速度和位置： Vi=Vi+c1·rand()·(Pbesti-Xi)+c2·rand()·(Nbesti-Xi) (2-1) Xi= Xi+ Vi (2-2) 式中 c1和 c2是加速常量，分别调节向全局最好粒子和个体最好粒子方向飞行的最大步 长，若太小，则粒子可能远离目标区域,若太大则会导致突然向目标区域飞去，或飞过目标 区域。合适的c1，c2可以加快收敛且不易陷入局部最优。rand()是 0 到 1 之间的随机数。粒 子在每一维飞行的速度不能超过算法设定的最大速度 Vmax。设置较大的 Vmax可以保证粒子种 群的全局搜索能力，Vmax较小则粒子种群优化算法的局部搜索能力加强。 粒子群优化算法是在模拟鸟群觅食时受到启发提出的。 提出之后却发现用动物或人的认 知来解释算法的原理更加完美。 在速度更新公式(2-1)中由 3 个部分构成。 第 1 个部分是 Vi， 表示粒子在解空间有按照原有方向和速度进行搜索的趋势， 这可以用人在认知事物时总是用 固有的习惯来解释。第 2 个部分是 c1·rand()·(Pbesti-Xi)，表示粒子在解空间有朝着过去 曾碰到的最优解进行搜索的趋势，这可以用人在认知事物时总是用过去的经验来解释。第3 部分是 c2·rand()·(Nbesti-Xi)，表示粒子在解空间有朝着整个邻域过去曾碰到的最优解进 行搜索的趋势， 这可以用人在认知事物时总可以通过学习其他人的知识， 也就是分享别人的 经验来解释。因此， 粒子群优化算法实际上是借用了人或动物认知事物时的习惯， 经验，及 学习过程来进行寻优的。粒子在优化过程中的运动轨迹见图1。 图图 1 1 粒子群算法优化搜索示意图粒子群算法优化搜索示意图 1.31.3 粒子群优化算法的优点粒子群优化算法的优点 粒子群优化算法具有以下主要优点： (1)易于描述；(2)便于实现；(3)要调整的参数很 少；(4)使用规模相对较少的群体；(5)收敛需要评估函数的次数少；(6)收敛速度快粒子群 优化算法很容易实现，计算代价低， 由于其内存和 CPU 速度要求都很低。而且，它不需要目 标函数的梯度信息， 只依靠函数值。 粒子群优化算法已被证明是解决许多全局优化问题的有 效方法。 2.2.粒子群优化算法的实现粒子群优化算法的实现 粒子群优化算法具有编程简单， 易实现的特点，粒子群优化算法的流程如图2 所示。下 面给出其实现的具体步骤： 00 步骤 1： 初始化。 初始搜索点的位置 X i及其速度 Vi通常是在允许的范围内随机产生的， 每个粒子的 Pbest 坐标设置为其当前位置，且计算出其相应的个体极值（即个体极值点 的适应度值） ，而整个邻域的最优粒子就是该粒子邻域中个体极值中最好的，记录该最好值 的粒子序号，并将 Nbesti设置为该最好粒子的当前位置。 . 步骤 2：评价每一个粒子。计算粒子的适应度值,如果好于该粒子当前的个