推理算法范文

2024-06-19

推理算法范文（精选9篇）

推理算法第1篇

1 模糊推理的概述

作为推理的一种重要分支, 模糊推理成为模糊控制理论的重要基础。然而, 在实际应用过程中, 模糊推理主要以数值计算为主, 通过模糊推理的算法, 由推理的前提进而计算出结论。因此, 模糊推理技术已经在计算机行业得到了广泛应用, 实现了软件编程的最佳智能计算方法。除此之外, 模糊推理算法也逐渐应用于模糊控制系统、模糊神经网络系统、模糊专家系统等领域范围内。

假设A和A*是论域X上的模糊集, B和B*是论域Y上的模糊集。通常情况下, 模糊推理主要以最简单的模糊假言推理模型为基础, 即FMP。

由此可见, (2) 式所体现的问题称为模糊拒取式, 简称FMT。因此, 为了解决模糊推理的问题, 众多学者提出了多种模糊推理的方法, 如三I算法, CRI方法等。具体分析如下。

2 模糊推理的三I算法分析

2.1 三I算法应用缺陷

目前, 模糊推理的三I算法已经受到众多各界的广泛关注, 然而, 人们对于三I算法的研究始终停留在理论层面, 还没有将其应用到实际控制中。而三I算法正是从逻辑语义的角度提出来的模糊推理, 所以, 有相关研究发现, 尽管三I算法具有比较完善的逻辑语义, 但在一定条件下还不能求解出人们所需的模糊集, 正因如此, 三I算法还不能应用到实际控制过程中。

2.2 模糊推理的三I算法研究的内容

首先, 要针对不同的蕴涵算子的三I算法进行研究, 即在三I算法刚被提出的过程中, 所采用的蕴涵算子R0, 而三I原则中所提出的是一般的蕴涵, 所以, 这才让更多的学者开始研究不同的蕴涵算子的三I算法。

其次, 要针对三I算法的理论知识进行研究, 比如三I算法的连续性、还原性等都在理论知识的研究的范围内。

最后, 要针对三I算法的改进算法进行研究, 这样有助于构造新型的三I算法。

3 模糊推理的CRI方法

针对模糊推理概述中FMP和FMT的问题, 以模糊推理理论中最基本的模糊分离原则为依据, 经过不少专家学者的共同研究, 将其算法化, CRI方法应运而生, 被众多领域所应用。

所谓CRI方法, 首先是要选择一个适宜的蕴涵算子I, 并将A→B转化为X×Y上面的模糊关系R, 可以记作:R (x, y) =I (A (x) , B (y) ) , (x, y) ∈X×Y, 然后将A*和模糊关系R进行复合运算, 就可以得到B*, 将其输出出来, 并记作:B*=xX[A* (x) ∧I (A (x) , B (y) ) ]。因此, 在CRI方法中, 由A→B所构造形成的模糊关系R, 在最初采用蕴含算子的是Iz (x, y) = (1-x) ∨ (x∧y) , x, y∈[0, 1], 然而得到的结果却和人们的直观大有不同, 因此, 采用其它方式来构造模糊关系R得到:Im (x, y) =1∧ (1-x+y) , x, y∈[0, 1], 由此可见, 这类方法的应用得到了全面推广。

而CRI方法中的A*和R的复合运算, 在最初时候采用的是∨-∧这样一对算子, 经过不断改进, 逐渐应用一般的三角模T来进行计算。在众多学者的不断努力研究下, CRI方法除了对模糊关系的构造进行研究之外, 还对合成运算以及输入模糊集A*进行适宜处理, 从而构造出X is A相对于X is A*的语言真值τA/A*, 而A*直接被其所代替, 最终得到推理的结果。

4 结语

总之, 模糊推理算法在计算机的模糊控制领域得到广泛应用, 同时也被应用于其他工业生产技术中, 从而为人们提供一个不完善的知识数据库, 对某一模糊问题得出一个比较接近的答案。所以, 模糊推理算法还应进一步探究, 这样才能为更多领域提供便利, 促进信息技术的发展。

摘要：随着科技的快速发展, 模糊推理算法逐渐成为信息技术中处理模数信息的重要工具, 受到计算机科学领域的广泛关注。作为推理的重要分支, 在计算机网络的帮助下, 模糊推理算法更是有了突飞猛进的发展, 为计算智能领域做出了重要贡献。而本文主要对模糊推理算法进行了详细探究, 为进一步理解模糊推理算法提供了重要依据。

关键词：模糊推理,算法,计算机,研究

参考文献

[1]邓冠男.模糊推理算法的研究进展[J].东北电力大学学报, 2013, (6) :64-69.

[2]潘正华.模糊推理算法的数学原理[J].计算机研究与发展, 2008, (Z1) :165-169.

[3]易安.基于神经网络的模糊推理模型和算法研究[D].西南大学, 2010:35-43.

模糊推理三I约束算法的一般表示第2篇

讨论模糊推理三I约束算法的表示问题.首先,改进FMP及FMT问题的三I约束原则,进而,为使更多的.蕴涵算子纳入统一的算法表示之下,基于较弱的条件建立三I约束算法的一般表示.如此,现有的三I约束算法的统一表示被推广到一种新的形式.

作者：刘华文王国俊 LIU Hua-wen WANG Guo-jun 作者单位：刘华文,LIU Hua-wen(山东大学,数学学院,山东,济南,250100)

王国俊,WANG Guo-jun(陕西师范大学,数学研究所,陕西,西安,710062)

多特征模糊推理的虹膜识别算法第3篇

高度信息化的社会在诸多领域都需要信息的高度交互,这使身份认证的重要性越来越突出。生物特征识别技术[1]是利用人所固有的生理特征和行为特征进行识别的技术,依靠生物特征进行身份的鉴别无疑是更加可靠和方便的手段。虹膜作为重要的身份鉴别特征,具有唯一性、稳定性、可采集性、非侵犯性等优点。在生物特征识别中虹膜识别具有更高的准确性[2]。这使虹膜识别技术的发展有着广阔的空间和前景。

典型的虹膜识别过程包括:虹膜图像的采集、预处理(定位与归一化、图像增强)、特征提取、编码、匹配等环节。虹膜图像的预处理过程如图1所示,具体方法可参阅文献[3,4,5,6]。本文利用尽量不受噪声干扰的虹膜图像作为算法的输入,如图1(d)中所示已标出白色矩形的部分,分辨力为:32×304。

由于虹膜含有极其丰富的纹理信息,能否有效的将这些信息尽量准确的表征是至关重要的。目前已经提出了很多特征提取和分类方法[4,5,6,7,8,9,10,11,12,13,14],在特征提取上,大多数方法只提取单一的纹理特征,缺点是不能直接反映丰富、变化的纹理细节,也由于采集图像时很多因素(尤其光照变化)的影响,可能对所提取的某种特征产生很大的干扰,如果能提取多种特征,将其相互融合进行识别,则在很大程度上降低了噪声同时影响多种特征的几率,使识别性能得到提高;在模式的分类上,大多数方法采用通过距离的方式进行直接线性分类,这虽具有直接快速的优点,但缺点是分类能力不高,尤其是在样本特征线性不可分的情况下。

本文提出了一种新的特征提取和分类方法,提取局部特征点、局部纹理方向和局部纹理的亮暗变化三种特征,更全面的描述了纹理的特征空间,克服了之前的虹膜识别算法提取单一特征易受干扰影响的局限性。同时,设计了模糊推理规则进行分类识别,在一定程度上提高了算法通过线性分类器进行分类的能力。

1 特征提取

利用虹膜纹理的复杂性特点,将虹膜图像等分为若干个子图像,再将每个子图像等分为若干个子区域。子区域的划分是为了找出虹膜纹理阶跃变化最强烈的局部位置,并找出该局部位置处虹膜纹理的方向和纹理的亮暗变化;子图像的划分保证了选中的特征在空间上相对分散,并使纹理方向和纹理的亮暗变化在相对分散的空间尺度上便于统计,这样会减少噪声对特征的干扰程度,减少了误匹配的发生。具体步骤如下:

1)在虹膜图像I(x,y)中,分别计算每一像素点(x,y)在8邻域内与其相邻8个像素灰度的差分值Gd(d=1,2,…,8)(这里将圆周360°按照每隔45°等分成8个方向,用d表示),如图2所示。将式(1)∼(8)求得的八个值中绝对值最大的一个作为该点的灰度变化特征值,记作gd(x,y),如式(9),并记录此时d的值作为该处的纹理方向;同时记录该方向差分值Gd的符号正负,表示该处纹理亮暗变化,用s表示正负(s为正:表示纹理由亮到暗;s为负:表示纹理由暗到亮),s符号为正号则此处标记为1,否则标记为0。在虹膜图像每一像素点处,都会得到灰度变化特征值gd(x,y)、纹理方向d和亮暗变化的符号s三个特征。

