一种更简化而高效的粒子群优化算法_胡旺

Journal of Software, Vol.18, No.4, April 2007, pp.861−868 http://www.jos.org.cn DOI: 10.1360/jos180861 Tel/Fax: +86-10-62562563 © 2007 by Journal of Software. All rights reserved.

一种更简化而高效的粒子群优化算法

胡 旺+, 李志蜀 (四川大学 计算机学院,四川 成都 610065)

∗

A Simpler and More Effective Particle Swarm Optimization Algorithm

HU Wang+, LI Zhi-Shu

(School of Computer Science and Engineering, Sichuan University, Chengdu 610065, China)

+ Corresponding author: Phn: +86-28-866988, E-mail: scuhuwang@126.com, http://www.scu.edu.cn

Hu W, Li ZS. A simpler and more effective particle swarm optimization algorithm. Journal of Software, 2007, 18(4):861−868. http://www.jos.org.cn/1000-9825/18/861.htm

Abstract: The basic particle swarm optimization (bPSO) has some demerits, such as relapsing into local extremum, slow convergence velocity and low convergence precision in the late evolutionary. Three algorithms, based on the simple evolutionary equations and the extrenum disturbed arithmetic operators, are proposed to overcome the demerits of the bPSO. The simple PSO (sPSO) discards the particle velocity and reduces the bPSO from the second order to the first order difference equation. The evolutionary process is only controlled by the variables of the particles position. The extremum disturbed PSO (tPSO) accelerates the particles to overstep the local extremum. The experiment results of some classic benchmark functions show that the sPSO improves extraordinarily the convergence velocity and precision in the evolutionary optimization, and the tPSO can effectively break away from the local extremum. tsPSO, combined the sPSO and tPSO, can obtain the splendiferous optimization results with smaller population size and evolution generations. The algorithms improve the practicality of the particle swarm optimization.

Key words: evolutionary computation; swarm intelligence; particle swarm optimization; disturbed extremum 摘 要: 针对基本粒子群优化(basic particle swarm optimization,简称bPSO)算法容易陷入局部极值、进化后期的收敛速度慢和精度低等缺点,采用简化粒子群优化方程和添加极值扰动算子两种策略加以改进,提出了简化粒子群优化(simple particle swarm optimization,简称sPSO)算法、带极值扰动粒子群优化(extremum disturbed particle swarm optimization,简称tPSO)算法和基于二者的带极值扰动的简化粒子群优化(extremum disturbed and simple particle swarm optimization,简称tsPSO)算法.sPSO去掉了PSO进化方程的粒子速度项而使原来的二阶微分方程简化为一阶微分方程,仅由粒子位置控制进化过程,避免了由粒子速度项引起的粒子发散而导致后期收敛变慢和精度低问题.tPSO增加极值扰动算子可以加快粒子跳出局部极值点而继续优化.对几个经典测试函数进行实验的结果表明,sPSO能够极大地提高收敛速度和精度;tPSO能够有效摆脱局部极值点;以上两种策略相结合,tsPSO以更小的种群数和进化世代数获得了非常好的优化效果,从而使得PSO算法更加实用化. 关键词: 进化计算;群体智能;粒子群优化;极值扰动 中图法分类号: TP18 文献标识码: A ∗ Received 2005-11-23; Accepted 2006-04-03

862

Journal of Software 软件学报 Vol.18, No.4, April 2007

由Eberhart和Kennedy于1995年提出的粒子群优化算法(particle swarm optimization,简称PSO)[1]是一种全局优化进化算法,它源于对鸟群和鱼群群体觅食运动行为的模拟.PSO作为一种并行优化算法,可以用于解决大量非线性、不可微和多峰值的复杂问题优化,并已广泛用于科学和工程领域,如函数优化、神经网络训练、模式分类和模糊系统控制等领域.

