一种改进的粒子群优化算法

《一种改进的粒子群优化算法》由会员分享，可在线阅读，更多相关《一种改进的粒子群优化算法（7页珍藏版）》请在金锄头文库上搜索。

1、一种改进的粒子群优化算法安进 (宁夏回族自治区宁东供电局，银川市 751408) 摘要：基本 PSO 算法及其各种改进算法都是着眼于如何更有效地用一个粒子群在解空间中 搜索最优解。但是粒子们在搜索时，总是追逐当前全局最优点和自己迄今搜索到的历史最优 点，因此粒子们的速度很快降到接近于0,导致粒子们陷入局部极小而无法摆脱，而出现粒子 的趋同或早熟。本文的改进PSO从BP神经网络中得到启示，改进如同使用低通滤波器来 平滑权重。通过使用经典测试函数，结果表明改进 PSO 在收敛精度和计算速度方面都有一 定程度的提高。关键词：粒子群算法；平滑权重；改进粒子群；优化算法1 引言20世纪 90年代以来，通

2、过模拟生物群 体的行为来解决计算问题已经成为新的研 究热点， 形成了以 群体智能 (swarm intelligence)为核心的理论体系，并已在一些 实际应用领域取得突破性进展。作为群体智 能的典型实现模式，模拟蚂蚁群落食物采集 过程的 蚁 群优化算法 1(ant colony optimization)和模拟鸟群运动模式的粒子群 优化算法(particle swarm optimization)受至U 学术界的广泛关注。粒子 群 优 化算法 (Particle Swarm Optimization, PSO)是在1995年由美国社会 心理学家 James Kennedy 和电气工程师 Ru

3、ssell Eberhart 共同提出的，其基本思想是 受他们早期对鸟类群体行为研究结果的启 发，利用了生物学家Frank Heppner的生物 群体模型。PSO 同遗传算法类似，粒子群优化算法 也是基于个体的协作与竞争来完成复杂搜 索空间中最优解的搜索，是一种基于群体智 能方法的进化计算技术。但PSO并没有遗 传算法用的交叉(crossover)、变异(m utation) 等操作，而是粒子在解空间追随最优的粒子 进行搜索，因此具有简单容易实现并且没有 过多参数需要调整的优点。2 基本粒子群算法 2.1基本粒子群算法数学模型PSO 的基本概念源于对人工生命 (artificial life)

4、和鸟群捕食行为的研究。设想 这样一个场景：一群鸟在随机搜寻食物，在 这个区域里只有一块食物，所有的鸟都知道 食物在哪里，但是它们不知道当前的位置离 食物还有多远。那么找到食物的最优策略中 最简单有效的就是搜寻目前离食物最近的 鸟的周围区域。PSO 算法就从这种生物种群行为特性 中得到启发，用于求解优化问题。在 PSO 中，每个优化问题的潜在解都可以想象成 N 维搜索空间上的一个点，我们称之为“粒 子”(particle)，所有的粒子都有一个被目标 函数决定的适应值(fitness value)。每个粒子 还有一个速度决定他们飞翔的方向和距离， 然后粒子们就追随当前的最优粒子在解空 间中搜索。在

5、一个N维的目标搜索空间中，由M 个粒子组成一个群落，其中第i个粒子表示为一个N维的向量X二(x ,x ,x )，i i1 i 2 iNi=1,2,m,即第i个粒子在N维空间的位 置。将X带入一个目标函数就可以计算出i其适应值，根据适应值的大小衡量 X 的优i劣。第i个粒子的飞翔速度也是一个N维的 向量，记为V二(v , v ,v )，其算法图ii1 i 2iN如图1所示。通过以下公式对粒子进行操作： V k+1 = w * V k + c * rand () * X k 一 X idid1idid ( pbesr )+ c *rand () * X k 一 X2idid ( gbest )(1

6、)X k +1 idXk + Vk+1idid(2)图1 PSO算法示意图2.2基本粒子群算法参数(1) 粒子种群大小M :粒子种群大小 的选择视具体问题而定，但是一般 设置粒子数为20-50。其实对于大 部分的问题10个粒子已经足够可 以取得很好的结果，不过对于比较 难的问题或者特定类型的问题，粒 子数也可以取到100或200。(2) 粒子的长度N :即是问题解空间 的维数。(3) 粒子的最大速度卩：粒子的速度max在空间中的每一维上都有一个最大速度限制值V ，用来对粒子的max速度进行钳制使速度控制在-v, V范围内，决定问题d max d max空间搜索的粒度。(4) 加速常数勺、2 :

