粒子群优化算法及其参数设置

百度文库-张曦元

粒子群优化算法及其参数设置

专 业：信息与计算科学 学 生： 指导教师：

摘 要

粒子群优化是一种新兴的基于群体智能的启发式全局搜索算法，粒子群优化算法通过粒子间的竞争和协作以实现在复杂搜索空间中寻找全局最优点。它具有易理解、易实现、全局搜索能力强等特点，倍受科学与工程领域的广泛关注，已经成为发展最快的智能优化算法之一。论文介绍了粒子群优化算法的基本原理，分析了其特点。论文中围绕粒子群优化算法的原理、特点、参数设置与应用等方面进行全面综述，重点利用单因子方差分析方法，分析了粒群优化算法中的惯性权值，加速因子的设置对算法基本性能的影响，给出算法中的经验参数设置。最后对其未来的研究提出了一些建议及研究方向的展望。

关键词：粒子群优化算法；参数；方差分析；最优解

I

百度文库-张曦元

目 录

摘 要................................................................................................................................... I Abstract ............................................................................................. 错误！未定义书签。 1.引言.................................................................................................................................. 1

1.1 研究背景和课题意义 .......................................................................................... 1 1.2 参数的影响 .......................................................................................................... 1 1.3 应用领域 .............................................................................................................. 2 1.4 电子资源 .............................................................................................................. 2 1.5 主要工作 .............................................................................................................. 2 2.基本粒子群算法 .............................................................................................................. 3

2.1 粒子群算法思想的起源 ...................................................................................... 3 2.2 算法原理 .............................................................................................................. 4 2.3 基本粒子群算法流程 .......................................................................................... 5 2.4 特点 ...................................................................................................................... 6 2.5 带惯性权重的粒子群算法 .................................................................................. 7 2.7 粒子群算法的研究现状 ...................................................................................... 8 3.粒子群优化算法的改进策略 .......................................................................................... 9

3.1 粒子群初始化 ...................................................................................................... 9 3.2 邻域拓扑 .............................................................................................................. 9 3.3 混合策略 ............................................................................................................ 12 4.参数设置 ....................................................................................................................... 14

4.1 对参数的仿真研究 ............................................................................................ 14 4.2 测试仿真函数 .................................................................................................... 15 4.3 应用单因子方差分析参数对结果影响 ............................................................ 33 4.4 对参数的理论分析 ............................................................................................ 34 5结论与展望 .................................................................................................................... 39 致谢................................................................................................................................... 40 附录................................................................................................................................... 41

II

百度文库-张曦元

1.引言

1.1 研究背景和课题意义

“人工生命”是来研究具有某些生命基本特征的人工系统。人工生命包括两方面的内容：

1、研究如何利用计算技术研究生物现象。 2、研究如何利用生物技术研究计算问题。

现在已经有很多源于生物现象的计算技巧。 例如，人工神经网络是简化的大脑模型。遗传算法是模拟基因进化过程的。现在我们讨论另一种生物系统- 社会系统。也可称做“群智能”(swarm intelligence)。这些模拟系统利用局部信息从而可能产生不可预测的群体行为。

粒子群优化算法(PSO) 也是起源对简单社会系统的模拟。最初设想是模拟鸟群觅食的过程。但后来发现PSO是一种很好的优化工具。

优化是科学研究、工程技术和经济管理等领域的重要研究课题。粒子群优化算法[1] (简称PSO)是由Kennedy和Eberhart通过对鸟群、鱼群和人类社会某些行为的观察研究，于1995年提出的一种新颖的进化算法。虽然PSO算法发展迅速并取得了可观的研究成果,但其理论基础仍相对薄弱，尤其是算法基本模型中的参数设置和优化问题还缺乏成熟的理论论证和研究。鉴于PSO的发展历史尚短，它在理论基础与应用推广上都还存在一些缺陷，有待解决。本文通过对PSO算法的步骤的归纳、特点的分析，利用统计中的方差分析，通过抽样实验方法，论证了该算法中关键参数因子:惯性权值、加速因子对算法整体性能的影响效果，并提出了参数设置的指导原则，给出了关键参数设置，为PSO算法的推广与改进提供了思路。

1.2 参数的影响

标准粒子群算法中主要的参数变量为w（惯性权值），c1 ，c2（加速因子），

vmax，本文重点对参数w，c1 ，c2做数据统计实验。包括w不变的情况下通过c1，c2变化找出加速因子对算法的影响。还有保持c1，c2不变对w分别取不同值分析其对算法结果影响。

1

百度文库-张曦元

1.3 应用领域

近年来，PSO快速发展，在众多领域得到了广泛应用。本文将应用研究分典型理论问题研究和实际工业应用两大类。典型理论问题包括：组合优化、约束优化、多目标优化、动态系统优化等。

实际工业应用有：电力系统、滤波器设计、自动控制、数据聚类、模式识别与图像处理、化工、机械、通信、机器人、经济、生物信息、医学、任务分配、TSP等等。

1.4 电子资源

身处信息和网络时代的我们是幸运的，丰富的电子资源能让我们受益匪浅。如果想较快地对PSO有一个比较全面的了解，借助网络空间的电子资源无疑是不二之选。对一些初学者而言，哪里能下载得到PSO的源程序，是他们很关心的话题；即使对一些资深的读者，为了验证自己提出的新算法或改进算法，如果能找到高级别国际期刊或会议上最近提出的算法源程序，那也是事半功倍的美事。这里介绍当今PSO研究领域较有影响的一个网址：

Maurice Clerc 博士(Maurice.Clerc@WriteMe.com)的PSO主页：

http://clerc.maurice.free.fr/pso/

