耦合體系拓撲空間的局部損壞與子空間的重構(gòu)

張季謙, 宣守智, 謝朔俏, 張健生, 徐 飛, 黃守芳

(安徽師范大學 物理與電子信息學院，安徽 蕪湖 241000)

引 言

意大利學者Dorigo等人在觀察螞蟻覓食習性時發(fā)現(xiàn)，它們總能找到巢穴與食物源之間的最短路徑[1]。螞蟻這種群體協(xié)作功能是通過一種遺留在其來往路徑上被稱為信息素(Pheromone)的揮發(fā)性化學物質(zhì)來通信和協(xié)調(diào)的。因此，1992年Dorigo在他的博士論文中提出一種算法：蟻群算法，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)最短路徑的行為。1998年Dorigo在比利時主持召開了第一屆蟻群算法研討會，很快掀起了蟻群算法的研究熱潮，隨后，Dorigo等人發(fā)表第一篇關(guān)于蟻群算法?？偨Y(jié)了蟻群算法已取得的成果及其應用。

蟻群算法最早成功地解決了旅行商(Traveling Salesm Problem)問題[2]，隨后許多科研工作者嘗試用蟻群算法去解決各種組合優(yōu)化問題。在發(fā)展了離散蟻群優(yōu)化算法之后，人們又發(fā)展了用于連續(xù)變量優(yōu)化體系的蟻群優(yōu)化算法。其一種思路是Socha用連續(xù)概率密度函數(shù)代替離散概率分布, 提出用多個正態(tài)分布函數(shù)混合的蟻群優(yōu)化算法[3]。另一種思路則是利用混沌來描述蟻群搜尋食物行為, 建立用于連續(xù)變量的混沌蟻群優(yōu)化算法[4]。為提高對連續(xù)空間求解的有效性，我們對蟻群算法進行了改進，將其用于混沌系統(tǒng)部分序列的參數(shù)辨識并證實可用于保密通信[5, 6]。

人們發(fā)現(xiàn)，單只螞蟻的行為具有混沌特征，但蟻群的整體則表現(xiàn)出較強的協(xié)作和自組織特性[7]。蟻群算法的思想正是基于真實螞蟻尋找食物的過程，用信息素去調(diào)控螞蟻在尋找食物的路徑選擇。蟻群在搜尋食物的過程中要遵循一定移動規(guī)則，即在行進過程中螞蟻會通過信息素來溝通和共享信息，對比所選路徑的優(yōu)劣，最后整個蟻群會找到一條最佳路徑，該路徑的選擇過程就對應于我們求解組合優(yōu)化問題最優(yōu)解的過程[8,9]。

因而,有個問題值得人們?nèi)ヌ剿鳎簩τ谏窠?jīng)網(wǎng)絡系統(tǒng)，若神經(jīng)元之間的耦合聯(lián)系出現(xiàn)了故障或斷路，生物體自身能否找到替代的信息通路呢？很顯然，這與蟻群尋找食物過程中, 道路突然被新的障礙物所封堵，蟻群能否構(gòu)建出新的路徑空間來完成食物的尋找過程相類似。為回答這樣的問題,首先，我們構(gòu)造一個在蟻穴和食物源之間具有多條搜尋路徑的拓撲空間結(jié)構(gòu)模型。接著，假設(shè)蟻群在搜索食物的過程中，該空間拓撲結(jié)構(gòu)發(fā)生局部改變或出現(xiàn)缺損。然后，采用蟻群優(yōu)化算法進行模擬計算，讓蟻群調(diào)整搜索策略，尋找新的替代路徑，構(gòu)建出讓耦合體系重新達到最優(yōu)狀態(tài)時所對應的拓撲結(jié)構(gòu)，計算出相應的連接通道。最后，利用路徑上信息素濃度的變化特點來判斷是否找到了新的路徑。

1 蟻群算法及路徑空間的結(jié)構(gòu)模型

