文档视界

最新最全的文档下载
当前位置:文档视界 > 粒子群优化算法及其应用

粒子群优化算法及其应用

2006年第1期信息技术 In formation T echnology 中图分类号:TP391.9 文献标识码:A 文章编号:1009-2552(2006)01-0053-04

粒子群优化算法及其应用

范 娜,云庆夏

(西安建筑科技大学管理科学与工程学院,西安710055)

摘 要:粒子群优化(PS O)算法是一种新颖的演化算法,它属于一类随机全局优化技术,PS O 算法通过粒子间的相互作用在复杂搜索空间中发现最优区域。PS O的优势在于简单而又功能强大。介绍了基本的PS O算法、研究现状及其应用,并讨论将来可能的研究内容。

关键词:粒子群优化算法;演化算法;群体智能

P article sw arm optimization algorithms and its applications

FAN Na,Y UN Qing2xia

(College o f M anagem ent Science and E ngineering,X i’an U niversity o f A rchitecture&T ech nology,X i’an710055,China)

Abstract:particle swarm optimization(PS O)alg orithm is a novel ev olutionary alg orithm.It is a kind of sto2 chastic global optimization technique.PS O finds optimal regions of com plex search spaces through the interac2 tion of individuals in a population of particles.The advantages of PS O lie in sim ple and powerful function.In this paper,classical particle swarm optimization alg orithm,the present condition and s ome applications of the alg orithms are introduced,and the possible research contents in future are als o discussed.

K ey w ords:particle swarm optimization alg orithms;ev olutionary alg orithms;swarm intelligence

0 引言

从20世纪90年代初,就产生了模拟自然生物群体(swarm)行为的优化技术。Dorig o等人从生物进化的机理中受到启发,通过模拟蚂蚁的寻径行为,提出了蚁群优化方法;美国学者Eberhart E C和K ennedy J于1995年提出的粒子群优化(particle swarm optimization)算法是基于对鸟群、鱼群的模拟[1]。这些研究可以称为群体智能(swarm intelli2 gence)。通常单个自然生物并不是智能的,但是整个生物群体却表现出处理复杂问题的能力,群体智能就是这些团体行为在人工智能问题中的应用。粒子群优化(PS O)最初是处理连续优化问题的,目前其应用已扩展到组合优化问题[2]。

同遗传算法(genetic alg orithm,G A)、蚁群优化等大多数进化计算方法一样,PS O也是一种基于群体的优化方法。但与其它进化计算方法相比,PS O的主要特点为:①每一个体(称为一个粒子)都被赋予了一个随机速度并在整个问题空间中流动;②个体具有记忆功能;③个体的进化主要是通过个体之间的合作与竞争来实现的。作为一种高效并行优化方法,PS O可用于求解大量非线性、不可微和多峰值的复杂优化问题,再加上PS O算法的程序实现异常简洁,需要调整的参数少,因而发展很快,出现了多种改进PS O算法,并已应用于许多科学和工程领域,得到了众多学者的重视和研究。

1 粒子群优化算法介绍

1.1 算法原理

PS O算法不像遗传算法那样对个体进行选择、交叉和变异操作,而是将群体中的每个个体视为多维搜索空间中一个没有质量和体积的粒子(点),这些粒子在搜索空间中以一定的速度飞行,并根据粒子本身的飞行经验以及同伴的飞行经验对自己的飞行速度进行动态调整,即每个粒子通过统计迭代过程中自身的最优值和群体的最优值来不断地修正自己的前进方向和速度大小,从而形成群体寻优的正

收稿日期:2005-05-23

作者简介:范娜,女,硕士研究生,研究方向为优化技术。

反馈机制。PS O算法就是这样依据每个粒子对环境的适应度将个体逐步移到较优的区域,并最终搜索、寻找到问题的最优解。PS O算法具有鲜明的生物社会背景:认知行为和社会行为,即在寻求一致的认知过程中,个体往往记住它们的信念,同时考虑其它同伴的信念,当个体察觉同伴的信念较好时,将进行适应性调整。