该主页主要介绍Maurice Clerc博士带领的PSO研究小组的研究成果。除了从中可以得到他们近几年公开发表的相关文献和源代码，还可以下载一些未公开发表的文章。这些未公开发表的文章往往是Maurice Clerc博士的一些设想，而且在不断更新，如“Back to random topology”、“Initialisations for particle swarm optimization”、“Some ideas about PSO”等等，对PSO研究人员很有启发。

1.5 主要工作

论文内容介绍了基本粒子群算法，用matlab实现标准粒子群算法算法，对两个不同类型函数做具体分析，然后对其参数w（惯性权值），c1，c2（加速因子）测试。分别对其利用单因子方差分析法，说明不同参数水平对算法速率性能的影响。并且通过公式计算准确判断参数对算法影响。最后说明粒子群优化算法在实际中的应用以及对未来展望，最后总结了算法的优缺点，附录里面附有测试程序和测试函数。

2

百度文库-张曦元

2.基本粒子群算法

2.1 粒子群算法思想的起源

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

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

(1) 避免与邻域个体相冲撞； (2) 匹配邻域个体的速度；

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

仿真中仅利用上面三条简单的规则，就可以非常接近的模拟出鸟群飞行的现象。1990年，生物学家Frank Heppner也提出了鸟类模型[8]，它的不同之处在于：鸟类被吸引飞到栖息地。在仿真中，一开始每一只鸟都没有特定的飞行目标，只是使用简单的规则确定自己的飞行方向和飞行速度（每一只鸟都试图留在鸟群中而又不相互碰撞），当有一只鸟飞到栖息地时，它周围的鸟也会跟着飞向栖息地，这样，整个鸟群都会落在栖息地。

1995年，美国社会心理学家James Kennedy和电气工程师Russell Eberhart共同提出了粒子群算法，其基本思想是受对鸟类群体行为进行建模与仿真的研究结果

3

百度文库-张曦元

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

2.2 算法原理

PSO从这种模型中得到启示并用于解决优化问题。PSO 中，每个优化问题的潜在解都是搜索空间中的一只鸟，称之为粒子。所有的粒子都有一个由被优化的函数决定的适值( fitness value) ，每个粒子还有一个速度决定它们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索[1]。

PSO初始化为一群随机粒子(随机解)，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己；第一个就是粒子本身所找到的最优解，这个解称为个体极值；另一个极值是整个种群目前找到的最优解，这个极值是全局极值。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。

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

Xi?(xi1,xi2,?,xiD)，i?1,2,?,N。

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

Vi?（vi1,vi2，?,viD)，i?1,2,?3。

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

pbest?(pi1,pi2,?,piD)，i?1,2,?,N。

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

gbest?(pg1,pg2,?,pgD)

4

百度文库-张曦元

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

vid?w?vid?c1r1?pid?xid??c2r2(pgd?xid) (2.1)

xid?xid?vid (2. 2)

其中：c1和c2为学习因子，也称加速常数(acceleration constant)，r1和r2为[0，1]范围内的均匀随机数。式(2.1)右边由三部分组成，第一部分为―惯性(inertia)‖或―动量(momentum)‖部分，反映了粒子的运动―习惯(habit)‖，代表粒子有维持自己先前速度的趋势；第二部分为―认知(cognition)‖部分，反映了粒子对自身历史经验的记忆(memory)或回忆(remembrance)，代表粒子有向自身历史最佳位置逼近的趋势；第三部分为―社会(social)‖部分，反映了粒子间协同合作与知识共享的群体历史经验，代表粒子有向群体或邻域历史最佳位置逼近的趋势，根据经验，通常c1?c2?2。i?1,2,?,D。vid是粒子的速度，vid?[?vmax,vmax]，vmax是常数，由用户设定用来限制粒子的速度。r1和r2是介于[0,1]之间的随机数[2][5]。

2.3 基本粒子群算法流程

算法的流程如下：

① 初始化粒子群，包括群体规模N，每个粒子的位置xi和速度Vi ② 计算每个粒子的适应度值Fit[i]；

③ 对每个粒子，用它的适应度值Fit[i]和个体极值pbest比较，如果（i）； Fit[i]?pbest(i) ，则用Fit[i]替换掉pbest（i）④ 对每个粒子，用它的适应度值Fit[i]和全局极值gbest比较，如果

Fit[i]?pbes(ti)则用Fit[i]替gbest；

⑤ 根据公式（2.1），（2.2）更新粒子的速度vi和位置xi ；

⑥ 如果满足结束条件(误差足够好或到达最大循环次数)退出，否则返回②。

5

百度文库-张曦元

开 始 初始化每个粒子的速度和位置 计算每个粒子的适应值 求出每个粒子的个体最优 求出整个群体的全局最优值 根据方程(2.1)对粒子的速度进行进化 根据方程(2.2)对粒子的位置进行进化 否 是否满足结束条件 是 输出结果

图2.1. PSO算法流程图

2.4 特点

1、式(2.1)中第1部分可理解为粒子先前的速度或惯性；第2部份可理解为粒子的“认知”行为，表示粒子本身的思考能力；第3部分可理解为粒子的“社会”行为，表示粒子之间的信息共享与相互合作。公式(2.2) 表示了粒子在求解空间中，由于相互影响导致的运动位置调整。整个求解过程中，惯性权重w、加速因子c1和

c2和最大速度vmax共同维护粒子对全局和局部搜索能力的平衡。

6

百度文库-张曦元

2、粒子群优化算法初期，其解群随进化代数表现了更强的随机性，正是由于其产生了下一代解群的较大的随机性，以及每代所有解的“信息”的共享性和各个解的“自我素质”的提高。

