基于改進BPSO的最小碰集搜索方法應用研究

陳 忱（中國航空綜合技術研究所,北京 100028）

?

基于改進BPSO的最小碰集搜索方法應用研究

陳 忱
（中國航空綜合技術研究所,北京 100028）

摘 要：本論文在對比分析常用最小碰集搜索方法性能優劣的基礎上，提出了一種改進的離散二進制粒子群算法，并給出了該算法應用于最小碰集搜索的基本規則與流程，從最小沖突集集合簇中搜索獲得全部最小碰集并做出診斷結論。隨后，以衛星電源系統為應用案例，驗證了該方法的性能優勢、適用性以及工程實用性。

關鍵詞：基于模型診斷；沖突集；碰集；離散二進制粒子群算法

1 引言

基于模型診斷（Model-Based Diagnosis, MBD）作為故障診斷技術的分支之一，又被稱為基于“深知識”的診斷方法，它通過建立診斷對象的定性抽象模型，發揮定性分析、推理方法簡單易行的優勢，總結出抽象建模的基本規則，既解決了知識獲取瓶頸與知識庫維護困難問題，又能有效提高診斷的精確性，特別是針對具備層次性、耦合性、冗余度等特點的航空航天類電子產品，具有較高的應用價值［1］。

基于MBD的基本思想，診斷過程可分為系統建模、沖突識別與診斷生成。其中，診斷生成環節的基本任務就是完成最小碰集搜索，如何盡可能提高最小碰集搜索效率也成為了MBD技術領域的研究熱點。目前，可以將最小碰集搜索算法分為三類，分別是樹形搜索算法、布爾代數搜索算法，以及以遺傳算法為代表的一系列人工智能方法。其中，HS-TREE、HST-TREE、BHS-TREE［2］等樹形搜索算法需要建立樹或者圖，可能因為剪枝問題而丟失正確解，算法編程實現繁瑣且計算效率差；布爾代數方法［3］在計算碰集時不需建樹，不會因剪枝而丟失正確解，但需要預先存儲所有碰集，通過化簡得出最小碰集，在一定程度上限制了計算效率；遺傳算法［4］的空間復雜性對沖突集的規模不敏感，適用于求解沖突集規模較大的情況，但只能較快計算出部分碰集，不能保證所有輸出結果均為最小碰集。

鑒于此，本文設計采用離散二進制粒子群算法BPSO，將最小碰集的搜索問題轉化為用0、1表示的二值空間的搜索問題，并通過對算法進行適當改進，提高原有最小碰集的搜索效率。

2 基于模型診斷MBD的基本原理

MBD的基本思想［5］是利用產品系統內部結構或行為知識完成診斷，是一套面向沖突的故障診斷推理方法，這里的沖突指的是在被診斷系統所有組成元件均正常工作的假設前提下，系統觀測值與預期值之間存在差異的現象。下面，首先給出MBD方法中的幾個基本概念。

定義1：待診斷系統：MBD的分析對象，采用一階謂詞邏輯語句將其抽象描述成一個三元組（SD,OBS,COMP）的形式。其中，SD是系統描述，用一階謂詞邏輯公式集合描述系統的正常結構和行為；OBS為系統觀測集，由一階謂詞公式的有限集來表達；COMP表示一階謂詞邏輯的函數符號或常量集，為組成系統的元件集合，是一個有限集合。

定義5：最小沖突集：當且僅當某一沖突集的任何一個非空真子集都不是沖突集時，該沖突集是最小沖突集。

定義6：碰集：給定一個集合簇（集合的集合），若一個集合與這個集合簇中的全部集合的交集均不為空集，則稱該集合為此集合簇的碰集。用符號表示方法如下所示。設C是一個集合簇，C的碰集是一個集合H，H需要滿足兩個條件：H? S∪，其中S∈ C；?S∈ C，則H∩ S≠?。

定義7：最小碰集：當一個碰集的任意一個非空真子集均不是碰集時，則稱它為最小碰集。

在上述基本概念定義的基礎上，Reiter最早提出了基于模型診斷的基本流程框架，即將診斷過程分為系統建模、沖突集識別、碰集搜索三個環節，這也是后續基于模型診斷領域研究的基礎。本論文在前序研究中將這一基本流程細化如圖1所示，在此重點針對其中的最小碰集識別過程進行論述。

3 基于改進BPSO的最小碰集搜索方法

3.1 基本思路