在PS O算法中,用粒子的位置表示待优化问题的解,每个粒子性能的优劣程度取决于待优化问题目标函数确定的适应值,每个粒子由一个速度矢量决定其飞行方向和速率大小。设在一个d维的目标搜索空间中,有m个粒子组成一个群体,其中,在第t次迭代时粒子i的位置表示为X i(t)=(x i1(t), x i2(t),…,x id(t)),相应的飞行速度表示为V i(t)=

(v

i2(t),v

i2

(t),…,v id(t))。开始执行PS O算法时,首

先随机初始化m个粒子的位置和速度,然后通过迭代寻找最优解,在每一次迭代中,粒子通过跟踪两个极值来更新自己的速度和位置:一个极值是粒子本身迄今搜索到的最优解,称为个体极值,表示为P i(t)=(p i1(t),p i2(t),…,p id(t));另一个极值是整个粒子群到目前为止找到的最优解,称为全局极值,表

示为P

g (t)=(p

g1

(t),p

g2

(t),…,p gd(t))。在第t+1

次迭代计算时,粒子i根据下列规则来更新自己的速度和位置:

V ik(t+l)=ωνik(t)+c1randl(p ik(t)-

x

ik (t))+c

2

rand2(p gk(t)-x ik(t))(1)

X ik(t+l)=x ik(t)+νik(t+l)(2)

式中ω为惯性权重,ω取大值可使算法具有较强的全局搜索能力,ω取小值则算法倾向于局部搜索。一般的做法是将ω初始取0.9并使其随迭代次数的增加而线性递减至0.4,这样就可以先侧重于全局搜索,使搜索空间快速收敛于某一区域,然后采用局部精细搜索以获得高精度的解;c

1

,c2:为两个学习因子,一般取为2;randl和rand2为两个均匀分布在(0,l)之间的随机数;i=1,2,…,m;k=1,2,…,d。

另外,粒子在每一维的速度V

i都被一个最大速度V max所限制。如果当前粒子的加速度导致它在某一维的速度超过该维上的最大速度Vmax,则该维的速度被限制为最大速度。式(1)中第1部分可理解为粒子先前的速度或惯性;第2部份可理解为粒子的“认知”行为,表示粒子本身的思考能力;第3部分可理解为粒子的“社会”行为,表示粒子之间的信息共享与相互合作。

1.2 算法流程

标准PS O算法流程[2]如下:

(1)随机初始化粒子群体的位置和速度。通常是在允许的范围内随机产生的,每个粒子的pbest坐标设置为其当前位置,且计算出其相应的个体极值(即个体的适应度值),而全局极值(即全局的适应度值)就是个体极值中最好的,记录该最好值的粒子序号,并将gbest设置为该最好粒子的当前位置。

(2)计算每个粒子的适应值。

(3)对每个粒子,将其适应值与个体极值进行比较,如果较优,则更新当前的个体极值。

(4)对每个粒子,将其适应值与全局极值进行比较,如果较优,则更新当前的全局极值。

(5)根据式(1)、(2),更新每个粒子的位置和飞行速度。

(6)如未达到预先设定的停止准则(通常设置为最大迭代次数),则返回步骤2,若达到则停止计算。PS O算法可用伪代码表示如下:

初始化粒子群;

DO

F or每个粒子

计算其适应度;

I f(适应度优于粒子历史最佳值)

用X

i更新历史最佳个体P i;

End

选取当前粒子群中最佳粒子;

I f(当前最佳粒子优于群历史最佳粒子)

用当前群最佳粒子更新P

g

;

F or每个粒子

按式(1)更新粒子速度;

按式(2)更新粒子位置;

End

While最大迭代数未达到或最小误差未达到。

粒子群优化算法框架图见图1。

2 粒子群优化算法的研究现状

受到人工生命研究结果的启发,粒子群算法(PS O)的基本概念源于对鸟群和鱼群捕食行为的社会模型的模拟。由于PS O算法概念简单,实现容易,短短几年时间,PS O算法便获得了很大的发展,出现了很多改进PS O算法,并且已经应用于多个科学和工程领域。目前已被“国际演化计算会议”(CEC)列为讨论专题之一。但由于PS O算法建立在

