陳 芳，梁家榮，張 乾

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

1 研究背景

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

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

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

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

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

表1 比較模型下三個結(jié)點的比較規(guī)則Table 1 Rules of three nodes under the comparison model

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

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

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

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

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

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

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

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

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

計算從i到j(luò)的可能路徑.基于從結(jié)點i到結(jié)點j的所有可能路徑(螞蟻覓食過程)的狀態(tài)轉(zhuǎn)換規(guī)則，得到公式，如下：

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

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

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

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

第7步.算法結(jié)束.

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

3 ACS的快速精確診斷算法

3.1 ACS環(huán)分割算法

定義3.螞蟻從起始結(jié)點a到終結(jié)點b，途中經(jīng)過所有其他結(jié)點且只經(jīng)過一次，此路徑組成的回路就是ACS環(huán).

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

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

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

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

算法2.ACS環(huán)分割算法

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

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

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

圖2 由16個螞蟻(結(jié)點)構(gòu)成的ACS環(huán)Fig.2 ACS ring composed of 16 ants(nodes)

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

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

將圖3中的結(jié)點如表2所示.

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

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

性質(zhì)2.每一個序列至少存在一個故障結(jié)點.

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

性質(zhì)3.如果一個ACS環(huán)由n個結(jié)點構(gòu)成，且其存在的故障結(jié)點個數(shù)為t(n≥3t+1)，依據(jù)算法2，將其分割為s個序列，那么2t≥s.

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

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

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

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

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

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

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

可見在環(huán)診斷算法下，超立方體網(wǎng)絡(luò)的t/s-診斷度大于t/k-診斷度大于t/t-診斷度大于t-診斷度.由此可見ACS的環(huán)分割策略也同樣適用于以超立方體網(wǎng)絡(luò)為基礎(chǔ)的變體立方體網(wǎng)絡(luò).

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

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

算法3.MM模型下ACS的深度優(yōu)先檢測

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

輸出：一個子集M?V.

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

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

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

第2步.輸出集合M中的結(jié)點.

由算法2可知系統(tǒng)中的所有結(jié)點都能被正確地診斷.

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

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

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

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

如果|Mi|≥t+1,

那么R=R∪Mi.繼續(xù)進行第2步.

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

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

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

4 仿真實驗

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

圖5 ACS中取螞蟻個數(shù)為30的覓食最優(yōu)路徑
Fig.5 Optimal feeding path of 30 ants in ACS

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

圖6 ACS中取螞蟻個數(shù)為70的覓食最優(yōu)路徑
Fig.6 Optimal feeding path of 70 ants in ACS

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

圖7 ACS中取螞蟻個數(shù)為100的覓食最優(yōu)路徑Fig.7 Optimal feeding path of 100 ants in ACS

表3 ACS環(huán)中Q1，Q0取不同值的統(tǒng)計數(shù)據(jù)Table 3 Statistics of different values of Q1and Q0in ACS ring

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

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

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

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

表4 幾種網(wǎng)絡(luò)拓撲結(jié)構(gòu)的時間復(fù)雜度比較結(jié)果Table 4 Comparison results of time complexity for several network topologies

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

5 結(jié) 論

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

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