7、调节pbest和gbest 方向飞行的最大步长，决定粒子个 体经验和群体经验对粒子运行轨 迹的影响，反映粒子群之间的信息 交流。如果c1二0，则粒子只有群 体经验，它的收敛速度较快，但容易陷入局部最优；如果c二0，则2粒子没有群体共享信息，一个规模 为M的群体等价于运行了 M个单 粒子，很难得到最优解，因此一般设置c二c。改变这些常数会改1 2变系统的“张力”，较低的C、c2值 使得粒子徘徊在远离目标的区域， 较高的C、c2值产生陡峭的运动或 越过目标区域。Shi和Eberhart建 议，为了平衡随机因素的作用，一般情况下设置c = c = 2，大部1 2分算法都采用这个建议。(5) rand

8、()：是介于0,1之间的随机数。(6) 迭代终止条件：一般设为最大迭代 次数T 、计算精度。max2.3基本粒子群算法步骤(1) 初始化粒子群:给定群体规模M :解 空间维数N，随机产生每个粒子的位置X、速度V。ii(2) 用基准测试函数f (X )各计算每个i粒子的当前适应值。(3) 更新个体极值:对每个粒子的适应值 进行评价，即将第i个粒子的当前适应值f (X )与该粒子的个体极值P的适应值进ii行比较，若前者优，则更新P,否则P保ii持不变。(4) 更新全局极值：从所有P中选出最i好的，作为全局极值P。g(5) 更新速度和位置：通过公式(1)和公 式(2)来更新每个粒子的速度V和位置X。

9、ii(6) 检查是否满足中止条件，若满足则退 出，否则，转至步骤(2)。3基本PS0算法存在的问题粒子趋同性限制了粒子的搜索范围。 要想扩大搜索范围，就要增加粒子群的粒子 数，或者减弱粒子对整个粒子群当前搜索到 的全局最优点的追逐。增加粒子数将导致算 法计算复杂度增高，而减弱粒子对全局最优 点的追逐又存在算法小、易收敛的缺点。由于基本PSO算法依靠的是群体之间 的合作与竞争，粒子本身没有变异机制，因 而单个粒子一旦受某个局部极值约束后本 身很难跳出局部极值的约束，此时需要借助 其它粒子的成功发现。事实上，PSO算法的 寻优能力主要来自于粒子之间的相互作用 和相互影响。如果从算法中除去粒子之间的

10、 相互作用和相互影响，则 PSO 算法的寻优 能力就变得非常有限。试验指出在算法的运行的初始阶段，收 敛速度比较快，运动轨迹呈正弦波摆动，但 运行一段时间后，速度开始减慢甚至停滞 34。当所有粒子的速度几乎为 0，此时粒 子群丧失了进一步进化的能力，可以认为算 法执行已经收敛。而在许多情况下 （如复杂 的多峰函数寻优），算法并没有收敛到全局 极值，甚至连局部极值也未必达到。这种现 象被称为早熟收敛或停滞（Stagnation）。发生 该现象时粒子群高度聚集，严重缺乏多样 性，粒子群会长时间或永远跳不出聚集点。 因此大量对粒子群优化算法的改进集中在 提高粒子群的多样性上，使得粒子群在整个 迭代过

