胡宇行，衛(wèi)志農(nóng)，孫國強，陳 婷，馬駿毅

（1.河海大學能源與電氣學院，南京210098；2.江蘇鎮(zhèn)江供電公司，鎮(zhèn)江212000）

配電網(wǎng)規(guī)劃是配電系統(tǒng)研究領域中的重要內(nèi)容，其本質(zhì)是一個非線性、高維數(shù)的復雜組合優(yōu)化問題。目前，求解方法可分為解析式算法和啟發(fā)式算法。解析式算法需要分析問題中各要素之間的關系，表示為函數(shù)表達式之后計算求解，這種方法可以得出最優(yōu)解，但計算費時，只適用于解空間較小的優(yōu)化問題；啟發(fā)式算法雖然不能確定每次優(yōu)化結果為最優(yōu)，但可以在合理的時間內(nèi)給出較優(yōu)解，能夠很好地適應大規(guī)模優(yōu)化問題。啟發(fā)式算法主要有遺傳算法、蟻群算法、粒子群算法等。其中，遺傳算法GA（genetic algorithm）是一種自適應隨機搜索優(yōu)化算法，GA 的遺傳算子對基因進行隨機操作，會產(chǎn)生不可行解，即孤網(wǎng)、環(huán)網(wǎng)等，故對這些不可行解的修復增加了GA 的計算量[1]。文獻[2-3]提出并論證了單親遺傳算法PGA（partheno-genetic algorithm）的理論可行性和收斂性，指出采用新遺傳操作方式可以快速高效地求解離散規(guī)劃問題；文獻[4-8]采用新型序號編碼和遺傳操作方式，即僅在一條染色體上進行全部遺傳操作，將樹的概念與PGA 相結合，對每個配電網(wǎng)的樹形結構進行遺傳操作，過程中不破壞配電網(wǎng)連通性和輻射性，有效地避免了孤網(wǎng)、環(huán)網(wǎng)等問題。但PGA 在遺傳操作中會產(chǎn)生相當數(shù)量的重復解，增加了計算量，降低該算法的空間搜索效率。

為了避免重復解的產(chǎn)生，本文提出無重訪單親遺傳算法NRPGA（non-revisit partheno-genetic algorithm），即在PGA 的基礎上增加無重訪環(huán)節(jié)，使得遺傳操作產(chǎn)生的解不僅是可行的而且互不相同。算例測試表明，NRPGA 能夠提高空間搜索效率，減少計算量，還可以提高最優(yōu)解命中概率。

1 配電網(wǎng)網(wǎng)架規(guī)劃模型

本文將配電網(wǎng)網(wǎng)架建設投資、運行費用、停電損失之和作為目標函數(shù)，該目標函數(shù)滿足輻射狀網(wǎng)架結構約束、線路電壓降落約束、線路容量約束和待選線路約束等[9-12]。

1.1 目標函數(shù)

目標函數(shù)可表述為

其中：

式中：f1為配電線路建設成本，指鋪設M 條線路的總投資；S 為按年度投資費用的現(xiàn)值之和折算的系數(shù)[12]；f2為配電網(wǎng)運行損耗成本，指把電網(wǎng)運行中線路上的有功損耗通過電價折算為費用；f3為配電線路故障停電成本，指把線路以一定的概率發(fā)生停電故障所造成的損失折算成費用；li為第i 條線路的長度；a 為單位長度架空線路價格；ΔPi為第i條線路上的有功損耗；t 為年最大損耗小時數(shù)[10]；β為電價（取居民生活用電電價）；λ 為單位長度線路故障率；t′為平均故障停電時間；Pi為流經(jīng)第i 條線路的有功功率；R 為規(guī)劃地區(qū)產(chǎn)點比；r 為折現(xiàn)率；T 為規(guī)劃年限[12]。

1.2 約束條件

1）輻射狀結構和連通性約束

配電網(wǎng)網(wǎng)架要保證連通性和輻射性，避免“孤網(wǎng)”與“環(huán)網(wǎng)”問題。

