推理算法

推理算法（共8篇）

推理算法 篇1

0 引言

现代大型复杂系统的贝叶斯网络结构也是庞大复杂的,对于诊断推理存在困难。因此在进行诊断推理前,应适当地对其网络结构进行简化。本文采用分簇优化联合树算法对贝叶斯网络结构进行简化处理及推理运算,下面介绍分簇优化联合树算法及其用于网络参数学习及诊断推理算法。

1 分簇搜索算法基本思想

用于故障诊断的贝叶斯网络的结构是非常复杂的,并且由于其结构的复杂性致使故障诊断推理也非常复杂,因此,通过贝叶斯网络结构学习,寻找一个与训练数据拟合度高且网络复杂性相对较低的网络结构成为一个非常有意义和研究价值的问题。由式可知,n个变量构成的贝叶斯网络结构的数目是指数级的,要从这些可能存在的网络结构空间中搜索出最优的网络结构也是很难的。当n=10时,需要搜索的模型个数就已经达到约为4.17*1018,可见搜索空间太大,为了缩小搜索空间,有效地找到最优解,一个较好的搜索算法就非常必要。

贝叶斯网络结构的学习实际就是优化搜索的问题。基于分簇的优化搜索方法就是将问题节点划分为团簇结构。团簇结构思想最早用于物理和化学领域中对分子和原子的处理,而在近代,团簇结构在许多领域得到了广泛的应用,包括模式识别,数据分析,图像处理等。许多学者都在这方面做出了研究,旨在发现能够用于更好聚类方法的簇结构,不同的网络拓扑结构对于分簇算法都是不同的。人工智能越来越多地研究这种方法,使之成为一种较为优秀的搜索算法。基于簇的搜索方法被证实较好地用于解决TSP问题。这种方法的主要优势在于不会陷入局部最优,并且搜索时间非常短。

分簇算法的基本思想是把网络结构中的节点划分为若干个簇,簇内依据某种事先约定的值进行连接,在簇与簇之间,也根据这种约定进行点与点之间的连接,这里设定一个阀值,节点间的关联程度大于这个阀值时就连接这两个节点,最终基于簇的这种搜索算法将形成一个团簇树状结构。

基于簇的结构学习算法是由初始的贝叶斯网络结构经过优化搜索构造出用于诊断的树形结构。设用于该算法的阀值为θ,由当前信息得到相关节点的关联程度为θij,表示第i个节点和第j个节点的关联程度,设两个数据结构D 1,D 2分别存放局部网络的起始参数节点表和目标节点表,首先把网络的所有节点都放入D 1表中。具体的步骤如下:

步骤1:随即选取一个起始节点V1,比较与V1相关的各个节点的θ1k值,若θ1k≥0,则将V1和Vk划分到一个簇S1内,把簇S1中的节点都从D1表中移出,放入表D2中。

步骤2:如果D1为空表,则转到步骤4。

步骤3:在D1表中随即选取一个节点Vn,比较与Vn相关的各个节点,分两种情况:

(1)若无关联节点,则将Vn单独划分到簇S2中,并将节点Vn从表D1中移出,放入表D2中,转入步骤2。

(2)若有关联的节点,且关联值为θnm,若θnm≥0,则将Vn和Vm划分到一个簇S2中,把簇S2中的节点从D1表中移出,放入表D2中,转入步骤2。

步骤4:在簇到S1之Sn间,观察是否簇间有相关联的节点,若相关联,且关联值θij≥θ,则将Vi与Vj相连接。

该算法的最终目的是搜索出一个较为简单的网络结构,减少网络推理的复杂度,使学习后的网络结构能够使用精确推理算法来实现推理,得出一个较为准确的结果。

搜索的过程如图1所示。

从图1可以看出,在经过分簇搜索之后,网络结构(d)比网络结构(a)有了一定程度的简化。

有效的贝叶斯网络推理算法是贝叶斯网络的重要内容,也是其应用的前提。大型复杂的故障诊断系统,所建立的贝叶斯网络模型也具有非常复杂的结构,为了降低贝叶斯网络的推理复杂度,使其更容易应用于解决实际问题,一般的推理算法都是在简化网络结构上进行研究的。下面来分析经过分簇结构优化算法后的网络推理。

2 联合树推理

分簇优化联合树算法实现对贝叶斯网络的诊断推理。分簇优化联合树算法是分簇优化算法与联合树算法的结合,其流程图如图2所示。分簇优化已在前文介绍,下面介绍流程图中其余步骤。

2.1 贝叶斯网络转化为联合树

将贝叶斯网络B转化为联合树,分为四步:建立B的Moral图;三角化Moral图;确定所有的团(Cliques);建立联合树。

(1)建立B的Moral图

简历Moral图的过程就是找出每个节点的父节点,并将他们用无相边两两相连,同时将所有有向边改为无向边。

(2)三角化Moral图

在Moral图中添加一些无向边,使图中每个大于或等于4的环中,都存在一条边连接两个非相邻节点。这就完成了对Moral图的三角化。

(3)确定所有的团(Cliques)

对Moral图三角化的目的就是找到构成联合树的所有团。团是Moral图三角化后最大的全连通子图,团中每对不同的节点都有边相连。

(4)建立联合树

利用得到的团,添加一些边和分隔节点就可构造一棵联合树T。联合树T要满足:树中任意两个团C,C′在连接它们的路径上的所有团节点必须包含变量C∩C′。

2.2 初始化

将贝叶斯网络转化为联合树后,就要对联合树的所有节点指定参数,即对联合树进行初始化。下面的算法实现了对满足条件的联合树参数的指定。

若联合树中的团Ci由X1,X2,…,Xr,r个节点组成,每一个节点有Sr个状态,则共有个状态组合。i代表Ci的分布函数,ij代表图Ci第j个状态组合的分布函数。具体步骤是:

for一个随机变量V

找到包含V的家庭的团Ci;

fori=1,…,n(n为团的数目)

orj=1,…,m(m为团C状态组合的个数)

初始化Φij,使Φij=1;

forj=1,…,m

Φij=Φij*P(Vj|Pa(Vj))

2.3 消息传递

对联合树进行初始化后,要在联合树上进行消息传递。通过个团节点之间的消息传递,可以是联合树达到全局一致,即达到稳态。如图3所示是团节点间一次消息传递的过程。

从节点Ci到Cj的一次消息传递过程包括以下几步:

(1)产生消息:

(2)吸收信息,更新团结点的分布函数:

(3)更新分隔节点的分布函数:

2.4 概率计算

当一个联合树通过消息传递满足全局一致性后,即可计算任意随机变量V的概率分布。找到任意一个包含变量V的团节点C,通过可计算出变量V的分布。

2.5 加入证据

若有新的证据加入,重复证据收集和证据扩散的过程,直到得到全局一致的联合树为止。当联合树再次满足全局一致性时,对任意的团C有:C=P(C,e),(e表示加入的证据)。要计算假设的变量V的概率分布,首先找到任意一个包含变量V团结点C,,再根据条件概率公式,求出变量V的概率分布

3 结束语

有效的贝叶斯网络推理算法是贝叶斯网络的重要内容,也是其应用的前提。大型复杂的故障诊断系统,所建立的贝叶斯网络模型也具有非常复杂的结构,为了降低贝叶斯网络的推理复杂度,使其更容易应用于解决实际问题,一般的推理算法都是在简化网络结构上进行研究的。而分簇简化联合树算法在对网络结构简化之后再进行网络推理,一定程度上简化了网络推理的难度。

摘要：大型复杂贝叶斯网络的诊断推理存在困难,在其推理诊断之前对网络结构进行适当的简化,可以有效地加快诊断推理速度。采用分簇联合树算法实现对网络结构的简化与推理。主要介绍了分簇搜索算法的基本思想、实现步骤及联合树推理算法,并将它们结合使用,使贝叶斯网络的简化推理更有效。

关键词：贝叶斯网络,概率推理,分簇理论,联合树

参考文献

[1]Wang Weidong,Zhu Qingxin.A Hierarchical Clustering Algorithmand Cooperation Analysis for Wireless Sensor Networks[J].Journalof Software,2006,17(5):1157-1167.

[2]Stephenson T.A.An Introduction to Bayesian Network Theory andUsage[Z].IDIAP-PR,Feb,2000.

[3]Gregory F Cooper,Edward Herskovits.A Bayesian method for theinduction of probabilistic networks from data[J].Machine Learning(S0885-6125),1992,9(4):309-347.

[4]衡星辰,覃征,邵利平,等.动态贝叶斯网络在复杂系统中建模方法的研究[J].系统仿真学报,2006,18(4):1002-1005.

[5]邢永康.信度网理论及应用研究:[D].重庆:重庆大学,2001.

[6]Huang C,Darwiche A.Inference in belief networks:a proceduralguide[J].International Journal of Approximate Reasoning,1994,11:1-58.

推理算法 篇2

【2013年高考会这样考】 1．数学归纳法的原理及其步骤．

2．能用数学归纳法证明一些简单的数学命题． 【复习指导】

复习时要抓住数学归纳法证明命题的原理，明晰其内在的联系，把握数学归纳法证明命题的一般步骤，熟知每一步之间的区别联系，熟悉数学归纳法在证明命题中的应用技巧．

基础梳理

1．归纳法

由一系列有限的特殊事例得出一般结论的推理方法，通常叫做归纳法．根据推理过程中考查的对象是涉及事物的全体或部分可分为完全归纳法和不完全归纳法． 2．数学归纳法

(1)数学归纳法：设{Pn}是一个与正整数相关的命题集合，如果：①证明起始命题或成立；②在假设{Pn}对一切正整数成立．

(2)用数学归纳法证明一个与正整数有关的命题时，其步骤为： ①归纳奠基：证明当取第一个自然数n0时命题成立；

②归纳递推：假设n＝k，(k∈N*，k≥n0)时，命题成立，证明当时，命题成立； ③由①②得出结论．

两个防范

数学归纳法是一种只适用于与正整数有关的命题的证明方法，第一步是递推的“基础”，第二步是递推的“依据”，两个步骤缺一不可，在证明过程中要防范以下两点：(1)0时，n0不一定为1，要根据题目要求选择合适的起始值．

(2)第二步中，归纳假设起着“已知条件”的作用，在证明n＝k＋1时，命题也成立的过

程中一定要用到它，否则就不是数学归纳法．第二步关键是“一凑假设，二凑结论”． 三个注意

运用数学归纳法应注意以下三点：双基自测

1．在应用数学归纳法证明凸n边形的对角线为2n(n－3)条时，第一步检验第一个值n0 等于()．

A．1B．2C．3D．0 解析 边数最少的凸n边形是三角形． 答案 C

12．利用数学归纳法证明不等式1＋f(n)(n≥2，n∈N*)的过程，由n＝k

232－1到n＝k＋1时，左边增加了()．

A．1项B．k项C．2k－1项D．2k项

1111111111＋„＋解析 1＋2＋3„＋＋＝＋„＋＋＋232－122＋12－12－1了2k项，故选D.答案 D

3．用数学归纳法证明：“1＋a＋a＋„＋a左端计算所得的项为()． A．1C．1＋a＋a2答案 C

4．某个命题与自然数n有关，若n＝k(k∈N*)时命题成立，那么可推得当n＝k＋1时该命

