下载掌阅APP，畅读海量书库
立即打开
PSO算法与其他的进化类算法类似，也采用“群体”和“进化”的概念，同样也根据个体的适应度值大小进行操作。不同的是，PSO算法中没有进化算子，而是将每个个体看作搜索空间中没有重量和体积的微粒，并在搜索空间中以一定的速度飞行，该飞行速度由个体飞行经验和群体的飞行经验进行动态调整。
设 X i =（ x i 1 ， x i 2 ，…， x in ）为第 i 个粒子的 n 维位置向量，根据事先设定的适应度函数计算该粒子当前的适应度值，即可衡量粒子位置的优劣； V i =（ v i 1 ， v i 2 ，…， v in ）为粒子 i 的飞行速度；Pbest i =（pbest i 1 ，pbest i 2 ，…，pbest in ）为粒子 i 迄今为止搜索到的最优位置。
为了方便讨论，设 f （ X ）为最小化的目标函数，则微粒 i 的当前最好位置为：
设群体中的微粒数为 N ，Gbest（ t ）=（gbest 1 ，gbest 2 ，…，gbest n ）为整个粒子群迄今为止搜索到的最优位置，则：
在每次迭代中，粒子根据式（4-4）更新速度和位置：
其中， j 表示为粒子的第 j 维， j =1，2，…， n ； i 表示第 i 个粒子， i =1，2，…， N ； t 是迭代次数； r 1 和 r 2 为[0，1]的随机数，这两个参数用来保持群体的多样性； c 1 和 c 2 为学习因子，也称加速因子， c 1 调节粒子飞向自身最好位置方向的步长， c 2 调节粒子飞向全局最好位置方向的步长，这两个参数对粒子群算法的收敛起的作用不是很大，但是适当调整这两个参数，可以减小局部最小值的困扰，当然也会使收敛速度变快。由于粒子群算法没有实际的机制来控制粒子速度，值太大会导致粒子跳过最好解，太小又会导致对搜索空间的不充分搜索，所以有必要对速度的范围进行限制，即 v ij ∈[- v max ， v max ]，位置 X i 的取值范围限定在[- X max ， X max ]内。
在粒子的位置更新公式（4-4）中，第一项表示粒子当前速度对粒子飞行的影响，这部分提供了粒子在搜索空间飞行的动力；第二项是“个体认知”部分，代表粒子的个人经验，粒子本身的思考促使粒子朝着自身所经历的最好位置移动；第三项是“群体认知”部分，代表粒子互相之间的信息共享与合作，体现群体经验对粒子飞行轨迹的影响，促使粒子朝着群体发现的最好位置移动。式（4-4）正是粒子根据上一次迭代的速度、当前位置，以及自身最好经验和群体最好经验之间的距离来更新速度，然后粒子根据式（4-5）飞向新的位置。
基本PSO算法的初始化过程如下所述。
（1）设定种群规模为 N ；
（2）对于任意 i ， j 在[- X max ， X max ]内服从均匀分布产生 x ij ；
（3）对于任意 i ， j 在[- V max ， V max ]内服从均匀分布产生 v ij 。
基本PSO算法的流程如图4.1所示。
步骤1：依照初始化过程，对微粒的随机位置和速度进行初始设定。
步骤2：计算每个微粒的适应度值。
步骤3：对于每个微粒，将其适应度值与所经历过的最好位置Pbest i 的适应度值进行比较，若较好，则将其作为当前最好位置。
步骤4：对每个微粒，将其适应度值与全局所经历的最好位置Gbest进行比较，若较好，则将其作为当前的全局最优值。
步骤5：根据式（4-4）和式（4-5）对微粒的速度和位置进行进化。
步骤6：如果未达到终止条件或达到预定的最大代数，则返回步骤2。
为了改善基本PSO算法的收敛性能，Y. Shi与R. C. Eberhart首次引入了惯性权重的概念 [2] ，即：
其中， ω 称为惯性权重，基本PSO算法是惯性权重 ω =1的特殊情况。惯性权重 ω 使粒子保持飞行惯性，使其可以扩展搜索空间，有能力探索新的区域。
图4.1 PSO算法流程图
惯性权重 ω 的引入清除了基本PSO算法对速度最大值的需求，因为 ω 的作用就是保持全局和局部搜索能力的平衡。当速度最大值增加时，就人为减少 ω 来达到搜索的平衡，而 ω 的减少可降低需要的迭代次数，就可以将 j 维速度的最大值锁定为每维变量的变化范围，只对 ω 进行调节。
对全局搜索，广泛使用的方法是在前期利用较高的探索能力得到具有超高潜力且多样化的种子，而在后期提升开发能力以加快收敛速度，所以，可将 ω 设定为随进化迭代次数线性减少（例如由0.9减到0.4）。Y. Shi和R. C. Eberhart的仿真实验结果表明， ω 线性减少取得了较好的实验结果 [3] ，这种线性变换的 ω 可以模仿模拟退火的中的温度。有些情况下对上轮迭代粒子速度给予不保留策略，能够有效提高整个种群的搜索能力。
为了克服高维问题中维数灾难的问题，Potter提出了将解向量分解成各个小向量，通过分割搜索空间完成寻优。Bergh等基于这种思想提出了一种协同PSO [4] 算法，该方法是将 n 维解向量分解成 n 个一维的解向量，再把种群分解成 n 个粒子群，每个粒子群优化一个一维解向量。在每一次迭代过程中，每个粒子群相互独立地进行粒子的更新，群之间不共享信息。计算适应度时，将分量合成一个完整的向量，组成 n 维向量并代入适应度函数计算适应度值。这种协同PSO算法有明显的“启动延迟”（start-up delay）现象，在演化初期，收敛速度偏慢。粒子群数目越大，收敛越慢。实际上，这种协同PSO算法采用的是局部学习策略，所以相对基本PSO算法有较高的收敛精度。
为了克服粒子群算法在遍历搜索空间上的缺陷，Sun等从量子力学的角度提出了量子粒子群算法（Qutantum-behaved Particle Swarm Optimization，QPSO） [5] 。在QPSO算法中，每个个体均被描述为量子空间中的粒子。在量子空间中，因为粒子的位置是根据不确定原则决定的，它可以以一定的概率出现在可行区域的任何位置，所以其全局收敛的性能要优于标准PSO算法。在QPSO算法中，丢弃了PSO算法中原来的速度向量，粒子的状态由波函数进行描述，通过求解薛定谔方程得到粒子在空间某一点出现的概率密度函数，然后再利用蒙特卡洛随机模拟得到粒子位置 [6-7] 。
根据没有免费的午餐理论，每种进化算法都有各自的优缺点，因此，如何将PSO算法与其他算法结合得到新的智能算法也是当前的研究热点之一。例如，在PSO算法中引入遗传算法的选择、交叉和变异算子；将差分进化算法用于种群陷入局部最优解时，产生新的全局最优粒子；将粒子更新后所获得的新的粒子，采用模拟退火的思想决定是否接受进入下一代迭代。Wei和陶新民提出基于均值的混合PSO算法，在算法运行过程中，根据每个粒子的适应度函数值来确定 K -means算法的操作时机，不仅增强算法局部精确搜索能力，而且还缩短了收敛时间。Qin和Zhao将局部搜索算法嵌入到PSO算法中，每间隔若干代对粒子自身最优位置进行局部搜索，如果获得的局部最优解优于粒子自身历史最优解，则进行替换，这种策略使得粒子避免了在局部最优解处的聚集。Ki-Baek等也提出具有变异操作的PSO算法，通过引入变异思想，提升算法的全局搜索能力，从而向最优解位置收敛。
还有很多关于混合PSO算法的研究，将PSO算法与其他算法通过一定的规则结合在一起，以发挥各自算法的优势。Shu、Xing和Xin将差分进化算法与PSO算法进行混合；Behnamian和Savsani将PSO算法与模拟退火算法 [8] 进行混合；Sadeghierad和Rashid将PSO算法与遗传算法进行混合；Niknam、Kaveh和Marinakis将PSO算法与蚁群算法进行混合；Wang、Li和Nakano将禁忌算法 [9-11] 与PSO算法进行混合等。
除了上述混合算法外，还出现大量基于自适应PSO算法、带有收缩因子的PSO算法和小生境PSO算法等的混合改进算法，还有提出从种群内个体共协作行为来改进算法的策略。总之，无论哪种混合算法，都是为了提升种群多样性，但这些混合策略都需要引入新的参数来控制各种操作的时机，而这些参数的设置也在一定程度上影响着算法的性能。较之其他进化算法，PSO算法的优势在于简单、易实现，同时又有深刻的智能背景，既适合科学研究，又特别适合工程应用。