苗偉威，雷 鳴，廖大鵬，劉 軍，姜 濤

（1.國(guó)網(wǎng)山東省電力公司電力調(diào)度控制中心，濟(jì)南 250001；2.天津大學(xué)電氣自動(dòng)化與信息工程學(xué)院，天津 300072）

電力系統(tǒng)主動(dòng)解列優(yōu)化斷面的實(shí)用化快速搜索方法

苗偉威1，雷 鳴1，廖大鵬1，劉 軍1，姜 濤2

（1.國(guó)網(wǎng)山東省電力公司電力調(diào)度控制中心，濟(jì)南 250001；2.天津大學(xué)電氣自動(dòng)化與信息工程學(xué)院，天津 300072）

本文提出一種電力系統(tǒng)主動(dòng)解列斷面的優(yōu)化搜索方法，以多層圖分割理論為框架，通過(guò)粗化、初始分區(qū)和還原優(yōu)化3個(gè)階段實(shí)現(xiàn)解列斷面的快速搜索。結(jié)合粗化階段信息，在還原優(yōu)化階段提出一種基于尋優(yōu)和校驗(yàn)的優(yōu)化搜索策略，依次進(jìn)行尋求目標(biāo)最優(yōu)解和連通性校驗(yàn)兩個(gè)過(guò)程，借此替代含復(fù)雜邏輯約束0-1規(guī)劃問(wèn)題的求解，在提高求解效率的同時(shí)具有更高的可靠性和可擴(kuò)展性。為提高拓?fù)溥B通性校驗(yàn)效率，提出一種最小化校驗(yàn)子圖的構(gòu)造方法。最后通過(guò)兩個(gè)算例驗(yàn)證了本文方法的有效性。

多層圖分割；電力系統(tǒng)主動(dòng)解列；最小化校驗(yàn)子圖；拓?fù)溥B通性

Abstract:In this paper，an optimal searching method for the controlled splitting surface in power system is proposed within the framework of multi-level graph partitioning theory.Three stages including coarsening，initial partitioning and refinement are utilized to achieve a rapid search for the splitting surface.Combined with the information in the coarsen?ing stage，an optimal searching strategy is proposed in the refinement stage based on optimal searching and verifying in?stead of the 0-1 programming with complex logical constraints.With this strategy，optimizing and connectivity-verifying processes are executed sequentially to achieve higher reliability and better extensibility while improving the solving effi?ciency.To improve the efficiency in verifying the topology connectivity，a construction method for a minimum sub-graph for verification is proposed.Finally，two numerical examples are used to illustrate the effectiveness of the proposed method.

Key words:multi-level graph partitioning；power system controlled splitting；minimum sub-graph for verification；to?pology connectivity

以廣域量測(cè)系統(tǒng)WAMS（wide area measure?ment system）為代表的先進(jìn)電力技術(shù)正不斷推動(dòng)傳統(tǒng)輸電網(wǎng)向智能電網(wǎng)快速發(fā)展[1]，大量可再生能源的接入也使得電網(wǎng)運(yùn)行方式發(fā)生了快速的變化。這些因素都促使著調(diào)度運(yùn)行工作不斷轉(zhuǎn)變行為方式，由經(jīng)驗(yàn)型調(diào)度進(jìn)入到科學(xué)型調(diào)度模式。對(duì)于電網(wǎng)的解列控制，電網(wǎng)運(yùn)行場(chǎng)景變得更加復(fù)雜與多變，傳統(tǒng)基于預(yù)想場(chǎng)景設(shè)定系統(tǒng)解列點(diǎn)的方式適用性不斷降低。因此，近年來(lái)很多學(xué)者開(kāi)始關(guān)注具有協(xié)調(diào)和智能特征的主動(dòng)解列方式，并探索出了很多主動(dòng)解列問(wèn)題的理論和方法[2-3]。

主動(dòng)解列是一個(gè)涉及到電網(wǎng)運(yùn)行、控制和保護(hù)等多個(gè)方面的課題，而該問(wèn)題的核心是如何快速地確定系統(tǒng)解列方案，使得解列后的子系統(tǒng)各自保持同步運(yùn)行且最大程度上保持功率供求平衡。上述問(wèn)題可以看作是圖的平衡分割問(wèn)題，可以利用圖論中的相關(guān)理論來(lái)進(jìn)行電力系統(tǒng)主動(dòng)解列問(wèn)題的研究。例如利用二元決策圖[4]、譜分析[5]、k-way[6-7]等方法求解平衡圖分割問(wèn)題，或者將問(wèn)題轉(zhuǎn)化為最大流最小割問(wèn)題[8]、含連通拓?fù)浼s束的背包問(wèn)題[9]加以求解，同時(shí)還有一部分方法借助于智能優(yōu)化算法，例如蟻群算法[10]等。