B．1＋aD．1＋a＋a2＋a

32n＋1

1－an＋

2(a≠1，n∈N*)”在验证n＝1时，1－a

题也成立，现已知n＝5时，该命题不成立，那么可以推得()． A．n＝6时该命题不成立C．n＝4时该命题不成立

*

B．n＝6时该命题成立 D．n＝4时该命题成立

tan kα

tan α·tan 2α＋tan 2α·tan 3α＋„＋tan(k－1)α·tan kα＝tan α－k，那么当n＝k＋1时，tan α·tan 2α＋tan 2α·tan 3α＋„＋tan(k－1)α·tan kα＋tan kα·tan(k＋1)α tan kα

＝tan αk＋tan kα·tan(k＋1)α tan kα

＝tan α1＋tan kα·tan(k＋1)α－(k＋1)tan kαtank＋1α－tan kα＝tan α－(k＋1)

tan[k＋1α－kα]

解析 法一 由n＝k(k∈N)成立，可推得当n＝k＋1时该命题也成立．因而若n＝4成立，必有n＝5成立．现知n＝5不成立，所以n＝4一定不成立．

法二 其逆否命题“若当n＝k＋1时该命题不成立，则当n＝k时也不成立”为真，故“n＝5时不成立”⇒“n＝4时不成立”． 答案 C

5．用数学归纳法证明不等式

11113

＋＋„＋＞24的过程中，由n＝k推导n＝k＋1n＋1n＋2n＋n

tank＋1α

＝tan α－(k＋1)．

这就是说，当n＝k＋1时等式也成立．

由(1)(2)知，对任何n∈N*且n≥2，原等式成立．

用数学归纳法证明等式时，要注意第(1)步中验证n0的值，如本题要取n0＝2，在第(2)步的证明中应在归纳假设的基础上正确地使用正切的差角公式． 【训练1】 用数学归纳法证明： 对任意的n∈N*，111n1×33×52n－12n＋12n＋1

1111

＝3，右边＝3，左边＝右边，所以等式成立． 1×32×1＋1

时，不等式的左边增加的式子是________． 解析 不等式的左边增加的式子是1

2k＋12k＋2答案

2k＋12k＋2

考向一 用数学归纳法证明等式

【例1】►用数学归纳法证明：

tan nα

tan α·tan 2α＋tan 2α·tan 3α＋„＋tan(n－1)α·tan nα＝tan αn(n∈N*，n≥2)． [审题视点] 注意第一步验证的值，在第二步推理证明时要注意把假设作为已知． tan 2α22tan2α证明(1)当n＝2时，右边＝tan α－2＝2＝＝tan α·tan 2α＝左边，等式

1－tanα1－tanα成立．

(2)假设当n＝k(k∈N*且k≥2)时，等式成立，即

1111

＋－＝，故填2k＋12k＋2k＋12k＋12k＋2

证明(1)当n＝1时，左边＝

(2)假设当n＝k(k∈N*且k≥1)时等式成立，即有 111k 1×33×52k－12k＋12k＋1则当n＝k＋1时，1111

1×33×52k－12k＋12k＋12k＋3k2k＋3＋1k1＝2k＋12k＋12k＋32k＋12k＋3

2k2＋3k＋1k＋1k＋1＝ 2k＋12k＋32k＋32k＋1＋1所以当n＝k＋1时，等式也成立． 由(1)(2)可知，对一切n∈N*等式都成立．

考向二 用数学归纳法证明整除问题

【例2】►是否存在正整数m使得f(n)＝(2n＋7)·3n＋9对任意自然数n都能被m整除，若存在，求出最大的m的值，并证明你的结论；若不存在，说明理由． [审题视点] 观察所给函数式，凑出推理要证明所需的项．

解 由f(n)＝(2n＋7)·3n＋9得，f(1)＝36，f(2)＝3×36，f(3)＝10×36，f(4)＝34×36，由此猜想：m＝36.下面用数学归纳法证明：(1)当n＝1时，显然成立；

(2)假设n＝k(k∈N*且k≥1)时，f(k)能被36整除，即f(k)＝(2k＋7)·3k＋9能被36整除；当n＝k＋1时，[2(k＋1)＋7]·3k＋1＋9＝(2k＋7)·3k＋1＋27－27＋2·3k＋1＋9＝3[(2k＋7)·3k＋9]＋18(3k－1－1)，由于3k－1－1是2的倍数，故18(3k－1－1)能被36整除，这就是说，当n＝k＋1时，f(n)也能被36整除．

由(1)(2)可知对一切正整数n都有f(n)＝(2n＋7)·3n＋9能被36整除，m的最大值为

36.证明整除问题的关键“凑项”，而采用增项、减项、拆项和因式分解等手段，凑出n＝k时的情形，从而利用归纳假设使问题获证． 【训练2】 用数学归纳法证明a

n＋

1a[ak＋1＋(a＋1)2k－1]＋(a2＋a＋1)(a＋1)2k－1，由假设可知a[ak＋1＋(a＋1)2k－1]能被a2＋a＋1整除，(a2＋a＋1)(a＋1)2k－1也能被a2＋a＋1整除，∴ak＋2＋(a＋1)2k＋1也能被a2＋a＋1整除，即n＝k＋1时命题也成立，∴对任意n∈N*原命题成立．

考向三 用数学归纳法证明不等式

1

【例3】►用数学归纳法证明：对一切大于1的自然数，不等式1＋3

12n＋11

1＋5·1＋2n－1>„·

[审题视点] 本题用数学归纳法证明不等式，在推理过程中用放缩法，要注意放缩的“度”．

5证明(1)当n＝2时，左边＝1＋3＝3；右边＝2.∵左边>右边，∴不等式成立．

(2)假设n＝k(k≥2，且k∈N*)时不等式成立，12k＋1111＋即1＋31＋5·„·>22k－1则当n＝k＋1时，1111

1＋31＋5·1＋2k－11＋2k＋1－1 „·2k＋12k＋22k＋24k＋8k＋42＝

2k＋122k＋122k＋14k＋8k＋32k＋32k＋12k＋1＋1

＝22 2k＋12 2k＋1∴当n＝k＋1时，不等式也成立．

由(1)(2)知，对于一切大于1的自然数n，不等式都成立．

＋(a＋1)

2n－1

(n∈N)能被a＋a＋1整除．

*

2证明(1)当n＝1时，a2＋(a＋1)＝a2＋a＋1可被a2＋a＋1整除．(2)假设n＝k(k∈N*且k≥1)时，ak＋1＋(a＋1)2k－1能被a2＋a＋1整除，则当n＝k＋1时，a

k＋2

＋(a＋1)

2k＋1

＝a·a

k＋1

＋(a＋1)(a＋1)

22k－1

＝a·a

k＋1

＋a·(a＋1)

2k－1

＋(a＋a＋1)(a＋1)

22k－1

＝

在由n＝k到n＝k＋1的推证过程中，应用放缩技巧，使问题得以简化，用数学

归纳法证明不等式问题时，从n＝k到n＝k＋1的推证过程中，证明不等式的常用方法有比较法、分析法、综合法、放缩法等．

【训练3】 已知函数f(x)＝33－x，数列{an}满足条件：a1≥1，an＋1≥f′(an＋1)．试比较11111的大小，并说明理由． 1＋a11＋a21＋a31＋an解 ∵f′(x)＝x2－1，an＋1≥f′(an＋1)，∴an＋1≥(an＋1)2－1.∵函数g(x)＝(x＋1)2－1＝x2＋2x在区间[1，＋∞)上单调递增，于是由a1≥1，得a2≥(a1＋1)2－1≥22－1，进而得a3≥(a2＋1)2－1≥24－1＞23－1，由此猜想：an≥2－1.下面用数学归纳法证明这个猜想： ①当n＝1时，a1≥2－1＝1，结论成立；

②假设n＝k(k≥1且k∈N)时结论成立，即ak≥2－1，则当n＝k＋1时，由g(x)＝(x＋1)

*

k

1n

当n＝2时，a1＋a2＝S2＝2×2－a2，∴a2＝2.7

当n＝3时，a1＋a2＋a3＝S3＝2×3－a3，∴a3＝41

5当n＝4时，a1＋a2＋a3＋a4＝S4＝2×4－a4，∴a482n－

1由此猜想an＝－(n∈N*)．

21－1

(2)证明 ①当n＝1时，左边＝a1＝1，右边＝1，左边＝右边，结论成立．

22k－1

②假设n＝k(k≥1且k∈N)时，结论成立，即ak＝－n＝k＋1时，*

ak＋1＝Sk＋1－Sk＝2(k＋1)－ak＋1－2k＋ak＝2＋ak－ak＋1，∴2ak＋1＝2＋ak，2k－12＋－22＋ak2k＋1－1

∴ak＋1＝＝，222这表明n＝k＋1时，结论成立，2n－1

由①②知猜想an＝－成立．

(1)归纳、猜想、证明是高考重点考查的内容之一，此类问题可分为归纳性问题

和存在性问题，本例从特例入手，通过观察、分析、归纳、猜想，探索出一般规律．(2)数列是定义在N*上的函数，这与数学归纳法所运用的范围是一致的，并且数列的递推公式与归纳原理实质上是一致的，数列中有不少问题常用数学归纳法解决．

1【训练4】 由下列各式1＞2 11

1＋231，11111131＋234567

2-4-

－1在区间[1，＋∞)上单调递增知，ak＋1≥(ak＋1)2－1≥22k－1≥2k＋1－1，即n＝k＋1时，结论也成立．

由①、②知，对任意n∈N*，都有an≥2n－1.1

1即1＋an≥2n，∴≤2，1＋an∴

11111111122221－2n＜1.1＋a11＋a21＋a31＋an

考向四 归纳、猜想、证明

【例4】►数列{an}满足Sn＝2n－an(n∈N*)．(1)计算a1，a2，a3，a4，并由此猜想通项公式an；(2)用数学归纳法证明(1)中的猜想．

[审题视点] 利用Sn与an的关系式求出{an}的前几项，然后归纳出an，并用数学归纳法证明．

解(1)当n＝1时，a1＝S1＝2－a1，∴a1＝1.11

11＋23152，11151＋2331

2„，你能得到怎样的一般不等式，并加以证明．

111n

答案 猜想：第n个不等式为1＋2＋3＋„＋＞2(n∈N*)．

2－11

(1)当n＝1时，1＞2

(2)假设当n＝k(k≥1且k∈N*)时猜想正确，111k即1＋2＋3＋„＋2

2－1那么，当n＝k＋1时，111111k111k11＋2＋32＋＋„＋＋＞2＋2＋＋„＋＋＞2＋＋＋

2－12＋12－12＋12－12k2kk1k＋1

＋„＋＋＋222222＋21

即当n＝k＋1时，不等式成立． ∴对于任意n∈N*，不等式恒成立．

阅卷报告20——由于方法选择不当导致失误

