改进的交互多模型粒子滤波算法
摘要
目标跟踪是研究目标运动不能被准确描述的目标运动估计的问题，它被广泛的应用于航海、航空以及安全防御等领域的跟踪、定位以及目标拦截等系统中。目标跟踪的主要内容包括建立能够准确地描述目标运动状态的数学模型和设计与之相匹配的能够进行精确地状态估计的滤波算法。
由于现代目标跟踪问题变的越来越复杂，机动性越来越高，所以对于目标跟踪算法的跟踪性能的要求也越来越高。到现在为止，科学家们提出了很多的建模方法，例如匀速直线运动模型、匀加速直线运动模型、机动转弯模型等。其中近年来提出的交互式多模型(Interacting-Multiple Model, IMM)算法在解决机动目标跟踪问题时最为有效，IMM算法是利用假设的描述目标机动方式的多模型来实进行目标均衡跟踪。传统的IMM算法的子模型通常选用卡尔曼滤波器。然而,交互多模型算法中,即使上一时刻每个模型的状态后验概率密度为高斯分布,但交互后的概率密度将变成非高斯分布的形式,因为卡尔曼线滤波算法要求状态空间模型为线性高斯白噪声模型，所以传统的IMM算法的应用具有一定的局限性，所以需要研究相适应的匹配滤波算法。
在目标跟踪领域，早期提出的比较实用的状态估计算法是适用于线性系统的卡尔曼滤波算法和适用于非线性系统的扩展卡尔曼滤波
算法。卡尔曼滤波器是最小均方意义下的最优滤波算法，四十多年以来一直是用来解决线性高斯环境下机动目标跟踪问题的最佳递推贝叶斯估计器。后来随着研究的深入，对非线跟踪系统的研究越来越多，科学家又提出了改进的卡尔曼滤波器。卡尔曼滤波算法是利用泰勒展开式将非线性部分线性化得到的一种次优贝叶斯估计滤波算法，在非线性不是很大的情况下，该算法近似于最优贝叶斯估计。但是当系统的非线性增大时，泰勒展开式的一阶和二阶方程都不足以描述目标的运动状态，并且鉴于其只限于高斯白噪声系统的局限性，所以科学家提出了各种能够适应于现代复杂机动目标的滤波估计算法其中适用于非线性非高斯噪声的粒子滤波算法较好。
粒子滤波算法是一种递推的次优贝叶斯估计算法，它是通过蒙特卡罗模拟来实现的。它在强非线性或者高度机动性的目标情况下的滤波性能指标很高,精度可以逼进最优估计并且使用灵活、容易实现以及具有并行运算结构和实用性强的特点，所以在目标跟踪领域具有广泛的应用。
本文主要对结合了结合了交互式多模型算法和粒子滤波算法的各自优点的互多模型粒子滤波算法进行了深入的研究。通过研究目标建模方法和滤波估计理对交互多模型粒子滤波算法的算法原理进行详细的描述和分析，然后介绍了交互多模型与粒子滤波算法相结合应用在强非线性条件下并和以往的与KF算法和EKF算法相结合的传统的交互多模型算法的滤波性能进行比较，由于现在的交互多模型粒子滤波算法还不是非常成熟，其中仍然存在许多问题，所以在一些方面
需要进行改进。本文主要针对交互多莫粒子滤波算法进中如何建立基于粒子的模型概率更新方法的问题进行研究。通过调整目标状态方程的似然函数来调整粒子权重值，使得采样粒子更加接近状态真实值，从而使后验概率的估计更加准确得到的机动目标跟踪的估计结果更加精确，并通过仿真仿真实验比较各种各种目标跟踪方法，证明了IMMPF的优越性。
关键词：机动目标目标跟踪算法，粒子滤波算法，交互多模型算法，交互多模型粒子滤波算法
第一章绪论
1.1 课题研究的背景及意义
无论是在人类社会中域还是在自然界，目标跟踪问题都是一个基本的问题。在大自然中，动物通过气味、痕迹等方法来搜寻猎物，寻找同伴等都涉及到了目标的定位跟踪问题；在人类社会中尤其是在军事领域，目标跟踪问题更是无处不在，从古到今跟踪方法从原始的烽火传递到现代先进的卫星雷达各种目标跟踪方法层出不穷。
在五十年代就有学者提出了目标跟踪这一概念，但是由于没有合适的目标跟踪算法使得在这一领域在早期并没有很大的发展。后来卡尔曼滤波算法的提出和在这一领域的应用使得目标跟踪算法得到了实际的应用，并且越来越多的人开始关注和研究目标跟踪问题。随着研究的深入，科学家又提出了其他的应用更加广泛的目标跟踪算法包括建模算法和滤波算法等算法。随着这些新技术的出现，目标跟踪算法结合了这些新技术的许多新方法也被提出，并且取得了长足的进步。尤其是近几十年来随着计算机运算能力的不断提高，将交互式多模型建模算法和粒子滤波算法相结合的交互式多模型粒子滤波算法在解决机动目标跟踪问题方面的优越性也越来越明显。
目前世界各国都在大力发展军事、航海、航空和航天事业，目标跟踪系统无论是对于军事方面的攻击和防御系统还是在航海、航空和航天方面的轨道运行和目标定位系统中都属于不可或缺的部分。另外在民用方面，目标跟踪也被应用在交通管制、人脸识别和车牌识别等很多方面。
基于上述讨论，无论在军事上还是民用上对目标跟踪进行理论上和应用上的研究研究都有着重大的意义。针对现代机动目标跟踪问题中目标的机动性增大，非线性变强的问题，对于交互多模型粒子滤波算法这种最近猜题出来的目标跟踪方法的研究有着重要的实际意义和重要价值。
1.2 交互多模粒子滤波算法的发展现状
在当今国际上,目标跟踪依然是非常活跃的热门领域之一。无论是对于现代军事防御还是对于海上和空中交通管制系统，机动目标跟踪都是不可或缺的重要技术。尤其是近现代以来，航海、航空和航天事业的蓬勃发展以及现代战争的信息化和网络化的不断发展，都使得各国越来越重视对机动目标跟踪技术的研究，现在机动目标跟踪问题已经成为一个活跃的研究领域。
现在随着科学技术的不断发展，目标的机动性越来越大而且在目标跟踪中对跟踪精度和实时性的要求也越来越高,所以目标跟踪算法为了获得较高的跟踪精度,需要建立
与目标运动形式相匹配的模型,并根据模型特性(如线性、非线性、机动性能等)选取合适的滤波算法。图1-1为目标跟踪发展的基本概况。从图1-1，我们可以看到目标跟踪系统的研究包括滤波估计和模型建立两个方面，随着目标本身的机动特性和非线性的不断提高，对滤波算法和目标模型的算法的研究也受到越来越多的重视。这两方面的研究既相互独立又相辅相成。应用滤波器解决机动目标跟踪问题的关键是要精确的建立机动目标模型。
“机动目标跟踪”中的‘机动’是指所观测的目标在飞行或航行时突然出现的变速、转向等变化的运动。由于机动通常是随机的、突然发生的，而且机动大小也是未知的，所以很难准确地实时地建立机动目标的运动学模型。所以为了能够在机动目标跟踪算法中准确地建立目标模型，人们提出了各种建立机动目标运动模型的方法，其中在1990年由Blom和Bar-Shalom 提出的基于广义伪贝叶斯算法的采用马尔科夫转移概率进行模型切换的交互式多模型(Interacting multiple model,IMM)算法最为有效,利用该模型来解决目标机动模式与其数学模型失配的问题[5]。标准的IMM的各个模型匹配的滤波器都是KF或EKF,虽然使得该算法的计算简单并且计算量小,但是由于滤波器本身存在线性化误差,且不适用于非高斯问题，使得该算法估计精度不高。
过去的30多年中，人们提出了许多非线性滤波算法来解决非线性非高斯性滤波问题。其中，PF算法是从非高斯、非线性、高维的观测数据中计算后验概
率的一种非常方便而有效的方法。由于该方法容易实现、非常灵活、使用性强，很好地解决了目标跟踪中的非线性非高斯问题[5]。所以将PF算法与IMM的模型相匹配来处理现代机动目标跟踪中所出现的非线性、高机动性的问题。正如图1-1所示的结合了PF和IMM的算法即是后来提出的交互式多模型粒子滤波(Interaction multiple model particle filter,IMMPF)算法[5]。
目前, IMMPF算法在目标跟踪领域已经取得了长足的进展，它在解决非高斯环境下的机动目标跟踪问题上具有非常乐观的应用前景,而且逐渐地延伸到故障诊断等领域,形成了很多有价值的理论和实践成果。然而IMMPF算法仍然处于发展和完善阶段,算法本身还存在许多问题，需要我们继续进行研究和改进。
1.3 本文的主要内容
本文主要针对交互多模型粒子滤波算法在机动目标跟中的应用进行研究。研究方面主要包括机动目标跟踪中的数学建模问题，滤波估计问题，以及交互多模型粒子滤波算法的理论，针对IMMPF算法存在的问题进行研究，并提出相应的改进方法及其在机动目标跟踪中的应用。通过实验仿真证明改进的IMMPF算法的优越性。
1.3.1 目标跟踪算法
目标跟踪过程包括进行信号接收数据整理、建立运动目标的数学模型、进行机动性能检测、进行状态估计、设定适当的阈值（即跟踪门）以及进行数据反馈和修正，最后根据得到的相关的航迹起始与终止结合预测估计值输出处理后的信号，图1-2为机动目标跟踪系统的基本流程框图[6]：
如图1-2描述，进行机动目标跟踪的工作可以具体概括为以下四个方面： (1)建立适当的数学模型描述机动目标的运动状态：根据目标机运动状态的特点建立相应的目标模型，设定目标的相关参数如速度、加速度、位移以及噪声等。在论文中介绍了几种常见的目标跟踪模型包括描述直线运动的CV/CA模型以及描述机动目标运动的机动转弯模型等模型，并且重点介绍了交互多模型（Interaction multiple-model）理论及其算法原理，并且通过仿真实验对比IMM 与CV模型和CA模型的的跟踪性能。
(2)量测数据形成与检测：在这一环节中是利用目标跟踪系统的前端设备对目标的相关信息进行收集并进行整理，将一些错误信息进行剔除。
(3)选择目标跟踪坐标系：在进行机动目标跟踪建模时，首先需要准确地选取合适的坐标系。在课题研究中，主要用到的坐标系是直角坐标系，它可以直观的反应目标的运动轨迹以及跟踪系统的跟踪效果。
(4)选择合适的滤波器：滤波器是目标跟踪系统的核心，建立精确的滤波算法是准确地跟踪运动目标的关键。在论文第三章介绍了滤波估计的算法原理，介绍了几种常见的滤波算法，其中重点介绍了传统的滤波算法如应用于线性的KF 算法和使用与非线性的EKF算法以及粒子滤波算法，并且通过仿真分析对这几种滤波算法的滤波性能进行比较。从而证实了粒子滤波算法适用于非线性高斯噪声系统。
现代目标跟踪领域里，随着科学技术的发展，目标的机动性和非线性不断增加，对于目标跟踪系统的跟踪精度的要求也越来越高，因此最新提出了交互多模型粒子滤波（Interaction Multiple Model- Particle Filter,IMMPF）算法,并对其进行深入的研究。
1.3.2 交互多模型粒子滤波算法
图1-1所表示的交互多模型粒子滤波理论的形成过程，可以看到IMMPF算法结合了IMM算法善于处理高机动目标跟踪问题和PF算法善于处理非线性系统的优点。IMMPF算法还处在发展和完善阶段，所以还需要继续进行研究和改进。
交互多模型粒子滤波理论是在机动目标跟踪算法不断的改进和发展的过程中形成的。论文主要介绍了交互多模型粒子滤波算法原理以及该算法的推导过程。在课题研究时指出当前IMMPF算法存在的问题，并对其进行分析。本文主要针对交互多模型粒子滤波算法在滤波过程中存在的采样粒子退化的问题提出改进的交互多模型粒子滤波（Improved IMMPF）算法。
Improved IMMPF 算法是在传统的交互多模型粒子滤波的基础上进行改进的。它主要是从似然函数和采样粒子的关系方面进行研究。
传统交互多模型粒子滤波算法在进行粒子滤波过程时，通常是选取先验概率密度函数作为重要性密度函数。这样将先验概率密度函数作为重要性密度函数的
方法使得滤波算法的计算量减小，实时性变的更高。但是这种方法也有一定的缺点即由量测值计算得到的当前时刻的状态过于的依赖于所建立的目标模型[8]。假如建立的目标模型不是非常精确，或者测量噪声突然增大，那么该方法就不能准确地表示概率密度函数的真实分布。解决的办法是设法将粒子向似然函数的峰值区移动，或采用其他更合适的建议分布，用似然函数作为建议分布，用先验概率密度作为迭代的比例因子。本文对改进的IMMPF算法进行了详细的介绍，同时研究了Improved IMMPF算法在机动目标跟踪中的应用，并且通过仿真实验分析与传统的交互多模型粒子滤波算法的跟踪性能进行比较，进一步证实了Improved IMMPF算法的滤波性能及其应用于机动目标跟踪问题的价值。
1.4 论文章节安排
全文包括六章，具体内容安排如下：
第一章绪论是引言部分主要介绍了目标跟踪算法的研究背景及意义、IMMPF算法的研究现状、论文主要研究内容以及论文的章节安排。
第二章介绍机动目标跟踪模型的基本理论知识，重点介绍交互式多模型算法。
第三章介绍滤波算法的原理和滤波估计理论然后介绍了几种滤波算法包括卡尔曼滤波算法、扩展卡尔曼滤波算法和粒子滤波算法，对几种常见的滤波算法的性能进行比较。讨论了粒子滤波算法存在的一些问题。
第四章具体介绍交互式多模型粒子滤波算法原理以及其存在的问题以及针对其在滤波过程中出现的采样粒子匮乏退化问题提出的改进的交互多模型粒子滤波算。
第五章介绍改进的交互多模型粒子滤波算法在机动目标跟踪中的应用。进行实验仿真，建立三维坐标下的机动目标运动模型，利用交互多模粒子滤波器对运动目标进行跟踪，并对传统交互多模型算法和改进后的交互多模型算法的估计结果进行比较。
第六章最后进行对论文工作和问题做了总结叙述。
第二章机动目标跟踪模型
在机动目标跟踪问题中，能够建立准确的机动目标跟踪模型是对目标进行准确地预测估计的基础。在进行目标跟踪时，首先需要准确地建立目标运动模型。目标跟踪是建立在各种跟踪数学模型上的分析讨论，能否建立相应的适当的目标模型会直接影响跟踪性能的好坏。首先目标当前的运动状态的估计就是通过目标模型得到的而且滤波器也是在目标模型的基础上进行估计预测的，所以目标模型的建立是非常重要的。以下小节将对其进行详细的介绍。
2.1 机动目标数学模型
目标跟踪算法都是以建立的目标运动模型为基础的，尤其是卡尔曼滤波理论。因此需要要对目标跟踪的运动模型进行讨论。在论文中研究的目标跟踪问题主要是指机动目标跟踪的问题，所以在这里主要介绍机动目标跟踪模型的建立。那么如何准确地建立目标跟踪的数学模型呢？建立目标模型的原则是既要符合目标的实际运动状态，又要便于对机动目标进行实时性的处理。当遇到作非机动运动的目标时，目标运动的数学模型很容易建立;但当目标做机动运动时，简单的的数学模型将不能满足目标跟踪算法的需要。因为在通常情况下，我们对做机动运动的目标的运动状态的先验知识知道的很少，所以很难用传统的数学模型对其进行精确地描述，只能根据经验对目标运动状态进行假设，然后用近似的方法对其运动状态进行描述[9]。
目标的运动模型的数学表达式包括两部分，第一部分是运动状态模型方程，第二部分是量测模型方程。运动目标的状态方程用来描述目标的运动状态变量、状态噪声变量随时间变化的递推关系，量测方程描述了量测数据与状态变量、量测噪声之间的函数关系。将这两部分的公式结合进行运算将目标运动状态的先验信息及其预测估计值与测量得到的值相比较，从而得到其估计的残差的值，通过残差值的大小来评估预测性能的好坏，从而得到其似然函数对其进行修正和预测。下面分别详细介绍连续时间跟踪系统和离散时间跟踪系统的数学模型的方程表达式。
公式（2-1）和公式（2-2）分别表示连续时间目标跟踪系统的状态模型和量测模型的数学表达式[9]。
(2-1)
(2-2)
在公式（2-1）和公式（2-2）所表示的目标模型的数学表达式中，表
示所表示运动目标的状态变量；表示所表示目标的量测变量；是状态变量转移矩阵，它表示由先验变量与当前时刻状态变量的递推关系；
是量测变量转移矩阵它表示状态变量与量测变量之间的数量转换关系。这两个转移矩阵可以是时变的也可以是非时变的；表示过程状态噪声转
移矩阵；和分别表示所建立模型的状态噪声和量测噪声，在论文的课题研究中，状态噪声和量测噪声都分别假定为互不相关的零均值高斯白噪声向量，其协方差矩阵分用和表示。
公式（2-3）和公式（2-4）是离散时间目标跟踪系统模型的数学表达式
(2-3)
(2-4)
同理，式中，，和所表描述的变量时一样的，分别表示运动目标的状态变量，量测变量，状态噪声和量测噪声，只是这些变量都是在离散时刻k的变量值。同时，表示状态转移矩阵，描述了k-1时刻的状态变量到k时刻的状态变量之递推的转变关系。是量测转移矩阵，与连续时间的量测转移矩阵的意义一样。这两个转移矩阵既可以是时变的也可以是非时变的。
目标跟踪系统中滤波器的设计通常是以系统所建立的运动模型为基础的，在该小节开始就介绍到目标模型的建立对跟踪系统的跟踪精度有很大的影响。所以需要建立合适的目标运动的数学模型。目标运动数学模型的状态方程和量测方程都是以移动的坐标系为依托的。坐标系的选择很大程度上影响了目标模型的准确
性，选择一个合适的坐标系可以是滤波估计过程中的估计代价大大减少。所以在选择目标模型所用的坐标系时，也需要根据目标的机动性能慎重考虑。
在本文中主要讨论IMMPF算法及其改进算法在机动目标跟踪中的应用，为了能够准确简便地描述被跟踪目标的机动变化，所以利用最直观的直角坐标系来建立目标运动的数学模型。通过MATLAB仿真形象的描述了目标做直线运动，转弯运动等具体的运动状态。现在借助现代的雷达卫星等先进的探测技术可以得到目标运动的准确信息，例如目标的运动速度，运动角度以及运动位移等，它的相对运动参数如图2-2所示。
其中，、和分别表示观测站ο到目标M的距离、目标M的方位角和目标M的高低角。
本文在进行仿真分析时，将上述目标运动参数分别用公式（2-2）到公式（2-4）所示的状态方程和量测方程中的状态变量和量测变量表示。其中，目标M的运动对应的x坐标值、y坐标值和z坐标值等分别用状态变量表示，
速度，映射M
1
值、值和值等分别用量测变量来表示。根据所设定的目标空间在直角坐标系中表示出相关的运动参数。通常情况下状态模型建立在在直角坐标系中，量测模型建立在球面坐标系，在实际中，为了操作方便需要统一坐标系具体方法是通过坐标变换把建立在球面坐标系中的量测方程变换到直角坐标系中[10]。
2.2 CV/CA模型
在第一小节中已经介绍过目标运动模型对于解决目标跟踪问题的重要性，建立目标模型的原则是建立的运动模型既要符合运动目标的实际机动情况，又要便于进行运算仿真操作。在这一小节主要介绍两种最简单的也是最基本的目标模型，即在绪论中提到的CV模型和CA模型。
建立CV模型和CA模型是假设在目标没有发生机动的理想情况下建立的目标模型，实际上所有的运动目标都会发生机动，在这里将目标的机动性看成是目标受到随机干扰，以噪声的形式描述。
在建立的CV模型和CA模型中，目标运动状态的数学表达式分别用公式（2-5）和公式（2-6）所表示的二阶方程和三阶方程表示。
(2-5)
（2-6）
在公式（2-5）和公式（2-6）中模型变量、和分别表示
运目标的某一方向上的位置、速度和加速度分量；在CV模型和CA模型中
的噪声分别表示目标收到的随机干扰即速度变化和加速度变化。
当物体做匀速直线运动或匀加速直线运动时，采用CV模型和CA模型的目标跟踪系统的跟踪性能很高。然而当目标的机动性和非线性变的很大时，如果仍然将目标发生的机动变化设成是随机噪声变量，则会出现很大的误差，这时需要考虑目标的机动状态。若事先已经知道目标的机动特点，即知道目标运动的加速度和变加速度的特性时，则直接将目标运动目标的加速度和变加速度
参数数字化然后代替，得到的目标模型应分别表示为公式（2-7）和公式（2-8）：
(2-7) 和
(2-8)
同理假设目标分别做一维的匀速直线运动和匀加速直线运动，离散时间跟踪系统的CV模型和CA模型的数学表达式如公式（2-9）和公式（2-10）所示：
(2-9)
公式（2-9）中的和分别是状态方程在k时刻和k-1时刻的状态变
量，对应于公式（2-5）中的变量，其中和分别表示目标的位置参数和
速度参数；假设为目标在k时刻所受到的随机扰动，是指速度的变化。T 表示在进行目标跟踪过程中获取数据所设定的时间间隔，称为采样周期，通常设为1s。
(2-10) 与公式（2-9）所表述的意义基本相同，公式（2-10）中和分别
对应于公式（2-6）中的变量，其中为目标的加速度分量，也假设
为目标在k时刻所受到的随机扰动，只是它表示加速度的变化。
同理在预先知道k时刻目标运动的加速度和变加速度的特性，则直接将目标运动目标的加速度和变加速度参数数字化然后来代替，可得到如公式（2-7）和公式（2-8）的形式的离散时间模型的数学表达式。
虽然用CV模型和CA模型的计算量小适合于实时跟踪，在过去经常用于解决目标跟踪问题，但是随着科学技术的发展，目标跟踪问题变的越来越复杂，跟踪系统中所跟踪目标的运功状态即目标的机动并不是预先知道的，而且目标的机动性和非线性越来越大，使得CV/CA模型不再适用于一般的跟踪系统。那么如何准确地描述目标的机动性呢？这是一个复杂的问题，于是还需要了解一些其他模型，如时间相关模型、半马尔可夫模型、Noval统计模型等模型。
2.3 其它模型
该小节介绍的是人们针对CV/CA模型存在的问题进行的研究。在不断的研究和修改过程中提出了几种新的目标跟踪建模的方法，这些方法也体现了建立目标模型方法的发展过程，下面分成几个小节分别对这几种方法进行简单的介绍。2.3.1 时间相关模型
时间相关模型是针对所跟踪的目标具有机动性但是机动性不是很大的问题提出的数学建模方法，在这里以连续时间跟踪系统为例对其进行介绍。目标的机动性能未知，所以我们首先假设一个值，假设它服从一阶时间相关过程，设定其时间相关函数为指数衰减形式，如公式（2-11）所示，
(2-11)
其中，表示做直线运动的目标加速度的方差;表示目标运动状态发生变化的机动频率。
在公式（2-11）中，假设的加速度均值为零，它的概率密度函数近似服从均匀分布，所以这里可以近似通过均匀分布的概率密度来计算得到其表达式，如公式（2-12）所示。
(2-12)
这里是通过经验值来取值，其中表示估计的最大机动加速度；表示
发生的概率；表示目标做非机动运动的概率。
即时间相关函数经过公式2-11和公式2-12的修正白化后，可以将目标的机动加速度表示为输入白噪声的一阶时间相关模型如公式（2-13）所示，
(2-13)那么目标的机动目标模型就可以由公式（2-14）来表示。
(2-14)
在上面公式中，则被设为白噪声（均值为零，方差为）。
上面介绍的时间相关模型是以一阶时间相关模型为例，一阶时间相关模型采用有色噪声建模比用白色噪声建模更加接近目标运动的实际情况，但是当目标的速度或加速度大小不确定时，这种建模方法会使目标跟踪结果出现很大的误差，所以需要更高阶时间相关模型，但是随着阶数的增大，目标跟踪的实时性会变差。
2.3.2 半马尔可夫模型
鉴于上面介绍的时间相关模型存在的问题，为了增加目标跟踪的准确性和实时性，对目标模型的建立进行了进一步的研究，提出了新的目标跟踪建模方法即该小节标题-半马尔可夫模型，该模型采用的是可以使机动加速度的零均值随时进行中断和执行的相关高斯噪声。马尔科夫模型是利用马尔可夫过程所设定的一系列有限的指令来描述目标发生的机动，这些指令通过马尔可夫转移概率来进行转移结合从而得到目标的近似运动状态，转移时间为随机变量所以可以根据具体的运动情况得到较准确的目标跟踪模型。。设定目标转移概率得到的半马尔科夫模型可被表示为公式（2-15）所示的数学模型。
(2-1
5)其中，o表示目标运动时遇到的阻力系数；表示建立模型时设定的确定的输入指令；不是前面公式中表示的加速度等机动变换它在这里表示机动频率；与前面描述的意义相同是指高斯白噪声。
半马尔可夫模型的主要差别与CV/CA模型的是半马尔可夫模型引入了非零加速度u(t)，来解决目标机动性不确定的问题，但是当目标的机动性非常大时，模型中所设定u(t)来解决目标机动性问题的方法还是不能满足越来越复杂的目标跟踪问题。
2.3.3 Noval统计模型
在前面介绍的三个目标跟踪模型都是假设目标做近似直线运动，但是实际目标运动时不一定是直线运动，所以针对这一问题专家提出Noval统计模型。该模型是将目标做机动运动时的法向加速度假定成是非对称的时间相关过程，设
的概率密度的非对称性为如公式（2-16）所表示的确定性非线性函数。
(2-16)公式中，、、是常数，他们分别对应于目标特定情况和特定类型；
表示零均值时间相关高斯随机过程，用公式（2-17）表示，
(2-17)
在公式（2-17）中，表示机动频率，表示高斯白噪声(均值为零，方差为)。
根据跟踪目标的特点设定b、c和d三个目标常数的值，通过公式（2-16）和公式（2-17）就可以推算得到该运动目标加速度概率密度的法向量的确定值。虽然该建模方法是描述的运动状态是非线性的，但是其还是在线性思想上得到的，其理论还是受到原始的建立线性模型原理的影响，在解决高机动目标跟踪问题时还是具有一定的局限性。
2.3.4 机动目标“当前”统计模型
机动目标“当前”统计模型，是利用目标的先验知识来预测和修正后验知识的原理来设计目标模型的。他是利用目标当前已知的运动加速度值来限定和修正下一时刻的目标加速度值，使得下一时刻的目标加速度是值属于当前加速度值可误差范围内的值。这一小节介绍的机动目标“当前统计模型”本质上是一个非零均值的时间相关模型。加速度的“当前”概率密度是通过修正的瑞利分布来描述的，它的均值等于“当前”加速度的预测值，具体的模型描述如公式（2-18）所示：
(2-18)
(2-19)
在公式（2-18）和公式（2-19）中，表示“当前”加速度的均值，在进行运算时设成是常数。
在机动目标建模时设，将其代如公式（2-18）和（2-19），可得到与当前时刻的表达式为，进而推导出当前统计模型的数学表达公式如（2-20）所示。
(2-20)
该模型在描述目标的运动状态时采用上面所述的方法更能形象的描述目标的机动性问题，准确地反应目标加速度变化范围。但是由当前加速度限制和修正下一时刻加速度的时候，当遇到机动变换较强时，其跟踪性能还是有待提高。
2.3.5 机动转弯模型
机动转弯模型是在机动目标Noval统计模型的基础上进行改进的，该模型通过设定目标的转弯速率来设定加速度的法向加速度分量的大小，根据2.1小节可假设目标的状态变量为，则通过带入目标运动模型进行推导可以得到目标的转弯模型如公式（2-21）表示。
(2-21)
式中表示系统的采样时间，表示过程噪声。
2.4 交互式多模型
2.4.1多模算法发展概述
随着目标跟踪问题变的越来越复杂，人们提出许多新的建模方法，除了前几节提到的几种建模方法外，近年来提出的多模型（Multiple Model, MM）跟踪算
法受到人们的广泛关注。多模型建模方法类似于结构控制系统，首先是建立机动目标模型和非机动模型，这两个模型是根据先验知识进行假设建立的；然后通过一定的方法根据目标运动实际运动状态使跟踪模型进行相互转换。在前面我们介绍了非机动目标运动模型如CV/CA模型以及机动目标模型如机动转弯模型，那么接下来，如何进行模型转换呢？一种是目标检测器设计方法，利用可操纵的检测控制器控制滤波算法在机动模型和非机动模型之间进行转变。但是这中转换方法计算量很大，使得跟踪的实时性变差。另一种切换方法是利用似然函数计算确定下一时刻采用哪种目标运动模型，利用这种似然函数通过转换概率比较来确定模型的方法使得计算量变小。
在前面几节主要介绍的是单模型目标跟踪算法，在该算法中只是使用单一的模型，所以当目标机动性很大时，跟踪算法的精确度很低，所以多模型的提出在很大程度上弥补了这一缺点。多模型算法设定多个目标模型，通过一定的方式使滤波器在不同的模型之间进行切换，使得跟踪算法能适应越来越复杂的机动目标。多模型的这一优点使得它受到越来越多的关注和重视，现在很多人开始研究这种建模方法。
MM跟踪方法是当前混合系统估计算法常用的一种建模方法。MM模型算法的优点如下：
(1)该建模方法采用多个模型相结合来描述目标的运动状态，使得对运动状态的描述更加精细。
(2)在状态估计过程中，通过模型间的转移概率来对模型间的切换进行自适应调整。
(3)如果能够精确的设定目标的先验条件，则其估计误差可以近似达到最优估计。
(4)该算法是并行结果便于进行实际操作。
1956年Magill 最先提出的MM算法，主要使用几个不同的目标模型，每个模型都使用卡尔曼滤波器进行并行工作，再对输出结果进行数据融合，但是各个模型之间没有进行交互，所以在目标的运动状态极不稳定的情况下，其跟踪算法的自适应能力就会变差，使得它的跟踪性能也随之下降。针对以上问题，科学家开始考虑模型之间的相互转换问题，如何对MM中的目标进行交互交？两种比较有效的解决方法是在1970年由Ackerson和Fu提出的年提出的，广义伪贝叶
斯算法和1988年由Blom和Bar-Shalom提出的交互式多模型算法。这两种方法都是对MM中的模型进行交互，但是交互方式不同。两种方法中交互多模型算法更为合理有效，近几年来在目标跟踪领域的应用较为广泛。在2.42小节中，对交互式多模型算法进行了详细的介绍。
2.4.2 交互式多模算法
交互多模型（Interaction Multiple Model,IMM）算法是在2.41节介绍的多模型算法的基础上进行改进的。将MM算法中有限个数的目标运动模型之间进行转换的系数利用马尔科夫链设定，利用由状态值和量测值得到的残差通过建立的马尔科夫模型对目标的运动模型进行自适应调整。
传统的交互式多模型算法的原理是根据目标不同的运动状态建立多个不同的目标模型，然后通过建立的马尔科夫模型通过目标模型间的转移概率使滤波器在建立的不目标模型间进行切换，在这里使用的滤波算法主要是卡尔曼滤波算法，转移概率通过残差序列进行调整，下面是交互多模型算法的主要算法结构。
（1）根据目标的不同运动状态建立不同运动模型，有限个运动模型组成模型集；
（2）选择合适的滤波器，设定适当的滤波参数，在传统的交互式多模型算法中主要选择卡尔曼滤波器作为跟踪模型的滤波股计算法；
（3）对跟个模型输出的滤波估计结果进行数据融合。
IMM的运算步骤包括输入交互，滤波估计，数据融合和输出交互。下面分别对交互式多模型(IMM)算法的运算步骤进行详细说明。
（1）输入交互和滤波估计
对k-1时刻IMM算法的数据输出进行数据融合并将其作为k时刻每个模型的滤波器的滤波循环输入。融合数据即k-1时刻的总体估计包含所有滤波器在k-1时刻的估计结果，这些滤波器再通过数据融合得到的总体估计结果来进行输入交互。则进行初始化的k时刻的子模型的滤波估计的状态协方差和条件预测值如公式（2-22）和公式（2-23）所示。
(2-22)
(2-23) 残差调整值和k时刻残差的方差值如公式（2-24）和公式（2-25）所示。
(2-24)
(2-25) 在传统的IMM目标跟踪算法通常是由卡尔曼滤波器对目标进行状态估计，下面公式(2-26),(2-27)和公式（2-28）表示卡尔曼滤波算法的基本方程。
(2-26)
(2-27)
(2-28) （2）切换概率计算
似然函数的计算如（2-29）所示
(2-29)
假设系统为高斯系统，则其似然函数可根据公式（2-30）进行计算。
(2-30)
计算模型概率
(2-31)
其中
(2-32)（3）数据融合
通过公式（2-31）得到的模型概率计算k时刻的总体估计值和总体估计误差的协方差矩阵，具体计算公式如公式（2-33）和公式（2-34）所示。
(2-33)
(2-34)
第37卷第4期河北工业大学学报2008年8月V ol.37No.4JOURNAL OF HEBEI UNIVERSITY OF TECHNOLOGY August2008 文章编号：1008-2373(2008)04-0055-05 改进的粒子群优化算法 宋洁，董永峰，侯向丹，杨彦卿 （河北工业大学计算机科学与软件学院，天津300401） 摘要粒子群优化算法是一种基于群体的自适应搜索优化算法，存在后期收敛慢、搜索精度低、容易陷入局部极 小等缺点，为此提出了一种改进的粒子群优化算法，从初始解和搜索精度两个方面进行了改进，提高了算法的计 算精度，改善了算法收敛性，很大程度上避免了算法陷入局部极小．对经典函数测试计算，验证了算法的有效性． 关键词粒子群优化算法；均匀化；变量搜索；初始解；搜索精度 中图分类号TP391文献标识码A A Modified Particle Swarm Optimization Algorithm SONG Jie,DONG Yong-feng,HOU Xiang-dan,Y ANG Yan-qing (School of Computer Science and Engineering,Hebei University of Technology,Tianjin300401,China) Abstract Particle Swarm Optimization Algorithm is a kind of auto-adapted search optimization based on community. But the standard particle swarm optimization is used resulting in slow after convergence,low search precision and easily leading to local minimum.A new Particle Swarm Optimization algorithm is proposed to improve from the initial solution and the search precision.The obtained results showed the algorithm computation precision and the astringency are im- proved,and local minimum is avoided.The experimental results of classic functions show that the improved PSO is ef- ficient and feasible. Key words PSO；average；variable search；initial solution；search accuracy 0引言 粒子群优化（Particle Swarm Optimization，PSO）算法是一种基于群体的随机优化技术，最早在1995年由美国社会心理学家James Kennedy和电气工程师Russell Eberhart[1]共同提出，基本思想源于对鸟群觅食行为的研究．PSO将每个可能产生的解都表述为群中的一个微粒，每个微粒都具有自己的位置向量和速度向量，和一个由目标函数决定的适应度，通过类似梯度下降算法使各粒子向适应度函数值最高的方向群游．该算法控制参数少、程序相对简单，因此在应用领域表现出了很大的优越性．由于PSO算法容易理解、易于实现，所以PSO算法发展很快．目前，多种PSO改进算法已广泛应用于函数优化、神经网络训练、模式识别、模糊系统控制以及其他的应用领域． 许多学者对PSO算法进行研究，发现其容易出现早熟、最优解附近收敛慢等现象，并提出了一些改进方案，例如自适应PSO算法、混合PSO算法、杂交PSO算法等[2-4]．因此，本文从初始解和收敛精度两个角度出发对PSO算法进行了改进，提高了算法的计算精度，有效的改善了算法的优化性能． 1基本PSO算法 PSO算法是一种基于群体的随机优化技术，基本思想源于对鸟群觅食行为的研究．通过对鸟群飞行时经常会突然改变方向、散开、聚集，但整体总保持一致性，个体与个体间鸟群好像在一个中心的控制 收稿日期：2008-04-17 基金项目：河北省自然科学基金（F2006000109） 作者简介：宋洁（1967-），女（汉族），副教授．
安康学院 学年论文（设计） 题目_____________________________________________ 学生姓名_______________ 学号_____________________________ 所在院（系）_______________________________________ 专业班级__________________________________________________ 指导教师_____________________________________________ 年月曰
基于粒子群优化算法的图像分割 （作者：） （） 指导教师： 【摘要】本文通过对粒子群优化算法的研究，采用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 引言 粒子滤波器，又称序贯蒙特卡罗方法。可以有效地处理非线性、非高斯滤波问题，广泛地应用在机动目标跟踪、信号传输与压缩、金融领域数据分析、图像处理、故障诊断等领域。所谓粒子滤波就是贝叶斯估计基于抽样理论的一种近似算法，通过非参数化的蒙特卡罗模拟方法来实现递推贝叶斯滤波，即通过一组动态状态空间上按贝叶斯准则进行更新的随机加权的样本或粒子，对未知状态的后验概率密度进行估计，其中这些粒子通过对后验密度序贯重
对于函数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)是一种进化计算技术(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、群智能算法研究背景 粒子群优化算法（Particle Swarm Optimization，PSO）是由Kennedy 和Eberhart 在研究鸟类和鱼类的群体行为基础上于1995 年提出的一种群智能算法，其思想来源于人工生命和演化计算理论，模仿鸟群飞行觅食行为，通过鸟集体协作使群体达到优。 PSO算法作为一种新的群智能算法，可用于解决大量非线性、不可微和多峰值的复杂函数优化问题，并已广泛应用于科学和工程领域，如函数优化、神经网络训练、经济调度、模式识别与分类、结构设计、电磁场和任务调度等工程优化问题等。 PSO算法从提出到进一步发展，仅仅经历了十几年的时间，算法的理论基础还很薄弱，自身也存在着收敛速度慢和早熟的缺陷。如何加快粒子群算法的收敛速度和避免出现早熟收敛，一直是大多数研究者关注的重点。因此，对粒子群算法的分析改进不仅具有理论意义，而且具有一定的实际应用价值。 2、国内外研究现状 对PSO算法中惯性权重的改进：Poli等人在速度更新公式中引入惯性权重来更好的控制收敛和探索，形成了当前的标准PSO算法。 研究人员进行了大量的研究工作，先后提出了线性递减权值( LDIW)策略、模糊惯性权值( FIW) 策略和随机惯性权值( RIW) 策略。其中，FIW 策略需要专家知识建立模糊规则，实现难度较大，RIW 策略被用于求解动态系统，LDIW策略相对简单且收敛速度快， 任子晖，王坚于2009 年，又提出了基于聚焦距离变化率的自适应惯性权重PSO算法。 郑春颖和郑全弟等人，提出了基于试探的变步长自适应粒子群算
法。这些改进的PSO算法既保持了搜索速度快的特点, 又提高了全局搜索的能力。 对PSO算法的行为和收敛性的分析：1999 年采用代数方法对几种典型PSO算法的运行轨迹进行了分析，给出了保证收敛的参数选择范围。在收敛性方面Fransvan den Bergh引用Solis和Wets关于随机性算法的收敛准则，证明了标准PSO算法不能收敛于全局优解，甚至于局部优解；证明了保证收敛的PSO算法能够收敛于局部优解，而不能保证收敛于全局优解。 国内的学者：2006 年，刘洪波和王秀坤等人对粒子群优化算法的收敛性进行分析，指出它在满足收敛性的前提下种群多样性趋于减小，粒子将会因速度降低而失去继续搜索可行解的能力，提出混沌粒子群优化算法。 2008 年，黄翀鹏和熊伟丽等人分析惯性权值因子大小对PSO算法收敛性所带来的影响，对粒子群算法进行了改进。2009 年，高浩和冷文浩等人，分析了速度因子对微粒群算法影响，提出了一种基于Gaussian 变异全局收敛的粒子群算法。并证明了它能以概率 1 收敛到全局优解。 2010 年，为提高粒子群算法的收敛性,提出了基于动力系统的稳定性理论，对惯性权重粒子群模型的收敛性进行了分析，提出了使得在算法模型群模型收敛条件下的惯性权重和加速系数的参数约束关系，使算法在收敛性方面具有显著优越性。在PSO算法中嵌入别的算法的思想和技术。 1997年，李兵和蒋慰孙提出混沌优化方法； 1998年，Angeline在PSO算法中引入遗传算法中的选择算子，该算法虽然加快了算法的收敛速度，但同时也使算法陷入局部优的概率大增，特别是在优化Griewank 基准函数的优值时得到的结果不理想； 2004 年，高鹰和谢胜利将混沌寻优思想引入到粒子群优化算法中，首先对当前群体中的优粒子进行混沌寻优, 再用混沌寻优的结果随机替换群体中的一个粒子，这样提出另一种混沌粒子群优化算法。
浅谈粒子群算法改进方法 【摘要】本文介绍了粒子群算法的基本概念及粒子群算法的训练过程，分别从基本进入、改变惯性因子、改变收缩因子三个方面对其进行优化改进。 【关键词】粒子群;进化方程;惯性因子;收缩因子 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
基于收缩因子的改进粒子群算法 陈国鸿 （河池学院计算机与信息科学系广西河池 546300） 摘要：针对基本粒子群优化算法(ParticleSwarmOptimization，简称PSO )存在的早熟收敛问题，提出了一种既保持粒子活性又保证粒子快速收敛于全局极值点的改进粒子群优化（XARPSO）算法。在算法运行过程中，如果种群多样性逐步减小，直至超出下限时，种群不再向整体最优位置靠近，而是纷纷远离该最优位置，从而执行了“扩散”操作，而当种群多样性逐步增大，直至超出上限时，种群又开始向整体最优位置靠拢，即执行了“吸引”操作，从而保持了粒子的多样性。同时，该方法引入收缩因子的概念，即通过正确选择惯性权重系数与加速常数即学习因子这些控制参数的值的方法，确保算法收敛。通过Goldstern-Price 函数的最小化测试结果表明，该算法不仅具有较快的收敛速度，而且能够更有效地进行全局搜索。 关键词：粒子算法；收缩因子；吸引；扩散；多峰值函数 引言 粒子群算法最早是在1995年由美国社会心理学家James Kennedy和电气工程师Russell Eberhart共同提出的，简称PSO算法。其基本思想是受他们早期对许多鸟类的群体行为进行建模与仿真研究结果的启发。粒子群算法与其他进化类算法一样，也是一类基于群智能的随机优化算法。但与其它进化计算方法相比， PSO算法具有收敛速度快、设置参数少、程序实现异常简洁、具有深刻的智能背景等特点，既适合科学研究，又特别适合工程应用。因此PSO算法一经提出就引起了国际上相关领域众多学者的关注和研究。目前PSO 算法已广泛应用于函数寻优、神经网络训练、模式分类、模糊系统控制以及其它的应用领域。但是，由于PSO算法在优化过程中所有粒子都向最优解方向飞去，所以粒子趋向同一化，群体的多样性逐渐丧失，即存在早收敛问题，因而也就难以获得较好的优化结果。 为了克服这一缺点，近年来出现了不少改进的PSO算法。如：Shi Y.(1998)提出的带惯性权重的PSO算法、Angeline P.（1999）提出
一种改进的粒子群优化算法 武燕Wu Yan；张冰Zhang Bing （江苏科技大学电子信息学院，镇江212003） （School of Electronics and Information，Jiangsu University of Science and Technology，Zhenjiang 212003，China） 摘要：介绍基本粒子群优化算法的原理、特点，并在此基础上提出了一种改进的粒子群算法。通过在粒子初始化时引入相对基的原理使粒子获得更好的初始解，以及在迭代过程中引入变异模型，部分粒子生成相对应的扩张及收缩粒子，比较其适应度，保留最佳粒子进行后期迭代，使算法易跳出局部最优。通过经典函数的测试结果表明，新算法的全局搜索能力有了显著提高，并且能够有效避免早熟问题。 Abstract: This paper introduces the principles and characteristics of Particle Swarm Optimization algorithm，and puts forward an improved particle swarm optimization algorithm. It adopted Opposition-Based Learning in initialization to get a better solution and adopted variation model which make some particles generate two corresponding shrink and expand particles and keep the best fitness particle iterate in later iteration to avoid getting into local minumum. The experimental results of classical function show this algorithm improves the global convergence ability and efficiently prevents the algorithm from the local optimization and early maturation. 关键词：粒子群优化算法；相对基；变异模型 Key words: Particle Swarm Optimization（PSO）；Opposition-Based Learning；variation model 中图分类号：TP301.6 文献标识码： A 文章编号：1006-4311（2011）07-0161-02 0 引言 粒子群优化算法（Particle Swarm Optimization，PSO）是一种新型的仿生算法，由Kennedy和Eberhart于1995年提出[1，2]。该算法是基于群体智能（Swarm I ntelligence，
收稿日期: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.doczj.com/doc/77483853.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] 但是,粒子群优化算法是根据全体粒子和自身的搜索经验向着最优解的方向进化,在进化后期收敛速度将变得缓慢,同时算法在收敛到一定精度时,容易陷入停滞,无法继续进化更新,因此,存在早熟和陷入局部极值点的现象
粒群算法的改进方法 一．与其他理论结合的改进 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算法，给出了算法交叉的具体形式。