1.1 蟻群優(yōu)化算法

(1)

其中，α和β分別表示信息素和啟發(fā)式因子的相對重要程度，(1)式中的ηij為預見度即信息素量，allowedk={1,2,…，n}表示螞蟻下一步允許選擇的城市。由于螞蟻在尋找食物時，是通過分泌信息素來進行通信聯(lián)系和調(diào)整各自路線的，因此，螞蟻在沿途所留下的信息素濃度的高低反映了其所找路徑的好壞優(yōu)劣。這樣，在蟻群空間中所有路徑都會存在一定濃度信息素，其濃度越高，說明這條道路被螞蟻選中的概率越大，也就越接近蟻群所要尋找的最優(yōu)路徑。當所有螞蟻完成一次周游后，各路徑上的信息素根據(jù)下式更新。

τij(t+n)=ρ×τij(t)+Δτij

(2)

(3)

其中ρ(0<ρ<1)表示信息殘留系數(shù)，用1-ρ表示信息素的揮發(fā)系數(shù)。按照上述算法規(guī)則，螞蟻可以搜尋出找到食物的最佳路徑。螞蟻k所走過的路徑便是TSP問題的一個可行解。

圖1 蟻群搜尋食物的路徑空間模型示意圖。A為蟻穴，H為食物源, 圖中數(shù)字代表節(jié)點之間路徑長度。Fig1. Diagram of the path space model of ant colony searching for food. A is a nest, and H is the food source, the numbers represent the path length between nodes.

1.2 蟻群搜尋路徑空間模型

路徑空間是指螞蟻在尋找食物過程中，經(jīng)歷各個節(jié)點(城市)所有路徑構(gòu)成的空間，這對應于我們解決最優(yōu)化問題的參數(shù)空間。本文設(shè)計一個蟻群搜索食物的路徑結(jié)構(gòu)模型，如圖1所示，其中A點是蟻穴，H點是食物源。蟻群在A點和H點之間運動，B、C、D、E、F、G是中間的節(jié)點。開始時，螞蟻都在蟻穴A處，并等概率地向B、C、D處前行，隨后在各節(jié)點繼續(xù)等概率向前前行直到H，隨后再由信息素含量控制螞蟻在A點和H點之間運動。節(jié)點之間的連線表示路徑，圖中數(shù)字代表路徑長度。很顯然，該路徑網(wǎng)絡空間中，A-C-E-H是一條最優(yōu)路徑，而A-B-F-H和A-D-G-H是該空間的次優(yōu)解。

1.3 拓撲空間局部損壞

本文中，我們采用蟻群優(yōu)化算法，重點考察該空間拓撲結(jié)構(gòu)發(fā)生局部改變或出現(xiàn)缺損時，對蟻群尋找最佳路徑的影響。研究過程中，利用兩個矩陣記錄兩類信息：一個記錄兩個節(jié)點之間的距離，另一個則記錄各條路徑上的信息素量。前者是一個不變的對稱矩陣，后者是一個動態(tài)的對稱矩陣，矩陣的行和列對應位置是連接兩條節(jié)點的道路信息，兩個節(jié)點沒有連接或者連接同一節(jié)點時，對應矩陣元設(shè)為0。

(4)

圖1是整個蟻群路徑空間的結(jié)構(gòu)模型，經(jīng)過蟻群搜尋一段時間后，所得的解其中包含最優(yōu)解、次優(yōu)解和一般解。所以，為簡化計算過程，本文先從簡化的蟻群模型中進行模擬計算。矩陣中各元素對應的節(jié)點是從左到右分別為A、B、C、D、E、F、G、H，對于蟻群簡化模型其道路矩陣為(4)。如果蟻群在尋找食物過程中，CE道路被破壞，路徑空間發(fā)生變化，這時從A出發(fā)的蟻群會考慮選擇其它替代路徑。螞蟻的數(shù)量取得適中，如果螞蟻數(shù)太少，則初始信息數(shù)分布對結(jié)果有很大影響，如果螞蟻數(shù)太多，則運行時間會增長。本文中，我們設(shè)置蟻群總共有250只螞蟻，單位路徑長度為1，初始道路信息素為0。蟻群搜尋一段時間后，局部路徑CE處被破壞，記錄此時信息素的含量。然后，螞蟻搜尋新的替代路徑，構(gòu)建出新的路徑空間，運行1000個時間單位后記錄相應各路徑上的信息素量。