【问题诊断】 用数学归纳法证明与正整数有关的一些等式命题时，关键在于弄清等式两边的构成规律，等式的两边各有多少项，由n＝k到n＝k＋1时，等式的两边会增加多少项，增加怎样的项，其难点在于归纳假设后，如何推证对下一个正整数值命题也成立.【防范措施】 把归纳假设当做已知条件参加推理.明确对下一个正整数值命题成立的目标，通过适当的变换达到这个目标，这里可以使用综合法，也可以使用分析法，甚至可以再次使用数学归纳法.【示例】► 在数列{an}、{bn}中，a1＝2，b1＝4，且an，bn，an＋1成等差数列，bn，an＋1，bn＋1成等比数列(n∈N*)．

(1)求a2，a3，a4及b2，b3，b4，由此猜测{an}，{bn}的通项公式，并证明你的结论；(2)证明：

1115

＋＋„＋＜12.a1＋b1a2＋b2an＋bn

实录(1)由条件得2bn＝an＋an＋1，a2n＋1＝bnbn＋1.由此可得a2＝6，b2＝9，a3＝12，b3＝16，a4＝20，b4＝25.猜测an＝n(n＋1)，bn＝(n＋1)2.用数学归纳法证明：

①当n＝1时，由上可得结论成立．

②假设当n＝k(k≥1且k∈N*)时，结论成立，即ak＝k(k＋1)，bk＝(k＋1)2，a2k＋1

那么当n＝k＋1时，ak＋1＝2bk－ak＝2(k＋1)－k(k＋1)＝(k＋1)(k＋2)，bk＋1b＝(k＋2)2，k

所以当n＝k＋1时，结论也成立．

由①②，可知an＝n(n＋1)，bn＝(n＋1)2对一切正整数都成立．

错因 第二问由于不等式的右端为常数，结论本身是不能用数学归纳法证明的，可考虑用放缩法证明，也可考虑加强不等式后，用数学归纳法证明．(2)当n＝1时

115

＝6＜12 a1＋b1

假设n＝k(k∈N*)时不等式成立 即

1115

＋12a1＋b1a2＋b2ak＋bk

当n＝k＋1时

111151

＋＜12＋ a1＋b1a2＋b2ak＋bkak＋1＋bk＋1ak＋1＋bk＋1到此无法用数学归纳法证明． 正解(1)用实录(1)

(2)证明：

115

＝6＜12.a1＋b1

n≥2时，由(1)知an＋bn＝(n＋1)(2n＋1)＞2(n＋1)n.故

＋„＋ a1＋b1a2＋b2an＋bn

11111

＜622×33×4 nn＋111111111＝622334 nn＋11115111

基于遗传算法的知识推理研究 篇3

1 掌握学习理论

掌握学习理论是美国著名教育学家布卢姆在卡罗尔的“学校学习模式”的基础上提出的，关于教学系列化和管理结构化研究的一种个别化教学理论[2]，“矫正-反馈”系统是掌握学习理论的一大特色[3]。布卢姆认为在教学前和过程中应及时对学习者进行评价，这样才能给学习者呈现最有益的学习序列，做到因材施教。

2 课程难度

本文选取难度值较低的课程作为起始课程，这一做法符合了学习认知理论的循序渐进原则。首先由课程专家依据李克特氏5点量表对课程的难度系数进行初始化，然后根据学习者反馈信息调整课程难度参数[4]。因此，课程的难度系数逐渐趋于合理和稳定，能有效降低部分学习者的异常反馈信息，具体计算公式如下所示：

其中bj(tuned)是专家预设和学习者投票线性组合后的第j个课程自适应调整的难度参数;bj(initial)是由专家所给定的第j个课程的难度初始值;bj(voting)是由学习者在测验后投票出的第j个课程的平均难度;w是调节权重，可以随课程类型变化而变化。

3 课程相似度

从认知能力发展的角度来说，相近的课程更方便学习者完成知识的同化与顺应。为了呈现符合学习者认知能力背景和需求的最佳学习路径，课程的相似度就成为了重要的课题。

为了便于计算课程的相关性，我们使用向量空间模型(VSM)[5]对课程进行建模。令A=(A1,A2,⋯,An)表示由m个知识点术语构成的n个课程文档集合，其中Aj=(A1j,A2j,⋯,Amj)T是课程文档向量，Aij表示知识点术语i在课程文档j中的信息权重。

假设课程i和课程j的知识点术语集合的个数为n。课程i和j的相似度rij可以用余弦度量法来计算：

4 基于遗传算法的知识推理模型

基于遗传算法的知识推理模型如图1所示，其主要步骤如下：

1)由有经验的教师作为专家依据教学目标对每个课程设计相应的测试题目;

2)学习者进行测试得到相应的评估数据，即：学习者需要的课程以及课程难度系数;

3)分析模块将各课程的专家预设难度系数与学习者投票得出的难度系数进行线性调整，得出各课程的难度系数;

4)系统将学习者需要进行校正活动所对应的课程难度系数和课程之间的相似度系数送到基于遗传算法知识推理模块，为学习者推荐最优个性化课程序列。

5 基于遗传算法的推理模块

5.1 基于传统遗传算法的知识推理

1)染色体编码方法

假设课程库共有n个课程，给每个课程分配从1到n的序号[6]。每个课程分配的序号与其后续课程的序号相结合形成的染色体代表了个性化课程学习路径。

2)初始化种群

该文将生成一个以难度值最低的课程作为起始基因，由随机函数随机产生其它课程序列的初始种群。

3)选择算子

采用轮盘赌选择算子来完成选择操作。

4)交叉算子

采用两点交叉算子的变形，区域交叉算子[7]，作为交叉操作的方式。

5)变异算子

采用倒置变异[8]算子，也就是逆转变异算子作为变异操作的方式。

6)适应度函数

该文把个性化学习路径上的所有相继课程染色体之间的相似度系数之和作为适应度函数。染色体的适应度函数值越高,所得染色体越优越。推荐的适应度函数定义如下:

其中，r(i-1)i代表了连继的两个课程的相似度，n代表了所需考虑的总课程量。

7)仿真实验与分析

计算机的实验平台是：处理器Intel(R)Core(TM)Duo T57502.0GHz 2.0GHz，内存3.0GB，操作系统Windows 7，在Matlab R2009a对知识推理实现仿真：假设一个学习者在诊断性测验或形成性测验中不正确检测项目数为10，其错误项目相对应的课程之间的相似度及课程本身的自适应调整难度参数如表1所示：

Pc为0.90;Pm设定为0.01;初始种群为100;迭代次数为150。

实验发现：基于传统遗传算法的知识推理算法最快迭代48次就能收敛到全局最优解，最慢迭代96次才能收敛到全局最优解。

图2是适应度函数图，其中圆圈所在的曲线代表了适应度函数最高值随着遗传迭代次数变化的曲线，方块所在的曲线代表了适应度函数平均值随着遗传迭代次数变化的曲线。

接下来，我们用表2来展示采用基于传统遗传算法的知识推理算法所寻找的最优个性化学习路径，并对路径中前后连续课程之间的相似度和课程本身的难度系数进行说明。

5.3 基于改进的遗传算法的知识推理

该文所提出的改进遗传算法与传统遗传算法的区别之处在于选择算子、交叉算子、变异算子和各遗传参数的不同，初始化、编码和适应度函数两者是一致的。

1)选择算子

中国计量学院的学者提出了两次最优个体保存法[9]，实验证明该方法能加快坐标测量系统的标定过程且算法精确。该文对两次最优个体保存法进行改进，提出了三次最优个体保存法和排序选择相结合的选择算子，即：在初始化、交叉后和变异后三次使用最优个体保存法，最后使用排序选择算子将对种群实施优胜劣汰的操作。

实验发现：新选择算子的遗传算法最快迭代10次就能收敛到全局最优解，最慢迭代30次也能收敛到全局最优解，其适应度函数图如图3所示。

2)交叉算子

厦门大学的学者提出将贪心算法引入到遗传算法的交叉算子[10]中，有效解决了TSP问题中的群体多样性和收敛速度的矛盾。该文将区域交叉算子换成基于贪心算法思想的交叉算子，即：在父代课程染色体p1、p2中分别找到交叉点的右或左课程基因cr1、cl1和cr2、cl2，选择与交叉点相似度系数大的课程基因作为下一课程基因以及新的交叉点。

实验发现：新交叉算子的遗传算法最快迭代45次就能收敛到全局最优解，最慢迭代100次才能收敛到全局最优解，其适应度函数图如图4所示。

3)变异算子

该文试着采用贪心算法和Inver-Overt算子相结合的变异算子操作方法，即每次选择的两交叉点的相似度是最大的。

实验发现：改进了变异算子的遗传算法最快迭代25次就能收敛到全局最优解，最慢迭代100次才能收敛到全局最优解，解空间分散的比较均匀，其适应度函数图如图5所示。

4)仿真实验与分析

下面我们应用Matlab对整个改进遗传算法的知识推理进行仿真实验，换言之，在与传统遗传算法知识推理中设定的一致情境中为学习者找寻一条符合其知识能力背景和需求的个性化学习路径。

Pc为0.90;Pm设定为0.01;初始种群为100;迭代次数为100。

实验发现：使用基于改进遗传算法的知识推理算法可以5次得到全局最优解6.4070，其它的解均可看成是近似最优解，其适应度函数图如图6所示。

综上所述，结合文中两种知识推理算法所进行的仿真实验，我们可以得到如下结论：使用改进的遗传算法的知识推理算法所得到的结果要明显好于使用传统的遗传算法的知识推理算法所得到的结果。前者的收敛速度更快，且产生的解空间均可看成近似最优解，解空间的染色体适应度函数值远高于后者。

6 结束语

该文提出了基于遗传算法的知识推理模型，该模型能为学习者推荐符合其知识能力背景和需求的，以难度参数值最低的课程起始的、课程序列的相似度系数之和达到最大值的个性化学习路径，为构建个性化学习服务的智能教学系统提供了支持。

摘要：该文提出了一个基于遗传算法的知识推理方法,它将为学习者构建一条最优个性化学习路径。通过在matlab R2009a中进行仿真,发现采用了最优个体保存方法、排序选择算子和与贪心算法相结合的交叉算子、变异算子的遗传算法的收敛速度要远快于传统的遗传算法,其知识推理过程中综合考虑了课程的难度系数和相似度。

关键词：遗传算法,贪心算法,知识推理

参考文献

[1]赖丁R.认知风格与学习策略[M].庞维国,译.上海:华东师大出版社,2003:128.

[2]吴杰.外国现代主要教育流派[M].吉林:吉林教育出版社,1989:345-346.

[3]张春玲.对布卢姆掌握学习理论的再认识[J].洛阳师范学院学报,2001(1):80-82.

[4]Chen C M,Lee H M,Chen YH.Personalized e-learning system using Item Response Theory[J].Computers&Education,2005(44):237-255.

[5]陶跃华.基于向量的相似度计算方案[J].云南师范大学学报,2001(9):17-19.

[6]Huang M J,Huang H S,Chen M Y.Constructing a personalized e-learning system based on genetic algorithm and case-based reasoning ap proach[J].Expert Systems with Applications,2007(10):551-564.

[7]蒋望东,林士敏.基于选择性集成的整数编码遗传算法及TSP问题求解[J].计算机与现代化,2007(5):38-43.

[8]高经纬.求解TSP问题的遗传算法实现[J].计算机时代,2004(2):19-21.

[9]王学影.关节臂式坐标测量系统关键技术研究[J].中国计量学院学报,2010(3):12-15