3、PSO 的一个优势就是采用实数编码，不需要像遗传算法一样采用二进制编

22码(或者采用针对实数的遗传操作) 。例如对于问题f?x12?x2求解， 粒子可?x3以直接编码为(x1,x2,x3) ，而适应度函数就是f(x) 。

4、粒子具有“记(x1,x2,x3)忆”的特性，它们通过“自我”学习和向“他人”学习，使其下一代解有针对性的从“先辈”那里继承更多的信息，从而能在较短的时间内找到最优解。

5、与遗传算法相比，粒子群优化算法的信息共享机制是很不同的:在遗传算法中，染色体互相共享信息，所以整个种群的移动是比较均匀的向最优区域移动;在粒子群优化算法中，信息流动是单向的，即只有gbest将信息给其他的粒子，这使得整个搜索更新过程跟随当前解。

2.5 带惯性权重的粒子群算法

探索是偏离原来的寻优轨迹去寻找一个更好的解，探索能力是一个算法的全局搜索能力。开发是利用一个好的解，继续原来的寻优轨迹去搜索更好的解，它是算法的局部搜索能力。如何确定局部搜索能力和全局搜索能力的比例，对一个问题的求解过程很重要。1998年，Yuhui Shi[9]提出了带有惯性权重的改进粒子群算法。其进化过程为：

vij(t?1)?wvij(t)?c1r1(t)(pij(t)?xij(t))?c2r2(t)(pgi(t)?xij(t)) （2.3）

xij(t?1)?xij(t)?vij(t?1) （2.4）

在式(2.1)中，第一部分表示粒子先前的速度，用于保证算法的全局收敛性能；第二部分、第三部分则是使算法具有局部收敛能力。可以看出，式（2.3)中惯性权重w表示在多大程度上保留原来的速度。w较大，全局收敛能力强，局部收敛能力弱；w较小，局部收敛能力强，全局收敛能力弱。

当w?1时，式(2.3)与式(2.1)完全一样，表明带惯性权重的粒子群算法是基本粒子群算法的扩展。实验结果表明，w在[0.8?1.2]之间时，PSO算法有更快的收

7

百度文库-张曦元

敛速度，而当w?1.2时，算法则易陷入局部极值。

2.7 粒子群算法的研究现状

在算法的理论研究方面。目前PSO算法还没有成熟的理论分析，少部分研究者对算法的收敛性进行了分析，大部分研究者在算法的结构和性能改善方面进行研究，包括参数分析，拓扑结构，粒子多样性保持，算法融合和性能比较等。PSO由于有简单、易于实现、设置参数少、无需梯度信息等特点，其在连续非线性优化问题和组合优化问题中都表现出良好的效果。

8

百度文库-张曦元

3.粒子群优化算法的改进策略

由于PSO中粒子向自身历史最佳位置和邻域或群体历史最佳位置聚集，形成粒子种群的快速趋同效应，容易出现陷入局部极值、早熟收敛或停滞现象[12-14]。同时，PSO的性能也依赖于算法参数[15]。为了克服上述不足，各国研究人员相继提出了各种改进措施。本文将这些改进分为4类：粒子群初始化、邻域拓扑、参数选择和混合策略。

3.1 粒子群初始化

研究表明，粒子群初始化对算法性能产生一定影响[16]。为了初始种群尽可能均匀覆盖整个搜索空间，提高全局搜索能力，Richard 和Ventura[17]提出了基于centroidal voronoi tessellations (CVTs)的种群初始化方法；薛明志等人[18]采用正交设计方法对种群进行初始化；Campana 等人[19]将标准PSO迭代公式改写成线性动态系统，并基于此研究粒子群的初始位置，使它们具有正交的运动轨迹；文献[16]认为均匀分布随机数进行初始化实现容易但尤其对高维空间效果差，并另外比较了3种初始化分布方法。

3.2 邻域拓扑

根据粒子邻域是否为整个群体，PSO分为全局模型gbest和局部模型gbest [20]。对于gbest模型，每个粒子与整个群体的其他粒子进行信息交换，并有向所有粒子中的历史最佳位置移动的趋势。Kennedy[21]指出，gbest模型虽然具有较快的收敛速度，但更容易陷入局部极值。为了克服gbest全局模型的缺点，研究人员采用每个粒子仅在一定的邻域内进行信息交换，提出各种gbest局部模型[21,]。根据现有的研究成果，本文将邻域分为空间邻域(spatial neighborhood)、性能空间(performance space)邻域和社会关系邻域(sociometric neighborhood)。空间邻域直接在搜索空间按粒子间的距离(如欧式距离)进行划分，如Suganthan[23]引入一个时变的欧式空间邻域算子：在搜索初始阶段，将邻域定义为每个粒子自身；随着迭

9

百度文库-张曦元

代次数的增加，将邻域范围逐渐扩展到整个种群。性能空间指根据性能指标(如适应度、目标函数值)划分的邻域，如文献[24]采用适应度距离比值(fitness-distance-ratio)来选择粒子的相邻粒子。社会关系邻域通常按粒子存储阵列的索引编号进行划分

[25]

，这也是研究最多的一种划分手段，主要有[21]：环形拓扑(ring or circle topology)、

