摘 要：在分析和研究電力線路最佳搶修路徑的基礎上，提出了一種改進的遺傳禁忌搜索算法來求解電力線路最佳搶修路徑。此算法基于變異思想和A^*算法產生禁忌搜索算法的鄰域解，并利用遺傳算法的階段進化思想減少調用禁忌搜索算法的頻率,進而提高改進的遺傳禁忌算法的執行效率。仿真結果表明在求解電力線路最佳搶修路徑時，遺傳禁忌搜索算法的性能優于其他算法。
　　關鍵詞：遺傳算法；禁忌搜索；最佳搶修路徑；A^*

　　隨著生活水平的提高，電力系統的發展，電力線路逐漸增多，線路故障時有發生。突如其來的自然災害更易造成大面積的桿塔和線路故障，搶修不及時將嚴重影響生產、生活。因此，電力線路最佳搶修路徑的研究就成為當今的一個熱點問題^[1]。
　　電力線路最佳搶修路徑問題就是在檢測到故障地點后，派遣搶修人員及時地到達故障現場，減少故障造成的破壞。現在已經有很多算法來解決此問題，如Dijkstra、模擬退火算法、蟻群算法、遺傳算法。但是隨著網絡規模的逐漸擴大，Dijkstra算法內部的二重循環將使其執行效率嚴重下降。模擬退火算法雖然能找到最優解，但是冷卻參數的設置很難把握^[1]。蟻群算法雖然具有很強的實用性，但易于陷入局部最優解且收斂速度慢。
　　傳統的遺傳算法具有很強的魯棒性，適合于求解電力線路最佳搶修路徑，但是具有較差的局部尋優能力^[2]。然而，禁忌搜索算法具有較強的局部搜索能力^[3]。本文結合兩者的優點，利用遺傳禁忌搜索算法來求解電力線路最佳搶修路徑；同時結合A*算法^[4]和變異思想^[1]，提出了一種禁忌搜索算法鄰域解產生的新方法，并利用遺傳算法階段進化思想，減少調用禁忌搜索算法的頻率，進而提高遺傳禁忌搜索算法的執行效率。
1 電力線路最佳搶修路徑的數學模型
　　電力線路最佳搶修路徑就是交通網絡中搶修人員從物資點到故障點花費時間最少的路徑。所以，需要先找到故障點鄰近的路段交叉口(目的節點T)和物資點鄰近的路段交叉口(起始節點S)，然后在交通網絡拓撲圖中求取S到T的耗費時間最短的路徑。因此，把交通網絡中的路段抽象為平面圖中的邊，把路段交叉口抽象為平面圖中的頂點，形成一個平面圖G(V,E)，其中V為頂點集合，E是邊的集合，如果頂點i到頂點j有直接相連的邊，則X_ij=1，否則Xij=0。Wij是邊(i,j)的權重，即通過路段i→j所花費的時間。最佳搶修路徑就是從S到T的一些中間節點的集合(a₀(S),a₁,a₂,…,a_i ,…,a_n(T))。因此電力線路最佳搶修路徑的數學模型為：
　　　　