對于某一電路系統來說，最小沖突集是由系統中若干元器件組成的，其中至少有一個是故障的，才能夠解釋電路系統通過模型推理得到的預期結果和實際觀測結果之間存在差異。本文引入BPSO算法求解最小碰集的基本思想，就是將沖突識別環節已求得的最小沖突集映射成用0、1表示的N緯二值集合， N代表元器件的規模，最小碰集的搜索問題就轉化為0、1表示的二值空間搜索問題。

具體來說，本文提出的最小碰集求解問題與BPSO算法之間的對應轉換關系見表1。

（1）電路系統的所有組成元器件都存在正常與故障兩種狀態，對應到最小沖突集映射成的N維二值集合中，每一維的值代表該維對應元器件的狀態，即0表示正常，1表示故障；

（2）BPSO算法關鍵變量之一為粒子位置，該向量每一維的值都被限制為0或1，即表示N維二值集合中每一維對應的元器件狀態是正常或故障；

表1 解最小碰集與BPSO算法的對應轉換關系列表

（3）BPSO算法的另一關鍵變量是粒子速度，它表示位置狀態改變的可能性，即粒子位置接近于1的概率，取值限定在［0,1］之間；

（4）碰集粒子是BPSO算法每次迭代獲得的中間結果，每個碰集粒子對應一個碰集，即該行向量中值為1的元素對應的元器件就是該粒子代表的碰集組成元素，需要進一步縮小獲得最小碰集粒子；

（5）BPSO算法最終獲得多個最小碰集粒子，由碰集粒子刪除超集后得到，每個粒子對應著一個最小碰集，即該行向量中值為1的元素對應的元器件就是該粒子代表的最小碰集組成元素。

通過上述對應轉換關系，可以實現用二進制編碼的方式來表示N維二值空間中的某一維是否被選擇進入最小碰集集合中，值為1即表示該維對應的元器件被選入最小碰集中，利用BPSO算法獲得的所有最小碰集即為最終輸出的診斷結論。

3.2 計算公式與規則的改造

在實際求解最小碰集的過程中，原始BPSO算法的計算公式不再適用于最小碰集搜索問題中的集合運算，需要重新定義計算規則。因此，本文針對求解最小碰集這一最終目標，對算法執行過程中涉及到的相關公式做出適當的調整與改造，并重新定義了二值向量/矩陣運算時的規則。

3.2.1 粒子速度更新公式

粒子速度更新公式與標準BPSO算法中的粒子速度更新公式保持一致。但在利用該公式進行迭代計算時，粒子速度的物理含義是狀態變化概率，經過上述公式中的乘法、加法運算后，更新后的粒子速度值仍應限定在［0,1］之間；同時，pid-xid（t）與pgd-xid（t）均為矩陣行向量之間的運算，且行向量元素均為0或1，則可能會出現元素“0-1=?”的情況。因此，需要對可能出現的運算設定合適的計算規則。首先，將本文中設計采用的BPSO算法中粒子速度更新的操作分解成如圖2所示的子過程，并將粒子速度更新過程中出現的計算類型分為四種情況，并分別給出計算規則。

①系數×速度。給定一系數c（c＞0）和一速度向量（概率向量）V，兩者乘積將定義為cV，具體形式如下：

其中pi（i=1,2,…,n）為原始速度向量中的概率，pi’為速度向量乘以系數后向量中的概率值。可以看出“系數×速度=系數×概率”，其結果為“概率”。

②位置-位置。“位置-位置”計算對應于傳統的集合減法操作定義，給定兩個粒子位置向量A與B，A-B具體定義如下。其中，A與B的元素為xi、yi（i=1,2,…,n），取值均為0或1。

根據本條規則可知，zi=xi-yi的所有可能情況見表2，“位置-位置”計算結果仍為“位置”。

表2 “位置位置”計算規則

③系數×（位置-位置）。“位置-位置”的結果仍是位置，則要進行“系數×（位置-位置）”，就需要定義“系數×位置”的計算規則。給定一個系數c（c＞0）和一個位置向量A，兩者的乘積將定義為cA，具體形式如下。

通過上述計算，實際上是將位置這一向量通過系數相乘后，轉化為一概率向量，即可以與速度向量（概率向量）進行加法運算，如下一條規則所示。

④概率+概率。給定兩個概率向量V1與V2，兩個向量的組成元素均為概率，即每個元素取值范圍都在［0,1］之間，兩者相加為V1+V2，具體形式如下，其中（i=1,2,…,n）。