2）節(jié)點電壓降落約束

式中：Vij為變電站節(jié)點i 與節(jié)點j 之間的電壓降；Vm為節(jié)點i、j 之間的最大允許電壓降。

3）線路容量約束

式中：Pij為節(jié)點i、j 的有功傳輸功率；Pm為節(jié)點i、j之間線路上允許的最大有功功率。

4）待選線路約束

式中：linei為在一次遺傳操作中產(chǎn)生的第i 條線路；U 為在算例中提供的可選線路的集合；x1，x2，…，xn為可選線路。在16 節(jié)點算例中，給定U 含有28 條可選線路；在51 節(jié)點中，U 含有98 條可選線路。遺傳操作產(chǎn)生的支路必須屬于可選線路合集，并非任意兩個負荷節(jié)點間都有可選支路。

2 無重訪單親遺傳算法

2.1 基于樹形結構編碼方式的單親遺傳算法

配電網(wǎng)拓撲結構類似樹，而單親遺傳算子對拓撲結構的操作實質(zhì)上是改變配電網(wǎng)的樹結構，即按照一定概率讓處在不同層的節(jié)點互換。單親遺傳算子可分為移位算子和重分配算子。移位操作指在樹的非負荷節(jié)點中隨機選擇一個移位點，斷開其與父節(jié)點的聯(lián)系，選擇另一個節(jié)點作為其新父節(jié)點；重分配操作指隨機選擇重分配點，將以該點為根節(jié)點的子樹中所有的節(jié)點進行重新分配。單親遺傳算子針對樹結構進行操作，保證了樹的輻射性和連通性。

2.2 無重訪算法原理

在單親遺傳算法中，每次遺傳操作產(chǎn)生一個種群A{X（1），X（2），…}。如果在這個種群中存在2 個染色體X（m）=X（n），說明解出現(xiàn)重復。重復解會增加不必要的計算量，從而影響空間搜索效率。本文引入無重訪算法，使得每代遺傳操作產(chǎn)生的種群中沒有任何兩個染色體是一樣的，在代與代之間也沒有任何兩個染色體相同，這樣保證了種群的多樣性，減少不必要的計算量，提高空間搜索效率。

無重訪算法依靠的是數(shù)據(jù)的快速查找，文獻[13]基于二叉分割樹（BSP tree）來實現(xiàn)無重訪功能，并沒有將該算法應用到配電網(wǎng)規(guī)劃領域，而且該方法對空間分割的操作較為抽象，不能直觀地表明各個可行解之間的聯(lián)系。所以本文使用多叉樹MS tree（multidimensional search tree）實現(xiàn)各新數(shù)據(jù)的快速查找與添加，避免了空間分割過程，使得無重訪算法實現(xiàn)的過程簡單、直觀。MS tree 是一個高效的數(shù)據(jù)存儲方式，當新數(shù)據(jù)產(chǎn)生時，使用這種存儲形式進行查找能夠快速地判斷該數(shù)據(jù)是否與已知數(shù)據(jù)重復?；诙嗖鏄涞臒o重訪算法原理如下。

圖1 顯示該多叉樹已建立3 層，包含的元素分別為：0000，0001，0100，0200，0010，0110。0000為初始元素，0111，0110 為新產(chǎn)生的兩個解。從第1 層第1 位開始往下逐一比較，如果數(shù)字相同，則比較下一層的下一位?？梢园l(fā)現(xiàn)新元素0111、0110與舊元素0100 的前兩位相同，則移到與0100 相連的第3 層，發(fā)現(xiàn)0110 重復而0111 沒有重復，所以加入0111 而刪除0110，這樣就完成了無重訪的功能。結果如圖2 所示。

圖1 產(chǎn)生新元素Fig.1 Produce new elements

圖2 加入新元素Fig.2 Add new element

2.3 無重訪功能在配電網(wǎng)中的應用