　　受到路段行駛速度、交叉路口的延誤、交通管制等交通因素的影響，路段i→j的權重Wij由行駛時間和交叉路口的延誤時間兩部分組成。本文將路段允許平均行駛速度劃分為8個等級^[5]。行駛時間tij為路段的長度d_ij除以行駛速度v_ij，即t_ij=d_ij/v_ij。利用道路等級來確定各交叉口的平均延誤時間t_i，每條路段均有兩個交叉口，則路段i→j的交叉口延誤時間為(t_i+t_j)/2，故W_ij=t_ij+(t_i+t_j)/2^[1]。
2 遺傳禁忌搜索算法的改進
　　GA和TS算法分別具有各自獨特的優點并存在著無法避免的缺點。若能將兩者混合起來使用，則能發揮兩者優勢，有效提高求解質量和均衡算法的運行效率。本文綜合分析了遺傳算法和禁忌搜索算法，提出了一種改進的遺傳禁忌搜索算法來求解電力線路最佳搶修路徑，即利用遺傳算法產生初始群體，經過選擇、交叉、變異操作后，在合適的時機調用禁忌搜索算法來對每個個體進行局部搜索。根據電力線路最佳搶修路徑的特點，此算法的改進主要集中在以下兩點：一方面針對遺傳算法頻繁調用禁忌搜索算法造成時間復雜度大幅度提高的問題，提出了減少禁忌搜索算法調用頻率的新策略；另一方面針對遺傳算法在求解最佳搶修路徑時，產生的每個個體的染色體長度是不同的，提出了禁忌搜索算法鄰域解產生的新方法。
2.1 禁忌搜索算法的調用時機
　　雖然遺傳算法和禁忌搜索算法的結合，使得禁忌搜索算法的強爬山能力彌補了遺傳算法較差的局部搜索能力，但是也存在一些問題。其中最主要的是算法的執行效率問題。遺傳算法頻繁調用禁忌搜索算法，顯然大大地增加了算法的計算復雜度，不利于大規模問題的求解。故本文按照遺傳算法階段進化的思想，確定禁忌搜索算法的調用時機，進而減少禁忌搜索算法的調用頻率。
　　遺傳算法進化初期屬于探索階段，必須充分利用交叉算子探索基因空間的能力，在較大的解空間中搜索全局最優解或其鄰域。此時，可以不調用或者以較小的概率調用禁忌搜索算法。隨著個體的逐漸進化，交叉操作的概率性和隨機性使得群體中的染色體具有局部相似性，這時可適當提高禁忌搜索算法的調用概率。在遺傳算法的進化后期，群體轉向局部搜索的過程。此階段側重個體的局部搜索。由于遺傳算法的局部搜索能力差，這時可以較大概率地調用禁忌搜索算法。經過以上分析，本文將遺傳算法的進化過程劃分為三個階段^[2]。三個階段劃分如下：第一階段[0,T₁]，第二階段[T₁, T₂]，第三階段[T₂, T_g]。其中
　　
2.2 鄰域解的產生
　　對于禁忌搜索來說，鄰域結構的設計是非常重要的。不同的鄰域結構將導致鄰域解的個數及其變化情況不同，對搜索質量和效率有一定的影響，但目前尚無一般定論。再者在電力線路最佳搶修路徑的求解過程中，遺傳算法產生的每個個體代表一條物資點到故障點的搶修路徑，是一些中間節點的集合。因此，本文利用A^*來產生當前解的鄰域解。同時，為解決過多調用A*算法帶來的算法復雜度大幅度提高問題，在鄰域解的產生過程中引入了變異思想。
　　

3 算法實現
　　在求解電力線路最佳搶修路徑問題時，本文提出的改進的遺傳禁忌算法的步驟如圖1所示。首先，在抽取出的交通網絡拓撲圖上，規定初始節點S和目標節點T；然后利用GA產生一些初始路徑，進而通過選擇、交叉、變異操作產生下一代種群；最后，判斷遺傳算法的當前迭代次數是否滿足調用禁忌搜索算法的時機。若滿足，則調用禁忌搜索算法對新一代種群中的每個個體進行局部搜索，接著進行GA的下一次迭代。若不滿足，則直接進入遺傳算法的下一次迭代。重復上述步驟，當滿足終止準則時，則結束迭代過程并輸出最優解。總之，利用改進的遺傳禁忌搜索算法求解電力線路最佳搶修路經的主要步驟是：染色體編碼、適應值函數、初始種群的產生、選擇算子、交叉算子、變異算子、局部搜索和終止準則。
3.1 染色體編碼
    在本文中，染色體的編碼采用字符編碼代替傳統的二進制編碼和實數編碼。它是從初始節點到目標節點的一系列中間節點的集合。再者，由于電力線路最佳搶修路徑是一系列中間節點的集合，所以每個個體的編碼長度是不同的。
3.2 適應值函數
    對電力線路最佳搶修路徑的研究就是要找到一條物資點到故障點耗費時間最少的路徑。按照上文提到的路段權重的確定方法，任一個體(a0(S),a₁,…,a_i ,…,a_n(T))的適應值函數為：
　　
