粒子群优化算法理论及应用

粒子群优化算法理论及应用主讲人：李林宜学院：遥感信息工程学院PSO算法起源“师法自然”，人们从自然现象与规律中得到启发，提出了许多新方法用于解决实际应用中遇到的难题，典型的方法有：受生物进化机理启发提出的遗传算法、进化规划和进化策略；受大脑机理启发提出的人工神经网络；受生物免疫系统机理启发提出的人工免疫系统；受固体退火原理启发提出的模拟退火算法；受群居生物群体(如蚁群、鸟群等)自组织行为启发提出的群体智能算法，如蚁群算法和粒子群优化算法（ParticleSwarmOptimization，简称PSO）。PSO算法起源PSO的理论基础

人工生命（ArtificialLife）进化计算（EvolutionaryComputation）PSO算法起源人工生命

人工生命的概念是由Langton教授于1987年提出来的，他把人工生命定义为“研究具有自然生命系统行为特性的人造系统”。

典型的人工生命研究有细胞自动机、数字生命、进化机器人和人工生命计算等。人工生命采用自下而上的原则，从问题的底层开始，通过定义底层规则来研究整体的行为。PSO算法起源人工生命的特征

人工生命由单个个体构成，每个个体只具有简单过程行为；个体的每个过程包含与其它个体的交叉，反映了对局部状态的影响；人工生命具有学习行为，即具有自学习及其传播行为；人工生命系统不存在全局控制过程，具有“突现”结构和性质；系统能够超越各过程范围产生高级行为，如自适应、新陈代谢等。PSO算法起源进化计算

生物进化过程是从简单到复杂、从低级到高级的过程，生物进化遵循“适者生存、优胜劣汰”的自然规律，通过遗传变异来实现，这个过程是自然的、稳健的优化过程。进化计算是模拟自然界生物进化过程与机理求解优化问题的人工智能技术，其形式是迭代算法，从选定的初始群体（一组初始解）出发，对群体中的每个个体进行评价，并利用进化产生机制产生后代个体，通过不断迭代，直至搜索到优化问题的最优解或者满意解。算法流程图

PSO算法起源进化计算内容进化计算包括进化策略、进化规划和遗传算法等。进化策略最初是由德国数学家Rechenberg和Schwefel为处理流体动力学问题而提出的优化算法，在此算法中，群体中的个体含有随机扰动因素，以变异操作为主，以交叉操作为辅，选择群体中的较好个体生存下来。

PSO算法起源进化计算内容

进化规划最初是由美国学者Fogel等为求解预测问题而提出的有限机进化模型，后来扩展到用于求解实值问题，在此算法中，采用变异操作,而不采用交叉操作，父辈群体通过变异产生子代群体,选择父辈和子代群体中的较好个体生存下来。遗传算法是由美国Michigan大学的Holland教授等在研究人工自适应系统中发展的随机优化算法，此算法强调交叉操作，交叉操作是产生新个体的主要方法，并采用随机变异操作，根据个体适应度进行概率选择操作。

PSO算法起源进化计算的特征算法的操作对象是由多个个体组成的集合，适应度是算法对个体优劣程度的度量；算法进行选择操作，以便当前群体中具有较高适应度的个体能够更多地保留到下一代群体中；算法通过个体重组、变异等进化操作来增进群体的多样性；算法所模拟的生物进化过程是反复迭代过程，在迭代进化过程中，个体适应度和群体中所有个体的平均适应度不断得到改进，最终可以得到具有较高适应度的个体，对应于问题的最优解或近似最优解；算法所模拟的进化过程受随机因素影响，不易陷入问题的局部最优解，能以较大的概率找到全局最优解；算法具有并行结构，适合于进行大规模复杂问题求解。PSO算法起源在自然界中，鸟群中的个体是离散的，但其整体运动形态流畅且富有美感，个体与个体之间保持着适宜的距离，群体中存在着个体与个体、个体与群体的相互作用与影响，体现的是一种存在于群体中的信息共享机制。Kennedy博士对鸟群协作模式用社会学观点进行了诠释，并引用了社会生物学家Wilson关于生物群体的一段话，“至少从理论上说，生物群体中的单个成员可从该群体中其它成员觅食经验和发现中获得好处，当事先不确定食物位于什么地方时，这种协作带来的优势可能是决定性的，超过成员之间食物竞争所带来的劣势”，这段话表明了生物群体成员间信息分享的重要性。PSO算法起源模拟鸟类飞行的Boid模型

