基于混合編碼遺傳算法的證據網節點可靠性評估

陳志剛, 李　賢, 井沛良, 徐世友

(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。