粒子群算法应用

A. 粒子群算法及应用的目录

前言
第1章绪论
1.1最优化问题
1.1.1函数优化问题与组合优化问题
1.1.2优化算法的发展
1.2几种常见的启发式算法
1.2.1遗传算法
1.2.2模拟退火算法
1.2.3人工神经网络
1.3群体智能算法
1.3.1蚁群算法
1.3.2粒子群算法
1.4粒子群算法的发展与应用
1.4.1粒子群算法的发展
1.4.2粒子群算法的应用
参考文献
第2章基本粒子群算法
2.1引言
2.2基本粒子群算法
2.3带惯性权重的粒子群算法
2.3.1一般的惯性因子设计
2.3.2基于模糊系统的惯性因子的动态调整
2.4带收缩因子的粒子群算法
2.5与其他算法的异同
2.5.1基于梯度的优化算法
2.5.2进化计算方法
2.5.3蚁群算法
2.6复杂度
2.6.1复杂度的判定标准和基本概念
2.6.2时空复杂度分析
参考文献
第3章粒子群算法的分析
3.1一维空间轨迹
3.1.1粒子群系统的简化
3.1.2单个粒子的轨迹
3.2多维空间轨迹
3.2.1区域特性
3.2.2步长分析
3.3代数分析
3.3.1系统简化
3.3.2代数观点
3.4解析分析
3.5差分方程分析
3.5.1粒子运动轨迹的稳定性分析
3.5.2粒子运动轨迹的影响因素
3.5.3粒子运动轨迹与算法收敛的关系
参考文献
第4章改进的粒子群算法及分析
4.1离散粒子群优化算法
4.1.1二进制离散粒子群优化算法
4.1.2改进的二值离散粒子群优化算法
4.1.3离散量子粒子群优化算法
4.1.4模糊离散粒子群优化算法
4.2小生境粒子群优化算法
4.2.1小生境粒子群算法
4.2.2基于聚类的小生境粒子群算法
4.2.3种群小生境粒子群算法
4.3混合粒子群优化算法
4.3.1基于遗传思想改进粒子群算法
4.3.2混沌粒子群优化算法
4.3.3基于模拟退火的粒子群优化算法
4.4其他粒子群改进算法
4.4.1子矢量
4.4.2子矢量的更新过程
4.4.3参数分析
参考文献
第5章在函数优化中的应用
5.1基准测试函数
5.2优化测试函数的分类
5.2.1无约束优化测试函数
5.2.2有约束优化测试函数
5.2.3极大极小优化测试函数
5.2.4多目标优化测试函数
5.3智能单粒子算法优化性能
参考文献
第6章在图像压缩中的应用
6.1矢量量化
6.2常用的几种矢量量化方法
6.2.1K-means算法
6.2.2模糊K-means算法
6.2.3模糊矢量量化算法
6.2.4FRLVQ算法
6.2.5FRLVQ-FVQ算法
6.3粒子对算法
6.3.1粒子结构
6.3.2与传统粒子群算法的差异
6.3.3码书更新过程
6.4算法比较
参考文献
第7章在基因聚类中的应用
7.1基因芯片技术简介
7.2基因表达数据聚类分析
7.2.1基因表达数据分析
7.2.2聚类分析
7.3基因表达数据聚类分析
7.3.1聚类算法的分类
7.3.2K-means聚类
7.3.3层次聚类
7.3.4自组织映射
7.3.5改进型聚类算法
7.4粒子对算法在基因聚类中的应用
7.4.1粒子结构
7.4.2聚类分析
7.4.3聚类结果
7.5基因聚类分析结果的评价标准
参考文献
第8章粒子群算法应用综述
8.1优化问题求解
8.1.1约束优化问题求解
8.1.2规划问题求解
8.1.3离散空间组合优化问题求解
8.2工程设计与优化领域
8.2.1电路及滤波器设计
8.2.2神经网络训练
8.2.3控制器设计与优化
8.2.4RBF网络优化训练举例
8.3电力系统领域
8.3.1电容器优化配置
8.3.2最优潮流计算与无功优化控制
8.3.3机组优化组合问题
8.3.4电网扩展计划
8.3.5电力系统恢复
8.3.6负荷经济分配及调度
8.3.7状态估计
8.3.8参数辨识
8.3.9优化设计
8.3.10OPF问题举例
8.4机器人控制领域
8.4.1机器人控制与协调
8.4.2移动机器人路径规划
8.5交通运输领域
8.5.1车辆路径问题
8.5.2VRP问题举例
8.5.3交通控制
8.6通信领域
8.6.1路由选择及移动通信基站布置优化
8.6.2天线阵列控制
8.6.3偏振模色散补偿
8.7计算机领域
8.7.1任务分配问题
8.7.2数据分类
8.7.3图像处理
8.8工业生产优化领域
8.8.1机械领域
8.8.2化工领域
8.9生物医学领域
8.10电磁学领域
参考文献
附录A粒子对算法应用于图像矢量量化的源代码
附录B智能单粒子优化算法求解函数的源代码
附录C23个基准测试函数
附录D基因聚类常用软件
……