与遗传算法类似,粒子群优化算法同样基于群体与适应度这两个概念.粒子群的个体代表问题的一个可能解.每个粒子具有位置与速度两个描述量,粒子位置坐标对应的目标函数值即可作为该粒子的适应度,PSO算法通过适应度来衡量粒子的优劣.与遗传算法不同,PSO不是通过遗传算子进化而是通过个体间协作与竞争来寻找最优解.PSO在进化初期,收敛速度快,运算简单,易于实现,没有遗传算法的编解码和选择、杂交、变异等复杂运算.因此,粒子群优化算法一经提出,立刻引起演化计算领域学者们的广泛关注,并出现了大量的研究成果.

但是,粒子群优化算法根据全体粒子和自身粒子的搜索经验向着最优解的方向发展,在进化后期收敛速度变慢,同时,算法收敛精度不高,尤其是对于高维多极值的复杂优化问题.本文通过简化基本粒子群(basic particle swarm optimization,简称bPSO)的进化方程和添加极值扰动算子两个改进策略,提出了简化粒子群优化(simple particle swarm optimization,简称sPSO)算法、带极值扰动的粒子群优化(extremum disturbed particle swarm optimization,简称tPSO)算法和基于前二者的带极值扰动的简化粒子群优化(extremum disturbed and simple particle swarm optimization,简称tsPSO)算法.

1 基本粒子群算法及相关改进

bPSO算法首先初始化一群随机粒子,然后通过迭代找到最优解.在每一次迭代中,粒子通过跟踪两个“极值”来更新自己:个体极值和全局极值.粒子根据上述两个极值更新自己的速度与位置.在D维目标搜索空间中,由种群数为m组成粒子群落,其中:第i个粒子在第d维的位置为xid,其飞行速度为vid,该粒子当前搜索到的最优位置为Pid,整个粒子群当前的最优位置为Pgd. Kennedy和Eberhart[1]最早提出的bPSO算法公式如下:

t+1tvid=vid+c1r1(pid−xid)+c2r2(pgd−xid) (1)

t+1tt+1

xid=xid+vid (2)

其中:i=1,2,…,m;d=1,2,…,D;r1和r2是服从U(0,1)分布的随机数;学习因子c1和c2为非负常数,通常取c1=c2=2;

vid∈[−vmax,vmax],vmax是由用户设定的常数.迭代终止条件为预设的最大迭代次数或(和)预定的最小适应度阈值.

因为Pgd为整个粒子群的最优位置,因此,上述算法也被称为全局版PSO.也可以把第i个粒子的部分邻居们搜索到的最优位置作为Pgd,则相应算法称为局部版PSO.全局版PSO收敛速度快,但有时会陷入局部最优;局部版PSO收敛速度相对较慢,但相对不易陷入局部最优值.

Shi[2]等人通过对式(1)添加动量惯性系数ω来提高跳出局部极值能力.修改后的方程如下:

Clerc[3]等人对式(2)添加控制速度的约束因子α:

t+1t

vid=ωvid+c1r1(pid−xid)+c2r2(pgd−xid) (3)

t+1tt+1

xid=xid+αvid (4)

很多学者将式(3)、式(4)视为bPSO算法.文献[4]采用模糊规则动态修改ω值,使算法自适应地调整全局系数,兼顾了搜索效率和搜索精度.但对许多复杂的非线性优化问题,试图通过自适应调整一个全局系数提高搜索精度的余地是有限的.Angeline[5]等人借鉴遗传算法思想提出杂交PSO算法概念,提高了算法的收敛速度和精度.吕振肃[6]等人根据粒子群适应度方差作为全局最优化变异条件,提出自适应变异的粒子群优化算法.Van de Bergh[7]提出了协同PSO,使粒子更容易跳出局部极小点,达到较高收敛精度,但出现了明显的“启动延迟现象”,

