基于貪婪算法的配網(wǎng)多階段快速重構(gòu)新方法

趙勝舉，么莉，林濟鏗，張旭

(1. 天津大學 電氣自動化與信息工程學院，天津 300072；2. 同濟大學 電子與信息工程學院，上海 201804)

0 引言

配網(wǎng)重構(gòu)是配電自動化實現(xiàn)優(yōu)化調(diào)度及運行的重要職能之一，快速有效的網(wǎng)絡重構(gòu)求解方法在保證配網(wǎng)運行安全的前提下，可明顯提升運行的經(jīng)濟性[1]。

對于靜態(tài)重構(gòu)的求解策略，求解策略大致可分為3類：（1）確定性方法重構(gòu)。文獻[2-3]采用分支定界算法確定配電網(wǎng)開關狀態(tài)實現(xiàn)重構(gòu)。文獻[4]將非線性整數(shù)規(guī)劃的配網(wǎng)重構(gòu)模型轉(zhuǎn)換為可用商用優(yōu)化工具求解的混合整數(shù)二次錐優(yōu)化模型實現(xiàn)重構(gòu)。文獻[5]構(gòu)建了有功網(wǎng)損最小的運行方式調(diào)整和最優(yōu)負荷恢復的負荷調(diào)整兩階段配網(wǎng)重構(gòu)模型，采用分支定界算法進行求解。對于中小規(guī)模的系統(tǒng)，該類方法可求得其局部最優(yōu)解，但對于大規(guī)模系統(tǒng)而言，求解速度較慢并且收斂性沒有理論上的保證。（2）進化優(yōu)化算法重構(gòu)。文獻[6]建立了基于遺傳算法的配網(wǎng)重構(gòu)優(yōu)化模型。文獻[7]提出了考慮合環(huán)約束的網(wǎng)絡重構(gòu)優(yōu)化算法并采用貪婪自適應搜索算法進行求解。文獻[8]提出一種綜合優(yōu)化網(wǎng)絡損耗、開關動作次數(shù)、電壓平穩(wěn)性的多目標模型，然后利用改進后的粒子群算法對其進行求解。文獻[9]將Mayeda生成樹算法應用到網(wǎng)絡重構(gòu)優(yōu)化問題中，然后采用粒子群算法進行求解。文獻[10]構(gòu)建了基于改進布谷鳥算法的配網(wǎng)重構(gòu)模型及求解算法。文獻[11]提出了基于動態(tài)小生境差分算法的配網(wǎng)重構(gòu)模型及求解算法。文獻[12]提出基于十進制編碼策略的遺傳算法的配網(wǎng)重構(gòu)模型及求解策略，因求解過程中避免了無效解過多而加快了計算速度。文獻[13]提出了基于改進克隆算法的配網(wǎng)重構(gòu)模型及求解算法。文獻[14]提出了簡化網(wǎng)絡技術與遺傳算法相結(jié)合的配網(wǎng)重構(gòu)模型及求解算法。該類模型的構(gòu)建求解過程相對簡單，但需要進一步克服計算效率問題。（3）啟發(fā)式算法。文獻[15]建立了考慮網(wǎng)絡損耗和節(jié)點負荷穩(wěn)定性的優(yōu)化數(shù)學模型并采用改進支路交換法進行求解。文獻[16]提出基于改進最優(yōu)流的配網(wǎng)重構(gòu)求解算法。文獻[17]提出把回路中網(wǎng)絡損耗增量最小確定為最優(yōu)開斷支路的啟發(fā)式規(guī)則。文獻[18]提出基于最優(yōu)環(huán)路電流快速確定開斷支路的規(guī)則。這些方法的突出優(yōu)點是計算速度快，但往往只能求得局部最優(yōu)解。

對于上述3類靜態(tài)重構(gòu)算法，如何在大幅提升其計算速度的同時，獲得最優(yōu)解或近似最優(yōu)解是仍需深入探索的共同課題。

