配電網重構中遺傳算法編碼策略的研究

三峽大學電氣與新能源學院 葉 婧 趙辛欣

1.引言

配電系統具有閉環結構、開環運行的特點，包含了大量的常合分段開關及少量常開的聯絡開關。在正常的運行條件下，配電調度員根據運行情況進行開關操作以調整網絡結構。通過配電網網絡重構，一方面平衡負荷，消除過載，提高供電電壓質量；另一方面降低網損，提高系統的經濟性。配電網絡重構是提高配電系統安全性和經濟性的重要手段。理論上，在滿足各種運行約束條件下，以網損最小為目標的配電網絡重構問題是一個非線性組合優化問題。其中作為優化變量的開關數量巨大，窮舉搜索將面臨“組合爆炸”問題。

遺傳算法(genetic algorithm，縮寫為GA)是模擬生物進化過程的計算模型，由于GA的整體搜索策略和優化時不依賴梯度信息的特點，使其在自適應控制、組合優化和模式識別等方面得到了廣泛應用。近幾年來，不少學者將GA應用于以網損最低為目標的配電網重構中。由于GA并不直接作用于待求變量本身，而是先將待求變量進行編碼，然后GA對這些編碼進行交叉、變異等操作，從而找到最優解，所以在使用GA前必須先選擇一種編碼方法。一般說來，由于GA的魯棒性，它對編碼的要求并不苛刻。但是，GA中編碼的策略或方法對遺傳操作，尤其是對于交叉操作的功能有很大的影響，在很多情況下，編碼形式也就決定了交叉操作。本文將針對現有的遺傳算法編碼方式的計算效率進行分析。

2.傳統的2進制編碼

用2進制表示時，一般將網絡中的開關狀態用0和1表示，每個開關占染色體的1位，0代表分閘狀態，1代表合閘狀態，各支路狀態組合在一起就形成了一條染色體，染色體的長度為網絡中開關的數目。如圖1所示的饋線系統的開關狀態可用二進制表示為：[1110111110111110]。種方案簡潔明了，但在GA的運行過程中會產生大量的不可行解，嚴重影響了GA的計算效率。

對于圖1所示的配電系統，一共有16條支路，一般認為每條支路上均有開關，按上述編碼方法，染色體長度為16，該配電系統GA空間將有216＝32758個染色體。通過組合數學可以得出圖1中的配電系統GA表現型個體為190個[1]。有效候選解只占 1 90 / 32768= 0 .5798%。這表明：按照傳統的二進制編碼方式進行編碼，在GA運行過程中，只能產生非常少的可行解，因此按這種編碼方式，搜索效率是非常低的。

圖1 IEEE典型三饋線系統

3.基于環路的2進制編碼

配電網在正常運行時呈放射形，并且每個節點的負荷都必須有電能的供給，因此配網中開關的開合并不是任意組合的。為了提高有效侯選解比例，很多文章提出了基于環路的2進制編碼策略[1，3，4]，對于環路，不同的文章定義不同，由此也產生了不同的編碼方式。

3.1 一個聯絡開關對應一個環路的編碼策略

文獻[1，4]提出采用構成同一環路的開關在同一基因塊內、相鄰開關在染色體中相鄰的染色體編碼策略。文獻[1，4]中一個環路對應著一個聯絡開關。如果一個聯絡開關合上，則會構成一個小環，必須在此環中打開一個分段開關，使配網保持輻射型。采用這種編碼策略，不可行解數目大大降低。文獻[1]對圖1的配電系統編碼如表1所示。

表1 圖1的編碼結果

文獻[1，4]采用交叉操作只進行對應基因塊的交換，而變異操作限制在基因塊內的遺傳操作策略。在同一個環內即同一個基因塊內，選擇一個開關斷開，以此形成初始解。變異操作時，首先選定一基因塊，然后在確定的基因塊中隨機選定一位基因將其值取反，產生不可行解后，再按一定的方式將不可行解消除。

采用這種編碼方式，相對于傳統的二進制編碼方式而言，產生初始解以及經過交叉變異產生的候選解中不可行解的比例大大降低。但是復雜的配電系統環路間存在公共開關的可能，故各環路對應基因塊可能重疊。因此，這種一個聯絡開關對應一個環網，一個環網內只允許有一個斷開開關的編碼方式，在存在公共開關的系統中，仍然會產生一些不可行解。

3.2 一個回路對應一個環路的編碼策略

文獻[3]提出一種新的環路的概念，即環路指的是配電網的開關全部閉合時，在網絡中形成的閉環回路，有2種形式：（1）從配電網的一個電源節點出發，每個節點只經過一次，到達另一個電源節點的環為第一類環；（2）從配電網的某一個節點出發，每個節點只經過一次，又回到這個節點的環稱為第二類環。

