配電網絡重構的改進混合遺傳算法

本文提出一種基于改進的混合遺傳算法的配電網重構算法，在算法中使用可操作開關支路的整數編號的排列順序來表示染色體，并通過譯碼器的設計來映射染色體所對應的輻射狀網絡結構，避免了產生不可行解的情況，大大提高了算法的運算效率。同時在算法中引入了局部尋優算子，改善了算法的局部尋優性能。算例結果表明本算法是高效，可行的。
　　關健字 網絡重構；遺傳算法；局部尋優算法

A refined hybrid genetic algorithm for
distribution network reconfiguration

ZHENG Xin1，YANG Li-xi1，C.T.Tse2

(1.College of Electrical Engineering，ZhengZhou University，
ZhengZhou，450002，China；
2.The Hong Kong Polytechnic University，Electric Engineering?
Department，China)

　　Abstract: This paper proposes an improved solution for distribution network reconfiguration based on a refined hybrid genetic algorithm. In the algorithm the "the integer permutation" encoding is adopted with each integer representing one controllable switch. A decoder is designed to decide the final network configuration corresponding every chromosome. A local search operator is combined with the genetic algorithm which improve the local optimal capability of the algorithm. The computational result on a tested system demonstrate the algorithm is feasible and efficient.?
　　Key words: Network reconfiguration；Hybrid genetic algorithm；Local search algorithm；

1 引言
　　基于網損最小的配網重構問題是一個典型的非線性、多約束的整數組合優化問題，配電網的輻射狀結構和弱環網特性是其重構的前提條件。基于圖論，配電網的結構可以用圖G(N,B)描述，N表示電源節點和負荷節點的集合，B表示饋線段集合，配網的輻射狀結構就由圖的多個樹來組成，T={t1t2t3t4...tn,l1l2...lm}，其中樹支t為供電支路，連支l為聯絡支路。這樣，配網重構問題，可以被描述為在圖中尋找一個使得總網損最小并滿足運行約束的樹狀結構。一個大型的配網包含眾多的節點和支路，因此圖中支撐樹的組合數目極大，若窮舉所有的樹，算法將非常的低效。
　　遺傳算法具有全局收斂性、無可微性要求、具有很好的魯棒性等優點，特別適合于求解組合優化問題。另外，與一般的隨機搜索方法進行的盲目無向搜索不同，遺傳算法進行的是高效有向的全局搜索，能夠逐步地逼近并收斂于全局最優解。因此，遺傳算法在配網重構中得到越來越廣泛的應用。
　　但是，遺傳算法對于求解配網重構這樣的非線性組合優化問題，還存在兩個重要的缺陷，一是父代的優質基因結構對于子代影響甚小，采用常規遺傳算法，收斂速度相當慢；二是配網重構是一個強約束的問題，對于電流、電壓等約束，可以用懲罰因子來進行約束，但對于出現環網和孤島的組合無法用一個合適的評價函數來進行評價。文獻[1]-[4]提出了不同編碼、雜交和變異算子設計方法雖然在一定程度上提高了算法的效率，但是這些基于二進制編碼方法的算法在產生下一代的時候都不可避免地出現大量的不可行解。在這些文獻中對于不可行解的處理方法分為兩種，一種是刪除，補充可行解進入新生代；另一種方法是修補，將不可行解的網絡結構通過打開開關解環，合上開關消除孤島，使不可行解變為可行解。這兩種方法雖然在理論上是可行的，但只適合于每一代出現很少量的不可行解的情況。在一個復雜、多環的配網中，這些算法在每一代中都將產生大量的不可行解，要耗費大量的時間來判斷解是否可行，而補充新的可行解與修補不可行解也是非常困難和耗時的，增加了算法的復雜度。同時由于進行大量的修補和補充新個體，子代不能保持與父代的親體相似性，父代中的優質基因結構在子代中遭到完全破壞，算法最終可能蛻變成盲目的隨機搜索，收斂速度慢，甚至出現不能收斂的現象，失去了遺傳算法的意義。
　　本文提出一種改進的混合遺傳算法，在常規的遺傳算法中加入局部尋優算子來改善算法的局部尋優性能，同時通過編碼器和譯碼器相結合的設計方法完全避免了出現不可行解的問題，進一步提高了遺傳算法的搜索效率，從而加快遺傳算法的收斂速度。

2　配網重構的數學模型
　　配網重構的目的就是在滿足運行約束的前提下，使系統的網損達到最小。因此配網重構的目標函數可以表示為：
?
其中:Ie是支路e的電流，Re是支路e的電阻，Ke表示支路的開關狀態，1表示支路開關處于閉合狀態，0表示支路開關處于斷開狀態；(2)式代表支路電流過載約束，Iemax表示支路電流的上限；（3）式代表節點電壓約束，Vimin、Vimax分別表示節點的電壓的上下限，（4）式代表輻射狀網絡且不出現孤島的拓撲約束。本文通過前推回代的潮流算法來求解配網網損，并用約束條件進行驗證。