鑒于電力系統(tǒng)龐大的節(jié)點(diǎn)數(shù)，許多方法在應(yīng)用時(shí)還會(huì)受掣于最終簡(jiǎn)化系統(tǒng)的規(guī)模，因此在進(jìn)行平衡圖分割之前要先對(duì)原系統(tǒng)進(jìn)行簡(jiǎn)化，利用電力系統(tǒng)的部分物理特性，在盡量不影響解列斷面搜索的前提下縮減節(jié)點(diǎn)規(guī)模。例如文獻(xiàn)[4，6，11]基于圖的等效原理對(duì)系統(tǒng)冗余節(jié)點(diǎn)進(jìn)行合并。文獻(xiàn)[11-12]分別基于電氣距離計(jì)算和潮流追蹤技術(shù)確定發(fā)電機(jī)和緊密負(fù)荷的依附關(guān)系從而可對(duì)系統(tǒng)進(jìn)行大幅簡(jiǎn)化。文獻(xiàn)[13]提出一種基于弱聯(lián)接理論的決策空間預(yù)篩方法以有效降低預(yù)決策的空間規(guī)模。

近年來(lái)，圖論中大型圖劃分方法的研究具有重要的參考意義。其中，多層圖分割方法通過(guò)多次粗化還原過(guò)程來(lái)保證劃分規(guī)模和自由度，求解策略可在求取速度和分割質(zhì)量之間取得較好的平衡[14-17]，在解決圖論中平衡圖分割這類(lèi)NP-hard問(wèn)題時(shí)，該方法也被證明是高效和可靠的。而且，在這種解列斷面搜索的有效架構(gòu)[17]下，通過(guò)考慮電力系統(tǒng)物理特性和多種啟發(fā)式邏輯可以進(jìn)一步提高劃分優(yōu)化效率。

本文沿用多層圖分割理論框架，提出一種快速實(shí)用的求解方法。在粗化階段將節(jié)點(diǎn)聚合信息有效存儲(chǔ)，在還原優(yōu)化階段將解列斷面的優(yōu)化搜索分為尋優(yōu)和校驗(yàn)兩個(gè)過(guò)程，尋優(yōu)過(guò)程篩選出備選方案，校驗(yàn)過(guò)程判斷子分區(qū)是否具有拓?fù)溥B通性。其中，校驗(yàn)過(guò)程提出一種利用粗化過(guò)程節(jié)點(diǎn)聚合信息構(gòu)造最小化校驗(yàn)子圖的方法，實(shí)現(xiàn)子分區(qū)連通性的快速判斷校驗(yàn)，提高了斷面搜索策略的整體效率。

1 多層圖分割理論及還原優(yōu)化階段斷面優(yōu)化模型

文獻(xiàn)[17]提出的基于多層圖分割理論的電力系統(tǒng)主動(dòng)解列斷面搜索方法主要分為粗化、初始分區(qū)和還原優(yōu)化3個(gè)階段，方法如圖1所示。首先，在粗化階段歸并節(jié)點(diǎn)減小圖的規(guī)模，直至簡(jiǎn)化到規(guī)模較小的圖Gn，快速給出一個(gè)較優(yōu)的初步劃分結(jié)果。然后在還原優(yōu)化階段，逐步將Gn還原到G0，通過(guò)恢復(fù)節(jié)點(diǎn)改善分區(qū)結(jié)果。

圖1 多層圖分割理論示意Fig.1 Schematic of multi-level graph partitioning

但是，電力系統(tǒng)的解列斷面搜索問(wèn)題并非是對(duì)平衡圖分割問(wèn)題的簡(jiǎn)單套用，在還原優(yōu)化階段要同時(shí)考慮解的改進(jìn)和子分區(qū)的連通性。針對(duì)還原優(yōu)化問(wèn)題，文獻(xiàn)[17]給出了1次還原優(yōu)化過(guò)程的求解模型，即

對(duì)于所有va∈VA（i），需滿(mǎn)足

式中：f為分區(qū)功率不平衡度優(yōu)化的目標(biāo)值；N為劃分的子分區(qū)個(gè)數(shù)；Ii為分區(qū)i的功率不平衡度；對(duì)應(yīng)分區(qū)i，VA（i）為從相鄰分區(qū)可能交換至分區(qū)i的節(jié)點(diǎn)集合，VB（i）為分區(qū)i可能交換至其他分區(qū)的節(jié)點(diǎn)集合，VC（i）為分區(qū)i中不參與優(yōu)化的其余節(jié)點(diǎn)集合；對(duì)于分區(qū)i中任一可能參與交換的節(jié)點(diǎn)，定義VSA（i，m）∪VSB（i，m）表示構(gòu)成該節(jié)點(diǎn)與分區(qū)i的第m條相連通路所包含的節(jié)點(diǎn)集合，其中VSA（i，m）∈VA（i）、VSB（i，m）∈VB（i），相連通路總數(shù)記為NS；類(lèi)似地，定義VRA（i，n）∪VRB（i，n）表示構(gòu)成該節(jié)點(diǎn)與相鄰分區(qū)的第n條相連通路所包含的所有節(jié)點(diǎn)，其中VRA（i，n）∈VA（i）、VRB（i，n）∈VB（i），相連通路總數(shù)記為NR；va、vb、vc、vsa、vsb、vra、vrb表示集合VA（i）、VB（i）、VC（i）、VSA（i，m）、VSB（i，m）、VRA（i，n）、VRB（i，n）中的節(jié)點(diǎn)；xa、xb、xsa、xsb、xra、xrb為待求0-1變量，表示節(jié)點(diǎn)va、vb、vsa、vsb、vra、vrb的交換狀態(tài)，等于0表示該節(jié)點(diǎn)通過(guò)割集支路交換到相鄰分區(qū)，等于1表示留在原分區(qū)；xˉ表示對(duì)x取反；P（va）、P（vb）、P（vc）為節(jié)點(diǎn)va、vb、vc的功率注入，發(fā)電為正，負(fù)荷為負(fù)。

