陈志刚, 李　贤, 井沛良, 徐世友

(1. 中南大学软件学院, 湖南 长沙 410075;

2. 中南大学信息科学与工程学院, 湖南 长沙 410083;

3. 国防科学技术大学自动目标识别重点实验室, 湖南 长沙 410073)



基于混合编码遗传算法的证据网节点可靠性评估

陈志刚1,2, 李贤2, 井沛良3, 徐世友3

(1. 中南大学软件学院, 湖南 长沙 410075;

2. 中南大学信息科学与工程学院, 湖南 长沙 410083;

3. 国防科学技术大学自动目标识别重点实验室, 湖南 长沙 410073)

摘要：证据网是一种基于D -S(Demspter-Shafer)理论层次化推广的推理模型,和D -S理论一样，当证据网中传感器节点不可靠时需要进行折扣(可靠性)处理。由于证据网是一种多层次的节点信息融合,折扣在不同融合层次传感器上,影响不同层次上的冲突,所以折扣的设置需全局考虑冲突情况。已有的可靠性评估方法是D -S理论中的评估,这些方法并不能保证在融合中全局的冲突最小,针对这一问题提出一种以减小全局冲突为目标使用混合编码遗传算法进行可靠性评估的方法。在仿真实验中通过与已有的可靠性评估方法进行比较，证明了该方法更能减小全局冲突,获得更好的结果。

关键词：证据网; 混合编码遗传算法; 证据折扣; 全局冲突

0引言

在经典的D -S(Demspter-Shafer)理论中,认为传感器对识别问题完全可靠,它们对各个目标的基本信任分配通过D -S组合规则进行融合。然而在实际的情况中,传感器的可靠性会受到噪声、杂波、电磁环境、传感器本身的测量精度、天气环境等因素的影响,无法保证传感器完全可靠。为了避免通过融合不可靠的信息产生的误差以及冲突,有效地利用D -S组合规则,在基于信任分配的融合中必须考虑传感器的可靠性。

目前,基于D -S理论的传感器可靠性评估主要分为两类方法,一类是评价传感器的一阶不确定性的相对稳定性,如识别概率或者虚警率视为传感器的可靠性[1];另一类是根据预测值的精度进行评估。文献[2]就是一种利用识别率进行可靠性评估的方法。文献[3]所提方法就是利用预测值精度来进行可靠性评估。另一种分类就是将传感器评估分为静态和动态两种,静态的评估是指传感器的可靠性事先已经得出,实测时可靠性无法动态变化。动态的评估是指可靠性在实测的时候动态得出。文献[4-5]是一种利用距离度量来静态评估传感器可靠性的方法。文献[6]是一种利用大多数传感器的信息一致性来动态进行可靠性评估的方法。文献[7]提出了一种上下文折扣的动态评估可靠性方法。

目前的方法都只考虑单一层次的传感器可靠性评估,未考虑多层次系统中的传感器可靠性评估问题。多层次系统和单一层次系统最主要的区别在:①系统中传感器是否识别不同信息;②传感器之间是否存在映射关系。文献[1-3,7]都是根据单一传感器的测量进行可靠性评估,不具有任何层次性的概念,文献[4-6]可以根据多个传感器的测量进行可靠性评估,但是要求多个传感器识别的信息保持一致,这也不是一种多层次的评估方法。这些方法在单一层次可靠性评估中比较合理,但由于多层次系统中的映射关系,并不能保证这种合理性传递到其他层次,在其他层次上可能会产生更大的冲突。在多层次系统中如何评估可靠性,使得这个可靠性对不同层次上的融合都是比较合理的,降低整个系统的全局冲突是本文着重研究的问题。

本文主要工作及创新如下:

(1) 建立了基于证据网的机载多传感器融合模型,并用联合信任推理方法进行推理。

(2) 通过基于格雷码和浮点数编码的混合编码、适应度函数构造、选择概率算式、混合编码的变异交叉,构造了一个用来可靠性评估的混合编码遗传算法。

(3) 此算法以减小全局冲突为目标进行传感器可靠性评估,并与一些已有传感器可靠性评估方法比较,证明本文方法获得的评估结果比其他方法更能减小全局冲突,获得更好的结果。

1证据网构建、推理方法和可靠性评估

1.1证据网络

1994年,文献[8]最早提出了证据网(evidential network, EN)的概念,这是一种图论与证据理论结合的有向无环图模型[9],将定性的网络结构知识与定量的网络参数有机结合,表达了原因到结果的影响。

