第21 卷 第6 期
Vol. 21 No. 6
控 制 与 决 策
Control and D ecision
2006 年6 月
Jun. 2006
收稿日期: 2005205208; 修回日期: 2005208226.
基金项目: 国家自然科学基金项目
(
60373095
)
; 国家973 计划项目
(
2100
CCA
00700
)
; 教育部科学基金项目
(
KP
0302
)
.
作者简介: 刘洪波
(
1971—
)
, 男, 武汉人, 博士, 讲师, 从事进化计算、神经网络等研究; 王秀坤
(
1945—
)
, 女, 辽宁辽阳
人, 教授, 博士生导师, 从事进化计算、机器学习等研究.
文章编号: 100120920
(
2006
)
0620636205
粒子群优化算法的收敛性分析及其混沌改进算法
刘洪波, 王秀坤, 谭国真
(
大连理工大学 计算机系, 辽宁 大连 116023
)
摘 要: 分析了粒子群优化算法的收敛性, 指出它在满足收敛性的前提下种群多样性趋于减小, 粒子将会因速度降
低而失去继续搜索可行解的能力; 提出混沌粒子群优化算法, 该算法在满足收敛性的条件下利用混沌特性提高种群
的多样性和粒子搜索的遍历性, 将混沌状态引入到优化变量使粒子获得持续搜索的能力. 实验结果表明混沌粒子群
优化算法是有效的, 与粒子群优化算法、遗传算法、模拟退火相比, 特别是针对高维、多模态函数优化问题取得了明显
改善.
关键词: 粒子群优化算法; 混沌; 多模态函数优化问题; 遗传算法; 模拟退火算法
中图分类号:
TP
301. 6 文献标识码:
A
Convergence Analysis of Particle Swarm Optim ization and Its
Improved Algorithm Based on Chaos
L IU H ong
2
bo
,
W A N G X iu
2
kun
,
TA N Guo
2
zhen
(
Departm ent of Computer
,
Dalian U niversity of T echno logy
,
Dalian
116023,
China
.
Correspondent
:
L IU Hong
2
bo
,
E
2
m ail
:
lhb
@
dlut
.
edu
.
cn
)
Abstract
:
The particle sw arm op tim ization
(
PSO
)
algorithm is analyzed
.
Its p rem ature convergence is due to the
decrease of velocity of particles in search space that leads to a to tal imp losion and ultim ately fitness stagnation of the
sw arm
.
A chaotic particle sw arm op tim ization
(
CPSO
)
algorithm is introduced to overcom e the p roblem of
p rem ature convergence
.
CPSO uses the p roperties of ergodicity
,
stochastic property
,
and regularity of chaos to lead
particles’ exp loration
.
This enable the sw arm system to have the ability of
“
sustainable developm ent
”.
Sim ulation
results show that CPSO p revents p rem ature convergence effectively and is better than PSO
,
genetic algorithm and
sim ulated annealing on som e benchm ark function op tim ization p roblem s
.
Key words
:
Particle sw arm op tim ization
;
Chaos
;
M ulti
2
modal function op tim ization p roblem
;
Genetic algorithm s
;
Sim ulated annealing
1
引 言
粒子群优化算法
(
PSO
)
是一种新兴的群智优化
算法
[1 ]
, 其思想来源于人工生命和演化计算理论, 是
对鸟群觅食过程中的迁徙和聚集的模拟. 由简单个
体组成的群落以及个体之间的互动行为模拟搜索最
优解, 收敛速度快. 相对遗传算法、模拟退火等算法
而言,
PSO
更简单有效
[2 ]
, 并已得到众多学者的重
视和研究
[3~ 5 ]
, 许多实际应用非常成功
[6~ 8 ]
. 但它存
在早熟问题, 大量的研究只集中在讨论粒子的轨迹
对算法收敛性所产生的影响
[9, 10 ]
, 以及惯性因子的
更新和种群拓扑结构的改进
[11, 12 ]
, 而深入分析粒子
的速度对算法收敛性的影响并给出其具体的证明并
不多见.
本文从理论上分析粒子的速度对算法收敛性的
影响, 并给出了证明. 同时提出了混沌粒子群优化算
法, 该算法在满足收敛性的条件下利用混沌的伪随
机性、对初始值敏感性和遍历性引导粒子群中的粒
子搜索, 提高种群的多样性和粒子搜索的遍历性, 将