轮形拓扑(wheel topology)或星形拓扑(star topology)、塔形拓扑(pyramid topology)、冯－诺以曼拓扑(Von Neumann topology)以及随机拓扑(random topology)等。针对不同的优化问题，这些拓扑的性能表现各异；但总的来说，随机拓扑往往对大多数问题能表现出较好的性能，其次是冯－诺以曼拓扑[22]。M. Clerc[25]对随机拓扑进行了进一步分析，并在2006年版和2007年版的标准PSO[23]中采用了随机拓扑。此外，文献[21]提出动态社会关系拓扑(Dynamic sociometry)，初始阶段粒子采用环形拓扑(ring-type topology)，随着迭代次数的增加，逐渐增加粒子间连接，最后形成星形拓扑(star-type topology)。

此外，还有其它一些主要对群体进行划分的邻域结构(本文暂称“宏观邻域”；则上述邻域称为“微观邻域”)。文献[19]引入了子种群，子种群间通过繁殖(Breeding)实现信息交流。Kennedy[20]提出了社会趋同(Stereotyping)模型，使用簇分析将整个粒子群划分为多个簇，然后用簇中心代替带收缩因子PSO中的粒子历史最佳位置或群体历史最佳位置。X. Li[21]根据粒子相似性动态地将粒子群体按种类划分为多个子种群，再以每个子种群的最佳个体作为每个粒子的邻域最佳位置。Stefan Janson等人[22]提出等级PSO(hierarchical particle swarm optimizer, HPSO)，采用动态等级树作为邻域结构，历史最佳位置更优的粒子处于上层，每个粒子的速度由自身历史最佳位置和等级树中处于该粒子上一个节点的粒子的历史最佳位置决定。文献[13]采用主－仆模型(master–slaver model)，其中包含一个主群体，多个仆群体，仆群体进行独立的搜索，主群体在仆群体提供的最佳位置基础上开展搜索。文献[14]将小生境(niche)技术引入到PSO中，提出了小生境PSO(Niching Particle Swarm Optimizer)。文献[15]采用多群体进行解的搜索。文献[14]则每间隔一定代数将整个群体随机地重新划分，提出动态多群体PSO。

在标准的PSO算法中，所有粒子仅仅向自身和邻域的历史最佳位置聚集，而没有向邻域内其他个体(即使这些个体很优秀)学习，造成信息资源的浪费，甚至因此而陷入局部极值；考虑到此因素，Kennedy 等人[17]提出了全信息粒子群(fully informed particle swarm, FIPS)，在FIPS中，每个粒子除了自身和邻域最佳历史位置外，还学习邻域内其他粒子的成功经验。

上述粒子间学习是在整个D维空间中构造邻域进行的，这样当搜索空间维数较高时往往容易遭受―维数灾(curse of dimensionality)‖的困扰[14]。基于这方面的考

10

百度文库-张曦元

虑，Van den Bergh等人[18]提出了协作PSO(Cooperative PSO)算法，其基本思路就是采用协作行为，利用多个群体分别在目标搜索空间中的不同维度上进行搜索，也就是一个优化解由多个独立群体协作完成，每个群体只负责优化这个解矢量部分维上的分量。Baskar和Suganthan[19]提出一种类似的协作PSO，称为并发PSO(concurrent PSO， CONPSO)，它采用两个群体并发地优化一个解矢量。近来，El-Abd 等人[20]结合文献[18,19]的技术，提出了等级协作PSO(hierarchal cooperative PSO)。

无论是粒子群在D-维的搜索还是多个粒子群在不同维上的协作搜索，其目的都是为了每个粒子能够找到有利于快速收敛到全局最优解的学习对象。J. Liang 等人[4]提出了一种既可以进行D-维空间搜索、又能在不同维上选择不同学习对象的新的学习策略，称为全面学习PSO (Comprehensive Learning Particle Swarm Optimizer，CLPSO)。与传统PSO只向自身历史最佳位置和邻域历史最佳位置学习不同，CLPSO的每个粒子都随机地向自身或其它粒子学习，并且其每一维可以向不同的粒子学习；该学习策略使得每个粒子拥有更多的学习对象，可以在更大的潜在空间飞行，从而有利于全局搜索。CLPSO的速度更新公式为：

vij(t)?wvij(t?1)??r(pfi(j),j)?x（ （3.1） ）ijt?1其中?为加速因子，r为[0,1]内的均匀随机数，fi(j)表示粒子i在第维的学习对象，它通过下面的策略决定：产生[0,1]内的均匀随机数，如果j该随机数大于为粒子i预先给定的学习概率pci，则学习对象为自身历史最佳位置；否则，从种群内随机选取两个个体，按锦标赛选择(tournament selection)策略选出两者中最好的历史最佳位置作为学习对象。同时，为了确保粒子尽可能向好的对象学习而不把时间浪费在较差的对象上，上述学习对象选择过程设定一个更新间隔代数(refreshing gap)，在此期间的学习对象保持上次选择的学习对象不变。

以上的各种邻域结构，无论是微观拓扑还是宏观邻域，也无论是在整个搜索空间进行信息交流还是以空间的不同维分量为单位协作搜索，都不主动改变邻域状态，而只是在给定的邻域内进行学习交流，本文称之为PSO的被动局部模型。还有一类局部模型就是主动改变粒子邻域空间，避免碰撞和拥挤，本文称之为PSO的主动局部模型。Blackwell 等人[3]将粒子分为自然粒子和带电粒子，当带电粒子过于接近时产生斥力，使之分开以提高粒子多样性；L?vbjerg 等人为每个粒子引入与相邻粒子距离成反比的自组织危险度(self-organized criticality)指标，距离越近

11

百度文库-张曦元

则危险度越高，当达到一定阈值后，对该粒子进行重新初始化或推开一定距离降低危险度，达到提高群体多样性的目的；文献[15]提出一种带空间粒子扩展的PSO，为每个粒子赋一半径，以检测两个粒子是否会碰撞，并采取随机弹离、实际物理弹离、简单的速度—直线弹离等措施将其分开。

