第8章粒子群优化算法PSO

粒子群优化算法Particleswarmoptimization一种基于群智能的优化算法

第1节绪论

1.最优化问题

在满足一定的约束条件下，寻找一组参数值，以使某些最优性度量得到满足，即使系统的某些性能指标达到最大或最小。

其中，为目标函数，为约束函数，为约束域，

为维优化变量。最优化问题普遍存在于工业、社会、经济等各个领域。

第1节绪论

对于

当，为线性函数，且，上述最优化问题即为线性规划问题，有成熟的求解方法（单纯形法）。

线性规划（Linearprogramming,

LP）是运筹学中研究较早、发展较快、应用广泛、方法比较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法，是研究线性约束条件下线性目标函数的极值问题的数学理论和方法。广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学依据。举例：（标准型线性规划问题）

max

s.t:

变量非负：

数学模型具有以下特点：

1）若干个决策变量，决策变量的一组值表示一种方案，同时决策变量一般是非负的。2）目标函数是决策变量的线性函数，根据具体问题可以是最大化（max）或最小化（min），二者统称为最优化

3）约束条件也是决策变量的线性函数

第1节绪论

非线性规划

对于

当，当中至少有一个为非线性函数，上述最优化问题即为非线性规划问题，非常复杂，目前仍然没有一种有效的适应所有问题的求解方法。

2.全局优化算法全局最优解的定义：如果存在，使得对有：

成立，其中为由约束条件限定的搜索空间，则称为在

内的全局极小点，为其全局极小值。

对于目标函数为凸函数、约束域为凸域的所谓凸规划问题，局部最优与全局最优等效。而对于非凸问题，由于在约束域内目标函数存在多峰值，因而其全局最优与局部最优相差可能很大。为了可靠解决全局优化问题，人们试图离开解析确定型的优化算法研究，转而探讨对函数解析性质要求较低甚至不作要求的随机型优化方法。基于Monte-Carlo（蒙特卡洛）方法思想的随机型优化方法

针对具体问题性质的特点，构造以概率1收敛于全局最优点的随机搜索算法。仿生型智能优化算法是近些年来人们模拟自然界的一些自然现象而发展起来的一系列群体智能算法，如模拟退火方法、进化算法、等等，是比较有效且具有普遍适应性的随机全局优化方法。3.无免费午餐定理(NoFreeLunchTheorem,NFL)

对于所有可能的问题，任意给定两个算法A，A’，如果A在某些问题上表现比A’好(差)，那么A在其它问题上的表现就一定比A’差(好)，也就是说，任意两个算法A、A’对所有问题的平均表现度量是完全一样的。NFL定理的主要价值在于它对研究与应用优化算法时的观念性启示作用。当我们所面对的是一个大的而且形式多样的适应值函数类时，就必须考虑算法间所表现出的NFL效应。即如果算法A在某些函数上的表现超过算法A’，则在这类的其它函数上，算法A’的表现就比A要好。因此，对于整个函数类，不存在万能的最佳算法，所有算法在整个函数类上的平均表现度量是一样的。

4.优化算法的研究导向

(1)以算法为导向，从算法到问题。对于每一个算法，都有其适用和不适用的问题；给定一个算法，尽可能通过理论分析，给出其适用问题类的特征，使其成为一个“指示性”的算法。(2)以问题为导向，从问题到算法。对于一个小的特定的函数集，或者一个特定的实际问题，可以设计专门适用的算法。

第2节群智能算法的产生

1.背景

(1)在科学研究和工程领域，存在大量的优化问题，特别是，大规模、非线性、离散性、多目标等复杂的问题。(2)随着科学研究和工程应用面临的问题越来越复杂，使优化问题的求解难度越来越大。仅用传统的数学方法已经不能满足求解要求，迫切需要研究新的优化理论与技术。(1)0-1背包问题：有n个不同的物品，每个物品具有重量和价值，一个背包可以承重的上限是W，找出不超过背包承重限制、且总价值最大的将物品装入背包的方案。

数学描述为：

2.几个经典的优化问题（2）旅行商问题

（travelingsalesmanproblem，TSP）

一个旅行商要访问n个城市的每个城市，若任意两个城市间的距离已知，寻找一条经过所有城市且每个城市只能经过一次的最短闭合路径。

100个城市的TSP最优解14（3）车间作业调度问题

（Jobshopschedulingproblem，JSSP）