推理算法 篇4

常用的聚焦曲线峰值搜索算法包括盲人爬山法[5]和基于二分正则化的峰值搜索算法[6 - 7]。在定焦成像系统中,这些算法都有较好的效果,不同算法的区别在于聚焦速度的不同。但在变焦成像系统如一体化摄像机机芯中,当镜头的变焦电机位于长焦端时,聚焦曲线变得平坦,峰值不明显,这些算法在这种情况下适应性不好,很难实现快速准确聚焦。

本文在盲人爬山法的基础上,在峰值搜索过程中引入模糊控制器和Zoom-Focus曲线,可以在系统中做到两点改善。一是结合镜头当前变焦电机位置和镜头Zoom-Focus曲线可以缩小聚焦电机搜索范围,就本文实验中采用的18 倍一体机镜头而言,广角端只需要搜索聚焦电机全程的5% ( 100 步) ,长焦端只需要搜索聚焦电机全程的50% ( 1 000 步) ,从而有效提高聚焦速度; 二是根据当前聚焦值和聚焦值变化率自适应调整搜索步长,可以将聚焦精度提升至最小搜索步长即1 步( 5 μm) ,同时解决了传统算法在镜头处于长焦端时无法有效聚焦的问题。

1 自动聚焦系统原理

在自动聚焦系统[8]中,当Zoom电机位置不变时,使Focus电机从最小位置运动到最大位置,通过图像清晰度评价函数对每一帧图像的清晰度进行计算,得到聚焦曲线形态( 见图1b) 。当Focus电机位于图的M点时( 见图1c) ,图像FV值最大,代表当前图像最清晰。假设当前Focus电机处于P0 点,传统的盲人爬山算法在搜索峰值时首先向任意方向移动一个步长,比如从P0 移动到P1,此时检测到清晰度上升,则认为上坡方向为初始方向,然后沿上坡方向一直运动,直到检测到下坡为止,最后再反向运动到最大值点。

从以上流程中可以看出,在峰值搜索过程中,可以控制的变量有3 个: 初始搜索方向Dir、搜索步长Step和搜索范围 ΔR。

镜头的Zoom-Focus曲线,是指当物距一定时,不同放大倍数下的Zoom电机位置与在该放大倍数下可得到清晰成像的Focus电机位置的关系曲线。典型的Zoom-Focus曲线簇如图2 所示。

从该曲线簇中可以看出,在不同放大倍数下搜索聚焦曲线峰值点时,并不需要Focus电机全程搜索,只需要搜索 ΔR = f1m( z) - f∞( z) 之间的范围即可,在Wide端即Z = 500 时,搜索范围只有全程的5% ; 在Tele端即Z = - 3 800 时,搜索范围为全程的50% 。图3 显示了搜索范围 ΔR与Zoom位置的关系。在实际应用中,无法获得Zoom-Focus曲线的解析形式,只有离散数据,因此在确定ΔR时需要采用线性插值进行计算,如式( 1) 所示

式中: ΔR( z) 表示搜索范围与Zoom电机位置z之间的函数关系; f1m( z) 表示物距为1 m时Focus电机位置与Zoom电机位置之间的函数关系; f∞( z) 表示物距为无穷远时Focus电机位置与Zoom电机位置之间的函数关系。

2 模糊控制器设计

图像的聚焦值受很多因素影响,这些因素包括当前光线亮度、场景复杂度、物体景深、变焦电机位置和聚焦电机位置等。对于这类难以建立数学模型的系统而言,应用模糊控制可以降低系统设计复杂度。模糊控制是一种基于规则的控制,它利用专家的经验和知识作为控制规则,不依赖于被控对象的精确数学模型[9]。将模糊控制应用于自动聚焦的峰值搜索过程中,可以在搜索过程中根据当前输入条件自适应调整步长大小,在远离焦点的地方采用大步长快速搜索,在接近焦点的时候采用小步长精确定位,从而提高搜索速度和精度。

本文选择当前图像的FV和FV的变化率d FV作为系统输入,选择Focus电机的步长Step作为系统输出,控制器结构采用二维模糊控制器,其结构图如图4 所示。

FV经过差分运算得到d FV后分别乘以增益系数Ge和Gd调整大小,之后通过隶属度函数将两个精确量转换为模糊量。为了保证在焦点附近有足够的定位精度,选择调整后的三角形隶属度函数,图5 分别表示FV 、d FV和Step的隶属度函数。经过模糊化后的变量按照模糊控制规则进行模糊推理,得到系统输出Step的模糊值,模糊控制规则根据先前经验得到。如表1 所示,其中NB表示负大,NS表示负小,PB表示正大,PS表示正小,O表示零,最终模糊推理的输出结果仍然是一个模糊量,按照重心法进行解模糊化,然后用一个增益参数Gu调整大小后作为控制量输出。

3 实验结果

本文在基于DM368 的一体机机芯平台上验证了上述峰值搜索算法。前端图像传感器采用Aptina公司推出的低照度CMOS图像传感器AR0130,其动态范围为83.5 d B,可以有效保证在夜晚低照度的条件下清晰成像。一体机镜头选用广州长步道公司针对高清监控市场推出的18 倍高清镜头CL0202D,其焦距范围为4. 7 × ( 1 ± 5% ) ~ 84. 6 ×( 1 ±5% ) mm,最大放大倍率18 倍,使用两个步进电机驱动变焦镜片群组和聚焦镜片群组。聚焦板上的步进电机驱动芯片为u PD16835A。

为了验证峰值搜索算法针对不同倍数下聚焦曲线的峰值搜索效果,选择两种典型情况做对比试验,第一组实验使镜头放大倍率固定为5x,因为从图3 可以看出,镜头在1x( Z =500) 到7x( Z = -2 600) 之间其搜索范围都很小,所以任意选取其中之一可以代表小倍率时的峰值搜索情况; 第二组实验使镜头倍率固定为18x,此时搜索范围最大,同时FV曲线变得平坦,可以代表大倍率时的峰值搜索情况。

图1 和图6 分别展示了两种情况的实验结果,其中MCS表示盲人爬山法,FCS表示采用模糊推理的峰值搜索算法,表2 和表3 代表两种实验情况的数据对比。从搜索过程可以看出,在小倍率情况下,由于可以根据Zoom-Focus曲线减小搜索范围,因此所需平均搜索次数和平均聚焦时间都比传统的爬山算法小很多,同时由于模糊控制器的引入,使得系统可以根据FV和d FV自适应调整步长,聚焦精度可以提升到5 μm。在大倍率情况下,由于FV曲线变得平坦且搜索范围加大,本文提出的方法在聚焦时间上没有明显提升,但可以把聚焦精度提升到5 μm,从而可以准确定位图像最清晰位置,这对于大倍率情况下的峰值搜索非常重要。

4 总结

推理算法 篇5

在石油测井解释、医疗诊断、柴油机车故障诊断等等一系列的等同机械故障诊断的问题中,尽管不同领域的判定故障的相关专家的知识是不同的,判断问题的范围、内容不同,但他们的知识结构都是因果型的,其推理结构都是从部分现象推出真正原因,即故障检测诊断型专家具有类似的知识结构类型,而且他们的诊断推理也极其相似[1,2]。

可以认为任一机械设备出现故障都是由一些和该设备相对应的相对固定的表象来反映。假如称某种机械设备所有可能故障集合为故障库,引起故障发生的原因所表现出来的表象集合称为表象库,故障库中的一种故障用图1上面的一排节点中的一个表示,库中的每个表象用图1中下面一排的一个节点表示,如果故障a i具有表象b j,那么在它们对应的节点之间连以线段,否则就不连线段,这样就得到了故障诊断专家的知识库结构——对集结构。

专家判定故障是依据机械设备的表象,确定设备的故障。换句话说,作为判定的依据,机械故障诊断专家如果认为机械设备有某故障,则该设备必然应该出现所具有的表象集,即一个有相应表象集合的机械设备必然产生了相对应的故障。假定某机械设备的某个故障对应的表象都展现出来,那么就判定该设备发生了对应的故障,如图1中,若机械设备出现了b1,b2,b3这三个表象就可判定具备了a1故障。这个思维方法即为判断机械故障专家的常见推理结构。

1 推理理论

在二值逻辑中,蕴含A→B的真值T(A→B)是由表1定义的:

可以在集合{0,1}上定义二元算子﹡r,令其运算等价蕴含算子,即:

当T(A)=1,且T(B)=1则r=1(1)

当T(A)=0,且T(B)=1则r=1(2)

当T(A)=1,且T(B)=0则r=0(3)

当T(A)=0,且T(B)=0则r=1(4)

已知蕴含A﹡rB的真值T(A﹡rB)=r与前提的真值T(A)=a,那么推理就是求下面方程的解:

其中,a,r∈{0,1}是已知的,x未知,算子﹡r由表1所定义,那么方程式(5)的解是:

x=1当a=1且r=1(6)

x∈{0,1}当a=0,且r=1(7)

x=0当a=1,且r=0(8)

x无解当a=0且r=0(9)

将二值逻辑的真值域{0,1}扩展到区间[0,1]上,就进入了无限值逻辑的领域,希望在值域[0,1]上找到一个蕴含算子﹡r(﹡r是[0,1]上的二元运算)使得(1)~(4)式作为边界条件而成立,并且条件(6)~(9)式是方程式(5)式的解。

如果T(A)和T(B)表示A,B在无限值逻辑中的真值,则定义A∪B,A∩B,蕴含A→B的真值如下:

其中(12)称为卢卡契夫斯基蕴含公式。令a=T(A),b=T(B),记r=T(A→B),从(12)中可以看到r是由a、b决定的,用运算符号*r表示r与a,b之间的关系,即

根据算子理论,*r的右逆算子为[3]:

由前所述,近似推理是指已知r=T(A→B)及T(A′)=a′,求T(B′)=b′=?,根据(14)式定义近似推理为:

利用(13)式,消去r,得到近似推理公式:b'=a'*(ar*b)=max(min(a'-a+b,a'),0)(16)称上式为卢氏近似推理公式,称a'为前提b'为结论。

2 系统实现

把上述推理诊断过程用在故障判断系统的工作过程如下。

首先进行专家知识获取,也就是要同某故障系统的专家共同研讨,确定该系统的故障表象点。这些反映故障的表象点及其反映故障点损坏程度的表象数值都是系统故障诊断维修的专家多年实际工作经验所得出的。

因此第一步要确定故障点个数和相关的表象点的个数及其对应的故障点损坏程度值和现象点相应的程度值。即要构造出表2。

表2即可称为应用的机械故障专家知识。上述的n和m为该系统的极限值。也即这n个故障点相关的现象点具有一致性。如果,其他的故障点所对应的现象点与上述m个不同,可构造另一个相应的判断表。

由于专家知识所描述的故障值及表象值是多种多样的,甚至是自然语言描述,而判定故障是基于模糊集的。所以这里要经过一次知识转换。即把程度词的自然语言描述转换为推理所需要的数值。即把程度值转为在[0,1]区间上的表示值。

因此,需要建立表3和表4两个转换表。

这里的程度词划分的个数及相应值是根据诊断专家的知识得到的。由此把推理判断表2转化为表5。