1.4 模擬結(jié)果

通過蟻群算法模擬計算，記錄圖1所示路徑空間中搜尋的結(jié)果。為簡單起見，矩陣中各元素值用該路徑上信息素與最大信息素的比來表示。路徑空間破壞前后的蟻群搜尋結(jié)果有三種情形：(1) 正常路徑空間情形；(2)蟻群短時搜索后局部路徑被破壞情形；(3)蟻群長時搜索后局部路徑的破壞及重構(gòu)。下面分別加以討論。

(1) 正常路徑空間情形

路徑空間處于正常狀態(tài)時，螞蟻搜索一段時間后，遺留在路徑上的信息素分布如圖2所示?？梢钥闯?，圖2實際上是蟻群搜尋過程的一個中間結(jié)果。即螞蟻通過一段時間的搜索后，逐步選中了三條路徑，其中，以ACEH這條路徑為最優(yōu)路徑，另外兩條為次優(yōu)路徑。隨著搜索過程的進行，遺留在ABFH,ADGH兩條路上的信息素逐漸降低直至為零，而在中間那條上的信息素則變得最大，表明所有螞蟻最終選擇了ACEH作為最佳路徑。

圖2 三條主要路徑上的信息素分布 圖3 搜索過程開始后不久，局部路徑CE即斷開，穩(wěn)定后信息素的分布示意圖Fig.2 The pheromone distribution on the three main paths Fig.3 The distribution graph where the pheromone reaches a steady state after the local path CE is disconnected shortly during the search process.

(2)蟻群短時搜索后局部路徑被破壞情形

按照上述搜尋方案進行模擬，當蟻群搜索過程進行較短時間后，局部路徑C-E就遭到了破壞。然后讓蟻群繼續(xù)進行搜索，可以發(fā)現(xiàn)，螞蟻會尋找替代路徑重構(gòu)空間。繼續(xù)搜尋一段時間后，相應各路徑上的信息素分布如圖3所示。

由于局部路徑C-E斷開，導致螞蟻重新尋找新的路徑，這樣從A出發(fā)的后續(xù)螞蟻就會重新評估A-B, A-C和A-D這三條路徑的優(yōu)劣了。因此，較多的螞蟻會逐步舍棄A-C這條路徑，而改走A-B和A-D這兩條。隨著時間的推移，已抵達C、E兩點的螞蟻會沿外圍的路徑尋找,在此基礎(chǔ)上，蟻群繼續(xù)進行搜索行動，最終結(jié)果選擇了A-B-F-H這條路徑。

(3) 蟻群長時搜索后局部路徑的破壞及重構(gòu)

當蟻群搜索較長一段時間后，搜索結(jié)果快接近穩(wěn)定狀態(tài)了，絕大部分螞蟻都集中在最優(yōu)解ACEH這條道路上，相應的路徑上信息素的含量也非常高，而次優(yōu)解路徑上的螞蟻信息素即將揮發(fā)殆盡,結(jié)果如圖2所示。此時若局部路徑CE遭到破壞，那么結(jié)果會是什么樣的情形呢？

圖4a 蟻群搜索較長一段時間后，局部路徑CE被破壞時蟻群道路上的信息素分布示意圖。圖4b 蟻群在局部路徑CE被破壞，繼續(xù)搜索一段時間后信息素的分布示意圖。圖中顯示有兩條較好路徑可供選擇：一條路線是ACBFEH,另一條路線是ACDGEH。Fig.4a The pheromone distribution on ant colony road following ant colony search for a long time and local path CE is destroyed.Fig.4b The distribution diagram of pheromone after the local path CE is destroyed and continues searching for a period of time. Two better paths could be chosen from: the red ACBFEH and the blue ACDGEH.

