置信規則庫參數訓練的布谷鳥搜索算法

李 敏,傅仰耿,劉莞玲,吳英杰

(福州大學 數學與計算機科學學院,福州 350116)

1 引 言

基于證據推理算法的置信規則庫推理方法(belief rule-base inference methodology using the evidence reasoning approach,RIMER)是在Dempster-Shafer理論[1,2]、決策理論[3]、模糊理論[4]和傳統IF-THEN規則[5]的基礎上發展起來的,能有效處理帶有含糊(vagueness)或不確定性、不完整的數據[6].目前,該方法已經成功應用在工程系統的安全評估[7]、輸油管道的檢漏[8]和石墨成分的檢測[9]等領域.

針對BRB系統的參數優化問題,傳統的方法主要有:近似線性法、Zoutendijk可行方向法以及Wolfe簡約梯度法等[10],但這些傳統的方法存在實現復雜、收斂精度低等缺陷.后來,Yang等[9]首次提出了BRB的參數優化模型.而后專家們在此方向上相繼提出了基于梯度下降算法[11]、基于變速粒子群算法[12]、基于差分進化算法[13]和基于改進粒子群算法[14]等的參數訓練模型.這些參數訓練模型已經能有效解決一些由于參數設置不合理導致的推理準確性低的問題,但是現有的這些方法仍然存在一些不足,如系統實現過于復雜、收斂效率不佳以及易陷入局部最優等.因此,為了使BRB系統具有更好的推理效率和推理準確性,研究更加通用和有效的置信規則庫參數學習方法是很有必要的.

鑒于此,本文結合布谷鳥搜索 (CS) 算法[15],提出了基于自適應擾動布谷鳥搜索算法的置信規則庫參數優化方法.該算法的本質是利用布谷鳥搜索算法求解優化模型,但標準的布谷鳥搜索算法魯棒性不佳,易早熟,易陷入局部最優解.為此本文引入自適應擾動策略,增加算法中每一代個體之間的差異性,并控制迭代過程中個體的活動范圍,從而優化種群的進化過程并得到更優的精度.在實驗分析中,本文首先通過擬合多極值函數的實驗,與其他現有方法進行比較,從而驗證自適應擾動布谷鳥搜索算法能夠取得更好的收斂精度與收斂速度;最后將該算法應用于輸油管道檢漏的實例中,并與其他現有的方法進行比較,進一步驗證本文改進的方法對實際問題具有良好的適用性.

2 置信規則庫推理方法與問題提出

2.1 BRB的表示

BRB中的置信規則在IF-THEN規則的基礎上增加了分布式置信框架,并為前件屬性和規則都設置相應的權重,下式給出第k條規則的表示:

(1)

Witharuleweightθkandattributeweightδ1,k,δ2,k,…,δTk,k

2.2 RIMER方法的推理機制

2.2.1 激活權重的計算

(2)

對于第k條規則激活權重的求解方法為:

(3)

2.2.2 修正置信度

(4)

2.2.3 合成激活規則

根據ER算法,屬性的可信度可以通過每條規則的置信度與屬性權重算出,具體公式如下:

mn,i=ωiβn,i

(5)

(6)

(7)

(8)

上式中n=1,…,N,i=1,…,L.

在求得基本可信度之后,運用ER算法的解析式[17]就能合成全部的基本屬性,具體公式為:

(9)

(10)

(11)

(12)

接著,可算出新合成屬性的結果評價等級置信度,其具體公式為:

(13)

(14)

式中βn和βH分別表示評價類型Dn對應的置信度和不完備信息的置信度.

最后,如果要求輸出的結果是簡單的數值類型時,可以計算出置信規則庫系統的期望效用值.假設等級效用值為μ={μ1,μ2,…,μN},則BRB系統的效用值計算公式如下:

(15)

2.3 BRB的參數訓練模型

Yang等提出的BRB參數學習的模型[9]如圖1所示.

圖1 BRB參數訓練模型Fig.1 Model of BRB parameter training

min{ξ(P)}
s.t.A(P)=0,B(P)≥0

(16)

Yang的BRB參數訓練模型中,每個參數的約束條件如下:

1)BRB中結果評價等級的置信度取值范圍為[0,1],第k條規則中的第n個結果評價等級對應置信度應符合下式的限制范圍:

0≤βn,k≤1,n=1,2,…,N;k=1,2,…,L

(17)

2)假設第k條規則的輸入信息具有完整性,那么置信度的總和為1.

(18)

3)第k條規則的貢獻值θk進行歸一化后,θk的值應該在0到1之間.

0≤θk≤1,k=1,2,…,L

(19)

(20)

同理,BRB系統的仿真輸出可表示為:

(21)

則BRB參數優化模型對應的目標函數是:

(22)

置信規則庫的推理輸出和真實輸出之間的偏差通常可以用均方差進行衡量,由此可得目標函數為:

(23)

2.4 問題提出

通過對置信規則庫推理過程的研究可以發現,BRB系統的參數直接影響著最終的推理精度.但現有的BRB系統的參數學習方法仍然存在一些不足.例如:Yang等[9]基于使用Matlab中FMINCON函數的參數學習方法,由于受限于FMINCON函數,不僅求解的效率慢,而且準確度較低;常瑞等[16]采用的將梯度下降法與二分法相結合的參數優化方法只對BRB中的部分參數做局部優化.吳偉昆等[11]在此基礎上進行進一步研究,提出了基于加速梯度求法的置信規則庫參數學習方法,雖然對算法的運行效率與精度都取得了一定的改進,但改進過程中也增加了算法實現的復雜度.而后王韓杰等[13]在差分進化算法的基礎上加入專家干預,提出了專家干預下的置信規則庫參數學習方法.蘇群等[12]在粒子群算法的基礎上通過加入粒子的變速操作,提出了基于變速粒子群算法的置信規則庫參數學習方法.但是這兩種涉及群智能算法的改進,在收斂效率和收斂精度方面還不夠理想,當實際問題對于效率與精度有更高的要求時,這些算法無法滿足需要.因此,本文提出基于布谷鳥搜索算法[15]的參數訓練方法來對BRB的內部參數進行訓練,最后在此基礎上構建BRB系統,從而提升BRB系統的推理效率與推理準確性.

3 基于自適應擾動布谷鳥搜索算法的參數訓練

3.1 自適應擾動的布谷鳥算法

布谷鳥搜索(CS)算法是劍橋大學Yang和S.Deb受到布谷鳥育雛和尋巢的習性啟發而提出的一種群智能算法[15].布谷鳥在育雛時具有寄生育雛(Brood Parasitism)的習性,而在移動中則具有萊維飛行(Levy flight)的特征,該算法通過對這兩種行為的模擬來有效地求解最優化問題[18].

標準的布谷鳥搜索算法采用飛行與遺棄并尋找新巢這兩種方式對個體進行更新:

1)通過Levy flight對當前個體進行更新,具體公式為:

(24)

L(λ)～u=t-λ,1<λ≤3

(25)

在Levy flight隨機取值后,可將當前個體中最優的個體作為參考值進行移動,最終的移動公式如下所示:

(26)

(27)

式中:Г為標準Gamma函數.

2)對于適應值較差的鳥巢,由遷移概率Pa判斷該鳥巢是否需要被遺棄并尋找新位置.新位置的生成方式如下:

(28)

3)為增加種群的多樣性,本文引入一種新的更新種群方法,即自適應擾動.

(29)

3.2 新參數訓練方法的算法步驟

本文提出的基于布谷鳥搜索算法的參數訓練算法流程如下:

具體步驟如下:

步驟1.初始化鳥巢.確定種群規模與遷移概率,并在已知的限定條件內隨機選取鳥巢的初始位置.

步驟2.計算鳥巢的適應值.根據實際問題設置目標函數,并以此求出各個鳥巢位置的適應值.

步驟3.依次從當前各個鳥巢出發進行Levy flight,由式(26)計算出飛行后的新位置.之后對鳥巢各個維度上超出限定條件的數值進行修正,防止出現鳥巢位置超出搜索空間的情況.

步驟4.根據遷移概率Pa對鳥巢進行遷移,根據式(28)計算出鳥巢的新位置.