2)按照8×8大小为一块的原则将图像I(x,y)等分成若干个互不重叠的子区域FPi,j,求每个8×8子区域内64个像素的灰度变化特征值gd(x,y)之和,得到此区域的灰度变化度,记作G(FPi,j)。灰度变化度越大,表明在该区域内,纹理的阶跃变化越强。

并把每8×8子区域内64个像素的纹理方向d做直方图统计,直方图的峰值代表该区域的主方向,把主方向值作为该子区域的方向特征码。

同时,统计子区域内符号s为正的个数,即统计计算此子区域纹理的亮暗变化是由亮到暗还是由暗到亮。如果s=1的个数,即符号为正的个数超过32,则表示此子区域纹理统计变化由亮到暗(标记flag为1),否则由暗到亮(标记flag为0),将flag的值作为该子区域的亮暗变化特征码。

3)将虹膜子区域FPi,j按照2×2大小的原则组成子图像,即4个子区域组成1个子图像。把子图像GPk,l中灰度变化度G(FPi,j)的值最大的子区域作为子图像的特征,并将此子区域标记为1,其余3个子区域标记为0,将此作为子区域的点特征码。

2 编码

每个子图像包含4个子区域,这样,每个子图像中都包含4个点特征码、4个纹理方向特征码和4个亮暗变化特征码,分别按照子图像和子区域行优先的顺序进行特征编码。编码顺序如图3所示。

编码顺序为:11(1)、11(2)、11(3)、11(4)、12(1)、12(2)、12(3)、12(4)、……、1n(1)、1n(2)、1n(3)、1n(4)、21(1)、21(2)、21(3)、21(4)、22(1)、22(2)、22(3)、22(4)、……、2n(1)、2n(2)、2n(3)、2n(4)、…………、m1(1)、m1(2)、m1(3)、m1(4)、m2(1)、m2(2)、m2(3)、m2(4)、……、mn(1)、mn(2)、mn(3)、mn(4)。按照此编码顺序,分别将点特征、方向特征和亮暗变化特征编成3组编码,并分别用p、d、v表示。

3 匹配

1)点特征匹配

其中:pk*和pk分别表示待匹配的两组一维点特征编码中的第k个码值,Np表示点特征码长,Dp表示两组点特征编码的海明距离。

2)方向特征匹配

其中:dk*和dk分别表示待匹配的两组一维方向特征编码中的第k个码值,Nd表示方向特征码长,Dd表示两组方向特征编码的距离。

3)亮暗变化特征匹配

其中:vk*和vk分别表示待匹配的两组一维亮暗变化特征编码中的第k个码值,Nv表示亮暗变化特征码长,Dv表示两组亮暗变化特征编码的海明距离。

4)融合三特征进行匹配

其中:λ1、λ2、λ3是加权系数。由于点特征和亮暗变化特征在编码时采用0、1编码,而方向特征采用的编码方式是如图2所示的八方向编码(即特征向量中的每个分量的编码值可能为数字1∼8中的某个值),这样所求得的Dp、Dv与Dd的数值便不在同一数量级。不同数量级的数据进行运算时,小数量级的数据容易被大数量级的数据吞没,因此为了避免不同特征之间的相互影响需要将不同数量级的数据调整到同一数量级。

4 模糊推理规则设计

为了有效的结合三种纹理特征,本文设计了一种模糊推理规则用于模式的分类,规则如下:

规则1:if融合三特征&&Df(k)

规则2:if融合三特征&&Df(k)≥TfHthen虹膜属于不同类;

规则3:if融合三特征&&TfH>Df(k)≥TfLthen用点特征进行分类;

规则4:if点特征&&Dp(k)

规则5:if点特征&&Dp(k)≥TpHthen虹膜属于不同类;

规则6:if点特征&&TpH>Dp(k)≥TpLthen用方向特征进行分类;

规则7:if方向特征&&Dd(k)

规则8:if方向特征&&Dd(K)≥TdHthen虹膜属于不同类;

规则9:if方向特征&&dTH>Dd(k)≥TdLthen用亮暗变化特征进行分类;

规则10:if亮暗变化特征&&Dv(k)

规则11:if亮暗变化特征&&Dv(k)≥Tvthen虹膜属于不同类。

上述11个规则中,Df、Dp、Nd、Dv分别为融合三特征加权和距离、点特征距离、方向特征距离、亮暗变化特征距离;Tf L、Tf H表示用三特征相融合进行分类的两个阈值;Tp L、Tp H表示用点特征进行分类的两个阈值;Td L、Td H表示用方向特征进行分类的两个阈值;Tv表示用亮暗变化特征进行分类的阈值。

5 实验

为了能充分验证本算法,本文分别采用了中国科学院自动化研究所的CASIA虹膜图像数据库(版本1.0)和本实验室自采集图库,从两图库中各选取60只眼睛分别进行实验,CASIA图库中每只眼睛7幅样本图像,共选取420幅图像;本实验室自采图库中每只眼睛10幅样本图像,共选取600幅图像。实验采用类内(相同模式)和类间(不同模式)图像分别两两匹配。在自动化研究所的CASIA图库中共进行匹配实验C2420=87990次,其中类内匹配60×C72=1 260次,类间匹配87 990-1 260=86 730次;在本实验室自采集图库中共进行匹配实验C2600=179 700次,其中类内匹配60×C210=2 700次,类间匹配179 700-2 700=177 000次。

正确识别率(CRR)的计算方法为:

首先,利用提取的三种特征((1)项点特征,(2)方向特征,(3)亮暗变化特征)及三种特征的融合特征(Fusion feature),针对两个图库,分别直接通过距离Dp、Nd、Dv、Df进行线性分类。实验的正确识别率(CRR),等错误率(EER)、错误拒绝次数(FR)、错误接受次数(FA)和总匹配次数(TM)共同列在表1中,在两个图库中的实验结果都以利用融合特征(Fusion feature)进行线性分类的效果最好,错误拒绝和错误接受的次数也最少,识别率分别为94.55%和96.11%,表明多种特征相结合能较全面的描述虹膜的纹理特征空间。

然后再利用本文设计的模糊推理规则进行分类识别,实验结果如图4(CASIA图库上的实验结果)和图5(本实验室自采集图库的实验结果)所示,分别为在两个图库上利用多特征进行分段线性分类的距离分布曲线。

本方法先利用融合特征(Fusion feature)进行分类,依据设计的模糊推理规则1、2、3,分别取得两个阈值Tf L和Tf H,其中将类间匹配距离的最小值设定为Tf L,将类内匹配距离的最大值设定为Tf H。例如图4(a)所示,靠左侧的曲线intra-class为融合特征的类内距离分布曲线,所有1 260次类内匹配的最大匹配距离为Tf H=4.123 6,靠右侧的曲线inter-class为融合特征的类间距离分布曲线,所有86 730次类间匹配的最小匹配距离为Tf L=3.055 3。在模式识别时,只要匹配距离Df>Tf H,则认为进行匹配的两种模式属于不同类,即两样本不属于同一只眼睛;当匹配距离Df

6 实验结果分析

从实验结果可以看出,尽管本算法具有很好的识别性能,但是,仍然存在错误识别的情况,通过对发生错误匹配的实验进行分析发现,主要有两个原因:

1)由于光照的强弱变化,会使瞳孔造成一定程度的缩放。光照强会使瞳孔收缩变小,光照暗则会使瞳孔扩张放大,这将使虹膜纹理受到瞳孔的缩放牵动和挤压而发生变化,如图6所示。在实验中,所有错误匹配的35.3%是由于这种情况造成的。

2)在空间域直接提取特征具有速度快、计算量小等优点,但受光照变化的影响却相对较大。由于光照的变化,使得局部纹理阶跃变化较弱的位置信息提取不够准确。在本实验中,所有错误匹配的64.7%是由于这种原因造成的,这也是目前在空间域提取特征所遇到的共同需要解决的问题和难点。本文方法也正是在这方面存在一定的弱势,特征的表征不稳定或容易出现错误。

因此,以后的工作将重点研究如何表征光照变化前后的稳定特征,使特征模板的提取更加准确。

7 结论

推理算法第4篇

13.3 直接证明与间接证明

一、选择题

1.“所有9的倍数都是3的倍数，某奇数是9的倍数，故该奇数是3的倍数.”上述推理()

A 小前提错B 结论错

C 正确D 大前提错

解析大前提，小前提都正确，推理正确，故选C.答案 C

2．在用反证法证明命题“已知a、b、c∈(0,2)，求证a(2－b)、b(2－c)、c(2－a)不可能都大于1”时，反证时假设正确的是()

A．假设a(2－b)、b(2－c)、c(2－a)都小于

1B．假设a(2－b)、b(2－c)、c(2－a)都大于

1C．假设a(2－b)、b(2－c)、c(2－a)都不大于

1D．以上都不对

解析 “不可能都大于1”的否定是“都大于1”，故选B.答案 B

3．下列命题中的假命题是()．

A．三角形中至少有一个内角不小于60°

