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

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

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

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

　　在實驗過程中，分別記錄每一代的最優(yōu)個體。分析圖4可以得到，遺傳算法在第13代找到最優(yōu)路徑35.33，遺傳禁忌算法在第7代找到最優(yōu)路徑33.81?？梢?，改進(jìn)的遺傳禁忌算法的收斂性明顯優(yōu)于標(biāo)準(zhǔn)遺傳算法。

　　仿真實驗2　在交通網(wǎng)絡(luò)圖中，抽取5個不同頂點數(shù)V，不同邊數(shù)E的拓?fù)鋱DG(V, E)。利用改進(jìn)的遺傳禁忌算法分別對這5個拓?fù)鋱D求取最佳搶修路徑。
　　分析表1，隨著網(wǎng)絡(luò)規(guī)模的擴大，算法的執(zhí)行時間為4.2s～15.2s，得到最優(yōu)解的概率為86 %～96 %?？梢钥闯?，改進(jìn)的遺傳禁忌算法的執(zhí)行時間短，并且得到最優(yōu)解的概率相對不錯。

　　仿真實驗3  分別利用Dijkstra、A^*算法、標(biāo)準(zhǔn)遺傳算法和改進(jìn)的遺傳禁忌算法求取仿真實驗2中給出的5個網(wǎng)絡(luò)拓?fù)鋱D的最佳搶修路徑，記錄其平均執(zhí)行時間和得到最優(yōu)路徑的概率。
　　觀察表2和表3的實驗數(shù)據(jù)，總結(jié)有如下兩條：首先，改進(jìn)的遺傳禁忌搜索算法的執(zhí)行時間雖然比A^*算法和標(biāo)準(zhǔn)遺傳算法長，但是比Dijkstra算法短。 再者，遺傳禁忌搜索算法得到最優(yōu)解的概率雖然沒有Dijkstra高，但是高于標(biāo)準(zhǔn)遺傳算法和A*算法?？梢?，權(quán)衡執(zhí)行時間和得到最優(yōu)解的概率，本文提出的遺傳禁忌搜索算法相對來說是一個理想的求解電力線路最佳搶修路徑的算法。

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

參考文獻(xiàn)
[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]  李敏強，寇紀(jì)松，林丹. 遺傳算法的基本理論與應(yīng)用[M]. 北京：科學(xué)出版社，2002：120-158.
[3] 王凌.智能優(yōu)化算法及其應(yīng)用[M]. 北京：清華大學(xué)出版社，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.