在迭代初期减缓了收敛速度.Ratnaweera等人[8]在自组织算法的基础上给出了一种变异操作随时间变化的自适应层次PSO算法(hierarchical particle swarm optimizer,简称HPSO),以进一步提高搜索性能,并给出了适合变异操作的自适应参数选择方式.但是,HPSO算法消除了速度公式中的惯性部分,其发生变异的条件是微粒速度为0,使微粒不能快速、有效地逃出局部极小点.赫然等人[9]结合生物界中物种发现生存密度过大时会自动分家迁

移的习性,给出了一种自适应逃逸微粒群算法,通过逃逸运动,使微粒能够有效地进行全局和局部搜索,减弱了

胡旺 等:一种更简化而高效的粒子群优化算法

863

随机变异操作带来的不稳定性.但是,上述研究都是对基本粒子群方程(1)、方程(2)或方程(3)、方程(4)的改进.

2 简化粒子群优化算法

2.1 关于bPSO中粒子速度项的分析

迄今为止,bPSO及其改进算法都是基于粒子“位置”和“速度”这两个关键概念,从而在进化方程中都包含位置变量和速度变量,大多数的PSO改进算法增加了一些操作算子,如杂交、变异、自适应参数变化等,使得PSO算法描述越来越复杂化,同时,也使得定量分析PSO的收敛性变得很繁琐[10−12].

仔细分析bPSO的生物模型和进化迭代方程式(3)和方程式(4)可以发现:在PSO中,粒子速度概念不是必 需的.

从bPSO模型角度来看,粒子位置xi代表当前问题的解,优化的最终结果是使xi无限逼近最优解X*,因此,只需要考虑xi的直接变化.粒子速度vi代表粒子移动的快慢程度,粒子移动速度的大小并不代表粒子能够有效趋近最优解位置,反而可能造成粒子偏离正确的进化方向,出现粒子“发散”现象,从而有可能造成后期收敛缓慢,收敛精度低.另外,从式(1)~式(4)来看,位置与速度直接进行加法运算,而没有粒子运动时间概念,这也不符合现实生活中的运动规律x=vt.

定理1. bPSO进化过程与粒子速度无关.

证明:文献[3]已经证明,约束粒子速度范围vid∈[−vmax,vmax]与添加约束因子α是等价的,因此,可以只考虑由式(3)与式(2)组成的联合进化方程.除pid和pgd对搜索空间各维的联系以外,每维的更新相互.故不失一般性,证明过程可以简化到一维进行,下标d可以省略.进一步地,假设种群中除第i个粒子外其余粒子保持不动,下

ϕ1p0+ϕ2pg

.为方便理解,将式(3)和式(2)中变量符的上标移到标I可以省略.再令ϕ1=r1c1,ϕ2=r2c2,ϕ=ϕ1+ϕ2,ρ=

ϕ1+ϕ2变量符后的括号中,则式(3)和式(2)可以变为

将式(5)和式(6)迭代可以得到式(7):

v(t+1)=ωv(t)+ϕ(ρ−x(t)) (5)

x(t+1)=x(t)+v(t+1) (6)

x(t+2)+(ϕ−w−1)x(t+1)+ωx(t)=ϕρ

(7)

式(7)是不含速度项的经典二阶微分方程(假设粒子的位置移动为连续过程). 子的收敛速度和收敛精度. 2.2 简化粒子群优化算法(sPSO)

根据第2.1节中的分析,不含速度项的粒子群优化方程可以简化为

□

定理1的重要性在于说明bPSO算法可以没有粒子速度的概念,避免了人为确定参数[−vmax,vmax]而影响粒

