第3章粒子群算法及其MATLAB实现
粒子群算法，也称粒子群优化算法(particleswarmoptimization,PSO)，是近年来发展起来的一种新的进化算法(evolutionaryalgorithm,EA)。
这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。粒子群算法是一种并行算法。
本章主要讲解了粒子群算法的原理及其在MATLAB上的运用。
学习目标：
■了解粒子群算法的发展。
■掌握粒子群算法的基本原理。
■熟悉MATLAB粒子群算法工具箱。
■掌握MATLAB在粒子群算法中的运用。
3.1粒子群算法基础
PSO算法属于进化算法的一种，和模拟退火算法相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的“交叉”和“变异”操作，它通过追随当前搜索到的最优值来寻找全局最优。
3.1.1粒子群算法的发展
1995年美国电气工程师Eberhart和社会心理学家Kenndy基于鸟群觅食行为提出了粒子群优化算法(PSO)，简称粒子群算法。由于该算法概念简明、实现方便、收敛速度快、参数设置少，是一种高效的搜索算法。
PSO是模拟鸟群随机搜寻食物的捕食行为。假设在搜索食物区域里只有一块食物，所有的小鸟都不知道食物在什么地方，所以Kenndy等认为鸟之间存在着互相交换信息，通过估计自身的适应度值，它们知道当前的位置离食物还有多远，所以搜索目前离食物最近的鸟的周围区域是找到食物的最简单有效的办法，通过鸟之间的集体协作使群体达到最优。
PSO就是从这种模型中得到启示并用于解决优化问题。在PSO中每个优化问题的潜在解都可以想象成搜索空间中的一只鸟，称之为“粒子”。粒子主要追随当前的最优粒子在解空间中搜索，PSO初始化为一群随机粒子(随机解)，然后通过迭代找到最优解。
在每一次迭代中，粒子通过跟踪两个“极值”来更新自己，第一个就是粒子本身所找到的最优解，这个解称为个体极值pbest，另一个极值是整个种群目前找到的最优解，这个极值是全局极值gbest。
这两个最优变量使得鸟在某种程度上朝着这些方向靠近，此外也可以不用整个种群而只用其中一部分作为粒子的邻居，那么所有邻居的极值就是局部极值，粒子始终跟随这两个极值变更自己的位置和速度，直到找到最优解。
到目前为止，粒子群算法的发展得到越来越多的众多领域学者的关注和研究，成为解决许多问题的热点算法的研究重点。
其中对PSO算法的改进也非常多，有增强算法自适应性的改进、增强收敛性的改进、增加多种群多样性的改进、增强局部搜索的改进、与全局优化算法相结合、与确定性的局部优化算法相融合等。
以上所述的是对于算法改进的目的的讨论，实际改进中应用的方法有基于参数的改进，即对PSO算法的迭代公式的形式上做改进；还有从粒子的行为模式进行改进，即粒子之间的信息交流方式，如拓扑结构的改进、全局模式与局部模式相结合的改进等；还有基于算法融合的粒子群算法的改进，算法融合可以引入其他算法的优点来弥补PSO算法的缺点，设计出更适合问题求解的优化算法。
目前，粒子群算法的发展趋势如下。
(1)粒子群优化算法的改进。粒子群优化算法在解决空间函数的优化问题和单目标优化问题上应用得比较多，如何应用于离散空间优化问题和多目标优化问题将是粒子群优化算法的主要研究方向。如何充分结合其他进化类算法，发挥优势，改进粒子群优化算法的不足也是值得研究的。
(2)粒子群优化算法的理论分析。粒子群优化算法提出的时间不长，数学分析很不成熟和系统，存在许多不完善和未涉及的问题，对算法运行行为、收敛性、计算复杂性的分析比较少。如何知道参数的选择和设计，如何设计适应值函数，如何提高算法在解空间搜索的效率算法收敛以及对算法模型本身的研究都需要在理论上进行更深入的研究。这些都是粒子群优化算法的研究方向之一。
(3)粒子群算法的生物学基础。如何根据群体进行行为完善算法，将群体智能引入算法中，借鉴生物群体进化规则和进化的智能性也是学者关注的问题。
(4)粒子群优化算法与其他进化类算法的比较研究。与其他进化算法的融合，如何将其他进化算法的优点和粒子群优化算法相结合，构造出有特色有实用价值的混合算法是当前算法改进的一个重要方向。
(5)粒子群优化算法的应用。算法的有效性必须在应用中才能体现，广泛地开拓粒子群优化算法的应用领域，也对深入研究粒子群优化算法非常有意义。
3.1.2粒子群算法研究内容
粒子群算法是一个非常简单的算法，且能够有效地优化各种函数。从某种程度上说，此算法介于遗传算法和进化规划之间。
此算法非常依赖于随机的过程，这也是和进化规划的相识之处，算法中朝全局最优和局部最优靠近的调整非常类似于遗传算法中的交叉算子。
粒子群算法的主要研究内容如下。
(1)寻找全局最优点。
(2)有较高的收敛速度。
算法还是用了适应值的概念，这是所有进化计算方法所共有的特征。
3.1.3粒子群算法的特点
粒子群算法的本质是一种随机搜索算法，它是一种新兴的智能优化技术，是群体智能中一个新的分支，它也是对简单社会系统的模拟。
该算法能以较大的概率收敛于全局最优解。实践证明，它适合在动态、多目标优化环境中寻优，与传统的优化算法相比较具有更快的计算速度和更好的全局搜索能力。
其具体特点如下：
(1)粒子群优化算法是基于群体智能理论的优化算法，通过群体中粒子间的合作与竞争产生的群体智能指导优化搜索。与进化算法比较，PSO是一种更为高效的并行搜索算法。
(2)PSO与GA有很多共同之处，两者都是随机初始化种群，使用适应值来评价个体的优劣程度和进行一定的随机搜索。但PSO是根据自己的速度来决定搜索，没有GA的明显交叉和变异。与进化算法比较，PSO保留了基于种群的全局搜索策略，但是其采用的速度位移模型操作简单，避免了复杂的遗传操作。
(3)由于每个粒子在算法结束时仍然保持着其个体极值。因此，若将PSO用于调度和决策问题时可以给出多种有意义的选择方案。而基本遗传算法在结束时，只能得到最后一代个体的信息，前面迭代的信息没有保留。
(4)PSO特有的记忆使其可以动态地跟踪当前的搜索情况并调整其搜索策略。
(5)PSO有良好的机制来有效地平衡搜索过程的多样性和方向性。
(6)在收敛的情况下，由于所有的粒子都向最优解的方向飞去，所以粒子趋向同一化(失去了多样性)使得后期收敛速度明显变慢，以致算法收敛到一定精度时无法继续优化。因此很多学者都致力于提高PSO算法的性能。
(7)PSO算法对种群大小不十分敏感，即种群数目下降时性能下降不是很大。
3.1.4粒子群算法的应用
粒子群算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的适应性，所以广泛应用于很多学科。粒子群算法的一些主要应用领域如下。
(1)约束优化。随着问题的增多，约束优化问题的搜索空间也急剧变换，有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。粒子群算法是解决这类问题的最佳工具之一。实践证明，粒子群算法对于约束优化中的规划，离散空间组合问题的求解非常有效。
(2)函数优化。是粒子群算法的经典应用领域，也是对粒子群算法进行性能评价的常用算例。
(3)机器人智能控制。机器人是一类复杂的难以精确建模的人工系统，而粒子群算法可用于此类机器人群搜索，如机器人的控制与协调，移动机器人路径规划。所以机器人智能控制理所当然地成为粒子群算法的一个重要应用领域。
(4)电力系统领域。在其领域中有种类多样的问题，根据目标函数特性和约束类型许多与优化相关的问题需要求解。PSO在电力系统方面的应用如配电网扩展规划、检修计划、机组组合等。随着粒子群优化理论研究的深入，它还将在电力市场竞价交易等其他领域发挥巨大的应用潜在力。
(5)工程设计问题。在许多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解，也会因简化得太多而使得求解结果与实际相差甚远。现在粒子群算法已成为解决复杂调度问题的有效工具，在电路及滤波器设计、神经网络训练、控制器设计与优化、任务分配等方面粒子群算法都得到了有效的应用。
(6)生物医学领域。许多菌体的生长模型即为非线性模型提出了用粒子群算法解决非线性模型的参数估计问题。还在分子力场的参数设定和蛋白质图形的发现。根据粒子群算法提出的自适应多峰生物测定融合算法，提高了解决问题的准确性。在医学方面，如医学成像上得到的推广应用等。
(7)通信领域。包括路由选择及移动通信基站布置优化，在顺序码分多址连接方式(DSCDMA)通信系统中使用粒子群算法，可获得可移植的有力算法并提供并行处理能力。比传统先前的算法有了显著的优越性，还可以应用到天线阵列控制和偏振模色散补偿等方面。
(8)交通运输领域。在物流配送供应领域中要求以最少的车辆数、最小的车辆总行程来完成货物的派送任务；在交通控制控制领域，城市交通问题是困扰城市发展、制约城市经济建设的重要因素。
3.2基本粒子群算法
PSO算法是起源对简单社会系统的模拟，具有很好的生物社会背景而易理解、参数少而易实现，对非线性、多峰问题均具有较强的全局搜索能力，在科学研究与工程实践中得到了广泛关注。同时，PSO是一种很好的优化工具。
3.2.1基本原理
PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的潜在解都是搜索空间中的一只鸟，称之为粒子。所有的粒子都有一个由被优化的函数决定的适值(fitnessvalue)，每个粒子还有一个速度决定它们“飞行”的方向和距离。然后粒子就追随当前的最优粒子在解空间中搜索。
粒子位置的更新方式如图31所示。
图31每代粒子位置的更新方式
……