11、程中能保持进一步优化的能力。 4 改进粒子群算法 4.1改进粒子群算法数学模型改进粒子群算法从BP神经网络中得到 启示。 BP 算法是目前处理多层次神经网络 问题常用的方法。它使用梯度下降法来减少 实际输出结果和预测输出结果之间的误差。 但是它存在着在局部最优值附近的停滞和 振荡，从而陷入局部最优，不容易得到全局 最优解。对这个问题通过以下的方法改进。 这种改进如同使用低通滤波器来平滑权重 5。其数学表达式为：yt 二（1 _九）* xt + 九 * yt-1（3）其中，X e 0,1，x为需要被平滑的信 号序列，xf为时间t时信号的值，yt为滤波 器在时间t时的输出。九取的值愈大，平滑 性能

12、越好。因此，通过对 PSO 的速度更新方程引入新 的参数如下：Vk+1 = (1 - X)Vk + c * rand() * X k 一 X idid 1idid ( pbesr )+c *rand()*Xk -X+X*Vk-12 idid ( gbest )id(4)X k+1 = X k + V k+1(5)idid id与原始PSO方程相比，改进的PSO算法增加了 X * Vk-1这项，其中X为引入项的系 id数。这种改进同已经存在的对速度更新方程 改进方法相比，很不相同。这是因为，原有 的对粒子速度更新方程为一阶差分方程，而 本文的改进型 PSO 的粒子更新速度方程为 二阶差分方程。这

13、种改进的 PSO 的主要优点有：1.简单 易操作。本文所采用的改进型 PSO 无论是 在数学表达式还是在程序的执行方面都具 有很强的操作性，由于没有引入复杂的操作 和数据结构，因此操作比较容易。 2.平滑粒 子的运动轨迹，消除了在迭代后期的振荡不 收敛而陷入了局部最优的停滞。 3.本文的改 进 PSO 几乎可以应用在已经存在的所有具 有明确粒子速度更新方程的改进型 PSO 算 法中，例如惯性权重改变型PSO6,收缩因 子改变型PSO7，混合型PSO8等。4.2改进型PS0流程图改进型 PSO 流程图如图2 所示：初始化粒子群计算每个粒子的适应度根据粒子的适应度更新 pbexr和gbexi由公式

14、和更新粒子群的速度和位置达到最大迭代次数或解在误差范围允许内YES结束 I图2改进型PSO流程图5 实验与结果分析5.1 测试函数为了验证改进型 PSO 算法的性能，目前该领域的研究人员一般采用下列测试函数，图3是这些函数的图像。(sin Jx2 + x2 )2 一 0.5 f4(x) = O1匚1 + 0.001( x 2 + x 2)21 2Schaffer函数是二维函数，全局极小点在x* = (0,0)，全局最小值f (x*) = 0。5.2改进PSO算法的评价指标为了表征改进PSO算法的性能，需要 引入评价指标。本文引入以下四个评价指 标，它们分别是：收敛精度误差、算法成功比率0、收敛

15、速度Y和迭代收敛曲线。其成功运行时间算法总运行时间成功运行时间是小值 f (x*) = 0。(4) Schaffer 函数:图3测试函数9 10(从左上到右下依次为Sphere函数、Rosenbrock 函数、Rastrigrin 函数、Schaffer 函数)(1) Sphere 函数：X 2i=1全局极小点在X* = (0,0,.0)，全局最小值 f (x*) = 0。(2) Rosenbrock 函数：f (x) = E100(x -X2)2 + (x -1)22i+1iii=1Rosenbrock函数是一个单峰函数，各变 量之间有很强的耦合性。它的全局最小点在 X* = (h1,D ,全局最小值f (X* ) = 0。(3) Rastrigrin 函数：f (x)=工x2 一 10cos(2兀x +10)3 iii=1Rastrigin函数是一个多峰函数，有很多 正弦突起的局部