遺傳災變算法在配電網絡重構中的應用

劉 斌，雷 霞，孔祥清，劉慶偉，劉秋榕

（1.西華大學電氣信息學院，成都610039；2.福建省電力有限公司南平電業局，南平353000）

配電網絡中存在著大量的分段開關和少數的聯絡開關，配電網絡重構就是通過調整網絡中分段開關和聯絡開關的組合狀態，以達到降低網損、平衡負荷、提高供電電壓質量的目的。

配電網重構是一個多目標非線性混合優化問題。目前，配電網絡重構求解的算法主要有：數學優化法[1，2]、傳統的系統分析方法[3-6]和人工智能算法[7-13]。其中，遺傳算法（genetic algorithm）由于具有較好的性能，可得到全局最優解，受到了眾多專家學者的關注。已提出的遺傳算法應用于配電網絡重構，根據配電網絡的結構及運行特點，聯絡開關的狀態可以很方便地用（0/1）直接編碼。針對不可行解的處理，文獻[11]提出不可行解的判定方法對簡單的含有公共支路的雙環網有效，對三環網或更復雜的環網情況無效。文獻[12-13]提出的改良策略，其步驟復雜、計算量大。文獻[9]提出的簡單遺傳算法應用于配電網絡重構的求解存在早熟收斂問題。

本文根據配電網的運行特點，結合圖論理論[14～16]，提出了基于鄰接矩陣隨機生成無供電孤島和環路的配電網絡算法，保證了生成的染色體與可行解之間的一一對映，提高了搜索效率。針對遺傳算法早熟收斂問題，本文引入了災變算子，將遺傳災變算法[17，18]應用于配電網絡重構。

1 配電網絡重構的數學模型

配電網的線損包括線路上導線的損耗以及變壓器的銅耗及鐵損等，一般通過配電網重構只可影響前者，所以線損最小的目標函數可以表示為

式中：W 為系統的有功損耗，可以通過前推回代潮流法求得；ki表示開關i 的狀態，是0/1 離散量，0表示斷開，1 表示閉合；ri表示支路i 的電阻；Pi、Qi表示流過支路i 的有功功率和無功功率；Ui表示支路i 末端節點的電壓。

約束條件為

3）網絡拓撲約束：無供電孤島

式中：Si為流過支路的復功率；Si，max為支路i 的額定傳輸容量；Ui、Ui，max、Ui，min分別為節點i 的電壓及其上下限。

2 供電孤島判斷

定義1 一個由同一電源供電的配電網，當所有開關全部閉合時，其拓撲結構是一個連通圖，記為G，它由V 和E 兩個集合組成G=（V，E），這里V 表示供電節點集合，E表示開關支路集合。

定義2 圖G 的鄰接矩陣A 有如下性質：

式中，Vi、Vj分別表示節點i 和節點j，（Vi，Vj）∈E表示節點i 與節點j 有支路相連。

供電孤島的判斷原理是根據鄰接矩陣的特點，若鄰接矩陣中存在全為零元素的行或列，則網絡必然存在供電孤島。否則逐次刪除網絡的葉節點，則其父節點成為葉節點，然后修改鄰接矩陣。以此類推直至網絡只剩下一條支路為止。算法的步驟如下：

1）根據節點集合V 生成網絡的鄰接矩陣A；

2）判斷鄰接矩陣A，若存在全為0 元素的行或列，則存在供電孤島，算法終止；否則轉步驟3）；

3）找出第1 行非主對角線上的第一個0 元素對應的列值設為k；將鄰接矩陣的第1 行和第k 行進行“或”操作并將其值賦給第k 行，第1 列和第k列進行“或”操作并將其值賦給第k 列；

4）刪除鄰接矩陣A 的第1 行和第1 列并置主對角線元素為0；

5）若鄰接矩陣A 階數為2，該網絡不存在供電孤島，算法終止。否則，返回步驟2）。

3 遺傳災變算法

遺傳災變算法就是在遺傳算法的基礎上模擬自然界的災變現象，當種群出現了超級個體，進化算法的選擇操作往往會讓超級個體的基因以極大的概率遺傳到下一代中，個體間的差異逐漸縮小，有可能使得種群朝著局部最優解的方向進化，不利于全局的搜索。為了進一步提高遺傳算法的全局搜索性能，本文引入了“災變”的概念，“災變”往往是對絕大多數生物的滅頂之災，只有適應能力特別強的物種或者個體才能得以生存，并進入下一代的繁衍。

3.1 染色體編碼

編碼是針對具體問題，選擇合適的編碼方案，完成問題解空間向遺傳算法解空間的轉化。為了更好地反映配電網絡重構問題的結構特征，本文采用二進制編碼方式，且應遵循以下兩個規則。

規則1 不在任何環路上的支路開關必須閉合，其對應基因座上的基因為“1”；

規則2 與電源點相連的開關也應閉合，其對應基因座上的基因也為“1”。

染色體生成步驟如下：

1）生成一個“1”的個數等于分段開關數，“0”的個數等于聯絡開關數的染色體；