將無重訪遺傳算法NRGA（non-revisiting genetic algorithm）應用于輸電網(wǎng)絡規(guī)劃[14]，但NRGA 并不適用于優(yōu)化配電網(wǎng)規(guī)劃問題。因為NRGA 雖然避免產(chǎn)生重復解，但無法避免不可行解的產(chǎn)生。GA算法對各個基因進行遺傳操作時，會隨機地交換或變異個體基因的某部分，這一操作對生成的基因有明顯影響，即GA 的遺傳操產(chǎn)生的大量新基因并不符合配電網(wǎng)的基本約束條件，稱為不可行解。對于這些不可行解，無論是修復還是舍去，都將造成計算量的顯著增加，減少空間搜索效率。使用矩陣的形式存儲配電網(wǎng)結構，可以快速判斷并修復不可行解[15]。但約束條件不包括待選線路約束，任意兩個負荷節(jié)點之間都可以連接，這使得搜索空間變大，而且不夠貼近配電網(wǎng)規(guī)劃實際情況。一旦增加了待選線路約束，則GA 算法所遇到的不可行解問題無法通過矩陣變換快速修復，失去了矩陣的優(yōu)越性。所以，GA 不適用于優(yōu)化帶有特殊約束條件的配電規(guī)劃問題。

為了適應配電網(wǎng)規(guī)劃的特殊約束條件，快速求解優(yōu)化問題，本文將無重訪算法和PGA 相結合，提出NRPGA。本文采用樹形結構存儲配電網(wǎng)拓撲結構，在滿足待選線路約束的條件下遺傳操作時，可以直接對配電網(wǎng)的樹形拓撲和父子節(jié)點進行重連，使得遺傳操作既不產(chǎn)生重復解也不產(chǎn)生不可行解，NRPGA 避免了不必要的計算，能夠有效提升空間搜索效率。

2.4 無重訪功能實現(xiàn)流程

使用最小生成樹算法產(chǎn)生初始解[13]，最小生成樹是指從一個n 條帶權無向完全圖中選擇n－1 條支路并使這個圖仍然連通，同時考慮使樹的權最小。常用Prim 算法和Kruskal 算法。設配電網(wǎng)有N個節(jié)點，M 條支路，無重訪判別過程如下。

步驟1 產(chǎn)生初始解，并存入解結構體數(shù)組中。解結構體包括：說明配電網(wǎng)連接方式的一維數(shù)組A[M]（該數(shù)組中包含M 個二進制數(shù)，1 表示該線路連通，0 表示斷開）和一個M 維的指針數(shù)組，作用是指向新的解結構體，并將所有不重復解結構體連接起來，建立了多叉樹。將初始解結構體作為對比結構體。

步驟2 遺傳操作產(chǎn)生配電網(wǎng)新解，存入新的結構體中。在算法收斂后，優(yōu)秀基因種群中只含有少量不同解甚至只有一種解，對這些解進行多次遺傳操作會遍歷所有的可能解，程序進入死循環(huán)，因此設立一個足夠大數(shù)MAX，當重復次數(shù)超過MAX 時，即使是重復解，也不再進行遺傳操作。

步驟3 使用廣度優(yōu)先遍歷對配電網(wǎng)新解的結構進行搜索，形成說明配電網(wǎng)連接方式的一維數(shù)組a[M]。

步驟4 比較新解數(shù)組a[M]與對比結構體數(shù)組A[M]。如果2 個數(shù)組在第k（0

步驟5 把新解的地址復制給該指針，退出程序。

步驟6 將步驟4 中第k 位指針所指向的結構體代替對比結構體。當kM 時，說明該解為重復解，退出程序。

2.5 無重訪單親遺傳算法的實現(xiàn)步驟

設配電網(wǎng)有N 個節(jié)點，M 條支路，以線路建設成本、故障停電成本和運行損耗成本之和作為目標函數(shù)，使用無重訪單親遺傳算法進行優(yōu)化，流程如圖3 所示。

圖3 NRPGA 實現(xiàn)流程Fig.3 Flow chart of NRPGA

3 算例分析