式（1）和式（2）描述了斷面優(yōu)化的目標(biāo)，即各分區(qū)功率不平衡量絕對(duì)值之和最小。式（3）和式（4）構(gòu)造了必要的連通性邏輯約束，由于分區(qū)的邊界節(jié)點(diǎn)都有可能被交換，則需要保證最終可行解滿(mǎn)足以下條件：①參與優(yōu)化的節(jié)點(diǎn)若未被交換，則至少需要與原分區(qū)保留一條相連通路；②若被交換，則需要與相鄰分區(qū)存在至少一條相連通路。

2 還原優(yōu)化問(wèn)題的快速求解策略

式（1）～式（4）構(gòu)造了一個(gè)完整的考慮連通性約束的邊界優(yōu)化模型，模型可以看作包含多個(gè)邏輯約束的0-1規(guī)劃問(wèn)題。對(duì)該問(wèn)題的直接求解是可行的，一方面，系統(tǒng)網(wǎng)架結(jié)構(gòu)的稀疏性決定了參與計(jì)算的割集邊界節(jié)點(diǎn)數(shù)目并不會(huì)隨系統(tǒng)規(guī)模的擴(kuò)大明顯增大，能夠保持在一個(gè)較小的范圍內(nèi)；另一方面，通過(guò)求解發(fā)現(xiàn)多個(gè)邏輯約束的加入可以減小尋優(yōu)空間，進(jìn)而提高求解效率。通過(guò)調(diào)用商業(yè)軟件（例如GAMS的sbb計(jì)算軟件包）直接求解的求解時(shí)間是ms級(jí)，計(jì)算速度可以接受。

但考慮邊界優(yōu)化問(wèn)題的實(shí)際特點(diǎn)，本文提出了一種實(shí)用的快速求解策略替代0-1規(guī)劃的求解，進(jìn)一步提高求解效率，其整體流程如圖2所示。

圖2 基于尋優(yōu)、校驗(yàn)過(guò)程的求解策略Fig.2 Solving strategy based on optimal searching and verifying

圖2給出了一種基于尋優(yōu)和校驗(yàn)的求解策略，流程分為策略尋優(yōu)和校驗(yàn)兩個(gè)過(guò)程，尋優(yōu)過(guò)程對(duì)應(yīng)式（1）和式（2），拓?fù)渌阉餍ｒ?yàn)對(duì)應(yīng)式（3）和式（4）。假設(shè)規(guī)劃問(wèn)題具有S個(gè)變量，則尋優(yōu)過(guò)程可分為S個(gè)子問(wèn)題。在不考慮拓?fù)溥B通約束的情況下加入約束條件x1+x2+…+xS=S-i(i=1,2,…,S)，其中待求變量x的含義同式（2），約束條件表示該子問(wèn)題僅允許i個(gè)節(jié)點(diǎn)交換。通過(guò)目標(biāo)尋優(yōu)將待校驗(yàn)的結(jié)果依次送入校驗(yàn)?zāi)K對(duì)連通性、靜態(tài)、暫態(tài)穩(wěn)定性等進(jìn)行校驗(yàn)，未通過(guò)校驗(yàn)時(shí)返回尋優(yōu)過(guò)程再將次優(yōu)解依次送入校驗(yàn)環(huán)節(jié)直至得到滿(mǎn)足校驗(yàn)約束的最優(yōu)解。該策略有以下3個(gè)特點(diǎn)。

（1）在尋優(yōu)過(guò)程中，不含拓?fù)浼s束的各子問(wèn)題計(jì)算簡(jiǎn)單，變量規(guī)模較為有限。同時(shí)，因?yàn)楣?jié)點(diǎn)權(quán)重往往具備足夠的多樣性，一般不需要交換大量節(jié)點(diǎn)來(lái)改善優(yōu)化解。通常完成i≤4的子問(wèn)題可得到最優(yōu)解或者相當(dāng)接近最優(yōu)解的結(jié)果。而且該方法各子問(wèn)題之間互相并行，適合于采用并行技術(shù)加快計(jì)算速度。

