—193—
动态粒子群优化算法
于雪晶
1
,麻肖妃
2
,夏 斌
2
(1. 长春工业大学信息传播工程学院,长春 130012;2. 94580 部队,蚌埠 233000)
摘 要:针对普通粒子群优化算法难以在动态环境下有效逼近最优位置的问题,提出一种动态粒子群优化算法。设置敏感粒子和响应阈值,
当敏感粒子的适应度值变化超过响应阈值时,按一定比例重新初始化种群和粒子速度。设计双峰 DF1 动态模型,用于验证该算法的性能,
仿真实验结果表明其动态极值跟踪能力较强。
关键词:粒子群优化算法;动态;双峰 DF1 模型;敏感粒子
Dynamic Particle Swarm Optimization Algorithm
YU Xue-jing
1
, MA Xiao-fei
2
, XIA Bin
2
(1. College of Information Broadcast Engineering, Changchun Industry University, Changchun 130012; 2. 94580 Army, Bengbu 233000)
【Abstract】Aiming at the problem that normal Particle Swarm Optimization(PSO) algorithm can not approach the best position effectively in
dynamic environment, this paper proposes a dynamic PSO algorithm. It sets sensing particle and response threshold. When sensing particle’s fitness
change exceeds response threshold, the algorithm reinitializes the swarm and particle velocity. It designs double-hump DF1 dynamic model to
validate the capability of this algorithm. Simulation experimental results show that it has high ability of dynamic extremum tracing.
【Key words】Particle Swarm Optimization(PSO) algorithm; dynamic; double-hump DF1 model; sensitive particle
计 算 机 工 程
Computer Engineering
第 36 卷 第 4 期
Vol.36 No.4
2010 年 2 月
Februar
y
2010
·人工智能及识别技术·
文章编号:1000—3428(2010)04—0193—02
文献标识码:A
中图分类号:TP18
1
概述
粒子群优化
(Particle Swarm Optimization, PSO)
算法是计
算机智能领域中,一种基于群体智能的优化算法。该算法最
早由文献
[1]
提出,其基本概念源于对人工生命和鸟类捕食的
研究。由于该算法收敛速度快、参数设置少,因此近年来受
到学术界的广泛重视,已成为一种重要的优化工具,并在函
数优化、神经网络训练、模式分类等工程领域得到广泛应用。
但普通粒子群优化算法缺乏动态环境探测和响应能力,因此,
本文对其进行改进。
2
动态粒子群优化算法
2.1
粒子群优化算法
粒子群优化算法采用速度
-
位置搜索模型,每个粒子代表
解空间的一个候选解,解的优劣程度根据优化目标由适应度
函数决定。粒子群算法随机初始化一群粒子,第
i
个粒子在
d
维解空间中的位置表示为
12
(, ,, )
iii id
x
xx x=
,粒子的飞行
速度
12
(, ,, )
iii id
vvv v=
决定粒子在搜索空间迭代时的位移。采
用如下公式进行迭代
[2-3]
:
12
(()) ( )
ii besti besti
v v c rand P i x c rand G x
ω
=×+× × − +× × −
(1)
11iii
x
xv
++
=+
(2)
其中,
ω
为惯性权重;
1
c
和
2
c
是非负的常数,一般取为
12
1.494 45cc==
;
rand
是随机数。每次迭代时,粒子通过动
态跟踪
2
个极值来更新其速度和位置,第
1
个极值是个体极
值
12
() ( , , , )
best i i id
P
iPP P=
,是粒子从初始到当前迭代次数搜索
产生的最优解。第
2
个极值是群体极值
12
(, ,, )
best d
GGGG=
,
是粒子种群目前能达到的最优解。
2.2
动态粒子群优化算法描述
在静态环境下,每个粒子通过跟踪自身记忆的个体最优
和种群记忆的全局最优得以逐渐逼近更优位置。但在动态环
境下,记忆的个体最优位置和全局最优位置对应的适应度值
是变化,粒子陷入对先前环境的寻优,因此,普通粒子群算
法难以在动态环境下有效逼近最优位置。
为了跟踪动态极值,需要对粒子群算法做
2
个方面改进:
(1)
引入探测机制,使种群或粒子获得感知外部环境变化的能
力;
(2)
引入响应机制,在探测到环境变化后,采用某种响应
方式对种群进行更新,以适应动态环境。采用如下方法设计
动态粒子群算法:先设置敏感粒子探测环境是否发生变化,
把可行空间划分为
1
n
个均匀的子空间,在每个子空间内随机
初始化
2
n
个敏感粒子,每次迭代时计算敏感粒子对应的适应
度值
i
f
,并计算相邻
2
次迭代适应度值差值
i
f
∆
,对所有差值
绝对值求和
F
。
(1) ()
ii i
f
fk fk∆= + −
(3)
1
n
i
i
F
f
=
=
∆
∑
12
()nnn
=
⋅
(4)
当
F
值不为
0
时,认为外部环境已发生变化,设定响应
阈值
F
阈
,当
F
值超过阈值
F
阈
时触发响应,响应机制为按一
定比例重新初始化粒子和粒子速度,描述如下:
if
F
F>
阈
max
max
() ( )
then
() ( )
Vi M V
Xi M X
=×
⎧
⎨
=×
⎩
rand
rand
其中,
()
M
rand
为
M
维向量,其中任一元素为
[0,1]
内的随机
数;
() [Vi
=
12
,,
ii
VV ,]
im
V
,
12
() [ , , , ]
ii im
X
iXX X=
,表示从种
群中选出的重新进行初始化的第
i
个粒子,
m
表示粒子的维
数;
max
V
为粒子最大速度,一般取
max max
VX=
。
2.3
算法流程
动态粒子群算法流程如下:
(1)
把可行空间划分为
1
n
个均
作者简介:于雪晶(1979-),女,讲师,主研方向:智能算法;
麻肖妃,助教、硕士研究生;夏 斌,工程师
收稿日期:2009-08-05 E-mail:cbaxueyu@sina.com