B. 粒子群优化算法

         粒子群算法 的思想源于对鸟/鱼群捕食行为的研究，模拟鸟集群飞行觅食的行为，鸟之间通过集体的协作使群体达到最优目的，是一种基于Swarm Intelligence的优化方法。它没有遗传算法的“交叉”(Crossover) 和“变异”(Mutation) 操作，它通过追随当前搜索到的最优值来寻找全局最优。粒子群算法与其他现代优化方法相比的一个明显特色就是所 需要调整的参数很少、简单易行 ，收敛速度快，已成为现代优化方法领域研究的热点。

         设想这样一个场景：一群鸟在随机搜索食物。已知在这块区域里只有一块食物；所有的鸟都不知道食物在哪里；但它们能感受到当前的位置离食物还有多远。那么找到食物的最优策略是什么呢？

        1. 搜寻目前离食物最近的鸟的周围区域

        2. 根据自己飞行的经验判断食物的所在。

        PSO正是从这种模型中得到了启发，PSO的基础是 信息的社会共享

        每个寻优的问题解都被想象成一只鸟，称为“粒子”。所有粒子都在一个D维空间进行搜索。

        所有的粒子都由一个fitness function 确定适应值以判断目前的位置好坏。

        每一个粒子必须赋予记忆功能，能记住所搜寻到的最佳位置。

        每一个粒子还有一个速度以决定飞行的距离和方向。这个速度根据它本身的飞行经验以及同伴的飞行经验进行动态调整。

        粒子速度更新公式包含三部分： 第一部分为“惯性部分”，即对粒子先前速度的记忆；第二部分为“自我认知”部分，可理解为粒子i当前位置与自己最好位置之间的距离；第三部分为“社会经验”部分，表示粒子间的信息共享与合作，可理解为粒子i当前位置与群体最好位置之间的距离。

        第1步   在初始化范围内，对粒子群进行随机初始化，包括随机位置和速度

        第2步   根据fitness function，计算每个粒子的适应值

        第3步   对每个粒子，将其当前适应值与其个体历史最佳位置（pbest）对应的适应值作比较，如果当前的适应值更高，则用当前位置更新粒子个体的历史最优位置pbest

        第4步   对每个粒子，将其当前适应值与全局最佳位置（gbest）对应的适应值作比较，如果当前的适应值更高，则用当前位置更新粒子群体的历史最优位置gbest

        第5步   更新粒子的速度和位置

        第6步   若未达到终止条件，则转第2步

        【通常算法达到最大迭代次数或者最佳适应度值得增量小于某个给定的阈值时算法停止】

粒子群算法流程图如下：

以Ras函数（Rastrigin's Function）为目标函数，求其在x1,x2∈[-5,5]上的最小值。这个函数对模拟退火、进化计算等算法具有很强的欺骗性，因为它有非常多的局部最小值点和局部最大值点，很容易使算法陷入局部最优，而不能得到全局最优解。如下图所示，该函数只在(0,0)处存在全局最小值0。

C. 粒子群算法的算法介绍

如前所述，PSO模拟鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。
PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitness value)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。
PSO 初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己。第一个就是粒子本身所找到的最优解，这个解叫做个体极值pBest。另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。 在找到这两个最优值时，粒子根据如下的公式来更新自己的速度和新的位置：
v[] = w * v[] + c1 * rand() * (pbest[] - present[]) + c2 * rand() * (gbest[] - present[]) (a)
present[] = present[] + v[] (b)
v[] 是粒子的速度, w是惯性权重,present[] 是当前粒子的位置. pbest[] and gbest[] 如前定义 rand () 是介于（0， 1）之间的随机数. c1, c2 是学习因子. 通常 c1 = c2 = 2.
程序的伪代码如下
For each particle
____Initialize particle
END
Do
____For each particle
________Calculate fitness value
________If the fitness value is better than the best fitness value (pBest) in history
____________set current value as the new pBest
____End
____Choose the particle with the best fitness value of all the particles as the gBest
____For each particle
________Calculate particle velocity according equation (a)
________Update particle position according equation (b)
____End
While maximum iterations or minimum error criteria is not attained
在每一维粒子的速度都会被限制在一个最大速度Vmax，如果某一维更新后的速度超过用户设定的Vmax，那么这一维的速度就被限定为Vmax

