基于改進的最大最小蟻群算法求解電力線路最佳搶修路徑

摘 要:電力線路最佳搶修路徑就是一條物資點到故障點耗費時間最少的交通路徑。最大最小蟻群算法改善了基本蟻群算法的過早停滯現象，適合于求解大規模問題，但仍存在收斂速度慢、求解質量差等缺點。針對最大最小蟻群算法的不足，提出了一種改進的最大最小蟻群算法來求解電力線路最佳搶修路徑。該算法采用分段函數設置狀態轉移規則，結合噪聲擾動方法進行局部搜索，并利用變異思想和A算法產生鄰域解。仿真實驗表明，在求解電力線路最佳搶修路徑時，該算法比其他改進蟻群算法具有更多的優越性，并分析了噪聲擾動方法的參數對求解質量的影響。

關鍵詞:最大最小蟻群算法; 噪聲擾動方法; 最短路徑

中圖分類號:TP393文獻標志碼:A

文章編號:1001-3695(2009)09-3436-04

doi:10.3969/j.issn.1001-3695.2009.09.066

Searching optimal rush repair path of power lines based onimproved max-min ant colony algorithm

ZHU Yong-lia， CHEN Ying-weia， HAN Kaia， WANG Leib

(a.School of Computer Science Technology， b.School of Control Science Engineering， North China Electric Power University， BaodingHebei 071003， China)

Abstract:The optimal rush repair path of power lines is a traffic road which costs the least time from the location of materials to location of fault. The max-min ant colony algorithm improved the premature stagnation brought by the basic ant colony algorithm， is suitable for solving large-scale problem. However， it still had some shortcomings such as slowly convergence rate and the poor quality of results. Based on the shortcoming of the max-min ant colony algorithm， this paper proposed an improved max-min ant colony algorithm to solve the optimal rush repair path. Segmented function for choosing state transition rule was introduced in the improved algorithm， as well as noising method for local search and the variation thought and A algorithm for generating the neighborhood of the current solution. The simulation tests prove that the improved max-min ant colony is superior to any other improved ant colony algorithm in solving the optimal rush repair path of power lines， and analyze the impact of parameters in noising method on quality of solution.

Key words:max-min ant colony algorithm; noising method; shortest path

0 引言

隨著人們生活水平的提高和電力系統的發展，電力線路逐漸增多，線路故障時有發生。突如其來的自然災害更易造成大面積的桿塔和線路故障，搶修不及時將嚴重影響生產、生活。因此，電力線路中的最佳搶修路徑的研究就成為當今的一個熱點問題。

電力線路中的最佳搶修路徑問題就是在檢測到故障點后，派遣搶修人員及時地到達故障現場，減少故障造成的破壞，也就是交通網絡中的最優路問題?，F在已經存在多種算法來求解此問題，如Dijkstra算法、模擬退火算法、蟻群算法和遺傳算法。但是Dijkstra算法隨著網絡規模的擴大，內部的二重循環將導致執行效率嚴重降低。模擬退火算法雖然能夠找到最優解，但是冷卻參數的設置很難把握。遺傳算法作為一種隨機優化算法，局部搜索能力較差，很容易出現早熟收斂現象。

蟻群算法是一種全局啟發式算法，它是在對自然界中真實蟻群的集體行為的研究基礎上，由意大利學者Macro

Dorigo等人提出來的[1]。求解效率最高的最大最小蟻群算法是德國學者T.Stuetzle等人[2]針對蟻群算法容易出現過早的停滯現象而提出的蟻群改進算法。本文就是將最大最小螞蟻算法與噪聲擾動算法相結合，利用蟻群算法的全局性避開局部極優，利用局部搜索加快求解速度，并采用信息素調解機制來求解電力線路最佳搶修路徑。仿真結果表明這一改進算法效果比較理想。

1 電力線路最佳搶修路徑的數學模型

電力線路中的最佳搶修路徑就是交通網絡中搶修人員從物資點到故障點花費時間最少的路徑。所以，找到故障點鄰近的交叉路口(目標節點T)和物資點鄰近的交叉路口(初始節點S)，然后在交通網絡拓撲圖中求取S～T耗費時間最少的路徑。因此，交通網絡中的路段抽象為平面圖中的邊，交叉路口抽象為平面圖中的頂點，形成一個平面圖G(V，E)。其中:V是頂點集合;E是邊的集合。如果頂點i到頂點j有直接相連的邊，則Xij=1;否則Xij=0。Wij是(i，j)的權重，即通過路段(i，j)所耗費的時間。最佳搶修路徑就是S～T的一些中間節點的集合(a0(S)，a1，…，ai，…，an(T))，因此電力線路最佳搶修路徑的數學模型如式(1)所示。

min∑(i，j)∈Ewijxij