此條規則實際上是用于三個概率向量相加，即ωvid（t）的計算結果為第一個概率向量，以c1r1（pid-xid（t））的計算結果是第二個，c2r2（pid-xid（t））的計算結果是第三個。通過規定概率相加的結果是取兩個概率的最大值，可以使最終計算結果的值始終被限定在［0,1］之間。可以看出，“概率+概率”的結果仍為概率，即更新后獲得的新的粒子速度向量。

3.2.2 粒子位置更新公式

利用BPSO算法進行最小碰集求解，需對粒子位置更新公式做出相應的調整，最終結果如下。如果t+1次迭代的粒子速度大于t次迭代時的粒子速度，t+1時刻的粒子位置更新為0，否則更新為1。

3.2.3 適應度函數計算公式

在BPSO算法中采用適應度函數來評價各個粒子位置的優劣以及粒子群位置的優劣，從而實現引導粒子群體向最優方向尋優（即更新粒子位置和粒子速度）。由此可見，適應度函數直接影響著通過BPSO算法求出的最小碰集的正確性，也影響著算法的搜索效率，即適應度函數在利用BPSO算法搜索最小碰集過程中起著至關重要的作用。

若直接將傳統BPSO算法應用于最小碰集搜索問題，則僅針對粒子群整體進行尋優，即算法的適應度函數僅用于評價整個粒子群。為了進一步提高搜索效率，本論文采用粒子群整體尋優與單個粒子尋優相結合的方法，即分別制定粒子群和單個粒子的適應度函數公式如下。

式中，P為粒子群種群規模，即設定的粒子數量；h為當前粒子群中不同的碰集粒子個數；m為最小沖突集集合簇中最小沖突集個數；x為單個粒子i對應的二值集合與最小沖突集有交集的個數。

由于本文采用BPSO算法的目的是搜索最小碰集，碰集與所有最小沖突集都有交集，結合適應度函數公式可以看出，單個粒子與粒子群的適應度值均是越大越好；同時，由于h的最大值只能為P，x的最大值只能為m，所以上述適應度函數的最大值均為1；另外，當fpi=1時，說明x=m，即該粒子i為碰集粒子，對應一個碰集。

3.3 算法流程

本文將上述利用改進BPSO算法搜索最小碰集的基本思路轉化為具體的實施流程，見圖3。

步驟一：將已獲得的最小沖突集映射到二值空間中，設此二值空間維數為N。

步驟二：粒子群及相關參數初始化設定。設定種群規模為P；初始化粒子群為一個P×N維的隨機二值矩陣作為粒子群初始位置x（1）；初始化一個P×N維的隨機矩陣作為粒子群初始速度v（1），所有元素取值均在［0,1］之間；設置慣性權重ω、學習因子c1和c2、最大迭代次數Tmax；令迭代次數t=1；初始化一個N維矩陣Hs存儲搜索出的碰集粒子。

步驟三：計算每個粒子的適應度函數值fpi（i=1,2,…,P）以及粒子群適應度值fg。

步驟四：若當前迭代次數t=1？若t=1，執行步驟五；若1＜t＜Tmax，執行步驟六。步驟五：迭代次數t=1時，更新個體極值向量與群體極值向量。對于個體：以初始狀態粒子適應度值和粒子位置作為個體適應度極值fpbesti（i=1,2,…,P）以及個體極值向量pi（i=1,2,…,P）。

對于群體：以初始狀態群體適應度值作為群體適應度極值fgbest，初始狀態下適應度函數值fpi最大的粒子位置作為群體極值向量pg。

步驟六：迭代次數1＜t≤Tmax時，更新個體極值向量與群體極值向量。

對于個體：若fpi≥fpbesti，令fpbesti=fpi，同時令pi=i（t），即將粒子個體極值向量更新為當前粒子；若fpi＜fpbesti，fpbesti與pi均保持不變。

對于群體：若fg≥fgbest，更新群體適應度極值fgbest=fg，更新群體極值向量pg=i（t），該粒子i（t）需要與現有Hs矩陣中存儲的碰集粒子不同，若相同則不更新pg；若fg＜fgbest，fgbest與pg均保持不變。

步驟七：根據fpi=1的原則，找出當前粒子群中的碰集粒子，將其中與現有Hs矩陣中存儲的碰集粒子不同的粒子存入Hs中。

步驟八：按照粒子位置、速度更新公式與相關計算規則，更新粒子群位置與速度，生成用于下一次迭代的新粒子群位置x（t+1）與粒子群速度v（t+1），t為當前的迭代次數。

步驟九：若當前迭代次數t=Tmax，執行步驟十；否則令t=t+1，返回步驟三。