對于動態(tài)重構(gòu)，其求解策略大都通過一定方式轉(zhuǎn)化為若干個相互關聯(lián)的靜態(tài)重構(gòu)來求解[19-22]。文獻[19]建立以網(wǎng)絡損耗成本與支路開斷動作成本之和為目標函數(shù)的配網(wǎng)重構(gòu)優(yōu)化模型，然后利用信息熵把整個重構(gòu)時段劃分為若干階段并采用雜草混合算法進行求解。文獻[20]構(gòu)建網(wǎng)損和電壓偏移量的歸一化綜合評估指標把整個重構(gòu)時段劃分為若干個階段，對于每一階段分別利用遺傳算法對配電網(wǎng)進行分段重構(gòu)。文獻[21]基于文獻[20]所提出的綜合評估指標，將模擬退火算法的Mertropolis準則引入粒子群算法實現(xiàn)對各階段的快速重構(gòu)。文獻[22]把多階段負荷需求通過聚類而得到若干聚類中心，進而利用進化優(yōu)化算法對各中心依次進行網(wǎng)絡重構(gòu)。上述算法基本上均利用進化優(yōu)化算法進行動態(tài)重構(gòu)，雖有個別算法試圖進行重構(gòu)時段的最優(yōu)劃分以期減少計算量，但合理性及在大系統(tǒng)中實際應用的可行性還有待驗證。上述算法理論上能夠找到全局最優(yōu)解，但共同的缺點是當系統(tǒng)的規(guī)模較大時計算時間相對于靜態(tài)重構(gòu)而言還要長得多，實際工程應用因時間過長而往往不可行。

基于如上所述，當可操作的開關數(shù)量較多時，遇到的組合爆炸將導致其計算失敗，使得目前動態(tài)重構(gòu)算法在大規(guī)模系統(tǒng)上應用有限，面對如上問題，本文提出一種基于貪婪算法的動態(tài)重構(gòu)實用新算法，該方法有望應用于實際大系統(tǒng)，實現(xiàn)有效的快速動態(tài)重構(gòu)。本文首先提出最優(yōu)流算法與基于Mayeda算法的進化算法相結(jié)合的確定性的快速靜態(tài)重構(gòu)新算法；然后把該快速靜態(tài)重構(gòu)新算法應用于多階段動態(tài)重構(gòu)，提出一種基于貪婪算法的多階段快速動態(tài)重構(gòu)新算法，它基于開關動作次數(shù)最多的兩個相繼階段及給定的尋優(yōu)尺度參數(shù)M，對相應范圍內(nèi)的階段進行合并，并利用所提出的靜態(tài)重構(gòu)新算法進行重構(gòu)優(yōu)化，得到當前所有階段的最優(yōu)目標函數(shù)值；如此反復迭代，直到目標函數(shù)值不再減少且當前解為可行解時，即得到近似最優(yōu)解。算例證明了所提方法的有效性。

1 配網(wǎng)重構(gòu)的數(shù)學模型

若T為日負荷曲線的時段數(shù)（如T=24），在此連續(xù)的T個時間段內(nèi)總的有功功率損耗成本和開關動作成本和最小的目標函數(shù)為

本文首先提出一個單階段快速靜態(tài)重構(gòu)方法，進而基于此方法，提出快速的多階段動態(tài)重構(gòu)算法。需要指出的是，目前雖然有很多分布式發(fā)電并網(wǎng)，但是因容量很小，本文上述模型實際上對其進行近似處理，忽略出力的不確定性，把相應的負荷減去出力的期望值，得到新的負荷?？紤]分布式發(fā)電出力的不確定性的最優(yōu)動態(tài)重構(gòu)模型及算法，將在另文發(fā)表。

2 單階段靜態(tài)重構(gòu)算法