群体行为可以用几条简单行为规则在计算机中建模，Reynolds使用以下规则作为行为规则：向背离最近同伴的方向移动；向目的移动；向群体的中心移动。PSO算法起源假设在一个区域里只有一块食物，一群鸟进行随机搜索，所有鸟都不知道食物具体在哪里，但知道它们当前位置离食物还有多远，那么一种简单有效的觅食策略是搜索目前离食物最近的鸟的周围区域。寻找特定问题的最优解与上述鸟类觅食过程有一定的类似，Kennedy博士和Eberhart博士从鸟群觅食过程和Boid模型中得到启发，于1995年提出了PSO算法，用于解决优化问题。PSO的研究与应用现状概述目前PSO已被如下国际会议列为讨论专题之一国际进化计算会议（IEEECongressonEvolutionaryComputation,简称CEC）国际群智能研讨会（IEEESwarmIntelligenceSymposium，简称SIS）智能计算和应用国际研讨会（InternationalSymposiumonIntelligenceComputationandApplications，简称ISICA）PSO的研究与应用现状概述许多有关PSO的文章已陆续发表在国际国内一些高水平期刊上国际期刊如《IEEETransactionsonEvolutionaryComputation》、《IEEETransactionsonGeoscienceandRemoteSensing》、《IEEETransactionsonPowerSystems》等国内期刊如《计算机学报》、《电子学报》、《物理学报》、《分析化学》等

PSO的研究与应用现状概述

截至2010年3月在《科学引文索引扩展版SCIExpanded》的“ScienceCitationIndexExpanded(SCI-EXPANDED)--1999-present”

数据库中以“GeneralSearch，TOPIC，Titleonly”为检索方式，以“ParticleSwarmOptimization”为检索词，进行检索，可以检索到1075篇相关文章；在《工程索引网络版EngineeringVillage》的“Compendex”

数据库中以“QuickSearch，Title”为检索方式，以“ParticleSwarmOptimization”为检索词，进行检索，可以检索到4241篇相关文章。PSO的研究现状目前，PSO尚未形成完整的理论体系，其算法研究主要集中在以下两大方面：算法的性能分析算法的性能改进PSO的研究现状算法的性能分析

一些研究者通过仿真实验，给出了PSO在典型优化问题中实现全局收敛的实验结果。

Solis和Wets提出了随机优化算法以概率1收敛于全局最优解需要满足的条件，Bergh利用该条件对PSO的收敛性进行了研究，证明了一种GCPSO的局部收敛性。

El-Gallad等利用统计实验方法研究了种群规模、迭代次数等参数对PSO算法性能的影响，并给出了相应的参数选择原则。曾建潮等利用Solis和Wets的研究结果对一种随机PSO的全局收敛性进行了理论分析，证明了其能够保证以概率1收敛于全局最优解。

PSO的研究现状算法的性能改进

PSO最初多用于解决连续优化问题，Kennedy等提出了一种离散二进制PSO，用于解决组合优化问题。

Shi等首次提出了惯性权重的概念，对基本PSO的速度更新公式进行了相应修正，并提出了采用随时间递减的动态惯性权重以提高算法性能。Clerc在进化方程中引入收缩因子以提高算法性能。Ratnaweera等提出了时变加速系数的PSO。PSO的研究现状算法的性能改进

一些研究者通过控制群体多样性来提高算法性能。

Lovbjerg等将自组织临界控制（Self-OrganizedCriticality,简称SOC）引入PSO，SOC粒子增加了当前临界值属性，如果两个粒子间的距离小于预定的距离阈值则增加彼此的临界值；如果某个粒子的临界值超过系统全局的极限值时，则重新分配其在搜索空间中的位置，如此可使算法有更快的收敛速度和得到更好的解。

Krink等提出了一种粒子空间扩展的方法以解决粒子间的冲突和聚集问题，并增强了粒子逃脱局部最优值的能力。PSO的研究现状算法的性能改进

一些研究者将其它计算智能算法的思想引入PSO以提高算法性能。

Angeline将进化规划中的竞赛选择方法引入PSO。

Lovbjerg等将遗传算法中的交叉算子引入PSO。

Natsuki等将遗传算法中的变异算子引入PSO。高鹰等把模拟退火思想引入到具有交叉和高斯变异的PSO中，还把免疫系统的免疫信息处理机制引入PSO。PSO的应用现状经典优化问题的求解

PSO最直接的应用是求解函数优化问题。