∑j:(i，j)∈Exij-∑j:(j，i)∈Exji=1i=S-1i=T0i≠S，T(1)

受到路段行使速度、交叉路口的延誤、交通管制等交通因素的影響，路段(i，j)的權重wij由行駛時間和交叉路口延誤的時間兩部分組成。本文將路段的允許平均行駛速度劃分為如表1所示的八個等級，則路段的行駛時間tij為路段的距離和行使速度的比值，即tij=dij/vij。利用道路等級來確定各交叉口的平均延誤時間ti，每條路段均有兩個交叉口，路段(i，j)的交叉口延誤時間為(ti+tj)/2，則每個路段的權重如式(2)所示。

wij=tij+(ti+tj)/2(2)

表1 道路等級

等級12345678

速度/km/h510152025303540

2 最大最小蟻群算法

蟻群算法是一種求解組合優化問題的啟發式搜索算法，它的正反饋機制確保了最優化過程的快速性，而其分布式計算特性又避免了過早收斂，既有貪婪啟發式的搜索特性，又能在搜索的早期獲得可以接受的問題解[3]。但基本蟻群算法在求解大規模的復雜問題時，容易出現早熟、停滯現象。最大最小蟻群算法對基本蟻群算法進行了許多改進，在一定程度上避免了過早停滯現象的發生[2]。最大最小蟻群算法的步驟如下:

a)規定群體規模為m的蟻群。

b)初始化信息量。為使螞蟻在算法的初始化階段能夠更多地搜索新的解決方案，將信息量初始化為最大值τmax。

c)狀態轉移規則。將初始節點S置于各螞蟻K的解集Ck中，螞蟻K(K=1，2，…，m)按狀態轉移規則式(3)和(4)移至下一個節點j，并將j加入當前解集CK中。

S=arg maxj∈allowedKταij#8226;ηβij q≤q0

pKijother(3)

PKij=ταijηβij/∑j∈allowedKταijηβij j∈allowedK0other(4)



其中:PKij表示轉移概率;allowedK表示螞蟻K下一步將要選擇的城市;τij表示邊(i，j)上殘留的信息量;ηij表示邊(i，j)的能見度，即ηij=1/wij。

d)局部搜索。計算各螞蟻的目標函數值，記錄最好解。為加快收斂速度，用局部搜索算法對其進行優化，得到最優值Ctbest。

e)全局信息素更新規則

τij(t+1)=ρτij(t)+Δτij(5)

Δτij=Q/f(Ctbest) (i，j)∈Ctbest

0(i，j)Ctbest (6)

每次迭代只允許本次迭代最優的那只螞蟻進行信息素的更新。同時為避免搜索停滯，把每條邊的信息素濃度限制在[τmin，τmax]之內。

f)重復c)～e)，直至達到最大迭代次數，或者所有螞蟻均選擇了同一條路徑，則算法終止，輸出全局最優解[2]。

3 求解電力線路最佳搶修路徑的改進的最大最小蟻群算法

大量研究表明，最大最小蟻群算法存在兩個主要問題[4～7]:一方面是易于陷入局部最優解，即算法進行到一定程度時，幾乎所有的螞蟻找到了一條完全一致的路徑。這時算法陷入僵局，并且不能進一步擴大搜索空間，以致無法找到全局最優解。另一方面是最大最小蟻群算法的收斂速度慢，導致算法在全局最優解與局部最優解之間振蕩。

1)螞蟻按照式(3)和(4)來選擇往哪個節點轉移 如果q0取值太大，大多數的螞蟻就會傾向于選擇具有最大信息素的邊，這樣將導致大多數的螞蟻搜索到同一條路徑，不利于找到全局最優解，很容易陷入局部最優;如果q0取值太小，具有最大信息素的邊被選擇的概率會相應減小，而其他邊被選擇的概率將大大增加，這樣就會擴大搜索空間，但是收斂速度變慢。從上述兩方面考慮，本文將迭代次數劃分為三個階段，每個階段取不同的q0，如式(7)所示。

q0=c1 0<cycle≤n0

c0 n0<cycle≤n1

c1 n1<cycle≤nmax(7)

在此分段函數中，n0和n1是迭代次數，nmax是最大迭代次數，0.8

2)傳統的局部搜索算法 其接受準則使得算法進程方向單軀直入，即從初始解開始，沿逐次更優的方向直至停止準則限定的某個局部最優解。除進程方向將初始解引導到整體最優解的極特殊情況外，最優解的質量與初始解的質量間存在某種相依關系。而在隨機初始解的情況下，最優解的質量無法得到保證。因此，本文利用噪聲擾動算法對每次迭代的最優解進行局部搜索。

