4.1 粒子群算法基本原理粒子群优化算法［45］最原始的工作可以追溯到 1987 年 Reynolds 对鸟群社会 系统 Boids（Reynolds 对其仿真鸟群系统的命名）的仿真研究 通常，群体的 行为可以由几条简单的规则进行建模 ，虽然每个个体具有简单的行为规则，但 是却群体的行为却是非常的复杂，所以他们在鸟类仿真中，即 Boids 系统中采 取了下面的三条简单的规则：（1）飞离最近的个体（鸟），避免与其发生碰撞冲突；（2）尽量使自己与周围的鸟保持速度一致；（3）尽量试图向自己认为的群体中心靠近虽然只有三条规则，但 Boids 系统已经表现出非常逼真的群体聚集行为 但 Reynolds 仅仅实现了该仿真 ，并无实用价值1995年Kennedy%-48］和Eberhart在Reynolds等人的研究基础上创造性地 提出了粒子群优化算法，应用于连续空间的优化计算中Kennedy和Eberhart 在 boids 中加入了一个特定点， 定义为食物， 每只鸟根据周围鸟的觅食行为来 搜寻食物Kennedy和Eberhart的初衷是希望模拟研究鸟群觅食行为，但试验 结果却显示这个仿真模型蕴含着很强的优化能力 ， 尤其是在多维空间中的寻 优。
最初仿真的时候， 每只鸟在计算机屏幕上显示为一个点 ， 而“点”在数学领 域具有多种意义,于是作者用“粒子（particle ）"来称呼每个个体,这样就产生 了基本的粒子群优化算法［49］假设在一个D维搜索空间中,有m个粒子组成一粒子群,其中第i个粒子 的空间位置为X二（x ,x ,x x ） i二1,2,..., m ,它是优化问题的一个潜在i i1 i 2 i3 iD解，将它带入优化目标函数可以计算出其相应的适应值 ，根据适应值可衡量 xi 的优劣 ； 第 i 个粒子所经历的最好位置称为其个体历史最好位置 ， 记为P二(p , p , p，…，p )归1,2,..加相应的适应值为个体最好适应值Fi ;同 i i1 i2 i3 i D时，每个粒子还具有各自的飞行速度V = (v , v , v ,..., v ) i = 1,2,..., m所有粒 i i1 i 2 i3 iD子 经 历 过 的 位 置 中 的 最 好 位 置 称 为 全 局 历 史 最 好 位 置 ， 记 为P g= ( Pg P g P, g・・，P相应的适应值为全局历史最优适应值 在基本 123DPSO算法中，对第n代粒子,其第d维(IsdsD )元素速度、位置更新迭代如式(4-1)、 (4-2)：vn+1 = ® X vn + c X r X (pn — Xn ) + C X 厂 X (pn — Xn ) (4-1)id id 1 1 id id 2 2 gd idX n+1 = X n + v n (4-2)id id id其中：3为惯性权值;cl和c2都为正常数,称为加速系数;r1和r2是 两个在［0, 1］范围内变化的随机数。
第 d 维粒子元素的位置变化范围和速度变化 范围分别限制为「X ,X ］和「V ,V ］迭代过程中，若某一维粒子元d ,min d ,max d ,min d ,max素的X 或V 超出边界值则令其等于边界值id id粒子群速度更新公式(4-1)中的第 1 部分由粒子先前速度的惯性引起 ， 为 “惯性”部分； 第 2 部分为“认知”部分， 表示粒子本身的思考， 即粒子根据自身历史经验信息对自己下一步行为的影响； 第 3 部分为“社会”部分， 表示粒子之 间的信息共享和相互合作， 即群体信息对粒子下一步行为的影响基本 PSO 算法步骤如下：(1) 粒子群初始化；(2) 根据目标函数计算各粒子适应度值， 并初始化个体、 全局最优值；(3) 判断是否满足终止条件， 是则搜索停止， 输出搜索结果； 否则继续下步；（4）根据速度、位置更新公式更新各粒子的速度和位置；（5）根据目标函数计算各粒子适应度值；（6）更新各粒子历史最优值以及全局最优值；（7）跳转至步骤 3对于终止条件 ，通常可以设置为适应值误差达到预设要求 ，或迭代次数超 过最大允许迭代次数基本的连续 PSO 算法中，其主要参数 ，即惯性权值 、加速系数、种群规 模和迭代次数对算法的性能均有不同程度的影响 。
惯性权值3的取值对PSO算法的收敛性能至关重要在最初的基本粒子 群算法中没有惯性权值这一参数 最初的 PSO 算法容易陷入局部最小，于是 在其后的研究中引入了惯性权值来改善 PSO 算法的局部搜索能力 ，形成了目 前常用的基本 PSO 算法形式 取较大的3值使得粒子能更好地保留速度，从 而能更快地搜索解空间，提高算法的收敛速度；但同时由于速度大可能导致算 法无法更好地进行局部搜索,容易错过最优解,特别是过大的3会使得PSO算 法速度过大而无法搜索到全局最优 取较小的3值则有利于局部搜索， 能够更 好地搜索到最优值， 但因为粒子速度受其影响相应变小从而无法更快地进行全 局搜索， 进而影响算法收敛速度 ；同时过小3值更是容易导致算法陷入局部极 值 因此， 一个合适的 3值能有效兼顾搜索精度和搜索速度 、全局搜索和局部 搜索， 保证算法性能加速系数 c1 和 c2 代表每个粒子向其个体历史最好位置和群体全局历史最 好位置的移动加速项的权值 较低的加速系数值可以使得粒子收敛到其最优解的过程较慢，从而能够更好搜索当前位置与最优解之间的解空间 ；但过低的加速系数值则可能导致粒子始终徘徊在最优邻域外而无法有效搜索目标区域 ，从 而导致算法性能下降。
较高的加速系数值则可以使得粒子快速集中于目标区域 进行搜索，提高算法效率；但过高的加速系数值则有可能导致粒子搜索间隔过 大，容易越过目标区域无法有效地找到全局最优解 因此加速系数对 PSO 能 否收敛也起重要作用，合适的加速系数有利于算法较快地收敛 ，同时具有一定 的跳出局部最优的能力对于速度更新公式(4-1 )中，若cl = c2 = 0,粒子将一直以当前的速度进行 惯性飞行， 直到到达边界此时粒子仅仅依靠惯性移动 ， 不能从自己的搜索经 验和其他粒子的搜索经验中吸取有用的信息， 因此无法利用群体智能， PSO 算 法没有启发性， 粒子只能搜索有限的区域 ， 很难找到全局最优解， 算法优化性 能很差若 c = 0， 则粒子没有认知能力， 不能从自己的飞行经验吸取有效信 息， 只有社会部分， 所以 c 又称为社会参数；此时收敛速度比基本 PSO 快， 但由于不能有效利用自身的经验知识 ， 所有的粒子都向当前全局最优集中 ， 因 此无法很好地对整个解空间进行搜索 ， 在求解存在多个局部最优的复杂优化问 题时比基本 PSO 容易陷入局部极值， 优化性能也变差若 c2 = 0， 则微粒之 间没有社会信息共享 ， 不能从同伴的飞行经验中吸取有效信息 ， 只有认知部 分,所以c又称为认知参数；此时个体间没有信息互享,一个规模为m的粒子 群等价于 m 个 1 单个粒子的运行， 搜索到全局最优解的机率很小。
PSO 算法中， 群体规模对算法的优化性能也影响很大一般来说， 群体规 模越大， 搜索到全局最优解的可能性也越大 ， 优化性能相对也越好； 但同时算 法消耗的计算量也越大， 计算性能相对下降群体规模越小， 搜索到全局最优解的可能性就越小，但算法消耗的计算量也越小 群体规模对算法性能的影响并不是简单的线性关系，当群体规模到达一定程度后 ，再增加群体规模对算法 性能的提升有限，反而增加运算量；但群体规模不能过小，过小的群体规模将 无法体现出群智能优化算法的智能性，导致算法性能严重受损对于最大允许迭代次数 ，较大的迭代次数使得算法能够更好地搜索解空 间，因此找到全局最优解的可能性也大些 ；相应地，较小的最大允许迭代次数 会减小算法找到全局最优解的可能性 对于基本连续 PSO 来说，由于缺乏有 效的跳出局部最优操作，因此粒子一旦陷入局部极值后就难以跳出 ，位置更新 处于停滞状态 ，此时迭代次数再增多也无法提高优化效果 ，只会浪费计算资 源但过小的迭代次数则会导致算法在没有对目标区域实现有效搜索之前就停 止更新，将严重影响算法性能此外，随机数可以保证粒子群群体的多样性和 搜索的随机性最大、最小速度可以决定当前位置与最好位置之间区域的分辨 率（或精度）。
如果最大速度（或最小速度）的绝对值过大，粒子可能会因为累 积的惯性速度太大而越过目标区域 ，从而无法有效搜索到全局最优解 ；但如果 最大速度（或最小速度）的绝对值过小，则粒子不能迅速向当前全局最优解集 中，对其邻域进行有效地搜索，同时还容易陷入局部极值无法跳出因此，最大、最小速度的限制主要是防止算法计算溢出 、改善搜索效率和 提高搜索精度 基本 PSO 算法中只涉及基本的加、减、乘运算操作，编程简 单，易于实现，关键参数较少，设定相对简单，所以引起了广泛的关注，目前 已有多篇文献对 PSO 算法进行综述 为了进一步提高基本 PSO 算法的寻优性能 ，大量研究工作致力于对基本 PSO 算法的改进，主要集中于：1）对 PSO 算法更新公式参数、结构的改进主要是对基本 PSO 算法的速度、位置更新公式中的参数 、结构进行调节 和增加，以进一步提高算法的优化性能 ，如引入了惯性权值的 PSO 算法 、自 适应惯性权值PSO］算法、模糊自适应惯性权值PSO算法、带收缩因子的 PSO算法、Kalman粒子群算法、带邻域算子的PSO算法、具有社会模式的簇 分析PSO算法、被动集合PSO算法等等2） 多群、 多项 PSO 算法多群 PSO 算法即引入多个群体进行优化搜索 ；而多相 PSO 算法中多群 体的各个群体对不同的搜索目标以不同的方式进行搜索 。
3） 混合 PSO 算法混合 PSO 算法的基本思想就是将 PSO 算法与其它不同算法相结合 ，实 现优势互补,从而进一步提高PSO算法的寻优性能,如模拟退火PSO算法、 GA-PSO 混合算法等等在工程应用中 ， 目前 PSO 算法在函数优化 、 神经网络训练 、 调度问 题 、 故障诊断 、 建模分析 、 电力系统优化设计 、 模式识别 、 图象处理 、 数据挖掘 等众多领域中均有相关的研究应用报道 ， 取得了良好的实际应用效 果4.2离散二进制PSO算法离散二进制优化算法具有很多优势 ， 首先对于纯组合优化问题的表达形式 要求优化算法是离散的， 其次二进制算法可以表达浮点数 ， 因此也同样适用于 连续空间的问题求解4.2.1 KBPSO 算法PSO 算法最初是用来对连续空间问题进行优化的 ，为了解决离散优化问题 Kennedy 和 Eberhart 于 1997 年在基本 PSO 的基础上提出了一种离散二进 制 PSO(KBPSO )算法在 KBPSO 算法中 ，粒子定义为一组由 0，1 组成的 二进制向量KBPSO保留了原始的连续PSO的速度公式(4-1),但速度丧失了 原始的物理意义。
在 KBPSO 中， 速度值 vid 通过预先设计的 S 形限幅转换函 数Sig(v )转换为粒子元素x取“1 ”的概率速度值v越大,则粒子元素位置 id id idx 取1的可能性越大， 反之则越小4-1)idVn+l = ® x Vn + c X r X (pn — Xn ) + C X 厂 X (pn — Xn ) id id 1 1 id id 2 2 gd idSig(vid ) =l+ exp(—v )id4-3)xid1 if - rand () < Sig (v )id0 otherwise(4-4)其中Sig。