B．四面体的三组对棱都是异面直线

C．闭区间[a，b]上的单调函数f(x)至多有一个零点

D．设a，b∈Z，若a＋b是奇数，则a，b中至少有一个为奇数

解析 a＋b为奇数⇔a，b中有一个为奇数，另一个为偶数，故D错误．答案 D

4．命题“如果数列{an}的前n项和Sn＝2n2－3n，那么数列{an}一定是等差数列”是否成立()．

A．不成立B．成立C．不能断定D．能断定解析 ∵Sn＝2n2－3n，∴Sn－1＝2(n－1)2－3(n－1)(n≥2)，∴an＝Sn－Sn－1＝4n－5(n＝1时，a1＝S1＝－1符合上式)．

又∵an＋1－an＝4(n≥1)，∴{an}是等差数列．

答案 B

1115．设a、b、c均为正实数，则三个数a＋b＋c＋)． bca

A．都大于2B．都小于

2C．至少有一个不大于2D．至少有一个不小于2 解析 ∵a＞0，b＞0，c＞0，11111a＋b＋c＋a＋b＋＋＋＝＋＋ ∴bcaab

1c＋≥6，c

当且仅当a＝b＝c＝1时，“＝”成立，故三者不能都小于2，即至少有一个不小于2.答案 D

6．设a＝lg 2＋lg 5，b＝ex(x＜0)，则a与b大小关系为()

A．a＞b

C．a＝bB．a＜bD．a≤b

解析 ∵a＝lg 2＋lg 5＝lg 10＝1，而b＝ex＜e0＝1，故a＞b.答案 A

7．定义一种运算“*”：对于自然数n满足以下运算性质：(n＋1)*1＝n*1＋1，则n*1＝()．

A．nB．n＋1C．n－1D．n2

解析由(n＋1)*1＝n*1＋1，得n*1＝(n－1)*1＋1＝(n－2)*1＋2＝„＝n.答案 A

二、填空题

8.用反证法证明命题“若a，b∈N，ab能被3整除，那么a，b中至少有一个能被3整除”时，假设应为.解析由反证法的定义可知，否定结论，即“a，b中至少有一个能被3整除”的否定是“a，b都不能被3整除”.答案 a、b都不能被3整除

9．要证明“3＋7＜25”可选择的方法有以下几种，其中最合理的是________(填序号)．

①反证法，②分析法，③综合法．

答案 ②

10．设a，b是两个实数，给出下列条件：

①a＋b>1；②a＋b＝2；③a＋b>2；④a2＋b2>2；⑤ab>1.其中能推出：“a，b中至少有一个大于1”的条件是______．(填序号)

12解析若a＝b＝a＋b>1，2

3但a<1，b<1，故①推不出；

若a＝b＝1，则a＋b＝2，故②推不出；

若a＝－2，b＝－3，则a2＋b2>2，故④推不出；

若a＝－2，b＝－3，则ab>1，故⑤推不出；

对于③，即a＋b>2，则a，b中至少有一个大于1，反证法：假设a≤1且b≤1，则a＋b≤2与a＋b＞2矛盾，因此假设不成立，故a，b中至少有一个大于1.答案 ③

11．如果aa＋bb＞b＋a，则a、b应满足的条件是________．解析首先a≥0，b≥0且a与b不同为0.要使aa＋bb＞b＋a，只需(aa＋bb)2＞(ab＋ba)2，即a3＋b3＞a2b＋ab2，只需(a＋b)(a2－ab＋b2)＞ab(a＋b)，只需a2－ab＋b2＞ab，即(a－b)2＞0，只需a≠b.故a，b应满足a≥0，b≥0且a≠b.答案 a≥0，b≥0且a≠b

12．若a，b，c是不全相等的正数，给出下列判断：

①(a－b)2＋(b－c)2＋(c－a)2≠0；

②a>b与a

③a≠c，b≠c，a≠b不能同时成立．

其中判断正确的是_______．

解析①②正确；③中a≠c，b≠c，a≠b可能同时成立，如a＝1，b＝2，c＝3.选C.答案 ①②

三、解答题

13．在△ABC中，三个内角A、B、C的对边分别为a、b、c，113a＋bb＋ca＋b＋c试问A，B，C是否成等差数列，若不成等差数列，请说明理由．若成等差数列，请给出证明．

解析 A、B、C成等差数列．

证明如下：

∵

∴

∴113＋＝，a＋bb＋ca＋b＋ca＋b＋ca＋b＋c＋＝3.a＋bb＋cc

a＋bb＋c＋a＝1，∴c(b＋c)＋a(a＋b)＝(a＋b)(b＋c)，∴b2＝a2＋c2－ac.在△ABC中，由余弦定理，得

a2＋c2－b2ac1cosB＝ 2ac2ac

2∵0°

|a|＋|b|14．已知非零向量a，b，且a⊥b，求证：2.|a＋b|证明 a⊥b⇔a·b＝0，|a|＋|b|要证2.|a＋b|只需证|a|＋|b2|a＋b|，只需证|a|2＋2|a||b|＋|b|2≤2(a2＋2a·b＋b2)，只需证|a|2＋2|a||b|＋|b|2≤2a2＋2b2，只需证|a|2＋|b|2－2|a||b|≥0，即(|a|－|b|)2≥0，上式显然成立，故原不等式得证．

15．若a、b、c是不全相等的正数，求证：

lga＋b2＋lgb＋c2＋lgc＋a2＞lg a＋lg b＋lg c.证明 ∵a，b，c∈(0，＋∞)，∴a＋b2ab＞0，b＋c2≥bc＞0，a＋c2ab＞0.又上述三个不等式中等号不能同时成立．

∴a＋bb＋cc＋a2·2·2＞abc成立．

上式两边同时取常用对数，a＋bb＋cc＋a＞lg(abc)，得lg222

∴lga＋b2＋lgb＋c2＋lgc＋a2＞lg a＋lg b＋lg c.16．(12分)已知二次函数f(x)＝ax2＋bx＋c(a＞0)的图象与x轴有两个不同的交点，若f(c)＝0，且0＜x＜c时，f(x)＞0.1(1)证明：是f(x)＝0的一个根； a

a1(2)试比较与c的大小；

(3)证明：－2＜b＜－1.解析(1)证明 ∵f(x)的图象与x轴有两个不同的交点，∴f(x)＝0有两个不等实根x1，x2，∵f(c)＝0，∴x1＝c是f(x)＝0的根，c11又x1x2＝x2＝≠c，aaa

1∴是f(x)＝0的一个根． a

11(2)假设＜c，又＞0，aa

由0＜x＜c时，f(x)＞0，111知f＞0与f＝0矛盾，∴c，aaa

11又∵≠c，∴＞c.aa

(3)证明由f(c)＝0，得ac＋b＋1＝0，∴b＝－1－ac.又a＞0，c＞0，∴b＜－1.二次函数f(x)的图象的对称轴方程为

bx1＋x2x2＋x21x＝－＝＜＝x2＝ 2a22a

b1即－＜.又a＞0，2aa

推理算法第5篇

文献[2]提出了一个基于模糊Petri网的反向推理算法，该算法可以用一个模糊与或图来表示。算法以目标库所为根节点，在模糊Petri网中沿弧反向搜索，生成模糊与或图，然后通过用户的输入，利用模糊与或图计算出推理结果。这个算法实质上是一个基于图搜索的算法，数据结构和算法复杂度都较大。文献[3]中也给出了一个用于从高级Petri网中抽取一个子网的算法，该算法利用高级Petri网简化得到的Petri网的关联矩阵和两个作为辅助存储结构的队列来得到需要的子网。算法从目标库所开始，在Petri网中沿弧反向搜索和目标库所相关的库所和变迁，其中关联矩阵用于寻找库所和变迁之间的连接关系。文献[4]给出了一个基于Petri网关联矩阵的反向推理算法，算法基于矩阵运算实现，推理过程简单、易于实现。

提出的反向推理算法得到的是整个加权模糊Petri网N的一个子网，子网由与用户给出的目标命题关联的库所相关的所有库所和变迁构成。在反向推理过程中并不涉及命题权值、变迁阈值和命题可信度等计算，只是从连接关系上加以考虑，因此在推理过程中使用的Petri网N*是从加权模糊Petri网N简化得到的，称N*为N的关联Petri网[3]，在N*中不考虑命题权值、变迁阈值和命题可信度等参数，只保留了N的基本结构，即库所、变迁以及它们之间的连接关系与库所和命题之间的映射。

定义1(加权模糊Petri网的关联Petri网，APN)加权模糊Petri网N的关联Petri网N*定义为一个六元组：

其中，，表示库所结点的有限集合。

表示变迁结点的有限集合。

表示命题的有限集合。

是输入函数,反映变迁到库所的映射。

是输出函数,反映变迁到结点的映射。

是一个映射,反映库所结点与命题之间的一一对应关系。

