李 云

(宿遷高等師范學校 計算機系，江蘇 宿遷223800)

0 引言

實際工作中，由于供電線路的突發(fā)故障引起的停電，一方面會影響人們正常的工作與生活;另一方面，在某些情況下甚至可能產(chǎn)生意想不到的嚴重后果，如毀壞設備等。因此就要求工作人員能迅速的進行檢修。為了保證檢修的高效性，挑選最優(yōu)的路徑就相當關鍵。這就要求在故障產(chǎn)生后，監(jiān)測系統(tǒng)能采集到故障信息并確定故障點，這樣就可以使用智能算法把到故障點的所有路徑里的最優(yōu)的那一條找出來，可以使線路得到及時修復，有效的保證電力的恢復。最近，學者提出了很多算法來求解最優(yōu)通路問題，具有代表性的有遺傳算法、Dijkstra 算法與蟻群算法等。其中遺傳算法本質(zhì)上是隨機優(yōu)化，部分搜尋效果不佳，很有可能發(fā)生早熟收斂;Dijkstra 算法對于小規(guī)模最優(yōu)路徑問題求解效果還可以，但對于大規(guī)模的問題求解時，算法的性能會快速下降。

蟻群算法本質(zhì)上用的是模擬進化的思想，既可以并行處理，又充分利用了正向反饋與啟發(fā)搜索，所以該算法一經(jīng)提出就獲得了廣泛的應用，比如說求解TSP 問題。但是基本螞蟻算法也有不足之處，有時只能得到局部最優(yōu)解。本文針對此問題進行了改進，并且把改進后的算法用于求解電力故障搶修問題中的最優(yōu)通路。從仿真實驗可以看出，算法改進后的性能得到明顯改善。

1 基本蟻群算法模型和問題模型

用圖來描述問題，節(jié)點數(shù)是n，V 是節(jié)點的集合。如果從S 點開始最終要到達T 點，螞蟻最初都在S 點，第i 只螞蟻在S 點起程，對接下來要到達的節(jié)點是按某種算法求得的，照此方式進行，最終到達目的地T，這樣第i 只螞蟻便可獲得S 到T 的路徑。在螞蟻挑選某邊后，會立即對此邊的相關信息量進行更新，這就是部分更新方式。螞蟻j 做類似的討論，對每個螞蟻都做這樣的處理，便可獲得當前循環(huán)里的最優(yōu)解，只不過這個解是局部最優(yōu)的，繼續(xù)這樣的循環(huán)，直到完成我們給定的次數(shù)，這時在找到的全部局部最優(yōu)解里選一個最好的解就是整體最優(yōu)解。其中，最關鍵的是螞蟻決定將要通過的路徑主要參考路上的信息量大小。tabuk(k =1，…，m)表示已走過的節(jié)點，根據(jù)進化過程對通路集合做動態(tài)調(diào)整。挑選下一個節(jié)點時，某條通路被選到的機率由它上的信息量和啟發(fā)信息決定的，在t 時螞蟻k 從i 到j 的概率為:

其中:allowedk= {V -tabuk}表示第k 只螞蟻將有可能轉(zhuǎn)向的全部節(jié)點，τij(t)表示t 時刻從i 到j 路上的信息量，α 是誘導因子，代表信息量通路的重要程度，β 是期望誘導因子，代表可見度的重要程度;ηij(t)是t 時刻的可見度，代表節(jié)點i 轉(zhuǎn)到j 的期望度，其中，ηij(t)= 1/dij，dij是經(jīng)過邊(i，j)需要的時間。

在每個螞蟻從起始點S 到結束點T 的搜索完成后，還需要更新殘留信息，τij(t)是時刻t 時路徑(i，j)的信息量的濃度，那么t +1 時刻該路徑的信息量為:

式中:ρ 顯示信息素的揮發(fā)程度，ρ ∈［0，1)，則1 - ρ 是信息素的殘留因子，指出殘留的信息量相對的重要性;Δτij(t)是t 到t +1 時刻間路徑(i，j)的信息量濃度增值，初始值Δτij(0)= 0;Δτkij(t)是第k 個螞蟻在t 到t +1 時刻之間在邊(i，j)上添加的信息量濃度。