（2）在還原優(yōu)化階段，連通拓?fù)浼s束是強(qiáng)制約束，這是潮流收斂和電網(wǎng)穩(wěn)定的基礎(chǔ)，保證拓?fù)溥B通性是可行解的必要條件。

（3）設(shè)置預(yù)篩選和控制模塊，預(yù)篩選模塊中存放當(dāng)前通過(guò)校驗(yàn)的最優(yōu)解，如果待校驗(yàn)子問(wèn)題的最優(yōu)解未能優(yōu)于目前最優(yōu)解，則直接忽略校驗(yàn)。此外，還可以擴(kuò)展定制一些簡(jiǎn)單的篩選邏輯，提前終止某些無(wú)效解的校驗(yàn)進(jìn)而實(shí)現(xiàn)快速識(shí)別。例如，部分交換節(jié)點(diǎn)通過(guò)調(diào)整后直接變?yōu)楣铝⒐?jié)點(diǎn)等。如果在線(xiàn)環(huán)境對(duì)計(jì)算時(shí)間有嚴(yán)格要求，那么控制模塊可設(shè)置最大等待時(shí)間（或迭代次數(shù)），當(dāng)計(jì)算時(shí)間（迭代步數(shù)）超過(guò)設(shè)定值時(shí)，終止各進(jìn)程并比較輸出當(dāng)前最優(yōu)可行解，其至少是一個(gè)滿(mǎn)足連通拓?fù)浼s束的改進(jìn)解。

由此可以看出，通過(guò)該求解策略可以在實(shí)際中有效地求解具有復(fù)雜約束的0-1規(guī)劃問(wèn)題。與優(yōu)化算法相比，該策略在取得理想結(jié)果時(shí)可以不考慮收斂性問(wèn)題，可以對(duì)計(jì)算時(shí)間和流程進(jìn)行良好控制，同時(shí)也便于與其他校驗(yàn)?zāi)K（例如潮流、靜暫態(tài)分析等）進(jìn)行銜接，具有良好的可擴(kuò)展性。但是，該策略要求連通性的校驗(yàn)必須具有較高的效率。下面本文結(jié)合粗化和還原階段提出一種最小化校驗(yàn)子圖的檢驗(yàn)策略來(lái)提高校驗(yàn)階效率。

3 最小化校驗(yàn)子圖構(gòu)造及校驗(yàn)方法

連通性校驗(yàn)的主要任務(wù)是對(duì)不同分區(qū)的節(jié)點(diǎn)進(jìn)行拓?fù)?，以保證歸在同一分區(qū)內(nèi)的所有節(jié)點(diǎn)構(gòu)成一個(gè)連通圖[18-21]。從搜索量上來(lái)看，每次校驗(yàn)搜索的范圍是圖中的所有節(jié)點(diǎn)，對(duì)于節(jié)點(diǎn)規(guī)模較大的網(wǎng)絡(luò)，以這種形式進(jìn)行校驗(yàn)顯然是不合適的?？紤]到該問(wèn)題的具體特點(diǎn)，優(yōu)化過(guò)程僅僅是邊界節(jié)點(diǎn)，其他節(jié)點(diǎn)的拓?fù)潢P(guān)系并未受到影響。因此本文考慮利用粗化過(guò)程中形成的聚合節(jié)點(diǎn)來(lái)替代分散的各個(gè)節(jié)點(diǎn)參與拓?fù)渌阉?，聚合?jié)點(diǎn)本身是一個(gè)連通子圖，以此為代表參與拓?fù)渌阉骱雎粤似鋬?nèi)部節(jié)點(diǎn)間的拓?fù)潢P(guān)系，可大大減少了節(jié)點(diǎn)數(shù)量，提高搜索的效率。圖3描述了利用聚合節(jié)點(diǎn)構(gòu)造最小化校驗(yàn)子圖的方法。

圖3 粗化階段的節(jié)點(diǎn)聚合信息Fig.3 Node-clustering information in coarsening stage

圖3中自下而上可以理解為粗化過(guò)程，而自上而下可以理解為還原過(guò)程。原始圖G0在粗化過(guò)程中，節(jié)點(diǎn)數(shù)不斷變少，直至初始劃分階段圖G2僅剩余3個(gè)節(jié)點(diǎn)。還原過(guò)程是粗化的逆過(guò)程，粗化過(guò)程圖G2、G3中的聚合節(jié)點(diǎn)本身便是一個(gè)連通子圖。

圖3中節(jié)點(diǎn)用符號(hào)vi，j來(lái)表示，vi，j為圖Gi中的節(jié)點(diǎn)j。假設(shè)圖G0已有初步分區(qū)結(jié)果，尋優(yōu)過(guò)程給出的優(yōu)化解為移動(dòng)節(jié)點(diǎn)v0，11，節(jié)點(diǎn)v0，11在圖3中以虛線(xiàn)節(jié)點(diǎn)表示，可知節(jié)點(diǎn)v0，11在節(jié)點(diǎn)v1，6中的局部拓?fù)浣Y(jié)構(gòu)發(fā)生了變化，進(jìn)而導(dǎo)致v1，6與鄰近節(jié)點(diǎn)的局部拓?fù)浣Y(jié)構(gòu)發(fā)生了變化，其他節(jié)點(diǎn)間的關(guān)系未受影響。因此，未受影響的范圍應(yīng)盡可能使用包含節(jié)點(diǎn)數(shù)最大的聚合節(jié)點(diǎn)，從而構(gòu)成一個(gè)節(jié)點(diǎn)規(guī)模最小的校驗(yàn)子圖。具體可通過(guò)以下步驟來(lái)實(shí)現(xiàn)：

