α+**算法

α+**算法（精选6篇）

α+**算法 篇1

0 引言

传统的建立模型的方法遇到了新的挑战, 如何正确并且高效地建立模型以描述业务流程成为当前需要探索的重要问题。传统的建模方法在它的生命周期中暴露了以下的问题:首先, 过程定义对设计者提出了较高的要求:它需要设计者懂得建模的语言, 同时深入理解业务流程的各个环节;其次, 复杂建模耗费大量的人力与时间, 通过这种方式构建的业务模型不可避免地会出现人为的疏忽与错误;并且, 目前的建模活动生命周期中缺少对模型诊断和改进的阶段。传统建模方法的缺陷严重影响了对业务流程的建模, 不利于面向服务业务流程的快速响应, 为了探讨解决这些问题, 本文设计并实现了流程挖掘系统。

流程挖掘系统的核心思想是利用信息系统流程日志构建流程模型。它具有挖掘企业级信息系统的潜能, 是实施“业务流程再造” (business process redesign BPR) 的重要技术之一。实际的流程日志中包含大量的信息, 它记录了业务流程中的各种活动。通过使用流程日志, 流程挖掘技术可以将实际的业务流程反馈给设计者, 完成模型的优化和再设计。国外的流程挖掘系统处于研究阶段, 主要有基于ADONIS模型语言的In Wo Lv E工具、基于Petri-net的Pro M framework等。但是, 流程挖掘系统在国内还鲜有实现。

1 系统实现的思想

1.1 语言模型

自九十年代中期至今, 研究者提出了多种模型语言以适应商业中的业务流程。其中有代表性的模型定义语言包括活动间依赖型模型语言、ADONIS模型语言、Petri网模型语言等几种。随着工作流模型理论的发展, 因为Petri网具有比较严格的数学理论基础, 有利于工作流模型的形式化验证和分析, 所以越来越趋向于用Petri网的理论来描述分析工作流。Van der Aalst在Petri网的基础上提出了WF-net (workflow net) , 即工作流网, Aalst借用Petri网的有效性和活性等概念定义了工作流的安全性和健全性等, 并获得广泛的影响。与其他模型相比, 这种模型语言在业务流程方面具备很强的针对性。本文旨在WF-net的基础上讨论流程挖掘。图1是一个工作流网的例子。

1.2 α-流程挖掘算法语言模型

流程挖掘算法利用流程日志构建流程模型, 是流程挖掘系统的核心。Afrawal等提出一种基于活动间依赖型模型语言的算法, 是用工作流管理系统日志挖掘工作流模型的。算法可以发现活动间的依赖关系但是没有考虑每个活动从开始事件到结束事件之间的时间间隔, 导致活动间的并行关系不完整。同时由于受到模型语言的影响, 这种方法简单直观, 但是缺乏对拥有复杂结构模型的解释。Herbst等人提出的基于ADONIS模型语言的算法能处理并行、选择结构, 在算法运行过程中, 相同的活动被赋予不同的名称, 从而很好地处理了流程中含有相同活动名的结构。但是它不能够发现隐藏结构, 而且对于循环结构的处理能力也有限。相对于其他挖掘算法而言, Aalst和Weijter等人提出的α-算法在流程挖掘中, 可以很容易地处理串行、并行、选择结构, 能够很好地对复杂结构进行解释。该算法输入一个包含业务模型执行过程的事件日志, 日志需要保证: (1) 每一项任务对应一个用例; (2) 每一项任务包括一个发起者; (3) 每一项任务需要起始时间和终止时间。注意到对时间记录的需要是为了保证任务之间的顺序。具体的例子将在下文表1给出。基于这样的日志, 定义1把任务之间的关系分成4种, 分别是顺序、因果、并行关系和无关, 由这4种排序关系为基础, 定义3引出了α-算法。在本文中, 系统的实施是以Aalst提出的α-算法为基础的。

定义1 (基于日志的排序关系) 令W代表任意日志, WI"P (T*) , 令a, b I"T:

(1) 顺序关系:a>wb当且仅当存在轨迹s=t1t2Ltn-1tn以及i{1, …, n 1}, 使得

(2) 因果关系。a®Wb当且仅当a>Wb且不存在b>Wa。

(3) 并行关系。a#Wb当且仅当a≯Wb且b≯Wa。

(4) 每个节点 都属于从i到o的一条路径。

定义2 (α-算法) 令W代表覆盖T的日志。α (W) 定义如下:

2 流程挖掘系统的实施

通过挖掘日志, 流程挖掘可以展现业务的实际运行过程, 从而具有实时监控业务流程发生变化的能力, 提高业务流程的柔性。流程挖掘产生的模型还能使用日志来验证正确性。事实证明流程挖掘是一项与用户密切交互的过程, 因此良好的交互性能在系统中是不可或缺的。针对这个问题, 本文提出两个方法: (1) 使用特殊的布局算法并允许用户对节点位置调整或编辑属性; (2) 给出挖掘质量的度量方法帮助用户完成最终设计。

2.1 系统结构

本文的流程挖掘系统采用JAVA技术实现。日志文件经过预处理后在流程挖掘内核中应用α-算法, 系统结合节点布局算法为用户提供了可交互的GUI界面, 并且定义使用WFML格式的文档存储挖掘的结果, 最后系统还提供了验证模型的方法。图2展示了流程挖掘的系统结构。

2.2 日志文件

挖掘系统的核心是从日志文件中提取出流程的信息并建立流程模型。从流程设计工具Staffware、ERP系统SAP R/3到电子邮箱Outlook, 它们都可以提供不同形式的系统运行记录。这些记录中分析归类出的一系列基本信息能够作为流程挖掘系统处理的日志的基础, 作为代表, 表1是一个例子。用例对应一系列的任务, 每一个任务有具体的人员操作记录和时间记录。后文将展示挖掘后的结果。

2.3 流程日志预处理

目标系统工作的时候会产生大量重复的任务, 但它们对应的用例却不相同, 因此系统使用日志提取数据的时候, 首先进行形式化处理, 然后需要检查数据的有效性, 除去冗余信息。对于实际的目标系统生成的日志, 检查与过滤数据十分繁琐并且复杂, 因此在预处理中允许根据不同的情况定制不同的规则是合理的。除此之外, 人为的因素或其他异常因素会使目标系统的日志产生残缺, 为了简化问题, 原始的流程日志被认为是理想的, 它没有噪音, 且包括足够的信息。

2.4 任务间依赖关系的计算

经过预处理后得到了规范的流程日志。在日志中同一用例的任务之间的顺序是相关的, 而用例与用例之间的任务顺序则无关紧要。定义2给出了两个任务之间的关系, 并且指出任意的关系都可以由关系>W表示。相对于特定用例的局部关系矩阵, 可以保证构成整个流程的全局关系矩阵。记全局关系R= (TW, E) , TW是日志中的任务集, E是日志中的>W关系集。由每一个用例产生的局部关系R'= (TW', E') 并且R'I`R, 容易得到R=R1'E`R2'E`…Rn'。至此, R就可以用布朗型矩阵DR来表示。因果关系!W, 无依赖关系#W分别用布朗型矩阵DC, DN来表示, 通过公式RW, = (>W>-1W) , #W= (TW'TW) (>WE`>-1W) 并且借助矩阵DR可以计算出上述矩阵。

2.5 生成流程模型

以上的计算是设计和运行挖掘算法的前提, 为了实现这个完整的算法, 下面定义一些重要的数据结构。

2.5.1 Linked Queue类

Linked Queue类是链表队列, 它支持入队出队操作, 可以进行节点的大小比较, 查找指定的数据。使用时无需定义数组的长度。它在核心算法中是最基本也是最重要的数据结构。

2.5.2 Transition类

它描述WF-net中的变迁。每一个这样的对象都保存一个唯一标识id和名称name。注意到日志中的任务使用Transition类表示, 把所有的变迁保存在一个Linked Queue中是方便的。

2.5.3 Place类

它描述WF-net中的库所。与Transition类相似, 这里不过多阐述。

2.5.4 Causal Relation Bag类

Causal Relation Bag类定义了因果关系, left Queue是原因, 它可以导致right Queue发生。核心算法的目标就是生成所有正确的Causal Relation Bag, Place类是它的抽象。定义fire和usable是为了剔除重复或是不再使用的数据。

利用以上介绍的数据结构和计算得出的关系依赖矩阵, Alpha算法就可以方便地实现。

输入:日志预处理后的结果。

输出:从日志里挖掘生成的包含所有Place与Transition的链表队列。

set Of Tasks找到所有的任务集合;

list Of First所有流程轨迹的首节点集合;

list Of Last所有流程轨迹的末节点集合;