下面以内燃机车柴油机故障诊断实例来描述系统实现。在铁路运输业中,存在着许多设备故障诊断问题,其中机车的故障诊断、定期维修就是一个非常复杂的问题,对这些问题的解决,已是作为延长机车运行里程及使用寿命的主要保证手段之一。

多年来,相关部门利用发射光谱,机油分析,铁谱分析等多种手段,对内燃机车柴油机润滑系统摩擦磨损过程进行状态监测和故障诊断等方面的研究,但是如何对监测所得到的定量和定性的信息进行分析,作出对设备状态的正确判断是很困难的。

在对相关部门作了大量细致的调研后,根据该摩擦系统的特性及现场诊断专家的思路特点并考虑到下面两方面的因素,把上述的推理方法和计算机系统技术结合起来,引入该系统的诊断技术之中。

(1)机械设备的摩擦磨损通常很复杂,它与各种应力干扰、系统参数、环境等有密切关联,而且这些影响又都是综合性的,即没有明确的规律可循,也没有十分明确的因果关系,对它们的故障诊断往往凭靠现场专家多年的工作经验,所以建立常规的具有一定计算公式的程序系统很困难。

(2)对故障的诊断与判别问题往往带有模糊性和经验性,采用模糊数学方法就比较贴切、自然。

根据现场专家的工作经验和诊断思路,这里以东风四型机车柴油机构造一个简单诊断模型,如图2所示。

主要考虑的表象因素集合为U={U1,U2,U3},其中:U1为润滑油劣化性程度(油的理化性分析);U2为磨损程度(直读铁谱分析);U3为磨损趋势(发射光谱分析)。而表象集合又由若干基本因素确定,即:

其中:

u11为润滑油粘度变化率;

u12为润滑油总碱值下降率;

u13为润滑油水污染程度;

u14为重油及燃烧产物的污染程度(钒含量PPM);

u15为尘埃污染程度(硅含量);

u21为磨损大颗粒读数;

u22为磨损小颗粒读数;

u23为磨损烈度;

u24为磨损颗粒浓度;

u31为润滑油铁元素浓度;

u32为润滑油铜元素浓度;

u33为润滑油铬元素浓度;

u34为润滑油铝元素浓度;

u35为润滑油铅元素浓度。

由图2可见整个诊断分为两级,首先由检测出的基本表象值u11,u12,u13,u14,u15推出U1;由u21,u22,u23,u24推出U2;u31,u32,u33,u34,u35推出U3;然后把推出的结论{U1,U2,U3}再作为参数并赋予一定的权值推出最终结果。

在对大量检测值分析的基础上,又参照专家的诊断经验值,对各基本表象值做了等级划分并导出推理矩阵如下:

在此诊断流程上,可以看到推理过程与专家判定故障的一般工作过程非常吻合;数据与知识匹配,产生中间结果,然后再匹配,直至输出最终结果。

用户在调用建造模块形成推理链表后,即可输入检测到的现象值来进行诊断,系统此时会给出一些中间结果并告知缺少的尚需检测的现象号,通过用户与系统的多次交互,最后给出确切的诊断结果。

3 结语

在已有的机械故障诊断系统中,多为依据规则“IF-THEN”结构,加上确定性理论和主观Bayes方法来实现系统工作的产生式系统[4,5],本文在集合理论及专家诊断知识结构为对集的前提下,给出了一种适用于故障诊断类型的基于逻辑算子进行推理运算的推理模型及算法实现。本诊断实例试运行后,与实际情况基本相符。由于本实例仅为一很小的子系统的诊断模块,由于时间关系,知识获取面窄,所以本系统的诊断结果仅限于“正常”与“异常”的判别和估计出摩擦故障的可能性,至于故障原因和故障部位的诊断还未涉及到,所以系统功能的增强还需要做相应的知识获取工作。

(编辑:向飞)

摘要：在机械故障分析诊断型专家知识结构及推理过程的基础上,利用离散数学集合理论,导出诊断思维的数学模型,最后给出了相应模型的机械故障诊断实例。

关键词：诊断模型,故障,推理

参考文献

[1]邵虹,崔文成,张继武,等.医疗诊断专家系统研究进展[J].小型微型计算机系统,2003,24(3):499-512.

[2]张晓丹,赵海.模糊专家系统在故障诊断中的应用研究[J].计算机工程与应用,2004,40(3):21-22.

[3]程里春.保并交映射与Fuzzy关系方程[J].模糊系统与数学,1987(1):71-79.

[4]牛福春,顾海明.基于模糊规则的故障诊断专家系统[J].微计算机信息,2008(19):207-208,119.

推理算法 篇6

目前,随着暂态量保护研究的显著进展[1],研究新型的快速故障选相元件已势在必行,这对有选择性地跳开故障相和实现超高压输电线路单相或三相自动重合闸是至关重要的。

基于行波的故障选相易受故障电弧、初始角、过渡电阻等不确定因素的影响[2,3];而基于暂态量的故障选相能够克服以上缺陷[4,5]。但是仅依靠故障暂态量进行选相需要对每一个特征参数的门槛进行整定,而门槛的整定很难给出一套完善的整定原则。为此,将模糊理论引入到基于暂态故障选相中不失为一种好的方法[6]。本文从模式识别的角度,提取了识别故障类型和判断故障相别的特征参数,并结合模糊理论,提出了基于分层模糊推理的快速综合故障选相新算法。ATP仿真表明该故障选相算法具有很好的选相性能。

1 故障特征分析

利用Clark相模变换技术[7]求解故障附加网络中的故障分量,如表1所示。

1.1 故障类型特征

a)零模量:单相或两相接地短路i0f≠0,实际上为接地电流,数值相对较大;而两相或三相短路时零模量i0f=0。

b)线模量:单相接地短路时,i1f≠0,i2f=0;两相短路时i1f=0,i2f≠0;而两相接地短路和三相短路时,两个线模量都不为零。

1.2 故障相别特征

a)单相接地短路:三个故障分量中最大者对应故障相,与故障相无关的两个故障分量为零。

b)两相接地短路:非故障相的故障分量为零,与故障相相关的两故障分量无明显特征。

c)两相短路:非故障相的故障分量为零,两故障相的故障分量幅值相等,但极性相反。

d)三相短路:三个故障分量之间无明显特征。

2 故障选相算法中的特征提取

2.1 区分故障类型的特征参数

设三个电流模量(i0f、i1f、i2f)和三相电流量(iA、iB、iC)正交小波变换的某尺度归一化能量分别为(e0、e1、e2)和(eA、eB、eC);将(eA、eB、eC)进行大小排序,记为(emin、emid、emax)。由上述故障特征分析,可以总结出:

a)零模量e0

当发生接地短路故障时,e0≠0,且数值较大;当发生相间短路故障时,理想情况下e0=0,即便是在不换位线路中零模分量也很小,近似为零。

b)模域中rm=e2/e1

单相接地短路时,rm=e2/e1很小,基本为零;两相接地短路和三相短路时,mr≠0;两相短路时,rm=e2/e1很大,理论值趋于∞。

c)相域中rp1=emin/emid

单相接地短路时rp1=emin/emid的值基本上为1;两相短路和两相接地短路时rp1≈0;而三相短路时rp1无明显特征。

d)相域中rp 2=emid/emax

单相接地短路时,rp1=emid/emax基本为零;两相接地短路和相间短路时,无明显特征,但数值一般比较大,不会为零。

e)i0 f与i1f之间的曼哈坦距离(Manhattan)dM10

定义序列x(n)、y(n)的Manhattan距离为:

Manhattan距离反映两序列的接近程度。两相短路中i0f=i1f=0,故二者之间的Manhattan距离dM10=0,而其他类型的故障无此特征。

2.2 区分故障相别的特征参数

定义如下三个相关系数:

由故障相别特征可知,单相接地短路时,非故障相的故障电流相等且基本为零,为正相关,即ρ=1;两相短路时,故障相的两故障电流具有负相等的关系,即ρ=-1;两相接地短路时,三故障相之间无明显的相关性关系,故-1<ρAB、ρBC、ρAC<1。但可以通过非故障相的故障电流为最小来选出故障相别。

3 基于分层模糊推理的快速综合故障选相

利用模糊逻辑理论,将多个特征进行模糊综合,制定反映故障类型和相别的隶属函数及模糊规则,进而建立两层模糊推理结构:模糊判别故障类型和模糊识别故障相别,如图1所示。

3.1 基于模糊推理的故障类型识别

3.1.1 特征参数的模糊化及其隶属函数的确定

考虑本线路末端故障时零模量在传输中的衰减,将e0>0.001视为接地性故障,0.0005~0.001置为模糊区。e0的隶属函数如图2所示,输出为λ1。

单相接地短路时,mr≈0,其他故障类型时rm≠0,考虑到故障暂态的不确定性,将0.02~0.1置为模糊区,输出为λ2;rp1在单相接地短路时基本为1,两相短路和两相接地短路时rp1≈0,三相短路时,rp1无明显特征,为此,将rp1的模糊区置为0.2~0.8,输出为λ3;rp2在单相接地短路时为0,两相接地短路和相间短路时,无明显特征,但数值比较大,不会为0,可置0.1~0.9为rp2的模糊区,输出为λ4。三个特征参数的隶属函数如图3所示。

3.1.2 模糊判别故障类型的规则

根据故障特征量e0、rm、rp1、rp2的隶属函数,制定出故障类型模糊判据的规则如表2所示。

对以上四个模糊输出设定权值时,考虑到故障发生的随机性,可将模糊判别设置相等的权值系数。式(2)是第一层判别故障类型的模糊输出:

其中:i代表每种故障类型。

根据最大化隶属原则,得到:

综合评判的最大输出所对应的故障类型即为模糊判别结果。

需要说明的是:在两相接地短路时0模量较之于其的最大模量较小,尤其是在当0模量在0o初始角时,e0的值将很小,可能会落入其模糊区,甚至会进入到S区,从而将两相接地短路误判为相间短路类型。加以解决的方法是在第二层模糊选相根据选相矛盾进行上述误判的自动校正。

3.2 基于常规判别和模糊推理的故障相识别

3.2.1 单相接地短路的模糊选相

根据相关系数的隶属函数(如图4)和模糊选相的规则(如表3)进行单相接地短路下的模糊选相。

设ρAB、ρBC、ρAC的输出分别为λ5λ6λ7,综合输出为:

其中:i分别表示三种故障相别。

综合评判的最大输出所对应的故障相即为单相接地短路的模糊选相结果。

3.2.2 两相接地短路的常规选相

利用如下方法完成两相接地短路时的故障相识别,即:

3.2.3 相间短路的模糊选相

相间短路的故障选相不仅要在区分三相及两相短路的基础上选出故障相,同时还要对可能误判到此故障类型下的两相接地短路进行校正。

选择相关系数和Manhattan距离dM10作为两相短路模糊选相的特征参数。相关系数的隶属函数仍为图4。dM10的隶属函数如图5,系数a和b可以通过仿真确定,本文通过大量仿真确定a=50,b=90。两相短路故障时的模糊选相规则如表4。

综合输出仍为:

对Rout3设置一门槛值Rset=0.8。如果Rout3≥Rset,表明该故障是两相短路,进而选出故障相别;如果Rout3