步驟5.根據式(29)對當前鳥巢進行自適應擾動,尋找更優的位置.

步驟6.如果當前更新次數未達到初始給定的次數,則返回步驟3;否則將當前最優解保留并設置為BRB系統的參數,算法結束.

圖2 布谷鳥搜索算法參數訓練流程圖Fig.2 Flow chart of the CS algorithm parameter training

4 實驗分析

實驗部分,本節通過兩個實例驗證本文提出的參數學習方法有效性,并與現有的參數學習方法進行比較.實驗環境為:Intel(R) Core(TM) i5-4570 @ 3.20GHz CPU、8GB內存,Windows 7操作系統.

4.1 多極值函數實例

首先以多極值函數來驗證基于布谷鳥搜索算法的參數學習方法的可行性,多極值函數的具體式子如下:

g(x)=e-(x-2)2+0.5e-(x+2)2

(30)

式中,g(x)大約在x=0存在一個局部最小值,在x=-2,x=2處分別有一個局部最大值和一個全局最大值.基于觀察到的這些關鍵點的輸出,置信規則的結果定義為:

{D1,D2,D3,D4,D5}={-0.5,0,0.5,1,1.5}

(31)

進行參數訓練時,選取該函數上1000個均勻分布的點作為訓練集,設定種群的大小為25,將均方誤差MSE作為目標函數.

對比圖3、圖4中曲線的擬合效果可以發現,初始BRB系統擬合函數的效果非常不理想,因此引入參數學習是必要的.而圖4表明采用布谷鳥搜索算法能夠更好地解決陷入局部最優的問題,訓練后的BRB系統推理準確性更高,擬合多極值函數的效果更好.

未經參數學習的BRB系統擬合函數效果如圖3所示.

圖3 初始BRB系統的擬合效果Fig.3 Results of initial BRB system

采用基于布谷鳥搜索算法訓練后的BRB系統擬合多極值函數的效果為圖4所示.

圖4 基于布谷鳥搜索算法的BRB函數擬合結果Fig.4 Results of BRB based on the CS algorithm

對比傳統FMINCON方法的BRB系統進行擬合的多極值函數與本文提出算法的均方誤差(MES)差異如圖5所示.

圖5 Fmincon與CS BRB以及標準CS BRB擬合結果的MES對比Fig.5 Compare of BRB parameters based on Fmincon,CS BRB and standard CS BRB

由圖5可知,基于自適應擾動布谷鳥搜索算法的BRB系統相比基于Fmincon函數的BRB系統以及標準的布谷鳥搜索算法的BRB系統取得了更好的推理準確性.

根據文獻[16]可以得到初始BRB規則庫如表1所示,由布谷鳥搜索算法訓練后的BRB規則庫如表2所示.

在表3中進一步對比了本文方法與傳統的FMINCON方法[20]、Chen的方法[19]及Wang的方法[13]的收斂精度和收斂時間.由表3可知本文提出的新方法相比于Fmincon函數、Wang的專家干預下基于差分進化算法的參數學習方法和Chen的局部優化參數訓練方法[19]具有更好的推理精度.而且Fmincon函數依賴于Matlab不易移植且耗時,可見本文方法更為有效.

表1 初始置信規則庫Table 1 Initial BRB

4.2 輸油管道檢漏實例

為了檢驗基于布谷鳥搜索算法的BRB參數學習方法解決實際問題時的能力,本文采用輸油管道檢漏實例[6]進行實驗分析.實驗選用英國的一條100多公里長的輸油管道的石油泄漏數據來進行實驗.

對于輸油管道系統,在正常工作時,若油液輸入量大于輸出量,那么油液對管道產生的壓力與管道中油液總量成正比例關系;在不滿足正常工作模式時,輸入量大于輸出量,壓力反而減小,那么該系統可能已發生泄漏故障.由此可見,輸油管道內的平均壓力(PD)和流量的差值(FD)能夠直觀地反應輸油管道的泄漏狀況.

表2 訓練后的置信規則庫Table 2 BRB after training

表3 BRB系統推理性能的比較Table 3 Performance comparison of BRB System in function fitting