3　遺傳算法在網絡重構中的改進
3. 1 編碼和譯碼策略
??? 編碼設計就是如何用一個染色體來表示一個唯一的配電網網絡結構；本文將配電網中所有的可操作的開關支路進行整數編號，染色體是由所有這些支路號的隨意排列組成，染色體中不允許出現相同的支路號，染色體的長度為可操作開關支路的數目。如一個16節點的配電系統，16條支路從1到16進行編號，其中一個染色體就可以表示為：
??? [1 2 3 5 6 7 8 9 10 12 14 15 16 4 11 13]
??? 對于遺傳算法而言，僅隨機產生不同順序的串，為了使串表示一個有效的網絡拓撲，這就需借助于譯碼器的實現。譯碼器的目標就是如何根據染色體的編碼來構造出一個唯一的支撐樹。
??? 本文在譯碼器的設計中，采取避圈法生成樹的構造方法：圖開始時，只有節點沒有邊，樹支和連支的集合為空，按照染色體中支路號從左到右的排列順序，選擇支路號對應的一條邊來加入圖中；如果與圖中的邊不構成環，就作為樹支放入樹支集合中，否則作為連支放入連支集合中，重復這個過程，直到不能進行為止；這樣最后將形成樹的形式，樹支即為閉合支路，連支為打開的聯絡支路。可見在避圈法生成樹的過程中，在一個弱環中先加入的邊會成為樹支，而最后加入的邊由于會形成環，只能作為連支，所以加入邊的順序不同也就是染色體的不同產生的樹就有可能不同，同時通過這種方法每一個染色體必然只對應出唯一一個樹狀結構的配網。雖然不同的染色體對應的樹可能是一樣的，如在上面的樹如果表示為一個染色體，隨意改變中樹支的排列順序和隨意改變連支的排列順序根據避圈法生成的樹都是一樣的，但是我們可以在產生初始代時通過連續大范圍的交叉轉換來減少出現等價染色體的機率。在本文的算例中，通過特定的交叉和變異方法在每一代中只有很少的機率出現等價或相同的染色體。由于這種通過譯碼器構造支撐樹的方法，對應的很自然的就是可行解，所以就不需要再判斷網絡結構是否符合網絡拓撲約束的問題，省去了各種對不可行解的處理步驟，大大提高了解的質量和算法的運算效率，加快了解的收斂速度。
3.2 交叉算子設計
??? 基于構造支撐樹的順序編碼，若采用簡單的一點或多點交叉策略，必然以極大的概率產生不可行的染色體，因此本文采用與部分匹配交叉比較類似的交叉方法，方法如下：
??? (1)隨機在串中選擇一個交配區域，如兩父串及交配區域選定為:
??? A=12|3456|789???? B=98|7654|321
??? (2)將B的交配區域加到A的前面或后面，A的交配區域加到B前面或后面得到:
??? A′=7654|123456789???? B′=3456|987654321
??? (3)在A′和B′中自交配區域后依次刪除與交配區相同的城市碼、得到最終的兩子串為:
??? A″=765412389?? B″=345698721
??? 與其它方法相比，這種方法在兩父類相同的情況下仍能產生一定程度的變異效果，這對維持群體內一定的多樣化特性有一定的作用，實驗中也顯示了較好的結果。
3.3 變異
　　為了維持群體內的多樣化，本文采用隨機連續多次對換的變異技術，使可行解在順序上有了較大的變化，以抑制交叉中有可能產生的同化作用。
　　所謂隨機對換變異，就是隨機選擇串中的兩點，交換其編碼。例如對于串A:
????? A=12|3456|789
　　如果隨機產生的交換點是2和7，則串A中的第2點和第7點將對換，對換后，串A變為：
???? A′=17|3456|289
　　由于經過一次對換后，A′仍然有可能與A表示為同一個網絡結構，所以本文采取連續多次的對換操作，來增強變異的效果。
3.4 更新
　　本文采用代間更新的方式，由代溝G控制每一代群體中個體被更新的百分比，在t代N個個體中有(1-G).N個適應度最高的個體被選擇完全復制到t+1代中去，即每代只產生N*G個新個體。代間更新的方式為遺傳算法利用優化過程中的歷史信息提供了條件，加快了遺傳算法的收斂過程，但當代溝過小時，可能會造成遺傳算法的過早收斂，G一般取0. 3～1，本文取0. 8。
3.5 適應度函數
??? 由于遺傳算法是一種在給定的解空間內不受約束的隨機搜索算法，因此必須構造一個精確的適應度函數指導遺傳算法的搜索方向向著最優解逼近。本文中適應度函數由目標函數和懲罰函數組成，定義如下：
?
其中:B1、B2、B3是懲罰因子，通常取較大的數，以加大懲罰力度。
??? 計算個體的適應度，需要用譯碼器對個體進行解碼，求出其對應的網絡結構，然后調用潮流計算程序計算出節點電壓和支路電流代入公式（5）即計算出個體的適應度值。當個體違反電流和電壓的約束條件時，由于懲罰因子取的比較大，其適應度值將非常的低，從而很容易在進化過程中被淘汰。