（1）創(chuàng)建一個(gè)空容器用來(lái)存放需要參加連通性校驗(yàn)的節(jié)點(diǎn)，同時(shí)將所有節(jié)點(diǎn)的可添加標(biāo)志符置1；

（2）以變動(dòng)節(jié)點(diǎn)為起點(diǎn)發(fā)起一次深度優(yōu)先搜索，從葉節(jié)點(diǎn)一直尋找到根節(jié)點(diǎn)，將過(guò)程中搜索到節(jié)點(diǎn)的可添加標(biāo)志符置0；

（3）由根節(jié)點(diǎn)開(kāi)始發(fā)起一次廣度優(yōu)先搜索，將可添加標(biāo)志位為1的節(jié)點(diǎn)放入容器中，同時(shí)停止搜索標(biāo)志位為1的節(jié)點(diǎn)的子節(jié)點(diǎn)，對(duì)標(biāo)志位為0的節(jié)點(diǎn)遞歸采用廣度優(yōu)先搜索，直至搜索到標(biāo)志位為1的子節(jié)點(diǎn)。

按照上述步驟通過(guò)一次正向的深度優(yōu)先搜索和一次逆向的廣度優(yōu)先搜索，便可將需參與校驗(yàn)的聚合節(jié)點(diǎn)構(gòu)成最小校驗(yàn)子圖。

由圖3可知，移動(dòng)節(jié)點(diǎn)v0，11需要校驗(yàn)的最小化校驗(yàn)子圖僅包含節(jié)點(diǎn)v2，1、v2，2、v1，7、v1，8、v0，10、v0，11、v0，12等7個(gè)節(jié)點(diǎn)，除v0，11外，其他節(jié)點(diǎn)在圖3中以粗實(shí)線(xiàn)節(jié)點(diǎn)標(biāo)出。節(jié)點(diǎn)v0，11與鄰近節(jié)點(diǎn)間的拓?fù)潢P(guān)系并未簡(jiǎn)化或忽略，然而節(jié)點(diǎn)數(shù)目卻減少了50%以上，而且隨著節(jié)點(diǎn)規(guī)模的擴(kuò)大，需交換節(jié)點(diǎn)的比例占全部節(jié)點(diǎn)的比例變低，說(shuō)明本搜索方法的優(yōu)勢(shì)會(huì)更加顯著。

另外，為了保證構(gòu)造最小化校驗(yàn)子圖的效率，在圖的粗化過(guò)程中應(yīng)同時(shí)完成高效節(jié)點(diǎn)聚合信息結(jié)構(gòu)的存儲(chǔ)，即在每個(gè)對(duì)象（聚合節(jié)點(diǎn)）生成過(guò)程中完成關(guān)聯(lián)結(jié)構(gòu)的構(gòu)建，父輩及子輩的指針、支路的對(duì)應(yīng)關(guān)系等應(yīng)有效存儲(chǔ)在各節(jié)點(diǎn)對(duì)象中，以便在訪(fǎng)問(wèn)子輩及父輩時(shí)可直接通過(guò)內(nèi)存尋址完成。在步驟（3）的逆向廣度優(yōu)先搜索過(guò)程中也可同時(shí)完成連通性的校驗(yàn)，這里不再贅述。

4 算例驗(yàn)證

本文通過(guò)新英格蘭系統(tǒng)和IEEE118節(jié)點(diǎn)測(cè)試系統(tǒng)兩個(gè)算例來(lái)說(shuō)明所提方法的有效性，使用C++編制相關(guān)程序，并在Intel Dual 2.0GHz CPU，2G RAM計(jì)算機(jī)環(huán)境下測(cè)試。

4.1 算例1

算例1首先以新英格蘭10機(jī)39節(jié)點(diǎn)系統(tǒng)為例闡述本文所提出的解列斷面搜索方法，該系統(tǒng)包含10臺(tái)發(fā)電機(jī)，總發(fā)電容量5 107 MW，具體網(wǎng)架結(jié)構(gòu)如圖4所示。這里假設(shè)由WAMS得到的同步機(jī)群分別為{30，37，38，39}和{31，32，33，34，35，36}，兩個(gè)機(jī)群之間因嚴(yán)重故障失步，以此為基礎(chǔ)搜索相應(yīng)的解列斷面。

圖4 新英格蘭測(cè)試系統(tǒng)的解列斷面優(yōu)化說(shuō)明Fig.4 Illustration of splitting surface optimization on New England test system