對于初始BRB的構建,以輸出流量差(Flow Difference,FD)和管道內平均壓力(Pressure Difference,PD)作為前件屬性,FD有8個參考值、PD有7個參考值.并選取泄漏量的大小(Leak Size,LS)作為系統輸出,共分為5個評價等級.前件屬性FD、PD和結果集LS經過量化后,候選值可表示為如下形式:

FD={-10,-5,-3,-1,0,1,2,3}

(32)

PD={-0.042,-0.025,-0.01,0,0.01,0.025,0.042}

(33)

LS={0,2,4,6,8}

(34)

由FD和PD可得到56條置信庫規則參數,從而組成BRB系統[19],實驗時,以2007組數據作為測試集,并隨機選取其中500組數據作為訓練集,以平均絕對誤差MAE作為目標函數.未訓練BRB系統對輸油管道進行檢漏的效果為圖6.

由圖6可知未訓練的BRB系統因參數設置不合理,擬合輸油管道泄漏時誤差大,所以要對初始BRB的參數進行訓練優化.

圖6 未訓練的BRB系統輸出與訓練數據Fig.6 Results of initial BRB system

訓練后的BRB系統的推理結果如圖7所示.

圖7 訓練后的BRB系統輸出與訓練數據Fig.7 BRB system outputs after training

從圖7中可以得到本文提出的方法訓練后的BRB系統能準確地擬合輸油管道泄漏的真實情況,訓練后系統的推理準確性到了極大的提升.

未訓練的BRB系統擬合的輸油管道泄漏情況為圖8所示.

使用FMINCON函數的參數訓練方法來擬合輸油管道泄漏的效果為圖9所示.

圖8 未訓練BRB系統對輸油管道系統泄漏的擬合情況Fig.8 Results of initial BRB system

由圖8、圖9和圖10可知,與初始BRB和利用FMINCON函數訓練后的BRB系統相比,本文所提出的新方法訓練后的BRB系統具有更好的決策推理能力,能夠很好反映輸油管道泄漏的實際情況,并且沒有出現過擬合的現象.

圖9 利用FMINCON函數參數訓練后BRB系統的擬合結果Fig.9 Results of BRB parameters based on FMINCON function

使用基于布谷鳥搜索算法的參數學習方法進行輸油管道泄漏的擬合結果為圖10所示.

圖10 基于布谷鳥搜索算法訓練后的BRB系統的擬合結果Fig.10 Results of BRB parameters based on the CS algorithm

為了進一步說明新方法的性能,實驗中將現有的參數學習方法作為比較對象,實驗仍為輸油管道泄漏檢測實例,對比結果如表4所示.

根據表4中MAE以及算法運行時間的對比,可以得出采用本文所提新方法進行訓練后的BRB系統推理精度高于其他現有的方法,同時收斂速度也相對更快,因此,本文提出的新方法綜合效益更高.

表4 BRB系統推理性能的比較Table 4 Comparison of reasoning performance of BRB system

5 結 語

針對現有BRB參數學習優化模型存在的不足,本文提出基于布谷鳥搜索算法的BRB參數學習方法,并通過多極值函數與輸油管道泄漏兩個實驗驗證了新方法的有效性.在多極值函數的實驗中,與現有其他方法在推理精度和運行時間進了對比,實驗表明,本文方法具有更好的收斂速度與精度.同時,通過輸油管道泄漏的實驗進一步表明了本文方法在解決真實問題時是高效可行的.

：

[1] Dempster A P.A generalization of Bayesian inference[J].Journal of the Royal Statistical Society-Series B,1968,30(2):205-247.

[2] Shafer G.A mathematical theory of evidence[M].Princeton:Princeton University Press,1976.

[3] Huang C L,Yong K.Multiple attribute decision making methods and applications,a state-of art survey[M].Berlin:Springer-Verlag,1981.

[4] Zadeh L Z.Fuzzy sets[J].Information and Control,1965,8(3):338-353.

[5] Sun R.Robust reasoning:integrating rule-based and similarity-based reasoning[J].Artificial Intelligence,1995,75(2):241-295.

[6] Zhou Zhi-jie,Yang Jian-bo,Hu Chang-hua,et al.Belief rule based expert system and complex system modeling:1stedition[M].Beijing:Science Press,2011.