3.3 混合策略

混合策略混合PSO就是将其它进化算法或传统优化算法或其它技术应用到PSO中，用于提高粒子多样性、增强粒子的全局探索能力，或者提高局部开发能力、增强收敛速度与精度。这种结合的途径通常有两种：一是利用其它优化技术自适应调整收缩因子/惯性权值、加速常数等；二是将PSO与其它进化算法操作算子或其它技术结合。文献[16]将蚂蚁算法与PSO结合用于求解离散优化问题；Robinson 等人[17]和Juang[18]将GA与PSO结合分别用于天线优化设计和递归神经网络设计；文献

[19]

将种群动态划分成多个子种群，再对不同的子种群利用PSO或GA或爬山法进行

独立进化；Naka等人[10]将GA中的选择操作引入到PSO中，按一定选择率复制较优个体；Angeline [11]则将锦标赛选择引入PSO 算法，根据个体当前位置的适应度，将每一个个体与其它若干个个体相比较，然后依据比较结果对整个群体进行排序，用粒子群中最好一半的当前位置和速度替换最差一半的位置和速度，同时保留每个个体所记忆的个体最好位置；El-Dib 等人[12]对粒子位置和速度进行交叉操作；Higashi [13]将高斯变异引入到PSO中；Miranda等人[14]则使用了变异、选择和繁殖多种操作同时自适应确定速度更新公式中的邻域最佳位置以及惯性权值和加速常数；Zhang等人[8]利用差分进化(DE)操作选择速度更新公式中的粒子最佳位置；而Kannan 等人[18]则利用DE来优化PSO的惯性权值和加速常数。

此外，其它一些搜索技术与PSO结合以提高算法的局部搜索能力，如文献[9]提出一种基于PSO和Levenberg-Marquardt的混合方法;文献[10]将PSO与单纯形法相结合；文献将PSO与序贯二次规划相结合；文献[12]将模拟退火与PSO结合；文献[13]将禁忌技术与PSO结合；文献[8]将爬山法与PSO结合；文献[15]将PSO与拟牛顿法结合。

还有作者引入其它一些机制，以改进PSO的性能。文献[6]根据耗散结构的自组织性，提出一种耗散粒子群优化算法(dissipative PSO)。该算法通过附加噪声持续为粒子群引入负熵(negative entropy)，使得系统处于远离平衡态的状态，又由于群体中存在内在的非线性相互作用，从而形成自组织耗散结构，使粒子群能够―持续进化‖，抑制早熟停滞。文献[7]将自然进化过程中的群体灭绝现象引入PSO，在微

12

百度文库-张曦元

粒的位置和速度更新之后，按照一个预先定义的灭绝间隔重新初始化所有微粒的速度。文献[8]通过模拟自然界的被动聚集(Passive Congregation)行为修改速度更新公式，实现种群内信息充分共享，防止了微粒因缺乏足够的信息而判断失误所导致陷入局部极小。文献[9]将引力场模型引入到PSO。此外，还有其它一些混合PSO：

1）高斯PSO：由于传统PSO往往是在全局和局部最佳位置的中间进行搜索，搜索能力和收敛性能严重依赖加速常数和惯性权值的设置，为了克服该不足，Secrest等人[10]将高斯函数引入PSO算法中，用于引导粒子的运动；GPSO不再需要惯性权值，而加速常数由服从高斯分布的随机数产生。

2）拉伸PSO(Stretching PSO, SPSO)：SPSO将所谓的拉伸技术(stretching technique)[11]以及偏转和排斥技术应用到PSO中，对目标函数进行变换，限制粒子向已经发现的局部最小解运动，从而利于粒子有更多的机会找到全局最优解[4, 6]。

混沌粒子群优化：混沌是自然界一种看似杂乱、其实暗含内在规律性的常见非线性现象，具有随机性、遍历性和规律性特点。文献[3]利用混沌运动的遍历性以粒子群的历史最佳位置为基础产生混沌序列，并将此序列中的最优位置随机替代粒子群中的某个粒子的位置，提出混沌PSO (chaos particle swarm optimization, CPSO)。除此之外，文献[4]利用惯性权值自适应于目标函数值的自适应PSO进行全局搜索、利用混沌局部搜索对最佳位置进行局部搜索，提出一种PSO与混沌搜索相结合的混沌PSO；文献[15]则利用混沌序列确定PSO的参数(惯性权值和加速常数);文献[9]提出一种不含随机参数、基于确定性混沌Hopfield神经网络群的粒子群模型。

3）免疫粒子群优化：生物免疫系统是一个高度鲁棒性、分布性、自适应性并具有强大识别能力、学习和记忆能力的非线性系统。文献[6]将免疫系统的免疫信息处理机制(抗体多样性、免疫记忆、免疫自我调节等)引入到PSO中，分别提出了基于疫苗接种的免疫PSO和基于免疫记忆的免疫PSO。

4）量子粒子群优化：文献[9]采用量子个体提出离散PSO；文献[9]则基于量子行为更新粒子位置。

5）卡尔曼PSO：文献[9]利用Kalman滤波更新粒子位置。

主成分PSO：文献[10]结合主成分分析技术，粒子不仅按照传统算法在n维的x空间飞行，而且还在m维的z空间同步飞行(m?n)。

13

百度文库-张曦元

4.参数设置

4.1 对参数的仿真研究

