粒子群算法基本原理

4.1 粒子群算法基本原理 [45] 最原始的工作可以追溯到1987 年 Reynolds 对鸟群社会 粒子群优化算法 系 统 Boids（Reynolds 对其仿真鸟群系统的命名）的仿真研究。通常，群体的行 为可以由几条简单的规则进行建模，虽然每个个体具有简单的行为规则，但是却 群体的行为却是非常的复杂， 所以他们在鸟类仿真中， 即 Boids 系统中采取了下 面的三条简单的规则 （1）飞离最近的个体 鸟 ，避免与其发生碰撞冲突； （2）尽量使自己与周围的鸟保持速度一致； （3）尽量试图向自己认为的群体中心靠近。 虽然只有三条规则， 但 Boids 系统已经表现出非常逼真的群体聚集行为。但 Reynolds 仅仅实现了该仿真，并无实用价值。 1995 年 Kennedy [46-48] 和 Eberhart 在 Reynolds 等人的研究基础上创造性地提 。Kennedy 和 Eberhart 在出了粒子群优化算法，应用于连续空间的优化计算中 boids 中加入了一个特定点，定义为食物，每只鸟根据周围鸟的觅食行为来搜寻 食物。Kennedy 和 Eberhart的初衷是希望模拟研究鸟群觅食行为，但试验结果 却显示这个仿真模型蕴含着很强的优化能力，尤其是在多维空间中的寻优。 最初 仿真的时候，每只鸟在计算机屏幕上显示为一个点，而“点”在数学领域具有多 种意义，于是作者用“粒子（particle）”来称呼每个个体，这样就产生了基本 的粒子群优化算法 [49] 。 假设在一个 D 维搜索空间中，有m 个粒子组成一粒子群，其中第i个粒子 的空间位置为X x , x ,x ,., xi1,2,., m，它是优化问题的一个潜在解， i1i 2i 3iDi 将它带入优化目标函数可以计算出其相应的适应值，根据适应值可衡量x的优 i 劣 ； 第i个 粒 子 所 经 历 的 最 好 位 置 称 为 其 个 体 历 史 最 好 位 置 ， 记 为 P p , p , p , . p , ii 1i2i 3i D i1, 2 ,，m相,应的适应值为个体最好适应值Fi；同 时，每个粒子还具有各自的飞行速度V i v ,v ,v ,., v i1,2,., m。所有粒 i1i 2i 3iD 子 经 历 过 的 位 置 中 的 最 好 位 置 称 为 全 局 历 史 最 好 位 置 ， 记 为 . PgPg ,Pg, Pg ,., PgD，相应的适应值为全局历史最优适应值 123 。在基本 PSO 算法中，对第n 代粒子，其第d维1≤ d≤ D 元素速度、位置更新迭代如式 4-1 、4-2 n 1nnn id n gd n v id n 1n v id n c 1 r 1 p id x c 2 r2px id 4-1 x id x id v id 4-2 其中 ω 为惯性权值； c1 和 c2 都为正常数，称为加速系数；r1 和 r2 是 两个在 [0, 1]范围内变化的随机数。第d 维粒子元素的位置变化范围和速度变 化范围分别限为制X ,min ,X ,max 和 V d ,min ,V d,max 。迭代过程中，若某一维粒子 dd 元素的 X或Vid超出边界值则令其等于边界 值。 id 粒子群速度更新公式4-1 中的第 1部分由粒子先前速度的惯性引起，为 “惯性”部分；第2 部分为“认知”部分，表示粒子本身的思考，即粒子根据 自 身粒 子 历基本 PSO 算法步骤如下 之 史 间 经 （1）粒子群初始化； 的 验 信 （2）根据目标函数计算各粒子适应度值，并初始化个体、全局最优值； 信 息 息 共 （ 对 享 步；3 自和 ） 相己 （4）根据速度、位置更新公式更新各粒子的速度和位置； 判 互 下 断 合 一 （5）根据目标函数计算各粒子适应度值； 是 作 步 否 ， 行（6）更新各粒子历史最优值以及全局最优值； 即满 为 群足 （7）跳转至步骤 3。 ；第 体 终 3 部分为“社会”部分，表示 信 止 对 息 于条 最大允许迭代次数。 对 终 粒 件 止 基 子 ， 条 和 是 下 续 件 迭 ω的取值对 PSO 算法的收敛性能至关重要。在最初的基本粒子群则 P一 惯性权值 ， 代 搜步S 次 算 行 O 索 通 数 法为 停 常 对 .。 中 算可 算 止 没 ，法 法 以 有 输中的 设 惯 性 置 出， 性 能 为 果其 一参数均 适 ；主 。最初的 PSO 算法容易陷入局部最小， 于是在其 后的研究中引入了惯性权值来改善PSO 算法的局部搜索能力，形成了目前常用 的基本 PSO 算法形式。取较大的 ω 值使得粒子能更好地保留速度，从而能更快 地搜索解空间， 提高算法的收敛速度； 但同时由于速度大可能导致算法无法更好 地进行局部搜索，容易错过最优解，特别是过大的ω会使得 PSO 算法速度过大 而无法搜索到全局最优。 取较小的 ω 值则有利于局部搜索， 能够更好地搜索到最 优值，但因为粒子速度受其影响相应变小从而无法更快地进行全局搜索，进而影 响算法收敛速度； 同时过小 ω 值更是容易导致算法陷入局部极值。因此，一个合 适的ω值能有效兼顾搜索精度和搜索速度、 全局搜索和局部搜索， 保证算法性能。 加速系数 c1 和 c2 代表每个粒子向其个体历史最好位置和群体全局历史最 好位置的移动加速项的权值。 较低的加速系数值可以使得粒子收敛到其最优解的 过程较慢，从而能够更好搜索当前位置与最优解之间的解空间；但过低的加速系 数值则可能导致粒子始终徘徊在最优邻域外而无法有效搜索目标区域，从而导致 算法性能下降。较高的加速系数值则可以使得粒子快速集中于目标区域进行搜 索，提高算法效率； 但过高的加速系数值则有可能导致粒子搜索间隔过大， 越过目标区域无法有效地找到全局最优解。因此加速系数对 容易 PSO 能否收敛也起 重要作用，合适的加速系数有利于算法较快地收敛，同时具有一定的跳出局部最 优的能力。 对于速度更新公式 4-1 中，若 c1 c2 0，粒子将一直以当前的速度进 行惯性飞行， 直到到达边界。 此时粒子仅仅依靠惯性移动，不能从自己的搜索经 验和其他粒子的搜索经验中吸取有用的信息，因此无法利用群体智能， PSO 算法 没有启发性， 粒子只能搜索有限的区域， 很难找到全局最优解， 算法优化性能很 差。若 c 0 ，则粒子没有认知能力，不能从自己的飞行经验吸取有效信息，只 有社会部分，所以 c 又称为社会参数；此时收敛速度比基本PSO 快，但由于不 能有效利用自身的经验知识， 所有的粒子都向当前全局最优集中，因此无法很好 地对整个解空间进行搜索，在求解存在多个局部最优的复杂优化问题时比基本 PSO 容易陷入局部极值，优化性能也变差。若c2 0 ，则微粒之间没有社会信 c 又称息共享，不能从同伴的飞行经验中吸取有效信息，只有认知部分，所以 为认知参数；此时个体间没有信息互享，一个规模为 单个粒子的运行，搜索到全局最优解的机率很小。 m 的粒子群等价于m 个 1 . PSO 算法中，群体规模对算法的优化性能也影响很大。一般来说，