文獻[23]為提升編碼效率提出了一種基于矩陣環(huán)和操作的Mayeda生成樹實用方法。文獻[9]將該方法和粒子群算法相結(jié)合，即采用粒子群算法隨機選擇來代替文獻[23]中窮舉方法來確認候選支路集中的待交換支路，進而獲得更快的計算速度，另外該方法因利用了完整樹的構(gòu)建方法，其所生成的新樹滿足放射性要求而無須進行非常煩瑣的放射性約束檢測，計算速度相對于其他進化類算法而言具有明顯優(yōu)勢，算例也充分證明了其先進性。但因仍屬于隨機類算法，理論上必須具有足夠長的計算時間，才能得到全局最優(yōu)解，尤其當系統(tǒng)規(guī)模較大時，計算時間仍然較長。

本文提出把確定性的最優(yōu)流算法與基于Mayeda生成樹的重構(gòu)算法相結(jié)合，獲得快速的單階段配網(wǎng)重構(gòu)新算法，簡稱為靜態(tài)重構(gòu)算法。該算法的基本思想是：在Mayeda生成樹產(chǎn)生過程中，采用最優(yōu)流方法生成交換支路取代隨機方式生成交換支路，具體是把由環(huán)和計算獲得的候選支路集，逐一開斷候選支路集中的支路，其中引起功率損耗增量最小的支路即作為交換支路，與待交換支路（實際是當前樹的一個連枝）進行替換，從而完成一次樹枝與連枝的交換；每一連枝的交換支路均按上述方式形成，直至生成一棵新樹。如此反復循環(huán)迭代，直至收斂。上述做法因采用局部的最優(yōu)支路代替隨機方式生成的交換支路，最后所生成的解只能是近似的最優(yōu)解，或次優(yōu)解，相應的目標函數(shù)與全局最優(yōu)解有一定的差距，但計算速度得到了明顯的提升，實際上是實現(xiàn)了二者方法的優(yōu)勢互補。

靜態(tài)重構(gòu)算法的基本過程如下。

（6）利用文獻[23]中的環(huán)和操作獲得網(wǎng)絡矩陣Mk；并將和Mk分別定義為參考樹和網(wǎng)絡矩陣M0，，轉(zhuǎn)步驟（2）。

3 基于貪婪算法的多階段重構(gòu)算法

3.1 多階段重構(gòu)算法基本思想

基于第2節(jié)所提出的快速單階段重構(gòu)算法，本文進一步基于貪婪算法提出對于由式（1） ～（6）組成的多階段重構(gòu)問題的快速求解新算法，其可以通過2個階段的優(yōu)化獲得：（1）0 ～T中的任意連續(xù)時段的合并，獲得相應的時段合并方案，當T比較大時，時段合并方案的數(shù)目非常龐大；（2）基于階段（1）所確定的時段合并方案，采用進化優(yōu)化策略獲得所有合并時段的相應開關動作策略，使得在滿足約束的條件下目標函數(shù)最??；如此反復迭代計算，直至遍歷所有時段合并方案，在所有可行方案中目標函數(shù)最小的時段合并及開關動作可行方案，即為最后的最優(yōu)解。若T比較大時，其階段（1）的時段合并方案的數(shù)目就非常大，而每一時段合并方案均需要計算其最優(yōu)開關動作策略，從而總體計算時間會非常的長?；趩渭兊倪M化優(yōu)化算法的動態(tài)重構(gòu)，其計算復雜度與上述全局組合優(yōu)化算法是等價的。

上述算法用于大系統(tǒng)時可能遇到計算時間過長問題，而限制了其應用。為了克服該問題，本文基于貪婪算法提出一種多階段重構(gòu)問題的快速求解新算法。其基本思想如下。

（1）不劃分階段（1）優(yōu)化及階段（2）優(yōu)化，以最小時段作為初始的階段劃分，對于初始階段（就是最小的時段）分別按單階段靜態(tài)優(yōu)化方法確定每一階段的最佳開關動作方案及網(wǎng)損值。

（2）對當前狀態(tài)下的所有相繼的兩個階段的開關動作次數(shù)進行排序，然后進行如下操作。

①若有解，則獲得階段合并之后的新階段解；

