比較模型下ACS的快速精確診斷算法

陳 芳，梁家榮，張 乾

(廣西大學 計算機與電子信息學院，南寧 530004)

1 研究背景

蟻群系統是通過對自然界中螞蟻覓食行為的分析而提出的.螞蟻之間通過信息素來進行相互聯系[1]，即螞蟻在尋找食物的過程中會產生一種信息素，它的同伴會根據其信息素的多少來選擇路徑.如果螞蟻沒有產生足夠多的信息素，隨著時間的流逝，信息素會消失，那么最初螞蟻的覓食路徑也會不復存在[2].反之，如果有許多螞蟻選擇同一條路徑，那么這條路徑的信息素會增加，從而會驅使更多的螞蟻選擇這條路徑，也就是說，信息素最多的路徑就是螞蟻覓食的最短路徑[3].

為了保證系統的可靠性，Preparata et al.提出了第一個系統級可診斷模型(PMC模型)[4].基于PMC模型，Maeng和Malek提出了比較模型(也稱MM模型)，即借助于圖論的思想，用無向圖G(V，E)表示多重處理機系統，其中，V表示系統中的結點(處理機)集合，E表示結點(處理機)之間的連通關系，用結點vk比較結點va和vb，當且僅當結點va，vb，vk滿足，(va，vk)∈E且(vb，vk)∈E，由此得到的測試結果用ω(vk：va，vb)來表示[5].表1展示了比較模型下結點的比較規則.基于MM模型，Sengupta和Dahbura提出了特殊化的MM模型(MM*模型)，即只要結點是相鄰的，那么任意一個結點就需要去測試另外兩個結點[6].

隨著信息技術的快速發展，傳統的故障診斷方法，不能夠診斷出大量的故障處理機，且不能有效的將故障處理機替換為無故障的處理機.對于如何高效地解決多重處理機系統在運行過程中的故障診斷問題，學者們相繼提出新的策略.而蟻群系統作為一個比較新穎的概念，逐漸受到學者們的廣泛關注，與早期的啟發式算法，如：遺傳算法、模擬退火算法相比較，蟻群算法具有時間復雜度小，且易于在計算機上實現的優點.已有的關于ACS的研究囊括了基于蟻群系統的路由算法[7，8]以及在人工智能方面的應用[9]等,但關于蟻群系統的故障診斷分析，現還沒有相應的研究成果，故本文通過模擬蟻群獲取食物的過程，并對其最短路徑進行分析，結合ACS環分割的方法，從而提出一種在比較模型下蟻群系統的精確診斷算法.

2 蟻群系統(ACS)中螞蟻的覓食算法

定義1.在ACS中，把螞蟻看做結點，螞蟻之間形成的覓食路徑看做結點之間的連接.

表1 比較模型下三個結點的比較規則Table 1 Rules of three nodes under the comparison model

定義2.用α表示信息素，螞蟻vi走過路徑a，螞蟻vj走過路徑b，假設從巢穴出發的螞蟻vk是無故障的.如果α(a)>α(b)，且ω(vk：vi，vj)=1，那么ω(vi)=0(vi無故障),ω(vj)=1(vj故障)(見圖1，灰色表示故障結點，白色表示無故障結點).

在圖1中，螞蟻vi，vj反饋給螞蟻vk的信息為1，即路徑a,b中的信息素有差異.螞蟻vk通過反饋回的信息判斷出螞蟻vi是無故障的(螞蟻vj是故障的)，也就是說螞蟻vk到螞蟻vi所處的覓食點是最短路徑(螞蟻vk到螞蟻vj所處的覓食點不是最短路徑)，因此螞蟻vk可依據反饋回的信息選擇最短覓食路徑.

圖1 螞蟻覓食路徑的分析圖Fig.1 Analysis diagram of ant foraging path

依據以上螞蟻覓食路徑的理論，得到蟻群系統(ACS)中螞蟻的覓食算法，如下：

算法1.ACS中螞蟻的覓食算法

第1步.將參數αij,Δαij,M,N,a,b進行初始化.其中，αij表示信息素的強度，Δαij表示信息素強度的變化量，M表示螞蟻的數量，N表示結點的個數，a,b表示常量.

第2步.對常量a,b進行迭代.

第3步.輸入M(1～N)，啟動螞蟻計數器.

第4步.i表示螞蟻的巢穴，j表示覓食點.

計算從i到j的可能路徑.基于從結點i到結點j的所有可能路徑(螞蟻覓食過程)的狀態轉換規則，得到公式，如下：

其中，PM(i,j)表示螞蟻從i到j的行走概率，f(i,j)表示螞蟻從i到j之間的信息素，g(i,j)表示螞蟻從i到j的選擇意愿.

第5步.根據測試的數據，比較PM(i,j)的大小，從而獲得螞蟻的初始覓食路徑.

第6步.完成覓食路徑的螞蟻返回到巢穴.

如果Yes(都返回)，進行下一步，反之，跳到第4步.

第7步.算法結束.