圖4a是路徑CE剛被沖毀時各路徑上信息素濃度分布示意圖。若讓蟻群在此基礎(chǔ)上繼續(xù)進行搜索，直至找到最終路徑，記錄相應的蟻群數(shù)量和信息素分布情況并進行分析，我們發(fā)現(xiàn)，蟻群搜索路徑與上述兩種情形完全不同，所得結(jié)果如圖4b所示。從圖中信息素的分布情況可以看出，當局部路徑CE被破壞后，蟻群就近尋找替代路徑，初始階段選擇ACBFEH和ACDGEH作為較好路徑，隨著時間推移，最終蟻群選擇出ACBFEH這一條最佳路徑。

2 結(jié)果分析與討論

現(xiàn)對上述結(jié)果進行簡要分析。對于第一種情形：路徑空間沒有被破壞，在搜尋過程中，利用蟻群算法，螞蟻很快會從眾多的路徑中篩選出較好的三條：ABFH, ACEH, ADGH，從遺留的信息素濃度高低也可比較出這三條路徑的優(yōu)劣：ACEH>ABFH> ADGH。全體螞蟻更新信息素后，在此基礎(chǔ)上繼續(xù)搜索和對比，所有螞蟻最終選擇了ACEH作為最佳路徑。

對于第二種情形，螞蟻搜尋過程開始不久，局部路徑C-E就斷開，此時，由于處于搜尋過程的初期，各條路徑上遺留的信息素濃度都低，特別是中間路徑ACEH上信息素相比其它路徑而言，并沒有形成優(yōu)勢。因此，一旦CE中斷，從A出發(fā)的后續(xù)螞蟻就會重新評估A-B, A-C和A-D這三條路徑的優(yōu)劣了。這樣一來，較多的螞蟻會慢慢舍棄A-C這條路徑，而改走A-B和A-D這兩條。并且隨著時間的推移，圍繞C、E兩點周邊路徑的螞蟻就慢慢沿外圍路徑尋找。蟻群繼續(xù)進行搜索，最終選擇了A-B-F-H這條路徑，結(jié)果如圖3所示。

對于第三種情形，蟻群搜索較長時間后路徑空間才被毀壞，由于長時間的搜索，蟻群搜索的結(jié)果已經(jīng)定型，基本確定了A-C-E-H作為最佳路徑，分布在該條上的螞蟻和信息素比其他路徑上要高得多。因而，此時局部路徑C-E斷開的話，聚集在C和E兩點附近的螞蟻會就近尋找替代路徑，而不是從C點沿C-A返回蟻穴后再重新尋找。這時有CB,CF, CG和CD四個可能的方向供選擇。比較這四個方向路徑的優(yōu)劣，其中CBFE、CDGE是較好的替代方案, 因而找出ACBFEH和ACDGEH兩條可能的較優(yōu)路徑(如圖4所示)，并最終選定ACBFEH路徑為最佳方案。

在這種情形下，與第二種情形的結(jié)果明顯不同，蟻群最終所選的最佳路徑是ACBFEH, 而不是ABFH，對比路徑長度，似乎蟻群選擇的不是最優(yōu)路徑，這是什么原因造成的呢？我們可以從圖4所示的拓撲結(jié)構(gòu)的子空間來尋找答案。當CE被破壞之前，蟻群經(jīng)過較長時間的尋找，借助于信息素的交流與溝通，毫無疑問會確定ACEH為最佳路線，但是，一旦CE被阻斷，螞蟻會就近尋找出路，而由于此時附近的CB等路徑上仍然遺留有一定濃度的信息素，提示聚集在C點處的螞蟻圍繞CE沿著局部子空間CBFE或CDGE尋找。最終找出的路徑為ACBFEH，這實際上是由原來全局最優(yōu)路徑的一部分AC與EH，與當前局部最優(yōu)子空間CBFE有機組合起來的結(jié)果。