②若無可行解，放棄相應階段合并，選擇當前狀態(tài)下的所有相繼2個階段的開關動作次數(shù)與當前的一樣或次于當前的2個階段，按上述方法所確定的相應的階段范圍進行合并，并進行階段合并之后的靜態(tài)重構(gòu)計算，并重復上述過程，直到找到合并之后具有可行解的相繼階段，并進行階段合并，而獲得其階段合并之后的解，轉(zhuǎn)步驟③；若所有階段均合并之后，仍無法獲得可行解，意味著目前的負荷狀態(tài)無解，算法結(jié)束；

③獲得當前狀態(tài)下的所有階段的總目標函數(shù)，若新的目標函數(shù)小于上一次階段合并的目標函數(shù)，或不是可行解，回到步驟②；若新的目標函數(shù)大于上一次階段合并的目標函數(shù)且當前解是可行解，已得到了最優(yōu)解，算法結(jié)束。

3.2 多階段重構(gòu)算法步驟

（4）獲得當前狀態(tài)下的所有階段的總目標函數(shù)值，判斷是否滿足該值小于上一次階段合并的總目標函數(shù)值，若滿足或不滿足但當前解不是可行解，轉(zhuǎn)步驟（2）；否則，已獲得最優(yōu)解，算法結(jié)束。

上述算法的流程如圖1所示。

圖1 動態(tài)重構(gòu)算法流程Fig. 1 Flow chart for dynamic reconfiguration

4 算例分析

試驗電腦配置為：Windows10操作系統(tǒng)；Intel（R）Core（TM）i5-3230M CPU2.60 GHz；4 GB內(nèi)存；編程實現(xiàn)語言為 Visual C++6.0。其中、取為0.5元/（kW·h）、5元/次。

4.1 靜態(tài)重構(gòu)結(jié)果分析

本文分別采用最優(yōu)流算法（下稱文獻[24]方法）、靜態(tài)重構(gòu)算法（下稱本文方法）、基于Mayeda生成樹的粒子群算法（下稱文獻[9]方法），對表1算例系統(tǒng)進行靜態(tài)網(wǎng)絡重構(gòu)，以驗證本文所提出的靜態(tài)重構(gòu)新算法的在計算效率和精度方面的優(yōu)勢。表2給出各系統(tǒng)在不同算法下的性能對比。

表1 算例系統(tǒng)參數(shù)Table 1 The system parameters

表2 3種算法在不同節(jié)點系統(tǒng)下的性能對比Table 2 Performance comparison of three algorithms under different test systems

由表2可見，文獻[24]方法計算速度最快，但平均網(wǎng)損值明顯高于其他兩種方法，因此競爭性實際上最弱；本文方法的網(wǎng)絡損耗非常接近于文獻[9]方法，而計算時間比文獻[9]方法少將近兩個數(shù)量級。不難看出，本文所提出的靜態(tài)重構(gòu)算法相對于其他兩個算法，具有明顯的綜合性能優(yōu)勢。

4.2 動態(tài)重構(gòu)結(jié)果分析

采用基于貪婪算法與本文所提出的靜態(tài)重構(gòu)快速算法相結(jié)合的動態(tài)重構(gòu)快速求解方法在不同的尺度參數(shù)下分別對系統(tǒng)1（IEEE 69節(jié)點系統(tǒng)）、系統(tǒng)2（IEEE 84節(jié)點系統(tǒng)）、系統(tǒng)3（IEEE 136節(jié)點系統(tǒng)）與系統(tǒng)4（實際配網(wǎng)系統(tǒng)（416節(jié)點））4個算例進行動態(tài)網(wǎng)絡重構(gòu)計算，節(jié)點負荷峰值為文獻數(shù)據(jù)的120%，由第3節(jié)介紹方法可知，在M=22時求得動態(tài)重構(gòu)的全局優(yōu)化解（下稱全局優(yōu)化法），將不同尋優(yōu)尺度參數(shù)下的性能指標值（計算時間、目標函數(shù)）分別與獲得全局優(yōu)化解時的相應指標值相比，獲得4種算例下的性能對比如圖2 ～5所示，各圖中的曲線是本文算法結(jié)果/全局算法結(jié)果。