實際問題的模型可以描述為:在供電系統(tǒng)產(chǎn)生故障后，需要找出一條到搶修點的最優(yōu)通路。每條路的權值由相應的距離和路況來確定，這樣我們便能將路線圖用有向圖(帶權值)來描述。如果給定的有向圖(有權值)G = (V，E)，集合V 中含有n 個節(jié)點，集合E 中含有h 條邊，(i，j)代表E 里從點i 到節(jié)點j 的邊，邊(i，j)上的權值(非負)以wij來表示。如果S 表示V 起始點，T 表示V 的目的節(jié)點，則路徑最優(yōu)問題也就轉(zhuǎn)換為:在G = (V，E)中搜索一條由S→T 的路徑，要使通路上的權值達到最小。

2 改進后的蟻群算法

2.1 改進信息素區(qū)域與更新方式

因為受到正反饋的作用影響，基本蟻群算法在求解時經(jīng)常出現(xiàn)局部最優(yōu)解，這樣后趕到的螞蟻在尋找時選到局部最佳解的機率就很大，當循環(huán)數(shù)量逐漸變多時，局部最優(yōu)解通路上的信息量會高出其余路徑很多，那么就會讓很大多數(shù)螞蟻挑選這條路徑，因此限制了該算法整體搜索性能，結果使算法陷入局部最優(yōu)解。算法開始執(zhí)行時，每一條通路的信息量均定為比較大的τmax，讓信息素的更新不至于過度的影響路徑上的信息素數(shù)量，使得螞蟻的搜尋空間能更大些。為避免出現(xiàn)局部最優(yōu)解(是部分路徑上的信息素過多累積造成的)，可將通路上信息量設置兩個臨界值τmin、τmax，使信息素τ 的值如下:

每當完成一次循環(huán)后，我們只更新某些特殊路徑(已經(jīng)算出最優(yōu)解的那些螞蟻所經(jīng)之路)上的信息素，這樣就可以做到使該算法沿著最優(yōu)解的方向逐步收斂。

2.2 改進的部分搜索法

在過去的算法中，搜索的方向是依據(jù)路徑上的信息量的多少來確定的。而在現(xiàn)實的尋徑過程中，選擇的路徑不是無向的，而是有向的，比如正常的人從來就不會選擇與自己的目的地相反的方向行駛。因此故障點和物資檢修點的交叉點與中間節(jié)點構成［0，π］的角。而且現(xiàn)實生活里人們不可能提前預測故障產(chǎn)生的地方，因此若只存儲角度的話，必須存(n - 1)2個相關的數(shù)據(jù)，這樣就沒有存節(jié)點的坐標節(jié)省空間。若i坐標用(ix，iy)表示，j 坐標用(jx，jy)表示，目標T 坐標用(Tx，Ty)表示，那么節(jié)點i 到j 的長度為:

同樣方法可求得diT，djT。形成的∠ijT 可由下式求出:

依此方法也能得到i 點、源點S 及目標點T 形成的∠SjT，其中η 反映節(jié)點轉(zhuǎn)向的期望度，因此角度也是具有影響的因素因素之一，滿足:

其中，μ 表示角度的權值。把ηij(t)代到式(1)中就可以求出pkij(t)。i，j 和T 形成的∠ijT 與所求出的一起決定應該如何挑選節(jié)點，如式(7)所示:

式中，γ 和λ 為兩部分所占權重系數(shù)。

2.3 建立雙向的搜索

基本的蟻群算法在求解TSP 等問題時容易陷入局部最優(yōu)解，因為它是將所有的螞蟻都置于起點，然后按照從起點到目標點的方向搜尋?；谏厦娲嬖谶@樣的問題，我們可以假設一半螞蟻從起點到目標點，另一半從目標點到起點，利用雙向搜索減少螞蟻彼此之間的影響，能夠增加結果的多樣化，從而達到全局的最優(yōu)解。

3 算法仿真與實現(xiàn)