PSO还能用于求解多目标优化问题。这类问题中各个目标之间是相互冲突的，不存在单个解使得所有目标同时最优，其最优解是一个解集，求解这类问题比求解单目标优化问题要困难得多。

PSO在求解组合优化问题中也得到了应用。旅行商问题是组合优化中的NP难题。PSO的应用现状电力系统中的应用

机组优化组合是电力系统中的典型优化问题，在机组间恰当地分配负荷可带来巨大的经济效益。电力系统无功优化是电力系统规划领域的重要研究内容，是一个多变量、多约束的混合非线性规划问题，无功优化的优劣对电力系统安全经济运行具有重要意义。配电系统状态估计在能量管理系统中具有重要作用。PSO的应用现状交通运输领域中的应用

城市交通是一个随机的、复杂的巨型系统，交通控制有利于缓解交通拥挤，有着重要意义。文献在PSO中引入灾变策略和模型，将其应用于城市区域交通协调控制信号配时优化。车辆路径问题是指对一系列发货点（或收货点），调用一定的车辆，组成适当的行车路径，使车辆有序地通过，在满足一定约束条件的情况下，达到一定的目标（诸如路程最短、费用最小、耗费时间尽量少等）。文献将PSO应用于带时间窗车辆路径优化问题。PSO的应用现状计算机领域中的应用

聚类分析是用数学方法研究和处理给定事物的分类,按照事物间的相似性对给定事物进行区分。文献将PSO用于数据聚类，提出了基于PSO的模糊C-均值聚类算法。文献将PSO用于数据分类，给出了适用于PSO的分类规则编码，构造了新的分类规则适应度函数来提取规则集，通过修改粒子位置更新方程使PSO适于解决分类规则挖掘问题。文献提出了一种快速k近邻分类文本分类算法，该算法利用PSO的随机搜索能力在训练文档集中进行有指导的全局随机搜索。

PSO在影像处理与分析中的应用现状影像配准

文献提出了一种基于PSO的多模态医学图像刚性配准方法，用PSO求解空间变换参数，具有操作方便、可靠性好、不易陷入局部极值等优点。文献提出了一种基于量子PSO的遥感影像配准框架，在粗配准过程中，量子PSO被用来搜索最优刚性参数，搜索过程不易陷入局部极值。

PSO在影像处理与分析中的应用现状影像分割文献提出了一种基于PSO的最大交叉熵影像分割方法，PSO方法不仅实现了正确分割，而且提高了分割的速度；文献提出了一种基于PSO和二维Otsu的影像分割方法，此方法不仅能得到理想的分割结果，而且大大减少了计算量，实现了快速分割，便于二维Otsu分割方法的实时应用；文献将PSO应用于红外影像分割。PSO在影像处理与分析中的应用现状图像压缩、影像去噪、影像插值、SAR影像非监督分类、影像模拟以及影像相似性评价等

标准PSO的算法原理PSO将优化问题的可行解空间作为其搜索空间，在搜索空间中随机生成初始群体，个体是没有体积没有质量的粒子，每个粒子的空间位置是优化问题的一个可行解，粒子的适应度是对其空间位置优劣的度量，粒子在搜索空间中以一定的速度飞行，根据自身飞行经验和同伴飞行经验来动态调整其飞行速度及空间位置，以搜索最优空间位置，即优化问题的最优解。标准PSO的算法原理

设群体规模为，搜索空间为维，群体中第

个粒子的空间位置为

，它的速度为

，它经历过的最佳空间位置为

，当前群体的所有粒子经历过的最佳空间位置为

，

是所有

中的最佳者，对于每一次迭代，分别按下式计算粒子在搜索空间的运动速度和空间位置：

（2-1）

（2-2）

（2-3）

离散二进制PSOPSO最初多用于解决连续优化问题，Kennedy等提出了一种离散二进制PSO，用于解决组合优化问题，在该算法中，粒子的空间位置被表示为由0或1组成的向量，对于每一次迭代，分别按下式计算粒子在搜索空间的运动速度和空间位置：

（2-7）

（2-6）

式中：

算法流程图

PSO的特点算法只需目标函数的输出值，而无需其相关梯度信息；算法需要调整的参数很少；算法仅涉及各种基本数学操作，易于实现；算法无集中控制约束，不因个别个体故障而影响整个问题的求解，具有很强的鲁棒性；算法可以进行并行分布式处理，可以充分利用多处理器，在搜索空间上进行并行操作，每个个体的搜索过程可以并行进行。PSO的设计原则适用性原则指算法所能适用的问题种类，这取决于具体问题所需的限制和假设。