t+1ttt

)+c2r2(pgd−xid) (8) xid=ωxid+c1r1(pid−xid

式(8)右边的第1项为“历史(history)”部分,表示过去对现在的影响,通过ω调节影响程度;第2项为“认知(cognition)”部分,表示粒子对自身的思考;第3项为“社会(social)”部分,表示与邻居粒子的比较和模仿,实现粒子

间的信息共享与合作.

采用第2.1节中的符号含义,式(8)可以变形为一阶微分方程:

阶,简化了分析和控制粒子的进化过程. 2.3 sPSO进化方程的收敛性能分析

x(t+1)+(ϕ−ω)x(t)=ϕρ (9)

由式(7)和式(9)的比较可知:改写后的sPSO进化方程不仅没有粒子速度参数,而且方程也由二阶降到了一

定理2. 若sPSO的平均行为按其期望值进行观察,当0<ω<

c1p0+c2pgc1+c2

时,sPSO收敛于. 2c1+c2−2ω

8

证明:式(9)的微分方程解为x(t)=Ce(ω−ρ)t−敛于limx(t)=

t→∞

Journal of Software 软件学报 Vol.18, No.4, April 2007

ϕρx(t+1)

,要使limx(t)收敛,则lim<1,解得0<ω<ϕ.式(8)收

t→∞t→∞ω−ρx(t)

ϕρ. ϕ−ω由于r1,r2服从均匀分布,故sPSO系统的平均行为可通过其期望值进行观察,即

1x 1xcc

E(c1r1)=c1∫dx=1,E(c2r2)=c2∫dx=2;

01−0 01−022

c1r1p0+c2r2pgc1p0+c2pgϕρ故limx(t)=p*=. ==t→∞ϕ−ωc1r1+c2r2−ωc1+c2−2ω因此,当0<ω<ϕ=c1r1+c2r2=

c1p0+c2pgc1+c2

时,sPSO算法收敛于. 2c1+c2−2ω□

3 带极值扰动的粒子群优化算法

bPSO在优化前期中收敛速度很快,但在优化后期中收敛速度变得缓慢,因而导致收敛精度低.这主要是粒变异PSO、子群难以摆脱局部极值的原因,也是bPSO的美中不足.很多学者提出了许多改进方法,如杂交PSO、

自适应PSO、重新初始化粒子群、结合模拟退火等局部寻优策略等.但是,这些策略主要用于调整式(3)、式(4)中的参数ω,r1,r2,α和变量xid.这些改进策略都不同程度地提高了收敛速度和精度,但都不是从bPSO收敛于局部极值的根本原因上采取改进策略.下面首先分析bPSO收敛于局部极值的原因,然后提出相应的改进策略. 3.1 bPSO收敛于局部极值的原因分析

实验发现:当bPSO处于进化停滞时,粒子群中的粒子都会出现“聚集”现象,直至突破进化停滞局面,粒子才会“飞散”开去.下面从理论上解释这一现象.

文献[10]通过严格的数学推导,得到式(10):

t→+∞

limx(t)=p*=

c1r1c2r2

p0+pg (10)

c1r1+c2r2c1r1+c2r2

由于r1,r2服从均匀分布,故bPSO系统的平均行为可通过其期望值进行观察,故式(10)可以变为 c1p0+c2pg

limx(t)=p*==(1−α)p0+αpg (11) t→+∞c1+c2由式(11)和定理2可知:在bPSO和sPSO中,粒子将聚集到由自身极值p0和群体全局极值pg决定的极值之

上,如果所有粒子在向p*靠近过程中没有找到优于pg的位置,则进化过程将处于停滞状态,粒子逐渐聚集到p*. 3.2 带极值扰动的粒子群优化算法

通过第3.1节中的分析,bPSO和sPSO中粒子可以通过两种途径摆脱局部极值:(1) 粒子“飞向”p*过程中发现比pg更优的解,但在这一过程中发现更优解的概率较小,因为PSO已经陷入局部极值,pg周围已经过高密度的

′和p′搜索,难以突破“封锁”,这也导致了进化后期收敛缓慢;(2) 调整个体极值和全局极值为p0g,使所有粒子飞向新的位置p*′,这使所有粒子从p*迁移聚集到p*′,经历新的搜索路径和领域,因此发现更优解的概率较大.

通过调整参数ω,r1,r2,α和变量xid来优化bPSO和sPSO后期收敛速度和精度的方法,属于上述第1种情况;文献[6]的改进方法属于第2种情况,以适应度方差作为触发条件,并以很小概率[0.1 0.3]改变pg.

本文采用进化停滞步数t作为触发条件,对个体极值p0和全局极值pg同时进行随机扰动.极值扰动算子为

p0=r3t0>T0p0;pg=r4g

t>Tg

pg,

其中:t0,tg分别表示个体极值和全局极值进化停滞步数;T0,Tg表示个体极值和全局极值需要扰动的停滞步数阈 值;r

t0>T0

3

⎧⎧1, t0≤T0⎪1, tg≤Tgtg>Tg

和r4表示带条件的均匀随机函数. =⎨=⎨

U(0,1) tTU(0,1) tT>>⎪gg00⎩⎩

胡旺 等:一种更简化而高效的粒子群优化算法

因此,对bPSO方程式(3)和sPSO方程式(8)添加极值扰动算子后的形式为

865

t+1tvid=ωvid+c1r1(r3t0>T0pid−xid)+c2r2(r4g

t>Tgt>Tg

pgd−xid) (3′)

t

pgd−xid) (8′)