[7] Liu J,Yang J B,Ruan D,et al.Self-tuning of fuzzy belief rule bases for engineering system safety analysis[J].Annals of Operations Research,2008,163(1):143-168.

[8] Zhou Z J,Hu C H,Yang J B,et al.Online updating belief rule based system for pipeline leak detection under expert intervention [J].Expert Systems with Applications,2009,36(4):7700-7709.

[9] Yang J B,Liu J,Xu D L,et al.Optimization models for training belief-rule-based systems[J].IEEE Transactions on Systems,Man,and Cybernetics-part A:Systems and Humans,2007,37(4):569-585.

[10] Ma Chang-feng.Optimization method and Matlab programming[M].Bejing:Science Press,2010.

[11] Wu Wei-kun,Yang Long-hao,Fu Yang-geng,et al.Parameter training approach for belief rule base using the accelerating of gradient algorithm[J].Journal of Frontiers of Computer Science and Technology,2014,8(8):989-1001.

[12] Su Qun,Yang Long-hao,Fu Yang-geng,et al.Parameter training approach based on variable particle swarm optimization for belief rule base[J].Journal of Computer Applications,2014,34(8):2161-2165.

[13] Wang Han-jie,Yang Long-hao,Fu Yang-geng,et al.Differential evolutionary algorithm for parameter training of belief rule base under expert intervention[J].Computer Science,2015,42(5):88-93.

[14] Yang Hui,Wu Pei-ze,Ni Ji-liang.Belief rule base parameter training approach based on improved particle swarm optimization[J].Computer Engineering and Design,2017,38(2):400-404.

[15] Yang X S,Deb S.Cuckoo search via Levy flights[C].Proceedings of World Congress on Nature & Biologically Inspired Computing,India,USA:IEEE Publications,2009:210-214.

[16] Chang Rui,Wang Hong-wei,Yang Jian-bo.An algorithm for training parameters in belief rule-bases based on the gradient and dichotomy methods [J].Journal of Systems Engineering,2007,25(Sup.):287-291.

[17] Chang L,Zhou Z J,You Y,et al.Belief rule based expert system for classification problems with new rule activation and weight calculation procedures[J].Information Sciences,2016,336(C):75-91.

[18] Yang X S,DEB S.Engineering optimization by cuckoo search [J].Int′l Journal of Mathematical Modeling and Numerical Optimization,2010,1(4):330-343.

[19] Chen Y W,Yang J B,Xu D L,et al.On the inference and approximation properties of belief rule based systems [J].Information Sciences,2013,234(11):121-135.

[20] Price K.Differential Evolution vs.the functions of the 2nd ICEO[C].Proceedings of the 1997 IEEE International Conference of Evolutionary Computation,1997:153-157.

[21] Xu D L,Liu J,Yang J B,et al.Inference and learning methodology of belief-rule-based expert system for pipeline leak detection [J].Expert Systems with Applications,2007,32(1):103-113.

附中文參考文獻：

[6] 周志杰,楊劍波,胡昌華,等.置信規則庫專家系統與復雜系統建模:第1版[M].北京:科學出版社,2011.

[10] 馬昌鳳.最優化方法及其Matlab 程序設計[M].北京:科學出版社,2010.

[11] 吳偉昆,楊隆浩,傅仰耿,等.基于加速梯度求法的置信規則庫參數訓練方法[J].計算機科學與探索,2014,8(8):989-1001.

[12] 蘇 群,楊隆浩,傅仰耿,等.基于變速粒子群優化的置信規則庫參數訓練方法[J].計算機應用,2014,34(8):2161-2165.

[13] 王韓杰,楊隆浩,傅仰耿,等.專家干預下置信規則庫參數訓練的差分進化算法[J].計算機科學,2015,42(5):88-93.

[14] 楊 慧,吳沛澤,倪繼良.基于改進粒子群置信規則庫參數訓練算法[J].計算機工程與設計,2017,38(2):400-404.

[16] 常 瑞,王紅衛,楊劍波.基于梯度法和二分法的置信規則庫參數訓練方法[J].系統工程,2007,25(增刊):287-291.