2）將染色體映射到網絡形成頂點集合；

3）判斷網絡是否存在供電孤島，若存在則刪除該染色體，返回步驟1）；否則轉步驟4）；

4）染色體生成完畢，算法結束。

3.2 染色體解碼

如前所述，根據配電網閉環設計、開環運行的特點，通過對每個染色體對應的網絡進行供電孤島判斷，以確保遺傳操作的每一個解都是可行的。把每條染色體映射到網絡形成網絡參數矩陣，按潮流方向重新調整該矩陣，調用潮流前推回代法計算程序，求得其對應的目標函數值即網絡有功損耗。采用罰函數法對式（2）的支路功率約束、式（3）的節點電壓降落約束進行處理，則該個體適應度函數為

式中：f 表示個體適應度；Ploss表示網絡的有功損耗；kS、kU及φSi、φUi分別為支路傳輸容量、節點電壓約束的懲罰因子與罰函數。

為克服電壓和功率量綱不統一及其數值差別較大等問題對計算適應度造成的影響，φUi和φSi的計算式為

3.3 選擇

為了克服輪盤賭選擇的盲目性，引入了隨機競爭選擇[15]。其方法與輪盤賭選擇基本相似，即在隨機競爭選擇中，每次按輪盤賭選擇機制選取一對個體，然后讓這兩個個體進行競爭，適應度高的被選中，如此反復，直到選滿為止。

3.4 精英保留策略

在遺傳算法中，由于選擇、交叉、變異等操作的隨機性，有可能破壞掉當前群體中適應度最好的個體。因此，把選擇操作后的當前群體中適度最高個體定義為精英個體。經交叉運算和變異運算后，把適應度最低的個體用精英個體代替，把適應度最高的個體與精英個體比較，如果更好，就用其代替精英個體。

3.5 交叉

本文采用兩點交叉的方法，即隨機產生2 個截斷點的位置，對將進行交叉的兩個染色體的截斷點所夾基因塊進行操作，使交換得到的基因塊和原基因塊上的“0”的個數相等。這種方法可在一定程度上提高解的可行性，但還是可能存在不可行解。因此，還需要對交叉后產生的新染色體進行供電孤島判斷，直至交叉操作產生的可行的個體數與初始種群數相同為止。

3.6 變異

由于變異本身是一種隨機算法，其目的在于保持種群的多樣性，避免算法陷入局部最優。因此，本文的變異采用簡單的替換操作，即隨機生成等數目的適應度值高于參與變異的染色體，并替換之。

3.7 災變判定

為了克服傳統遺傳算法的早熟收斂問題，本文引入災變算法。即，在程序運行到指定代數之前，當連續10 代內最佳染色體沒有任何進化時，則突然增大變異概率以打破原有基因的壟斷優勢。這樣更能保證種群個體的多樣性、防止早熟收斂問題，提高遺傳算法的性能。

應用于配電網絡重構的遺傳災變算法流程如圖1 所示。

圖1 遺傳災變算法流程Fig.1 Flow chart of genetic catastrophic algorithm

4 算例分析

本文算法的交叉率為pc= 0.618，變異率為pm=0.05，實行災變時的變異率為pmc=0.2，進化代數為100 代，程序連續運行50 次。

4.1 算例1

對IEEE33 節點系統[4]進行了網絡重構。該系統為一有5 個聯絡開關的12.66 kV 配電網絡。其負荷有、無功分別為3 715 kW、2 300 kvar。

文中方法與遺傳算法應用于IEEE33 節點系統的重構，其結果比較見表1。

4.2 算例2

對美國PG&E 69 節點系統[10]進行了網絡重構，該系統為一有5 個聯絡開關的12.66 kV 配電網絡。其負荷有、無功分別為3 802 kW、2 695 kvar。

表1 IEEE33 節點配電網重構結果Tab.1 Reconfiguration results of the IEEE33-bus network

采用本文提出的算法，程序連續運行50 次，均能保證在進化次數60 代以內獲得最優解。圖2為69 節點算例采用本文所提方法，繪制出進化代數和當前代最佳染色體對應系統網損的關系曲線。圖中顯示為最好一次進化到48 代取得網損最小值。

圖2 69 節點算例最佳適應度Fig.2 The optimum fitness of 69-bus network

重構前系統的有功損耗為225.0 kW，重構后系統的有功損耗為99.62 kW。系統重構前后比較見表2。

表2 重構前后有功損耗比較Tab.2 The power loss comparison between pre-and post-reconfiguration

應用本文算法重構后所得到的系統最優網絡與文獻[10]所得結果相同。圖3 給出了重構前后系統節點電壓標么值的比較。

從圖中可以看出，重構后系統各節點電壓質量較重構前有了一定的提高，系統最低電壓從0.908 9 升到了0.942 5。

圖3 重構前后節點電壓比較Fig.3 Comparison of node voltages between before and after reconfiguration

5 結語