圖5為39節(jié)點(diǎn)系統(tǒng)由G0→G6的粗化過(guò)程，即節(jié)點(diǎn)聚合的過(guò)程。由G0→G6依次將節(jié)點(diǎn)規(guī)模由39下降至23、15、8、4、2、1。由于算例較為簡(jiǎn)單，本文僅執(zhí)行最后一次還原優(yōu)化過(guò)程以說(shuō)明本文方法，還原至初始圖G0后，初始解列斷面如圖4中虛線(xiàn)所示。此時(shí)，兩個(gè)分區(qū)的不平衡度及邊界節(jié)點(diǎn)權(quán)重如表1所示，其中正表示發(fā)電，負(fù)表示負(fù)荷。

表1 子分區(qū)不平衡度及邊界關(guān)聯(lián)節(jié)點(diǎn)權(quán)重Tab.1 Imbalance of partition and the weight of relative nodes next to the boundary

圖5 最小化校驗(yàn)子圖A的構(gòu)造過(guò)程Fig.5 Construction process of minimum subgraph A for verification

當(dāng)不考慮拓?fù)浼s束時(shí)，尋優(yōu)過(guò)程的最優(yōu)解為節(jié)點(diǎn)v0，3、v0，4交換分區(qū)，如圖4（a）中的實(shí)線(xiàn)斷面所示，目標(biāo)不平衡度降至1，進(jìn)一步通過(guò)校驗(yàn)過(guò)程檢查其拓?fù)溥B通性。

按照最小化校驗(yàn)子圖的構(gòu)造方法，由于節(jié)點(diǎn)v0，3、v0，4是被移動(dòng)節(jié)點(diǎn)，圖5中虛線(xiàn)給出了從起點(diǎn)v0，3、v0，4尋至根節(jié)點(diǎn)v6，1的路徑。虛線(xiàn)連接的節(jié)點(diǎn)表示其部分拓?fù)浣Y(jié)構(gòu)發(fā)生了變化，實(shí)線(xiàn)表示逆向搜索過(guò)程，實(shí)線(xiàn)箭頭指向的節(jié)點(diǎn)表示其拓?fù)浣Y(jié)構(gòu)未發(fā)生變化，可直接代表其所聚合的節(jié)點(diǎn)進(jìn)入校驗(yàn)子圖。通過(guò)圖5的搜索過(guò)程得出的最小化校驗(yàn)子圖記為校驗(yàn)子圖A，其包含11個(gè)節(jié)點(diǎn)，具體節(jié)點(diǎn)構(gòu)成如圖4（a）所示，其中聚合節(jié)點(diǎn)通過(guò)框線(xiàn)標(biāo)出。通過(guò)對(duì)圖4（a）的連通性校驗(yàn)可發(fā)現(xiàn)，節(jié)點(diǎn)v0，3、v0，4交換分區(qū)并非一個(gè)可行解，v0，4被交換后與左側(cè)分區(qū)不存在連接通路。

尋優(yōu)過(guò)程的出的次優(yōu)解將節(jié)點(diǎn)v0，17、v0，18交換至分區(qū)1，如圖4（b）中的實(shí)線(xiàn)斷面所示，調(diào)整后子分區(qū)的不平衡度為49。與上一步的校驗(yàn)過(guò)程類(lèi)似，最小化校驗(yàn)子圖的搜索過(guò)程如圖6中虛線(xiàn)及實(shí)線(xiàn)所示，最終參與校驗(yàn)的校驗(yàn)子圖記為校驗(yàn)子圖B，節(jié)點(diǎn)數(shù)為7個(gè)，具體接點(diǎn)構(gòu)成如圖4（b）所示。調(diào)整后各子系統(tǒng)均為連通子圖，因此將v0，17、v0，18交換至分區(qū)1為滿(mǎn)足連通拓?fù)浼s束的最優(yōu)解。

圖6 最小化校驗(yàn)子圖B的構(gòu)造過(guò)程Fig.6 Construction process of minimum subgraph B for verification

4.2 算例2

算例2以IEEE118節(jié)點(diǎn)系統(tǒng)為例對(duì)所提出的方法進(jìn)一步驗(yàn)證。系統(tǒng)接線(xiàn)如圖7所示，該系統(tǒng)的總發(fā)電負(fù)荷約為3 800 MW，發(fā)電機(jī)失穩(wěn)模式為機(jī)群{10，12，25，26，31，49，54，59，61，65，66，69，80}對(duì)機(jī)群{87，89，100，103，111}失穩(wěn)，以此為基礎(chǔ)進(jìn)行解列斷面搜索。

圖7 IEEE 118節(jié)點(diǎn)測(cè)試系統(tǒng)的解列斷面優(yōu)化Fig.7 Splitting surface optimization on IEEE 118-node test system