图1 粒子群优化算法框架图

对社会模型仿真的基础上,因而在方法提出初期并没有严格的数学基础,随着Clerc M和Bergh Van den 等人研究成果的公开发表,PS O算法的严格数学基础正在逐步建立。

基本PS O算法是函数优化的有力工具,其优点是收敛速度快且需设置的参数较少;其缺点是易陷入局部极小点,且搜索精度不高。据此当前典型的改进算法有:自适应PS O算法、模糊PS O算法、杂交PS O 算法、混合粒子算法(HPS O)、离散PS O算法等等。

其中自适应和模糊PS O算法是Eberhart Shi研究了惯性因子ω对优化性能的影响:发现较大的ω值有利于跳出局部极小点,较小的ω值有利于算法的收敛。自适应PS O算法通过线性地减小ω值动态的调整参数ω,而模糊PS O算法则在此基础上利用模糊规则动态调整参数ω的值,即构造一个2输入、1输出的模糊推理机来动态地修改惯性因子ω。模糊推理机的两个输入分别是当前ω值,以及其适应度;而输出是ω的增量。

杂交和混合粒子算法(HPS O)是受遗传算法、自然选择机制的启示,将遗传算子与基本PS O相结合而得。其中,混合PS O算法是将基本PS O算法和选择机制相结合而成,基本PS O算法的搜索过程很大程度上依赖pbest和gbest,它的搜索区域受到pbest 和gbest的限制。在通常的遗传算法中,选择机制用来选择相对较好的区域和淘汰较差的区域,可以更

合理地分配有限的资源。杂交PS O在基本PS O中引入了杂交算子,两者均取得了满意的结果,改善了算法的性能。

离散二进制版PS O算法是用来解决工程实际中的组合优化问题。Eberhart R A等在提出的模型中将每一维x

id和pbest id限制为1或者为0,而速度v id不作这种限制。用速度来更新位置时,如果v id高

一些,粒子的位置x

id更有可能选1,v id低一点则选0,阈值在[0,1]之间。而有这种特点的函数就是Sig m oid函数:

sig(V k id)=lΠ(l+exp(-V k id))

二进制版本PS O的公式为

ifρk+1

id

id

then X k+1

id

=1;

else X k+1

id

=0

向量ρk+1

id的各个分量是[0,1]之间的随机数。

为了防止Sig m oid函数饱和,可以将V k

id钳位在[-4.0,+4.0]之间。二进制PS O其他部分与基本连续PS O类似。实验结果显示,在大多数测试函数中,二进制PS O都比遗传算法速度快,尤其在问题的维数增加时。

基本PS O算法是求解连续函数优化的有力工具,但对离散问题却无能为力。因此K enndy J和Eberhart R A又提出了离散型PS O算法,用于解决组合优化问题等,它在一定程度上完善发展了基本PS O算法,并将其应用于旅行商问题(TSP)的求解,取得了较好的结果。离散PS O算法扩展了基本PS O 算法的应用领域,让人看到了PS O在组合优化问题中的应用前景。

3 粒子群优化的应用

PS O的优势在于算法的简洁性,易于实现,没有很多参数需要调整,且不需要梯度信息。PS O是非线性连续优化问题、组合优化问题和混合整数非线性优化问题的有效优化工具[2]。目前已经广泛应用于函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用领域。PS O最初应用到神经网络训练上在随后的应用中,PS O又可以用来确定神经网络的结构。文献[5]中用改进的速度更新方程训练模糊神经网络。Pars opoulos等将PS O用于解决多目标优化问题、最小最大化问题、整数规划问题和定位所有全局极值等问题。

一般说来,PS O比较有潜力的应用包括系统设

粒子群优化算法及其应用

计、多目标优化、分类、模式识别、调度、信号处理、决策、机器人应用等。其中具体应用实例有:模糊控制器设计、车间作业调度、机器人实时路径规划、自动目标检测、时频分析等[3]。总之,PS O算法的应用十分广泛,它有着比较好的发展前景,值得做进一步的研究。

