百度文库-张曦元
的启发。他们的模型和仿真算法主要对Frank Heppner的模型进行了修正，以使粒子飞向解空间并在最好解处降落。Kennedy在他的书中描述了粒子群算法思想的起源。自20世纪30年代以来，社会心理学的发展揭示：我们都是鱼群或鸟群聚集行为的遵循者。在人们的不断交互过程中，由于相互的影响和模仿，他们总会变得更相似，结果就形成了规范和文明。人类的自然行为和鱼群及鸟群并不类似，而人类在高维认知空间中的思维轨迹却与之非常类似。思维背后的社会现象远比鱼群和鸟群聚集过程中的优美动作复杂的多：首先，思维发生在信念空间，其维数远远高于3；其次，当两种思想在认知空间会聚于同一点时，我们称其一致，而不是发生冲突。
2.2 算法原理
PSO从这种模型中得到启示并用于解决优化问题。PSO 中，每个优化问题的潜在解都是搜索空间中的一只鸟，称之为粒子。所有的粒子都有一个由被优化的函数决定的适值( fitness value) ，每个粒子还有一个速度决定它们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索[1]。
PSO初始化为一群随机粒子(随机解)，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己；第一个就是粒子本身所找到的最优解，这个解称为个体极值；另一个极值是整个种群目前找到的最优解，这个极值是全局极值。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。
假设在一个D维的目标搜索空间中，有N个粒子组成一个群落，其中第i个粒子表示为一个D维的向量
Xi?(xi1,xi2,?,xiD)，i?1,2,?,N。
第i个粒子的“飞行 ”速度也是一个D维的向量，记为
Vi?（vi1,vi2，?,viD)，i?1,2,?3。
第i个粒子迄今为止搜索到的最优位置称为个体极值，记为
pbest?(pi1,pi2,?,piD)，i?1,2,?,N。
整个粒子群迄今为止搜索到的最优位置为全局极值，记为
gbest?(pg1,pg2,?,pgD)
4
百度文库-张曦元
在找到这两个最优值时，粒子根据如下的公式(2.1)和( 2.2)来更新自己的速度和位置[12]：
vid?w?vid?c1r1?pid?xid??c2r2(pgd?xid) (2.1)
xid?xid?vid (2. 2)
其中：c1和c2为学习因子，也称加速常数(acceleration constant)，r1和r2为[0，1]范围内的均匀随机数。式(2.1)右边由三部分组成，第一部分为―惯性(inertia)‖或―动量(momentum)‖部分，反映了粒子的运动―习惯(habit)‖，代表粒子有维持自己先前速度的趋势；第二部分为―认知(cognition)‖部分，反映了粒子对自身历史经验的记忆(memory)或回忆(remembrance)，代表粒子有向自身历史最佳位置逼近的趋势；第三部分为―社会(social)‖部分，反映了粒子间协同合作与知识共享的群体历史经验，代表粒子有向群体或邻域历史最佳位置逼近的趋势，根据经验，通常c1?c2?2。i?1,2,?,D。vid是粒子的速度，vid?[?vmax,vmax]，vmax是常数，由用户设定用来限制粒子的速度。r1和r2是介于[0,1]之间的随机数[2][5]。
2.3 基本粒子群算法流程
算法的流程如下：
① 初始化粒子群，包括群体规模N，每个粒子的位置xi和速度Vi ② 计算每个粒子的适应度值Fit[i]；
③ 对每个粒子，用它的适应度值Fit[i]和个体极值pbest比较，如果（i）； Fit[i]?pbest(i) ，则用Fit[i]替换掉pbest（i）④ 对每个粒子，用它的适应度值Fit[i]和全局极值gbest比较，如果
Fit[i]?pbes(ti)则用Fit[i]替gbest；
⑤ 根据公式（2.1），（2.2）更新粒子的速度vi和位置xi ；
⑥ 如果满足结束条件(误差足够好或到达最大循环次数)退出，否则返回②。
5
百度文库-张曦元
开 始 初始化每个粒子的速度和位置 计算每个粒子的适应值 求出每个粒子的个体最优 求出整个群体的全局最优值 根据方程(2.1)对粒子的速度进行进化 根据方程(2.2)对粒子的位置进行进化 否 是否满足结束条件 是 输出结果
图2.1. PSO算法流程图
2.4 特点
1、式(2.1)中第1部分可理解为粒子先前的速度或惯性；第2部份可理解为粒子的“认知”行为，表示粒子本身的思考能力；第3部分可理解为粒子的“社会”行为，表示粒子之间的信息共享与相互合作。公式(2.2) 表示了粒子在求解空间中，由于相互影响导致的运动位置调整。整个求解过程中，惯性权重w、加速因子c1和
c2和最大速度vmax共同维护粒子对全局和局部搜索能力的平衡。
6
百度文库-张曦元
2、粒子群优化算法初期，其解群随进化代数表现了更强的随机性，正是由于其产生了下一代解群的较大的随机性，以及每代所有解的“信息”的共享性和各个解的“自我素质”的提高。
3、PSO 的一个优势就是采用实数编码，不需要像遗传算法一样采用二进制编
22码(或者采用针对实数的遗传操作) 。例如对于问题f?x12?x2求解， 粒子可?x3以直接编码为(x1,x2,x3) ，而适应度函数就是f(x) 。
4、粒子具有“记(x1,x2,x3)忆”的特性，它们通过“自我”学习和向“他人”学习，使其下一代解有针对性的从“先辈”那里继承更多的信息，从而能在较短的时间内找到最优解。
5、与遗传算法相比，粒子群优化算法的信息共享机制是很不同的:在遗传算法中，染色体互相共享信息，所以整个种群的移动是比较均匀的向最优区域移动;在粒子群优化算法中，信息流动是单向的，即只有gbest将信息给其他的粒子，这使得整个搜索更新过程跟随当前解。
2.5 带惯性权重的粒子群算法
探索是偏离原来的寻优轨迹去寻找一个更好的解，探索能力是一个算法的全局搜索能力。开发是利用一个好的解，继续原来的寻优轨迹去搜索更好的解，它是算法的局部搜索能力。如何确定局部搜索能力和全局搜索能力的比例，对一个问题的求解过程很重要。1998年，Yuhui Shi[9]提出了带有惯性权重的改进粒子群算法。其进化过程为：
vij(t?1)?wvij(t)?c1r1(t)(pij(t)?xij(t))?c2r2(t)(pgi(t)?xij(t)) （2.3）
xij(t?1)?xij(t)?vij(t?1) （2.4）
在式(2.1)中，第一部分表示粒子先前的速度，用于保证算法的全局收敛性能；第二部分、第三部分则是使算法具有局部收敛能力。可以看出，式（2.3)中惯性权重w表示在多大程度上保留原来的速度。w较大，全局收敛能力强，局部收敛能力弱；w较小，局部收敛能力强，全局收敛能力弱。
当w?1时，式(2.3)与式(2.1)完全一样，表明带惯性权重的粒子群算法是基本粒子群算法的扩展。实验结果表明，w在[0.8?1.2]之间时，PSO算法有更快的收
7
百度文库-张曦元
敛速度，而当w?1.2时，算法则易陷入局部极值。
2.7 粒子群算法的研究现状
在算法的理论研究方面。目前PSO算法还没有成熟的理论分析，少部分研究者对算法的收敛性进行了分析，大部分研究者在算法的结构和性能改善方面进行研究，包括参数分析，拓扑结构，粒子多样性保持，算法融合和性能比较等。PSO由于有简单、易于实现、设置参数少、无需梯度信息等特点，其在连续非线性优化问题和组合优化问题中都表现出良好的效果。
8