文献[10]通过构建因果图,采用信度分配构建证据网络,用扩展和边缘化操作来进行推理过程,并用以解决满意度评估。另外，在目标威胁度评估[11]、机器人的智能控制[12]、病人诊断护理[13]等方面证据网络也得到有效应用。

1.2机载多传感器信息融合证据网模型

先进的现代战机一般具有强大的多源信息的综合处理能力,可以通过协作式与非协作式传感器进行目标敌我属性综合识别,在这种综合识别中属性信息的融合是一个关键技术。使用证据网进行属性信息融合有以下优点:

(1) 信度分配不再是点函数而是一种集合函数,能表示对某个区间信度分配;

(2) 可以准确表达因为知识缺乏产生的无知;

(3) 不需要设置先验概率,容易建模,并且可以有效利用合成规则组合多个证据;

(4) 随着证据的不断增加,可行解空间不断收敛,最终可以得出一致结果。

根据以上分析,通过证据网进行机载多传感器属性信息融合可以有不错的效果。

综合识别中最主要的是进行敌我识别,配备的敌我识别类传感器以及对应的信息识别能力如表1所示。

表1　敌我识别类传感器

除了敌我识别的传感器,还包括一些获取目标其他信息如目标大小、目标辐射源类型等的传感器,具体如表2所示。

表2　其他类传感器

上述分析可以看出在证据网络中有两个核心节点,分别为目标类型(Target Type)、敌我属性(Foe-Ally)。因此本文采用识别中心——信源终端的构造方式,分别以目标类型、敌我属性作为两个识别中心,构建各自的证据网络,然后将两个证据网络合并,进行独立性分析,最后针对具体情况调整边的方向。所建模型如图1所示,这个模型具备多层次性,首先传感器识别信息并不相同,其次它们之间存在表示映射关系的边。网络中设有5个传感器,分别为IFF、DE、HRRP、IR、ESM,其中HRRP、IR的辨识框架为Θ1={J10,F15,F16,θType},其中θType表示未知类型,ESM的辨识框架为Θ2={1473,AGP68,AGP63,θESM},其中θESM表示未知类型,DE的辨识框架为Θ2={Foe,Unknown},IFF的辨识框架为Θ3={Unknown,Ally},而Target Type节点的辨识框架为Θ4={J10,F15,F16,θType},Foe-Ally节点的辨识框架为Θ5={Foe, Unknown, Ally}。

图1　证据网模型

1.3推理方法

在证据网中主要的推理方法有:条件信任证据网推理、联合信任证据网推理、信度规则证据网推理[14-15]。联合信任证据网推理表达简明有效,并且是通过严密的数学推导过程,实现信息在证据网络中的有效传递,故联合信任证据网推理将作为本文的推理方法。

在联合信任证据网推理中,信息主要通过两种操作进行传递:扩张(Extension)操作、边缘化(Marginalization)操作,以一例来说明。

某一融合判决假设有F,G,H3个辨识框架,变量G和F,H之间的联合信任测度为mF-G,mG-H,结构如图2所示。感兴趣变量在框架G内,G的信任测度表示为

(1)

式中,扩张和边缘化分别用“↑”“↓”表示。

图2　基于联合信任函数的证据网络结构

图1各节点间的联合信任如表3所示。

表3　联合信任表

1.4冲突最小化可靠性评估

尽管一个传感器的可靠性是由多种因素所影响的,但在证据理论中,可靠性可以表达如下:

设θ为识别框架,所谓识别框架就是一个论域集合,集合内的子集称为焦元,焦元间是互不相容的,m(A)为焦元A的基本概率赋值,传感器的可靠性因子为α,根据文献[7],引入传感器可靠性后的基本概率赋值公式如下:

(2)

从式(2)可以看出,折扣运算将那部分可靠的信任留在焦元中,将折扣所剩余的信任赋予全集θ,表示未知。事实上证据网络中的每个节点也是一个传感器,也可以进行可靠性处理,而这些节点上的可靠性又和节点间基本概率赋值融合时产生的冲突有着直接的关系。

设l为融合节点,n为在此融合节点处融合的子节点个数,不妨将这n个节点从1到n进行编号,a和b表示这n个子节点中两个不相等节点,Ka b为a和b两节点融合时所产生的冲突,fl(n)表示l节点处所产生的冲突,可表示为

(3)

(4)

对于整个证据网络而言,对同一目标当有多个节点信息依次传递和融合时,整个证据网络所产生的冲突可如下描述:设L为融合节点集合,即l∈L,Fconflict(l,n)表示整个证据网络的冲突,可表示为

(5)