PSO的参数主要包括最大速度、两个加速常数和惯性常数或收缩因等。 a) 最大速度的选择：如式(2.1)所示的粒子速度是一个随机变量，由粒子位置更新公式(2.2)产生的运动轨迹是不可控的，使得粒子在问题空间循环跳动[3, 6]。为了抑制这种无规律的跳动，速度往往被限制在??vmax,vmax?内。vmax增大，有利于全局探索(global exploration)；vmax减小，则有利于局部开发(local exploitation)[3]。但是vmax过高，粒子运动轨迹可能失去规律性，甚至越过最优解所在区域，导致算法难以收敛而陷入停滞状态；相反vmax太小，粒子运动步长太短，算法可能陷入局部极值[16]。vmax的选择通常凭经验给定，并一般设定为问题空间的10?20% [3]。此外，文献[17]提出了的动态调节方法以改善算法性能；而文献[48]提出了vmax自适应于群体最佳和最差适应度值vmax的选择方法。

b) 加速常数的选择：式(1)中的加速常数c2和c2分别用于控制粒子指向自身或邻域最佳位置的运动。文献[20]建议??c1?c2?4.0，并通常取c1?c2?2。Ratnaweera 等人[13]则提出自适应时变调整策略，即c1随着进化代数从2.5线性递减至0.5，与传统PSO取正数加速常数不同，Rigetc2随着进化代数从0.5线性递增至2.5。和Vesterstrom[11]提出一种增加种群多样性的粒子群算法，根据群体多样性指标调整加速常数的正负号，动态地改变―吸引‖(Attractive)和―扩散‖(Repulsive)状态，以改善算法过早收敛问题。

c) 惯性权值或收缩因子的选择：当PSO的速度更新公式采用式(1)时，即使vmax和两个加速因子选择合适，粒子仍然可能飞出问题空间，甚至趋于无穷大，发生群体“爆炸(explosion)”现象[12]。有两种方法控制这种现象：惯性常数(inertia constant)[3]和收缩因子(constriction factor)[12]。带惯性常数PSO的速度更新公式如下：

14

百度文库-张曦元

（4.1） vijt?wvijt?1?c1r（?c2r2(t（)pij?xijt）1pij?xijt）其中为惯性常数。文献[8]建议随着更新代数的增加从0.9线性递减至0.4。近来，文献[15]通过采用随机近似理论(stochastic approximation theory)分析PSO的动态行为，提出了一种随更新代数递减至0的取值策略，以提高算法的搜索能力。带收缩因子PSO由Clerc 和 Kennedy[12]提出，其最简单形式[20]的速度更新 公式如下：

（4.2） vijt?xvijt?1?c1r（?c2r2(t（)pij?xijt）1pij?xijt）其中x?22?????4?2，??c1?c2?4.0；通常??4.1从而x?0.729，

c1?c2?1.49445。

虽然惯性权值PSO和收缩因子PSO对典型测试函数表现出各自的优势[16]，但由

于惯性常数方法通常采用惯性权值随更新代数增加而递减的策略，算法后期由于惯性权值过小，会失去探索新区域的能力，而收缩因子方法则不存在此不足[18]。

4.2 测试仿真函数

例1. 函数f(x)??xi对于适应度函数fitness对其参数w，c1，c3做出不同方

2i?110式的比较已测试其对函数结果影响。

（1）当c11?c21?2，c12?c22?1.5，w?1.2。 当惯性权值不变c1?c2的情况下对c取不同的值1.5和2。 程序（1）运行结果为：

15

百度文库-张曦元

图4.1 粒子群位置初始化

16

百度文库-张曦元

图4.2 粒子群速度初始化

17

百度文库-张曦元

图4.3 迭代结果对比

最优点坐标（1）： [0.452429778718878 -0.037721251936116 0.059472309970162 0.840740574648050]

最优点坐标（2）： [-0.295863893648182 0.475115714243873 -0.262874734324870 0.248526708588574]

适应度值（1）为：1.690633278729210 适应度值（2）为：0.769455496424646

（2）当c11?c21?2于c12?0,c22?2,w?1.2对比（加速因子c1?0与正常情况对比）且运行程序（2）得如下结果：

18

0.320640272233576 -0.587907547759961 -0.105031512919075

0.521629692208334 -0.197327841733574 -0.060192285082351

-0.228564770714395 -0.330571564292149 -0.134696331837768

0.244463764764120 -0.153811057636018 -0.249466572982610

百度文库-张曦元

图4.4 初始化速度

19

百度文库-张曦元

图4.5 初始化速度

20

百度文库-张曦元

图4.6 迭代结果对比

最优点坐标（1）： [-0.301082521586939 -0.002964214272033 -0.888573463449087 -0.243136586226299]

最优点坐标（2）： [-0.541610401047606 0.669477968063575 0.051863122302620 0.009764111144065]

适应度值（1）为：1.759984065528661 适应度值（2）为：1.424283049626009

（3）当c11?c21?2,w?1.2于c12?2,c22?0,w?1.2对比（加速因子c2?0与正常情况对比）的结果为：

-0.107148776434457

-0.066670850819150 0.605184616096295 0.406977740018377

-0.349186281873742 -0.101089710356064

0.130176903218111

0.149468203209848 -0.123775878581260 0.707421391133458

-0.101420705756867 0.505280093056671

21

百度文库-张曦元

图4.7 初始化位置

22

百度文库-张曦元

图4.8 初速度位置

23

百度文库-张曦元

图4.9 迭代结果对比

最优点坐标（1）： [0.032596367547015 -0.184050929120391 -0.505184051372427 -0.194148350056426]

最优点坐标（2）： [-1.099975300165443 0.620982109338000 0.595836418318090 -0.344875728471985]

适应度值（1）为：0.801579381651326 适应度值（2）为：2.208540081759679

