粒子群优化算法的发展

2.1.2　粒子群优化算法的发展

1．基本粒子群优化算法

PSO算法是一种高效的并行搜索算法。它同样基于群体和适应度两个概念，保留了基于种群的全局搜索策略，采用的“速度—位移”模型操作简单，避免了复杂的遗传操作。它特有的记忆功能使其可以动态跟踪当前的搜索情况调整其搜索策略。每个粒子代表问题的一个解，具有位置和速度两个描述量。粒子的位置坐标对应的目标函数值即可作为该粒子的适应度，通过适应度来衡量粒子的优劣。PSO算法随机初始化一群粒子，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”————个体极值和全局极值，来更新自己的速度和位置。

假设在一个d维的目标搜索空间中，有N个代表潜在问题解的粒子组成的一个种群S={X₁，X₂，…，X_N}，其中，X_i=(x_i1，x_i2，…，x_id)，i=1，2，…，N表示第i个粒子在d维解空间的一个矢量点。将P_i=(p_i1，p_i2，…，p_id)，i=1，2，…，N代入一个与求解问题相关的目标函数可以计算出相应的适应值。用P_i=(p_i1，p_i2，…，p_id)，i=1，2，…，N记录第i个粒子自身搜索到的最好点，记为pbest。而在这个种群中，至少有一个是最好的，将其编号为g，则p_g=(p_g1，p_g2，…，p_gd)就是种群搜索到的最好值，记为gbest，其中g∈{1，2，…，N}。而每个粒子还有一个速度变量，可以用V_i=(v_i1，v_i2，…，v_id)，i=1，2，…，N表示第i个粒子的速度。在找到这两个最优值后，粒子通过下面的两个公式来更新自己的速度和位置。

在公式(2.1)和(2.2)中，i=1，2，…，N(N是该群体中粒子的总数)。

图2.1　基本粒子群优化算法流程图

其中，t为算法当前迭代的次数;v^t_id为粒子i第t次迭代后的速度矢量的第d维分量;x^t_id为粒子i第t次迭代后的位置矢量的第d维分量;p_id为粒子i历史最好位置的第d维分量;p_gd为种群当前最好位置的第d维分量;R₁，R₂为服从U(0，1)分布的随机数;c₁，c₂为学习因子，通常取c₁=c₂=2。

在每一维，粒子都有一个最大限制速度V_max，如果某一维的速度超过设定的V_max，那么这一维的速度就被限定为V_max。PSO算法的流程图如图2.1所示。

2．标准粒子群优化算法

Yuhui Shi等^［59］引入了惯性权重(Inertia Weight)的概念，并对公式(2.1)进行了修正，得到如下公式，其中ω非负，称为惯性权重因子。

从此，公式(2.2)和(2.3)被研究学者视为标准PSO算法。

从社会学的角度来看，公式(2.3)的第一部分称为记忆项，表示过去速度大小和方向对现在的影响;第二部分称为自身认知项，是从当前点指向此粒子自身最好点的一个矢量，表示粒子的动作来源于自己的经验;第三部分称为群体认知项，是从当前点指向种群最好点的一个矢量，反映了粒子间的协同合作和知识共享。粒子就是这样通过自己的经验和同伴中最好的经验来决定下一步的运动，这与人类的决策极其相似，人们通常也是通过自身已有的信息和从外界得到的信息来做出决策的。

当ω=0时，即如果公式(2.3)没有第一项，那么粒子的速度仅仅取决于粒子的当前位置和它们最好的历史位置，模型变为

公式(2.4)说明速度自身没有记忆性，假设在开始的时候，粒子i正好是在整体最好点，那么粒子i将以速度0“飞翔”，这将保持粒子此次的位置不变，直到出现新的一个最好点替代粒子i。同时，每个粒子将向自身最好点和整体最好点的加权中心方向“飞翔”。c₁和c₂通常取常数2，这样使得“社会认知”和“个体经验”的期望权重为1。这种情况下，各个粒子逐渐地向当前最好的位置靠拢，直到出现新的最好点，粒子群体又向那个位置靠拢。因此，可以想象，没有第一项内容的情况下，粒子群算法更多显现的是局部搜索能力。从另外一层意思来说，第一项内容使得粒子有一种扩展搜索空间的能力，即开拓能力，是一种全局搜索能力的表现。