4 遺傳算法與局部尋優算法的混合策略
??? 在基本遺傳算法中，存在著局部搜索能力差、收斂速度慢的缺點。如果在遺傳算法框架中加入適當的基于鄰域的局部搜索機制，使遺傳算法與傳統的、基于問題知識的啟發式搜索技術相結合構成一種全局和局部搜索相結合的混合遺傳算法，則可以保證在種群進化的每一代，算法的解都是局部最優解，再通過競爭從局部最優解中選擇產生出優良解。
??? 本文對經過交叉和變異后的染色體執行連續多次的“連支前插”操作，來尋找染色體對應解所在局部解空間的最優點。首先通過解碼器將染色體解成支撐樹的形式T={t1t2t3t4...tn,l1l2...lm}。事實上樹支集合內的排列排序和連支集合內的排列順序的改變對于配網的結構都不產生影響，即適應度是不發生變化的，只有當連支與自己所在環內的其它樹支發生交換，也就是發生了支路交換，才對網絡結構產生影響；連支前插法，就是將連支向前插入至樹支區內，例如將組合T中的連支l1向前插至樹支t4的前面，T的組合變成{t1t2t3l1t4...tn,l2...lm}的形式，這樣將由于先加入而變成樹支，同一環內排在最后的樹支將變成連支，因此實現了支路交換。
??? 本文使用的“連支前插”是一種爬山行為(朝著改進的方向)和連續多次的“前插”操作，如果“前插”使串的適應度提高，則執行操作，如此反復，直至不能再前插為止，最后將重新形成組合替代原來的染色體。這一操作實際上使給定的串改良到它的局部極點，這種局部爬山能力與基本遺傳算法的全局搜索能力相結合在實驗中顯示了良好的效果。如圖1，算法通過局部尋優算子來修復通過雜交和變異產生的新個體，使它到達局部最優點。圖1中父代個體X和個體Y產生出子代個體Z′，通過局部尋優產生出最終個體Z。

5 配網重構的混合遺傳算法流程
　　在給定配電網絡和數據后，應用本算法求解最優運行方案的步驟如下：
　　a.算法首先讀入原始數據進行初始化，設定遺傳算法的最大進化代數，群體規模N，代溝G,染色體長度，雜交概率，變異概率等參數。
　　b.采用支路整數編碼方法隨機產生第一代的初始種群作為父代。并對初始群體的個體進行解碼，調用潮流計算程序，計算個體適應度及群體平均適應度。
　　c.基于賭輪選擇機制從交代中選擇適應度較高的個體進行交叉操作，產生新一代個體。
　　d.對子代個體執行變異操作。
　　e.對子代個體執行“連支前插”操作，使個體得到進一步的改良。
　　f.重復步驟c,d,e，直到子代個體數達到N*G個。
　　g.執行代間更新操作，從父代中復制N*(1-G)個的適應度最高的個體補充到子代中。
　　h.計算子代個體適應度及群體平均適應度，并將子代作為下一輪進化的父代。
　　i.當算法達到預先設定的最大進化代數，算法將結束，并輸出適應度最高的個體所對應的網絡方案。否則轉到步驟c，繼續進行進化。

6 算例分析
　　本文算例采用一個33節點、5聯絡開關的配電網測試系統[4]，如圖2所示。

　　5個常開聯絡開關分別位于支路7～20、11～21，8～14，17～32，24～28上，假設所有支路都裝有分段開關，按照文中的編碼方法，電源支路不參與重構，一直是閉合狀態，不參與編碼，因此染色體長度為35，群體規模取50個，交叉概率取0. 6，變異概率取0. 01。運算程序后，最優重構方案為合上支路7～20、11～21，8～14，17～32上的分段開關，斷開6～7，8～9，13～14，31～32上的分段開關。表1給出了運算結果并與文獻4的算法計算結果進行了比較。

　　本文算法與文獻[1]-[4]所述算法相比，其收斂性能有了很大的提高。采用文獻的基于二進制編碼的遺傳算法，在同樣的算例上常常要進行到300多代才能收斂，而采用本算法進行到40多代就發現最優個體，在100代左右其平均適應度逐漸收斂于最優，同時相對于文獻[1]-[2]，本文在每一代的計算效率也有很大提高。

7　結論
　　在采用遺傳算法來解決配網重構中的大規模組合優化問題時，本文采用支路整數編碼方法實現基因編碼和基于構造支撐樹方法的譯碼器設計方法，避免了生成不可行解的情形，減少了算法的無效搜索，提高了計算效率。同時本文還提出了基于圖論的連支前插法的局部尋優算法，將它作為一個局部尋優算子加入到算法中，提高了算法的局部尋優性能，加快了算法的收斂速度。算例結果表明這種方法是可行、有效的。