3.3 初始群體的產生
　　每一代的個體之間總是有聯系的，否則進化過程將變得沒有意義。本文采用下面的步驟產生初始種群：
　　（1） 把初始節點作為第一個節點。
　　（2） 從它的子節點中隨機地選取一個節點作為當前節點。
　　（3） 如果當前節點不是目標節點轉步驟（2）；否則繼續。
　　（4） 如果當前節點是目的節點，則終止搜索過程，若此個體含有環路，則消除個體中的最大環，進而產生一個個體。
　　（5） 重復上述步驟，直到產生所有的個體。
3.4 選擇算子
　　本文中選擇了輪盤賭選擇算子。
　　選擇即從當前種群中選擇適應值高的個體以生成交配池的過程。輪盤賭選擇算子是最基本的選擇方法，其中每個個體被選擇的期望數量與其適應值和群體平均適應值的比例有關。輪盤賭選擇算子首先計算每個個體的適應值，然后計算出適應值在群體適應值總和中所占的比例,表示該個體在選擇過程中被選中的概率。由于輪盤賭選擇算子體現了生物進化過程中“適者生存,優勝劣汰”的思想，并且保證優良基本遺傳給下一代個體。故本算法采用了輪盤賭選擇算子。
3.5 交叉算子
　　交叉操作的步驟為：
　　（1） 尋找兩個父代染色體的相同中間節點。
　　（2） 隨機選擇一個相同節點作為交叉點。
　　（3）如果父代個體交叉點前后的內容相同，則取消本次交叉操作；否則繼續。
　　（4） 交換兩個父代個體交叉點后的部分，產生兩個子個體。
　　（5） 檢查產生的兩個子個體是否存在環路，如果存在則消除環路中的最大環。
3.6 變異算子
　　為了增強種群的多樣性，本文提出一種新的變異操作方法來解決電力線路中的最佳搶修路徑問題。
　　（1） 從變異個體X(a₀(S),a₁,…,a_i ,…,a_n(T))中隨機選擇一個中間節點a_i作為變異基因。
　　（2） 把與a_i相連的節點存入集合N(集合N已經提前存入計算機)。
　　（3） 在集合N中隨機選擇一個節點Y，當然節點Y沒有出現在個體X中。
　　（4） 若Y分別和a_i-1、a_i+1相連接，則用Y替代a_i產生一條新的路徑；否則取消這次變異操作。
　　（5） 重復步驟（3）到（4）直到找到一個合適的節點Y取代a_i或者搜索完集合N中的元素。
3.7 局部搜索
　　分析遺傳算法的當前迭代次數Tc，若滿足禁忌搜索算法的調用時機，則對遺傳算法產生的新一代種群中的每個個體K調用禁忌搜索算法進行局部搜索，來彌補遺傳算法較差的局部尋優性。局部搜索算法的步驟為：
　　（1） 設定參數：禁忌表長度為L，迭代次數為T_b，當前迭代次數i=0，候選解個數為m，禁忌表為空，全局最優解S_gbest=K，當前解S_local=K。
　　（2） i>T_b或者n　　（3）利用上文提到的Neighborhood(X)產生當前解的鄰域解，計算鄰域解的個數n。
　　（4）若n　　（5）判斷m個候選解是否滿足藐視準則？若成立，假設滿足藐視準則的最佳候選解為Y，則S_local=Y且S_qbest=Y，修改禁忌表中各元素的任期，并將Y加入禁忌表，轉步驟（7），否則，繼續以下步驟。
　　（6）若存在非禁忌狀態的候選解，則假設非禁忌候選解中的最佳解為Y，那么S_local=Z。同時修改禁忌表中各元素的任期，然后把Z放入禁忌表；若候選解均被禁忌，則解禁最佳候選解X，修改S_local=X。同時修改禁忌表中各元素的任期，然后把X放入禁忌表。
　　（7） i=i+1轉步驟（3）。
3.8 終止準則
　　本算法采用精英保留策略，即若新一代中目標函數的最小值大于上一代目標函數的最小值，則用上一代中的最好個體替換下一代中的最差個體。如果最優個體連續10代保持不變或者達到了遺傳算法的最大迭代次數T_g，則終止進化過程。
4 仿真實驗和結果分析
　　仿真實驗1　在MapInfo平臺和VC++環境下，進行仿真實驗。設置算法參數：種群規模M=10，遺傳算法的最大迭代次數為T_g=50，交叉概率P_c=0.5，變異概率P_m=0.05，禁忌表長度L=3，候選解個數m=3，個體基因變異概率P_L=0.8，禁忌搜索算法的最大迭代次數T_b=5，A^*啟發函數中的V_max=40km/h,起始節點S為N0.1，目標節點T為NO.39。
　　分別用標準遺傳算法和改進的遺傳禁忌算法求解此問題，仿真結果如圖2和圖3粗線部分所示。遺傳算法得到的最佳搶修路徑為1-15-18-29-32-37-38-39，適應值為35.33min。改進的遺傳禁忌算法得到的最佳搶修路徑為1-15-18-29-28-27-26-25-36-39，適應值為33.81min。可以看出，改進的遺傳禁忌算法的性能優于標準遺傳算法。