使用PGA 與NRPGA 分別對不同的配電網(wǎng)算例進行優(yōu)化，配電網(wǎng)算例模型參數(shù)見表1。進行200 次獨立重復優(yōu)化運算，記錄并分析數(shù)據(jù)。

表1 模型參數(shù)Tab.1 Model parameters

3.1 16 節(jié)點配電網(wǎng)算例

圖4 為16 個節(jié)點、28 條待架支路的10 kV 輻射型網(wǎng)絡[16]。其中0～15 為各節(jié)點的編號，0 號節(jié)點為供電首端，帶字母L 的節(jié)點為負荷點，其余為交叉節(jié)點，虛線為可以架線的走廊。

PGA、NRPGA 這2 種算法最終均能找到最優(yōu)解，優(yōu)化后的最小費用為81.75 萬元。優(yōu)化后的配電網(wǎng)網(wǎng)架結構如圖5 所示。選取能夠找到最優(yōu)解的收斂過程為樣本后取平均值，在16 節(jié)點算例中PGA 與NRPGA 的平均收斂過程如圖6 所示。

圖4 16 節(jié)點待規(guī)劃配電線路Fig.4 Unplanned 16 pots distribution network

圖5 優(yōu)化后配電網(wǎng)線路示意Fig.5 Sketch map of 16 nodes planned distribution network

圖6 16 節(jié)點中2 種算法收斂過程比較Fig.6 Comparison of PGA and NRPGA in 16 nodes

3.2 51 節(jié)點配電網(wǎng)算例

圖7為一個51 個節(jié)點、92 條待架支路的輻射型網(wǎng)絡，優(yōu)化后的配電網(wǎng)網(wǎng)架結構如圖8 所示。

優(yōu)化后最小費用為301.4 萬元。在51 節(jié)點算例中，操作方法與16 節(jié)點相同，PGA 與NRPGA 的收斂過程比較見圖9。

3.3 PGA 與NRPGA 的比較

由于遺傳算法的不確定，每次收斂過程和結果不盡相同。本文選取2 種算法都找到最優(yōu)解的收斂過程為樣本，取平均值，繪制成收斂過程圖。

圖7 51 節(jié)點待規(guī)劃配電線路Fig.7 Unplanned 51 nodes distribution network

圖8 51 節(jié)點優(yōu)化后配電網(wǎng)線路示意Fig.8 Sketch map of 51 nodes planned distribution network

圖9 51 節(jié)點中2 種算法收斂過程比較Fig.9 Comparison of PGA and NRPGA in 51 nodes

由圖6 和圖9 得出以下結論：

（1）隨著配電網(wǎng)規(guī)模的增加，算法的搜索解空間變大，每次迭代找到最優(yōu)解的概率變小，所以2種算法的平均收斂代數(shù)都明顯增加；

（2）在不同規(guī)模的優(yōu)化過程中，每次迭代后NRPGA 都找到了比PGA 更優(yōu)秀的解。NRPGA 避免了遺傳操作產(chǎn)生的重復解，相對于PGA，NRPGA收斂代數(shù)更小。由此，在增加無重訪功能后，NRPGA 的空間搜索效率明顯提高。

表2 和表3 分別為PGA 與NRPGA 這2 種算例優(yōu)化過程中200 次獨立重復實驗的數(shù)據(jù)統(tǒng)計。

表2 16 節(jié)點算例中PGA 與NRPGA 的數(shù)據(jù)統(tǒng)計Tab.2 Statistics of PGA and NRPGA in 16 nodes

表3 51 節(jié)點算例中PGA 與NRPGA 的數(shù)據(jù)統(tǒng)計Tab.3 Statistics of PGA and NRPGA in 51 nodes

由表2 可知：①NRPGA 在尋找最優(yōu)解次數(shù)占總實驗次數(shù)比例上有非常明顯的優(yōu)勢，即命中率高。在NRPGA 中，遺傳操作產(chǎn)生的解是不重復的，所以NRPGA 有效地避免了早熟現(xiàn)象；②由于遺傳操作方式的局限，PGA 在進行變異操作時不可避免地產(chǎn)生大量重復解，這些重復解會占據(jù)精英種群使得該算法出現(xiàn)早熟現(xiàn)象，影響了PGA 對解空間搜索的效率。