表2為最后一次優(yōu)化過(guò)程的解列斷面及不平衡度變化，初始解列斷面如圖7中虛線(xiàn)所示，初始分區(qū)的不平衡度為61.22，尋優(yōu)過(guò)程給出的最優(yōu)解為將節(jié)點(diǎn)v0，82，v0，96、v0，98交換，不平衡度可降至1.17。由于兩個(gè)分區(qū)的連接關(guān)系較為簡(jiǎn)單，通過(guò)本文方法構(gòu)造的最小校驗(yàn)子圖僅包含19個(gè)節(jié)點(diǎn)，規(guī)模與圖G0的初始規(guī)模（118節(jié)點(diǎn)）相比大大減小，聚合節(jié)點(diǎn)通過(guò)圖7中的框線(xiàn)標(biāo)出。對(duì)圖7進(jìn)行校驗(yàn)可知，該解為最優(yōu)可行解，繼續(xù)通過(guò)后續(xù)的還原優(yōu)化過(guò)程無(wú)法繼續(xù)改善該結(jié)果，最終的解列斷面即如圖7中實(shí)線(xiàn)斷面所示。通過(guò)IEEE118節(jié)點(diǎn)算例測(cè)試本文方法的優(yōu)化校驗(yàn)過(guò)程耗時(shí)小于1 ms，證明了方法的有效性。

表2 優(yōu)化前后的解列斷面及分區(qū)不平衡度變化Tab.2 Splitting surface before and after optimization and the change of imbalance degree of partition

4 結(jié)語(yǔ)

本文沿用多層圖分割理論框架，通過(guò)粗化、分區(qū)和還原優(yōu)化3個(gè)階段完成電力系統(tǒng)主動(dòng)解列斷面的搜索?？紤]電力系統(tǒng)解列問(wèn)題的具體要求，著重討論了子圖的連通拓?fù)浼s束。通過(guò)尋優(yōu)和校驗(yàn)兩個(gè)過(guò)程進(jìn)行邊界的還原優(yōu)化，避免了含復(fù)雜邏輯約束的0-1規(guī)劃問(wèn)題的求解，在提高求解效率的同時(shí)具備更好的可靠性和擴(kuò)展性。在圖的粗化過(guò)程有效存儲(chǔ)節(jié)點(diǎn)的聚合信息，并利用該信息構(gòu)造一個(gè)用于連通性校驗(yàn)的最小化校驗(yàn)子圖，該子圖不改變與邊界有關(guān)的拓?fù)潢P(guān)系，但節(jié)點(diǎn)規(guī)模大幅降低，進(jìn)一步提高了斷面優(yōu)化搜索的效率。通過(guò)算例證明了本文方法的有效性。

[1]崇志強(qiáng)，戴志輝，焦彥軍（Chong Zhiqiang，Dai Zhihui，Jiao Yanjun）.典型廣域保護(hù)通信網(wǎng)絡(luò)的信息傳輸可靠性評(píng)估（Information transmission reliability assessment of com?munication network in typical wide area protection）[J].電力系統(tǒng)及其自動(dòng)化學(xué)報(bào)（Proceedings of the CSU-EP?SA），2014，26（4）：20-24．

[2]高鵬，王建全，甘德強(qiáng)，等（Gao Peng，Wang Jianquan，Gan Deqiang，et al）.電力系統(tǒng)失步解列綜述（Review on power system out-of-step separation）[J].電力系統(tǒng)自動(dòng)化（Automation of Electric Power Systems），2005，29（19）：90-96．

[3]宋洪磊，吳俊勇（Song Honglei，Wu Junyong）.基于廣域量測(cè)信息的電力系統(tǒng)主動(dòng)解列控制研究綜述（A sum?marization of research on wide-area measurement informa?tion based power system controlled islanding）[J].電網(wǎng)技術(shù)（Power System Technology），2013，37（12）：3467-3474.

[4]Sun Kai，Zheng Dazhong，Lu Qiang.Splitting strategies for islanding operation of large-scale power systems using OBDD-based methods[J].IEEE Trans on Power Systems，2003，18（2）：912-923．

[5]楊健，唐飛，廖清芬，等（Yang Jian，Tang Fei，Liao Qing?fen，et al）.基于半監(jiān)督譜聚類(lèi)的最優(yōu)主動(dòng)解列斷面搜索（An optimal controlled partitioning scheme based on semi-supervised spectral clustering algorithm）[J].電網(wǎng)技術(shù)（Power System Technology），2015，39（1）：242-249．

[6]Xu Guangyue，Vittal Vijay.Slow coherency based cutset determination algorithm for large power systems[J].IEEE Trans on Power Systems，2010，25（2）：877-884．

[7]Yang Bo，Vittal Vijay，Heydt Gerald T，et al.A novel slow coherency based graph theoretic islanding strategy[C]// IEEE Power Engineering Society General Meeting.Tam?pa，USA，2007．

[8]Wang Xiaoming，Vittal Vijay.System islanding using mini?mal cutsets with minimum net flow[C]//IEEE PES Power Systems Conference&Exposition.New York，USA，2004．

