人工智能–粒子群算法

人工智能之粒子群算法PSO

前言：人工智能机器学习有关算法内容，请参见公众号“科技优化生活”之前相关文章。人工智能之机器学习主要有三大类:1)分类;2)回归;3)聚类。今天我们重点探讨一下粒子群算法PSO^_^。粒子群优化算法PSO起源对简单社会系统的模拟,最初设想是模拟鸟群觅食的过程。后来发现PSO是一种很好的优化工具。

粒子群算法，也称为粒子群优化算法或鸟群觅食算法（Particle Swarm Optimization），缩写为 PSO。该算法由J. Kennedy和R. C. Eberhart两位博士在1995年提出，是对Hepper的模拟鸟群(鱼群)的模型进行修正，以使粒子能够飞向解空间，并在最好解处降落，从而得到了粒子群优化算法。

粒子群算法PSO是一种新的进化算法EA(Evolutionary Algorithm)。它和遗传算法相似，也是从随机解出发，通过迭代寻找最优解，也是通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的“交叉”(Crossover) 和“变异”(Mutation) 操作，它通过追随当前搜索到的最优值来寻找全局最优。

粒子群算法PSO以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。粒子群算法是一种并行算法。

粒子群算法概念：

先说说遗传算法GA（请参见人工智能（28））。它通过模仿自然界的选择与遗传的机理来寻找最优解. 遗传算法有三个基本算子:选择、交叉和变异. 但是遗传算法的编程实现比较复杂,首先需要对问题进行编码,找到最优解之后还需要对问题进行解码,另外三个算子的实现也有许多参数,如交叉率和变异率,并且这些参数的选择严重影响解的品质,而目前这些参数的选择大部分是依靠经验。

再说说粒子群优化算法PSO。它是一种进化计算技术，源于对鸟群捕食的行为研究。该算法最初是受到飞鸟集群活动的规律性启发，进而利用群体智能建立的一个简化模型。粒子群优化算法PSO在对动物集群活动行为观察基础上，利用群体中的个体对信息的共享使整个群体的运动在问题求解空间中产生从无序到有序的演化过程，从而获得最优解。

粒子群优化算法PSO同遗传算法GA类似，都是基于迭代的优化算法。系统初始化为一组随机解，通过迭代搜寻最优值。但是它没有遗传算法用的交叉(crossover)以及变异(mutation)，而是粒子在解空间追随最优的粒子进行搜索。同遗传算法比较，PSO的优势在于简单容易实现并且没有许多参数需要调整。

粒子群算法原理：

PSO从鸟群的捕食行为中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟,称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitness value)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。

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

粒子群算法核心：

粒子群优化算法PSO的核心：利用群体中的个体对信息的共享，从而使得整个群体的运动在问题求解空间中产生从无序到有序的演化过程，从而获得问题的最优解。

粒子群算法公式:

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

v[]= w * v[] + c1 * rand() * (pbest[] - present[]) + c2 * rand() * (gbest[] -present[]) ----(1)

present[]= present[] + v[] ----(2)

v[]----粒子的速度

w----惯性权重

present[]----当前粒子的位置.

pbest[]----个体极值pBest

gbest[]----全局极值gBest

rand()----介于（0， 1）之间的随机数

c1,c2 ----学习因子,通常 c1 = c2 = 2

PSO算法的精华在于上述两个公式：

公式（1）为速度更新公式：看别的解有哪些优越的东西值得当前解去学习，将那些优秀的东西提取出来。

公式（2）为位置更新公式：让当前解去学习提取出来的别的解的优秀之处。速度更新公式

让公式（1）和（2）过程迭代。在迭代过程中，每一只鸟要记录自己的历史最好成绩，另外记录全局最优的那只鸟的位置，不断根据这些比当前解好的部分去微调，直到算法结束。

粒子群算法过程：

粒子群算法步骤：

粒子群算法有两个重要步骤:

1）问题解的编码: 采用实数编码

2）适应度函数: 适应度函数就是f(x)

接着就可以利用前面过程去寻优.这个寻优过程是一个叠代过程, 中止条件一般为设置为达到最大循环数或者最小错误。

粒子群算法参数设置：

下面列出关键参数和经验设置：

1）粒子数: 一般取 20~40。对于一般问题10个粒子就足够。对于比较难的问题或者特定类别的问题, 粒子数可以取到100 ~ 200

2）粒子的长度: 就是问题解的长度，由优化问题所决定。

3）粒子的范围: 由优化问题决定,每一维可以设定不同的范围。