步驟十：當迭代完成后，根據當前矩陣Hs，刪除其中的超集粒子，剩余的即為最小碰集粒子組成矩陣Hs’，這些粒子中元素值為1的維度所對應的元器件所組成的集合即為最小碰集，最小碰集粒子的個數即為最小碰集的個數。

3.4 算法性能比較

將本文提出的改進BPSO算法（針對單個粒子以及粒子群整體共同尋優）與傳統的BPSO算法（僅針對粒子群進行尋優）分別用于解決同樣的最小碰集搜索問題，同時也經典樹形搜索算法HS-Tree、布爾代數搜索算法Boolean、遺傳算法GA的診斷效果進行比較，利用問題規模與搜索時間之間的關系比較上述算法的搜索效率。

引用姜云飛、林笠學者在文獻［3］中的例子進行算法對比驗證，已知如下三個條件：

假設最小沖突集集合簇中包含10個最小沖突集，即n=10；

各個沖突集分別為｛1,2,…,m｝，｛2,3,…,m+1｝，…，｛n,m+1,…,n+m-1｝；

問題規模P=n+m-1分別取10，20，30，…，90，即m分別取1，11，…，81。

利用上述五種不同方法搜索最小碰集，得到的實驗最終對比結果見圖4，各算法性能對比分析的具體情況總結如下：

（1）傳統的HS-Tree搜索方法與布爾邏輯算法Boolean對沖突集的問題規模極其敏感，在問題規模達到50以后都出現了由于內存溢出而終止算法執行的情況，說明這兩種算法不僅實現過程繁瑣，而且難以用于解決實際問題；

（2）遺傳算法GA在問題規模較小或適中時，搜索效率與離散二進制粒子群BPSO算法相差不大，但當問題規模達到60后，相應的搜索時間開始急劇增加，即不再適用于此種情況的最小碰集求解；

（3）兩種BPSO算法（傳統BPSO與本論文提出的改進BPSO）對沖突集問題規模不敏感，適用于求解問題規模較大的情況，且規模越大，BPSO算法相對于其它搜索算法的搜索效率越高；

（4）本論文采用的單個粒子尋優與粒子群尋優相結合的改進BPSO算法用于最小碰集搜索時所用的時間比傳統BPSO算法用于同樣案例所用的時間縮短了近1/3。

綜上所述，本文提出的單個粒子尋優與粒子群尋優相結合的BPSO算法具有較高的計算效率和較快的收斂速度，這一實驗結果恰恰符合了本文采用該方法搜索最小碰集的出發點，同時該算法還有效地避免了樹形搜索算法因剪枝丟失真實解的問題、以及布爾邏輯算法的操作繁瑣問題，這也證明了該方法具有較強的實用價值。

4 診斷案例

以某典型衛星電源系統的核心模塊PCU（電源控制器）為診斷案例，對其進行定性描述與邏輯推理，重點驗證本文提出的最小碰集搜索算法與流程的正確性與實用性。PCU的控制電路原理圖見圖5,由充電控制電路、放電調節電路、分流調節電路、誤差放大電路構成。太陽電池陣輸出的能量經過一個二極管直接傳遞至負載設備；功率管Q2與Q3，分別為分流開關盒控制蓄電池充電的充電開關；Q2與Q3的控制端信號是G1與G2的輸出值，G1與G2是誤差放大器，分別受母線電壓和充電電流控制；Q4和Q5用于避免功率管Q2與Q3發生相互干涉現象。

4.1 診斷案例推理過程

4.1.1 抽象建模

在PCU轉化為抽象模型結構圖的過程中，進行了適當簡化，即不考慮電路中二極管的影響，僅分析功率管和誤差放大器。

首先對PCU中的功率管與誤差放大器這兩類元器件進行抽象建模，以功率管Q2與誤差放大器G2為例，所建模型見表3。

建立PCU的抽象模型，按MBD中的規則描述成三元組的形式如下：

①組成元器件集合COMP：COMP=｛G1，G2，Q2，Q3，Q4，Q5，Q6｝。其中，G1與G2為誤差放大器，記作VMEA；Q2、Q3、Q4、Q5與Q6為功率管，記作PT。

表3 功率管Q2/誤差放大器G2模型

②系統描述SD：

組成元器件屬性

組成元器件連接關系

元器件功能邏輯描述

觀測集OBS：該系統輸入端為in（G1）與in（G2），輸出端為out（Q2）與out（Q3），構成觀測集合OBS=｛ in（G1）, in（G2）, out（Q2）, out（Q3）｝。

4.1.2 沖突識別