两相接地短路时i1f=-i0f,有E1f≈E0f即re01=E0fE1f≈1;三相短路时,i0f=0,i1f≠0,有re01=E0fE1f≈0。因此可利用此特征差异来识别和区分三相短路和两相接地短路。re01的隶属函数如图6所示;模糊规则如表5所示。

re01的输出为λ9,根据最大隶属度原则,有:

通过以上方法就可以完成相间短路故障类型下,两相短路的模糊选相和三相短路的识别以及两相接地短路误判到此类型下的二次校正。

4 故障选相算法的ATP仿真

图7为500 k V超高压输电系统,线路采用J.Marti频率相关模型,结构参数取自平武线。考察基于分层模糊推理的故障选相元件算法随故障位置、初始角、过渡电阻变化时的选相性能。仿真中采样频率为400 k Hz,采用DB4小波对各特征量进行三尺度分解,得到第三尺度空间的小波变换系数。取故障后第三尺度1 ms内的数据进行分析。

4.1 不同位置故障时选相元件的仿真测试

故障初始角为30°,过渡电阻为100Ω,考察在被保护线路内部距保护1 km、50 km、100 km、174 km处故障时的选相结果。

4.1.1 故障类型的模糊识别

图8给出了每种类型的故障下判为四种不同类型故障时的隶属度,其中最大隶属度所对应的故障类型即为模糊判别结果,用“○”表示。由图8可以看出:不同位置故障时,四种不同类型的故障均能够被正确地分类到相应的模式空间中,判别非常明确,且不受故障位置的影响。

4.1.2 故障相别的综合评判

综合评判故障相别的部分仿真结果如表6~9所示。由表可以看出:故障选相元件的第二层均能够在识别故障类型的基础上通过综合评判,正确选出故障相别,且选相性能不受故障位置的影响。

4.2 不同初始角故障时选相元件的仿真测试

在距保护安装100 km处,过渡电阻100Ω,考察在0.024~0.034 s(初始角为-24°~157°)内故障时的选相性能。仿真中每隔0.000 2 s设置一次故障。

4.2.1 故障类型的模糊识别

由图9可以看出:两相接地短路和三相短路受初始角的影响较大,但三相短路仍能够可靠正确地判别为相间短路(即P类型)故障;两相接地短路在少数情况下会被误判为相间短路故障。

之所以会出现上述的误判,其原因是此类故障发生在0模电流过零点附近,图10给出了0.025 4 s发生两相接地短路时的各模量波形,由图10可知,该时刻故障时0模量相对于其他两个模量基本为零,不具有接地性短路的基本特征,经第一层模糊识别将其误判为相间短路。如图9右上子图中所标出的三个误判情况,针对此问题,将用本文前面提出的二次校正解决之。

4.2.2 故障相别的综合评判

在识别故障类型的基础上,进行第二层故障相别的综合评判,评判结果如表10和表11所示。

由表11可以看出:当两相接地短路误判到相间短路类型中时,通过第二层的再次模糊判别,能够正确识别为两相接地短路,从而完成了两相接地短路误判为相间短路时的自动校正,通过校正,均能够正确识别出该故障类型和故障相别。

文中还对不同过渡电阻故障时对该故障选相元件进行了仿真(限于篇幅这里就不再列出)。仿真结果也表明,该故障选相元件同样不受过渡电阻的影响,具有很好的选相性能。

5 结论

本文提出的基于分层模糊推理的快速综合故障选相元件具有以下特点:

1)能够准确识别出故障的类型和综合评判出故障的相别。由于各特征参数均采用了归一化能量,因此选相性能不受故障位置和过渡电阻的影响,受故障初始角的影响较小。

2)在少数情况下,两相接地短路会误判为相间短路,但经过校正,仍能可靠识别且选出故障相别。

3)在计算各特征参数时,选取故障分量在1 ms内的小波变换低频尺度能量,计算量小,满足快速故障选相的要求,具有实用性。

参考文献

[1]Jiang Joe-Air,Chen ching-shan,Liu Chi-wen.A New Protection Scheme for Fault Detection,Direction Discrimination,Classification and Location in Transmission Lines[J].IEEE Trans on Power Delivery,2003,18(1):34-42.

[2]DUAN Jian-dong,ZHANG Bao-hui,HA Heng-xu.A Novel Approach to Faulted-phase Selection Using Current Traveling Waves and Wavelet Analysis[A].in:IEEE Power Con[C].Kunming(China):2002.1146-1150.

[3]段建东,张保会,周艺.利用电流行波进行超高压输电线路故障类型识别的研究[J].中国电机工程学报,2005,25(7):58-62.DUAN Jian-dong,ZHANG Bao-hui,ZHOU Yi.Study of Fault-type Identification Using Current Traveling-waves in Exrea-high-voltage Transmission Lines[J].Proceedings of the CSEE,2005,25(7):58-62.

[4]Omar A S.New Algorithm to Phase Selection Based on Wavelet Transform[J].IEEE Trans on Power Delivery,2002,17(4):908-914.

[5]段建东,张保会,周艺,等.基于暂态量的超高压输电线路故障选相[J].中国电机工程学报,2006,26(3):1-6.DUAN Jian-dong,ZHANG Bao-hui,ZHOU Yi,et al.Transient-based Faulty Phase Selection in EHV Transmission lines[J].Proceedings of the CSEE,2006,26(3):1-6.

[6]姜惠兰,梁昭君,杨维,等.基于模糊逻辑的高压输电线路故障类型识别新方法[J].电工电能新技术,2004,23(1):60-63.JIANG Hui-lan,LIANG Zhao-jun,YANG Wei,et al.Fuzzy Logic Based High Voltage Transmission Line Fault Type Recognition[J].Advanced Technology of Electrical Engineering and Energy,2004,23(1):60-63.

推理算法 篇7

关键词：协方差矩阵自适应进化策略,云推理,步长控制,全局优化

0 引言

协方差矩阵自适应进化策略(CMA-ES)是一种高效的群体随机搜索进化策略算法,具有不依赖种群大小、收敛速度快、全局性能好等优点,以其优良的寻优性能在实值优化领域备受关注[1]。同其他进化类算法一样,其在求解某些复杂的多峰函数问题时仍存在易早熟收敛、求解精度不高等缺点。

目前,许多学者从不同的角度对算法进行了改进。文献[2]为算法设置重启,通过动态地增大种群规模来获得较强的全局搜索性能;文献[3]通过正交设计构造正交试验向量来引导算法跳出局部最优;文献[4]通过限制协方差矩阵为对角阵来降低算法的时空复杂度。

云模型具有良好的不确定性建模与处理能力[5]。近年来,众多学者将云模型应用于进化算法领域,取得了一定的成果。其中,文献[6]提出云遗传算法(CGA),利用Y条件云实现交叉操作,基本云实现变异操作,最后证明了算法的有效性,具有一定的参考价值。文献[7]提出了基于云模型的进化算法,在定性知识的控制下自适应地控制遗传和变异的程度,较好地避免了传统GA易陷入局部和早熟收敛等问题。文献[8]将云模型与粒子群算法(PSO)结合,通过将粒子分群,利用X条件云自适应地控制普通粒子的惯性权重,具有较高的计算精度和较快的收敛速度。

进化过程充满了不确定性,CMA-ES中种群进化的步长采用确定函数映射进行伸缩变化,其不能很好地反映进化过程的不确定性。本文基于云模型对不确定性问题良好的处理能力,通过利用云模型的不确定推理对CMA-ES步长控制进行改进,得到了一种基于云推理的CMA-ES改进算法。该算法利用云模型对不确定性问题良好的建模和推理能力来克服CMA-ES中步长确定性控制过程的不足,通过建立求解问题的步长控制云推理模型,来更好地处理和利用进化过程中的不确定性。最后通过测试函数的数值优化实验,验证了算法在求解成功率、求解精度、稳定性和收敛速度等方面的良好性能。

1 CMA-ES算法

CMA-ES算法是在进化策略(ES)算法的基础上发展起来的一种算法,其继承了基本ES的优点,并与高引导性的协方差矩阵结合起来。CMA-ES的主要操作是变异,变异操作通过采样多维正态分布来实现,算法的实现过程为:

算法1 CMA-ES算法

步骤1参数设置及初始化。设置求解问题的静态参数λ、μ、wi=1,…,μ、cσ、dσ、c1、cc、cμ等;动态参数m∈RN,C=I∈RN×N,σ∈R+,进化路径pσ=0,pc=0,代数g=0。

步骤2正态采样。采样多维正态分布生成由λ个个体组成的种群,采样过程为:

步骤3评价与选择。根据适应度函数逐个评价种群中的个体,并根据评价的结果进行排序,选出排名靠前的μ个个体组成当前最优子群。

步骤4根据步骤3的最优子群信息更新种群分布参数如下:

步骤4.1移动均值。均值m的更新计算如下:

其中,x(g+1)i:λ表示第g+1代种群中排名第i的个体。

步骤4.2协方差矩阵调整。

其中y(g+1)i:λ=(x(g+1)i:λ-m(g))/σ(g)。

步骤4.3全局步长控制。

步骤5判断是否达到停止条件,若是,则停止,否则返回步骤2。

可见,协方差矩阵的更新结合“秩1”和“秩μ”两种机制,可以很好地适应大小种群的变化,通过高引导性的协方差矩阵和有效的全局步长,使得进化过程具有很高的效率。图1描述了CMA-ES算法的迭代寻优过程,其中“★”代表了搜索空间的全局最优解,表示求解问题的等高线,“●”代表了种群中的个体,“—●—”代表了种群的分布形状。更详细的CMA-ES算法描述见文献[1]。

2 云模型

云模型作为一种定性概念和定量数值之间的不确定性转换模型,在知识表达时具有不确定中带有确定性、稳定之中又有变化的特点,可以很好地表达进化知识。

2.1 云模型的基本概念

定义1设U是一个用精确数值表示的定量论域,C是U上的一个定性概念,若定量值x∈U且x是定性概念C的一次随机实现,x对C的确定度μ(x)∈[0,1]是有稳定倾向的随机数,则x在论域U上的分布称为云,每一个x称为一个云滴。

云模型结合随机性和模糊性,仅仅使用期望Ex、熵En和超熵He三个数字特征就勾画出由大量云滴组成的云图来表示一个定性概念,如图2所示,表示为C(Ex,En,He)。在多种云模型形态中,正态云模型具有普遍适应性[9]。

2.2 云发生器

(1)正向云发生器

正向云发生器实现从定性到定量的映射,它根据云模型的3个数字特征(Ex,En,He)产生满足条件的一定数量的云滴[5]。

(2)逆向云发生器

逆向云发生器是实现从定量到定性的映射,它可以将一定数量的精确数据转换为用3个数字特征(Ex,En,He)表示的定性概念。在多种逆向云算法中,刘常昱等人[10]提出的无确定度逆向云算法在准确性和稳定性方面都优于现有的其他算法,应用最为广泛。

(3)X条件云与Y条件云发生器

X条件云与Y条件云发生器构成了云推理规则的前件云和后件云。云规则发生器根据前件云CxA(ExA,EnA,HeA),后件云CxB(ExB,EnB,HeB)及前件云定量值xA产生满足确定度μ的后件云滴drop(xB,μ)。“If A Then B”的规则形式可以构成单条件单规则发生器,具体算法如下:

(1)生成以EnA为期望,HeA为标准差的正态随机数En'A;

(2)计算确定度

(3)生成以EnB为期望,HeB为标准差的正态随机数En'B;

(4)若xA≤ExA,则

(5)若xA>ExA,则

如果有多条“If A Then B”的规则,则可以构成单条件多规则云发生器。对于某一个前件输入定量值,如果激活多条云规则,则相应的后件有多个输出定量值,可采取加权平均的方法得到一个最终的后件输出定量值[11]。

3 基于云推理的变步长CMA-ES算法

在CMA-ES算法中,步长的控制过程采用了累积步长自适应控制方法,其充分利用了“进化路径”的历史反馈信息,使得进化过程具有很高的效率。CMA-ES中步长变化的基本规则是:当累积进化路径较长时,算法正全力大范围搜索,步长应增大;当累积进化路径较短时,算法正全力小范围搜索,步长应减小。具体地,由式(6)可知,步长变化通过伸缩因子ρ=exp(cσ(‖p(g+1)σ‖/E(‖N(0,I)‖)-1)/dσ)来实现,ρ是归一化进化路径长度‖pσ‖的单调递增指数函数,如图3所示。然而,进化过程是一个充满诸多不确定性的过程,用自然语言描述的CMA-ES步长控制规则也充分体现了这一点,CMA-ES使用这种确定函数映射的控制方式会在一定程度上忽略进化过程的不确定性,显然不能很好地表达进化知识。基于云模型在不确定性方面的优势,可以用云的不确定性推理来实现CMA-ES步长控制规则所描述的关系,从而可以很好地继承和传播进化过程中的不确定性,进而更好地表达进化过程。

3.1 基于云推理的步长控制模型

基于云推理的步长控制过程主要是将算法1的步长控制过程替换为云推理步长控制过程,具体建模过程如下:

1)确定输入输出概念:将‖pσ‖作为前件云概念,ρ作为后件云概念;

2)概念程度划分:将前件云概念划分为“较小”、“适中”和“较大”3个等级;将后件云概念划分为“减小”、“不变”和“增大”3个等级,从而得到3组控制规则:

规则1:如果‖pσ‖较小,则ρ减小;

规则2:如果‖pσ‖适中,则ρ不变;

规则3:如果‖pσ‖较大,则ρ增大。

3)确定云参数:以CMA-ES运行过程中前件云概念和后件云概念的历史数据作为输入,通过逆向云算法确定前件云和后件云各等级概念的云参数。

通过上述步骤挖掘出的云规则可反映CMA-ES基本的步长控制规律,对规则云参数作进一步调整,从而得到最终的云推理规则库。

3.2 算法描述

根据3.1节的建模过程,本文的基于云推理的CMA-ES改进算法,命名为CR-CMA-ES算法,具体实现步骤如下:

算法2 CR-CMA-ES算法

步骤1参数设置及初始化。执行算法1的步骤1。

步骤2 CMA-ES寻优。执行算法1的步骤2、步骤3、步骤4.1和步骤4.2。

步骤3基于云推理的步长控制。确定求解问题的云推理步长控制规则,将根据式(5)计算得到的‖pσ‖的大小作为云推理模型的输入,推理的具体步骤为:

步骤3.1将输入大小是否属于概念的“3En”区间作为激活规则的依据,如果某条规则被激活,则计算该规则下的X条件云滴的确定度μi;

步骤3.2计算该规则下的满足确定度为μi的Y条件云滴drop(yi,μi);

步骤3.3采用加权平均的方法计算所有Y条件云滴的精确化输出作为最终的输出结果ρ;

步骤3.4全局步长更新,σ=σρ。

步骤4判断是否达到停止条件,若是,则停止;否则返回步骤2。

总之,CR-CMA-ES算法的步长控制通过图4所示的推理过程来实现。对于给定的前件定量值‖pσ‖,得到带有不确定性的μ,后件云在该μ值的控制下,最终得到一个同样不确定的后件定量值作为当前的ρ,从而实现了步长的不确定性更新与传递。

4 仿真实验与分析

4.1 测试函数

为了检验本文CR-CMA-ES算法的性能,选取了10个测试函数[12]进行数值优化实验。表1给出了各测试函数的函数名、维数、搜索空间、理论最优值等内容。其中,F1-F9为多峰函数,在搜索空间中有多个局部或全局极值,F1有760个局部极小值和18个全局最小值,F2有1个全局最小值和两个局部极小值,F3的全局最小值非常靠近局部极小值,F4有6个局部极小值,F5-F9随着维数的增加,具有大量的局部极值,这些函数常用来测试算法的全局探索与开采能力;F10为单峰函数,在搜索空间中只有一个全局最小值,是优化算法的经典测试函数。

4.2 参数设置

CMA-ES算法的初始均值m设为求解问题搜索空间内满足均匀分布的一个随机向量,初始全局步长σ设为搜索空间范围的0.618倍,其他参数的设置见文献[1]。CR-CMA-ES算法中云推理步长控制规则库采用表2所示的一组云模型控制参数,其中Ep为归一化进化路径在随机选择下的期望长度E(‖N(0,I)‖),其他参数设置同CMA-ES。

两种算法的停止条件均设置为求解误差达到10-10或最大迭代次数达到1000。

4.3 仿真结果与分析

将两种算法分别独立运行30次,得到表3的测试结果。其中:Best表示30次独立实验中的最好值,Mean表示平均值,STD表示标准偏差,SR表示成功率。Mean可以反映算法在给定最大迭代次数下的求解精度,STD可以反映算法的求解稳定性。

从表3中可以看出:对于F1、F2,CR-CMA-ES在求解精度和求解成功率上均优于CMA-ES,特别地,CR-CMA-ES的求解成功率可以达到100%;对于F3,在给定最大迭代次数下,两种算法均未收敛到全局最优,但CR-CMA-ES可以很好地逼近全局最优解的邻域;对于F4,CR-CMA-ES在求解成功率上得到进一步提高;对于F5和F6,CR-CMA-ES表现出100%的求解成功率,并获得较高的求解精度;对于F7、F8和F9,两种算法表现出相同的求解成功率和求解精度;对于F10,CR-CMA-ES的表现明显优于CMA-ES,不仅在求解精度上得到大幅度提高,而且可以保持100%的求解成功率。通过STD的结果对比可以看出,CR-CMA-ES较CMA-ES表现出较高的求解稳定性。可见,CR-CMA-ES利用云模型良好的不确定性处理能力可以更好地控制步长,表现出较高的求解效率。

为了能更直观地分析算法的性能,可分析算法的归一化成功执行经验分布图[12],如图5所示。其中,SP(Success Performance)代表成功执行,为算法对某一测试函数求解成功时所需要的函数评价次数,具体的计算如下:

其中,#fevals for successful runs代表所有成功运行的函数评价次数,#of successful runs代表成功运行的次数,#of all runs代表运行的总次数(如本文为30次)。SPbest为所有算法对该测试函数的SP的最小值,SP/SPbest为所有算法对该测试函数的归一化成功执行。纵轴数据为横轴数据SP/SPbest的经验分布值,可反映求解的成功率。从图5中可以看出:

1)CR-CMA-ES的分布曲线总是位于CMA-ES之上,表明CR-CMA-ES较CMA-ES可以更好地解决这些优化问题;

2)在SP/SPbest数值较小时,CR-CMA-ES较CMA-ES可以更快地收敛,说明CR-CMA-ES能够以较少的评价次数来更好地解决这些优化问题。

总之,本文的CR-CMA-ES算法不仅在求解精度、稳定性上有明显的提高,而且通过归一化成功执行经验分布图可以看出,CR-CMA-ES在求解成功率和评价次数上也优于CMA-ES。

5 结语

1)基本的CMA-ES算法中步长采用确定性函数映射进行伸缩变化,其在一定程度上忽略了进化过程的不确定性;

2)云模型具有良好的不确定性问题处理能力,能够很好地对CMA-ES步长控制过程进行数据建模和规则提取;

3)采用基于云推理的步长控制方法可以更好地处理和利用进化过程的不确定性,从而更好地表达进化过程。测试验证结果表明:CR-CMA-ES能够提高求解成功率,并在求解精度、稳定性和收敛速度等方面得到进一步提高。

推理算法 篇8

在大多数无线传感器网络（Wireless Sensor Network,WSN）应用中，都利用聚类技术来减少能量消耗[1]。在分簇网络中，成员节点负责发送遥感数据到根节点，根节点负责收集、处理和发送数据到基站，所以根节点会比成员节点产生更多的能量消耗。当簇中的根节点能量消耗完，则无法处理数据使网络失效[2]。所以需要一种能够平衡能源消耗、提高簇和网络生命周期的算法。

本文提出一种基于模糊逻辑的WSN分布式分簇（Distributed Fuzzy-logic Clustering,DFLC）算法。采用分布式模糊逻辑推理系统，以能量大小、中心性、到基站的距离、跳数和节点密度等参数作为输入，来动态选择根节点。每个节点都分配分布式模糊逻辑引擎，防止消息在传输过程中产生高能耗。通过在中间节点上运行模糊逻辑推理，降低成员节点到根节点的消息传输量。仿真实验表明，DFLC算法的性能优于其他分簇算法。

1相关研究

文献[3]提出的低能耗自适应聚类层次算法（LEACH）是一种分布式自组织分簇算法，其过程分为簇建立和簇稳定2个阶段，通过随机选择机制选举簇头来平衡节点负载。然而，该算法没有考虑节点位置，不适合应用于较大的WSN环境。文献[4]对LEACH进行改进，通过构建双层簇来减小簇头与Sink节点的传输距离。然而其最多能够实现两跳传输，也不适合大型网络。文献[5]提出一种基于模糊逻辑簇头选举算法（CHEF），以节点能量、密度和中心性为输入，利用Mam dani模糊逻辑推理进行簇头的选举。然而其使用基站收集所有节点的信息，需要大量的节点间通信，消耗较多的能量。文献[6]提出一种集中化使用模糊逻辑引擎来选择生成簇头的算法，然而该方法没有考虑到需求情况，而是周期性运行。

不同于上述提到的算法，DFLC没有使用基站从所有传感器节点收集数据或集中化执行模糊逻辑，而是使用了一个完全分布式结构。避免了节点到基站、基站到节点的大量计算开销和消息传输开销，从而降低整个网络的能量消耗，提高网络寿命。模糊逻辑引擎只由根节点或者有较高概率被选择作为新根节点的父节点执行，进一步节约能耗。此外，DFLC还考虑了容错性、负载均衡、时效性和可扩展性等因素。

2提出的分簇算法

2.1网络模型

系统节点分为Sink节点、根节点、成员节点、父节点和子节点。Sink节点为基站，从根节点中收集数据。根节点为每个簇的领导者，从簇中成员节点收集数据，然后发送数据到Sink节点。父节点是具有叶节点的成员节点，转发或处理其子节点发送的数据。子节点是成员节点，通过父节点把数据发送给根节点。

2.2能量模型

传感器主要在分组传输、数据包接收、数据感知和处理过程中消耗能量。本文使用的能量模型[6]中，发送k字节数据包消耗的能量为：