通過算法1得到螞蟻覓食的初始路徑，第4節中，通過改變螞蟻M的數量，對算法1進行多次仿真實驗，隨著螞蟻數量的不斷增多，螞蟻的覓食路徑逐漸趨近環.下面一節，將運用ACS環分割方法，對螞蟻的覓食路徑進行分析.

3 ACS的快速精確診斷算法

3.1 ACS環分割算法

定義3.螞蟻從起始結點a到終結點b，途中經過所有其他結點且只經過一次，此路徑組成的回路就是ACS環.

接下來的部分將得出一些關于ACS環在比較模型下的重要屬性，這對于研究環分割算法是很有必要的.

引理1.一個ACS環由n個結點組成，其中有t個故障結點，如果n≥3t+1，那么存在這樣的一個結點va，使得ω(va:va-1,va+1)=0.

證明：因為在系統中最多有t個故障結點且至少由3t+1個結點構成，那么一定存在三個連續的無故障結點va,vb,vc滿足ω(vb:va,vc)=0.

由算法1，得到螞蟻覓食的路徑.將螞蟻的覓食路徑形成的環通過ACS環分割算法(見算法2)得到一系列的序列，并對其進行分析研究.

算法2.ACS環分割算法

第1步.找到一個測試結果為0的螞蟻(結點)，且其后面順序地連接一個測試結果為1的螞蟻(結點).由引理1以及表1，可以判斷出測試結果為0的螞蟻(結點).與此同時，測試結果為1的蟻群(結點集)S應滿足1≤|S|≤t.

第2步.繼續按順時針方向來檢測螞蟻(結點)的測試結果.如果螞蟻(結點)的測試結果為0，返回第2步，反之，進行第3步.

第3步.繼續按順時針方向來檢測螞蟻(結點)的測試結果.如果螞蟻(結點)的測試結果為1，返回第3步.如果螞蟻(結點)先前沒有被檢測，且其測試結果為0，則將其標注為X并返回第2步.如果螞蟻(結點)先前已被檢測，則算法結束.

圖2 由16個螞蟻(結點)構成的ACS環Fig.2 ACS ring composed of 16 ants(nodes)

由算法2得到的每一個序列都是由按順時針方向標注的兩個X之間的螞蟻(結點)以及連接這些螞蟻(結點)的路徑(邊)構成.顯然，被標注為X的螞蟻(結點)是一個序列的頭結點，同時也是另一個序列的尾結點(見圖2)，其中灰色代表故障結點，白色代表無故障結點.

圖3 由算法2得到16個螞蟻(結點)構成的序列Fig.3 Sequences of 16 ants (nodes) by algorithm 2

將圖3中的結點如表2所示.

綜上所述，得到如下屬性：

性質1.序列的測試結果為如下形式：0…01…01…0，且如果序列由三個結點組成，那么測試結果為010.

性質2.每一個序列至少存在一個故障結點.

表2 算法2得到的序列表Table 2 Sequence table obtained by algorithm 2

性質3.如果一個ACS環由n個結點構成，且其存在的故障結點個數為t(n≥3t+1)，依據算法2，將其分割為s個序列，那么2t≥s.

定理1. 序列由x個測試結果為0，y個測試結果為1的結點構成，則其滿足如下條件：

1)在序列中，如果頭結點是無故障的，那么前x個連續的結點也是無故障的且第x+1個結點是故障的.

2)在序列中，如果頭結點是故障的，那么前x-1個連續的結點也是故障的.

證明：依據算法2，表1以及引理1得證.

證明：因為序列的頭結點是故障的，由定理1得到此序列的前x-1個連續的結點也是故障的.考慮序列中剩余的y+1個結點的情況：

情況1.y=1，很明顯引理2是正確的.

圖4 算法2下超立方體網絡的4種策略診斷度Fig.4 Four strategies of the hypercube networks under the algorithm 2

可見在環診斷算法下，超立方體網絡的t/s-診斷度大于t/k-診斷度大于t/t-診斷度大于t-診斷度.由此可見ACS的環分割策略也同樣適用于以超立方體網絡為基礎的變體立方體網絡.

3.2 基于MM模型下ACS的快速精確診斷算法

為了盡可能多地找到ACS中的故障結點，需要用到深度優先算法.對于一個至多存在t個故障結點的n-環，DAS總能輸出集合M(|M|≥t+1)，且M中的每一個結點在M中至少存在兩個鄰居結點.那么，可以把M看做一個無故障結點集.

算法3.MM模型下ACS的深度優先檢測

輸入：無向圖G(V,E)表示由n個螞蟻(結點)構成的系統，且結點va∈V,vb∈V,令M={v}.

輸出：一個子集M?V.

第1步.DAS(v)：對于任意的兩個結點va,vb(va,vb∈N(v))且va≠M(或vb≠M).

如果ω(v:va,vb)=0.

那么M=M∪va且DAS(va).

第2步.輸出集合M中的結點.

由算法2可知系統中的所有結點都能被正確地診斷.