可靠性原则指算法能对优化问题提供可靠解。PSO是随机优化算法，其结果往往带有一定的随机性和不确定性，应尽量通过反复检验以确认算法的可靠性。

收敛性原则指算法能否收敛到全局最优解，并且具有一定的收敛速度。稳定性原则指算法对其控制参数和优化问题数据的敏感程度。PSO设计中的关键问题将待解决问题转换为优化问题进行处理

明确需要确定的参数或者组合，确定其最优评价标准，将问题转换为优化问题进行处理。根据优化问题的类型，采用相应的PSO算法模型。确定粒子编码及初始化方式

粒子编码方式会对算法性能产生影响，根据选定的PSO算法模型，采用相应的编码方式。确定粒子适应度函数

适应度函数是对粒子空间位置优劣的度量，引导着优化过程的进行。通常，适应度函数的确定依赖于需要解决的具体优化问题。

PSO在遥感领域中的应用研究各种飞机和卫星系统提供了以TB级计的海量航空和卫星遥感影像数据，但其中大量数据得不到充分利用，实现影像处理与分析的自动化和智能化是摄影测量与遥感学科亟待解决的瓶颈问题。PSO是基于群体智能的新型进化计算技术，具有自适应、自组织等智能特性，具有强大的寻找最优解的能力，将PSO应用于航空和卫星遥感影像的处理与分析，探索出PSO用于解决影像分割、影像分类等关键问题的有效途径，为实现影像处理与分析的自动化和智能化打下一定的基础。基于PSO的影像自适应增强方法存在的难点

增强参数选取基于PSO的影像自适应增强方法非完全Beta函数增强算法原理

Tubbs提出了一种能完全覆盖典型灰度变换函数的非完全Beta函数，具有理想的影像增强效果，归一化的非完全Beta函数F(u)定义如下：

（3-2）

（3-1）

式中：

为Beta函数，0<α<10，0<β<10。α和β的取值控制着F(u)的形状，通过对α和β进行不同取值，可以得到各类灰度变换曲线。

基于PSO的影像自适应增强方法非完全Beta函数增强算法流程基于PSO的影像自适应增强方法方法可行性分析首先确定最优增强参数评价标准和增强参数的可行取值范围，将参数选取问题转换为优化问题进行处理；然后确定粒子具体表达方法，每个粒子的空间位置是一个可行的参数向量；最后确定群体寻优策略，通过利用信息共享机制，粒子不断调整自身的飞行速度和空间位置，以搜索最优空间位置，即最优参数向量。基于PSO的影像自适应增强方法算法设计中的关键问题

（1）将问题转换为优化问题进行处理本文提出α和β最优取值评价标准，如下：设为在这组参数取值情况下增强影像的质量评价指标值，，，若对于在和可行域中的每一组，有成立，则为最优参数取值。

其中：；和分别为影像的信息熵和平均梯度。

基于PSO的影像自适应增强方法（2）确定粒子编码及初始化方式（3-13）

（3-12）

式中：表示群体中第个粒子位置向量的第维分量，对应于，由于，，在此参数取值精度精确到，因此，，，。

基于PSO的影像自适应增强方法（3）确定粒子适应度函数（3-14）

式中：为第个粒子的适应度函数值；为在这组参数取值情况下增强影像的质量评价指标值。

算法流程图

基于PSO的影像自适应增强方法实验结果与分析基于PSO的影像自适应增强方法

增强前后影像质量定量评价，如表3-2所示，其中，E(Y)是信息熵和平均梯度的综合评价指标，D(Y)是样本标准差。

基于PSO的影像自适应增强方法

由于本文方法的增强效果取决于增强参数的取值，因此有必要将用本文方法得到的取值与用穷尽法得到的取值进行比较。

基于PSO的影像自适应增强方法基于PSO的影像自适应增强方法基于PSO的影像自适应增强方法基于PSO的影像自适应增强方法实验结论

实验结果表明，本文方法具有较好的影像增强效果，将PSO用于增强参数的自适应选取，不仅能得到与穷尽法相同的最优参数组，而且具有较高的搜索效率和可靠性。

基于PSO的影像模糊阈值分割方法存在的难点

模糊阈值选取基于PSO的影像模糊阈值分割方法影像模糊阈值分割原理根据模糊集理论，影像可以表示为模糊隶属度矩阵：式中：，为像素的隶属度。（4-2）