[9]林濟(jì)鏗，王旭東，李勝文，等（Lin Jikeng，Wang Xudong，Li Shengwen，et al）.基于含連通圖約束的背包問(wèn)題的圖分割方法（Graph partition method based on connected graph constraints knapsack problem）[J].中國(guó)電機(jī)工程學(xué)報(bào)（Proceedings of the CSEE），2012，32（10）：134-141．

[10]王乙斐，唐飛，廖清芬，等（Wang Yifei，Tang Fei，Liao Qingfen，et al）.帶連通性約束的蟻群優(yōu)化算法主動(dòng)解列斷面求解策略（Controlled splitting surface searching strategy based on ant colony optimization algorithm under connectivity constraints）[J].電力系統(tǒng)及其自動(dòng)化學(xué)報(bào)（Proceedings of the CSU-EPSA），2016，28（9）：56-62．

[11]吳學(xué)娟，沈沉，向?qū)W軍，等（Wu Xuejuan，Shen Chen，Xiang Xuejun，et al）.主動(dòng)解列策略求解過(guò)程中的網(wǎng)絡(luò)化簡(jiǎn)（Network simplification for active splitting strategy searching）[J].中國(guó)電機(jī)工程學(xué)報(bào)（Proceedings of the CSEE），2008，28（7）：7-12．

[12]Wang C G，Zhang B H，Hao Z G，et al.A novel real-time searching method for power system splitting boundary[J].IEEE Trans on Power Systems，2010，25（4）：1902-1909．

[13]喬穎，沈沉，盧強(qiáng)（Qiao Ying，Shen Chen，Lu Qiang）.大電網(wǎng)解列決策空間篩選及快速搜索方法（Islanding de?cision space minimization and quick search in case of large-scale grids）[J].中國(guó)電機(jī)工程學(xué)報(bào)（Proceedings of the CSEE），2008，28（22）：23-28．

[14]Hendrickson B，Leland R.A multilevel algorithm for parti?tioning graphs[R].Albuquerque：Sandia National Labora?tories，1993．

[15]Karypis G，Kumar V.A fast and high quality multilevel scheme for partitioning irregular graphs[J].SIAM Journal on Scientific Computing，1998，20（1）：359-392．

[16]Karypis G.METIS：A software package for partitioning un?structured graphs，partitioning meshes，and computing fillreducing orderings of sparse matrices version 5.0[EB/OL].http：//glaros.dtc.umn.edu/gkhome/views/metis，2012.

[17]苗偉威，賈宏杰，田圳（Miao Weiwei，Jia Hongjie，Tian Zhen）.電力系統(tǒng)主動(dòng)解列斷面的快速搜索方法（A fast partitioning method for power system controlled splitting）[J].電力系統(tǒng)自動(dòng)化（Automation of Electric Power Sys?tems），2013，37（12）：24-30．

[18]Gao Bo，Yang Yuhang，Ma Huiye.An effective distributed approximation algorithm for constructing minimum con?nected dominating set in wireless and Hoc networks[C]// The Fourth International Conference on Computer and In?formation Technology.Wuhan，China，2004：658-663．

[19]Kernighan B W，Lin S.An efficient heuristic procedure for partition graphs[J].Bell System Technical Journal，1970，49（2）：291-308．

[20]尹專(zhuān)，劉天琪，江東林，等（Yin Zhuan，Liu Tianqi，Jiang Donglin，et al）.含風(fēng)力發(fā)電的配電網(wǎng)計(jì)劃孤島搜索方法（Search method for international islanding of distribu?tion network with wind power generation）[J].電力系統(tǒng)及其自動(dòng)化學(xué)報(bào)（Proceedings of the CSU-EPSA），2013，25（1）：142-147．

[21]Fiduccia C M，Mattheyses R M.A linear time heuristic for improving network partitions[C]//ACM IEEE Nineteenth Design Automation Conference Proceedings.Las Vegas，USA，1982：174-181．

Practical and Rapid Searching Method for Controlled Splitting Surface Optimization in Power System

MIAO Weiwei1，LEI Ming1，LIAO Dapeng1，LIU Jun1，JIANG Tao2
（1.Dispatch and Control Center，State Grid Shandong Electric Power Company，Jinan 250001，China；2.School of Electrical and Information Engineering，Tianjin University，Tianjin 300072，China）

TM77

A

1003-8930（2017）09-0122-07

10.3969/j.issn.1003-8930.2017.09.020

2015-07-13；

2017-05-25

苗偉威（1985—），男，博士，工程師，研究方向?yàn)殡娏ο到y(tǒng)運(yùn)行、穩(wěn)定與控制，大規(guī)模新能源集成。Email：miaowei?wei@tju.edu.cn

雷 鳴（1974—），男，碩士，高級(jí)工程師，研究方向電力系統(tǒng)運(yùn)行分析。Email：leiming@sd.sgcc.com.cn

廖大鵬（1974—），男，碩士，高級(jí)工程師，研究方向電力系統(tǒng)運(yùn)行分析。Email：liaodapeng@sd.sgcc.com.cn