基于改进粒子滤波算法的比较分析研究
2011年5月吉林师范大学学报(自然科学版)
.2第2期
Journal of Jilin Normal University (Natural Science Edition)
May.2011
收稿日期:2011 03 20
第一作者简介:万智萍(1980 ),男,湖北省鄂州人,现为中山大学新华学院信息科学系讲师,工程硕士.研究方向:计算机技术,嵌入式技术,电子与通信工程技术.
基于改进粒子滤波算法的比较分析研究
万智萍1,叶仕通2
(1.中山大学新华学院信息科学系,广东广州510520;2.广东工业大学华立学院,广东增城511325)摘 要:提出一类改进的粒子滤波算法.对于建议分布的选取方案,此算法采取强跟踪分散的卡尔曼滤波方式
建立它的建议分布.由于线性调节参数,此算法让系统拥有更优越的自适应性及鲁棒性,对高机动目标具有更强的跟踪效果,继而为强跟踪扩展卡尔曼滤波的能力.仿真结论说明,此算法的性能比别的几类非线性滤波算法更加优秀.比如辅助粒子滤波器(APF)、迭代扩展卡尔曼粒子滤波器(IE KF PF)、Unscented 粒子滤波器(UPF)、正则化粒子滤波器(RPF),则是在bootstrap 粒子滤波器提出之后,继而出现的改进的粒子滤波器0基于粒子滤波,本文提出了阻止粒子退化的两个重点原因,以及选取合适的采样建议分布及重采样算法.
关键词:粒子滤波;密度函数;滤波算法;目标跟踪;卡尔曼滤波;
中图分类号:TP311 文献标识码:A 文章编号:1674 3873 (2011)02 0114 05
0 引言
基于使用一组有权值的粒子集合来说明解决问题时需求的后验概率密度,然后以它近似的表示去计算系统的状态估计为粒子滤波基本构思.指出一类改进的粒子滤波算法,并通过非线性系统的数值仿真,基于用此类强跟踪卡尔曼滤波器组建一个建议分布,验证了此算法的可行性.并基于改进粒子滤波算法对4种滤波器进行比较.
1 关于粒子滤波基本理论
假设系统模型的状态方程和观测方程分别为:
x k +1=f [x k ]+w k ,z k =h[x k ]+v k
式中,f [ ]及h[ ]都是非线性函数,w k 及v k 则是不联系的零均值过程噪声及测量噪声,它的协方差分别为Q k 及R k .:
p (x k |z 1:k-1)=p
(x k |x k-1)p (x k-1|z 1:k-1)d xk-1p (x k |z 1:k )=p (z k |x k )p (x k |z 1:k-1)/p (z k |z 1:k-1)
式中,转移先验概率分布是p (x k |x k -1),归一化常数是p (z k |z 1:k -1).
将积分运算成为有限样本点的求积运算是粒子滤波算法的基础,某一个抽样的详细建议分布函数经过加入,能够用下式近似表示状态概率密度分布:
p (xk |z 1:k ) 1
N
N
i =1
w i
k (xk -x i
k )
其中,x i k 为时刻自建议分布上随机取出的第i 个粒子,他的权值是,w i k 狄拉克脉冲函数是 ( ).
在实际运用里,来选取各异的建议分布函数根据具体状况,采用最实用的手段为选取先验密度,但如果建议分布函数,为q (x k |x k -1,z 1:k )=p (x k |x k -1).其效果直观并容易成功,这种方式缺点就是:不考虑使用新的观测值,这可能造成精度低,其滤波容易失败.
114
2 关于不敏粒子滤波算法(UPF)
生产粒子滤波的必要性密度函数基于Merwe 等假设运用不敏的卡尔曼滤波方法(UKF),被称为Unscented 粒子滤波器,它的支集重叠程度更大,预计精度较高于UKF 产生的必要性密度函数和最真状态的概率密度函数.该思路是基于每一次抽取的粒子于UKF 算法进行更新,所得的均值和方差用于下次取样标准.它的重点方式为:
(1)初始化:采样N 个粒子x i 0~p (x 0),i =1,2, ,N 自先验分布之中.(2)采用不敏卡尔曼滤波更新每一个粒子于每一个时刻,则: 算出各个粒子的西格玛点.
x a(i )
k -1j =
x a(i)k -1 x a(i )
k -1 (L + )p a(i )
k -1
时间更新.
x x (i)k |k -1j =f (x x (i)k -1j x v (i)
k -1j u k )
j =0, ,2L
x -(i )k|k-1
=
2l
j =0
w (m )j
x x (i)
k |k -1
p -(i )
k |k-1
=
2l
j=0
w (e)
j
(x x (i)k |k-1-x -(i )k |k-1) (x x (i )k |k -1j -x -(i )k|k-1)
T
z (i )k |k -1=h(x x (i)k |k -1j x n(i)k |k -1j )z -(i)k|k-1
=
2l
j=0
w (m )j z (i )k|k-1
量测更新.
p xz =
2l
j=0
w (e)
j
(x (i )k |k -1j -x (i )k|k-1) (z (i)k |k-1j -z -(i)k |k -1)T ,K k =P xz P -1
zz
x -(i )
k
=x -(i )k |k -1+K (z k -z -(i)k |k -1),p (i )k =p (i )k |k -1-K k P zz K T k
抽取粒子并且计算归一化权重于重要性密度函数q(xk |x
(i )
k -1,z k )=
N(xk ;x
(i )k ,P (i)
xk 中.
(3)重采样
3 关于强跟踪扩展卡尔曼粒子滤波算法
改进的粒子滤波算法的重心方式如下:
(1)初始化:w i 0为初始化权值,抽取N 个点{x 10,x 20, ,x N
0}从开始概率密度分布p (x 0).
(2)滤波更新:时刻为k 时,针对粒子进行滤波采用强跟踪扩展卡尔曼算法,并且重新产生粒子:
x i k/k -1=f N i
(x k -1
) p i k /k -1= (k )A(k )p i k -1A T
(k)+Q(k -1)K i k =p i k /k -1H T (k ) [H (k)p i k /k -1H T (k)+R(k )]-1
x i
k =
x i k /k -1+K i k (z k -h(
x i k /k -1)) p
i k =(I -K i k H (k ))P i k /k -1
分个担任正态分布的均值及方差:x i
k 和p
i
k ,生成一个新粒子,k 时刻的粒子集继而得出:
x i k :q (x i k /x i k -1,z 1:k )=N (x i k ,p
i
k )
(3)权值计算,归一化
w i k
=
w i
k-1p (zk /
x :
i k )
p (x :i k /
x :
i
k-1)
q (x :
i k /
x :
i 0:k -1,z 1:k )
w -i k
=
w j k /
N
j=1
w j
k
(4)重采样(可选):从{x :
i k ,
i =1,2, ,N }在此抽取样本,{x :
i k ,i =1,2, ,N }为新粒子集合,相应w -i
k
=1/N.
(5)状态更新
115
x
=
N
-i w k
x i k
我们为验证改进算法的可行性,必须将E K-PF 、EKF 、标准PF 算法和本算法实行了比较.采取了观测方程和状态方程为:
x (t)=1+sin (4e -2 t)+0.5x (t -1)+w (t -1)
y (t)=
0.2x 2(t)+v (t),t 30
-2+0.5x (t)+v(t),t >30
如上所示,举例v(t)服从N (0,1e -5)的高斯分布,w (t)服从N(0,0.75)的高斯分布.仿真过程,运行时间是100s,采样粒子数是200个.图1及2分别是EKPFSTEKPF 、EKF.
图1 EKF 和STED PF 滤波比较 图2 EKPF 和STEKPF 滤波比较
实行仿真的时候,通过观测方程及其余参数维持恒定,区别通过50次独自的实验仿真,例如表1所示为两次仿真的平均均方误差(MSE).再用两次仿真的MSE 差值与第一次仿真MSE 的商数的值作为滤波误差增长其百分比,且实行了对比.
表1 两次仿真数据对比
算法第一次MSE 第二次MSE 误差增长率/%
EK F 0.0632270.14581130.61PF 0.0403340.07694690.77EKPF 0.0283440.04652464.14STEKPF
0.019934
0.011621
13.48
通过对两次仿真的比较看出,在非线性滤波的情况之下,STEKPF 算法性能是相对较稳定的,但其余几类算法性能相互对比有不小的降低,由于非线性的增大而快速降低的更是E KF 算法性能.
4关于辅助粒子滤波算法(A PF)
基于SIS 的APF 滤波,并且掺入一个重要性密度函数q(Xk ,i |Z 1,k ),能导出样本集{Xjk,ij }基于该函数它的优势为运用两次加权操控,所以得出的估计结果更精确.其核心步骤是
(1)经过 i k :p (Xk |X i k -1)算出 i
k ,而i =1,2, ,N ;
(2)依据先验条件概率取样X i k ~p (X k );(3)w i k =
p (z i
k |x i
k )p (z k | i k )并归一化于计算得权值后;(4)再次抽取样本.
5 正则化粒子滤波算法(R PF)概念
从FrancoisLeGland 和ChristianMusso 推断的RPF,其验分布的连续密度于此算法采用密度估计理论计算后,以至连续分布
q (x k |
x
(i)k-1,z
k
)=
N
i=1
(i )k K h (x k -x (i )
k )
在上式中取样,从而降解粒子退化状况.K h(x )为核密度函数(Kemel p. d.f).与适应
K h (x )=
1h
n k(x
h )
116
核带宽为h >0,标准的核密度函数为k(.),并适合
x K (x )d x =0,
x 2
K (x )d x <
为等权值粒子时,Epanechnikov 核为最佳核密度函数
k o p t n +2
2c n
(1- x 2), x <1
0, x 1
在其中:R n
上分布的维数为n;单位球体体积为c.在最简单情况之下,假如后验分布为有着单位协方差的高斯密度,最佳带宽则是
h o p t =8c -1(n +4)2
n 1/(n +4)
N 1/(n +
4)
N 为粒子数.
需于等权值的粒子下执行正则化粒子滤波算法,因此针对粒子滤波,需要一个相似于系统取样的经过去首次生产等权值的粒子集.
6 关于扩展卡尔曼粒子滤波算法(EPF)
高效使用观测信息,来解决如今粒子滤波算法的问题,通过尝试用扩展卡尔曼滤波方法(EKF)去运算重要性密度函数于Freitas 、Doucet 等:
q (x k |x
(i )k -1,z k =(xk ;x
(i)
k
,P (i )x )
并且从里面取样x
(i)k ,为采用EKF 更新的粒子的方差及均值,P (t)
xk 因此构成了一种改进粒子滤波算
法,这种算法其重点方式是:
(1)初始化.取出N 个粒子x i
0~p (x 0),i =1,2, ,N 至先验分布中(2)用扩展卡尔曼滤波更新每一粒子于每一时刻,即
x
(i)k ,k -1=
f (
x (i )
k -1,
0) P
i k ,k -1=Fk P i k -1F T k +Q k -1 K i k =p i k ,k -1H T k (S i k )
-1
x i
k =
x
i k ,k -1+K i k (z k -h(x
i k,k -1,0)) p i k =p i k ,k -1-K i k H k p i k,k -
1
非线性状态转移函数及量测函数的局部线性化函数是F k ,H k .k 时刻的量测噪声及过程噪声的协方
差阵为Q k -1,R k ;
F k =
f (x ) x |x =x k -1 H k = f (x )
x
|x =x k k -1抽样粒子
x
i k :
q (x k |x
(i )k,k -1,z k )=
N (xk ;x
(i )
k
,P (i)
x )
(3)实行计算于各粒子的权值.
(4)重采样.
对于上述3种改进算法实行仿真并与bootstrap 粒子滤波器的滤波性能进行比较于本文针对Gorden 提出bootstrap 粒子滤波器时仿真从而运用的一个一维模型,其对结论实行解析.
该模型的状态方程是
x k =f k (x k -1,k )
+w k
其中
f k (x k -1,k )=0.5x k -1+25x k -1/(1+x 2k -1)+8cos (1.2(k -1))
量测方程是
Z k =x 2k /20+v k
为零均值的高斯白噪声且相互独立:w k 及v k .
w k 及v k 的方差为Q k =R k =1是实验的参数设置:并且x 0=1是原始状态,P 0=2是原始方差,针对每个算法均利用相同的粒子数,N =100,50为时间步长,各种改进算法的状态估量结果如图3表示,误差曲线如图4表示.如表2表示各算法的性能指标.
117
表2 滤波性能比较
滤波方法
性能指标
均方根误差(RM SE)运行时间/s
EPF0.05180.37
UPF0.02360.29
APF0.05780.63
RPF0.06140.81
图3 状态估计比较 图4 滤波误差比较
7 结语
对于往常的粒子滤波算法其改良的算法,这种方式跟踪精度提高了,粒子退化的状况减轻了.该算法的可行性仿真也被解释了.对于实际的目标跟踪运用里,可以应用更好的逼近对目标突变状况.对于EPF,由于涉及太多误差的扩展卡尔曼(E KF)的模型线性化及高斯假设,其改良成果较之UPF,比RPF和APF 好,不如序贯重要性采样滤波对外部观测量影响如此灵敏的APF,继而得出的估计结论更精准.其离散经验分布的连续近似于RPF完成,使能于连续分布中实行取样,粒子的多样性得到增大,其下降的滤波效率,终究为一种高效的滤波方式.
参 考 文 献
[1]韩崇昭,朱洪艳,段战胜.多源信息融合[M].北京:清华大学出版社,2006.
[2]夏克寒,许化龙,张朴睿.粒子滤波的关键技术及应用[J].电光与控制,2005,12(6):1~4.
[3]GORD ON N J,SALMOND D J,SMITH A FM.Novelapproach to nonlinear non Gauss ian Bayesian state esti mation[J].IEE Proceedings F,1993,140(2):
107~113.
Based on Improving Particle Filter Algorithm Comparative Study
WAN Zhi ping1,Y E Shi tong2
(1.Xinhua College of Sun Yat s en University,Guangzhou510520,China;
2.Huali College Guangdong Uni versity of Tec hnology,Guangzhou511325,China)
Abstract:This article puts forward one kind of particle filter algorithm.According to the selection of proposal distribution,this algorithm uses a method which is called The Strong tracking scattered Kalman filter to set up its proposal distribution.Because lines adjust the parameter,this system has the advantage of self adaptability and robust ness.To the high maneuvering target,it uses a stronger tracking effect to e xtend the perfor mance of the Kalman filtering. The c onclusion of sim ulation explains tha t the performance of algorithm is much more outstanding than other kinds of nonlin ear filte ring.For e xa mple,after the bootstrap Particle Filter was invented,a uxiliary particle filter(APF),I terated extended kalman particle filte r(I EKF PF)、unsc ented particle filter(UP F)、regulariza tion particle filter(RPF)appea red continuwhich le y.B asing on the particle filter,this ar ticle mention two important reasons of preventing the pa rticle dege neratively.In the meanwhile,it selec ts proposal distribution and resample technique pr operly to solve the problems.
Key words:particle filter;density function;filtering algorithm;target track;Kalman filtering
118
基于粒子群优化算法的图像分割
安康学院 学年论文（设计） 题目_____________________________________________ 学生姓名_______________ 学号_____________________________ 所在院（系）_______________________________________ 专业班级__________________________________________________ 指导教师_____________________________________________ 年月曰
基于粒子群优化算法的图像分割 （作者：） （） 指导教师： 【摘要】本文通过对粒子群优化算法的研究，采用Java编程，设计出一套用于图像分割的系统。 基于粒子群优化算法的图像分割系统，可以将一幅给定的图像进行分割，然后将分割结果保存。图像分割的目的是将感兴趣的区域从图像中分割出来，从而为计算机视觉的后续处理提供依据。图像分割的方法有多种，阈值法因其实现简单而成为一种有效的图像分割方法。而粒子群优化（PSO）算法是一类随机全局优化技术，它通过粒子间的相互作用发现复杂搜索空间中的最优区域缩短寻找阈值的时间。因此，基于粒子群优化算法的图像分割以粒子群优化算法为寻优工具，建立具有自适应和鲁棒性的分割方法。从而可以在最短的时间内，准确地确定分割阈值。 关键词：粒子群优化（PSO，图像分割，阈值法，鲁棒性 Abstract T his paper based on the particle swarm optimizati on algorithm, desig ns a set of system for image segme ntati on using Java program min g. Image segme ntati on system based on particle swarm optimizati on algorithm, the image can be a given segmentation, and then the segmentation results would be saved. Image segmentation is the purpose of the interested area from the image, thus providing the basis for the subsequent processing of computer vision. There are many methods of image segmentation, threshold method since its simple realization, becomes a kind of effective method in image segmentation. Particle swarm optimization （PSO） algorithm is a stochastic global optimization technique; it finds optimal regions of complex search spaces for threshold time shorte ned through the in teractio n betwee n particles. Therefore, particle swarm optimization algorithm of image segmentation based on particle swarm optimization algorithm based on optimizati on tools; establish segme ntati on method with adaptive and robust. Therefore, it is possible for us in the shortest possible time to accurately determ ine the segme ntati on threshold. Key word s: PSO, image segmentation, threshold method, robust. 1引言 1.1研究的背景和意义 技术的不断向前发展，人们越来越多地利用计算机来获取和处理视觉图像信息。据统计，人类
一种改进的粒子滤波重采样算法研究_金玉柱
2011年4月第4期 电子测试 ELECTRONIC TEST Apr.2011 No.4一种改进的粒子滤波重采样算法研究 金玉柱，李善姬 （延边大学工学院，吉林 延吉 133002） 摘要：粒子滤波是基于递推的蒙特卡罗模拟方法的总称，可用于任意非线性，非高斯随机系统的状态估计。为了减轻退化现象，引入重采样过程，但重采样过程算法复杂，计算量大，不利于硬件实现，并且会削弱粒子的多样性，从而导致滤波性能下降。提出了一种将局部重采样和优化组合算法结合的重采样算法。将粒子按权值大小分类，小权值的粒子抛弃，大权值的粒子进行复制，将复制的粒子和抛弃的粒子线性组合产生新的粒子，增加了粒子多样性并且只对大权值粒子进行运算，故降低了计算量利于实时系统的硬件实现。仿真结果证明了该算法的有效性。 关键字：粒子滤波; 局部重采样; 优化组合 中图分类号： TP391 文献标识码：A Research of improved particle filter resampling algorithm Jin Yuzhu, Li Shanji (College of Engineering, Yanbian University, Yanji 133002, China) Abstract: Particle filtering is a sequential Monte Carlo simulation algorithm. It can be used to estimate the state of any nonlinear, non-Gaussian system. In order to reduce the degeneracy, the resampling algorithm is adopted. But the resampling process has complex algorithm architecture, which have restricted its implementation in real-time system. Resampling process also leads to the loss of diversity of particles, and the loss makes filter’s performance worse. A new algorithm-partial resampling combined with optimizing combination resampling method is proposed. Assort the particles by their weights, the particles which have low weights are abandoned and the particles which have high weights are reproduced, and generate new particles by combining the reproduced particles and abandoned particles. This new method partly overcomes the loss of diversity and because it simply operates to the high weights particle so its calculation is simplified. And it is propitious to implement by hardware. The simulation results prove the effectiveness of the proposed method. Keywords : particle filtering; partial resampling; optimizing combination 0 引言 粒子滤波器，又称序贯蒙特卡罗方法。可以有效地处理非线性、非高斯滤波问题，广泛地应用在机动目标跟踪、信号传输与压缩、金融领域数据分析、图像处理、故障诊断等领域。所谓粒子滤波就是贝叶斯估计基于抽样理论的一种近似算法，通过非参数化的蒙特卡罗模拟方法来实现递推贝叶斯滤波，即通过一组动态状态空间上按贝叶斯准则进行更新的随机加权的样本或粒子，对未知状态的后验概率密度进行估计，其中这些粒子通过对后验密度序贯重
基于改进粒子群算法的优化策略
收稿日期:2009-12-13 基金项目:国家自然科学基金资助项目(60674021) 作者简介:卢 峰(1982-),男,辽宁抚顺人,东北大学博士研究生;高立群(1949-),男,辽宁沈阳人,东北大学教授,博士生导师 第32卷第9期2011年9月东北大学学报(自然科学版)Journal of Northeastern U niversity(Natural Science)Vol 32,No.9Sep.2011 基于改进粒子群算法的优化策略 卢 峰,高立群 (东北大学信息科学与工程学院,辽宁沈阳 110819) 摘 要:为提高传统粒子群算法的搜索速度和搜索精度,提出了一种改进的自适应粒子群优化算法 将正则变化函数和慢变函数引入传统位置更新和速度更新公式当中,形成两种新的更新机制:搜索算子和开发算子 在算法运行的初始阶段,种群中大部分个体将按照搜索算子进行更新,搜索算子将有助于种群遍历整个解空间;随着迭代次数的增加,按照搜索算子进行更新的个体将逐渐减少,而按照开发算子进行更新的个体将逐渐增多,开发算子将有效地克服陷入局部最优解的问题 通过典型测试函数的仿真实验,新算法在加快收敛速度同时,提高了算法的全局搜索能力 关 键 词:进化算法;粒子群算法;全局优化;慢变函数;自适应 中图分类号:T G 273 文献标志码:A 文章编号:1005 3026(2011)09 01221 04 Novel Optimization Mechanism Based on Improved Particle Swarm Optimization L U Feng ,GAO L i qun (School of Information Science &Engineering,Northeaster n U niv ersity,Shenyang 110819,China.Corresponding author :LU F eng,E mail:feng.lu.lf @g https://www.wendangku.net/doc/8013472862.html,) Abstract :To accelerate searching speed and optimization accuracy of traditional PSO,an improved particle swarm optimization (PSO )algorithm w as presented.Regularly vary ing function and slow ly varying function were introduced in the position and velocity update formula.New mechanisms such as explorative operator and exploitative operator are formulated.At the beginning,most elements will be updated by explorative operator in the entire search space sufficiently.Within the iterations,more and more particles w ill be handled by ex ploitative operator,which are useful to overcome the deceptions of multiple local optima.It can be seen from the simulation results of the standard benchm ark test functions that the proposed algorithm not only accelerates the convergence process,but also improves g lobal optim ization ability. Key words:evolutionary algorithms;particle sw arm optimization;global optimization;slow ly v arying function;self adaptive 20世纪90年代初,产生了模拟自然生物群体行为的优化方法,被称为群智能优化方法 Dorigo 等人通过模拟蚂蚁的寻径行为,提出了蚁群优化算法(ant colony optimization)[1] ;Eberhart 等人基于对鸟群、鱼群的模拟,提出了粒子群优化算法(particle sw arm optim ization )[2] 作为一种群智能优化方法的代表,粒子群算法通过个体间的协作来寻找最优解,每个个体都被赋予一个随机速度并在整个解空间中搜索,通 过个体之间的合作与竞争来实现个体进化 由于粒子群优化算法运算简单,易于实现,具有良好的解决非线性、不可微和多峰值复杂优化问题的能力,已被广泛应用于科学和工程实际领域[3-5] 但是,粒子群优化算法是根据全体粒子和自身的搜索经验向着最优解的方向进化,在进化后期收敛速度将变得缓慢,同时算法在收敛到一定精度时,容易陷入停滞,无法继续进化更新,因此,存在早熟和陷入局部极值点的现象
基于MATLAB的粒子群优化算法的应用示例
对于函数f=x*sin(x)*cos(2*x)-2*x*sin(3*x)，求其在区间[0,20]上该函数的最大值。 ?初始化种群 已知位置限制[0,20],由于一维问题较为简单，因此可以取初始种群N 为50，迭代次数为100,当然空间维数d 也就是1。 位置和速度的初始化即在位置和速度限制内随机生成一个N×d 的矩阵，对于此题，位置初始化也就是在0~20内随机生成一个50×1的数据矩阵，而对于速度则不用考虑约束，一般直接在0~1内随机生成一个50×1的数据矩阵。 此处的位置约束也可以理解为位置限制，而速度限制是保证粒子步长不超限制的，一般设置速度限制为[-1,1]。 粒子群的另一个特点就是记录每个个体的历史最优和种群的历史最优，因此而二者对应的最优位置和最优值也需要初始化。其中每个个体的历史最优位置可以先初始化为当前位置,而种群的历史最优位置则可初始化为原点。对于最优值，如果求最大值则初始化为负无穷，相反地初始化为正无穷。 每次搜寻都需要将当前的适应度和最优解同历史的记录值进行对比，如果超过历史最优值，则更新个体和种群的历史最优位置和最优解。 ?速度与位置的更新
速度和位置更新是粒子群算法的核心，其原理表达式和更新方式如下: 每次更新完速度和位置都需要考虑速度和位置的限制，需要将其限制在规定范围内，此处仅举出一个常规方法，即将超约束的数据约束到边界（当位置或者速度超出初始化限制时，将其拉回靠近的边界处）。当然，你不用担心他会停住不动，因为每个粒子还有惯性和其他两个参数的影响。 代码如下： clc;clear;close all; %% 初始化种群 f= @(x)x .* sin(x) .* cos(2 * x) - 2 * x .* sin(3 * x); % 函数表达式figure(1);ezplot(f,[0,0.01,20]); N = 50; % 初始种群个数 d = 1; % 空间维数 ger = 100; % 最大迭代次数 limit = [0, 20]; % 设置位置参数限制 vlimit = [-1, 1]; % 设置速度限制 w = 0.8; % 惯性权重 c1 = 0.5; % 自我学习因子 c2 = 0.5; % 群体学习因子 for i = 1:d
标准粒子群算法(PSO)及其Matlab程序和常见改进算法
一、粒子群算法概述 粒子群优化算法(PSO)是一种进化计算技术(evolutionary computation)，1995 年由Eberhart 博士和kennedy博士提出，源于对鸟群捕食的行为研究。该算法最初是受到飞鸟集群活动的规律性启发，进而利用群体智能建立的一个简化模型。粒子群算法在对动物集群活动行为观察基础上，利用群体中的个体对信息的共享使整个群体的运动在问题求解空间中产生从无序到有序的演化过程，从而获得最优解。 PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitness value)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。 PSO 初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个”极值”来更新自己。第一个就是粒子本身所找到的最优解，这个解叫做个体极值pBest。另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。 二、算法原理 粒子群算法采用常数学习因子，及惯性权重，粒子根据如下的公式更新自己的速度和位置。 V ki=ωk V i?1i+c1r1(Q bi?Q k?1i)+c2r2(Q bg?Q k?1i)Q ki=Q k?1i+V ki 三、算法步骤 1、随机初始化种群中各微粒的位置和速度； 2、评价个粒子的适应度，将各粒子的位置和适应度储存在各微粒的pbest（Q bi）中，将所有pbest中适应度最优的个体的位置和适应度存储在gbest（Q bg）中。 3、更新粒子的速度和位移。 V ki=ωk V i?1i+c1r1(Q bi?Q k?1i)+c2r2(Q bg?Q k?1i)Q ki=Q k?1i+V ki 4、对每个微粒，与其前一个最优位置比较，如果较好，则将其作为当前的最优位置。 5、比较当前所有的pbest和上一迭代周期的gbest，更新gbest。 6、若满足停止条件（达到要求精度或迭代次数），搜索停止，输出结果，否则，返回2。
浅谈粒子群算法改进方法
浅谈粒子群算法改进方法 【摘要】本文介绍了粒子群算法的基本概念及粒子群算法的训练过程，分别从基本进入、改变惯性因子、改变收缩因子三个方面对其进行优化改进。 【关键词】粒子群;进化方程;惯性因子;收缩因子 1.粒子群算法综述 二十世纪九十年代，美国的社会心理学家James Kennedy和电气工程师Russell通过对自然界的鸟群进行觅食的行为进行观察和研究，提出了模仿鸟群行为的新型群体智能算法——粒子群（Particle Swarm Optimization，PSO）算法。 粒子群算法与其它进化类算法十分相似，同样也是采用“群体”与“进化”的概念，同样也是依据粒子的适应值大小进行操作。而与之不同的是，粒子群算法不像其它进化算法那样，对于每个个体使用进化算子，而是将每个个体看作是在一个n维搜索空间中的没有重量没有体积的微粒，并在搜索空间中以一定的速度进行飞行。该飞行速度这个个体的飞行经验和群体的飞行经验来进行动态的调整。 2.粒子群算法实现的步骤 这里将基本粒子群算法的训练过程描述如下： （1）首先将初始化方程作为依据，将该粒子群体的随机位置和速度进行初始化设置; （2）计算粒子群中每个粒子的适应度值; （3）将该粒子群中每个粒子的适应值与其经历过的最好位置Pi的适应值进行比较，如果好，将它作为当前的最好位置; （4）将该粒子群体中每个粒子的适应值与所有粒子经历的最好位置Pg的适应值进行比较，如果好，将它作为当前的全局最好位置; （5）以粒子群进化方程为依据，进化粒子的速度及位置; （6）如果没有达到设置的结束条件或达到一个设置的最大迭代次数，则返回到第二步，否则结束。 3.粒子群算法进化方程的改进 3.1 基本粒子群算法进化方程的分析
基于粒子群优化算法的神经网络在
基于粒子群优化算法的神经网络在农药定量构效关系建模中的应用 张丽平 俞欢军3 陈德钊 胡上序 (浙江大学化工系,杭州310027) 摘 要 神经网络模型能有效模拟非线性输入输出关系,但其常规训练算法为BP 或其它梯度算法,导致训练时间较长且易陷入局部极小点。本实验探讨用粒子群优化算法训练神经网络,并应用到苯乙酰胺类农药的定量构效关系建模中,对未知化合物的活性进行预测来指导新药的设计和合成。仿真结果表明,粒子群优化算法训练的神经网络不仅收敛速度明显加快,而且其预报精度也得到了较大的提高。关键词 粒子群优化算法,神经网络,定量构效关系 2004201204收稿;2004207225接受 本文系国家自然科学基金资助项目(N o.20276063) 1 引 言 药物定量构效关系(QS AR )是研究药物生理活性和药物分子结构参数间的量变规律并建立相应的 数学模型,进而研究药物的作用机理,从而用于预测未知化合物的生物活性,探讨药物的作用机理,指导新药的设计和合成,在药物和农药的研究与设计中已经显示出广阔的应用前景1。以往QS AR 的建模方法大多基于统计原理,局限于线性模型,只进行简单的非线性处理,由此所建立的模型很难契合实际构效关系,并且其处理过程都比较繁琐2。神经网络通过学习将构效关系知识隐式分布在网络之中,适用于高度非线性体系。 在药物QS AR 中采用神经网络(NN )始于20世纪80年代末3,此后得到迅速的发展,目前已发展为除多重线性回归和多元数据分析之外的第3种方法4。通常多层前传网络采用BP 算法,通过误差反传,按梯度下降的方向调整权值。其缺点是可能陷入局部极小点,且对高维输入收敛速度非常缓慢。 粒子群优化算法(particle swarm optimization ,PS O )是K ennedy 等5源于对鸟群、鱼群和人类社会行为的研究而发展的一种新的进化型寻优技术。PS O 已成为进化寻优算法研究的热点,其最主要特点是简单、收敛速度快,且所需领域知识少。本实验拟将该方法初始化前传神经网络为苯乙酰胺类农药建立良好适用的QS AR 模型。 2 苯乙酰胺类农药的Q SAR 问题 苯乙酰胺类化合物是除草农药,其除草活性与其分子结构密切相关。所有的N 2(12甲基212苯乙基)苯乙酰胺都可用相应的羧酸酰胺通过霍夫曼反应生成。N 2(12甲基212苯乙基)苯乙酰胺的基本结构式为 : 其中X 为Me 、F 、Cl 、OMe 、CF 3和Br 等,Y 为Me 、Cl 、F 和Br 等,由不同的X 和Y 取代基可构成不同的化合物。常用以下7个理化参数描述化合物的分子组成和结构:log P 、log 2P (疏水性参数及其平方项)、 σ(电性效应参数)、E s (T aft 立体参数)、MR (摩尔折射度),1χ、2 χ(分子连接性指数)。于是这类化合物的QS AR 就转化为上述理化参数与除草活性间的关系。为研究这种关系,选用具有代表性的50个化合物, 他们的活性值取自文献1,见表1。 第32卷2004年12月分析化学(FE NXI H UAX UE ) 研究报告Chinese Journal of Analytical Chemistry 第12期1590～1594
改进粒子群算法的目标函数变化分类动态优化
龙源期刊网 https://www.wendangku.net/doc/8013472862.html, 改进粒子群算法的目标函数变化分类动态优化 作者：苏玉孔国利 来源：《现代电子技术》2017年第07期 摘要：由于优化问题的目标函数和约束条件都随着时间而改变导致其最优值也发生改变，提出一种基于改进粒子群算法的目标函数变化分类动态优化算法。首先对动态优化问题进行定义，明确问题的研究对象，提出对目标函数随时间变化程度分类的思想，通过对变化的函数进行监测的方法将其分为剧烈变化、中等程度变化和弱变化三种类型，并针对不同的强度变化对粒子群算法采用不同的改进策略，最后将不同的策略融入计算。通过采用移动多峰问题进行测试，结果表明，提出的改进粒子群优化算法能监测目标函数变化，并能随时跟踪到最优解，平均离线误差相对于标准粒子群算法更小，性能更稳定。 关键词：粒子群算法；动态优化；目标函数时变分类；移动峰问题 中图分类号： TN911.1?34； TP301.6 文献标识码： A 文章编号： 1004?373X（2017）07?0175?04 Dynamic optimization of objective function changing classification based on improved particle swarm optimization SU Yu， KONG Guoli （College of Information Engineering， Zhongzhou University， Zhengzhou 450001，China） Abstract： The objective function and constraint condition for the optimization problem are changed with time， and may change its optimal value. A dynamic optimization of the objective function changing classification based on improved particle swarm optimization is proposed. The dynamic optimization problem is defined to determine the study object of the problem. The classification thought that the objective function is changed with the time varying degree is put forward. The varying function is divided into the types of drastic change， medium grade change and weak change with the monitoring method. Different strategies are adopted for the particle swarm optimization according to the different intensity changes， and integrated for computation. The algorithm was tested with the moving multi?peak problem. The test results show that the improved particle swarm optimization can monitor the changes of the objective function， track the optimal solution momentarily， its average offline error is smaller than that of the standard particle swarm optimization algorithm， and the performance is more stable.
扩展卡尔曼滤波和粒子滤波算法比较
扩展卡尔曼滤波和粒子滤波算法比较上海大学2013 , 2014学年秋季学期 研究生课程小论文 课程名称: 随机信号导论课程编号: 07SB17002 论文题目: 扩展卡尔曼滤波和粒子滤波算法比较 研究生姓名: 班孝坤 (33%) 学号: 13720843 研究生姓名: 倪晴燕 (34%) 学号: 13720842 研究生姓名: 许成 (33%) 学号: 13720840 论文评语: 成绩: 任课教师: 刘凯 评阅日期: 扩展卡尔曼滤波和粒子滤波算法比较 第一章绪论 在各种非线性滤波技术中, 扩展卡尔曼滤波是一种最简单的算法, 它将卡尔曼滤波局部线性化,适用于弱非线性、高斯环境下。卡尔曼滤波用一系列确定样本来逼近状态的后验概率密度, 适用于高斯环境下的任何非线性系统。粒子滤波用随机样本来近似状态的后验概率密度, 适用于任何非线性非高斯环境, 但有时选择的重要性分布函数与真实后验有较大差异, 从而导致滤波结果存在较大误差, 而粒子滤
波正好克服了这一不足, 它先通过UKF产生重要性分布, 再运用PF 算法。通过仿真实验, 对其的性能进行比较。 严格说来,所有的系统都是非线性的,其中许多还是强非线性的。因此,非线性系统估计问题广泛存在于飞行器导航、目标跟踪及工业控制等领域中,具有重要的理论意义和广阔的应用前景。 系统的非线性往往成为困扰得到最优估计的重要因素，为此，人们提出了大量次优的近似估计方法。包括EKF,基于UT变换的卡尔曼滤波(UKF)，粒子滤波，等等。 第二章扩展卡尔曼滤波介绍 2.1 扩展卡尔曼滤波的理论(EKF) 设非线性状态空间模型为: xfxv,(,)(1)ttt,,11 yhxn,(,)(2)ttt 式中和分别表示在t时刻系统的状态和观测，和 xR,yR,vR,nR,tttt分别表示过程噪声和观测噪声，f和h表示非线性函数。 扩展卡尔曼滤波(Extended kalman filter,以下简称EKF)是传统非线性估计的代表,其基本思想是围绕状态估值对非线性模型进行一阶Taylor展开,然后应用线性系统Kalman滤波公式。 EKF是用泰勒展开式中的一次项来对式(1)和 ( 2 ) 中的非线性函数f和h 进行线性化处理, 即先计算f和h 的雅克比矩阵, 然后再在标准卡尔曼滤波框架下进行递归滤波。和均为零均值的高斯白噪声。 vntt 2.2 扩展卡尔曼滤波的算法 EKF的算法同KF 一样, 也可分为两步预测和更新。如图2.1所示
粒子群算法常用改进方法总结
粒群算法的改进方法 一．与其他理论结合的改进 1.协同PSO(CPSO)算法 原理：提出了协同PSO的基本思想，采用沿不同分量划分子群体的原则，即用N个相互独立的微粒群分别在D维的目标搜索空间中的不同维度方向上进行搜索。 优点：用局部学习策略，比基本PSO算法更容易跳出局部极值，达到较高的收敛精度． 缺点：此算法在迭代初期，适应值下降缓慢，且其收敛速度与种群所含微粒数目成反比． 2.随机PSO(SPSO)算法 原理：其基本思想是利用停止进化的微粒来改善全局搜索能力。即将式(1)中的当前速度项V过去掉，从而使得速度本身失去记忆性，减弱了全局搜索能力．但这样也使得在进化的每一代均至少有一个微 粒出予处于微粒群的历史最好位置而停止进化．然后在搜索空问中重新随机产生新的微粒以代替停止微粒的进一步进化．这样就大大增强了全局搜索麓力． 3.有拉伸功能的PSO算法 原理：为了有效地求解多模态复杂函数优化问题，Parsopoulos等人将函数“Stretching”技术引入PSO算法，形成了一种高效的全局优化算法一“Stretching PSO”(SPSO)。它通过消除不理想的局部极小而保留全局最小来避免陷入局部极小．在检测到目标函数的局部极小
点后，立即对待优化的目标函数进行拉伸变换． 优点：．SPSO具有稳健的收敛性和良好的搜索能力，在很多高维度，多局部极值的函数最小值的求解问题上，搜索成功率显著提高。 缺点：计算耗时相应地也会增加． 4.耗散PSO(DPSO)算法 原理：谢晓峰等人根据耗散结构的自组织性，提出了一种耗散型PSO 算法．耗散PSO算法构造了一个开放的耗散系统．微粒在开放系统中的“飞行”不只依赖于历史经历，还要受环境的影响．附加噪声从外部环境中，持续为微粒群弓|入负熵，使得系统处于远离平衡态的状态．又由于群体中存在内在的非线性相互作用，从而使群体能够不断进化。 二．与其他算法结合的改进 1.混合PSO(HPSO)算法 原理：Angeline于1998年提出采用进化计算中的选择操作的改进型PSO模型，成为混合PSO(HPSO)。 优点：HPSO提高了收敛速度并保持了一定的全局收敛能力 缺点：在解决超高维、非线性、多局部极值的复杂性优化问题时有些力不从心。 2.杂交PSO算法 原理：借鉴遗传算法的思想，Angelinec最早提出了杂交PSO算法的概念，而Lovbjerg等人进一步将进化计算机制应用于PSO算法，给出了算法交叉的具体形式。
粒子滤波算法
粒子滤波算法 09S003057 徐飞 由于我的课题是用粒子滤波进行目标跟踪，今天参加了一场粒子滤波算法的讲座，对经典粒子滤波与其它粒子滤波进行了详细的讲解，学到了很多知识。 经典粒子滤波 算法的一般描述： 1.初始化：取k ＝0，按0()p x 抽取N 个样本点() 0i x ，i ＝1,…,N 。 2.重要性采样： ()()0:11:(|,)i i k k k k x q x x z -~，令 ()() ()0:0:1(,)i i i k k k x x x -=，其中i ＝1,…,N 。 3.计算权值： ()()() () ()11 ()() 0:11:(|)(|)(|,) i i i i i k k k k k k i i k k k p z x p x x q x x z ---ω =ω 若采用一步转移后验状态分布，该式可简化为()()() 1(|)i i i k k k k p z x -ω=ω。 4.归一化权值： () j j i i k k N k () ()=1 ωω = ω ∑ 5.重采样：根据各自归一化权值 () i k ω 的大小复制/舍弃样本 () 0:i k x ，得到N 个近似服从()0:1:(|)i k k p x z 分布的样本()0:i k x 。令()i k ω＝ ()i k ω＝1/N ，i ＝1,…,N 。 6.输出结果：算法的输出是粒子集() 0:{: 1...}i k x i N =，用它可以近似表示后验概率和函数 0:()k k g x 的期望 0:0:1:0:11(|)()i k N k k k x i p x z dx N ()==δ∑ 0:0:1 1(())()N i k k k k i E g x g x N ==∑ 7.K=K+1,重复2步至6步。 其它粒子滤波 正则粒子滤波 正则粒子滤波(Regularized Particle Filter ，RPF)是为了解决由重采样引入的新问题而提出的一种改进的粒子滤波。当通过序贯重要性采样后引起粒子退化问题时，前面提到可以用重采样的方法来减小退化的影响，但是引入重采样策略同时也引入了新的问题，即粒子匮乏问题，经过若干次迭代之后，所有粒子都趋向于同一个粒子，导致粒子的多样性丧失。这是因为在重采样过程中，粒子是从离散分布中采样取得的，而不是从连续分布中采样得到的。 正则粒子滤波正是为了解决上述问题而提出的。它与SIR 粒子滤波的区别在于：在重采样过程中，SIR 从离散近似的分布中重采样，而正则粒子滤波则从连续近似的分布中重采样。 1 0:1 {,} (|)()N j j m i i k k j k k k h k k i x p x y K x x ==ω~≈ω-∑ 其中,1()()h n x x K x K h h = 是对核密度()K 进行了重新标度后的结果，n 为x 的维数,h 称为
基于粒子滤波的目标跟踪算法浅析
基于粒子滤波的目标跟踪算法浅析 高 翔 （甘肃联合大学 电子信息工程学院 甘肃 兰州 730010） 摘 要： 所做的工作是利用粒子滤波理论解决目标跟踪所面临的技术问题。首先介绍粒子滤波中的两种重要算法：贝叶斯理论和蒙特卡罗方法，接着在此基础上详细阐述基于粒子滤波的目标跟踪算法。 关键词： 目标跟踪；粒子滤波；序列重要性采样 中图分类号：TN.2 文献标识码：A 文章编号：1671－7597（2011）0510193－02 1 绪论 时就可以根据上式计算出p 的概率分布。可以表示为： 粒子滤波技术在非线性、非高斯系统表现出来的优越性，决定了它的应用范围非常广泛。另外，粒子滤波器的多模态处理能力，也是它应用广泛有原因之一。本文首先介绍了粒子滤波理论的基础，接下来在此基础上研究了基于粒子滤波的目标跟踪算法。 2 粒子滤波的计算理论方法 其中，为模拟随机试验的次数，即是p 的子样本的个数。p i ，表示试2.1 贝叶斯理论 验所得到的相应的子样本。 贝叶斯估计理论较经典的统计估计理论具有更大的优势，逐渐成为科蒙特卡罗方法是以概率模型为基础的，它解题的三个主要步骤是：学界推理的一个重要工具。贝叶斯推论提供了一种与传统方法不同的概率分布形式的估计，它利用所有的已知信息来构造系统状态变量的后验概率密度，即用系统模型预测状态的先验概率密度，再利用最新的量测值进行修正，得到后验概率密度。这样它就包括了量测值和先验知识在内的所有可以利用的信息，得到的估计误差自然就小一些。 我们将会描述一个以状态x 为参数的一般模型的框架，其中t 表示离散时t 间。对于跟踪所关心的分布是后验概率 也叫滤波分布，其中 波分布可以用两步递归迭代来计算： 其中预测阶段是一个边缘分布，而新的滤波分布则是由贝叶斯法则直 接得到的。递归过程的完成需要有状态演进 的动态模型和一个当前测量值 的状态似然模型，迭代过程用一些初始状态的分布来初始化。上述跟踪迭代只是在极少的情况下具有严格的表述形式。其中最著名的是用于线性和高斯动态系统与似然模型的卡尔曼滤波器（KF ），而对于一般的非线性和非高斯模型跟踪迭代变得束手无策，这时就需要逼近技术。而序列蒙特卡罗方法也叫粒子滤波器由于它们具有有效、简单、适应性强、易实现等优点，作为一个计算复杂模型的跟踪迭代近似方案近年来受到广泛的欢迎。 2.2 蒙特卡罗方法 蒙特卡罗方法的基本原理是：在物理、数学、建筑工程以及工业生产等领域，如果要求解的问题是某种事件出现的概率，或者是某个随机变量的数学期望时，首先按照一定的方法建立一个数学模型，使该模型的参数等于要求的问题的解，然后以此数学模型为基础通过抽样试验来计算出参数的统计特性，最后给出所求问题的近似估计值。在实际的应用中，解的精确度可以用估计值的标准误差来表示。 假如有以下的函数关系式：P 二f （x ） 其中，变量x 服从某一概率分布，是一个随机变量。f （x ）是一个包含多重积分的表达式，直接用解析的方法很难求出函数 p 的概率分布。 按照蒙特卡罗方法的基本思想，要想用“试验”的方法求出函数p 的概率分布概率分布，就要在函数表达式满足的定义域内，随机的抽取每一个随机变量二，并把它带入表达式f （x ）中，进而求出函数p 的值。由于变量：的值是在一定的定义域内随机抽取的，所以经过多独立的模拟试验后，可以得到相应的抽样数据Pi 。当对变量：进行模拟抽取的次数足够大 第一步：构造或者描述概率过程。在实际的应用中，有些问题不具有随机性质，比如计算多重积分问题，偏微分方程的边值求解问题等。使用传统的计算方法求解这些问题比较困难，为了能利用蒙特卡罗方法求解，就需要人为的设计一个概率过程，并且该概率过程要能很好的描述该事件的发生，同时把要求问题的解设置为该概率过程的某些参数。对于本身就具有随机性质的问题，其主要任务是如何准确的描述和模拟这个概率过程。把不具有随机性质的问题，通过特定的模型转化为具有随机性质的问题，是蒙特卡罗方法应用和研究的主要问题之一。 第二步：实现从已知概率分布中抽样。由概率论的知识可知，各种各样的概率分布都可以按照一定的方式构造出相应的概率模型。当概率 模型构造完成以后，如何准确的产生己知概率分布的随机变量，就成为实现蒙特卡罗方法的关键步骤。从另一个方面来讲，如何产生合适的随机变量也是蒙特卡罗方法随机抽样原理的重要体现。通常情况下，一个最典型的概率分布是（0，l ）区间上的均匀分布。同时，这种分布也是最简单的概率分布，在这种分布上产生的随机变量就是我们常说的随机数。具有相同分布的随机数构成的一个序列就是随机数序列，随机数序列中的各个子样都是相互独立的。因此，随机数的产生问题，就演化为从己知的概率分布中抽样的问题。随机数的独立性就保证了抽取的样本是若干次独立的试验，这样就保证了样本的多样性。具有这些特性的样本总体就能准确的表达相应的概率分布，这就是蒙特卡罗方法的重要特征。 第三步：建立各种估计量。通常情况下，要实现蒙特卡罗模拟试验，首先要构造概率模型，然后从已经的概率分布中抽样，最后还要设置一个合适的随机变量。使该随机变量恰好是所求问题的解，我们称之为无偏估计。在前两步的基础上，建立各种估计量，相当于对模拟实验的结果进行考察和登记，进而得到所求问题的解。 3 粒子滤波的基本原理 3.1 序列重要性采样 序列重要性采样算法，是一种通过蒙特卡罗模拟实现递推的贝叶斯滤波的技术。它的主要思想可以描述为：利用一系列随即样本的加权和来表示所需状态的后验概率密度，进而得到状态的估计值。当样本点增至无穷大时，蒙特卡罗特性与后验概率密度的函数表示等价，515滤波器逼近最优的贝叶斯估计。重要采样技术是一个关键的步骤，因为粒子的权值就是根据重要采样技术来选择的，所以提议分布的设计是一项重要的工作。如果粒子是根据重要密度q （x0：k|z0：k ）选择的，那么粒子的权值可以表 示为： 预测阶段：