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

陳 芳，梁家榮，張 乾

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

1 研究背景

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

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

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

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

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

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

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

在圖1中，螞蟻vi，vj反饋給螞蟻vk的信息為1，即路徑a,b中的信息素有差異.螞蟻vk通過(guò)反饋回的信息判斷出螞蟻vi是無(wú)故障的(螞蟻vj是故障的)，也就是說(shuō)螞蟻vk到螞蟻vi所處的覓食點(diǎn)是最短路徑(螞蟻vk到螞蟻vj所處的覓食點(diǎn)不是最短路徑)，因此螞蟻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進(jìn)行初始化.其中，αij表示信息素的強(qiáng)度，Δαij表示信息素強(qiáng)度的變化量，M表示螞蟻的數(shù)量，N表示結(jié)點(diǎn)的個(gè)數(shù)，a,b表示常量.

第2步.對(duì)常量a,b進(jìn)行迭代.

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

第4步.i表示螞蟻的巢穴，j表示覓食點(diǎn).

計(jì)算從i到j(luò)的可能路徑.基于從結(jié)點(diǎn)i到結(jié)點(diǎn)j的所有可能路徑(螞蟻覓食過(guò)程)的狀態(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ù)測(cè)試的數(shù)據(jù)，比較PM(i,j)的大小，從而獲得螞蟻的初始覓食路徑.

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

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

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

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

3 ACS的快速精確診斷算法

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

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

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

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

證明：因?yàn)樵谙到y(tǒng)中最多有t個(gè)故障結(jié)點(diǎn)且至少由3t+1個(gè)結(jié)點(diǎn)構(gòu)成，那么一定存在三個(gè)連續(xù)的無(wú)故障結(jié)點(diǎn)va,vb,vc滿足ω(vb:va,vc)=0.

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

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

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

第2步.繼續(xù)按順時(shí)針?lè)较騺?lái)檢測(cè)螞蟻(結(jié)點(diǎn))的測(cè)試結(jié)果.如果螞蟻(結(jié)點(diǎn))的測(cè)試結(jié)果為0，返回第2步，反之，進(jìn)行第3步.

第3步.繼續(xù)按順時(shí)針?lè)较騺?lái)檢測(cè)螞蟻(結(jié)點(diǎn))的測(cè)試結(jié)果.如果螞蟻(結(jié)點(diǎn))的測(cè)試結(jié)果為1，返回第3步.如果螞蟻(結(jié)點(diǎn))先前沒(méi)有被檢測(cè)，且其測(cè)試結(jié)果為0，則將其標(biāo)注為X并返回第2步.如果螞蟻(結(jié)點(diǎn))先前已被檢測(cè)，則算法結(jié)束.

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

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

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

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

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

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

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

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

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

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

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

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

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

證明：因?yàn)樾蛄械念^結(jié)點(diǎn)是故障的，由定理1得到此序列的前x-1個(gè)連續(xù)的結(jié)點(diǎn)也是故障的.考慮序列中剩余的y+1個(gè)結(jié)點(diǎn)的情況：

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

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

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

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

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

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

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

輸出：一個(gè)子集M?V.

第1步.DAS(v)：對(duì)于任意的兩個(gè)結(jié)點(diǎn)va,vb(va,vb∈N(v))且va≠M(fèi)(或vb≠M(fèi)).

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

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

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

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

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

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

輸出：一個(gè)故障結(jié)點(diǎn)集F，一個(gè)無(wú)故障結(jié)點(diǎn)集R，且F∪R=V.

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

如果|Mi|≥t+1,

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

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

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

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

4 仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 論

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

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