（4）当c1?c2，w1?w2分别对其取值c1?1.1，c2?2，w1?1.2，w2?1.5。分析结果如下：

24

-0.253447234013828 -0.060526233943504 0.081261771085495

0.220174027850755 0.325089660099637 0.495050821497124

0.213471891229638 -0.022759191613578 0.059545555995647

0.230838988305651 0.136151982169503 0.132504460404116

百度文库-张曦元

图4.10 初始化位置

25

百度文库-张曦元

图4.11 初始化速度

26

百度文库-张曦元

图4.12 迭代结果对比

最优点坐标（1）： [-0.069619159841467 -0.630693562346744 0.624967732306244]

最优坐标（2）： [0.360645808223021 0.640951653807223 0.010556466456078]

适应度值（1）为：2.022968351158053 适应度值（2）为：1.850007680165146

（5）对c1?c2?2，对分别取w1?1.2，w2?0对比其迭代影响

-0.462713179464868 -0.309321710810512

0.172157445992416 0.519209219049760

0.161165210517313 0.158416597461891 -0.805569345032097

0.488557857942322 -0.360652175419648

-0.587877368802422 0.104997980821461

0.577000714765126 -0.255019353943860 -0.326212573465861

27

百度文库-张曦元

图4.13 初始化位置

28

百度文库-张曦元

图4.14 初速度位置

29

百度文库-张曦元

图4.15 迭代结果