噪聲擾動方法是Charon等人[8，9]在1993年提出的一種局部搜索算法，并在解決組合優化問題時取得了良好的效果。噪聲擾動算法的基本思想是:為計算組合優化問題的最優解，并不直接考慮真實值，而是給它增加一個逐漸降低的噪聲。噪聲是特定區間上服從均勻分布的一個隨機變量。如今已經有多種方法來增加噪聲。其中一種方法是給實際值增加一個噪聲，然后對增加噪聲的量進行下降搜索。本文是給適應值f(C)(即沿路徑C從起始點到達目標點所耗費的時間，此路徑上所有邊上的權重之和)的增量Δf(C，C′)增加一個噪聲，即當產生當前解C的一個鄰域解C′時，是否用C′替代C成為當前解，不是利用實際增量Δf(C，C′)，而是利用式(8)給出的噪聲增量參與運算[5～7]。

Δfnoised(C，C′)=Δf(C，C′)+ρK(8)

其中:ρK代表每次循環K的噪聲，并且依賴于噪聲等級NR。ρK是一個區間上的隨機變量，并且這個區間范圍隨著迭代過程不斷縮小。例如在區間[-NR，NR]上，按照一定的概率分布取得噪聲值ρK，NR每隔一定的迭代次數即進行一次下降。隨著迭代次數的不斷增加，最后從rmax一直下降到rmin。為了在方法的最后階段得到適應值函數f的真實值，一般讓NRmin取值為0。但實際上，當NR取值很小時，局部搜索算法就已經不進化了。因此，NR沒有必要減小到0，否則只會白白浪費CPU的時間。所以，本文讓NRmax按照式(9)下降。

μ=rmax-rmin/[(total_nb_it/fixed_rate)-1](9)

其中:total_nb_it是局部搜索算法總的迭代次數;fixed_rate是某個噪聲等級下算法的迭代次數。對蟻群算法每次迭代的最優解進行局部搜索的噪聲擾動算法。

noise-method(C)的步驟如下:

a)當前解C(a0(S)，a1，a2，…，ai，…an(T));

b)全局最優解best_sol=C;

c)r=rmax;

d)當前迭代次數nb_it=0;

e)重復以下步驟:

nb_it=nb_it+1;

調用neighborhood(C)產生鄰域解C′;

取[-r，+r]上服從均勻分布的隨機數ρ;

計算Δfnoised(C，C′)=Δf(C，C′)+ρ;

若Δfnoised(C，C′)<0，則C←C′;

若f(C)

若nb_it mod fixed_rate=0，則縮小r的值;

f)直到nb_it=total_nb_it;

g)返回best_sol。

3)利用噪聲擾動算法對每次迭代的最優螞蟻進行局部搜索時，需要利用neighborhood(C)來產生當前解的鄰域解 由于最佳搶修路徑問題區別于傳統的TSP問題，即每個螞蟻找到的路徑中含有的中間節點的個數不同，不能利用傳統的2-opt方法產生鄰域解。本文基于變異思想和A算法，提出了一種產生鄰域解的新方法。此方法的主要思想為:假設當前解為C，規定一個[0，1]的數PL。隨機選取C中的一個中間節點ai，并產生一個[0，1]的隨機數Pi。若Pi

Neighborhood(C)產生鄰域解的步驟如下:

a)隨機產生當前解C中間節點ai，產生Pi;

b)若Pi

c)利用1)～8)搜索ai-1～ai+1的一條路徑，進而得到一個鄰域解C′。

(a)open={ai-1}，f(ai-1)=g(ai-1)+h(ai-1)。 

(b)如果open表為空，則失敗退出。

(c)取出open表中的第一個元素acurrent。

(d)如果是目標節點ai+1，則成功退出。

(e)從open表中刪除acurrent，放入closed表。

(f)擴展acurrent形成子節點的集合{mi}。計算f(acurrent，mi)=g(acurrent)+len(acurrent，mi)+h(mi)，如果miopen且miclosed，則將mi放入open;如果mi∈open且f(acurrent，mi)

(g)把open表中的元素按f值從小到大排序。

(h)轉步驟(b)。

4 計算機實現和仿真結果

仿真實驗1 設定參數:α=1，β=5，ρ=0.9，m=30，nmax=100，τmax=10，τmin=0.1，n0=20，n1=40，c1=0.88，c0=0.26，rmax=10，rmin=5，total_nb_it=50，fixed_rate=5，Vmax=40 km/h。圖1是分別用最大最小蟻群算法和改進后的最大最小蟻群算法求解的電力線路最佳搶修路徑，并記錄每次迭代最優個體的適應值和最優解。仿真結果如圖2所示。