由表3 可知：①優(yōu)化規(guī)模變大后，NRPGA 的最優(yōu)解次數(shù)占總實驗次數(shù)比例（即命中率）相應降低，但相對于PGA，命中率依然保持較大優(yōu)勢；②在51節(jié)點算例中，PGA 的命中率為2.5%，這說明大量的重復解占據(jù)精英種群導致了早熟現(xiàn)象。

對比表2、表3 可以發(fā)現(xiàn)：

（1）當算例規(guī)模變大后，遺傳操作時各操作節(jié)點的可選節(jié)點變多，遺傳操作產(chǎn)生重復解的概率下降，NRPGA 平均使用無重訪功能的次數(shù)減少，由50 526.7 次下降為3 214.8 次。所以，隨著搜索空間的變大，NRPGA 的命中率由88%下降為42%，無重訪功能的效果下降。

（2）在2 個算例中，NRPGA 的命中率與PGA的命中率比值從4.4 上升為16.8，說明PGA 的命中率對搜索空間的大小更敏感，隨著優(yōu)化規(guī)模的增加，PGA 命中率從20%下降為2.5%。因此，在求解離散組合優(yōu)化問題時，搜索空間越大，NRPGA 在命中率上的相對優(yōu)勢越明顯。

（3）在2 個算例中，PGA 的平均收斂代數(shù)均比NRPGA 少，這是PGA 出現(xiàn)早熟現(xiàn)象的結果，不能說明PGA 在空間搜索效率上的優(yōu)越性。

（4）在51 節(jié)點算例中，如果使用PGA 進行優(yōu)化，在100 次獨立重復運算后，優(yōu)化后的解為最優(yōu)解的概率為92%（1-0.975100）；而使用NRPGA 優(yōu)化，在運算5 次后，就可以超過93%（1-0.585）的概率找到最優(yōu)解。在實際運算中，NRPGA 有著巨大優(yōu)勢。

4 結語

本文將無重訪功能和單親遺傳算法結合起來用以求解配電網(wǎng)網(wǎng)架優(yōu)化問題。相比PGA，NRPGA不僅能夠快速收斂，還能在遺傳操作中保持種群的多樣性，避免了早熟現(xiàn)象，從而提高空間搜索效率。測試表明，NRPGA 在大規(guī)模離散優(yōu)化算例中有著較高的命中率，具有一定的工程實用價值。

[1]李茂軍，童調(diào)生，羅隆福（Li Maojun，Tong Tiaosheng，Luo Longfu）.單親遺傳算法及其應用研究（Partheno-genetic algorithm and its application）[J]. 湖南大學學報（Journal of Hunan University），1998，25（6）：56-59.

[2]李茂軍，童調(diào)生（Li Maojun，Tong Tiaosheng）.單親遺傳算法及其全局收斂性分析（A partheno-genetic algorithm and analysis on its global convergence）[J]. 自動化學報（Acta Automatica Sinica），1999，25（1）：68-72.

[3]李茂軍，羅日成，童調(diào)生（Li Maojun，Luo Richeng，Tong Tiaosheng）.單親遺傳算法的遺傳算子分析（Analysis on the genetic operators of partheno-genetic algorithm）[J].系統(tǒng)工程與電子技術（SystemsEngineeringandElectronics），2001，23（8）：84-87.

[4]陳婷，衛(wèi)志農(nóng)，吳霜，等（Chen Ting，Wei Zhinong，Wu Shuang，et al）. 考慮電動汽車充電站選址定容的配電網(wǎng)規(guī)劃（Distribution network planning by considering siting and sizing of electric vehicle charging stations）[J]. 電力系統(tǒng)及其自動化學報（Proceedings of the CSU-EPSA），2013，25（3）：1-7.