3 結(jié)論

在本文中，首先構(gòu)建一個蟻群搜尋食物的空間結(jié)構(gòu)，螞蟻從蟻穴出發(fā)有多條路徑可以尋找到食物，我們利用蟻群優(yōu)化算法設(shè)置一定數(shù)量的螞蟻進行尋找。模擬結(jié)果發(fā)現(xiàn)，當路徑不存在局部毀損情況時，螞蟻所找路徑為通常全局最優(yōu)的ACEH。若尋找過程中在最優(yōu)路線上出現(xiàn)局部毀壞，則會使得螞蟻重新構(gòu)建新的路徑。這時所尋找的路徑有兩種情形：其一，當出現(xiàn)毀壞是在搜尋過程進行較短時間后發(fā)生，則蟻群重新找到的路徑即為正常情況下的次優(yōu)解。其二，若毀壞是在搜尋較長時間后發(fā)生，則蟻群所找的路線是將全局最優(yōu)路徑的部分路段和局部子空間中的最優(yōu)路段綜合起來的結(jié)果。

本文模擬結(jié)果告訴我們，一方面，利用蟻群優(yōu)化算法，可以尋找出存在局部空間結(jié)構(gòu)出現(xiàn)毀損時的最優(yōu)路徑，重構(gòu)出新的拓撲空間。另一方面，利用這種現(xiàn)象可分析和判斷網(wǎng)絡空間中的故障所在。例如，對于神經(jīng)元網(wǎng)絡或通訊網(wǎng)絡，若某個局部出現(xiàn)故障，則會使得其周圍的線路出現(xiàn)電流突然變化或信息突然擁堵等現(xiàn)象，監(jiān)控這些現(xiàn)象就可以快速定位和排查神經(jīng)網(wǎng)絡中的病變或電力網(wǎng)絡中的故障所在。

[1] DORIGO M, BLUM C. Ant colony optimization theory: A survey Theory[J]. Comput Sci， 2005，344(2-3):243-278.

[2] FORSATIA R, MOAYEDIKIAA A, JENSENC R, et al. Enriched ant colony optimization and its application in feature selection[J]. Neurocomputing, 2014(142):354-371.

[3] AKPINAR S. Hybrid large neighbourhood search algorithm for capacitated vehicle routing problem[J]. Expert Syst Appl, 2016(61):28-38.

[4] CAI J J, LI Q, LI L X, et al. A fuzzy adaptive chaotic ant swarm optimization for economic dispatch[J]. Int J Electr Power Energy Syst, 2012(34):154-160.

[5] LIU L Z, ZHANG J Q, XU G X, et al. A modified chaotic ant swarm optimization algorithm[J]. Acta Phys Sin, 2013(62):170501-1-6.

[6] LIU L Z, ZHANG J Q, XU G X, et al. A chaotic secure communication method based on chaos systems partial series parameter estimation[J]. Acta Phys Sin, 2014(63):010501-1-6.

[7] LI L X, PENG H P, WANG X D, et al. Comment on two papers of chaotic synchro- nization[J]. Phys Lett A, 2004(333):269-270.

[8] LISSOVOI A, WITT C. Runtime analysis of ant colony optimization on dynamic shortest path problems[J]. Theor Comput Sci, 2015(561):73-85.

[9] ZHANG J Q, HUANG S F, PANG S T, et al. Optimizing calculations of coupling matrix in Hindmarsh-Rose neural network[J]. Nonlinear Dynamics, 2016，83(3):1303-1310.

[10] JIANG K L, LI M A, ZHANG H W. Improved Ant Colony Algorithm for Travelling Salesman Problem[J]. Journal of Computer Applications, 2015，35(S2):114-117.