　　在實驗過程中，分別記錄每一代的最優個體。分析圖4可以得到，遺傳算法在第13代找到最優路徑35.33，遺傳禁忌算法在第7代找到最優路徑33.81。可見，改進的遺傳禁忌算法的收斂性明顯優于標準遺傳算法。

　　仿真實驗2　在交通網絡圖中，抽取5個不同頂點數V，不同邊數E的拓撲圖G(V, E)。利用改進的遺傳禁忌算法分別對這5個拓撲圖求取最佳搶修路徑。
　　分析表1，隨著網絡規模的擴大，算法的執行時間為4.2s～15.2s，得到最優解的概率為86 %～96 %。可以看出，改進的遺傳禁忌算法的執行時間短，并且得到最優解的概率相對不錯。

　　仿真實驗3  分別利用Dijkstra、A^*算法、標準遺傳算法和改進的遺傳禁忌算法求取仿真實驗2中給出的5個網絡拓撲圖的最佳搶修路徑，記錄其平均執行時間和得到最優路徑的概率。
　　觀察表2和表3的實驗數據，總結有如下兩條：首先，改進的遺傳禁忌搜索算法的執行時間雖然比A^*算法和標準遺傳算法長，但是比Dijkstra算法短。 再者，遺傳禁忌搜索算法得到最優解的概率雖然沒有Dijkstra高，但是高于標準遺傳算法和A*算法。可見，權衡執行時間和得到最優解的概率，本文提出的遺傳禁忌搜索算法相對來說是一個理想的求解電力線路最佳搶修路徑的算法。

　　在分析和研究電力線路最佳搶修路徑的基礎上，提出了一種改進的遺傳禁忌搜索算法來求解電力線路最佳搶修路徑。此算法基于變異思想和A*算法來產生禁忌搜索算法的鄰域解，并利用遺傳算法的階段進化思想降低調用禁忌搜索算法的頻率，進而提高禁忌搜索算法的執行效率。仿真實驗表明，遺傳禁忌搜索算法的收斂速度和最優路徑都優于標準遺傳算法，并且在不同的網絡規模下分析遺傳禁忌算法、Dijkstra、A^*算法、標準遺傳算法和遺傳禁忌搜索算法表現出的優良特性。由此可見，遺傳禁忌搜索算法適合于求解電力線路最佳搶修路徑。

參考文獻
[1]  YE Xian Yi ，CHENG Xiao Rong . Research of the best repair path based on an improved ant colony algorithm in power distribution network[C]. Transmission and Distribution Conference & Exhibition，2005：1-5.
[2]  李敏強，寇紀松，林丹. 遺傳算法的基本理論與應用[M]. 北京：科學出版社，2002：120-158.
[3] 王凌.智能優化算法及其應用[M]. 北京：清華大學出版社，2001:36-37.
[4] FU Meng Yin，XUE Bin. A path planning algorithm based on dynamic networks and restricted searchiing area[C]. Proceeding of the IEEE international Conference on Automation and Logistics，2007，8：1193-1196.
[5] LI Qing ，XIE Si Jiang . Path planning algorithm for vehicles based on time-dependant optimization criterion[C]. International Conference on Control and Automation，2007，5：2360-2364.