当c₁=0时，即如果公式(2.3)没有第二项，则粒子没有了认知能力，模型变为只有社会(Social-Only)模型:

此时的算法被称为全局PSO算法。粒子有扩展搜索空间的能力，具有较快的收敛速度，但由于缺少局部搜索，对于复杂的优化问题此算法比标准PSO算法更易陷入局部最优。

当c₂=0时，即如果公式(2.3)没有第三项，则粒子之间没有社会信息，模型变为只有认知(Cognition-Only)模型:

此时的算法被称为局部PSO算法。由于个体之间没有信息的交流，整个群体相当于多个粒子进行盲目的随机搜索，收敛速度慢，因而得到最优解的可能性小。

当c₁=c₂=0时，即如果公式(2.3)既没有第二项，也没有第三项，则粒子没有认知能力和社会信息，模型变为

当ω＞1时，粒子的速度将很快达到最大限制速度V_max或－V_max，粒子将一直以此速度飞行直到边界，这样的粒子群算法将不可能找到一个可接受的解;当0＜ω＜1时，粒子的速度将很快趋近于零，说明粒子的飞行接近停止，算法亦很快停滞，粒子也很难找到最优解。

综上分析，在求解各种优化问题时，全局搜索和局部搜索都是非常关键的部分，在实际解决不同的优化问题时，我们应该要衡量好两种搜索对问题求解的贡献，不能顾此失彼。

3．带有收缩因子的粒子群优化算法

PSO算法起源于对生物群体行为的模拟，但算法的理论基础还相对比较薄弱。Clerc^［60］在对PSO算法的初步理论研究中，提出了收缩因子(Constriction Factor)的概念，描述了一种选择ω，c₁，c₂这三个参数值的方法，以确保算法收敛。通过正确地选择这些控制参数，Clerc认为没有必要将粒子速度控制在速度的极值区间内。接下来讨论一个带有收缩因子的粒子群优化算法相关的收敛模式特例:

其中，χ=，且L=c₁+c₂＞4。通常取L为4.1，c₁=c₂=2.05，得出χ=0.729 8，将这些参数的数值带入公式(2.8)可得到如下公式:

因为2.05×0.729 8=1.496 2，所以这个公式与带有惯性权重的PSO算法速度更新公式(2.3)在c₁=c₂=1.496 2和ω=0.729 8时所得到的公式是等价的。表明带有收缩因子的PSO算法和带有惯性权重的PSO算法本质上是一致的，因此前者可以看做是后者的一个特例。

在算法早期的实验和应用中，一般认为当采用收敛因子模型时V_max参数无足轻重，因此将V_max设置为一个极大值，如100 000。后来的研究表明设置合适的V_max，算法可以取得更好的优化效果。Eberhart和Yuhui Shi^［61］分别对利用速度极值和收缩因子来控制粒子速度的两种算法性能做了比较，结果表明后者通常比前者具有更好的收敛率。然而在有些测试函数的求解过程中，使用收缩因子的算法在给定的迭代次数内无法达到全局极值点。按照Eberhart和Shi的观点，这是由于粒子偏移所期望的搜索空间太远而造成的。为了降低这种影响，他们建议在使用收缩因子时首先对算法进行限定，比如使得速度极值等于搜索域极值或者预先设置搜索空间的大小，这样不管是在收敛率方面还是在搜索能力方面可以改进算法对所有测试函数的求解性能。

4．二进制粒子群优化算法

最初的PSO算法只能解决连续优化问题，但是很多实际的工程优化问题是组合优化问题，Kennedy等巧妙地对粒子的位置更新公式做了修改，提出了PSO算法的离散二进制版，用来解决工程实际中的组合优化问题。在二进制粒子群优化算法^［62-63］(Binary Particle Swarm Optimization，简称BPSO)中，每一维，和限制为1或者0，但是速度没有此限制。如果高一些，粒子的位置更有可能选取1，低一点则选取0的概率就大些，阈值在［0，1］之间，而有这种特点的函数就是Sigmod函数，它的定义如下:

BPSO算法的公式就要相应地做出调整，速度更新公式(2.3)不变，位置更新公式(2.2)调整为

rnd是服从U(0，1)均匀分布的随机数，为了防止Sigmod函数饱和，可以将速度分量限制在［－4，+4］之间。BPSO算法流程与PSO算法基本一致，此处不再赘述。