圖1為某一地區(qū)的交通與電力路線圖，其中顏色較深的矩形區(qū)域是某一物資檢修點，故障點是深色地方所示。參照故障點與物資點的有關線路，可以用如下的帶16 個頂點的有加權值的有向圖(圖2)來仿真，頂點1 作為起點，頂點16 是目標點，各邊的路況和長度等權重信息如圖2所示。相關參數(shù)設置為α =1，β = 5 ，m = 30，τmax= 10，τmin= 0.1，μ = 0.8，γ = 0.9，λ = 0.1/π，cycle = 50。

圖1 路線的走向圖

圖2 帶加權值的有向圖

3.1 改進后的蟻群算法與基本算法的仿真對比

在給定的仿真條件下，下面的圖3是未改進的蟻群算法求解頂點1 到達頂點16 的最佳路徑的效果示意圖，圖4是用改進之后的算法求解這個問題的結果。

圖3 用基本的蟻群算法進行仿真所得結果

圖4 用改進后的蟻群算法進行仿真所得結果

觀察圖3我們可以發(fā)現(xiàn)用基本螞蟻算法尋求最優(yōu)解時，50 代內(nèi)的頻率有很大波動，相比較而言要求得最優(yōu)解不太容易，與此同時搜索還有一定盲目性，很容易導致最優(yōu)解是局部的。從圖4可以看出改進后算法求解初期有一定波動，可是迅速地往最優(yōu)解方向收斂，迭代中期雖然偶有波動，最終還是完全收斂于整體最優(yōu)解。

3.2 實驗仿真的參數(shù)γ 與λ 的取值

用參數(shù)γ 表示角度在部分搜索選取節(jié)點時的權重，γ 的值在很大程度上影響節(jié)點的選取，在圖5與圖6中選取γ = 0.2，λ = 0.8/π 與γ = 0.8，λ = 0.2/π。

由兩圖對比情況可以發(fā)現(xiàn)，若角度權重的系數(shù)較大，用此算法執(zhí)行部分搜索時，目標點與所在點的夾角越大越容易被被搜索到，從圖2可以判斷出:最終算法收斂于路徑1→2→5→7→12→13→16，因為這條路徑的角度相比較而言更占優(yōu)勢。此路徑權重和為23.7，而且波動較大。但全局最優(yōu)解應是1→2→5→9→12→13→16 這條路徑，權值總和是21.55。把角度權值相應減小，算法就可以找出全局最優(yōu)通路。

圖5 角度權重系數(shù)較大

圖6 角度權重系數(shù)較小

4 結語

基本的蟻群算法可能會很早就陷入局部最優(yōu)解，在本文中，我們對此不足之處進行了改進。改進之一是引入“最大”、“最小”的方法;改進之二用角度配合信息量共同作用于部分搜索。把此法用于解決電路故障維修如何挑選最佳路徑的現(xiàn)實問題，通過實驗仿真表明改進后的算法明顯提高了全局最優(yōu)解的搜索能力。

［1］段海濱，王道波，朱家強，等，蟻群算法理論及應用研究的進展［J］.控制與決策，2004，19(12):1321 -1326，1340.

［2］Colony A，M.Dorigo ，Maniezzo V·Distributed Optimization by Ant Colonies［C］.France:Proc of 1st European Conf.Artificial life.pans，1991:134 -142.

［3］Dorigo M.Optimization，learning and natural algorithms［D］.Italy:ph.D.Thesis in politecnico imilano，1992.

［4］Dorigo M，Maniezzo V，Colorni A.Ant system:optimization by a colony of cooperating agents［J］.IEEE transaction on systems，man，and cybernetics-part B ，1996，26(1):29 -41.

［5］張紀會，徐新和，一種新的進化算法-蟻群算法［J］系統(tǒng)工程理論與實踐，1999，19(3):84 -87.

［6］段海濱，王道波，于秀芬，等.基于云模型理論的蟻群算法改進研究［J］.哈爾濱工業(yè)大學學報，2005，37(1):115 -119.

［7］段海濱，蟻群算法原理及應用［M］.北京:科學出版社，2005.

［8］李士勇.蟻群算法及其應用［M］.哈爾濱:哈爾濱工業(yè)大學出版社，2004.

［9］秦嶺.蟻群算法的改進及應用［D］.揚州:揚州大學碩士學位論文，2004.