for (set Of Tasks中的每一个节点) {

任意的子集sub Tasks[k]属于set Of Tasks;

//把left Side和right Side合并成一列除去重复的元素, 查找所有相同//的left Queue/right Queue, 如果其对应的right Queue left Queue之间存//在从属关系, 则去除被包含的一项数据, 否则不变。这样就得到最//简化的元组。

}

至此, 每一个最简化的元组实际上可以代表一个具有记录出边和入边能力的库所, 通过这些库所和变迁就很容易提取出它们之间的有向弧, 然后经过布局算法与图形组件引擎的作用形成与用户的交互能力。图3展示了表1列出的流程日志完成挖掘后的结果。

2.6 WFML (WF-net Markup Language)

本文定义的WFML文件作为一种XML的应用提出了挖掘算法的中间格式, 它可以表示可交互的图形结果, 并且具备高效、简单且具有高度开放性、兼容和跨平台性能的数据存储和数据交换标准的优点。基于日志的流程挖掘生成图形化结果后由WFML记录交互内容。WFML主要包含以下功能: (1) 表示整个WF-net的结构; (2) 记录变迁、库所在显示页面上的位置、标识等相关属性。

XML Schema能够规范定义WFML, 并且将来XML Schema还将会验证WFML文档的合法性。在我们的流程挖掘系统中我们设计定义了WFML文档的合法组件群。图4所展示的是系统中描述工作流网的XML Schema的结构, 即WFML的元素的逻辑关系。

WFML由WF-net组成, WF-net中包括它本身的属性 (attributes) 与标识符 (Identifier) , 还包括库所 (Place) 、变迁 (Transition) 、有向弧 (Arc) 、发生规则 (Firing rule) 。标识符指明父结点的名字以及相关图形信息 (Graphics) 。为了面向对象化的设计, 库所元素除了描述它本身的含义外, 还把初始标识 (InitialMarking) 和标识 (Marking) 一同囊括在内。有向弧需包含源 (Source) 和目的 (Target) 节点的记录, 它们都存放在属性中, 这里没有具体列出。

在WFML文档中还定义了一些通用属性, 使得它们可以被大部分WFML元素使用, 比如id表示唯一的WF-net节点;name代表WF-net节点的名称;value保存了初始标识、标识的权值或代表弧中的容量;在多文档中, 通过page指明WF-net的元素所在的页面等。

3 结果验证与质量度量

系统中构建的模型验证模块不仅可以验证对流程日志挖掘的实际效果, 还可用来感知流程模型与商业中执行的业务流程的异同, 从而做出指导。模型的质量取决于它描述业务流程执行的能力, 同样, 流程执行的恰当与否应该由它与模型的吻合程度来判断。当流程模型的表达和流程执行产生分歧的时候, 就意味着需要做出一些改进。

为了验证挖掘的实际效果, 我们设计了流程仿真生成器, 以产生的日志文件作为系统的输入数据集进行流程挖掘, 挖掘出的模型与原模型相对比。观察系统挖掘的模型图3, 同时对照原始模型图1会发现它们所表达的内容是一致的。系统在挖掘顺序、并行、选择关系方面是较为准确并具有很好的应用价值。事实上, 我们开发的系统能够挖掘出无噪音、日志完整情况下的日志中活动的结构关系。同时, 对非自由选择结构的挖掘、噪音处理等问题, 有待我们进一步研究。

4 结束语

实践证明, 流程挖掘技术可以解决传统的工作流管理生命周期中存在的问题, 减小了复杂流程建模的工作量, 保证了流程改进、BPR的顺利进行, 可有效进行流程诊断分析。本文的流程挖掘系统利用流程日志文件提取出流程中任务间关系的信息, 并建立相应的流程模型, 同时为业务人员根据需求构造新的流程提供帮助。目前, 系统的商业应用正在进行中。

参考文献

[1]Van der Aalst W M P, Weijters A J M M.Process mining-a research agenda, computers in industry[J].2004 (3) :231～244.

[2]Van Der Aalst W M P, Weijters A J M M, Marudter L.Workflow mining:discovering process models from event logs[C].IEEE Transactions on Knowledge and Data Engineering, Eindhoven, 2002:101～132.

[3]Agrawal R, Gunopulos D, Leymann F.Mining process models from workflow log[C].Proceedings of the Sixth International Conference on Extending Database Technology, USA, 1998:469～483.

[4]Guido Schimm.Mining exact models of concurrent workflows[J].Computers in Industry, 2004 (2) :265～281.

α+**算法 篇2

雷达数据处理是指通过雷达测量, 在取得目标的位置参数, 运动参数 (如径向距离, 径向速度, 方位和俯仰角等) 后进行的互联, 跟踪, 滤波, 平滑, 预测等运算。经过上述运算处理, 可以有效地抑制测量过程中引入的随机误差, 精确估计目标位置和有关的运动参数, 预测目标下一时刻的位置, 并形成稳定的目标航迹。

在雷达数据处理中, 滤波算法的优劣决定着数据处理的最终目标预测的精确性以及整个系统的实时性。当前主要的滤波算法主要有α-β和Kalman算法以及基于他们的各种变种算法。自适应α-β滤波算法是一种基于α-β滤波算法的一种改进算法。本文主要研究它在雷达数据处理中滤波的应用以及和其他算法的优劣对比。

2 滤波算法原理

2.1 常系数α-β滤波算法

α-β滤波器是针对匀速运动目标模型的一种常增益滤波器。此时目标状态向量只包含位置和速度两项。现假设令:

Xn=目标测量值;

可得到α-β滤波方程组为:

其中:

系统α和β是无量纲变量, 分别为目标状态的位置和速度分量的常滤波增益。工程上常采用与采样时刻k有关的α和β确定方法:

可以看出随着k的变大, α和β值持续变小, 当他们取值小于一定数值时滤波器会发散。为了避免滤波器的发散, 必须保证α和β值在正常范围之内。根据公式推导计算得到一个滤波器稳定三角形, 见图1。其稳定区为:

在实际工程应用中只在0<α<1及0<β<1范围内取值。

以上可以看出α-β滤波算法的目标状态估计与α和β增益系数计算是分开独立计算的, 运算相对简单, 计算量较小。

2.2 Kalman滤波算法

卡尔曼 (Kalman) 实质上是线性无偏差最小估计的一种递推形式, 在工程中的应用已经很多。它是通过协方差来计算滤波增益参数, 而协方差和目标状态估计的计算是交织在一起的;协方差计算包括协方差的预测, 新息协方差和协方差的更新。所以卡尔曼滤波计算量比α-β滤波算法要大很多。

在滤波系统计算过程中要将状态方程过程噪声方差Q (k) 和测量噪声方差R (k) 带入方程, 两者均为高斯白噪声序列;这俩个参数取决与过程噪声和测量噪声的的统计特性, 对Kalman滤波效果的好坏有很大的影响。

卡尔曼滤波算法在跟踪机动性目标的时候效果较好, 但同时它的运算量往往比较大, 随着状态向量维数的增加, 运算量以阶数形式迅速增加。这就要考虑到滤波的实时性能力和数据吞吐率的问题。同时如果系统的过程噪声和测量噪声的参数选取与实际情况不符, 都会造成滤波器的发散。而这些量都是未知的, 需要假设估计得到。

2.3 自适应α-β滤波算法

自适应α-β滤波算法是基于常系数α-β滤波算法的一种延续和改进。常系数α-β滤波器在跟踪非机动目标时运算量少且简单, 但是当目标机动时, 跟踪精度就会迅速下降, 滤波器发散, 从而使目标丢失。而这个过程可以通过观察误差体现出来, 如果人们能够根据误差的变化自动的调整滤波增益α和β, 使得误差保持在一定的范围内, 那么就可以避免滤波器的发散以及跟踪目标的丢失。这个就是自适应α-β滤波算法的基本思想。

若定义残差:

V (k) 不仅反映了观测误差的大小, 也反映了目标机动的情况。目标机动性可由用加速度项表示, 令其方差为σ2ω, 根据统计知识可知:

由于目标机动情况随时间变化, 因此, 残差σω2 (k) 是一个时变参数, 为了及时准确地反映目标最近的机动情况, 设置一个宽度为N的滑窗, 用最近时间内的残差值来求近似值。这里N一般取值3~8。

滤波器增益还和测量误差有关, 定义测量误差方差为σ2n, 雷达天线扫描周期为T, 则可以得到目标综合机动指数:

推导近似得到r和α (k) 和β (k) 之间的关系:

以上可以看出自适应α-β滤波器就是在增加少量运算量的情况下, 它可以自动根据目标误差的数值来改变滤波增益参数, 可以避免滤波器发散, 保持了对机动目标的跟踪。