本文針對遺傳算法應用于配電網絡重構問題產生的不可行解，結合配電網的輻射狀運行的特點，提出了基于隨機生成可行解策略的配電網絡重構，使得遺傳進化在解空間內連續進行，確保每次產生的解均是可行解，又保證了解空間的完備性。通過引入災變算子有效地解決了遺傳算法的早熟收斂問題。通過對IEEE33 節點系統和美國PG&E69 節點系統的重構結果表明所提算法的正確性、可行性。

[1]Merlin A，Back H.Search for a minimal loss operating spanning tree configuration in an urban power distribution system [C]// 5th Power Systems Computation Conference.Cambridge，UK：1975.

[2]Chiang H-D，Jean-Jumeau R.Optimal network reconfiguration in distribution systems.I.A new formulations and a solution methodology [J]. IEEE Trans on Power Delivery，1990，5（4）：1902-1909.

[3]Civanlar S，Grainger J J，Yin H，et al. Distribution feeder reconfiguration for loss reduction [J].IEEE Trans On Power Delivery，1998，3（3）：1217-1223.

[4]雷健生，鄧佑明，張伯明（Lei Jiansheng，Deng Youming，Zhang Boming）. 綜合潮流模式及其在配電系統網絡重構中的應用（Hybrid flow pattern and its application in network reconfiguration）[J].中國電機工程學報（Proceedings of the CSEE），2001，21（1）：57-62.

[5]畢鵬翔，劉健，張文元（Bi Pengxiang，Liu Jian，Zhang Wenyuan）.配電網絡重構的改進支路交換法（A refined branch-exchange algorithm for distribution networks reconfiguration）[J].中國電機工程學報（Proceedings of the CSEE），2001，21（8）：98-103.

[6]王素華，張道乾，馬保軍（Wang Suhuan，Zhang Daoqian，Ma Baojun）.考慮多種負荷方式的配電網絡重構（Distribution network reconfiguration considering multi-load modes）[J].電力系統及其自動化學報（Proceedings of the CSU-EPSA），2009，21（5）：109-112，118.

[7]黃健，張 堯，李綺雯（Huang Jian，Zhang Yao，Li Qiwen）.蟻群算法在配電網重構的應用（Application of ant colony system in distribution reconfiguration）[J].電力系統及其自動化學報（Proceedings of the CSU-EPSA），2007，19（4）：59-64.

[8]張利民，馬強，李振坤，等（Zhang Limin，Ma Qiang，Li Zhenkun，et al）. 基于禁忌克隆遺傳算法的配電網故障恢復重構（Service restoration reconfiguration in distribution network based on tabu clonal genetic algorithm）[J].電力系統及其自動化學報（Proceedings of the CSU-EPSA），2010，22（1）：60-64.

[9]梁勇，張焰，候志儉（Liang Yong，Zhang Yan，Hou Zhijian）.遺傳算法在配電網重構中的應用（Application of the genetic algorithm in the distribution reconfiguration for loss reduction）[J]. 電力系統及其自動化學報（Proceedings of the CSU-EPSA），1998，10（4）：29-34.

[10]余健明，張凡（Yu Jianming，Zhang Fan）.基于改進免疫遺傳算法的配電網重構（Distribution network reconfiguration based on improved immune genetic algorithm）[J].電網技術（Power System Technology），2009，33（19）：100-105.

[11]麻秀范，張粒子（Ma Xiufan，Zhang Lizi）.基于十進制編碼的配網重構遺傳算法（Distribution network reconfiguration based on genetic algorithm using decimal encoding）[J].電工技術學報（Transactions of China Electrotechnical Society），2004，19（10）：65-69.

[12]李曉明，黃彥浩，尹項根（Li Xiaoming，Huang Yanhao，Yin Xianggen）. 基于改良策略的配電網重構遺傳算法（A genetic algorithm based on improvement strategy for power distribution network reconfiguration）[J]. 中國電機工程學報（Proceedings of the CSEE），2004，24（2）：49-54.

[13]楊建軍，戰紅，劉揚（Yang Jianjun，Zhan Hong，Liu Yang）.基于環路和改進遺傳算法的配電網絡重構優化（Optimization of distribution network reconfiguration based on loop and improved genetic algorithm）[J]. 高電壓技術（High Voltage Engineering），2007，33（5）：109-113.

[14]謝政.網絡算法與復雜性理論[M].長沙：國防科技大學出版社，2003.

[15]沙特朗，張萍，范益政，等.圖論導引[M].北京：人民郵電出版社，2007.

[16]田魯懷.數據結構[M].北京：電子工業出版社，2006.

[17]王東，史燕琨，叢吉遠，等（Wang Dong，Shi Yankun，Cong Jiyuan，et al）.災變遺傳算法在配電網開關優化配置中的應用（Application of catastrophic genetic algorithm to the optimal configuration of switching devices in distribution system）[J]. 高壓電器（High Voltage Apparatus），2004，40（3）：180-182.

[18]雷英杰，張善文，李續武.MATLAB 遺傳算法工具箱及應用[M].西安：西安電子科技大學出版社，2005.