有m台机器和n个待加工工件,每个工件均需要不重复地经过所有机床加工。工件的加工路线和加工时间已确定。同时假设：

1）每台机器在同一时刻只能加工一个工件；2）不同的工件之间没有顺序约束；3）工件加工过程不能间断；如何安排每台机器上的工件加工顺序，使全部工件的最大完工时间最短。

工件机器/加工时间/工序11/9/O112/6/O2122/10/O221/4/O1232/4/O231/6/O1342/3/O241/2/O14以一个4*2的调度问题为例：(Oij表示第j个工件在第i台机器上加工)1516假设一种调度方案为：O11，O23，O22，O24，O12，O14，O13，O21完工时间为26（4）组播路由问题3.源于生物（动物）行为的启发

（1）

蚂蚁的觅食行为观察发现，蚂蚁可以在没有任何可见提示的情况下，找出从巢穴到食物源的最短路径，并且能随环境的变化而变化。19

preyfoodanobstacleislaidinthepath

choosingpaththeshortestpath蚂蚁是如何在食物源和巢穴之间找到最短路径的？

蚁群优化算法原理

在蚂蚁的体内存有一种化学物质，称为信息素（pheromone），当它们移动时通过释放信息素，以产生一条返回巢穴的路径。

在寻找食物时，蚂蚁先随意地对其巢穴周围的区域进行搜寻，并在走过的路上留下信息素。一旦一只蚂蚁找到了食物源，它会对食物做出评估并将一部分带回巢穴。在返回的途中，蚂蚁会根据食物的数量和质量留下不同量的信息素，信息素的浓度痕迹会引导其他蚂蚁找到食物源。21

蚂蚁行为的机制

蚂蚁个体之间的信息交换是一个正反馈过程，其觅食的协作本质可以概括为：路径概率选择机制：信息素浓度越高的路线，被选中的概率越大。信息素更新机制：路径越短，信息素的浓度增长得越快。协同工作机制：蚂蚁个体之间通过信息素进行信息传递。

由此，创造了蚁群优化算法（AntColonyOptimization，ACO）

（2）鸟群行为23

人们观察鸟群的群体行为发现：当一群鸟在随机搜寻食物时，发现某个区域内有一块食物，鸟会先后飞向食物，以及在食物最近的鸟的周围区域继续搜寻食物。数目庞大的鸟群在飞行中可以有形的改变方向，散开，或者队形的重组。

科学家认为，上述行为是基于鸟类的社会行为中的两个要素：个体经验和社会学习。由此，创造了粒子群优化算法

（ParticleSwarmoptimization，PSO）

(3)鱼群行为25

鱼在一片水域的游动，可以归纳为四种行为：

a.觅食行为

当鱼群发现食物时，会向着食物的方向快速游去；

b.追尾行为

一条鱼向其视野内的另一条游向食物的鱼游去；

c.聚群行为

为了避免被其他动物捕食，游向伙伴多的地方；d.随机游动

无目的的游动。由此，创造了人工鱼群算法

（ArtificialFishSwarmAlgorithm，AFSA）

1.群(Swarm)群在自然界中广泛存在。根据剑桥高级学生词典的释义，Swarm被定义为alargegroupofinsectsallmovingtogether.也即：一大群一起运动的昆虫。然而，群的概念并不仅仅局限于昆虫，例如：鱼群，椋鸟群，也都表现出一定的群集性。

群的每个成员，称为一个个体。每个个体，其运动只遵循简单的规则。并且群成员之间是平等关系，而没有主从关系。由这些平等的、相互间能够协调运动的个体的集合，称之为“群”。第3节群智能算法2.群智能(SwarmIntelligence)通过观察鸟群和鱼群，科学家发现，由这些生物群体所表现出的集体行为以及群成员之间的相互作用是如此的协调，以致于我们从主观的观感上认为群的运动一定是由一个或若干个“与众不同”的群成员所指挥。

然而事实并非如此。

因此，一个问题产生了：Howcouldaswarmperformlikethat？答案只有一个：群智能。

实际上，群成员的集体运动以及它们之间的相互作用是从每个群成员个体所遵循的一些简单行为规则自底向上的一种“突现（emergence）”。个体仅具有简单智能，但群体行为却表现出比较高级的智能。

第3节群智能算法（1）计算机仿真

外国学者Reynolds使用计算机图形动画对复杂的群体行为进行仿真，仿真中采用三个简单规则，成功地模拟了飞行的鸟群。这三个规则是：1.避免碰撞2.飞向目标3.飞向群体的中心第3节群智能算法