算法4.MM模型下ACS的快速定位診斷

輸入：無向圖G(V,E)表示由n個螞蟻(結點)構成的系統，T表示故障結點集的上界,ω表示癥狀.

輸出：一個故障結點集F，一個無故障結點集R，且F∪R=V.

第1步.令Mi=φ(1≤i≤n)，R=F=φ.

如果|Mi|≥t+1,

那么R=R∪Mi.繼續進行第2步.

第2步.通過診斷結果ω(vk:va,vb)來鑒別結點ξ∈N(Mi)，其中vk,vb∈Mi.如果ξ是故障的，那么F=F∪{ξ}.反之,Mi=Mi∪{ξ}.重復第2步，直到N(Mi)?F.

第3步.如果V=R∪F,那么輸出無故障結點集R以及故障節點集F.反之，跳到第4步.

第4步.令R=V-F，輸出無故障結點集R和故障結點集F.

4 仿真實驗

選用Matlab進行仿真實驗，系統Windows10，軟件平臺Matlab 7.0.4,硬件環境：X86架構且支持SSE2指令集，硬盤空間4G，內存2G.基于算法1，分別取螞蟻個數M=30,70,100，運行Matlab，得到的實驗結果如圖5，圖6，圖7所示.

圖5 ACS中取螞蟻個數為30的覓食最優路徑
Fig.5 Optimal feeding path of 30 ants in ACS

通過仿真實驗得到螞蟻M覓食的最優路徑(如圖5，圖6，圖7所示).隨著實驗次數以及螞蟻數目的不斷增加(無限趨于n)，將得到一條更趨近于環的最優路徑，且得到的路徑逐漸趨于穩定.

圖6 ACS中取螞蟻個數為70的覓食最優路徑
Fig.6 Optimal feeding path of 70 ants in ACS

在N-ACS環中取5組不同的Q1，Q0值.得到的結果如表3所示.表3的實驗結果顯示，Q1，Q0的取值不影響N-ACS環的診斷結果，且對于任意的ACS環，運用算法2的ACS環診斷算法，能夠通過已診斷出的無故障結點診斷出可能存在的故障結點.

圖7 ACS中取螞蟻個數為100的覓食最優路徑Fig.7 Optimal feeding path of 100 ants in ACS

表3 ACS環中Q1，Q0取不同值的統計數據Table 3 Statistics of different values of Q1and Q0in ACS ring

基于以上實驗結果，將Q1，Q0的初始值都設為0.3.運行Matlab，對結點進行檢測以及定位，經過多次仿真實驗，得到的實驗結果如圖8所示.可見系統中存在的故障結點數與診斷出的故障結點數趨同.

圖8 MM模型下算法3、算法4的測試結果Fig.8 Test results of algorithm 3 and algorithm 4 under MM model

定理2.MM模型下ACS的快速精確診斷算法的時間復雜度為O(N)，其中N為蟻群中螞蟻的數量.

證明：用F表示系統中存在的故障結點集，R表示剩余V-F的集合.若結點v屬于V-F集合，則在算法3、算法4中，第1步的時間復雜度為O(N).若節點v屬于R∪F，則在算法3、算法4中，第1步的時間復雜度為O(N).因此，在算法3、算法4中，第1步的時間復雜度為O(N).第2步以及第3步的時間復雜度為O(N).算法4的第4步，時間復雜度也為O(N).因此，總的時間復雜度為O(N).

表4 幾種網絡拓撲結構的時間復雜度比較結果Table 4 Comparison results of time complexity for several network topologies

目前，基于比較模型下ACS環的故障診斷度以及故障診斷算法還沒有學者研究，故本文提出的方法是較為新穎的，且與超立方體網絡[10,11]、擴展立方體網絡[12]以及星型網絡[13]相比，本文提出的算法時間復雜度更小(比較結果見表4).

5 結 論

本文在螞蟻覓食行為的啟發下，形象的將螞蟻作為系統中的結點，螞蟻之間通過釋放信息素而得到的路徑作為結點之間的連接，結合圖論，對蟻群系統(ACS)進行了深入研究.通過對蟻群系統中螞蟻覓食路徑的算法分析，由大量仿真實驗，且隨著螞蟻數目的不斷增多(無限趨于n),得到一條更趨近環的覓食最優路徑，并對此路徑進行環分割，從而得到一系列的序列.通過分析，得到關于序列的一些重要屬性，基于這些屬性，提出了ACS系統在MM模型下的快速精確診斷算法，通過大量仿真實驗，得出ACS中存在的故障結點數與診斷出的故障結點數趨同，且時間復雜度為O(N)，其中N為蟻群系統中螞蟻的數量.

對于解決類似問題的(如TSP(旅行商問題)，蝙蝠的回聲定位問題等)故障診斷，本文的研究方法同樣適用.未來研究以ACS為基礎的擴展問題(如TSP)的t/t-診斷度、t/k-診斷度以及t/s-診斷度，本文的研究思路同樣適用.