雖然最大最小蟻群算法和改進后的最大最小蟻群算法找到的最優解均為1-2-5-9-13-15-16，但從圖2可以看出，最大最小蟻群算法在0～20代波動特別激烈，在20～40代波動稍微平緩，而在41～49代每代的最優值穩定在23.11一段時間后又跳到36;而改進的最大最小蟻群算法在0～8代曲線下降迅速，在10～40代曲線波動相對激烈，在41～49代曲線趨于平緩?？梢娮畲笞钚∠伻核惴ㄒ子谙萑刖植孔顑灲?，且收斂速度慢;而改進的最大最小蟻群算法的收斂速度較快，且通過引入局部搜索算法擴大的搜索空間，不易陷入局部最優解。

仿真實驗2 讓噪聲擾動算法中的噪聲等級上界rmax變化為6～15，分別記錄不同rmax時，改進的最大最小蟻群算法每次迭代的最優螞蟻的適應值的變化趨勢如圖3～5所示。

圖3～5中，橫軸為迭代次數，縱軸為每次迭代的最優個體的適應值。從圖3可以看出，當rmax取值為6～9時，曲線波動較為平緩;當rmax取值為11～15時，曲線波動前期較為激烈，后期趨于平緩。從圖4可以看出，當rmax取值為10時，0～4代曲線下降較快，5～30代曲線波動比較厲害，30～50代曲線波動較為平緩?？梢姼倪M的最大最小蟻群算法在rmax取值為6～9時，雖然收斂速度快，但易于陷入局部最優。從圖5可以看出，當rmax取值為11～15時，雖然擴大了算法的搜索空間，但收斂速度慢;當rmax取值為10時，收斂速度進化階段前期和后期都比較快，易于收斂到全局最優解，進化階段的中期收斂速度比較慢，有益于擴大搜索空間。所以在求解電力線路最佳搶修路徑時，噪聲擾動方法的rmax取值為10比較合理。

仿真實驗3 讓噪聲擾動算法中的噪聲等級下界rmin變化為0～10，分別記錄不同的rmin時，改進的最大最小蟻群算法每次迭代的最優個體的適應值。

圖6～8中，橫軸為迭代次數，縱軸為每次迭代最優個體的適應值。

從圖6可以看出，rmin取值為[0，4]時，改進的最大最小蟻群算法在0～10代曲線下降很快，在10～20代波動比較激烈，在20～50代波動平緩;rmin取值為[0，4]時，收斂速度過快。從圖7可以看出，當rmin取值為5時，改進的最大最小蟻群算法在0～10代下降稍快，在10～40代波動比較激烈，在40～50代波動特別平緩。從圖8可以看出，當rmin取值為[6，10]時，在0～20代波動相當激烈，在20～33代波動相對平緩，在35～50代波動特別平緩。總結如下:rmin取值為[0，4]時，收斂速度過快;當rmin取值為[6，10]時，收斂速度過慢;當rmin=5時，收斂速度比較快。因此，利用改進的最大最小蟻群算法求解電力線路最佳搶修路徑時，噪聲擾動算法的rmin取值為5較為合理。

5 結束語

最大最小蟻群算法雖然改進了蟻群算法的許多不足，但是仍存在一些問題。針對電力線路最佳搶修路徑問題，本文提出了改進的最大最小蟻群算法。此算法利用變異思想和A算法產生鄰域解，并結合噪聲擾動算法進行局部搜索。同時，提出了一些方法來解決算法的收斂速度慢和易于陷入局部最優解的方案。仿真實驗證明了改進的最大最小蟻群算法優于最大最小蟻群算法，并且證明了當rmax=10，rmin=5時的求解質量最好。

參考文獻:

[1]李士勇，陳永強，李妍. 蟻群算法及其應用[M].哈爾濱:哈爾濱工業大學出版社，2004:200-207.

[2]STUTZLE T，HOOS H H. Max-min ant system[J]. Future Generation Computer Systems， 2000， 16(19): 889-914.

[3]謝民， 高利新.蟻群算法在最優路徑規劃中的應用[J]. 計算機工程與應用， 2008，44(8):245-248.

[4]賴金富，李向新. 基于改進蟻群算法在最短路徑搜索中的應用[J]. 昆明冶金高等?？茖W校學報，2008，24(1):59-62.

[5]陳星宇， 金惠云， 肖偉. 求解旅行商問題的高效自適應混合螞蟻算法[J]. 計算機工程與應用， 2007，43(27): 84-87.

[6]萬旭，林健良，楊曉偉. 改進的最大—最小螞蟻算法在有時間窗車輛路徑問題中的應用[J].計算機集成制造系統，2005，11(4):572-576.

[7]唐增明，蔣泰. 一種改進的動態自適應最大—最小蟻群算法[J]. 計算機與現代化，2008(3):90-92.

[8]CHARON I，HUDRY O. The noising method: a new method for combinatorial optimization[J]. Operation Research Letters，1993， 14(3): 133-137.

[9]CHARON I， HUDRY O. Application of the noising method to the traveling salesman problem[J]. European Journal of Operational Research， 2000，125(2): 266-277.