下边给出反向推理算法中关联Petri网N*的矩阵定义，设关联Petri网N*有n个库所结点，m个变迁结点。

定义2(关联Petri网N*的矩阵)反向推理算法中关联Petri网N*的矩阵定义：

(3)，为库所向量，其中第i个元素表示库所pi关联的命题是否为目标命题或是与目标命题有关，如果是则pi为1，否则pi为0。，表示目标库所向量。其中第i个元素表示库所pi关联的命题是否是目标命题，如果是则pi为1，否则pi为0。

(4)，为变迁向量，其中第j个元素表示变迁tj是否与目标命题有关，如果是则tj为1，否则tj为0。，表示初始变迁向量，初始值一般是一个零向量。

在算法中引入了两个极大代数中的矩阵运算算子[5]：

，其中X,Y,Z都是n×m为矩阵。

，其中X,Y,Z分别为n×l、l×m、n×m维的矩阵。

1 反向推理算法

文献[1]中指出在Petri网模型中，只要将网中的弧方向进行颠倒，就可得到一个向后推论的Petri网模型。基于这个思想，在本节中利用APN的输入矩阵和输出矩阵来表示网中库所与变迁的连接关系，通过引入两个极大代数中的矩阵运算算子，利用矩阵运算来进行迭代，实现基于矩阵运算的反向推理算法，算法利用了Petri网的并行处理能力，提高了推理效率，也使得推理过程更加简单、快速和易于实现。下边给出基于矩阵运算的反向推理算法：

1.1 算法B

输入：输入矩阵，输出矩阵，初始变迁向量，目标库所向量。

输出：库所向量P1和变迁向量T1。

B1：计算输出库所是目标库所的变迁

B2：计算B1中求出的变迁的输入库所

B3：将B2中求出的库所加入到P1中

B4:如果转B1。否则,算法结束,P1和T1中的非零元素分别是和目标库所相关的库所和变迁。

1.2 分析

下边对算法B的正确性进行证明并对复杂性进行分析。

1.2.1 正确性证明

下边考虑两种情况来对算法的正确性进行证明。

(1)在算法执行第一步时，对于给定的目标库所P0,

因为，所以给定的目标库所全部是加权模糊Petri网中的初始库所，这些库所不由网中的其他库所推出，因此算法推理结果应该等于P0。

因为,则根据输出矩阵的定义,,j=1,2,…,m,执行算法B第1步有:

法能够终止且结果正确。

(2)在算法执行第一步时，对于给定的目标库所P0，至

因为不妨设则根据输出矩阵的定义,执行算法B第1步有:

从结果可以看出,T1中第k个元素由初始值0变为了1,即表示变迁tk与给定的目标库所相关,这与显然是一致的。为不失一般性,设,,则根据输入矩阵的定义,执行算法B第2步有:

从结果可以看出,P1中第r个元素由初始值0变为了1,即表示库所pr与给定的目标库所相关,这与显然是一致的。执行算法第三步将算法B第2步中增加的库所加入到P1中。算法B通过不断地迭代,将与给定的目标库所相关的库所和变迁逐渐地加入到P1和T1中,由于网中的库所和变迁数目是有限的,当最后新加入到P1中的库所均为网中的初始库所时,考虑算法B的第1步:

为了讨论方便，设新加入到P1中的初始库所为pj,则根据输出矩阵的定义,m,执行算法B第4步,因为有新的库所加入到P1中,所以P0≠P1,令P0=P1,执行算法B第1步有:

从上边的计算可以看出新加入到P1中的初始库所为pj并没有改变T1的值，执行算法第二步和第三步之后，P1=P0，因此算法能够终止。综上所述，算法正确性得证。

1.2.2 算法B复杂性分析

考虑最坏情况，每次执行算法B第1步运算，向量T1中只有一个元素由0变为1而且一定至少有一个由0变为为1，否则下一次迭代时P0=P1，算法B结束，经过m次循环后，T1中的元素全为1，则算法循环第m+1次时，P0=P1，算法结束。所以在最坏情况下算法循环次数为m+1，总的算法复杂度为：O((m+1)(O(nm)+O(nm)+O(n)+O(n)))，即O(nm2)，其中n为网中库所结点的个数，m为变迁结点的个数。

2 实例计算

这里采用文献[6]中的实例。这个推理过程的Petri网模型如图1所示。

根据定义3.9，它对应的矩阵形式为：

利用前边给出的反向推理算法B进行迭代运算，结果如下：

第1次迭代：

第2次迭代：

第3次迭代：

由于第2、3次迭代结果相同，所以算法结束。最终结果为：

在图1中去除向量P1与T1中为“0”的元素以及相关的连接弧，得到与用户给出的目标库所p4关联的库所和变迁构成的一个子网，如图2所示。它是从整个Petri网中抽取的一个子网模型，可以在这个子网模型中处理与命题p4有关的问题，而不必在整个Petri网模型上进行。

3结语

通过对加权模糊Petri网模型和反向推理算法的研究,建立了加权模糊Petri网的关联Petri网推理模型。在此基础上提出了基于矩阵运算的反向推理算法,最后利用Visual C++6.0实现了该算法并通过实例对算法进行了检验,结果表明该算法具有解决复杂问题的并行推理能力,推理效率高,推理过程简单,容易实现。

摘要：通过对加权模糊Petri网模型和反向推理算法的研究,建立了加权模糊Petri网的关联Petri网推理模型。在此基础上,提出了基于矩阵运算的反向推理算法。通过实例对算法进行了检验,结果表明该算法具有解决复杂问题的并行推理能力、推理效率高、推理过程简单、容易实现。

关键词：加权模糊Petri网,关联Petri网,反向推理,子网

参考文献

[1]林闯,王鼎兴.使用Petri网T_不变量求解子句的逻辑推理[J].计算机学报,1996,19(10):762-767.

[2]Shyi-Ming Chen;Fuzzy backward reasoning using fuzzy Petrinets.Systems,Man and Cybernetics,Part B,IEEE Transactions on Volume 30,Issue 6,2000:846-856.

[3]H.Scarpelli;F.Comide;R.Yanger;A Reasoning Algorithm for High-Level Fuzzy Petri Nets.IEEE Trans.Fuzzy Systems,Vol.4,no.3,Aug.1996:282-294.

[4]鲍培明.模糊Petri网模型的反向推理算法[J].南京师范大学学报,2003,3(3):21-25.

[5]高梅梅,吴智铭.模糊推理Petri网及其在故障诊断中的应用[J].自动化学报,2000,26(3):677-680.

直觉区间值模糊推理的三I算法第6篇

Zadeh的模糊集理论是描述模糊现象的理论工具,它的创立使数学的应用范围从清晰现象扩展到模糊现象的领域,模糊集理论目前已广泛应用于自动控制、遥感技术、图象识别、信息处理、系统工程、人工智能、地震预测、医疗诊断、天气预报等众多科学技术领域。Atanassov提出的直觉模糊集[1]是对Zadeh模糊集理论的一种扩充和发展。直觉模糊集增加了一个新的属性参数:非隶属度函数,能够更加细腻地描述和刻画客观世界的模糊性本质,因而引起众多学者的研究和关注。在实际应用中,参数往往不是用一个数值,而是用一个数值的范围即区间值来表示更符合实际。因此,Atanassov又进一步提出区间值直觉模糊集[2,3](本文称之为“直觉区间值模糊集”)。

模糊推理是模糊控制的逻辑基础。然而通用的模糊推理CRI算法却缺乏严格的逻辑依据,近期问世的模糊推理全蕴涵三I算法有效地改进了CRI算法。本文在文献[4]的基础上,对直觉区间值模糊推理的三I算法进行了初步研究,由于一般形式的直觉区间值模糊推理均可以通过一定的处理方式转化为基本形式的MP或MT问题,所以本文仅就这两种最简单的推理形式进行了讨论。

2 直觉区间值模糊集和直觉区间值模糊三角模

定义2.1[2,3]定义:

则直觉区间值集合(D,≤)是一个完备格,<[1,1],[0,0]>与<[0,0],[1,1]>分别为最大元与最小元。

定义2.2[2,3]给定论域X的直觉区间值模糊集A,即指映射

将X上直觉区间值模糊集的全体记为I I V F S(X),即“Intuitionistic Interval-valued Fuzzy Sets”的意思。其中

定义2.3[2,3]设A,B∈IIVFS(X),规定序及运算如下:

定义2.4设二元函数T:D×D→D,若对D中任意元a,b,c,有

⑴交换性:T(a,b)=T(b,a),

⑵单调性:T(a,c)≤T(b,c),其中a≤b,

⑶结合性:T(T(a,b),c)=T(a,T(b,c)),

⑷单位元:T(a,<[1,1],[0,0]>)=a,

则称T为直觉区间值模糊三角模,简称三角模。

3 直觉区间值模糊蕴涵算子及其剩余原理

定义3.1设映射R:D×D→D,若满足性质

则称R为直觉区间值模糊蕴涵算子,简称蕴涵算子或蕴涵。