4 未来的研究

PS O算法是一个新的基于群体智能的进化算法,其研究刚刚开始,远没有像遗传算法和模拟退火算法那样形成系统的分析方法和一定的数学基础,有许多问题还需要进一步研究。

(1)适用范围。PS O算法应用得最成功的是在进化神经网络方面,其它的一些应用许多还停留在研究阶段。显然,PS O算法不会仅仅局限于目前的这些领域,如果将PS O算法引入机器学习、自动控制等领域,将大大地促进算法的研究与发展。

(2)参数的选择与设计。PS O算法中参数的选择依赖于具体问题,设计合适的参数需要经过多次试验。研究如何选择和设计参数,使其减少对具体问题的依赖,也将大大促进PS O算法的发展和应用。

5 结束语

粒子群优化算法是一种新兴的有潜力的演化算法,在实际应用中被证明是有效的,但还存在一些问题,在给出其收敛性、收敛速度估计等方面的数学证明还没有,其理论和数学基础的研究还不够。PS O 在理论上并不能保证能够得到最优解。PS O算法在进行优化问题的求解时应用范围有限,尤其对离散的组合优化问题,其理论建模还处于起步阶段。PS O算法中的一些参数如学习因子c1,c2,惯性权重ω,以及粒子个数往往根据有限的应用经验确定,并不具有广泛的适应性。因此将PS O与进化算法、模糊系统、神经网络以及一些优化技术结合,根据不同的优化问题建立相应的PS O模型是PS O算法当前的研究重点。

目前我国已有学者开始了对PS O算法的研究[4],希望PS O可以为优化研究工作带来更多的新思路。

参考文献:

[1] K ennedy J,Eberhart R C.Particle S warm Optlmization.Proc.[R].

IEEE Int,Lcon f.on Neural Netw orks.IE BE Service Center,Pisca2

taway,N J,1995(4):1942-1948.

[2] Fukuyama Y.Fundamentals of Particle S warm T echiques[A],Lee K

Y,E l-Sharkawi M A,M odern Heuristic Optimization T echniques W ith

Applications to P ower Systems[C].IEEE P ower Engineering S ociety,

2002:45-51.

[3] Eberhart R C,Shi Y.Particle S warm Optimization:Developments,Ap2

plications and Res ources[A].Proceedings of the IEEE C ongress on

Ev olutionary C om putation[C].Piscataway,N J:IEEE Service Center,

2001:81-86.

[4] 徐海,刘石,马勇,等1基于改进粒子群游优化的模糊逻辑系统

自学习算法[J].计算机工程与应用,2000(7):62-63.

[5] He Z,W ei C,Y ang L,et al.Extracting Rules from Fuzzy Neural Net2

w ork by Particle S warm Optimization[A].proceedings of IEEE C on2

gress on Ev olutionary C om putation[C].Anchorage,Alaska,US A

粒子群优化算法及其应用

,

1998:74-77.

责任编辑:杨立民(上接第52页)进行累加,所得到的和就是y(n+1)。

整个算法的实现可参看以下的流程图如图4所示。

图4 程序流程图

3 结论

文章讨论了数字滤波器的DSP实现,对于基于

DSP采样信号的数字滤波具有参考意义。运用Mat2

lab可以方便的设计出符合要求的数字滤波器。用

定点的DSP实现滤波器要考虑定标、循环寻址等关

键问题。本文所介绍的是FIR滤波器的定点DSP实

现,但其思想对IIR滤波器和在其他浮点DSP上的

实现同样具有参考意义。

参考文献:

[1] 宗孔德,胡广书.数字信号处理[M].北京:清华大学出版社,

1988.

[2] 刘彤.用DSP实现FIR数字滤波器[J].无线通信技术,2000

(2):53-56.

[3] 刘和平,等.T MS320LF240x DSP C语言开发应用[M].北京:北

京航空航天大学出版社,2003.

[4] 董长虹.M atlab信号处理与应用[M].北京:国防工业出版社,

2005.

责任编辑:杨立民