基于改進蟻群算法求解最優路徑方法的研究

鄧 雷，朱永利，張 雷

(華北電力大學 電氣與電子工程學院，河北 保定 071003)

基于改進蟻群算法求解最優路徑方法的研究

鄧 雷，朱永利，張 雷

(華北電力大學 電氣與電子工程學院，河北 保定 071003)

為保障電力系統供電可靠性，快速確定故障點到物資點最短路徑是電力線路管理的一項重要功能。傳統蟻群算法存在著收斂速度慢，易陷入局部最優解等缺點。文章針對其缺點，提出了一種結合最大最小蟻群算法，采用基于角度和信息素混合因素進行局部搜索并從起點和目標點雙向搜索的改進蟻群算法。通過實驗仿真表明，改進算法能有效地解決最短路徑問題，在實際應用中具有可行性。

蟻群算法;最優路徑;電力線路

0 引言

電力線路意外故障所導致的停電將會嚴重影響人們的生活質量，也會對生產設備以及產品的生產造成嚴重后果，因此，對電力線路故障快速修復有重要意義。如何選擇最優修復路徑成為電力線路搶修中的重要問題。當發生故障時，故障監測設備會監測到故障并發送信號給線路管理系統，系統確定故障點并通過智能算法在眾多故障點到搶修物資點的路徑中確定最優的搶修路徑，使路障得到快速搶修，保證快速恢復供電。目前，對確定最優路徑的選擇已經有了很多算法，如Dijkstra算法、A*算法、遺傳算法和蟻群算法等。傳統的Dijkstra算法雖然能確保找到最優路徑，但隨著網絡規模的擴大，內部的二重循環將導致執行效率嚴重降低。A*算法的全局性較差，容易陷入局部最優解。遺傳算法作為一種隨機優化算法，局部搜索能力較差，很容易出現早熟收斂現象［1］。

蟻群算法是20世紀90年代的一種模擬進化算法，這種算法的優點是具有分布計算、信息正反饋和啟發式搜索的特征，已經成功用于解決TSP(旅行商)組合優化問題，但是傳統蟻群算法有著易早熟、陷入局部最優解等問題。本文對其進行了改進，并嘗試將其用于確定電力線路最優搶修路徑這種單源最短路徑問題。通過仿真表明，本方法的優化效果較好。

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

在有n個節點的網絡中，V是所有節點的集合，設起點為S，目標節點為T，開始時所有的螞蟻都位于起點S，螞蟻i從S點出發，按照選擇策略選擇下一節點，以此類推，直到搜索到終點T，于是螞蟻i得到一個從S到T的解。每當螞蟻選擇完一條邊后，就馬上更新邊上的信息量 (局部更新)。然后螞蟻j出發，當m只螞蟻都進行完搜索，可以得到此次循環的最優解，但這是局部最優解，然后進行下一次循環，當達到設定迭代次數，在所有局部最優解中選擇的最優解為全局最優解。算法關鍵步驟如下:螞蟻 k(k=1，2，…，m)在運動過程中，根據各條路徑上的信息索濃度決定其轉移方向。這里用禁忌表tabuk(k=1，2，…，m)來記錄螞蟻當前所走過的節點，路徑集合隨著tabuK進化過程作動態調整。在路徑選擇過程中，螞蟻根據各條路徑上的信息素濃度及路徑的啟發式信息來計算狀態轉移概率。設(t)表示在t時刻螞蟻k由節點i轉移到節點j的狀態轉移概率:

式中:allowedk= {V－tabuk}為螞蟻k下一步允許選擇的節點集合;τij(t)為t時刻路徑 (i，j)上的信息素濃度;α為信息素啟發因子，表示信息素軌跡的相對重要性;β為期望啟發因子，表示能見度的相對重要性;ηij(t)為t時刻的能見度，反映由節點i轉移到節點j的期望程度，其中ηij(t) =1/dij，dij為經過路段 (i，j) 所需的花費。

當每只螞蟻走完一步或者完成了從起點S到終點T的搜索后，要對殘留信息進行更新處理。用τij(t)表示在t時刻路徑 (i，j)上的信息素濃度，則在t+1時刻此路徑上的信息素為:

式中:ρ為信息素揮發系數，ρ∈ ［0，1)，則1－ρ表示信息素濃度殘留因子，表示殘留信息素的相對重要程度;Δτij(t)表示在時刻t到t+1之間在路徑 (i，j)上的信息素濃度增量，初始時刻 Δτij(0) =0; Δ(t)表示第k只螞蟻在時刻t到t+1之間在路徑 (i，j)上增加信息素濃度。