定义3.2称D上的三角模T满足剩余定理当且仅当,对于D中任意元素a,b,c,

其中RT表示由T生成的剩余蕴涵,定义为

4 直觉区间值模糊推理的MP三I算法

直觉区间值模糊推理MP三I算法的一些基本问题,包括定义、存在性和算法过程等。

设A与A*是论域X上的直觉区间值模糊集,B与B*是论域Y上的直觉区间值模糊集,则MP问题的推理形式为:

从而三I算法的基本原则可表述为:

定义4.1(MP问题的α-三I原则)设A∈IIVFS(X),B∈IIVFS(Y),且给定A*∈IIVFS(X),α∈D,则(3.1)中的B*,是IIVFS(Y)中对于任意的x∈X,y∈Y,使得

总成立的最小IIVF集。称B*为MP问题的α-三I解。特别,若α=<[1,1],[0,0]>,则称B*为MP问题的三I解。

本文主要将文献[4]中的有关结果推广到直觉区间值模糊环境中,首先给出MP问题的α-三I解存在性:

命题4.2设A∈IIVFS(X),B∈IIVFS(Y),且给定A*∈IIVFS(X),α∈D。若(1)和(2)中的蕴涵算子“→”以R表示,且满足

则MP问题存在α-三I解。

证明设Γ={B*∈IIVFS(Y)|B*满足(3.2)式}。1D为X上或Y上的IIVF集:

根据蕴涵算子的定义,易有

因此1D∈Γ,便知Γ非空。可设B*=∧{B*|B*∈Γ},下面证明B*满足(2)式,即对于任意的x∈X,y∈Y,有

注意到(3)式,可得

又因为对于任意的B*∈Γ,R(R(A(x),B(y)),R(A*(x),B*(y)))≥α,所以

故B*满足(2)式,并且是IIVFS(Y)中满足(2)式的最小IIVF集。从而MP问题存在α-三I解。

然后给出MP问题的α-三I算法:

命题4.3(MP问题的的α-三I算法)设T是D上满足剩余原理的三角模,RT是由T生成的剩余蕴涵。则由下式确定的B*是MP问题的α-三I解:

证明易知

又由于三角模的性质和剩余原理,可有

因而B*(y)满足(3.2)式。设E*(y)∈IIVFS(Y)也满足(3.2)式,即

便得

因此,B*(y)是IIVFS(Y)中满足(2)式的最小IIVF集,即B*(y)是MP问题的α-三I解。

当α=<[1,1],[0,0]>时,由三角模的定义,可得MP问题的三I解:

5 直觉区间值模糊推理的MT三I算法

设A与A*是论域X上的直觉区间值模糊集,B与B*是论域Y上的直觉区间值模糊集,则MT问题的推理形式为:

定义5.1(MT问题的α-三I原则)设A∈IIVFS(X),B∈IIVFS(Y),且给定B*∈IIVFS(Y),α∈D,则(4)中的A*,是IIVFS(X)中对于任意的x∈X,y∈Y,使得

总成立的最大IIVF集。称A*为MT问题的α-三I解。特别,若α=<[1,1],[0,0]>,则称A*为MT问题的三I解。

首先给出MT问题的α-三I解存在性:

命题5.2设A∈IIVFS(X),B∈IIVFS(Y),且给定B*∈IIVFS(Y),α∈D。若(4)和(5)中的蕴涵算子“→”以R表示,且满足

则MT问题存在α-三I解。

证明设Δ={A*∈IIVFS(X)|A*满足(5)式}。0D为X上或Y上的IIVF集:

根据蕴涵算子的性质,则有

因此0D∈Γ,便知Δ非空。可设=∨{A*|A*∈Δ},下面证明满足(5)式,即对于任意的x∈X,y∈Y,有

由(6)和(7),可得

又因为对于任意的A*∈Δ,R(R(A(x),B(y)),R(A*(x),B*(y)))≥α,所以

故满足(5)式,并且是IIVFS(X)中满足(5)式的最大IIVF集。从而IIVFMT问题存在α-三I解。

然后给出MT问题的α-三I算法:

命题5.3(MT的α-三I算法)设T是D上满足剩余原理的三角模,RT是由T生成的剩余蕴涵。则由下式确定的A*是MT问题的α-三I解:

证明易知

又由于三角模的性质和剩余原理,可有

因为RT是由T生成的剩余蕴涵,所以

从而A*(x)满足(5)式。设H*(x)∈IIVFS(X)也满足(5)式,即

则有

因此,A*(x)是IIVFS(X)中满足(5)式的最大IIVF集,即A*(x)是IIVFMT问题的α-三I解。

5 结束语

直觉模糊理论业已成为人们感兴趣的研究热点,自从直觉模糊集概念提出以来,国内外刊物的相关文献已经累计达百篇以上,而且还有逐步增加的趋势。直觉区间值模糊集将直觉模糊和区间值模糊两个理论紧密融合在一起,是求解不确定性问题、处理不完全信息、进行不精确推理的更为有效的数学方法,但是直觉区间值模糊集的相关文献并不多。本文初步研究了直觉区间值模糊推理的三I算法,分别给出MP问题和MT问题的三I解,填补了直觉区间值模糊理论在该领域的研究空白。

参考文献

[1]ATANASSOV K.Intuitionistic fuzzy sets[J].Fuzzy Setsand Systems,1986,20:87-96.

[2]ATANASSOV K.,Gargov G.Interval-valued intuitionisticfuzzy sets[J].Fuzzy Sets and Systems,1989,31:343-349.

[3]ATANASSOV K.Operations over interval-valued intuitionisticfuzzy sets[J].Fuzzy Sets and Systems,1994,64:159-174.

推理算法第7篇

关键词：贝叶斯网络,故障诊断,概率推理

贝叶斯网络(简称BN)是一种基于网络结构的有向图解描述,适用于表达和分析不确定和概率性事物,可从不完全或不确定的知识或信息中作出推理。它是基于概率分析、图论的一种不确定性知识表达和推理模型,是一种将因果知识和概率知识相结合的信息表示框架,如图1所示。

贝叶斯网络作为一种图形化的建模工具,具有一系列的优点:

(l)贝叶斯网络将有向无环图与概率理论有机结合,不但具有正式的概率理论基础,同时也具有更加直观的知识表示形式。

(2)贝叶斯网络与一般知识表示方法不同的是对于问题域的建模,当条件或行为等发生变化时,不用对模型进行修正。

(3)贝叶斯网络可以图形化表示随机变量间的联合概率,能够处理各种不确定信息。

(4)贝叶斯网络没有确定的输入或输出节点,节点之间是相互影响的,任何节点观测值的获取或者对于任何节点的干涉,都会对其它节点造成影响,并可以利用贝叶斯网络推理来进行估计和预测。

(5)贝叶斯网络的推理是贝叶斯概率理论的基础,不需要外界的任何推理机制,不但具有理论依据,而且将知识表示与知识推理结合起来,形成统一的整体。

1 贝叶斯网络推理算法

贝叶斯网络推理建立在对网络结构学习的基础上,而用于故障诊断的贝叶斯网络的结构是非常复杂的,并且由于其结构的复杂性致使故障诊断推理也非常复杂。所以需要在进行诊断推理之前对其网络结构进行简化。分簇搜索算法可以有效地完成这一使命。

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

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

搜索的过程如图2所示。

在网络结构简化后的基础上,对其进行诊断推理,会在一定程度上减少推理所用的时间,提高诊断效率;又因为图形得到简化,使推理难度降低,也在一定程度上提高了诊断推理的准确性。

研究人员提出了多种精确和近似推理算法,其中联合树(Junction Tree)算法,是目前计算速度最快,应用最广的贝叶斯网络精确推理算法。该算法最初是由Lauritzen and Spiegelhalter(1988)提出的,此后Jensen(1990)和Dawid(1992)又对其进行了改进。

目前通常采用Jensen提出的联合树算法[3],主要思想是将贝叶斯网络转化为联合树,然后通过定义在联合树上的消息传递过程来进行概率计算。联合树算法分为两种:Shafer-Shenoy算法和Hugin算法。本文将详细介绍基于Hugin消息传递方案的Hugin联合树算法。

联合树是一个无向树,树中的每一个节点称为团,由原贝叶斯网络中的一组随机变量构成,是无向图中最大的全连通子图。连接两个相邻团节点的称为分隔节点。

联合树构造过程如图3所示。

第一步:构造Moral图:将原贝叶斯网络中同一节点的父节点两两相连,即Marrying Parents,同时去掉每一条连接边的箭头。图4是图1所示贝叶斯网络的Moral图。

第二步:三角化图(Triangulating):对包含4个及以上个节点数的环,增加一条无向边将环中两个非相邻节点连接起来,完成对Moral图的三角化。图4所示的Moral图中不存在符合上述条件的无向环,所以不必再进行三角化。