對圖1所示的網絡，按照文獻[1]中環路的定義，對應的三個環路為[1 5 10 9 7 6]；[6 11 16 15 12]；[1 2 3 4 14 13 12]。而按照文獻[3]環路的定義，則圖1中含有五個環路，分別是[1 5 10 9 7 6]；[6 11 16 15 12]；[1 2 3 4 14 13 12]；[1 5 10 9 7 11 16 10 12]；[2 3 4 14 13 15 16 11 7 9 10 5]。其中前4個環路為第一類環，第5個環為第二類環。

文獻[3]產生初始解的方法為：(1)令所有基因值均為1；(2)按順序判斷各環路中是否有斷開的開關，如果沒有，則隨機斷開該環路中任一個開關，這樣可以保證不形成閉環；如果已經存在，不論幾個，都不再操作，因為當一個環路與其它環路有公共開關時，可能出現一個環路中斷開多個開關的情況，但不會行成孤島。

按這種方法產生的初始解都為可行解。這種方法避免了文獻[1]中的初始解出現不可行解情況，但是在交叉和變異過程中，含有公共開關時，仍然可能產生不可行解。

4.十進制編碼策略

4.1 基于環路的編碼策略

采用二進制編碼染色體的長度很長，采取開關狀態為控制變量，用0或1表示，并且不采用任何縮短染色體長度策略時，染色體的長度為網絡開關數總和。基于上述原因文獻[2]提出了十進制編碼規則。

首先將全網的聯絡開關以自然數編號，并在每個聯絡開關所確定的環網內將開關單獨編號（從1到小環里的開關總數）。遺傳編碼以聯絡開關確定的小環網為基因位，該位上的值是該環網里打開的開關編號，基因位上的取值是受限制的，必須是正整數，并且從1到小環里的開關總數。染色體長度等于聯絡開關數（環網數）。

文獻[2]中環路的定義同文獻[1]中相同，即一個聯絡開關對應著一個環路，一個環路只能存在一個斷開的開關。采取這種編碼方式，有效地縮短了染色體的長度，但對于環路間含有公共開關的復雜配電網，由于公共開關，與文獻[1]中的方法存在著同樣的問題，在初始解的形成和基因操作過程中會產生不可行解。并且文獻[2]中所提方法需要對聯絡開關進行編號，并且在每個環網中需要對每個開關進行重新編號，與二進制編碼相比更為復雜。

4.2 基于隨機生成樹策略的編碼方法

常規的編碼策略容易產生不可行解，文獻[7]利用圖論的避圈策略生成樹，保證重構后的結果為放射形，避免了不可行解的產生。

對配網中所有的開關支路進行十進制編碼，將不在環路中的開關始終保持閉合狀態，將環路中的所有支路按順序組成一個支路序列。如圖1所示網絡，可形成染色體:[5 10 9 7 11 16 15 2 3 4 14 13]，改變基因座的順序可以得到其它的染色體。任一染色體對應著可以生成一棵樹，通過圖論“避圈法”文獻[7]保證了所生成的樹都為連通的放射型。

文獻[7]所提方法，在配電網重構過程中可以避免不可行解的產生，提高了計算效率。但在染色體解碼過程中不如其它方式簡單直觀。

5.總結

由于GA適用于解決大規模非線性組合優化問題，許多學者對其在配電網重構中的應用進行了嘗試。本文較全面地分析比較了編碼策略對重構計算效率的影響。隨著編碼策略不斷地改進，侯選解的有效比例已經大幅度地提高甚至可以完全避免不可行解的產生。但如何辯識和修復不可行解以及提高解碼效率是遺傳算法需要研究的問題。

[1]畢鵬翔,劉健,劉春新.配電網絡重構的改進遺傳算法[J].電力系統自動化,2002,26(2):57-61.

[2]麻秀范,張粒子.基于十進制編碼的配網重構遺傳算法[J].電工技術學報,2004,19(10):65-69.

[3]楊建軍,戰紅,陳憲國.基于遺傳算法并避免不可行解的配電網絡重構優化[J].電力系統保護與控制,2008,36(17):43-46.

[4]唐斌,羅安,王擊.改進遺傳算法的編碼策略及其在配電網重鉤中的應用[J].繼電器,2004,32(13):35-39.

[5]文勁宇,劉沛,程時杰.遺傳算法及其在電力系統中的應用[J].電力系統自動化,1996,20(10):57-60.

[6]李曉明,黃彥浩,尹項根.基于改良策略的配電網重構遺傳算法[J].中國電機工程學報,2004,24(2):49-54.

[7]歐陽武,程浩忠,張秀斌等.基于隨機生成樹策略的配網重構遺傳算法[J].高電壓技術,2008,34(8):1726-1730.