粒子群算法基本原理.doc

: .

粒子群优化算法［45］最原始的工作可以追溯到1987年Reyn olds对鸟群社会系 统Boids（ Reynolds对其仿真鸟群系统的命名）的仿真研究 。通常，群体的行为 可以由几条简单的规则进行建模，虽然每个个体具有简单的行为规则，但是却群 体的行为却是非常的复杂，所以他们在鸟类仿真中，即 Boids系统中采取了下面 的三条简单的规则：
（1） 飞离最近的个体（鸟），避免与其发生碰撞冲突；
（2） 尽量使自己与周围的鸟保持速度一致；
（3） 尽量试图向自己认为的群体中心靠近。
虽然只有三条规则，但Boids系统已经表现出非常逼真的群体聚集行为。但 Rey nolds仅仅实现了该仿真，并无实用价值。
1995年Kenn edy46-48］和Eberhart在Reyn olds等人的研究基础上创造性地提
出了粒子群优化算法，应用于连续空间的优化计算中 。Kennedy和Eberhart在
boids中加入了一个特定点，定义为食物，每只鸟根据周围鸟的觅食行为来搜寻 食物。Kennedy和Eberhart的初衷是希望模拟研究鸟群觅食行为，但试验结果却 显示这个仿真模型蕴含着很强的优化能力， 尤其是在多维空间中的寻优。最初仿
真的时候，每只鸟在计算机屏幕上显示为一个点，而“点”在数学领域具有多种 意义，于是作者用“粒子（particle）”来称呼每个个体，这样就产生了基本的粒 子群优化算法［49］。
假设在一个D维搜索空间中，有m个粒子组成一粒子群，其中第i个粒子 的空间位置为Xi = （X1,Xi2,Xi3,..., XiD ） i=1,2,…，m，它是优化问题的一个潜在解， 将它带入优化目标函数可以计算出其相应的适应值，根据适应值可衡量 人的优
劣；第i个粒子所经历的最好位置称为其个体历史最好位置，记为 P =（Pi1,Pi2,Pi3,…，Bd） i =1,2,...,m，相应的适应值为个体最好适应值 Fi ;同时，
每个粒子还具有各自的飞行速度 V^ （vi1,vi2,vi3,..., viD） i =1,2,..., m。所有粒子经 历过的位置中的最好位置称为全局历史最好位置，记为
Pg =(Pgi,Pg2,Pg3,…，Pg°),相应的适应值为全局历史最优适应值 。在基本pso
算法中，对第n代粒子，其第d维(K d< D )元素速度、位置更新迭代如式(4-1)、
(4-2):
(4-1)
(4-2)
n1 n nn nn、
Vd =国汉Vid +G>;r1x(Pd —Xid)+C2><r2x(Pgd —Xid)
n 1 n n xid = xid vid
其中：3为惯性权值；c1和c2都为正常数，称为加速系数；r1和r2是两 个在［0, 1］范围内变化的随机数。第 d维粒子元素的位置变化范围和速度变化范 围分别限制为 Xd ,min , Xd ,max I 和 Vd ,min , Vd ,max 。迭代过程中，若某一维粒子元素 的Xid或Vid超出边界值则令其等于边界值。
粒子群速度更新公式(4-1)中的第1部分由粒子先前速度的惯性引起，为“惯 性”部分；第2部分为“认知”部分，表示粒子本身的思考，即粒子根据自身 历史经验信息对自己下一步行为的影响；第 3部分为“社会”部分，表示粒子
之间的信息共享和相互合作，即群体信息对粒子下一步行为的影响。
基本PSO算法步骤如下：
(1) 粒子群初始化；
(2) 根据目标函数计算各粒子适应度值，并初始化个体、全局最优值；
(3) 判断是否满足终止条件，是则搜索停止，输出搜索结果；否则继续下
步；
(4) 根据速度、位置更新公式更新各粒子的速度和位置；
(5) 根据目标函数计算各粒子适应度值；
(6) 更新各粒子历史最优值以及全局最优值；
(7) 跳转至步骤3。
对于终止条件，通常可以设置为适应值误差达到预设要求， 或迭代次数超过
最大允许迭代次数。
基本的连续PSO算法中，其主要参数，即惯性权值、加速系数、种群规模 和迭代次数对算法的性能均有不同程度的影响 。
惯性权值3的取值对PSO算法的收敛性能至关重要。在最初的基本粒子群 算法中没有惯性权值这一参数 。最初的PSO算法容易陷入局部最小，于是在 其后的研究中引入了惯性权值来改善 PSO 算法的局部搜索能力，形成了目前常 用的基本PSO算法形式。取较大的3值使得粒子能更好地保留速度，从而能更 快地搜索解空间， 提高算法的收敛速度； 但同时由于速度大可能导致算法无法更 好地进行局部搜索