基于改進蟻群算法求解最優(yōu)路徑方法的研究

鄧 雷，朱永利，張 雷

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

基于改進蟻群算法求解最優(yōu)路徑方法的研究

鄧 雷，朱永利，張 雷

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

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

蟻群算法;最優(yōu)路徑;電力線路

0 引言

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

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

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

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

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

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

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

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

2 蟻群算法的改進

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

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

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

2.2 局部搜索方法的改進

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

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

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

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

式中:γ和λ為兩部分所占權(quán)重系數(shù)［4］。

2.3 雙向搜索

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

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

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

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

圖3和圖4分別是基本蟻群算法和改進后的蟻群算法求解實驗環(huán)境中由節(jié)點1到節(jié)點16最優(yōu)路徑的結(jié)果。

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

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

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

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

4 結(jié)論

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

［1］黃貴玲，高西全，靳松杰，等．基于蟻群算法的最短路徑問題的研究和應(yīng)用 ［J］．計算機工程與應(yīng)用，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］多里戈，施蒂茨勒．蟻群優(yōu)化 ［M］．北京:清華大學(xué)出版社，2007．

［3］聶彬，沈祖成．一種改進的蟻群算法在配電網(wǎng)規(guī)劃中的應(yīng)用 ［J］．電力科學(xué)與工程，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］張學(xué)敏，張航．基于改進蟻群算法的最短路徑問題研究 ［J］．自動化技術(shù)與應(yīng)用，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．a(chǎn)nt Algo rithm and stigmergy［J］．Future Generation Computer Systems，2000，16(6):851 －871．

［6］夏立民，王華，竇倩，等．基于蟻群算法的最優(yōu)路徑選擇問題的研究［J］．計算機工程與設(shè)計，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］王倩，呂林．配電網(wǎng)最佳搶修路徑算法研究 ［J］．電力科學(xué)與工程，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］別文群．物流配送最短路徑網(wǎng)搜索的改進蟻群算法［J］． 計 算 機 工 程 與 設(shè) 計，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。

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