[5]劉曉飛，彭建春，高效，等（Liu Xiaofei，Peng Jianchun，Gao Xiao，et al）. 基于單親遺傳算法的配電網(wǎng)絡規(guī)劃（Distribution network planning based on partheno-genetic algorithm）[J]. 電網(wǎng)技術（Power System Technology），2002，26（3）：52-56.

[6]麻秀范，崔換君（Ma Xiufan，Cui Huanjun）.改進遺傳算法在含分布式電源的配電網(wǎng)規(guī)劃中的應用（An improved genetic algorithm for distribution network planning with distributed generation）[J]. 電工技術學報（Transactions of China Electotechnical Society），2011，26（3）：175-181.

[7]章文俊，程浩忠，王一，等（ZhangWenjun，Cheng Haozhong，Wang Yi，et al）.基于樹形結構編碼單親遺傳算法的配電網(wǎng)優(yōu)化規(guī)劃（Distribution network optimal planning based on tree structure encoding partheno-genetic algorithm）[J]. 電工技術學報（Transactions of China Electotechnical Society），2009，24（5）：154-160.

[8]孔濤，程浩忠，李鋼，等（Kong Tao，Cheng Haozhong，Li Gang，et al）.配電網(wǎng)規(guī)劃研究綜述（Review of power distribution network planning）[J].電網(wǎng)技術（Power System Technology），2009，33（19）：92-99.

[9]于會萍，劉繼東，程浩忠，等（Yu Huiping，Liu Jidong，Cheng Haozhong，et al）.電網(wǎng)規(guī)劃方案的成本效益分析與評價研究（Cost-benefit analysis and evaluation of power network planning）[J].電網(wǎng)技術（Power System Technology），2001，25（7）：32-35.

[10]陸廣香，單淵達，龔樂年（Lu Guangxiang，Shan Yuanda，Gong Lenian）.最大負荷損耗小時數(shù)求取方法質(zhì)疑（The method about the determination of maximum load′s loss hours is Doubtful）[J]. 電工技術學報（Transactions of China Electotechnical Society），1996，11（1）：55-59.

[11]蘇海鋒，張建華，梁志瑞，等（Su Haifeng，Zhang Jianhua，Liang Zhirui，et al）.基于改進均值聚類隨機粒子群算法的變電站LCC 規(guī)劃（Substation LCC planning based on refined mean clustering random particle swarm algorithm）[J].電工技術學報（Transactions of China Electotechnical Society），2012，27（4）：209-215.

[12]蘇海鋒，張建華，梁志瑞，等（Su Haifeng，Zhang Jianhua，Liang Zhirui，et al）.基于LCC 和改進粒子群算法的配電網(wǎng)多階段網(wǎng)架規(guī)劃優(yōu)化（Multi-stage planning optimization for power distribution network based on LCC and improved PSO）[J].中國電機工程學報（Proceedings of the CSEE），2013，33（4）：118-125.

[13]Yuen Shiu Y，Chow Chi Kin. A genetic algorithm that adaptively mutates and never revisits[J].IEEE Trans on Evolutionary Computation，2009，13（2）：454-472.

[14]高元海，王淳（Gao Yuanhai，Wang Chun）. 無重訪遺傳算法及其在輸電網(wǎng)絡規(guī)劃中的應用（Non-revisiting genetic algorithm and its application in transmission network planning）[J]. 中國電機工程學報（Proceedings of the CSEE），2011，33（4）：110-117.

[15]王方方（Wang Fangfang）.基于改進遺傳算法的配電網(wǎng)規(guī)劃（Distribution Network Planning Based on Improved Genetic Algorithm）[D].上海：上海交通大學電子信息與電氣工程學院（Shanghai：School of Electronic Information and Electrical Engineering，Shanghai Jiao Tong University），2009.

[16]Jonnavithula S，Billinton R. Minimum cost analysis of feeder routing in distribution system planning[J]. IEEE Trans on Power Delivery，1996，11（4）：1935-1940.