問題模型:電力線路故障搶修路徑是一條距搶修物資點最近的道路交叉點到線路故障點最近的道路交叉點的交通路徑。線路的權值將由路線的長度、路況、交通管制等屬性信息確定，那么就可以把道路網絡抽象為一個加權有向圖。給定一個加權有向圖G為二元組G=(V，{E})，其中V是包含n個節點的集合，E是包含h條邊的集合，(i，j)是E中從節點i至j的邊，用Wij表示邊 (i，j)的非負權值。設S，T分別為V中的起始節點和目標節點，則最優路徑問題就是在加權有向圖中搜尋一條從S點到T點的路徑，并使路徑權值最小。

2 蟻群算法的改進

2.1 對信息素區域和更新方式的改進

傳統蟻群算法由于正反饋的作用，在搜索過程中出現局部最優解時，接下來的螞蟻搜索時就會以較高的概率選擇局部最優解，隨著搜索循環次數的增加，就會使局部最優解路徑上的信息素含量遠遠高于其他路徑，進而造成大部分螞蟻都會選擇這一條路徑，限制了算法的全局搜索能力，很容易陷入局部最優解。在算法運行之初，給每條路徑上的信息素都設置一個較大的值τmax，使得信息素更新對路徑信息素含量的影響不是特別顯著，使螞蟻有更大的搜索空間。為防止部分路徑信息素大量累積出現局部最優解，將路徑上的信息素含量設置兩個界值τmin，τmax，使信息素τ的值如下:

為保證算法向最優方向收斂，每進行一次循環后，只對得出最優解的螞蟻走過的路徑進行信息素的更新，其他路徑不更新。

2.2 局部搜索方法的改進

在傳統算法中，搜索依據只是路徑上信息素的含量。在現實交通行駛中，人們所選取的路徑是有一定方向性的，如人們不會選擇朝目標相反的方向行駛。這就會使距物資點和故障點的路徑交差點與中間節點間形成一個 ［0，π］的角。由于現實中不可能提前知道故障發生在什么地方，所以如果單單存儲角度，那n個節點就要存儲 (n－1)2數據量，不如存儲節點坐標。設節點i的坐標為 (ix，iy)，節點j的坐標為 (jx，jy)，目標節點T的坐標為 (Tx，Ty)。設dij為節點 i和j之間的距離，則:

同理可求出diT，djT。形成的∠ijT由式 (5)可得:

同理也可求出i點與起點S和目標節點T的角度∠SjT。式中的能見度η表示節點轉移的期望程度。所以可以把角度也作為影響的因素。則可以使:

式中:μ為角度所占權重。將ηij(t)代入式 (1)中得(t)。由節點i和j與T所組成的∠ijT與所求得的(t)共同決定選擇節點，如式 (7):

式中:γ和λ為兩部分所占權重系數［4］。

2.3 雙向搜索

傳統蟻群算法是將所有螞蟻放置在起點S，從S點向目標節點T去搜尋，所有螞蟻的初始環境的搜索方向大致相同，這也是該算法易于趨于局部最優級解的一個因素。針對此缺點，可以設定一半數量的螞蟻是從目標節點T向著起點S尋找路徑，這樣可使半數螞蟻受另外螞蟻搜尋結果的影響減少，增加搜索結果的多樣性，更容易找到全局最優解。

3 算法的實現和仿真

圖1是某地區的電力線路及交通路線圖，圖中深色矩形區域為一檢修物資點，而深色橢圓區域為故障點。根據物資點與故障點相關線路，抽象出一個具有16個節點的加權有向圖2作為實驗環境，節點1為起點，節點16為目標節點，每一條邊綜合長度，路況等后的權重也在圖中標出。實驗參數設定如下:α=1，β=5，m=30，τmax=10，τmin=0.1，μ =0.8，γ =0.9，λ =0.1/π，cycle=50。

3.1 仿真實驗1基本蟻群算法和改進算法仿真對比

圖3和圖4分別是基本蟻群算法和改進后的蟻群算法求解實驗環境中由節點1到節點16最優路徑的結果。

由圖3可以看出基本蟻群算法在50代中求解的最優值振動頻率波動很大，相對來說不易得到最優解，搜索具有一定的盲目性，很容易陷入局部最優解。圖4顯示改進算法運行之初有一定的波動，但很快就向著最優解收斂，在迭代次數中期偶有波動，但最終完全收斂到全局最優解上。

3.2 仿真實驗參數γ和λ取值

