水资源系统分析理论与应用

水资源系统分析理论与应用课程

论文

学院：水文水资源

专业：水利工程

题目：粒子群算法（VBA）

学号：171601010078

指导老师：王建群

姓名：张轶文

2017年11月14日

粒子群算法

张轶文

（学号：161601010078，专业：水利工程）

一、粒子群算法的起源

粒子群优化(Particle Swarm Optimization, PSO)算法是Kennedy和Eberhart受人工生命研究结果的启发、通过模拟鸟群觅食过程中的迁徙和群聚行为而提出的一种基于群体智能的全局随机搜索算法，1995年IEEE国际神经网络学术会议发表了题为“Particle Swarm Optimization”的论文，标志PSO算法诞生(注：国内也有很多学者译为“微粒群优化”)。它与其他进化算法一样，也是基于“种群”和“进化”的概念，通过个体间的协作与竞争，实现复杂空间最优解的搜索；同时，PSO又不像其他进化算法那样对个体进行交叉、变异、选择等进化算子操作，而是将群体(swarm)中的个体看作是在D维搜索空间中没有质量和体积的粒子(particle)，每个粒子以一定的速度在解空间运动，并向自身历史最佳位置pbest和邻域历史最佳位置pbest聚集，实现对候选解的进化。PSO 算法具有很好的生物社会背景而易理解、参数少而易实现，对非线性、多峰问题均具有较强的全局搜索能力，在科学研究与工程实践中得到了广泛关注。

自然界中各种生物体均具有一定的群体行为，而人工生命的主要研究领域之一是探索自然界生物的群体行为，从而在计算机上构建其群体模型。自然界中的鸟群和鱼群的群体行为一直是科学家的研究兴趣，生物学家Craig Reynolds在1987年提出了一个非常有影响的鸟群聚集模型，在他的仿真中，每一个个体遵循：

(1) 避免与邻域个体相冲撞；

(2) 匹配邻域个体的速度；

(3) 飞向鸟群中心，且整个群体飞向目标。

仿真中仅利用上面三条简单的规则，就可以非常接近的模拟出鸟群飞行的现象。1990年，生物学家Frank Heppner也提出了鸟类模型，它的不同之处在于：鸟类被吸引飞到栖息地。在仿真中，一开始每一只鸟都没有特定的飞行目标，只

是使用简单的规则确定自己的飞行方向和飞行速度（每一只鸟都试图留在鸟群中而又不相互碰撞），当有一只鸟飞到栖息地时，它周围的鸟也会跟着飞向栖息地， 这样，整个鸟群都会落在栖息地。

1995年，美国社会心理学家James Kennedy 和电气工程Russell Eberhart 共同提出了粒子群算法，其基本思想是受对鸟类群体行为进行建模与仿真的研究结果的启发。他们的模型和仿真算法主要对Frank Heppner 的模型进行了修正，以使粒子飞向解空间并在最好解处降落。Kennedy 在他的书中描述了粒子群算法思想的起源。自20世纪30年代以来，社会心理学的发展揭示：我们都是鱼群或鸟群聚集行为的遵循者。在人们的不断交互过程中，由于相互的影响和模仿，他们总会变得更相似，结果就形成了规范和文明。人类的自然行为和鱼群及鸟群并不类似，而人类在高维认知空间中的思维轨迹却与之非常类似。思维背后的社会现象远比鱼群和鸟群聚集过程中的优美动作复杂的多：首先，思维发生在信念空间，其维数远远高于3；其次，当两种思想在认知空间会聚于同一点时，我们称其一致，而不是发生冲突。

二、算法的基本原理

PSO 中，每个优化问题的潜在解都是搜索空间中的一只鸟，称之为粒子。所有的粒子都有一个由被优化的函数决定的适值(fitness value) ，每个粒子还有一个速度决定它们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。PSO 初始化为一群随机粒子(随机解)，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己；第一个就是粒子本身所找到的最优解，这个解称为个体极值；另一个极值是整个种群目前找到的最优解，这个极值是全局极值。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。

假设在一个D 维的目标搜索空间中，有m 个粒子组成一个群落，其中第i 个粒子表示为一个D 维的向量

),,,(21iD i i i x x x X =，N i ,,2,1 =

第i 个粒子的“飞行 ”速度也是一个D 维的向量，记为

),,21i iD i i v v v V ，（=，3,2,1 =i

第i 个粒子迄今为止搜索到的最优位置称为个体极值，记为

),,,(21iD i i best p p p p =，N i ,,2,1 =

整个粒子群迄今为止搜索到的最优位置为全局极值，记为

),,,(21gD g g best p p p g =

在找到这两个最优值时，粒子根据如下的公式(2.1)和( 2.2)来更新自己的速度和位置：

())(2211id gd id id id id x p r c x p r c v w v -+-+*= (2.1)

id id id v x x += (2. 2)

其中：1c 和2c 为学习因子，也称加速常数，1r 和2r 为[0，1]范围内的均匀随机数。式(2.1)右边由三部分组成，第一部分为“惯性”或“动量”部分，反映了粒子的运动“习惯”，代表粒子有维持自己先前速度的趋势；第二部分为“认知”部分，反映了粒子对自身历史经验的记忆或回忆，代表粒子有向自身历史最佳位置逼近的趋势；第三部分为“社会”部分，反映了粒子间协同合作与知识共享的群体历史经验，代表粒子有向群体或邻域历史最佳位置逼近的趋势，根据经验，

通常221==c c 。id v 是粒子的速度。],[max max v v v id -∈，max v 是常数，由用户设定

用来限制粒子的速度。1r 和2r 是介于[0,1]之间的随机数。

带有惯性权重的改进粒子群算法其进化过程为：

))

()()(())()()(()()1(2211t x t p t r c t x t p t r c t wv t v ij gi ij ij ij ij -+-+=+ （2.3）

)1()()1(++=+t v t x t x ij ij ij （2.4） 在式(2.1)中，第一部分表示粒子先前的速度，用于保证算法的全局收敛性能；第二部分、第三部分则是使算法具有局部收敛能力。可以看出，式（2.3)中惯性