此时对可靠性的评估问题,就转化为寻找最优D集合使得Fconflict(l,n)较小甚至最小的问题,显然这是一个不确定性多项式(nondeterministic polynomial, NP)的多值优化问题,遗传算法是处理这类优化问题的典型方法,有着全局搜索、收敛较快等优点[17],本文将采用遗传算法来解决证据网中可靠性评估的问题。

2可靠性评估的混合编码遗传算法

为了提高算法的搜索和收敛的性能,本文采用一种格雷编码和浮点编码同时编码的方案。格雷码的局部搜索能力强,且不存在Hamming悬岸问题[18-19],而浮点编码全局搜索能力强,可以用浮点编码先进行大范围搜索,当适应度到达一定的阈值后再进行格雷码搜索,这样既能较快收敛又能增强局部收敛能力,主要的操作如图3所示。下面简单介绍编码、适应度函数和选择方法,详细介绍根据不同的编码提出的交叉、变异方法。

图3　混合编码遗传算法流程图

2.1染色体编码

在本文中一条染色体由多个基因组成,一个基因表示一个传感器的可靠性。设c表示一条染色体,αi为传感器i的可靠性,本文一共有5个传感器,那么染色体表示为c=α1α2…α5,其中的基因αi需根据适应度函数的值来选择格雷编码[18-19]和浮点数编码[20]。

2.2适应度函数

本文采用总体冲突函数作为评价染色体优劣的函数,即

(6)

显然这个函数是一个多维空间内的单值、连续、非负函数,满足适应度函数的选取要求。编码选取的适应度阈值设置为3。

2.3选择

选择操作根据适应度来计算,和编码方式无关。设Fi表示第i个染色体的适应度,m表示种群的数量,那么第i个染色体被选中的概率算式如下:

(7)

2.4交叉

2.4.1格雷编码的交叉

当染色体适应度大于等于一个阈值η时将采用格雷编码,根据格雷编码可以有效计算基因间的海明距离的特点提出一种基于格雷编码海明距离的交叉操作。

设两个染色体中同位置的两个基因为pi和qi,其海明距离为Ui=|pi-qi|,基因的最大海明距离为Umax,这两个染色体的适应度分别为Ffitness(p)和Ffitness(q),r为调节系数,那么这个位置的交叉概率为

(8)

2.4.2浮点数编码的交叉

(9)

2.5变异

2.5.1格雷编码的变异

2.5.2浮点数编码的变异

(10)

式中,t随机的为0或1中间的一个数；a为调节系数；Ffitness为这条染色体的适应度。通过此种变异,当适应度大时搜索空间变大,适应度小时搜索空间变小,有利于进行小范围的局部搜索。

2.6终止过程

当一批证据来到后,训练结束条件为

(11)

式中，C是染色体集合；|C|是集合C的基；c是C中的一个元素；K为染色体个数阈值,其取值为种群数的一半,意味着达到适应度的种群个数为起始种群的一半即可；P=5为适应度阈值,意味着融合节点产生的冲突要小于0.2。当不满足式(11)时应满足m>M,其中m为迭代次数,M为迭代次数阈值,其取值为1 500。

3仿真实验与结果分析

将直接Dempster融合方案(D)、文献[4]中的融合方案(D1),文献[6]中的融合方案(D2),文献[21]中的融合方案(D3),经典二进制编码遗传算法评估可靠性融合方案(GD),本文的混合遗传算法评估可靠性融合方案(CD)进行对比。由于Foe-Ally节点是顶端节点,D1和D3方法无法对中间节点评估可靠性,为了保证对比的有效性,本文实验中中间节点都不计算可靠性, D3方案需要各个传感器的混淆矩阵,表4~表8给出了5个传感器的混淆矩阵。

表4　DE传感器的混淆矩阵

表5　IFF传感器的混淆矩阵

表6　HRRP传感器的混淆矩阵

表7　IR传感器的混淆矩阵

表8　ESM传感器的混淆矩阵

整个仿真过程采用蒙特卡罗仿真,对同一目标输入的证据为5个,每个传感器1个,仿真次数为20次。首先通过输入不同的种群数量比较GD和CD方法的收敛时间,其中GD方法交叉、变异与本文中的格雷码类似,得出如图4的结果。

图4　初始种群与训练时间的关系

从图4可以看出达到收敛条件时,CD方法比GD方法所耗时间要少,在种群数为50时,时间相差130 s。随着种群数量的增加CD和GD方法时间都是大幅增加,但GD方法时间增加更多。因为CD方法采用混合编码,浮点数编码可以加速CD方法的收敛速度。