第三步:区分团节点(Identifying Cliques):在三角化图中,确定团节点,每个团节点都是无向图的子图。图4中包含三个团节点ABC、BCE、BD。

第四步:建立联合树。建立的联合树必须包含所有团节点,交集作为连接两个团节点的分隔节点。图5是图1所示贝叶斯网络对应的联合树。

2 测试平台框架

设计的故障诊断系统提供了可视化的操作界面,通过选择要进行故障诊断的电子设备的类型和具体型号,根据故障现象判断故障的定位级别,选择模块电路对应的贝叶斯网络进行模式识别,最后得出故障诊断结果的相关信息。平台的各个功能函数用Visual C++实现。平台的整体框架如图6所示。

3 推理算法实现

运用分簇优化联合树算法,针对电子设备建立故障诊断系统,其构建代码如下:

由有向无环图(DAG)构建联合树

定义节点如下:

定义团如下:

定义分离集如下:

系统诊断推理流程图如图7所示。

4 结束语

随着电路复杂性和集成度的不断提高,电路的故障诊断变得越来越困难。通过对贝叶斯网络学习、贝叶斯网络推理及其在数据挖掘等方面应用的研究,可以有效地提高故障诊断的效率和故障覆盖率。基于贝叶斯网络决策模型的故障诊断方法在各个领域都得到了成功的应用。

参考文献

[1]Lauritzen S L,Spiegelhalter D J.Local Computations with Probabilities on Graphical Structures and their Applications to Expert Sys-tems[J].Journal of the Royal Statistical Society,1988,50(1570):157-224.

[2]刘启元.信度网及因果网理论与实现研究[D].重庆:重庆大学,2001.

[3]Lepar V,Shenoy P P.A comparison of Lauritzen and Spiegelhalter,Hugin and Shafer and Shenoy architectures for computing marginalsof probability distributions[Z].Uncertainty in Artificial Intelli-gence.1998,328-327.

[4]张少中,王秀坤,孙莹光.贝叶斯网络及其在决策支持系统中的应用[J].计算机工程,2004,30(10):90-95.

[5]李俭川,胡笃庆,秦国军,等.贝叶斯网络理论及其在设备故障诊断中的应用[J].中国机械工程,2003,14(10):896-900.

[6]胡春玲.贝叶斯网络的结构学习算法研究[D].合肥:合肥工业大,2006.

一种加权改进的D-S证据推理算法第8篇

智能交通系统中的信息来源多而复杂,如何有效甄别并处理大量交通信息成为智能交通研究者必须面临的研究课题。

传统交通信息的识别多依据传感器。随着多传感器技术的迅猛发展,各种面向应用背景的多传感器信息系统也随之大量涌现。在多传感器系统中,信息的表现形式多种多样的、容量巨大,信息之间的关系也复杂,并要求很高的处理速度。没有任何一种传感器可以保证在任何时候都能提供全面的、准确无误的信息,而且单纯依靠提高传感器本身的精度和容量来改善系统性能已经是比较困难的了。因此,需要一种方法将多个不必非常精确的传感器信息综合起来,通过它们之间的协调和性能互补,得出对环境或对象特征的全面、正确认识,以提高整个系统运行速度。它实际上是一种多元信息的融合处理技术,通过对来自不同传感器的信息进行分析和智能化合成,获得被测对象及其性质的最佳一致估计,从而产生比单一信息源更精确、更完全的估计和决策[1]。

智能交通信息特别是交通信息的外部特征在智能交通信息识别方面有重要作用。以现在的传感器的精度,仅靠一个传感器的报告提供的信息来对交通信息进行准确地识别是相当困难的。所以必须通过多传感器信息融合的方法来提高对目标的识别率。因此有关交通目标识别的信息融合方法的研究有极深远的战略意义。

D-S证据推理[3]作为Bayes估计的推广,可以更为有效和合理地处理不确定性推理的问题,具有融合后信任度上升、不确定性减小、信息量增加等优点。而将之用于信息融合,可以有效地处理传感器所得信息的不确定性。但是,由于其基本信度分配函数的获得需要人为地给定公式,所以主观性太强。可以考虑利用神经网络技术对传感器数据进行初级处理[3],得到D-S推理所需要的基本信度分配函数,然后用证据推理技术进行决策级的处理[4]。因为D-S推理不能处理具有矛盾冲突的证据,限制了它在实际中的应用。为处理矛盾证据,以便使D-S方法能够真正应用到实际中,本文对D-S证据推理的算法进行一些改进。

1 D-S的基本理论[2]

1.1 基本概念

(1) 识别框架设Θ是某个问题的可能答案(或关于答案的命题)的有限集,而且假设已知这些答案中(或关于答案的命题)有且只有一个是正确的,在此情形下,称Θ为识别框架。于是可以将对命题的研究转化为对集合的研究,当Θ有n个元素时,它所代表的空间大小为2Θ。

(2) 基本信度分配函数若集函数m:2Θ→[0,1]满足:

(m1) m(ϕ)=0

$(m 2) \sum_{A \subseteq 2^{Θ}} m (A) = 1$ ,则称m为框架Θ上的基本信度分配,m(A)称为A的基本信度值。

(3) 信度函数若集函数Bel:2Θ→[0,1]满足:

(b1) Bel(ϕ)=0

(b2) Bel(Θ)=1

(b3) ∀A1,A2,…,An∈2Θ(n为自然数)

$\begin{array}{l} B e l (\cup_{i = 1}^{n} A_{i}) \geq \sum_{i = 1}^{n} B e l (A_{i}) - \sum_{i < j}^{n} B e l (A_{i} \cap A_{j}) + \dots + \\ (- 1)^{n + 1} B e l (\cap_{i = 1}^{n} A_{i}) = \sum_{Ι \subseteq {1, 2, \dots, n}, Ι \neq ϕ} (- 1)^{| Ι | + 1} B e l (\underset{i \in Ι}{\cap} A_{i}) \end{array}$

则称Bel为框架Θ上的信度函数。可以证明如下定义的函数Bel是信度函数:

Bel(A)=∑B⊆Am(B)

(4) 似然函数Pl定义

$Ρ l (A) = 1 - B e l (A^{c}) = \sum_{B \cap A \neq ϕ} m (B)$

∀A∈2ΘAc=Θ-A

Pl(A)表示不否定A的信任程度,它是所有与A相交子集的基本信度分配函数m(B)(B∩A≠ϕ)的数值和。而似然性和信度的差U(A)=Pl(A)-Bel(A),表示了既不信任A也不信任Ac的一种度量,即表示对A不知道的程度。

在D-S证据理论中,由于缺少关于总概率的分配信息,所以不能确切地知道概率是如何分配给每个元素x∈U的,因而也就不可能计算与U的子集有关的概率P(A)。这样,可以采用区间(Bel(A),Pl(A))来描述A的不确定性。Bel(A)表示度量的下限,Pl(A)表示度量的上限,即:

Bel(A)≤P(A)≤Pl(A)

当(Bel(A),Pl(A))=1时,因为此时Bel(A)=1,说明对A信任;另一方面,由于Pl(A)=1,即Bel(Ac)=1-Pl(A)=1-1=0,说明对Ac不信任。所以(Bel(A),Pl(A))=(1,1)表示A为真。

1.2 D-S合成法则

信度函数Bel1(基本信度分配为m1)和信度函数Bel2(基本信度分配为m2)的合成信度函数Bel为:Bel=Bel1⊕Bel2,子集A的基本信度分配为:

$m (A) = Κ^{- 1} \sum_{A_{i} \cap B_{j} = A} m 1 (A_{i}) m 2 (B_{j})$

其中,K为正交化系数, $Κ = \sum_{A_{i} \cap B_{j} \neq ϕ} m 1 (A_{i}) m 2 (B_{j})$ ,K-1可作为各数据源矛盾程度的测度,K-1越大,证据之间矛盾越激烈。

1.3 D-S理论存在的一些问题

证据推理表示不确定问题的优势是显著的,但仍然存在一些问题。

首先其组合规则处理证据冲突方法引起许多问题,例如,下面的鲁棒性问题:

假设两条证据的基本概率赋值情况分别为:

${\begin{cases} m 1 (a) = 0.9 m 1 (b) = 0.1 \\ m 2 (b) = 0.1 m 2 (c) = 0.9 \end{cases}$

其中a、b、c是相互独立的焦元,组合结果为m1⊕m2(b)=1,事件b由置信度0.1变为必然确定事件,这显然不合理。首先,Yager给出三种解决方法:①把冲突的基本信任指派加入m(Θ)中;②假定m(ϕ)>0用来表示证据冲突,但是这样就破坏证据推理的封闭性,从而带来其他问题。③引入优先级的证据的组合[5]。

其次,证据推理的组合条件十分严格,Dempster组合规则要求两证据是条件独立的,而且要求辨别框架能够识别证据的相互作用,两条相关证据的融合问题[6]早已提出,Wu等学者对此有尝试性研究。

第三,证据组合会引起焦元“爆炸”,焦元以指数级数递增,造成计算量变大。这一问题已经有许多解决方法,如Tenceux提出了证据推理的神经网络实现;另外还有减少焦元的方法,Mahler提出的先验条件一致度具备距离的性质,可以作为删除焦元前后证据变化的量度,而用证据对焦元灵敏度的方法删除不必要证据,用信息的变化也可以减少证据数目。

第四,证据推理和贝叶斯推理的比较仍然是大家注视的焦点之一。

2 结合加权法的D-S证据推理的算法

为了能用证据推理处理矛盾证据,根据次协调理论中商讨逻辑[7]的思想,可以将矛盾相对弱化。为了达到这一目的,在实际应用中采取了对矛盾证据用均值加权法进行融合,将冲突弱化并将矛盾搁置,达到暂时的次协调,等下一条证据到来时可以继续融合下去,并得到比较理想的结果。

以上节中所举的鲁棒性问题为例,因为这时证据有冲突(证据m1倾向于判定为a,而证据m2倾向于判定为c,但两者都倾向于不判定为b),所以我们应用均值加权法对这两条证据进行融合,融合后的结果为:

$m 1 \oplus m 2 (a) = \frac{(m 1 (a) + m 2 (a))}{2} = 0.45$

$m 1 \oplus m 2 (b) = \frac{(m 1 (b) + m 2 (b))}{2} = 0.1$

$m 1 \oplus m 2 (c) = \frac{(m 1 (c) + m 2 (c))}{2} = 0.45$

从上面的结果可以看出,融合后的结果是比较合理的,而且将矛盾弱化后传播了下去,从而可以继续进行更进一步的融合。这时,如果有下一条证据过来,就可以再和它利用D-S证据理论融合,并根据结果作出比较准确的判定。

结合上面的讨论,结合加权法的D-S证据推理的算法处理有矛盾冲突的证据:

(1) 读入两条证据m1和m2;

(2) 计算冲突因子K-1,判断是否有矛盾冲突,如果是冲突证据,转(4);否则进行下一步;

(3) 按D-S融合规则对证据进行融合,转(5);

(4) 按均值加权法处理冲突证据 $m 1 \oplus m 2 (A) = \frac{(m 1 (A) + m 2 (A))}{2}$ ,A∈2Θ,进行下一步;

(5) 如果可以进行判定,做出判决,退出;如果不能够进行判定,读入下一条证据,转(2)。

3 仿真试验

3.1 对一组矛盾证据用改进的D-S方法进行融合

假设识别框架Θ=T={T1,T2,T3},把三个传感器对同一个目标的识别结果作为用D-S方法的三个基本信度分配函数,设这三个基本信度分配函数如表1所示,其它表中没有列出的2Θ中的集合上的信度分配为0。用D-S方法和改进的D-S方法对这三个传感器的数据进行融合。

首先用D-S方法对证据m1和m2进行融合:

$\begin{array}{l} Κ = \sum_{A \cap B \neq ϕ, A, B \subset 2^{Θ}} m_{1} (A) \cdot m_{2} (B) = m_{1} ({Τ_{1}}) \cdot m_{2} ({Τ_{1}}) + \\ m_{1} ({Τ_{2}}) \cdot m_{2} ({Τ_{2}}) + m_{1} ({Τ_{3}}) \cdot m_{2} ({Τ_{3}}) = 0 \end{array}$

由于K=0,所以K-1=∞,也就是说证据m1和m2是矛盾冲突的,不能按照D-S融合规则进行融合。于是,融合无法继续进行。

下面用前面讨论的与加权均值法相结合的改进的D-S算法对这三个证据进行融合。

由于证据m1和m2有矛盾冲突,所以用均值加权法对它们进行融合:

$\begin{array}{l} m ({Τ_{1}}) = m 1 \oplus m 2 ({Τ_{1}}) \\ = \frac{(m 1 ({Τ_{1}}) + m 2 ({Τ_{1}}))}{2} = 0.5 \end{array}$

$\begin{array}{l} m ({Τ_{2}}) = m 1 \oplus m 2 ({Τ_{2}}) \\ = \frac{(m 1 ({Τ_{2}}) + m 2 ({Τ_{2}}))}{2} = 0.25 \end{array}$

$\begin{array}{l} m ({Τ_{3}}) = m 1 \oplus m 2 ({Τ_{3}}) \\ = \frac{(m 1 ({Τ_{3}}) + m 2 ({Τ_{3}}))}{2} = 0.25 \end{array}$

然后,把证据m1和m2融合的结果m和第三条证据m3继续融合:

$\begin{array}{l} Κ = \sum_{A \cap B \neq ϕ, A, B \subset 2^{Θ}} m (A) \cdot m_{3} (B) = m ({Τ_{1}}) \cdot m_{3} ({Τ_{1}}) + \\ m ({Τ_{2}}) \cdot m_{3} ({Τ_{2}}) + m ({Τ_{3}}) \cdot m_{3} ({Τ_{3}}) \\ = 0.5 \times 0.95 + 0.25 \times 0.02 + 0.25 \times 0.03 = 0.4875 \end{array}$

$\begin{array}{l} m \oplus m_{3} ({Τ_{1}}) = Κ^{- 1} \cdot \sum_{A \cap B = {Τ_{1}}} m (A) m_{3} (B) \\ = Κ^{- 1} \cdot m ({Τ_{1}}) m_{3} ({Τ_{1}}) = 0.9744 \end{array}$

$\begin{array}{l} m \oplus m_{3} ({Τ_{2}}) = Κ^{- 1} \cdot \sum_{A \cap B = {Τ_{2}}} m (A) m_{3} (B) \\ = Κ^{- 1} \cdot m ({Τ_{2}}) m_{3} ({Τ_{2}}) = 0.0103 \end{array}$

$\begin{array}{l} m \oplus m_{3} ({Τ_{3}}) = Κ^{- 1} \cdot \sum_{A \cap B = {Τ_{3}}} m (A) m_{3} (B) \\ = Κ^{- 1} \cdot m ({Τ_{3}}) m_{3} ({Τ_{3}}) = 0.0153 \end{array}$

从上面的融合过程可以看出,用改进的D-S方法解决了证据m1和m2的矛盾冲突。均值加权法融合方式通过暂时搁置缓和矛盾冲突来有效处理具有矛盾冲突的证据,从而使得整个的融合过程能够继续下去,最终得到比较理想且合理的结果。

3.2 用改进的D-S方法对神经网络组的输出进行决策级融合

当噪声信号比较大时,特征级融合结果往往不能令人满意,所以需要进一步进行决策级的融合。在决策级一般需要对特征级的融合结果在进行空间(不同地方的传感器得到的数据)和时间(不同时刻传感器得到的数据)融合。下面利用D-S方法对大噪声的特征级识别结果进行空间和时间融合。

用神经网络组[8]对于加有500%高斯噪声的目标1的数据(即交通信息T1的待识别数据)进行识别(横轴为数据数量,纵轴为阈值),识别率为23.44%,识别结果图像如图1所示。

取τ=0.99作为判决门限,即:若网络的输出t={t1,t2,t3}中某一分量ti≥τ=0.99(i∈{1,2,3}),也就认为目标是交通信息Ti的可信度ti大于判决门限时,就可以判定目标是交通信息Ti了。

对神经网络组的输出结果利用D-S方法进行空间融合,识别率为35.83%,识别结果图像如图2所示。

经过对特征级融合结果进行空间融合后,识别率得到了很大提高,但是仍然不是很好,所以需要对空间融合结果进一步利用D-S方法进行时间融合。时间融合后,对目标为T1的识别率为51.00%,识别结果图像如图3所示。

可以看出,经过时间融合后,识别率又得到了很大的提高,取得了比较令人满意的识别效果。

4 结语

D-S方法在实际应用中,经常用于处理神经网络组内部对各网络输出进行融合的问题以及决策级融合中对神经网络组的输出进行空间和时间融合的问题。但由于D-S方法有不能处理矛盾证据的缺陷,限制了对它的进一步的应用。因此,本文给出了一种改进的D-S算法将矛盾弱化,它对矛盾证据的处理能得到较理想亦合理的结果。并通过仿真试验,证明改进的D-S算法采用均值加权法融合方式缓和矛盾冲突证据是有效的,使得整个的融合过程能够继续下去,并在实际中的应用中取得比较理想且合理的结果。

本文对如何处理矛盾证据做了一个有意义的尝试,但所给出的方法还不尽完美,对加权方式的进一步完善还待进一步研究。

参考文献

[1]刘同明,等.多传感器数据融合及应用[M].北京:国防工业出版社,1998.

[2]李宏.基于人工神经网络与证据理论相结合的信息融合空间点目标识别方法研究[J].信息与控制,1997,26(2):151-155.

[3]段新生.证据决策[M].北京:经济科学出版社,1996.

[4]Huadong Wu,Mel Siegel,Rainer Stiefe-lhagen,et al.Sensor FusionUsing Dempster-Shafer Theory[C]//IEEE Instrume-ntation andMeasurement Technology Confe-rence.Anchorage,AK,USA,May2002:21-23.

[5]Thierry Denceux.A Neural Network Class-ifier Based on Dempster-Shafer Theory[C].IEEE TRANSACTIONS ON SYSTEMS,MAN,AND CYBERNETICS-PART A:SYSTEMS AND HUMANS.MARCH2000,30(2):131-150.

[6]孙怀江,等.学习相关源证据[J].南京大学学报:自然科学,2001,36(2):154-158.

[7]桂起权,等.次协调逻辑与人工智能[M].武汉:武汉大学出版社,2002.

推理算法第9篇

关键词：双枝模糊逻辑,网络安全,攻击建模

随着网络攻击技术和安全防御技术的不断发展,攻击和防御已经成为网络安全的两个密切相关的侧面。不深入研究攻击理论和技术就不能做到知己知彼,也就无法有效地保护网络信息系统的安全。网络攻击研究的一个关键问题是对攻击的认识和描述。而攻击过程采用不同的攻击行为组成,不同的攻击行为又有不同的阶段和状态。攻击模型能对整个攻击过程进行结构化和形象化的描述,有助于分析和充分利用已知的攻击行为研究成果,进一步提高攻击检测和安全预警的效率。目前常用的几种攻击模型基本上都处于理论研究阶段。根据主要功能的不同可以将攻击模型分为两种,即适用于安全知识共享的模型和适用于攻击检测和安全预警的模型[1]。适用于知识共享的攻击模型主要有AttackTree[2,3]和AttackNet[4]模型,适用于攻击检测和安全预警的攻击模型主要有基于系统状态集合的攻击模型[5]。

以往在对网络攻击进行描述和评估时,一般都只针对网络漏洞与弱点,从网络攻击者的角度来进行研究,所研究的多是对攻击发生起积极作用的因素,对攻击起抑制作用的因素很少涉及。我们曾在文献[6]中,以双枝模糊决策理论[7,8]为基础对此做了初步的尝试,综合考虑了对网络攻击起促进和抑制作用的两种因素。同时,依据MYCIN置信度方法[9]提出了相应的攻击模型BBFPAN推理算法但是,该BBFPAN推理算法过于注重最终的结果,而忽视了整个推理过程中各个结点的状态变化情况,致使模型不能提到很好的安全预警功能。但就攻击模型而言,我们更多的时候关注的并不是本次网络攻击的最终结果,而是要发现网络系统当中最脆弱的结点。

为此本文将以双枝模糊逻辑理论[10,11,12]为理论基础,就攻击模型BBFPAN推理算法进行深入的探究。文献[10]在双枝模糊集的基础上,建立了双枝模糊逻辑的框架,对单枝模糊逻辑进行了合理的扩展。并从双枝糊命题入手,给出了双枝模糊逻辑的性质和双枝模糊逻辑公式,以及双枝模糊逻辑的析取范式、合取范式,为双枝模糊推理和双枝模糊控制奠定了基础。文献[11]在文献[10]的基础之上,从双枝模糊判断句出发,给出了双枝模糊推理的基本形式,讨论了基于模糊关系的双枝模糊推理和双枝模糊似然推理,以及条件语句的双枝模糊推理模型,为研究双枝模糊控制的前提和基础。文献[12]在已取得的研究成果基础之上,对双枝模糊逻辑的性质、逻辑公式、析取范式、合取范式进行了总结,进一步地完善了双枝模糊逻辑的推理框架,为最终实现双枝模糊控制的算法建立了完善的理论基础。

本文首先以文献[12]中介绍的双枝模糊逻辑推理的几种基本形式为依据,提出BBFPAN模型推理的基本规则。随后,根据BBFPAN模型的基本推理规则,并结合BBFPAN模型的定义,给出其相应基于双枝模糊逻辑的推理算法。在该推理算法中,预设起始库所集Pset、中间状态库所集Pg、可激发变迁集Tset,通过这三个集合元素的变化情况清晰地反映网络攻击的整个过程,以便发现那些网络系统中最危险的节点,为安全预警提供依据。

2 BBFPAN基本推理规则

文献[12]中介绍了双枝模糊逻辑推理的几种基本形式,本文在此基础之上,结合BBFPAN的定义提出以下BBFPAN模型推理的基本规则。

与规则,IFd1(θ1)andd2(θ2)and…anddn(θn)THEN dg(CF=μ),按照规则中命题(库所)对应网络攻击因素对网络攻击作用的不同,可以将与规则的推理分为以下三种形式:

(1)若θi∈[0,1],i=1,2,…,n,即pi所对应的因素均对网络攻击起促进作用,则:

(2)若θi∈[-1,0],i=1,2,…,n,即pi所对应的因素均对网络攻击起抑制作用,则:

(3)若θi∈[-1,1],i=1,2,…,n,即pi所对应的因素中,既有对网络攻击起促进作用的因素,也有起抑制作用的因素。我们假设:p1,p2,…,pk(1≤k<n)所对应的因素,对网络攻击起促进作用,则θh∈[0,1],h=1,2,…,k;pk+1,pk+2,…,pn所对应的因素,对网络攻击起抑制作用,则θl∈[-1,0],l=k+1,k+2,…,n。那么相应的BBFPAN模型,可以分解为攻击枝BBFPAN和防御枝BBFPAN,如图1所示。

在图1中,我们将pg库所一分为二,分处攻击枝和防御枝的双枝之上,故而将其表示为虚圈,以示区别。θg+表示了ph(h=1,2,…,k)所对应的对网络攻击起促进作用的因素,对最终状态pg的支持度;θg-表示了pl(l=k+1,k+2,…,n)所对应的对网络攻击起抑制作用的因素,对最终状态pg的支持度。

由式(1)和式(2),可以得到:

或规则,IFd1(θ1)ord2(θ2)or…ordn(θn)THEN dg(CF=μj)j=1,2,…,n,按照规则中命题(库所)对应网络攻击因素对网络攻击作用的不同,也可以将或规则的推理分为以下三种形式:

(1)若θi∈[0,1],i=1,2,…,n,即pi所对应的因素均对网络攻击起促进作用,则:

(2)若θi∈[-1,0],i=1,2,…,n,即pi所对应的因素均对网络攻击起抑制作用,则:

(3)若θi∈[-1,1],i=1,2,…,n,即pi所对应的因素中,既有对网络攻击起促进作用的因素,也有起抑制作用的因素。依照与规则中的假设,可以将相应的BBFPAN模型,分解为攻击枝BBFPAN和防御枝BBFPAN,如图2所示。

在图2中,将pg库所采用与图1中相类似的方法,表示为虚圈,以示区别。其中,θg+和θg-所表示的意义和与规则中的一致。

由式(5)和式(6),可以得到:

对于与、或两种规则第三种情况下,库所pg的可信度θg,可以分别依据式(3)、式(4)、式(7)、式(8)求得,计算公式如下:

3 BBFPAN模糊推理算法

在该模糊推理算法中,首先根据的iθ0取值情况,将库所集P分为起始库所集Pset和中间状态库所集Pg。然后根据起始库所集Pset,构造可激发变迁集Tset,并对tj按照与规则进行推理计算,并将推理计算结果存放在矩阵θg中。最后,再对中间状态库所集Pg中库所的输入变迁按照或规则进行推理计算,从而得到中间状态库所集Pg中每个库所所对应命题的可信度。

BBFPAN模糊推理算法如下:

Step1:分别构造起始库所集Pset和中间状态库所集Pg:若iθ0≠0,则pi∈Pset,否则,pi∈Pg。构造矩阵θg={θgij},θgij初值设为0,矩阵θg为n×m阶矩阵。构造变迁集Ts用以记录可激发变迁集Tset中已经激发的变迁,Ts=;

Step2:构造可激发变迁集Tset:若pi∈tj,pi∈Pset且tjTs,则tj∈Tset;

Step3:对pi∈Pset,tj∈Tset,对tj进行如下操作:

Step4:对pi∈Pg,对pi进行如下操作:

Step5:若Pg=则推理结束,否则转Step2。

4 结论

攻击模型是一个较新的研究领域,本文从攻击模型化的角度出发,再次将对网络攻击起积极和消极的正反两种因素进行综合考虑分析,首次将双枝模糊逻辑理论应用于攻击模型BBFPAN的推理计算,提出了BBFPAN模型推理的基本规则,并给出了一种基于双枝模糊逻辑的攻击模型BBFPAN模糊推理算法。

本研究丰富了攻击模型的分析研究方法,同时也扩展了双枝模糊逻辑理论的研究领域。

参考文献

[1]陈春霞,黄皓.攻击模型的分析与研究.计算机应用研究,2005;(7):115—118

[2] Moore A P,Tllison R,Linger R C.Attack modeling for informationsecurity and survivability.CMU/SEI-2001-TN-001,2001