(2)行为主义《SwarmIntelligence》一书中阐述了这样的重要观点：Mindissocial.

也就是说：人的智能源于社会性的相互作用，文化和认知是人类社会性不可分割的重要部分，这一观点也成为了群智能发展的基石。

群智能已经成为了有别于传统人工智能中连接主义和符号主义的一种新的关于智能的描述方法，也称为行为主义。

（3）技术方法

群智能的思路，为在没有集中控制且不提供全局模型的前提下寻找复杂的分布式问题求解方案提供了基础。在计算智能领域已经取得成功的两个典型的基于Swarmintelligence的优化算法分别是蚁群算法和粒子群算法。除此之外，鱼群算法、蜂群算法、蛙跳算法、萤火虫算法、细菌觅食算法等基于群智能的优化算法也受到了广泛的关注。

引例：极值、搜索空间、局部最优

*我们为什么不用计算驻点的方式？而要用搜索的方式？3.群智能算法的一般框架(1)产生一个初始种群，种群中的每一个个体表示待求解问题的一个潜在解（可行解）；(2)计算种群中每个个体的适应度；(3)用学习算子产生新一代种群；(4)若满足终止条件，则算法停止；否则转步骤(2)。1995年，Kennedy和Eberhart在模拟鸟群觅食过程中的迁徙和群集行为时提出的一种基于群智能的演化计算技术。通过粒子在搜索空间中追随最优粒子飞行的方式进行搜索。PSO是一种基于种群的随机优化技术。通过粒子间的相互作用发现复杂搜索空间中的最优区域。其优势在于简单容易实现,同时又有着深刻的智能背景。既适合于科学研究，又适合于工程应用，并且参数少，收敛快。粒子群算法应用广泛：系统优化、模式识别、信号处理、机器人技术等。第4节粒子群优化算法(PSO)粒子群优化算法的发展（1）PSO的基本思想优化问题的潜在解都是搜索空间中的一只鸟，称为“粒子”。每个粒子都有一个由待优化函数决定的适应度值fitness。每个粒子还有一个速度决定它一次飞行的方向和距离。粒子协同运动，一起在解空间中搜索。在迭代的搜索过程中，每个粒子通过跟踪两个“极值”来更新自己。第一个极值叫个体极值，就是当前粒子自身经历过的最好位置；另一个极值叫社会极值，指的是当前种群经历过的最好位置。通过两个极值的引导，整个种群逐渐收敛，最终找到最优解。

（2）PSO的基本原理

将每个个体看作是在n维搜索空间中的一个没有重量和体积的微粒，并在搜索空间中以一定的速度飞行。该飞行速度由个体的飞行经验和群体的飞行经验进行动态调整。

假设搜索空间是n维的，粒子群中第i个粒子可以被表示成一个n维向量：

粒子的速度向量为：看做粒子在搜索空间的位置粒子i到达过的最好位置表示为：粒子群中所有粒子到达过的最好位置表示为：

在第k次迭代中，粒子i按照下述公式通过调整其每一维的速度和位置实现粒子的位置变化：其中，下标“i”表示第i个粒子，“j”表示粒子的第j维，C1

和

C2

是加速度常量，r1

和r2

是在(0,1)内均匀分布的随机数.

个体认知社会学习其中，是惯性系数，

（3）算法流程图粒子群算法演示程序算法流程中粒子群算法的初始化过程为：1.设定种群规模（粒子数量）

2.对任意i，j，在[Xmin,Xmax]内服从均匀分布产生Xij

3.对任意i，j，在[Vmin,Vmax]内服从均匀分布产生Vij评价粒子个体：根据优化目标函数设计适应度函数，用来计算每个粒子的适应度值。算法步骤：Step1按照初始化过程，对粒子的位置和速度随机初始化；Step2计算每个粒子的适应度值；Step3

对于每个粒子，将其适应值与所经历过的最好位置Pi的

适应度值进行比较，若较好，则将其作为当前的最好位置；Step4

对每个粒子，将其适应值与全局所经历的最好位置Pg的适

应值度进行比较，若较好，则将其作为当前的全局最好位置；

Step5

根据粒子飞行公式对粒子的速度和位置进行更新；Step6

如果满足结束条件（通常为满足需要的适应度值或达到一个

预先设定的最大迭代代数），则算法结束，输出Pg；否则，返回Step2。第3节基本PSO算法程序伪代码