參數γ代表著角度在局部搜索中選擇節點時所占的權重，其大小對節點的選取有很大影響，圖5和圖6為γ=0.2，λ=0.8/π和γ=0.8，λ=0.2/π所得實驗結果。

對比兩圖可知，當角度權重系數較大時，算法進行局部搜索時更傾向于與所在點和目標點所成夾角較大的節點，由圖5可知最后算法收斂到了另一條角度更占優勢的路徑1－2－5－7－12－13－16。這條路徑的權重和為23.7，并且波動很大。而全局最優解應該是1－2－5－9－12－13－16，權重和為21.55。當角度權重系數較小時，算法成功尋找到了全局最優路徑。

4 結論

本文針對傳統蟻群算法易于過早陷入局部最優解的問題進行了改進，利用最大、最小蟻群算法的改進方法并結合角度與信息素雙重因素對局部搜索的影響，成功解決了由電力線路故障搶修所抽象出來的最優路徑選擇問題。實驗證明，改進算法性能確實優于傳統算法。但是角度權重系數不應太大，對于具體系數的確定，還有等進一步研究。

［1］黃貴玲，高西全，靳松杰，等．基于蟻群算法的最短路徑問題的研究和應用 ［J］．計算機工程與應用，2007，43(13):233－235．

Huang Guiling，Gao Xiquan，Jin Songjie，et al．Study and application on shortest path search problem based on ant algorithm ［J］．Computer Engineedng and Applications，2007，43(13):233－235

［2］多里戈，施蒂茨勒．蟻群優化 ［M］．北京:清華大學出版社，2007．

［3］聶彬，沈祖成．一種改進的蟻群算法在配電網規劃中的應用 ［J］．電力科學與工程，2010，26(5):30－ 33．

Nie Bin，Shen Zucheng．Improved ant colony algorithm application for electric distribution network planning ［J］．Electric PowerScience and Engineering， 2010， 26(5):30－33．

［4］張學敏，張航．基于改進蟻群算法的最短路徑問題研究 ［J］．自動化技術與應用，2009，28(6):4－7．

Zhang Xuemin，Zhang Hang．Research an improved ant colony algorithm of the optimal routing problem ［J］．Techiques of Automation and Application，2009，28(6):4－7．

［5］ Dorigo M，Bonabeau E，Theraulaz G．ant Algo rithm and stigmergy［J］．Future Generation Computer Systems，2000，16(6):851 －871．

［6］夏立民，王華，竇倩，等．基于蟻群算法的最優路徑選擇問題的研究［J］．計算機工程與設計，2007，28(16):3957－3940．

Xia Limin，Wang Hua，Dou Qian，et al．Research for optimal routing problem based on ant colony algorithm［J］．Computer Engineering and Design，2007，28(16):3957－ 3940．

［7］王倩，呂林．配電網最佳搶修路徑算法研究 ［J］．電力科學與工程，2007，23(2):15－19．

Wang Qian，Lu Lin．Research on distribution optimal repairing path algorithm ［J］．Electric Power Science and Engineering，2007，23(2):15 －19．

［8］ StutzleT，HoosHH．Max-min ant systems［J］．Future Generation Computer Systems， 2000， 16 (19):889－ 914．

［9］別文群．物流配送最短路徑網搜索的改進蟻群算法［J］． 計 算 機 工 程 與 設 計，2008，29(19):5040－ 5043．

Bie Wenqun．Study on advanced ant colony algorithm searching shortest path in logistics network of distribution［J］．Computer Engineering and Design，2008，29(19):5040－5043．

Research on Optimal Path Lines Based on Improved Ant Colony Algorithm

Deng Lei，Zhu Yongli，Zhang Lei
(School of Electrical and Electronic Engineering，North China Electric Power University，Baoding 071003，China)

In order to ensuring the reliability of the power system．Quick-searching the shortest line from the location of materials to the location of fault is an important function for management for transmission line．The traditional ant colony algorithms had some shortcomings such as slowly convergence rate and easily falling into local optimal solution．For these deficiencies，the paper proposes a method which combined Max-min ant system and it uses angle and pheromone mixed factor for local search，and uses bidirectional search way from start point and end point．The simulation experiments show that the improved algorithm can effectively solve the shortest lines searching problem and it improved the traditional algorithms which is feasible in practice．

ant colony algorithm;optimal path;power line

TM711

A

2010－08－09。

鄧雷 (1984－)，男，碩士研究生，主要研究方向為人工智能在電力系統中的應用，E-mail:greenreed123@126．com。