t+1tt

xid=ωxid+c1r1(r3t0>T0pid−xid)+c2r2(r4g

本文将式(3′)对应的算法称为带极值扰动的粒子群优化算法,简称tPSO;将式(8′)对应的算法称为带极值扰动的简化粒子群优化算法,简称tsPSO.需要说明的是,T0和Tg的取值大小决定了极值扰动算子生效的延迟长短,一般取值范围为3~8.当T0和Tg等于进化世代数时,式(3′)和式(8′)分别退化为式(3)和式(8).因此,tPSO和tsPSO分别是bPSO和sPSO的推广,bPSO和sPSO分别是tPSO和tsPSO的特例.

4 实验及结果分析

4.1 实验设计

为了测试本文提出的sPSO,tPSO和tsPSO的性能,本文设计了4类测试实验:(I) bPSO优化实验;(II) sPSO优化实验;(III) tPSO优化实验;(IV) tsPSO优化实验.实验选用6个常用于优化算法比较的基准函数,函数形式、维数、搜索范围、理论极值和优化目标精度见表1.这些测试函数在不同的文献中有不同的版本,为了方便比较,本文微调了部分函数的形式,使其理论上的最小值都为0.

Table 1 Benchmark functions used to test the improvement methods

表1 用于测试改进算法的基准函数

Name and code Sphere f1 Griewank f2 Rosenbrock f3 Rastrigin f4 Duadric f5

Formula

Dim

n 30 30 30 30 30

Range [xmin,xmax] [−100,100]30 [−600,600]30 [−100,100]30 [−100,100]30 [−100,100]30

Optimal

f 0 0

Goal for f 10−5 10−5

f1(x)=∑xi2

i=1

n

f2(x)=

n⎛xi⎞1n2

⎟+1()−cos⎜x∑∏i⎜⎟4000i=1i=1⎝i⎠n−1i=1

f3(x)=∑(100(xi+1−x2)2+(xi−1)2)

0 10 0 0

10−5 10−5

f4(x)=∑(xi2−10cos(2πxi)+10)

i=1

n

⎛D⎞ f5=∑⎜∑xj⎟⎜⎟d=1⎝j=1⎠

D

22⎛⎜sinx+y

f6(x)=0.5+⎝

(1.0+0.001(x2

2

Shaffer f6

⎞⎟−0.5⎠ 22+y))

2

[−100,100]2

0 10−5

待优化函数的维数越高、自变量范围越大、目标精度越高,优化过程的难度就越大.为了便于比较和突出改进算法的性能,本文均选用参考文献中最苛刻的函数参数,其具体值见表1.算法的实验参数也比参考文献中更加严格,具体算法参数设置为:种群数粒子数为15;进化世代数为150;最终结果采用运行20次后的平均值;c1=c2=2;ω=0.8;T0=3;Tg=5.

性能评估采用如下方法:(1) 固定进化迭代次数,评估算法收敛速度和收敛精度;(2) 固定收敛精度目标值,评估算法达到该精度目标所需要的迭代次数;(3) 与文献报道的性能进行比较. 4.2 实验结果及分析

4.2.1 固定进化迭代次数的收敛速度和精度

固定进化迭代次数的实验结果如图1所示,其中:a,b,c,d,e,f分别表示待优化函数f1,f2,f3,f4,f5和f6的适应度的对数值进化曲线(注:为了方便进化曲线的显示和观察,本文对函数的适应度取以10为底的对数;同时,为了避免真数为0和纵坐标范围过大,对函数的适应度均加上10−7作为截止值).标号I,II,III,IV分别表示

bPSO,sPSO,tPSO和tsPSO对以上6个函数的进化曲线.

866

Log10 (fitness) 20−2−4−6−8II IV IIIIFitness of f1 (sphere) Journal of Software 软件学报 Vol.18, No.4, April 2007

Log10 (fitness) 420−2−4−6Fitness of f2 (griewank)

IIIII IVI −80 50 100 1500 50 100 150

Generations Generations

(a) (b)

Fitness of f3 (rosenbrock)

1210Log10 (fitness) 820−2

Log10 (fitness) 20−2−4−6Fitness of f4 (rastrigin)

IV I

I IIIVIII II III −80 50 100 1500 50 100 150

Generations Generations

(c) (d)

Fitness of f5 (quadric)

Log10 (fitness) 10820−2−4−6−80−1−2−3−4−5−6−7Fitness of f6 (schaffe) Log10 (fitness)

III IV III IIIII IVI −80 50 100 1500 50 100 150

Generations Generations

(e) (f)

Fig.1 Fitness evolutionary curves of f1~f6 by the four experiments (I,II,III,IV)

图1 f1~f6在4个实验(I,II,III,IV)中的适应度进化曲线

由图1中的曲线(I)和曲线(III)可以看出,sPSO比bPSO在收敛精度和收敛速度上有非常显著的提高,说明了sPSO所对应方程式(8)的正确性和高效性;由曲线(I)和曲线(III)可以看出,tPSO比bPSO在摆脱局部极值能力、进化后期收敛速度和收敛精度等方面具有显著提高,说明了极值扰动算子具有很好的优化性能;曲线(IV)具有最高的收敛精度和最快的收敛速度,在经过20~50次进化迭代后,测试函数基本上达到了目标精度,说明了

tsPSO算法具有很好的实用性能. 4.2.2 固定收敛精度下的迭代次数

4个实验在表1中指定的收敛精度下经过20次运行后的平均迭代次数见表2.其中:成功率(SR)=达到精度的运行次数÷总实验次数;期望迭代次数(EI)=粒子种群数×平均迭代次数÷成功率;“∞”表示期望迭代次数为无穷大;实验代号为“V”是文献[10]报道的结果(注:文献[12]中:f1,f2,f3,f4,f6对应的搜索范围分别为±100,

±600,±30,±5.12,±100;它们对应的目标精度分别为0.01,0.1,100,100,10−5).

胡旺 等:一种更简化而高效的粒子群优化算法

867

由表2中实验代号I与II可以看出:bPSO对所有函数都没有达到目标精度;sPSO除了f3和f6以外均获得

100%的成功率,并且在很少的平均迭代次数(14~24)内就达到了指定的目标精度;sPSO对于f6也获得了很好的结果,而对f3的优化效果稍差,但还是获得了20%的成功率.以上结果说明,sPSO比bPSO的优化效果好得多.

同样比较实验代号I和III可以看出:tPSO总体上比bPSO的优化效果好一些.

实验代号IV全部以100%的成功率达到收敛目标,并且平均迭代次数均在12~48次之间,均小于50次.这表明,带极值扰动的sPSO算法具有非常高的优化性能和实用性.

Table 2 The number of iterations for the goal after 20 runs

表2 在目标精度下20次实验的进化代数

4.2.3 与参考文献中的优化性能比较

Experiment Iterations Iterations SuccessExpectedExperimentSuccess Expectedcode iterationscode rate iterationsMean Min Max rate MeanMinMax

I 150 150 150 0 I 150 150150 0 ∞ ∞ II 14 12 17 1 210 II 24 1751 1 360 f1 f4III 144 106 150 0.3 7 200 III 149 132150 0.05 44 700

IV 13 6 27 1 195 IV 18 9 30 1 270 V 769 523 1 377 0.4 28 838 V 172 102308 0.35 7 371 I 150 150 150 0 I 150 150150 0 ∞ ∞ II 15 12 19 1 225 II 17 1319 1 255 f2 III 147 130 150 0.25 8 820 f5III 150 150150 0 ∞

IV 12 6 24 1 180 IV 14 9 18 1 210 V 6 443 1 5 0.35 29 529 V － －－ － － I 150 150 150 0 I 150 150150 0 ∞ ∞ II 140 75 150 0.2 10 500 II 84 18150 0.7 1 800 f3 f6III 139 105 150 0.4 5 212 III 110 60150 0.85 1 941

IV 48 16 138 1 720 IV 15 7 29 1 225 V 531 413 695 1 15 120 V 583 633 706 0.45 19 433

(1) 由表2可以看出:除f4的实验III外(文献[12]中对f4的搜索范围比本文小了近40,而目标精度低了10倍),实验II,III,IV比文献[10]报道的实验代号V在函数参数更为苛刻的条件下获得了小得多的期望迭代次数.

(2) 表3是本文实验II,III,IV与参考文献的实验结果比较.需要特别说明的是,本文实验条件(如粒子种群数、进化迭代次数等)和函数约束条件(如搜索区间、函数维数等)比参考文献中的要苛刻很多.由表3可以看出,本文实验II,III,IV具有更高的收敛精度.

由上可知,本文提出的sPSO,tPSO和tsPSO算法比参考文献中的算法具有更好的收敛速度和收敛精度.

Table 3 Comparison of some modified PSOs 表3 一些改进粒子群算法的性能比较

Result f1 f2 f3 f4 f5 f6

II 0 0 21.386 96 0 0 0.001 94 III 0.002 57 0.003 19 20.395 62 0.320 59 1.076 75 0.000 002 IV 0 0 0.803 73 0 0 0

57.1941 36 Ref.[13] 0 0.002 095 50.798 139 0.000 155 － 46.468 9 Ref.[5] 9.880 8 0.403 3 1 610.359 － － 81.6 550 Ref.[10] 0 0.008 614 39.118 488 0.002 915 －

Ref.[14] 30.316 998 － － － － －

5 结 论

本文从理论上分析和证明了bPSO进化方程中的粒子速度概念不是必需的,进而提出了简化版本的sPSO,使进化方程由二阶降为一阶,并分析了sPSO的收敛条件和收敛极值点.同时,本文分析了bPSO陷入局部极值的原因,设计了极值扰动算子,使得bPSO可以快速摆脱局部极值,并将该极值扰动算子应用于bPSO和sPSO.通过对6个经典优化测试函数进行优化实验,结果表明:sPSO能够极大地提高收敛速度和精度;tPSO能够有效摆脱局部极值点;以上两种策略相结合,使得tsPSO以更小的种群数和进化世代数获得了更好的优化效果,从而使得粒子群优化算法更加实用化.

868

Journal of Software 软件学报 Vol.18, No.4, April 2007

本文的sPSO算法已经应用于图像刚性配准中,以两幅待配准图像的规一化互信息作为适应度,获得了很好的应用效果.在相同的种群数和粒子参数下,sPSO比bPSO获得了更高的互信息值(适应度值),表明sPSO比

bPSO具有更高的配准精度;在优化前期,sPSO比bPSO的互信息值上升得更快,表明sPSO比bPSO具有更快的收敛速度;sPSO基本上在进化50~100代内达到了极大互信息值,而bPSO在进化到150代时仍未达到sPSO的极大值,表明sPSO比bPSO在优化后期具有更快的配准速度和更高的配准成功率.限于篇幅,本文的算法结合小波分析技术在图像配准中的具体应用将另文发表. References:

[1] Kennedy J, Eberhart RC. Particle swarm optimization. In: Proc. of the IEEE Conf. on Neural Networks, IV. Perth: IEEE Press,

1995. 1942−1948. http://www.engr.iupui.edu/～shi/Coference/psopap4.html

[2] Shi Y, Eberhart RC. A modified particle swarm optimizer. In: Proc. of the IEEE Int’l Conf. of Evolutionary Computation.

Piscataway: IEEE Press, 1998. 69−73.

[3] Clerc M. The swarm and the queen: Towards a deterministic and adaptive particle swarm optimization. In: Proc. of the ICEC.

Washington, 1999. 1951−1957.

[4] Shi Y, Eberhart RC. Fuzzy adaptive particle swarm optimization. In: Proc. of the Congress on Evolutionary Computation.

Piscataway: IEEE, 2001. 101−106.

[5] Angeline PJ. Evolutionary optimization versus particle swarm optimization: Philosophy and performance differences. In: Proc. of

the 7th Annual Conf. on Evolutionary Programming. Berlin: Springer-Verlag, 1998. 601−610.

[6] Lü ZS, Hou ZR. Particle swarm optimization with adaptive mutation. Acta Electronica Sinica, 2004,32(3):416−420 (in Chinese

with English abstract).

[7] van den Bergh F, Engelbrecht AP. Cooperative learning in neural networks using particle swarm optimizers. South African

Computer Journal, 2000,(11):84−90.

[8] Ratnaweera A, Halgamuge SK, Watson HC. Self-Organizing hierarchical particle swarm optimizer with time-varying acceleration

coefficients. IEEE Trans. on Evolutionary Computation, 2004,8(3):240−255.

[9] He R, Wang YJ, Wang Q, Zhou JH, Hu CY. An improved particle swarm optimization based on self-adaptive escape velocity.

Journal of Software, 2005,16(12):2036−2044 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/16/2036.htm [10] Clerc M, Kennedy J. The particle swarm: Explosion stability and convergence in a multi-dimensional complex space. IEEE Trans.

on Evolution Computer, 2002,6(1):58−73.

[11] Trelea IC. The particle swarm optimization algorithm: Convergence analysis and parameter selection. Information Processing

Letters, 2003,85(6):317−325.

[12] Van den Bergh F. An analysis of particle swarm optimizers [Ph.D. Thesis]. South Africa: University of Pretoria, 2002.

[13] Eberhart RC, Shi Y. Comparing inertia weights and constriction factors in particle swarm optimization. In: Proc. of the 2000

Congress on Evolutionary Computation. Piscataway: IEEE, 2000. 84−88.

[14] Ke J, Qian JX, Qiao YZ. A modified particle swarm optimization algorithm. Journal of Circuits and System, 2003,8(5):87−91 (in

Chinese with English abstract).

附中文参考文献:

[6] 吕振肃,侯志荣.自适应变异的粒子群优化算法.电子学报,2004,32(3):416−420.

[9] 赫然,王永吉,王青,周津慧,胡陈勇.一种改进的自适应逃逸微粒群算法及实验分析.软件学报,2005,16(12):2036−2044.

http://www.jos.org.cn/1000-9825/16/2036.htm

[14] 柯晶,钱积新,乔谊正.一种改进粒子群优化算法.电路与系统学报,2003,8(5):87−91.

胡旺(1974－),男,湖南湘潭人,博士生,主 李志蜀(1946－),男,博士生导师,CCF高级

要研究领域为计算机应用.

会员,主要研究领域为计算机网络,多媒体技术,智能控制.