4）Vmax最大速度: 决定粒子在一个循环中最大的移动距离,通常设定为粒子的范围宽度。

5）学习因子: 一般 c1 等于 c2 ，范围在0和4之间，通常c1 和 c2 等于2。

6） 中止条件: 最大循环数以及最小错误要求。这个中止条件由具体的问题确定。

7）全局PSO和局部PSO: 即两种版本的粒子群优化算法: 全局版和局部版。前者速度快不过有时会陷入局部最优。后者收敛速度慢一点不过很难陷入局部最优。 在实际应用中, 可以先用全局PSO找到大致结果,再用局部PSO进行搜索。

8）惯性权重：当Vmax很小时（对schaffer的f6函数，Vmax=3),使用权重w=0.8较好.如果没有Vmax的信息,使用0.8作为权重也是一种很好的选择.惯性权重w很小时偏重于发挥粒子群算法的局部搜索能力；惯性权重很大时将会偏重于发挥粒子群算法的全局搜索能力。

粒子群算法分类：

基于粒子群算法PSO的约束优化工作，主要分为两类：

1）罚函数法。罚函数的目的是将约束优化问题转化成无约束优化问题。

2）将粒子群的搜索范围都限制在条件约束簇内，即在可行解范围内寻优。

粒子群算法优点：

PSO优点是简单，容易实现，无需梯度信息，参数少，特别是其天然的实数编码特点特别适合于处理实优化问题。同时又有深刻的智能背景，既适合科学研究，又特别适合工程应用。

1）相较于传统算法计算速度非常快，全局搜索能力也很强；

2）PSO对于种群大小不十分敏感，所以初始种群设为500-1000，速度影响也不大；

3）粒子群算法适用于连续函数极值问题，对于非线性、多峰问题均有较强的全局搜索能力。

粒子群算法缺点：

PSO缺点是对于离散的优化问题处理不佳，容易陷入局部最优。在某些问题上性能并不是特别好。网络权重的编码而且遗传算子的选择有时比较麻烦。

粒子群算法与遗传算法比较：

两个算法的共同点：

1)种群随机初始化。

2)对种群内的每一个个体计算适应值(fitnessvalue)。适应值与最优解的距离直接有关。

3)种群根据适应值进行复制。

4)如果终止条件满足的话，就停止，否则转步骤2)。

从以上步骤可以看出：两者都随机初始化种群，都使用适应值来评价系统，而且都根据适应值来进行一定的随机搜索。两个系统都不是保证一定找到最优解。但是，PSO没有遗传操作如交叉(crossover)和变异(mutation)，而是根据自己的速度来决定搜索。粒子还有一个重要的特点，就是有记忆。

另外，两者都具有演化计算的优势，处理一些传统方法不能处理的东西，比如不可导的节点传递函数或者没有梯度信息存在。

两个算法的不同点：

与遗传算法比较，PSO信息共享机制是不同的。在遗传算法中，染色体互相共享信息，所以整个种群的移动是比较均匀的向最优区域移动。而在PSO中,只有gBest(orlBest)给出信息给其他的粒子，这是单向的信息流动。整个搜索更新过程是跟随当前最优解的过程。与遗传算法比较,在大多数的情况下，所有的粒子可能更快的收敛于最优解。

遗传算法适合求解离散问题,具备数学理论支持,但是存在着汉明悬崖等问题。

粒子群算法适合求解实数问题,算法简单,计算方便,求解速度快,但是存在着陷入局部最优等问题。

遗传算法比较适用于离散问题的求解，而粒子群算法比较适合连续性问题的求解。

要将两种算法进行混合,就要针对特定问题,然后融合其中的优势,比如将遗传算法中的变异算子加入粒子群中就可以形成基于变异的粒子群算法。

粒子群算法应用：

最近已经有一些利用PSO来代替反向传播算法来训练神经网络的论文。研究表明PSO是一种很有潜力的神经网络算法。PSO速度比较快而且可以得到比较好的结果。

目前PSO已广泛应用于函数优化，神经网络训练，模糊系统控制以及其他遗传算法的应用领域。

结语:

粒子群算法PSO是一种基于群智能的演化计算方法，由Kennedy和Eberhart于1995年提出。该算法源于对鸟类捕食行为的模拟。通过群体中个体之间的协作和信息共享来寻找最优解。因其概念简明、实现方便、精度高、收敛速度快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。粒子群算法应用范围较广，灵活性很大扩展性强。它在函数优化，神经网络训练，模糊系统控制以及其他遗传算法等领域得到越来越广泛的应用。

------以往文章推荐-----