式中：Eelec（单位：nJ/b）和εelec（单位：pJ/b/mα）是无线电路的能量系数；放大器α是路径损耗指数，数值在2～4之间；d是传输距离。接收器的能量消耗模型为：

传感能耗模型为：

式中：s为传感半径；Esensor为传感器能量系数。

用于数据处理的能耗模型为：

式中Ecpu为处理器能量系数。

2.3分布式模糊聚类分簇算法

分布式模糊聚类算法（DFLC）中，每个节点都使用模糊逻辑推理，根据该节点的信息和与之直接连接的子节点信息来判断哪个传感器节点最适合成为根节点。分布式模糊聚类算法（DFLC）中的有限状态机，如图1所示。若当前根节点的剩余能量低于阈值（初始能量的50%）或当前根节点出现故障，则根节点将会给所有树中成员节点广播报警信息。成员节点接收到报警信息后，它就通过它的父节点给当前根节点发送回复信息（ID，剩余能量，中心性，距基站的距离，跳数，节点密度）。收集完毕后，节点运行分布式模糊逻辑，避免把不必要的消息发送到根节点。通过分布式模糊逻辑，中间成员节点只需发送质量最高子节点的回复消息，大大减少了被发送到根节点的消息数量。

当一个根节点从它的子节点接收到回复消息后，该根节点就运行分布式模糊逻辑算法来选择一个节点作为新的根节点，并且发送“你是新的根节点”的消息给被选定的根节点。成员节点接收“你是根节点”的消息后，检查本身是否是目的节点，若当前节点是目的节点，它就洪泛“我是根节点”的消息给当前簇中的所有节点；否则就把“你是根节点”的消息朝着目的节点继续转发。若一个目的成员节点接收了“我是根节点”的消息，它就开始更新自己存储空间中根节点ID和父节点的信息，同时给它的邻居节点发送“我是根节点”的消息。算法1给出了分布式模糊聚类算法的伪代码。基于模糊规则的模糊化和推理、集成输出和去模糊化是分布式模糊逻辑推理系统的主要步骤。该系统的隶属函数如图2所示。

模糊化：模糊化是利用隶属度函数，确定一个从清晰的输入到模糊集之间的映射。其中有五个输入，即节点的能量、中心性、到基站的距离、跳数、节点密度；一个输出，即概率。节点能量（NE）：每个节点的剩余能量。中心性（C）：树中一个节点到其他节点的距离。基站距离（DBS）：从节点到基站的距离。跳数（NoH）：在根节点和成员节点之间的中间节点数。节点密度（ND）：节点的邻居节点数。概率（P）：具有被选为根节点的最大概率的节点。

应用模糊规则：数据在进行模糊化输入时使用了模糊规则。计算概率输出参数度的公式如下：

式（5）考虑了剩余能量的增量、节点密度值对概率的正面影响和中心值、到基站的距离、跳数对概率的负面影响。输入参数度被设置为0,1,2，分别对应低、中、高三种情况。与之相类似，0,1,2的值分别对应了距离相近、距离相当、距离遥远三种情况。

输出集合：将所有输出规则汇总到统一的输出。模糊输出变量的概率可以从模糊规则中得到。概率越高意味着该节点有更多的机会成为一个根节点。

模糊化：把模糊输出的概率变量转变为清晰输出的过程。其中的反模糊化方法是面积中心算法（COA）。该算法中，模糊逻辑控制器首先计算隶属函数和输出变量范围内的面积，然后使用下面的公式计算几何中心的面积[7]。

式中x是语言变量的值。

2.4 系统性能分析

2.4.1容错

传感器节点可能会因为能源耗尽或中断等多种原因而失效，这些情况下，系统需要用另一条路径解决问题[8]。为了达到这个目的，在系统建立阶段，当一个节点接收到“发现”消息时，它就把发送节点的ID存储下来，并指定该节点是到Sink节点最近的一个邻居节点，作为备用路径。同时，一些节点被确定为根节点的备份，以防当前根节点失效[8]。根节点故障也会引发根节点的选举过程。为了检测根节点的状态，当前根节点周期性地广播“检查”消息，其中包含具有最大概率成为根节点的备份根节点的ID。若一段时间内成员节点没有收到任何“检查”消息，则就判定当前根节点出现故障，随后在簇内部把备份根节点作为目的地址，洪泛发送“新簇”的消息。当中间节点接收到“新簇”的消息后，它检查自己是否存储了该目的节点。若存储空间已有该目的节点，就发送含有从自身节点到目的节点距离的“回复新簇”的消息。否则，该成员节点就继续把“新簇”的消息广播给它的相邻节点。

2.4.2负载平衡

负载均衡对延长网络寿命是非常重要的。使用同一条路径传输和使用相同节点进行大量计算都会导致能量的快速消耗。为了避免这种情况，负载必须均衡分配给所有节点。本文通过循环担任根节点和使用多路径传输，有效平衡了网络负载。

2.4.3时效性

为了避免簇中节点与根节点之间的数据包传输发生冲突，本文利用TPIPE[9]调度模型调度聚集树拓扑结构中每个节点的传输。除此之外，在系统初始化阶段还使用了退避等待时间机制[8]。在退避等待时间中，传感器节点接收广播信息后，只以最小数量的跳数作为参数来评价消息。以此来减少设置信息的传输数量。

2.4.4可扩展性

由于较多的节点数量和较高的节点密度，WSN应用程序中聚类协议必须具有良好的可扩展性和对网络拓扑的适应性。同时，当网络规模越来越大时，负载不断增加，协议也必须能够良好的运行。本文模拟了不同节点数目和节点密度的场景并进行实验，结果表明本文提出的分布式模糊聚类系统能够良好运行。除此之外，利用多路径路由策略，使其能够自适应网络中拓扑结构的变化。

2.5参数计算

2.5.1消息复杂度

假设DCBTA(PF)消息复杂度为O(n)。在簇中，当一个根节点消耗了50%能量或发生故障时，它就给树中所有节点广播报警消息。成员节点收到报警信息后，把cs（簇中的节点的平均数）消息返回给根节点。根节点接收回复消息后，运行DFL算法，并把“你是根节点”的消息发送给目的节点。最坏的情况是新的根节点在距离根节点dt（簇中树的深度）距离处。这种情况下，为了把消息发到目的节点，“你是根节点”的消息可能被转发dt次。当新的根节点接收“你是根节点”的消息后，它就把“我是根节点”的消息广播给树中所有的节点。假设n是网络中簇的平均数，则整体的消息复杂度O(n)可计算如下：

消息总数为：

2.5.2能量消耗

传感器主要在分组传输、数据包接收、数据传感和处理中消耗能量。本文算法中能量消耗的步骤如下：

若n是网络中簇的平均数；d0是传输距离；用k表示平均消息长度。根节点给树中所有节点发送报警信息的能量消耗为：

成员节点收到报警信息的过程中也有一定的能量消耗。若cs是簇中节点的平均数目，则接收信息所消耗的能量为：

成员节点收到报警信息后，会把cs应答消息回复给根节点。发送该回复消息消耗的能量为：

根节点接收回复消息消耗的能量为：

根节点接收到回复消息后会运行分布式模糊逻辑来处理数据。该数据处理过程所消耗的能量为：

根节点运行分布式模糊逻辑之后，就发送“你是根节点”的消息给目的节点。这一过程中所消耗的能量为：

目的节点接收“你是根节点”所消耗的能量为：

新的根节点接收“你是根节点”的消息后，就把“我是根节点”的消息广播给树中所有节点。这一过程所消耗的能量为：

成员节点接收“我是根节点”所消耗的能量为：

3实验

利用NS2仿真器将提出的DFLC与低能耗自适应聚类层次算法（LEACH)[3]、等待定时自适应聚类算法（ACAWT)[10]、基于模糊逻辑簇头选举算法（CHEF)[4]和Gupta算法[11]，在消息负载、网络能耗、存活节点数、容错性和簇头能耗方面进行了实验对比。表1给出了相关的仿真参数。

不同运行时间下的信息传输数量比较情况，如图3所示。

从图3中可以看出，DFLC算法产生的消息传输量最少，LEACH算法产生的消息传输量最大。在ACAWT算法中，簇被分成了各个子簇，成员节点分为子簇头和子簇成员。基于分簇头之间的通信来选择新簇头，这样就降低了消息传输量。在Gupta算法中，基站统一收集来自节点的信息，然后运行聚类算法，这一过程产生了巨大的消息传输量。在CHEF算法中，基站不需要从所有节点收集信息，所以CHEF算法要优于Gupta算法。本文提出的DFLC算法通过筛选最有可能成为根节点的那个节点的信息，使中间节点减少了从叶节点发到根节点的信息量，所以产生的数据量最小。

不同算法的能量消耗，如图4所示。可以看出，随着仿真时间的增加，所有算法的能量消耗也都将会增加。其中，DFLC算法产生的能源消耗最低，LEACH算法产生的能源消耗最高。ACAWT算法中，在新簇头的选择阶段，分簇头向整个簇广播数据，这就导致产生高能耗，尤其在有大量簇头数的情况下。尽管Gupta算法考虑了能耗、节点浓度和中心参数等因素，收集节点和基站之间的数据，在基站集中运行模糊逻辑系统的过程仍然导致了较大的能源消耗。CHEF和Gupta算法类似，与之主要不同点是使用了局部簇头选举机制，从而使基站不需要从所有节点收集信息。LEACH算法完全取决于概率模型，导致簇头节点的能量被迅速消耗。

不同仿真时间下各算法中存活节点的数量，如图5所示。可以看出，随着时间的增加，存活节点数量不断减少。其中，本文DFLC算法中存活节点数最多，而LEACH算法最少。因为与LEACH,Gupta和CHEF算法不同的是，DFLC算法中传输消息的数量较少，能量消耗低，存活节点数也高于其他算法。

有限的能源是WSN的一个非常重要的约束。由于能源的消耗，节点可能会失效，这就导致不能及时完成正常任务，这就需要一个容错机制，当节点失效后，用另一个节点来代替它继续发挥作用，继而使整个过程能够继续进行。为此，本文DFLC算法中集成了容错机制。图6为各个算法中容错机制的性能。实验中，通过故意丢弃节点的数据包来制造一些故障节点。将传送的所有数据包记为“提供数据”，成功传输的数据包记为“投递数据”。从图6可以看出，和其他没有考虑系统故障情况的算法相比，本文提出的算法具有最好的性能。同时，DFLC算法还与文献[12]提出的具有簇头容错聚类技术的FTFC算法进行比较。结果表明，DFLC的容错性能优于FTFC。

为了延长系统寿命，需要均衡簇头负载。将本文算法同现有的2种WSN负载均衡分簇算法：EELBC[13]和LBC[14]进行比较，结果如图7所示。实验中计算了6组簇头的能耗平均值作为能量消耗率。可以看出，DFLC算法具有最低的簇头能量消耗率。

4结语

本文提出了一种基于模糊逻辑的WSN分布式聚类算法（DFLC）。通过仿真实验，将本文算法与LEACH,ACAWT,Gupta和CHEF算法在产生消息数量、能源消耗、存活节点数、容错性、负载平衡等方面进行比较。结果表明，DFLC算法优于其他分簇算法。