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

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

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

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

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

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

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

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

參考文獻(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]  李敏強(qiáng)，寇紀(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.