圖2 系統(tǒng)1的性能對比Fig. 2 Performance comparison of system 1

圖3 系統(tǒng)2的性能對比Fig. 3 Performance comparison of system 2

圖4 系統(tǒng)3的性能對比Fig. 4 Performance comparison of system 3

由圖2 ～5可看出本文所提方法的目標函數(shù)隨著尋優(yōu)尺度參數(shù)M的增大越來越接近于全局優(yōu)化法。系統(tǒng)1、系統(tǒng)2、系統(tǒng)3等3個算例系統(tǒng)在M=3時，目標函數(shù)值之比分別為 1.0639、1.0678和1.0761，系統(tǒng)4在M=4時目標函數(shù)值之比為1.0908，意味著此時的本文算法的目標函數(shù)已經(jīng)非常接近于全局優(yōu)化算法的計算結(jié)果，而此時4 個系統(tǒng)的相應的計算時間之比僅為 0.0843、0.0887，0.0787與 0.0629，即本文算法的計算速度比全局優(yōu)化算法快近兩個數(shù)量級，在之后隨著M上升，本文算法的目標函數(shù)值繼續(xù)減小，到M=22時本文算法等效于全局優(yōu)化算法。上述算例表明，在M較小情況下，比如等于3或4，本文算法最優(yōu)解的目標函數(shù)值已非常接近于最優(yōu)解，但計算速度明顯優(yōu)于全局優(yōu)化算法。

表3給出了本文方法和全局優(yōu)化法分別對系統(tǒng)1、系統(tǒng)2、系統(tǒng)等3個算例系統(tǒng)在尋優(yōu)尺度參數(shù)M=3時與系統(tǒng)4在M=4時重構(gòu)優(yōu)化后的開關動作次數(shù)?？梢钥闯?，各系統(tǒng)的開關動作總次數(shù)相較于全局優(yōu)化法都得到明顯下降，其中系統(tǒng)4開關動作次數(shù)下降最為明顯，在M=4時比全局優(yōu)化法減少29次，且計算速度在M=3時相對于全局優(yōu)化法提升將近14倍，而此時動態(tài)重構(gòu)成本僅是全局優(yōu)化法1.09倍。同時考慮到M取值的靈活性，結(jié)合圖5當M=5時計算速度、重構(gòu)成本分別為全局優(yōu)化法的7.24倍、1.001倍。實現(xiàn)保證重構(gòu)質(zhì)量下計算效率顯著地提升。因此，該計算結(jié)果充分地證明了本文方法的有效性及先進性。

圖5 系統(tǒng)4的性能對比Fig. 5 Performance comparison of system 4

表3 開關動作次數(shù)比較Table 3 Comparison of switching action times

5 結(jié)論

本文首先提出一種基于最優(yōu)流法與Mayeda生成樹法相結(jié)合的靜態(tài)重構(gòu)算法，既克服了文獻[9]所提出的隨機進化優(yōu)化方法速度慢的缺點，又克服了窮舉法生成過多劣樹的缺點，達到了快速性與解空間完備性地良好結(jié)合，實現(xiàn)了二者的優(yōu)勢互補，而明顯提升了計算效果。進而提出一種基于貪婪算法的配網(wǎng)動態(tài)重構(gòu)新方法。方法以靜態(tài)重構(gòu)為基礎，基于開關動作次數(shù)最多的兩個相繼階段及給定的尋優(yōu)尺度參數(shù)M，對相應范圍內(nèi)的階段進行各種可能的合并，并利用所提靜態(tài)重構(gòu)算法進行重構(gòu)，得到當前所有階段下最優(yōu)目標函數(shù)值；如此反復迭代，直到目標函數(shù)值不再減少且當前解為可行解時，即求得近似最優(yōu)解。算例表明，只要選擇較小的M，所提出的方法在解非常接近于全局最優(yōu)解的前提下，實現(xiàn)了計算速度的接近兩個數(shù)量級的提高，提升了多階段重構(gòu)的計算效率。