符号含义：N：种群规模，D：粒子的多维向量的维数，P：粒子飞行所经历的最好位置，G：所有粒子飞行经过的最好位置，Lbest：P所对应的适应度值，Gbest：G所对应的适应度值,t：迭代次数ProcedurePSObegint=0Lbest=Lbest(0)Gbest=Gbest(0)while(i<N)while(d<D)在[Xmin,Xmax]内随机产生Xid在[Vmin,Vmax]内随机产生Vid

endwhile计算粒子Xi的适应度fitnessi，if(fitnessi>Gbest)令G=Xi

更新Lbest,Gbestendwhilewhile(终止条件未满足时)t=t+1while(i<N)while(d<D)计算Vid计算Xidendwhile计算粒子Xi的fitnessiif(fitnessi>Gbest)令G=Xi

if(fitnessi>Lbest)令P=Xi

更新Lbest,Gbestendwhileendwhileendbegin第3节基本PSO算法程序2.程序源代码优化函数第4节改进的PSO算法1.算法分析

为了方便起见，我们将基本粒子群算法的形式表述如下：

（1）

（2）

为了更好地分析基本粒子群算法，我们将(1)式改写为:

(3)

其中

从（3）可以看出，其右边可以分成三部分：第一部分为粒子先前的速度；第二部分为粒子的“认知”部分、第三部分为“社会”部分。表示对原先速度的修正。其中，第二部分考虑该粒子历史最好位置对当前位置的影响，而第三部分考虑粒子群体历史最好位置对当前位置的影响。

如果

此时，粒子将会保持速度不变，沿该方向一直“飞”下去直至到达边界。因而，在这种情形下，粒子很难搜索到较优解。如果

由于粒子的速度将取决于其历史最优位置与群体的历史最优位置，从而导致速度的无记忆性。假设在开始时，粒子j处于整体的最优位置，则按照上式它将停止进化直到群体发现更好的位置。

此时，对于其它粒子而言，。这表明，整个粒子群的搜索区域将会收缩到当前最优位置附近，即如果没有第一项，则整个进化方程具有很强的局部搜索能力。

如果

即，粒子群算法的速度进化方程仅包含认知部分，则其性能变差。主要原因是不同的粒子间缺乏信息交流，即没有社会信息共享，粒子间没有交互，使得一个规模为N的群体等价于运行了N个单个粒子，因而得到最优解的概率非常小。如果

则粒子没有认知能力，也就是“只有社会”的模型。这样，粒子在相互作用下，有能力到达新的搜索空间，虽然它的收敛速度比基本微粒群算法更快，但对于复杂问题，则容易陷入局部最优点。

通过以上的分析，可以看出粒子更新公式中第一项用于保证算法的全局收敛性能；第二项和第三项使得粒子群算法具有局部收敛能力。因此，基本粒子群算法具有快速的全局搜索能力。2.

带有惯性权重的改进粒子群算法

对于不同的问题，如何确定局部搜索能力与全局搜索能力的比例关系，对于其求解过程非常重要。甚至对于同一个问题而言，进化过程中也要求不同的比例。为此，YuhuiShi在1998年提出了带有惯性权重的改进粒子群算法。其粒子更新公式为：

文献[YuhuiShi1998]建议的w取值范围为[0,1.4]，但实验结果表明当取[0.8,1.2]时，算法收敛速度更快，而当时w>1.2，算法则较多地陷入局部极值。较大的w有较好的全局收敛能力，而较小的则有较强的局部收敛能力。因此，随着迭代次数的增加，惯性权重应不断减少，从而使得微粒群算法在初期具有较强的全局收敛能力，而晚期具有较强的局部收敛能力。在[YuhuiShi1999]中，惯性权重满足：

MaxNUMber为最大截止代数，这样，将惯性权重看作迭代次数的函数，可从0.9到0.4线性减少，从对四个测试函数的测试结果来看，效果很好。

第5节PSO的实验设计与参数选择

为分析与检验微粒群算法的性能，目前该领域的研究人员一般采用Benchmark测试函数，下面列举几个典型的测试函数：1无约束优化测试函数（F1-F11）

F1

是著名的Sphere函数，单峰，在xi=0时达到极小值。F2

被称为Rosenbrock函数，非凸，在xi=1时达到极小值