假設衛星電源系統實際觀測到的現象為PCU模塊出現負載母線電壓過低，而蓄電池電流正常，即Q2輸出異常，Q3輸出正常。以此為輸入條件，轉換為觀測集具體取值后，進行沖突識別得到的最小沖突集集合簇為PCM2=｛G1,G2,Q4,Q2｝與PCM3=｛Q2,Q3,Q4,Q5,Q6｝，兩者將作為后續搜索最小碰集的輸入。

4.1.3 診斷生成

利用本文提出的改進BPSO搜索最小碰集。首先，將最小沖突集集合簇映射到由0、1組成的二值空間中，表示形式如下：

初始設定種群規模P=20，慣性權重ω=0.4、學習因子c1=c2=2、最大迭代次數為Tmax=50，初始化粒子群為一個20×7維的隨機二值矩陣x（1），同時初始化一個7維空矩陣Hs用于存儲后續搜索的碰集粒子。此處的學習因子和慣性權重作為預置參數，按照大部分BPSO算法的設置方式分別設置為2和0.4。同時，本文分析種群規模P對衛星電源系統這一案例在應用改進BPSO算法搜索最小碰集時產生的影響，獲得的分析結果如下表4所示。可以看出，針對這一案例，選擇P=20在取得較好的搜索結果的同時耗時最短。

根據本文提出的改進BPSO算法實施流程，借助計算機程序完成

表4 衛星電源系統中不同種群規模下算法性能比較

50次迭代，用于存儲碰集粒子的矩陣Hs的變化過程如下：

最終從迭代獲得的碰集粒子矩陣Hs中刪去所有超集粒子后得到的結果為Hs’ ，具體形式如下：

根據Hs’可以看出，共有2個最小碰集粒子，相應的最小碰集分別為｛Q2｝和｛Q4｝，即“功率管Q2或功率管Q4故障”為改進BPSO算法搜索后輸出的診斷結論。

綜上，在實際觀測到衛星電源系統中電源控制器的負載母線電壓過低而蓄電池電流正常的情況下，利用本論文提出的電子產品基于模型診斷方法流程進行故障診斷推理得出的結論是電源控制器故障，具體來說就是電源控制器下的功率管Q2或功率管Q4故障。

4.2 應用效果分析

（1）故障識別準確性。一方面，衛星電源系統的實際觀測值所代表的真實情況為“功率管Q2故障”，最終診斷結論中故障元器件也包含Q2，與實際情況相符，驗證了本論文提出的診斷方法的正確性；另一方面，通過本論文提出改進BPSO方法流程得到的最終診斷結論中還包含一些非故障部件，如“功率管Q4”，這一結果雖與實際情況不符，但考慮到安全性是本應用案例衛星電源系統的一個重要影響因素，所以在故障診斷推理過程中以略保守的方式進行，得到的結果仍是可以接受的。

（2）故障診斷速度。參考本論文3.4節對5種不同的搜索算法的性能比較分析結果，從中不難看出，利用本文提出的粒子群整體尋優與單個粒子尋優相結合的改進BPSO算法求解最小碰集搜索問題在診斷速度上同樣具有較大優勢，并且對問題規模不敏感，適用于求解大規模搜索問題。

5 結論

本論文通過將改進BPSO算法引入最小碰集求解，將傳統的集合搜索問題轉化為二值空間中的矩陣求解問題，并結合粒子群整體尋優與單個粒子尋優，提高算法收斂速度與搜索效率，制定出具體實施流程，并結合實例驗證了該算法具有良好的適用性以及較高的工程應用價值。后續，可以繼續深入研究動態系統的MBD方法，拓展應用范圍。

參考文獻：

［1］韓旭,史忠植,林芬等.基于模型診斷的研究進展［J］.高技術通訊,2009,19（05）：543-550.

［2］Reiter R. A theory of diagnosis from first principles［J］. Artificial Intelligence,1987（32）：57-96.

［3］姜云飛,林笠.用布爾代數方法計算最小碰集［J］.計算機學報,2003,26（08）：920-924.

［4］何士玉.基于模型診斷的搜索算法研究及其在配電網中的應用［D］.西南交通大學,2013.

［5］歐陽丹彤,張立明,趙劍等.利用標志傳播求解基于模型的故障診斷［J］.儀器儀表學報,2011,32（12）：2857-2862.

DOI：10.16640/j.cnki.37-1222/t.2016.12.215

作者簡介：陳忱（1988-），女，重慶人，工程師，主要從事測試性設計與驗證、PHM設計技術研究。