D. 粒子群算法（一）：粒子群算法概述

  本系列文章主要针对粒子群算法进行介绍和运用，并给出粒子群算法的经典案例，从而进一步加深对粒子群算法的了解与运用（预计在一周内完成本系列文章）。主要包括四个部分：

  粒子群算法也称粒子群优化算法（Particle Swarm Optimization, PSO），属于群体智能优化算法，是近年来发展起来的一种新的进化算法（Evolutionary Algorithm, EA）。 群体智能优化算法主要模拟了昆虫、兽群、鸟群和鱼群的群集行为，这些群体按照一种合作的方式寻找食物，群体中的每个成员通过学习它自身的经验和其他成员的经验来不断地改变搜索的方向。 群体智能优化算法的突出特点就是利用了种群的群体智慧进行协同搜索，从而在解空间内找到最优解。
  PSO 算法和模拟退火算法相比，也是 从随机解出发，通过迭代寻找最优解 。它是通过适应度来评价解的品质，但比遗传算法规则更为简单，没有遗传算法的“交叉”和“变异”，它通过追随当前搜索到的最大适应度来寻找全局最优。这种算法以其 容易实现、精度高、收敛快 等优点引起了学术界的重视，并在解决实际问题中展示了其优越性。

  在粒子群算法中，每个优化问题的解被看作搜索空间的一只鸟，即“粒子”。算法开始时首先生成初始解，即在可行解空间中随机初始化 粒子组成的种群 ，其中每个粒子所处的位置 ，都表示问题的一个解，并依据目标函数计算搜索新解。在每次迭代时，粒子将跟踪两个“极值”来更新自己， 一个是粒子本身搜索到的最好解 ，另一个是整个种群目前搜索到的最优解 。 此外每个粒子都有一个速度 ，当两个最优解都找到后，每个粒子根据如下迭代式更新：

  其中参数 称为是 PSO 的 惯性权重(inertia weight) ，它的取值介于[0,1]区间；参数 和 称为是 学习因子(learn factor) ；而 和 为介于[0,1]之间的随机概率值。
  实践证明没有绝对最优的参数，针对不同的问题选取合适的参数才能获得更好的收敛速度和鲁棒性，一般情况下 , 取 1.4961 ，而 采用 自适应的取值方法 ，即一开始令 ， 使得 PSO 全局优化能力较强 ；随着迭代的深入，递减至 ， 从而使得PSO具有较强的局部优化能力 。

  参数 之所以被称之为惯性权重，是因为 实际 反映了粒子过去的运动状态对当前行为的影响，就像是我们物理中提到的惯性。 如果 ，从前的运动状态很少能影响当前的行为，粒子的速度会很快的改变；相反， 较大，虽然会有很大的搜索空间，但是粒子很难改变其运动方向，很难向较优位置收敛，由于算法速度的因素，在实际运用中很少这样设置。也就是说， 较高的 设置促进全局搜索，较低的 设置促进快速的局部搜索。

E. 粒子群算法

粒子群算法（particle swarm optimization，PSO）是计算智能领域中的一种生物启发式方法，属于群体智能优化算法的一种，常见的群体智能优化算法主要有如下几类：

除了上述几种常见的群体智能算法以外，还有一些并不是广泛应用的群体智能算法，比如萤火虫算法、布谷鸟算法、蝙蝠算法以及磷虾群算法等等。

而其中的粒子群优化算法（PSO）源于对鸟类捕食行为的研究，鸟类捕食时，找到食物最简单有限的策略就是搜寻当前距离食物最近的鸟的周围。

设想这样一个场景：一群鸟在随机的搜索食物。在这个区域里只有一块食物，所有的鸟都不知道食物在哪。但是它们知道自己当前的位置距离食物还有多远。那么找到食物的最优策略是什么？最简单有效的就是搜寻目前离食物最近的鸟的周围区域。

Step1:确定一个粒子的运动状态是利用位置和速度两个参数描述的，因此初始化的也是这两个参数；
Step2:每次搜寻的结果（函数值）即为粒子适应度，然后记录每个粒子的个体历史最优位置和群体的历史最优位置；
Step3:个体历史最优位置和群体的历史最优位置相当于产生了两个力，结合粒子本身的惯性共同影响粒子的运动状态，由此来更新粒子的位置和速度。

位置和速度的初始化即在位置和速度限制内随机生成一个N x d 的矩阵，而对于速度则不用考虑约束，一般直接在0~1内随机生成一个50x1的数据矩阵。

此处的位置约束也可以理解为位置限制，而速度限制是保证粒子步长不超限制的，一般设置速度限制为[-1,1]。

粒子群的另一个特点就是记录每个个体的历史最优和种群的历史最优，因此而二者对应的最优位置和最优值也需要初始化。其中每个个体的历史最优位置可以先初始化为当前位置,而种群的历史最优位置则可初始化为原点。对于最优值，如果求最大值则初始化为负无穷，相反地初始化为正无穷。

每次搜寻都需要将当前的适应度和最优解同历史的记录值进行对比，如果超过历史最优值，则更新个体和种群的历史最优位置和最优解。

速度和位置更新是粒子群算法的核心，其原理表达式和更新方式：

每次更新完速度和位置都需要考虑速度和位置的限制，需要将其限制在规定范围内，此处仅举出一个常规方法，即将超约束的数据约束到边界（当位置或者速度超出初始化限制时，将其拉回靠近的边界处）。当然，你不用担心他会停住不动，因为每个粒子还有惯性和其他两个参数的影响。

粒子群算法求平方和函数最小值，由于没有特意指定函数自变量量纲，不进行数据归一化。