为了分析冲突的变化,可以计算每次证据输入时不同方法所得出的全局冲突。由于是蒙特卡罗仿真,那么这个全局冲突是20次的平均值,从图5中可以看到,第一次由于未进行可靠性计算,所有方法冲突差别不大,随后一开始并不是GD冲突最小,而是D2方法,这是因为由于证据少,样本少,GD所得可靠性并不合适,而D2方法却能保证每次在中间节点Target Type处冲突最小,尽管不能保证全局冲突最小。到了第5个证据输入时GD方法的全局冲突已经明显是所有方法中最小的了,同时CD方法全局冲突也较小。

图5　各方法全局冲突比对

以Target Type和Foe-Ally作为最后进行评估的节点,通过计算可以得到图6中的结果。

因为Target Type只是一个中间层次节点,对于中间层次节点，从图5中看出，CD并不是最优的,因为CD是一种全局方法,考虑的是全局的冲突最小,同时GD情况也一致,但GD的平均识别率要低于CD,D2方法是一种基于局部冲突最小化的方法,对于Target Type来说效果必然最好；同时，D1和D3方法效果甚至还不如D方法,因为虽然D1和D3能够较好评估出传感器的可靠性,但这个可靠性对于融合来说未必最优,反而可能引起更多的冲突。图7给出了各方法在Foe-Ally节点的比对结果。

图6　各方法在Target Type节点比对

从图7可以看出,从结果比对看CD算法有着良好效果,这是因为CD算法是一种全局评估,从中间节点Target Type过来的信息是经过优化的,而其他算法都无法优化中间节点过来的信息,同时GD也取得了较好的结果,但平均识别率仍然低于CD。

图7　各方法在Foe-Ally节点比对

4结论

本文以证据网融合为基础,提出了一种通过混合编码遗传算法来评估节点可靠性的方法。这种方法是以证据网融合过程中冲突最小化作为评价函数来选取可靠性序列,针对证据网融合具有网络化、层次化的特点,本文方法能提供一种全局化可靠性评估,通过与一些现存的可靠性计算方法比较，证明了此方法能获得更好的结果。

参考文献：

[1] Cooke R M.Expertsinuncertainty[M]. New York: Oxford University Press, 1991.

[2] David M, Benjamin Q. General correction mechanisms for weakening or reinforcing belief functions[C]∥Proc.ofthe9thInternationalConferenceonInformationFusion, 2006: 1-7.

[3] Galina L R, Vincent N. Reliability in information fusion: literature survey[C]∥Proc.ofthe7thInternationalConferenceonInformationFusion, 2004:1158-1165.

[4] Guo H W, Shi W K, Deng Y. Evaluating sensor reliability in classification problems based on evidence theory[J].IEEETrans.onSystems,ManandCybernetics-PartB:Cybernetics, 2006, 36(5): 970-981.

[5] Jousselme A L, Grenier D, Bosse E. A new distance between two bodies of evidence[J].InformationFusion,2001,2(2):91-101.

[6] Fu Y W, Jia Y P, Yang W, et al. Sensor dynamic reliability evaluation and evidence discount[J].SystemsEngineeringandElectronics, 2012, 34(1): 212-216.(付耀文, 贾宇平, 杨威, 等. 传感器动态可靠性评估与证据折扣[J].系统工程与电子技术, 2012, 34(1): 212-216.)

[7] David M, Benjamin Q, Thierry D. Refined modeling of sensor reliability in the belief function framework using contextual discounting[J].InformationFusion, 2008,9(2): 246-258.

[8] Xu H, Smets P. Reasoning in evidential networks with conditional belief functions[J].InternationalJournalofApproximateReasoning, 1996, 14(2/3): 155-185.

[9] Attoh-Okine N O. Aggregating evidence in pavement management decision-making using belief functions and qualitative Markov tree[J].IEEETrans.onSystems,ManandCybernetics:PartC-ApplicationsandReviews,2002,32(3):243-251.

[10] Srivastava R P, Liu L. Applications of belief functions in business decisions: a review[J].InformationSystemsFrontiers, 2003, 5(4): 359-378.

[11] Benavoli A, Ristic B, Farina A, et al. An application of evidential networks to threat assessment[J].IEEETrans.onAerospaceandElectronicSystems, 2009, 45(2): 620-639.

[12] Hong X, Nugent C, Mulvenna M, et al. Evidential fusion of sensor data for activity recognition in smart homes[J].PervasiveandMobileComputing, 2009, 5(3): 236-252.

[13] Lee H, Choi J S, Elmasri R. A static evidential network for context reasoning in home-based care[J].IEEETrans.onSystems,ManandCybernetics:PartA-SystemsandHumans, 2010, 40(6):1232-1243.