最优点坐标（1）： [0.148332996728680 0.656268331316766 -0.069905771435114 0.060375755047727

最优坐标（2）： [-0.078496311635274 0.070447936565837 0.032804423901163 0.061389486373012]

适应度值（1）为：1.506027752348302 适应度值（2）为：108141522528168

（6）标准粒子群算法无参数对比c1?c2?2，w?1.2

0.464843694691154

-0.379559837826470 0.550631814306402 -0.044385131261800

0.104011057125470 -0.607186822378544

0.053450658106748 0.040978014348305 0.034324881708865 -0.038580266459785

-0.189785878868686 0.221247950866089

30

百度文库-张曦元

图4.16 粒子群位置初始化

31

百度文库-张曦元

图4.17 粒子群初始化速度

32

百度文库-张曦元

图4.18 迭代结果

在以上仿真中，我们5个实验实数的选择分别对c1，c2，w不同情况做出对比得出结论：

惯性权重w的不同取值对PSO的影响

试验表明权值w将影响PSO 的全局与局部搜优能力，w值较大，全局搜优能力强，局部搜优能力弱;反之，则局部搜优能力增强，而全局搜优能力减弱。线性惯性权的引入使PSO可以调节算法的全局与局部搜优能力，但，还有两个缺点:其一，迭代初期局部搜索能力较弱，即使初始粒子已接近于全局最优点，也往往错过;其二，在迭代后期，则因全局搜索能力变弱，而易陷入局部极值。w?1.05时，粒子群优化算法的搜索效率和搜索精度高。实验结果证明:按照方差分析选择适应的参数设置水平，能够获得稳健和高效的优化效果。

4.3 应用单因子方差分析参数对结果影响

按照方差分析选择适应的参数设置水平，能够获得稳健和高效的优化效果。关键参数设置如下:粒子种群大小N:较小的群能充分探索解空间，避免了过多的适应值评估和计算时间。一般取[20 -40]，对于大部分的问题， 10个粒子已经足够取得好的结果，对于比较难的问题或者特定类别的问题，粒子数可以取到100，200。

33

百度文库-张曦元

粒子的长度D(空间维数) :这是由优化问题决定，就是问题解的长度。粒子的坐标范围:由优化问题决定，每一维可以设定不同的范围。vmax决定粒子在一个循环中最大的移动距离，通常设为粒子的范围宽度。学习因子：c1 和c2通常等于2，不过文献中也有其它的取值，一般c1?c2，且范围在0和4之间。终止条件:按最大循环数及最小偏差要求，这个终止条件由具体问题确定。例如，最小错误可以设定为1 个错误分类，最大循环数设定为2000。惯性权值w:w 控制着速度前一变化量对当前变化量的影响，如果较w大，则影响较大，能够搜索以前所未能达到的区域，整个算法的全局搜索能力加强，有利于跳出局部极小点；而w值较小，则前一动量项的影响较小，主要是在当前解的附近搜索，局部搜索能力较强，有利于算法收敛。研究表明，让惯性权值随着叠代次数的增加在1. 4到0之间逐步减少可以取得较好的效果。

4.4 对参数的理论分析

方差分析是分析试验数据的一种方法。利用此方法亦可分析算法中同一参数的不同水平或者不同参数的各个水平对算法性能影响的差异性，从而探究不同参数设置范围与算法系统性能之间的潜在关系。单因子方差分析是通过观察一个因子的量值变化，分析这个因子变化对整个试验的影响程度。利用这种方法可考查PSO中c2和c2这两个关键的参数因子各自对算法性能的影响。在试验中影响指标的因素称为因子，因子所处的状态，所取的等级称为因子水平。本文采取相等的试验次数进行方差分析。首先，假定因子A有m个水平，在每种水平下，做k次试验，在每次试验后可得一试验值，记做xij它表示在第i个水平下的第j个试验值

i?1,2,?,m;j?1,2,?,k， 如表1 所示，在考察因子A对试验结果的影响程度时，

把因子A的m个水平A1,A2,,?,Am看成是m个正态总体，因此可设

Xij~N(ai,?2)， i?1,2,?,m， j?1,2,?,k。其中， ai????i，?i是因子A的第i水平Ai所引起的差异。因此检验因子A的各水平之间是否有显著的差异，相当于判断公式(4.2)：H01：a1?a2??或H01：?1??2????m?0(3)利用公式(4.1)

34

百度文库-张曦元

表述的平方和ST分解公式可将总的离差平方和进行分解，从而将因子水平不同而造成的结果差异与随机因素影响而造成的结果差异从量值上区分开来。

ST?Se?SA，ST???(xij?x)2 （4.3）

i?1j?1mk其中Se???(xij?x)?k?(xi?x)2，

2i?1j?1ki?1mkm1kSe???(xij?x)，xi??xij，

kj?1i?1j?12m1m1mkx??xi???xij

mi?1mi?1j?1总离差平方和ST是所有观察值xij与其总平均值x之差的平方和，是描述全部数据离散程度的数量指标。由于xij是服从正态分布的随机量，当公式(4.2) 成立时

xij是独立同分布。同正态分布的随机变

量， 则有公式(4.3) 是服从fT?mk?1的x2分布:

ST??(x?i?1j?1mkij?xi)2?2?2 （4.4）

Se是观察值xij与组内平均值xi之差的平方和，也就是组内平均和，它反映了

组内(同一水平下) 样本的随机波动，其自由度为fe?mk?m，是组内平均值xi与总平均值之差的平方和，即组间平方和。它在一定程度上反映了因子各个水平不同而引起的差异，其自由度为fA?m?1。平方和分解公式说明观察值关于其总平均值之的差异是由组内平方和组间平方和组成的。因此，公式(4.4) 表示的SA和Se之间的比值F就是反映了两种差异所占的比重。

35

百度文库-张曦元

SAF?Sem?1 （4.5）

m(k?1)F越大说明因子各水平不同引起的差异越显著，所以统计量F可用来检验各因子的影响效应。惯性权值w、加速常数c1和c2的不同设置水平，每个设置水平进行10次测试，通过单因子方差分析，说明不同参数水平对算法速率性能—迭代次数和算法优化性能———近似最优解的影响能力，能够获得比较一致的迭代次数均值， 且在此范围内进行更细致的单因子方差分析进一步证明较小的惯性权值能够提高算法速率。在需要较高计算速率的应用中，可适当减小惯性权值。

针对本程序（适应函数

f(x)??xii?1102）令c1?c2?2，

w1?0.4,w2?0.8,w3?1.2,w4?1.4做单因子方差分析，判断因子对程序的影响。运行程序（6），在此基础作5次试验的结果。

第一组实验对应w1?0.4的迭代次数为43，适应值为0.043133738358137 第一组实验对应w1?0.8的迭代次数为20，适应值为0.978441955858031 第一组实验对应w1?1.2的迭代次数为9，适应值为1.704780367886482 第一组实验对应w1?1.4的迭代次数为7，适应值为3.165437900832790

第二组实验对应w1?0.4的迭代次数为45， 适应值为0.116223586568965 第二组实验对应w1?0.8的迭代次数为132，适应值为0.024791910872392 第二组实验对应w1?1.2的迭代次数为8， 适应值为1.434014355783529 第二组实验对应w1?1.4的迭代次数为7， 适应值为4.109304406313233

第三组实验对应w1?0.4的迭代次数为47，适应值为0.028101866552785 第三组实验对应w1?0.8的迭代次数为80，适应值为0.978441955858031

36

百度文库-张曦元

第三组实验对应w1?1.2的迭代次数为8，适应值为1.704780367886482 第三组实验对应w1?1.4的迭代次数为9，适应值为4.109304406313233

第四组实验对应w1?0.4的迭代次数为44，适应值为0.004206314348390 第四组实验对应w1?0.8的迭代次数为85，适应值为0.002833378597589 第四组实验对应w1?1.2的迭代次数为12，适应值为1.147718650602618 第四组实验对应w1?1.4的迭代次数为9， 适应值为1.225161171509811

第五组实验对应w1?0.4的迭代次数为30，适应值为0.002959199530585 第五组实验对应w1?0.8的迭代次数为120，适应值为0.003593621732353 第五组实验对应w1?1.2的迭代次数为10，适应值为2.319085675976360 第五组实验对应w1?1.4的迭代次数为25， 适应值为0.577322689031719 现在讨论单因子方差分析，设A有4水平A1,A2,A3,A4在水平AJ(J?1,2,3,4,5)下进行5次试验，检验假设（??0.05）。

H0:?1??2??3??4 H1:?1,?2,?3,?4不全相等。

解：现在s?4，n1?n2?n3?n4?5，n?20。

37

百度文库-张曦元

水平 观察结果 1 2 3 4 5 样本总和 样本均值

W1=0.4 0.04313 0.11622 3.29793 0.00420 0.00295 3.46443 0.69288 W2=0.8 0.97844 1.70478 0.97844 0.00283 0.00359 3.66804 0.73361 W3=1.2 1.70473 1.43402 1.70471 1.14774 2.31905 8.30959 1.661918 W4=1.4 4.10930 1.43400 4.10930 1.22510 0.57730 11.4550 2.29100 T2 ST???X? （4.6）

20j?1i?1452ij SE???(Xij?Xij)2 （4.7）

J?1i?155nJ SA??njX.j?nX2 （4.8）

2j?1SAF?SE(s?1)(n?s) （4.9）

F?(s?1,n?s)=6.1 （4.10） 方差来源 因素 误差 总和 平方和 0.43212 0.04734 0.47946 自由度 3 20 23 均方 0.14404 0.00236 F比 64.4418 F0.05(3,20)?6.10000?64.4418故在H0认为参数变化对程序结果有显著影响。

38

本文来源：https://www.bwwdw.com/article/ec2g.html