基于PSO的影像模糊阈值分割方法

在模糊阈值分割算法中，采用较多的隶属度函数是模糊集合理论中的标准S函数，定义如下:（4-4）

（4-3）

式中：，是模糊参数，称为渡越点。是模糊区域，模糊区域的宽度为。与是非模糊区域。

基于PSO的影像模糊阈值分割方法

模糊熵是模糊集不确定性的一种度量，定义如下：式中：是香农函数，定义如下：

（4-6）

（4-5）

根据信息论，模糊集的模糊熵越大，则模糊集包含的信息越多。因此，当模糊集的模糊熵最大时，模糊集包含的信息最多，相应的模糊参数组是最优参数组，由最优参数组通过（4-4）式计算出的渡越点是最优模糊阈值。影像按如下公式被分割为目标和背景：（4-7）

基于PSO的影像模糊阈值分割方法方法可行性分析首先确定最优模糊参数组评价标准和模糊参数组的可行取值范围，将参数组选取问题转换为优化问题进行处理；接着确定粒子具体表达方法，每个粒子的空间位置是一个可行的参数向量；然后确定群体寻优策略，通过利用信息共享机制，粒子不断调整自身的飞行速度和空间位置，以搜索最优空间位置，即最优参数向量，在此基础上，由最优参数组计算得到最优模糊阈值。基于PSO的影像模糊阈值分割方法算法设计中的关键问题

（1）将问题转换为优化问题进行处理本文提出最优参数组评价标准，如下：设为在参数组取值为的情况下影像对应模糊集的模糊熵，，，若对于在和可行域中的每一组，有成立，则为参数组最优取值。

基于PSO的影像模糊阈值分割方法（2）确定粒子编码及初始化方式（4-9）

（4-8）

式中：表示群体中第个粒子位置向量的第维分量，对应于，，。

基于PSO的影像模糊阈值分割方法（3）确定粒子适应度函数（4-10）

式中：为第个粒子的适应度函数值；为在参数组取值为的情况下影像对应模糊集的模糊熵。

算法流程图

基于PSO的影像模糊阈值分割方法实验结果与分析基于PSO的影像模糊阈值分割方法基于PSO的影像模糊阈值分割方法

由于本文方法的分割效果取决于模糊参数组和模糊阈值的取值，因此，有必要将用本文方法得到的模糊参数组和模糊阈值的取值与用穷尽法得到的取值进行比较。基于PSO的影像模糊阈值分割方法基于PSO的影像模糊阈值分割方法基于PSO的影像模糊阈值分割方法基于PSO的影像模糊阈值分割方法实验结论

实验结果表明，本文方法具有较好的影像分割效果，将PSO用于模糊阈值自适应选取，不仅能得到与穷尽法相同的最优模糊阈值，而且具有较高的搜索效率和可靠性。基于PSO的影像模糊纹理分类方法存在的难点

（1）模糊特征选择

（2）模糊类别中心选取基于PSO的影像模糊纹理分类方法模糊分类原理

模糊分类方法首先计算待识别模糊模式与已知模糊集的贴近度，再根据择近原则来判断待识别模糊模式的类别。几种常用的贴近度表达式，如下：海明贴近度

欧氏贴近度

明氏贴近度

模糊贴近度

（5-22）

（5-21）

（5-24）

（5-23）

基于PSO的影像模糊纹理分类方法模糊分类算法流程

基于PSO的影像模糊纹理分类方法模糊特征选择方法可行性分析首先确定最优特征组合评价标准和特征组合的可行取值范围，将特征选择问题转换为组合优化问题进行处理；接着确定粒子具体表达方法，每个粒子的空间位置是一个可行的特征组合；最后确定群体寻优策略，通过利用信息共享机制，粒子不断调整自身的飞行速度和空间位置，以搜索最优空间位置，即最优特征组合。基于PSO的影像模糊纹理分类方法算法设计中的关键问题

（1）将问题转换为优化问题进行处理本文提出最优特征组合评价标准，如下：设为在这一特征组合情况下进行分类得到的综合评价指标值，为1或者0，，为特征总数，表示第个特征被选择，表示第个特征未被选择，若对于在特征组合可行域中的每一有成立，则为最优特征组合。

式中：为综合评价指标，,和分别为总体精度和Kappa系数。

基于PSO的影像模糊纹理分类方法（2）确定粒子编码及初始化方式（5-35）

（5-34）

式中：为0或者1的随机数，表示群体中第个粒