[14] Jiang J. Modeling, reasoning and learning approach to evidential network[D]. Changsha: National University of Defense Technology,2011.(姜江.证据网络建模、推理及学习方法研究[D].长沙:国防科学技术大学,2011.)

[15] Smets P. Belief fucntions: the disjunctive rule of combination and the generalized Bayesian theorem[J].InternationalJournalofApproximateReasoning, 1993,9(1): 1-35.

[16] Elouedi Z, Mellouli K, Smet P. Assessing sensor reliability for multi-sensor data fusion within the transferable belief model[J].IEEETrans.onSystem,Man,andCybernetics-PartB:Cybernetics, 2004, 34(1): 782-787.

[17] Chien H K, Shu F W. Precast production scheduling using multi-objective genetic algorithms[J].ExpertSystemswithApplications, 2011, 38(7): 8293-8302.

[18] Lin H, Ma Z F, Yao C H, et al. 3D measurement technology based on binocular vision using a combination of gray code and phase-shift structured light[J].ChineseJournalofElectronics,2013,41(1):24-28.(林焕,马志锋,姚春海,等.基于格雷码-相移的双目三维测量方法研究[J].电子学报,2013,41(1):24-28.)

[19] Sun H J, Wang X M, Lu X B, et al. An algorithm of test pattern assignment of circuit BIST based on gray code[J].ChineseJournalofComputers, 2011, 34(9): 1697-1704.(孙海珺, 王宣明, 卢晓博, 等.一种基于格雷码的电路自测试序列分配算法[J].计算机学报, 2011, 34(9): 1697-1704.)

[20] Fan H, Meng Q F, Zhang Y Y. Matching pursuit via genetic algorithm based on hybrid coding[J].JournalofXi’anJiaotongUniversity,2005,30(3):295-299.(范虹,孟庆丰,张优云.用混合编码遗传算法实现匹配追踪算法[J].西安交通大学学报,2005,30(3):295-299.)

[21] Yang W, Jia Y P, Fu Y W. Research on fusion recognition algorithm for different reliable sensors based on the belief function theory[J].SignalProcessing,2009,25(11):1766-1770.(杨威,贾宇平,付耀文.传感器可靠性相异的信任函数理论融合识别算法研究[J].信号处理,2009,25(11):1766-1770.)

陈志刚(1964-),男,博士研究生导师,博士,主要研究方向为信息融合、传感器分布式网络。

E-mail:czg@csu.edu.cn

李贤(1982-),男,博士研究生,主要研究方向为融合识别、数据挖掘。

E-mail:lx20010@gmail.com

井沛良(1987-),男,博士研究生,主要研究方向为目标跟踪、信息融合。

E-mail:jingpeiliang@nudt.edu.cn

徐世友(1978-),男,副教授,博士,主要研究方向为雷达目标识别与信息融合。

E-mail:xsy2000@163.com

网络优先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20150316.1417.001.html

Reliability evaluating of evidential network nodes with

hybrid-code genetic algorithm

CHEN Zhi-gang1,2, LI Xian2, JING Pei-liang3, XU Shi-you3

(1.SchoolofSoftware,CentralSouthUniversity,Changsha410075,China; 2.SchoolofInformationScienceand

Engineering,CentralSouthUniversity,Changsha410083,China; 3.ScienceandTechnologyonAutomatic

TargetRecognitionLaboratory,NationalUniversityofDefenseTechnology,Changsha410073,China)

Abstract:Evidential Network is a reasoning model based on extending the Demspter-Shafer(D -S) theory, when the sensors node are unreliable, discounts(reliability) should be set at the nodes as in the D -S theory. Because the evidential network fuses the multiple echelons of information of nodes, the discounts of sensors are at the different fusion levels and take effect at the different fusion levels, the whole conflict should be taken into consideration when the discounts are set up. The existing ways of evaluating the reliability are used in the D -S theory, and they cannot ensure the minimum of the whole conflict when taking the fusing in the evidential network. In order to resolve the problem, the hybrid-code genetic algorithm is proposed to evaluate the reliability of evidential network nodes, with the aim of reducing the whole conflict. Compared with some other algorithms, the results prove that the proposed algorithm takes some advantages in reducing the conflict and finding a better result.

Keywords:evidential network; hybrid-code genetic algorithm; evidence discount; whole situation conflict

作者简介：

中图分类号：TB 114

文献标志码：A

DOI:10.3969/j.issn.1001-506X.2015.07.35

基金项目：国家自然科学基金(61309001, 61379057)；高等学校博士学科点专项科研基金(优先发展领域)(20120162130008)资助课题

收稿日期：2014-07-09；修回日期：2014-12-18；网络优先出版日期：2015-03-16。