3 Matlab滤波仿真

本文提取了雷达数据仿真系统中的一组航迹数据作为原始数据;对其进行了Matlab滤波仿真计算。状态向量包含距离和方位, 距离和方位分别由位置和速度两项参数表示, 仿真为四维数据滤波。其中常系数α-β滤波算法α的值限制在1~0.4之间, β的值限制在0.2~1之间, 起防止滤波器发散的作用。自适应滤波系数没有做相应的人为限制。在两种滤波器的原始数据以及添加的随机噪声均相同情况下得到的滤波对比效果如下图所示:

通过观察对比可知:图2中, 目标在机动拐弯处, 航迹预测点很明显向外发散, 没有及时得到修正, 预测误差较大。而图3中, 效果明显优于图2的情况, 基本没有发散迹象, 预测误差自然较小。这点在滤波方差上也得到了很好的体现:

可见自适应α-β滤波器的在滤波平滑以及滤波精度方面均优于常系数α-β滤波器。

在滤波仿真的过程中, 可以观察滤波计算过程中的中间变量, 来对滤波器进一步分析和熟悉, 其中计算得到距离滤波残差和动态滤波系数如下图:

上图第一部分是仿真系统计算得到的滤波残差, 即由公式 (1) 计算得到;第二部分是滤波残差滑窗均值, 有公式 (2) 计算得到;第三部分是滤波增益α参数数值, 由公式 (5) 计算得到。

从图3和图4相结合可以在目标机动拐弯处, 预测误差增大, 残差均值随着增加, 最终反映到滤波增益参数α也随之增加, 从而使得滤波跟踪机动的能力增强, 避免了滤波器的发散失效;反之在机动量小的情况下各个参数也得到了相应的调整, 达到自动适应跟踪的目标的目的。

另外一个方面经过粗略计算比较, 三种滤波算法的基本运算量结果如下表:

其中自适应α-β滤波器的数值是公式 (2) 中的N取5的时候得到的;Kalman滤波器的计算量数值是四维滤波情况下的计算量;可以看出Kalman滤波的运算量是非常大的, 而自适应α-β算法增加的运算并不是很多。从两方面看出自适应α-β滤波器在增强了跟踪机动目标特性的情况下, 运算量并没有增加多少, 同时具有较Kalman滤波具有更好的实时性。

4 结论

通过仿真试验验证, 可得出自适应α-β滤波算法在跟踪机动目标的时候, 与常增益α-β算法相比较, 在运算量略有增加的情况下, 克服了易发散的问题, 同时具有良好的跟踪性能;与相比Kalman算法相比较, 运算量少了不止一个数量级, 其实时性更佳对系统硬件性能要求更低。可见自适应α-β滤波算法是一种实用性较强的滤波方法, 为以后工程应用提供了一种新的选择。

摘要：详细介绍了自适应α-β滤波算法的基本原理和其在雷达数据处理中的应用情况, 并从原理上与其他两种比较常用的滤波算法的性能优劣对比;最后通过Matlab仿真对比和量化分析, 进一步分析验证了自适应α-β滤波算法的适用性和实用性。

关键词：滤波器,α-β,数据处理,自适应,航迹处理

参考文献

[1]何友, 修建娟, 张晶炜, 关欣, 等.雷达数据处理及应用[M].电子工业出版社, 2006.1

α+**算法 篇3

说话人确认是根据说话人的语音个性特征证明说话人所声称的身份的过程[1],它是说话人识别领域的一个重要的分支。支持向量机SVM以其出色的分类性能在说话人确认领域获得了成功的应用。高斯混合模型GMM是一种有效的说话人语音建模方法。侯风雷等人最早将这两种方法结合用于说话人确认,获得了较为理想的实验结果[2]。然而在噪声环境下,由于测试语音和训练语音的不匹配,导致GMM的性能急剧下降[3]。文献[4]提出α-GMM说话人模型,并将其应用于说话人辨认系统,仿真实验结果表明该模型具有良好的鲁棒性。然而,随着系统注册人数的增加,语音数据规模急剧变大,α-GMM的计算复杂度增大,导致SVM训练速度变慢,进而影响系统的性能。针对上述问题,本文提出一种新的基于α-GMM聚类和SVM的说话人确认方法。借助于α-GMM模型,消除背景噪声对话者模型的影响,同时对得到的话者α-GMM模型根据模型间的α散度进行聚类,减少SVM训练样本数量,达到提高系统的识别性能和鲁棒性的目的。

1 说话人α-GMM

传统GMM模型利用若干个高斯概率密度函数的加权和来近似地描述说话人特征矢量在概率空间的分布。对于一个D维的输入特征向量X,M个成员高斯概率密度的加权和表示为:

${\rm P}(X|S)={\displaystyle \sum _{i=1}^{{\rm M}}\omega }{}_{i}g{}_i(x)$ (1)

其中P(X|S)表示话者S的语音序列:X={x1,x2,…,xN}的似然概率。gi(x)(i=1,2,…,M)是每个成员的高斯概率密度函数。ωi是混合权值且${\displaystyle \sum _{i=1}^{{\rm M}}\omega }{}_i=1$,μi是均值向量,∑i为协方差矩阵。

α-GMM是传统GMM各个密度函数线性组合的扩展,用于消除在噪声环境下,测试语音和训练语音不在同一信道而对识别结果产生的影响。高斯混合模型中各个成员的高斯概率密度函数通过参数α集成[3]。假设话者S的各个成员高斯密度函数为gi(x)(i=1,2,…,M)。则α-GMM模型Pα(X|S)可以定义为:

${\rm P}{}_{\alpha }(X|S)=cf{}_{\alpha }^{-1}\left\{{\displaystyle \sum _i^{{\rm M}}\omega }{}_i\cdot f{}_{\alpha }[g{}_i(x)]\right\}$ (2)

其中$c=\frac{1}{{\displaystyle \int \begin{array}{c}f{}_{\alpha }^{-1}\left\{{\displaystyle \sum _{i=1}^{{\rm M}}\omega }{}_{i}f{}_{\alpha }[g{}_i(x)]\right\}ds\end{array}}}$是α-GMM的标准化常数。fα[gi(x)]是各个成员的密度的α集成函数,其计算公式如下:

$f{}_{\alpha }[g{}_i(x)]=\{\begin{array}{l}\frac{2}{1-\alpha }g{}_i(x){}^{\frac{1-\alpha }{2}}\alpha \ne 1\\ \log (g{}_i(x))\alpha =1\end{array}$

(3)

逆函数f${}_{\alpha }^{-1}$(y)的计算可定义如下:

$f{}_{\alpha }^{-1}(y)=\{\begin{array}{l}\left(\frac{1-\alpha }{2}y\right){}^{\frac{2}{1-\alpha }}\alpha \ne 1\\ e{}^y\alpha =1\end{array}$

(4)

结合式(3)和式(4)可得α-GMM模型Pα(X|S)为:

${\rm P}{}_{\alpha }(X|S)=\{\begin{array}{l}c\left({\displaystyle \sum _{i=1}^{{\rm M}}\omega }{}_{i}g{}_i(x){}^{\frac{1-\alpha }{2}}\right){}^{\frac{2}{1-\alpha }}\alpha \ne 1\\ ce{}^{\left({\displaystyle \sum _i^{{\rm M}}\omega }{}_i\cdot \log (g{}_i(x))\right)}\alpha =1\end{array}$

(5)

显然在公式(5)中,当α=-1时,α-GMM模型变成传统GMM模型。α-GMM模型参数估计是α-GMM的关键问题,直接影响到α-GMM的性能。本文同样还是采用传统GMM模型中的EM参数估计方法[5]。

2 α散度聚类

在说话人识别系统中,随着注册说话人数目增加,语音数据的规模急速增大,使得α-GMM的建模计算量较大,进而会影响到系统的识别性能。在深入研究K均值聚类算法[6]的基础上,本文提出基于α散度的模型聚类方法,以期在保证识别率的情况下,提高系统的识别速度。

假设聚类数目为K,聚类中心模型为:

p${}_{\alpha }^{(c)}$={ω${}_i^{(c)}$,μ${}_i^{(c)}$,∑${}_i^{(c)}$} i=1,…,M

其中$\omega {}_i^{(c)}=\frac{1}{s{}_n}{\displaystyle \sum _{j=1}^{s{}_n}\omega }{}^{(j)}$,${\displaystyle {\sum }_i^{(c)}=}\frac{1}{s{}_n}{\displaystyle \sum _{j=1}^{s{}_n}{{\displaystyle \sum }}^{(j)}}$,$\mu {}_i^{(c)}=\frac{1}{s{}_n}{\displaystyle \sum _{j=1}^{s{}_n}\mu }{}^{(j)}$,分别是聚类中心模型的权值向量,协方差矩阵和均值向量,其中sn表示当前类别n中说话人α-GMM模型的数量,n=1,…,K。

α散度是一种有效的概率模型差异度量方法,两位话者α-GMM模型p${}_{\alpha }^{(\lambda )}$和p${}_{\alpha }^{(\gamma )}$之间的α散度可定义为:

$D{}_{\alpha }[p{}_{\alpha }^{(\lambda )},p{}_{\alpha }^{(\gamma )}]=\{\begin{array}{l}{\displaystyle \int p}{}_{\alpha }^{(\lambda )}\log \frac{p{}_{\alpha }^{(\lambda )}}{p{}_{\alpha }^{(\gamma )}}ds\alpha =-1\\ {\displaystyle \int p}{}_{\alpha }^{(\gamma )}\log \frac{p{}_{\alpha }^{(\gamma )}}{p{}_{\alpha }^{(\lambda )}}ds\alpha =1(6)\\ \frac{4}{1-\alpha {}^2}\left[1-{\displaystyle \int (}p{}_{\alpha }^{(\lambda )}){}^{\frac{1-\alpha }{2}}(p{}_{\alpha }^{(\gamma )}){}^{\frac{1+\alpha }{2}}ds\right]\alpha \ne \pm 1\end{array}$

式(6)可知,当α=±1时:

$\begin{array}{l}D{}_{-1}[p{}_{\alpha }^{(\lambda )},p{}_{\alpha }^{(\gamma )}]=D{}_{{\rm K}L}[p{}_{\alpha }^{(\lambda )},p{}_{\alpha }^{(\gamma )}]\\ D{}_1[p{}_{\alpha }^{(\lambda )},p{}_{\alpha }^{(\gamma )}]=D{}_{{\rm K}L}[p{}_{\alpha }^{(\gamma )},p{}_{\alpha }^{(\lambda )}]\end{array}(7)$

式(7)变成KL散度。当α=0时,$D{}_0[p{}_{\alpha }^{(\lambda )},p{}_{\alpha }^{(\gamma )}]=2{\displaystyle \int \left(\sqrt{p{}_{\alpha }^{(\lambda )}}-\sqrt{p{}_{\alpha }^{(\gamma )}}\right)}{}^2\text{d}s$。由此可见Dα[p${}_{\alpha }^{(\lambda )}$,p${}_{\alpha }^{(\gamma )}$]≥0,Dα[p${}_{\alpha }^{(\lambda )}$,p${}_{\alpha }^{(\gamma )}$]≠Dα[p${}_{\alpha }^{(\gamma )}$,p${}_{\alpha }^{(\lambda )}$]。

α散度聚类算法具体步骤如下:

① 设定聚类数K,随机指定K个说话人的α-GMM模型为K个聚类的中心模型:

p${}_{\text{α}}^{(\text{c})}$={ω${}_{\text{i}}^{(\text{c})}$,μ${}_{\text{i}}^{(\text{c})}$,∑${}_{\text{i}}^{(\text{c})}$i=1,…,M},sc=0(n=1,…,K)用于记录当前类别c中聚类的说话人模型数目;

② 根据式(6)计算说话人模型p${}_{\alpha }^{(\lambda {}_s)}$(s=1,…,S)和p${}_{\alpha }^{(c)}$之间的α散度距离Dα[p${}_{\alpha }^{(\lambda )}$,p${}_{\alpha }^{(\gamma )}$],S为注册说话人的数目;

③ 将α散度距离最小的说话人α-GMM模型划分到当前的类中,sc=sc+1,重新计算聚类中心模型;

④ 重复执行步骤②和③,直到聚类中心模型不再变化为止。

3 基于α-GMM模型聚类的SVM说话人确认

将本文提出的说话人α-GMM聚类算法应用于SVM说话人确认系统。SVM的决策分类函数是:

$f(x)=\mathrm{sgn}({\displaystyle \sum _{i=1}^{l}y}{}_i\alpha {}_i{\rm K}(x{}_i,x)+b)$ (8)

其中xi∈Rn,i=1,2,…,l是用于训练的约简向量集,yi∈{-1,1}是类别标号,αi>0是Lagrange 系数,对应于支持向量(SV)的αi取值非零,其余取值为零。而b是分类的域值,可以由任意一个线性支持向量求得。K(xi,x)是核函数用于替代点积运算,避免在高维特征空间进行复杂的运算。在新提出的说话人确认系统中,得到的约简向量集的分布是非线性的,若要使用SVM进行处理,需用到核函数,在此选择类似于GMM的径向基核函数:

${\rm K}(x{}_i,x{}_j)=\exp (-\parallel x{}_i-x{}_j\parallel {}^2/2\sigma {}^2)$ (9)

4 仿真实验及结果分析

为了验证本文提出算法的有效性,实验中采用自己录制的语音库,录音的人数为53人,其中男26人,女27人,采用高质话筒在低噪环境下进行录音。每位话者录制了10个语音段,每个语音段的长度为30s。为了反映说话人的发声随时间变化,录入是间隔一段时间多次进行的。录音后的数据通过采样频率为11025Hz、量化位数为16bit、单声道的A/D转换成数字信号存储。采用一阶数字滤波器H(z)=1-0.95z-1对语音信号预加重,采用帧长30ms,帧移15ms为语音信号分帧和加汉明窗。每个话者的每个语音段共有1999帧,对每帧数据提取13维的MFCC及它的一阶差分和二阶差分共同构成39维输入特征向量。文献[4]中,在NTIMIT电话语音集上进行α-GMM的性能测试,当α=-6时其性能最高,因此在本文的仿真实验中设置α=-6。仿真实验以等错误率EER(Equal Error Rate)和最小决策代价函数minDCF(Minimum Decision Cost Function)值[7]作为衡量分析实验结果的标准。

实验1 噪声环境下α-GMM性能测试

为了验证α-GMM的抗噪性能,我们在训练样本中叠加白噪声[6]。通过对噪声样本乘一衰减系数得到不同信噪比的语音:40dB、30dB、20dB。测试样本保持不变。对GMM、SVM、GMM+SVM、α-GMM和α-GMM+SVM算法的抗噪性能进行测试,核函数采用RBF(σ=1.6)核函数。得到的实验结果如表1所示。

由表1可知,随着信噪比的降低(噪声增加),GMM、SVM、GMM+SVM的EER和minDCF的变化比较明显,其中GMM性能下降的最快,说明噪声对GMM的影响最大。而α-GMM相比较于GMM、SVM和GMM+SVM,其性能下降的较慢,在信噪比为40dB时,其EER为5.33%,minDCF为0.0411。当信噪比降为30dB时,EER提高了0.61%,minDCF提高了0.0091;当信噪比降为20dB时,EER提高了1.61%,minDCF提高了0.02。因此,α-GMM相比于传统的说话人识别算法具有更好的鲁棒性。而在五种算法中,α-GMM+SVM的识别性能是最好的,该方法具有良好的抗噪性,同时发挥了SVM高识别性能的优势。

实验2 聚类性能测试

本实验用于测试本文提出的聚类算法的性能。系统采用α-GMM为话者语音建模,使用SVM识别目标说话人。表2为不同聚类数目下系统的EER和minDCF比较。

从表2中可以很明显地看出,系统在聚类数目为50,40,30,20下的EER分别是4.33%、4.92%、5.51%和6.83%。类别划分越细,其性能越好。然而,随着聚类数目的增加,系统的语音数据也随之增加,进而会影响到α-GMM建模和SVM的训练速度,使得系统识别时间变长。图1是四种聚类情况下的系统DET曲线比较,倾斜向上的虚线是由错误拒绝率(FR)和错误接受率(FA)相等的点构成。

5 结 语

在深入研究GMM和SVM的基础上,提出一种基于α-GMM聚类和SVM的说话人确认方法。一方面借助于α-GMM可以有效地去除噪音环境对训练语音样本和测试样本的影响;另一方面根据说话人α-GMM模型间的α散度可以迅速地对说话人模型聚类,有助于降低SVM的计算复杂度,提高系统的性能。仿真实验结果表明,本文提出的说话人确认算法具有较高的识别性能和良好的鲁棒性。然而α-GMM模型计算复杂度较高,因此在后续的研究中我们将致力于α-GMM模型计算的简化,更好地发挥其高鲁棒性的优势。

参考文献

[1]Kong Aik Lee,Chang Huai You,Haizhou Li,et al.Using DiscreteProbabilities with Bhattacharyya Measure for SVM-Based Speaker Veri-fication[J].IEEE Transactions on Audio,Speech,and LanguageProcessing,2011,19(4):861-869.

[2]侯风雷,王炳锡.基于说话人聚类和支持向量机的说话人确认研究[J].计算机应用,2002,22(10):33-35.

[3]Yuxiang Shan,Jia Liu.Robust speaker recognition in cross-channelcondition based on Gaussian mixture model[J].Multimedia tools andapplications,2011,52(1):159-173.

[4]Dalei Wu,Ji Li,Haiqing Wu.α-gaussian Mixture Modelling ForSpeaker Recognition[J].Pattern Recognition Letters,2009,30(6):589-594.

[5]Fujimoto M,Riki Y A.Robust speech recognition in additive andchannel noise environments using GMM and EM algorithm[C].Acous-tics,Speech,and Signal Processing 2004:I-941-944.

[6]Vijendra Raj Apsingekar,Phillip L,De Leon.Speaker Model Cluste-ring for Efficient Speaker Identification in Large Population Applica-tions[J].IEEE Transactions on Audio,Speech,and Language pro-cessing,2009,17(4):848-853.

α+**算法 篇4

所谓目标机动, 是指目标的加速度的方向和幅度在短时间内出现急剧地变化, 表现为急转弯、急加速和急减速。针对目标的机动, 传统的α-β、α-β-γ和卡尔曼滤波算法均出现了性能下降, 因此需要对适应高机动目标的跟踪滤波算法进行研究。α-β和α-β-γ滤波算法由于增益计算量小, 且可以离线计算, 在工程中得到广泛应用。但是由于增益固定, 传统的α-β和α-β-γ滤波算法对于机动目标的跟踪性能下降明显。本文提出一种基于多模型混合估计的自适应α-β-γ滤波算法, 有效提高了对于机动目标的跟踪性能。

1 α-β-γ滤波算法

α-β-γ滤波器实质上是运动方程为匀加速的卡尔曼滤波器的稳态解形式[1]。假设目标做匀加速直线运动, 此时状态向量为

其中, x1, x2, x3分别代表目标的位置、速度、加速度。则系统的状态方程为

噪声w (k-1) 为均值为0, 协方差阵为Q的正态噪声。量测方程为

其中, y (k) 为k时刻的量测值;量测向量C=[1 0 0];量测噪声v (k) 为均值为0, 方差为R的正态噪声。

则相应的卡尔曼滤波公式为

其中, Xs (k-1/ k-1) 为k-1 时刻的平滑向量, Xp (k/ k-1) 为对k时刻的预测向量, H (k) 为增益向量, P′ (k/k-1) 为k时刻的预测协方差阵, P (k-1/ k-1) 为k-1 时刻的滤波协方差阵。

当卡尔曼滤波递推足够多步后, 增益向量H (k) 将趋于常数向量H, 即得到α-β-γ滤波公式

根据α-β-γ滤波与卡尔曼滤波的关系, 如果卡尔曼滤波稳定后, 预测协方差阵为

则α-β-γ滤波器的增益满足

其中, R为量测噪声的方差

由此可见, α-β-γ滤波对应着相应卡尔曼滤波的稳态解, 增益系数不随迭代改变, 计算量小。但是传统的α-β-γ滤波器增益无法随着目标的运动模型的改变而改变, 固定的增益无法适应机动目标的跟踪。

2 自适应多模型α-β-γ滤波算法

目前得到广泛应用的目标跟踪算法是卡尔曼滤波算法、α-β和α-β-γ滤波算法, 但均在跟踪机动目标时存在不足。对于卡尔曼滤波, 当系统达到稳态时, 其预测协方差将趋于极小值, 使得滤波器的增益也趋于极小值, 此时若状态发生突变, 残差增大, 预测协方差和滤波器的增益不能随残差同步改变[2]。而对于α-β和α-β-γ滤波算法, 增益为常量, 不随残差改变。因此, 不具有对机动目标良好的跟踪能力。针对这个问题, C.B.Chang和R.H.Whiting等人将可调白噪声模型的思想应用于机动目标跟踪。这种方法通过观测目标滤波残差的变化来判断机动的产生与结束, 并对滤波器进行相应的调整。但这种方法需要先人为设定门限, 不同的门限对应不同的跟踪性能。同时, 该算法只适用于卡尔曼滤波, 无法优化α-β和α-β-γ滤波算法。

在使用基于单模型的滤波算法进行机动目标跟踪时, 滤波模型需要先验设定, 但是先验滤波模型不能较好地匹配目标的机动, 因此其跟踪效果往往不好, 特别是当前目标机动能力日益增强, 目标运动模式的结构、参数变化起伏很大, 导致单模型算法很难及时准确地辨识机动参数, 从而造成模型的不准确, 而导致算法的性能下降[3]。为了适应目标机动, 根据目标机动时残差增大的特点, 本文提出一种自适应多模型α-β-γ滤波算法:

2.1 先验滤波模型的确定

已知k时刻的残差为

当目标非机动且滤波收敛时, 根据α-β-γ滤波与卡尔曼滤波的关系, 可知残差的方差为

即, e (k) 服从均值为0, 方差为P11+ R的正态分布[3]。当目标机动时, 残差e (k) 为非平稳随机过程, 并且幅度急剧增大。

α-β-γ跟踪滤波器的收敛速度和精度取决于增益系数α、β、γ的选取。在选取增益系数时, 必须折中考虑噪声特性与动态性能之间的平衡[1]。研究表明, 最优增益系数应满足如下关系[4]:

其中, ξ 为平滑系数, 也是系统特征方程的三重正实根。所以, 在最优的情况下, 可以利用平滑系数ξ 来确定α、β、γ的值。不同的平滑系数ξ , 决定了不同的滤波模型。由式 (12) 和式 (15) 可得

这说明, 可以根据先验参数R和P11确定先验平滑系数ξ1。其中, R为量测噪声方差, P11为预测协方差阵的第一项, 即目标位置的预测误差的方差。由先验设定确定的先验平滑系数ξ1 代表着先验α-β-γ滤波器模型。

2.2 自适应多模型α-β-γ滤波算法原理

自适应多模型α-β-γ滤波算法的原理图如图1:

其中, 滤波器M1 到Mn分别是平滑系数为ξ1到ξn的α-β-γ跟踪滤波器, 滤波器M1 的平滑系数为ξ1, 代表先验滤波器。Xis (k |k ) 和ei ( k) 分别代表使用滤波器Mi得到的k时刻的滤波值和残差; Pi (k) 为滤波器Mi在k时刻的模型概率。

多模型算法的关键是模型概率的计算。本文提出一种滤波模型失配度, 用Ei (k) 表示, 计算公式为

式 (19) 也可以写为

其中, h1与h2为非负的权系数, 且h1+ h2=1 。

式 (19) 采用序贯式结构对各个时刻的残差幅度加权地进行积累, 得到滤波模型失配度Ei (k) 。从中可以看出Ei (k) 是迭代计算的, 因此不需要存储大量数据。为了增加新数据的权重, h1通常取小于1 的正数, 作为衰减因子。

则滤波器Mi在k时刻的模型概率Pi (k) 为

式 (20) 表示, 滤波模型失配度越大, 则滤波器的模型概率越小。在得到k时刻的滤波器集合的模型概率后, 就可以混合估计k时刻的滤波值Xs (k |k)

通过式 (21) 可以看出, 算法自适应地控制了各个滤波器的权重, 使得对目标跟踪性能较好的滤波器权重加大, 对目标跟踪性能较差的滤波器权重减小。

2.3 仿真分析

如果由先验信息知道量测噪声方差R为100m2, 目标的跟踪误差的方差P11为25m2, 则由此计算得ξ1 =0.9283。进而计算得系数α1=0.2000 , β1 =0.0149 , γ1=3.7 ×10-4。如果采样间隔设定为T=0.5s , 则初始滤波模型的增益向量为H1=[000, 0.0297, 0.0015]1=TH。

对目标的跟踪一般都是多维上同时跟踪滤波, 只有每一维上跟踪效果都好, 整体的跟踪效果才能好。本文仿真对一个运动目标在X轴这一维上的跟踪滤波。目标的起始点在10000m处, 起始量测值为10020m, 目标在X轴这一维上的运动状态如表1 所示:

使用初始α-β-γ滤波器对目标的跟踪滤波效果如图2所示, 预测误差幅度如图3 所示:

从图2 和图3 可以看出, 在目标出现较强机动的时候, 初始α-β-γ滤波器的预测误差急剧增大。在目标机动最强的加速段1 和加速段2 上目标预测误差达到最大, 进入目标匀速直线运动段后, 预测误差逐渐减小, 但减小速度较慢, 到[70s, 100s]段时预测误差已经减小到低于量测噪声了, 才达到较好的跟踪效果。

如果选取5个滤波模型作为模型集合, 用平滑系数ξi代表滤波模型Mi, 选取模型集合。如果选取0.51 2h=h=, 则自适应多模型α-β-γ滤波的滤波效果如图4所示, 滤波误差幅度如图5所示:

从图4 和图5 可以看出, 自适应多模型α-β-γ滤波算法有效地改善了对较强机动目标的跟踪性能。在目标非机动和机动时, 算法的滤波误差幅度总体上小于量测噪声幅度, 得到了较好的跟踪效果。

3 结论

针对单模型α-β、α-β-γ和标准卡尔曼滤波算法对于机动目标跟踪性能下降的问题, 本文基于多模型混合估计思想, 提出了一种自适应多模型α-β-γ滤波算法。仿真结果表明, 该算法可以较好地适应目标的机动, 对目标的跟踪性能较好。但该算法需要多模型并行运算, 计算量较大。同时, 模型集合如何选取最优以及模型概率如何计算最优, 这些问题仍需要进一步研究解决。

参考文献

[1]黄鹤, 张会生, 许家栋, 等.一种改进的α-β-γ滤波跟踪算法[J].西北工业大学学报, 2008, 26 (2) :146-151.

[2]高增敏, 王首勇, 郑作虎, 等.一种适用于机动目标跟踪的改进卡尔曼滤波算法[J].空军雷达学院学报, 2011, 5 (25) :339-342.

[3]何友, 修建娟, 张晶炜, 等.雷达数据处理及应用 (第二版) [M].北京:电子工业出版社, 2009:160-161.

[4]Tenne D.Optimal Design ofα-β-γFilters.Proceedings of the American Control Conference[J].Chicago IL USA, 2000, (6) :4348-4352.

[5]Y.Bar-Shalom, T.E.Fortmann.Tracking and Data Association[M].Academic Press, 1988.

α+**算法 篇5

1传统的二阶Volterra LMP算法

一个截断二阶Volterra滤波器输入输出关系为:

其中N是记忆长度,输入向量为:

其中,X1T(n),X2T(n)分别为线性部分和非线性部分的输入向量:

相应地,Volterra滤波器的权向量为:

n时刻线性部分的权向量为:

非线性部分的权向量为:

所以整个系统的输出为y(n)=HT(n)X(n)。

传统的Volterra LMP算法是将Volterra滤波器建模成一个伪线性算子,从而可以直接利用α稳定分布下线性滤波器的LMP算法,得到VLMP算法的权向量修正公式[5]:

在α稳定分布背景下Volterra滤波器的非线性项将稳定分布的尖峰脉冲特性放大,导致输入信号自相关矩阵的特征值扩展更大,只用一个收敛因子同时调整线性部分和非线性部分的权值后的收敛性能仍然很不理想。

2α稳定分布下Volterra滤波器的数据块算法

现构建由n时刻及其前m-1个时刻的输入矢量所构成的矩阵,分别表示如下:

分别记D(n)和ξ(n)为由n时刻及其前m-1个时刻的期望输出矢量和相应的误差矢量,表示为:

则误差矢量ξ(n)可以表示为:

在α稳定分布下,基于最小分散系数(MD)准则[4]的代价函数为:

以误差信号的瞬时值代替其统计平均,得到梯度估计[6]为:

其中:

由此可以得到α稳定分布下Volterra滤波器数据块LMP(DBVLMP)算法的权系数调整公式如下:

3算法仿真与性能分析

在α稳定分布环境下,将本文算法应用于非线性系统辨识。非线性系统期望输出信号为:

d(n)=0.7x(n)+0.4x(n-1)-0.5x2(n)+0.1x2(n-1)-0.2x(n)x(n-1)+v(n),其中,v(n)为特征指数为α、分散系数γ为1、对称参数和位置参数均为0的α稳定分布(称为标准对称α稳定分布)噪声,输入信号x(n)=0.5x(n-1)+s(n),s(n)为均值为0的高斯噪声。令var_x为x的方差,定义广义信噪比为,设GSNR=30。用权系数误差范数如式(16)所示分析算法的收敛性能。每条曲线由20次独立实验求平均得到。

实验一:比较m=1时的DBVLMP算法和VLMP算法。特征指数α=1.8标准对称α稳定分布环境中权值h0曲线和权系数误差范数曲线如图1和图2所示。

m=1时,DBVLMP算法退化为一般的采用2个收敛因子分别对线性部分和非线性部分进行调整的改进型VLMP算法。由图1可知,m=1时的DBVLMP算法权值h0能快速稳定地收敛,而VLMP算法不能正常工作;从图2可看出,本文算法表现出了远比VLMP算法优越的性能;说明对权向量的线性项部分和非线性项部分采用不同的收敛因子可以大大改善VLMP算法性能。

实验二:在不同特征指数标准对称α稳定分布下,m对DBVLMP算法性能的影响。取不同值时DBVLMP算法权系数误差范数曲线和权值的仿真结果如图3~图6所示。

图3和图5给出了当特征指数α=1.8和α=1.3,m取不同数时,本文算法的权系数误差范数曲线。由图可知,随着m的增大,DBVLMP算法的收敛速度越来越快,但是这种加快的趋势在减小;m燮10时,增大m,DB-VLMP算法收敛速度提高明显;m叟10时,增大m,收敛速度提高缓慢。图4和图6所示的是取m=10时,不同特征指数下DBVLMP算法的权值的收敛曲线。由图可知,在不同脉冲噪声背景下,DBVLMP算法都能够非常快速地收敛到期望权值。同时,当算法收敛时,没有因为大幅度的脉冲噪声而出现大的抖动,这说明DBVLMP算法对脉冲噪声有较强的韧性。

本文提出了α稳定分布下Volterra滤波器的一种数据块LMP新方法,该算法分别采用不同的收敛因子,自适应调节滤波器权向量的线性项部分和非线性部分,利用了更多的输入信号和误差信号的信息估计梯度,从而获得比VLMP算法更高的滤波过程的收敛速度和精度。

摘要：基于分数低阶统计量原理提出了α稳定分布下Volterra滤波器的数据块滤波算法。该算法对Volterra滤波器权向量的线性项部分和非线性项部分分别采用不同的收敛因子,克服了传统只采用一个收敛因子的Volterra滤波器算法收敛性能差缺点,利用更多的输入信号和误差信号信息,更好地估计梯度,更精确地调节自适应滤波器权向量,提高了收敛速度。仿真结果验证了该方法的优越性。

关键词：α稳定分布,Volterra滤波器,数据块,自适应滤波,梯度

参考文献

[1]TAN L,JIANG J N.Adaptive volterra filters for active control of nonlinear noise processes[C].IEEE Transaction on Acoustics Speech and Signal Processing,2001,49(8):1667-1676.

[2]ZHOU Da Yong,DEBRUNNER V,ZHAI Yan.Efficient adaptive nonlinear ECHO cancellation,using sub-band implementation of the adaptive volterra filter[C].IEEE international Conference on Acoustics,Speech and Signal Processing,2006,(5):277-280.

[3]MATHEWS V J.Adaptive polynomial filters[J].IEEE Signal Processing Magazine.1991,8(3):10-26.

[4]邱天爽,张旭秀,李小兵,等.统计信号处理[M].北京:电子工业出版社,2004.

[5]WENG Bin Wei,NONLINEAR K E.Nonlinear system identification in impulsive environments[C].IEEE Transac-tions on signal processing,2005,53(7):2588-2594.

α+**算法 篇6

关键词：微电网,优化,α约束支配,进化算法,多属性决策,模型

0引言

随着节能减排的需求逐渐增强,分布式发电DG (Distributed Generation)的利用率也逐渐增加 ,由小容量分布式电源形成的微电网研究也逐渐深入[1,2]微电网将微型燃气轮机、燃料电池、光伏电源和风力发电机等分布式电源通过电力电子接口等方式联合在一起,为负荷端提供电能和热能。 根据微电网与常规配电网的连接与否,将其划分为并网、孤岛2种运行模式[3,4]。

微电网的经济运行与优化调度一直是国内外研究的热点,微电网运行优化问题的研究中,优化目标多种多样,如电能质量等技术目标、运行成本等经济目标、排污成本等环境目标,其中经济目标和环境目标是目前微电网运行所考虑的主要优化指标[5,6,7],鉴于微电网内基于化石燃料的分布式电源运行时会产生一定的碳排放,且排放量与其出力密切相关,同时基于国家“十二五”规划对低碳经济更为重视,本文将以运行成本和CO2排放量最小化为目标构建微电网多目标优化运行模型。

微电网的多目标优化运行是一个复杂的带多种等式约束和不等式约束条件的多目标优化问题,采用多目标优化算法求解其帕累托(Pareto)最优解集是一种常用手段[8]。 然而如何在优化算法中方便快捷地处理这些约束条件一直是各学者所致力研究的难题,常用的约束处理方法有罚函数法及多目标法等[9,10],这些方法都存在不足之处。 罚函数法为个体加入惩罚项,将约束问题简化成无约束问题,但惩罚项的设计多种多样,很难找到一个确切方案;多目标法将个体违反约束条件的程度作为优化指标,增加了优化问题目标函数的个数,计算更加复杂。 随着约束条件数量的增加,传统的约束处理方法复杂度也大幅增加。 因此,本文提出一种新型的 α 约束支配排 序混合进 化算法 α-CDSHEA (α-Constrain Dominant Sorting Hybrid Evolution Algorithm),可显著提高约束处理效率,降低算法的复杂度。 同时,为有效利用种群的宏观分布信息和个体信息,保持种群多样性,提高算法的收敛性和寻优速度,提出一种微分进化算法DEA(Differential Evolution Algorithm以及分布估计算法EDA(Estimation of Distribution Algorithm)相融合的混合进化算法 。 最后,通过分类逼近理 想解的排 序TOPSIS (Technique for Orde Preference by Similarity to an Ideal Solution)方法对算法得到的Pareto最优解集进行多目标决策,以获得最优折中解。

本文将以一个含光伏PV(Photo Voltaic)、风机WT (Wind Turbine)、微型燃气轮机MT(Micro Turbine) 燃料电池FC(Fuel Cell)以及负荷的微电网为算例分别用 α-CDSHEA、采用常规罚函数约束处理方法的非劣 排序微分 进化算法NSDEA (Non-dominate Sorting Differential Evolution Algorithm)和动态加权遗传算法(GA)进行求解,对比各自得到的Pareto最优前沿和运行时间,测试本文提出算法的有效性。

1微电网运行数学模型

1.1分布式电源模型

1.1.1微型燃气轮机模型

微型燃气轮机运行时的耗量特性[11]可描述为:

其中,PMT(t)为微型燃气轮机t时刻的功率 (k W);Δt为微型燃气轮机运行时间(h);ηMT(t)为微型燃气轮机t时刻发电效率;RLHVf为天然气低位热值(k W·h/m3); VMT(t)为 Δt运行时间内微型燃气轮机消耗的天然气量(m3)。

1.1.2燃料电池模型

燃料电池的耗能特性与微型燃气轮机类似[11], 可描述为:

式中各参数的意义参照式(1)。

光伏和风机的功率外特性模型分别参照文献 [12]和文献[13]。

1.2优化运行目标函数

1.2.1运行成本目标函数

运行成本目标函数F1包括投资折旧成本、运行维护成本、燃料成本以及微电网与外网的交互成本[14,15]:

其中,CDP(t)、COM(t)、Cfuel(t)、Cgrid(t) 分别为t时刻各DG的投资折旧成本 、运行维护成本 、燃料成本以及微电网向外网的购电成本;NG为系统DG总数;Caz,i为第i个DG的单位容量安装成本;Pi N为第i个DG的装机容量;r为年利率;ni为第i个DG的使用寿命;KOM,i为第i个DG的单位电量运行维护成本系数;Pi(t)为第i个DG在t时刻的有功输出 ;fi为第i个DG的燃料成本函数;CF为天然气的价格;CE(t)为t时刻微电网向外网购电的实时电价 ;Pgrid(t)为t时刻微电网向外网的购电量。

1.2.2CO2排放量目标函数

CO2排放量目标函数F2为[16]:

其中,ki为第i个DG的CO2排放系数;kgrid为配电网的CO2排放系数。

1.3约束条件

a. 潮流方程约束:

其中,Pfs、Qfs分别为节点f的有功和无功注入量;UfUg分别为节点f和g的电压;Gfg、Bfg、θfg分别为节点f和g之间的电导、电纳和相角差;g  f为与节点f相连的节点。

b. 功率平衡约束:

其中,Pd(t)为实时有功负荷;Ploss(t)为实时有功损耗。

c. 节点电压约束:

其中,Ui,min、Ui,max分别为节点i的最小、最大电压允许值;N为系统节点数。

d. 微电源的有功出力约束:

其中,Pi,min、Pi,max分别为第i个DG有功功率的最小、最大值。

e. 微电网与外网允许交互的传输功率约束 :

其中,Pgrid,max、Qgrid,max分别为微电网与外网允许交互的最大有功和无功功率。

f. CO2排放约束:

其中,Lmax为该地区CO2允许排放的最大限值。

2α-CDSHEA

2.1α约束支配排序

Takahama提出了 α 约束处理方法[17],α 约束方法将种群个体符合约束条件的程度数值化,提出了约束水平度的概念。 用 μ(x)表示个体x的约束水平度,且 μ(x) [0,1]。 μ(x)越大表示个体x属于可行解的概率越大,若 μ(x)=1,则表示个体x属于可行解。 约束水平度 μ(x)的值可由下式计算得出:

其中,hi(x)、gj(x) 分别表示个体的等式约束和不等式约束值;bi、bj分别为种群中不可行解对应的等式约束和不等式约束的平均值。

在得到个体x对应各约束条件的约束水平度之后,定义个体x的总约束水平度为:

从而定义 α 约束水平截集为:

对于个体x,如果xAα,则称之为满足 α 约束的个体。

由此可定义如下的 α 约束支配关系(用fα表示):

式(17)中,若个体x、y均满足 α 约束,即x,y∈Aα, 或者个体x、y的 α 约束水平度相等,即 μ(x)=μ(y),那么目标函数值f(x)、f(y)决定它们之间的支配关系; 否则,α 约束水平度 μ(x)、μ(y)决定它们之间的支配关系。

式(16)中的约束判定量 α 是一个时变量,可表示为 α(T),它随着进化代数T在0~1之间逐渐增加。 其初值 α(0)的大小由优化问题的可行域占全部搜索空间的比例决定,比例越大,α(0)可取的值越大。 α(T)可由下式计算得出:

其中,β 为 α 的控制参数,β [0,1],根据文献[17], 本文取 β=0.03。 由式(18)可以看出,在 β 的控制下, α 的值随着进化代数T增大逐渐增大到1,即 α 约束条件越来越严格,代表解集逐渐向可行域收敛。

将 α 约束支配关系作为主选择排序机制并以传统的非劣排序方法[18]为辅助排序机制引入多目标优化算法。 在算法种群进化过程中,父代和子代种群按以下原则进行选择和种群更新操作。

a. 父代群体P (T) 和子代种群P (T +1) 构成集合Q(T),将Q(T)分成满足 α 约束的子集Qf和不满足 α 约束的子集Qinf。

b. 将Qf中的个体进行 α 约束支配排序分级,同一级别的个体按非劣排序方法进行排序;将Qinf中的个体按 α 约束水平度大小进行排序。

c. 将Qinf中的个体按顺序排在Qf中的个体之后更新集合Q(T),按照种群规模M在Q(T)中选择前M位的个体更新子代种群P(T+1)。

设最优前沿的个体集合为Bbest(Bbest最终输出即为Pareto最优解集),初始Bbest为空集,在产生初始种群并进行种群排序后,将满足 α 约束的个体储存其中。 种群进化过程中,考察Qf中满足 α 约束的全部个体xi与Bbest中的全部个体yj之间的 α 约束支配关系,Bbest的更新操作按以下原则进行:如果xi被yj支配,Bbest集合不变;如果xi支配yj,则从Bbest中删去yj并加入xi,即Bbest= (Bbest- yj)∪xi。

Bbest的规模如果超过预定值,则按非劣排序方法对其中个体进行排序,删去排序靠后的个体以保持其规模恒定。

2.2混合进化算法

文献[18]提出NSDEA,它是一种基于DEA的多目标优化算法。 DEA是一种非常优秀的进化优化算法,具有结构简单、鲁棒性强、收敛性好、易于与其他进化算法混合等特点[19]。 至今为止,DEA已发展出多种进化策略[20]。 本文采用的DE / best / 2 / bi策略简述如下。

a. 变异。

在种群进化到第T代时,通过下式变异产生新个体:

其中,vi,T为变异得到的新个体;xbest,T为全局最优个体;F为缩放因子,F  (0,1);xr1,T、xr2,T、xr3,T、xr4,T为随机抽取的4个个体。

b. 交叉。

进化群体Xi,T+1和变异之后的群体Vi,T+1通过下式进行交叉产生新个体:

其中,uj,i,T+1为交叉位;k为随机整数;rand(0,1)为随机产生的0~1之间的数;δCR为交叉概率。

然而,上述DEA在进化过程中,种群会较快失去个体多样性而导致变异差分项趋于0,使得寻优停滞或陷入局部搜索。 EDA是一种基于统计学原理的新型进化算法[21],不同于传统进化算法采用交叉、变异等进化手段,EDA通过建立概率模型描述解集在搜索空间的分布信息,然后采用随机采样从群体宏观角度进化产生子代,能充分利用群体的智能信 息,具有较强的全局搜索能力。 为此本文拟将EDA基于整个种群统计信息的宏观层面控制种群进化的模式与DEA基于个体变异、交叉的传统进化模式相融合,提出一种混合进化算法,可有效加强算法的种群多样性,提高其收敛速度并防止早熟收敛。 本文采用基于高斯分布建模的连续域EDA,其建模原理简述如下。

用一个概率向量pT(x)来表示第T代种群的概率分布,pT(x)=(pT(x1),pT(x2),…,pT(xM))。 从其中选择m个优势个体,本文取m = M / 2,假设其满足以下高斯分布:

其中,N(xi; μiT; σiT)为关于xi、 μiT、σiT的高斯分布。 各代的均值 μi和方差 σi2估计如下:

其中,xiT,1、xiT,2、…、xiT,m为第T代种群的m个优势个体。

3算法求解步骤

3.1Pareto最优解集

本文提出的 α-CDSHEA流程如图1所示。

综上所述,α-CDSHEA的Pareto最优解求解步骤如下。

a. 种群初始化 。 进化代数T = 0, 最优前沿以一天24 h各时段的微型燃气轮机 、 燃料电池有功出力和微电网向电网的实时购电量为个体变量,随机产生初始种群P(T),计算种群的适应度f和针对各约束条件的约束值[gj(x) hi(x)],然后计算个体的 α 约束水平度进而得到个体的总 α 约束水平度。

b. 排序并选择优势个体。 对种群进行 α 约束支配排序和非劣支配排序,选择前一半个体形成优势种群,并更新最优前沿集合Bbest。

c. 种群进化产生子代 。 根据优势种群建立概率分布模型,分别用DEA和EDA进化产生子代种群P1(T + 1)和P2(T + 1),计算子代种群的适应度f和约束值[gj(x) hi(x)],并计算个体的 α 约束水平度和总 α 约束水平度。

d. 选择和种群更新 。 依据2.1节中的操作原则更新种群P(T+1)和最优前沿集合Bbest。

e. 判断 。 若达到进化代数要求且最优前沿集合Bbest达到预定规模,进入下一步;否则T =T +1,转步骤b。

f. 输出最优前沿集合Bbest中的个体为最终的Pareto最优解。

3.2最优折中解

为挑选最优折中解,决策者需根据偏好对Paret最优解集 进行筛选 排序 。 Hwang和Yoon提出的TOPSIS方法[22]通过计算Pareto最优解集和理想解的距离,使其与理想解距离最近,并且与负理想解距离最远,判断解集的优劣并排序。 以r个目标、l个解为例,其排序流程如下:

a. 对原始决策矩阵X =[xij]l ×r进行向量规范化, 得到规范化决策矩阵Y=[yij]l×r;

b. 构成加权规范化决策矩阵Z = [zij]l×r,其中zij= τjyij,τ=[τ1,τ2,…,τr]T为决策者给定的加权向量;

c. 确定正理想解Z+和负理想解Z-;

d. 计算各个解到正理想点的距离di+和到负理想点的距离di-;

e. 计算各个解的综合评价指数, 进而排序 。

其中的加权向量τ 可采用客观赋权的变异系数法[23]确定 , 其流程如下 : 计算各目标的均值和方差计算各目标的变异系数将变异系数归一化 , 可得各目标的加权系数

4算例分析

4.1微电网结构与参数

本文以一个含光伏发电、风力发电、微型燃气轮机、燃料电池4种微源的微电网系统为例[24],如图2所示,馈线L1为民用负荷(功率因数为0.85),馈线L2、 L3分别为工业负荷和商业负荷(功率因数为0.90)。

本文作如下假设:在单位时间间隔内,各微源的有功和无功出力恒定、负荷需求恒定、微电网与主网间的交互功率恒定且交互电价维持恒定。 本文取单位时间间隔为1 h。

微电网中各线路参数以及各节点最大负荷如表1所示,表中R、X和Smax分别为线路电阻、电抗和末节点最大负荷。 实时的民用负荷、工业负荷、商业负荷占节点最大负荷的百分比如图3所示。 微电网与外网允 许传输的 最大有功 和无功功 率分别设 为75 k W和46.48 kvar(传输线功率因数0.85),实时电价见文献[25],天然气价格为3元 / m3,各DG的运行成本系数、CO2的排放系数以及某地区CO2的排放限值见文献[26],微电网中各DG的参数见表2。

光伏和风机均为不可控的分布式电源,采用最大功率跟踪输出模型,且由于光伏、风机发电成本低和污染物排放率低,本文假设其为零运行成本、零排放。 根据某日的光照和风力强度,假定光伏和风机的预测日小时出力如图4所示。

4.2优化结果

为了证明本文算法在处理复杂约束多目标优化问题上的优越性,分别用 α-CDSHEA、采用常规罚函数约束处理方法的NSDEA以及动态加权遗传算法对本文算例进行求解,得到该日微电网运行成本和CO2排放量的Pareto最优解集。 3种算法的种群规模均设为100,α-CDSHEA和NSDEA的微分进化缩放因子均为0.85,交叉概率为0.5,α-CDSHEA的 α 初值设为0.5。 本文中遗 传算法直 接调用现 成的MATLAB遗传算法工具箱(GAOT)[27],由于该软件包不能直接求解多目标优化的Pareto前沿,为此需对双目标函数进行加权使之转化成单目标函数,鉴于加权值难以确定,可通过在0~1之间均匀取100个动态权值构造动态加权遗传算法,以间接获得Pareto前沿。 本文运行算法硬件环境的CPU为Intel Core i53317 @ 1.70 GHz 1.70 GHz , 仿真环境为MATLAB R2013a。 以上3种算法各自运行100代得到的优化曲线如图5所示,运行时间如表3所示。

图5中曲线对比可以看出,α-CDSHEA比采用常规罚 函数约束 处理方法 的NSDEA最终得到 的Pareto前沿分布更加均匀 、解集更加全面 。 而采用GAOT通过动态加权函数优化得到的解集明显劣于 α-CDSHEA,与真正的Pareto最优解集相差甚远。 另外,由于采用GAOT求解多目标优化问题需要不断动态改变权值进行单目标优化,因此表3中GAOT运行时间远大于 α-CDSHEA和NSDEA。 而 α-CDSHEA所需要的运行求解时间略小于NSDEA,实际上由于 α-CDSHEA是融合了DEA与EDA这2种不同算法机制的混合算法,其理论运行时间应远大于NSDEA,但本文提出的约束处理方法有效降低了算法的复杂度,导致最终运行时间略小。

为进一步 比较 α-CDSHEA和NSDEA在得到Pareto解集时在收敛速度上的优劣 ,取各自运行25代时的优化曲线对比,如图6所示。

由图6可知,运行至25代时,α-CDSHEA已基本收敛,而NSDEA还远未达到收敛,可见 α-CDSHEA的收敛速度要高于NSDEA,说明引进 α 约束处理方式和混合进化算法是有效、可行的。

经过对 α-CDSHEA优化得到的Pareto前沿进行最终多目标决策优选,可得到该日最终运行成本和CO2排放量分别为4 101.2元和68.236 8 kg,对应的该日微型燃气轮机、燃料电池的有功出力及微电网系统与电网的交互购电优化结果如图7所示。

为保证微电网的独立性,当网内DG输出足够满足负荷需求时,不向外网购电,此时相当于孤岛运行;当网内DG输出无法满足负荷需求时,在允许传输限值范围内向外网购电,此时相当于并网运行。 从图7中可以看出,01:00 — 08:00时微型燃气轮机和燃料电池的出力足够满足网内负荷安全有效运行不需要向外网购电;09 : 00 — 14 : 00、16 : 00 — 19 : 00 22 : 00 — 24 : 00,微型燃气轮机和燃料电池的出力满足不了网内负荷需求,故需要向外网购电 ;15:00 19:00 — 21:00, 微型燃气轮机 、 燃料电池的出力配合向外网购电仍然不能满足网内负荷需求,存在有功缺额,此时微型燃气轮机和燃料电池为最大功率输出,向外网所购电量也达到传输上限,此时为保证微电网安全有效运行,应适当切除民用负荷。 微电网的无功负荷也由微型燃气轮机和燃料电池共同负担,并配合少量外网提供的无功出力。

5结论