F5是著名的Schaffer函数，由J.D.Schaffer提出，全局极大点是(0,0),在距离全局极大点大约3.14的范围内存在无限多的次全局极大点，函数强烈震荡的性态使其很难全局最优化。

2.约束优化测试函数（F1-F6）测试问题F1其最优解为3.多目标优化测试函数（F1-F5）F12.设计PSO算法的基本原则与步骤

（1）适用性原则一个算法的适用性，是指该算法所能适用的问题种类，这取决于算法所需的限制与假设。如果优化问题的性质不同，则相应的具体处理方式也不同。

（2）可靠性原则一个算法的可靠性，是指算法具有以适当的精度求解大多数问题的能力，即能对大多数问题提供一定精度的解。与其他众多的进化算法一样，PSO同样是一种随机的优化算法，因此在求解不同问题时，其结果具有一定的随机性与不确定性。故设计算法实验时，应尽量经过较多样本的检验，以确定算法的可靠性.

（3）收敛性原则PSO算法的收敛性是指算法能否以概率1收敛到全局最优解,并具有一定的收敛速度和收敛精度。通常评价算法的收敛性能，可通过比较在有限时间代内算法所求解的精度来实现。

（4）稳定性原则算法的稳定性是指算法对其控制参数及问题数据的敏感程度。一个性能稳定的算法，应该具有以下两种特性：一是对一组固定的控制参数，算法能用于较广泛问题的求解；二是对给定的问题数据，算法的求解结果应不会随控制参数的微小扰动而波动。

（5）生物类比原则.粒子群算法的设计思想源于对生物群社会行为的模拟，因此生物界中相关的进化理论、策略、方法，均可通过类比的原则，引入到算法中以求提高算法性能。PSO算法的设计步骤：

1．确定问题的表示方案(粒子编码方案)

PSO算法在求解问题时，首先应先将问题的解从解空间映射到具有某种结构的表示空间，即用特定的码串表示问题的解。根据问题的特征选择适当的编码方法，将会对算法的性能及求解结果产生直接的影响。

PSO算法的早期研究均集中在数值优化领域中，其标准计算模型适用于具有连续特征的问题函数，因此目前算法大多采用实数向量的编码方案。用PSO算法求解具有离散特征的问题对象，是此领域内的一个研究重点。

2．确定优化问题的评价函数在求解过程中，借助于适应值来评价解的质量。因此在求解问题时，必须根据问题的具体特征，选取适当的目标函数或费用函数来计算适应度。适应度是唯一能够反映并引导优化过程不断进行的参量。3．选取控制参数PSO算法的控制参数，通常包括粒子群的规模（粒子的数量）、算法执行的最大代数，惯性系数、认知参数、社会参数及其他一些辅助控制参数等等。针对不同的算法模型，选取适当的控制参数，直接影响算法的优化性能。

4．设计粒子的飞行方式。在粒子群算法中，最关键的操作是如何确定粒子的飞行速度。由于粒子是由多维向量来描述的，故相应的粒子飞行速度也表示为一个多维向量。在飞行过程中，粒子借助于自身的记忆（Lbest）与社会共享信息（Gbest），沿着每一分量方向动态地调整自己的飞行速度与方向。

5．确定算法的终止准则与其它进化算法一样，PSO算法中最常用的终止准则是预先设定一个最大的迭代代数，或者是当搜索过程中解的适应度在连续多少代后不再发生明显改进时，终止算法。6．编程上机运行。根据所设计的算法结构编程，并进行具体优化问题的求解。通过所获得问题的解的质量，可以验证算法的有效性，准确与可靠性。第6节PSO的研究热点1.算法设计

基本粒子群算法是针对连续函数的优化问题提出的，其核心是粒子更新公式，那么对于离散的函数优化问题、组合优化问题，如何设计粒子编码，如何依据PSO的思想设计粒子的飞行方式。第6节PSO的研究热点2.粒子群拓扑结构

粒子群优化算法的重要特点是其社会性学习，即粒子间的相互作用。那么，以什么样的形式把粒子组织起来，使粒子间能够更有效地共享信息。目前已提出的有环形粒子群结构、多子群结构。3.参数选择与优化

粒子更新公式中的C1和C2的取值、惯性系数等。4.与其他演化计算方法的融合

由NFL定理，PSO在解决某个或某类问题时可能会存在缺陷，可考虑与其它演化计算方法相结合，取长补短，提高PSO的寻优性能。

5.应用

应用PSO解决目前其它方法尚未解决好的老问题、