電網節點編號優化算法的改進

劉啟蒙，楊 鑒，戈文江

(1.華北電力大學，河北 保定 071003；2.河北建投新能源有限公司，石家莊 050001；3.河北省電力研究院，石家莊 050021)

0 引言

由于導納矩陣節點消去過程中會注入新的非零元素，而消去過程注入新的非零元素與導納矩陣中的元素排列有關，也就是和節點編號順序密切相關，不同節點編號方案所產生的注入元素數目也不相同，因此為了充分利用電力網絡模型矩陣的稀疏特性，減少不必要的計算，提高求解效率，有必要對網絡節點進行節點編號優化。節點編號優化嚴格地說是一個組合優化問題，針對不同電網結構會采取不同的節點編號優化方法，對于輻射配電網可采用樹狀編號、逆流編號等算法，對于復雜電力網絡會有大量的節點編號方案，很難求出最優方案，因此目前實際工程應用中廣泛采用的是求次優編號的方法，如靜態優化法、半動態優化法和動態優化法3類傳統優化算法。

1 傳統優化算法簡介

1.1 靜態優化法

根據導納矩陣消去過程可知，導納矩陣小行號的非零元素越少，消去過程中注入新的非零元素越少。導納矩陣的行號就是網絡的節點號，其每行的非零元素就是相應節點所連接的支路數(非對地支路)，因此按照連接支路最少的節點順序編號，就是靜態優化法。編號前，統計網絡各節點連接支路數，支路少的優先編號，若支路相同，則順序編號。靜態優化法的主要特點是優化快，編程簡單，但優化效果差。

1.2 半動態優化法

該方法的基本思想是找到連接支路最少的節點進行編號，然后消去該節點，每消去一個節點，尚未編號節點的支路連接數就會發生變化，然后從未編號節點中查找連接支路最少的節點進行編號。如此反復，直到消去所有節點。半動態優化法考慮了各節點出線數目的變動情況，注入元素減少，具有優化效果好，編程簡單，優化快等優點，但與動態優化法相比元素仍然過多。

1.3 動態優化法

動態優化法分為兩步，第一步是將網絡的所有節點輪流進行一次消去運算，統計各節點消去后各自增加的新支路數，將增加支路數最少的節點編號為1，然后消去該節點；第二步是將尚未編號的每個節點依次進行一次消去運算，統計各節點消去后各自增加的支路數，將增加支路數最少的節點編號為2，隨后消去該節點。依此類推，對尚未編號的節點全部按照此操作，即完成節點編號優化。從理論上說，動態法的優化效果最好，但優化速度慢，運算量大。

2 優化算法的改進

以下根據電力網絡節點編號優化問題的特點，設計了一套結合動態法和半動態法優點的改進優化方法，來完成節點編號優化。

a. 對電網循環查找出線度(節點連接支路數)為1的節點，對該節點進行優化編號(因為消去該節點不會產生新的注入元素)，消去該節點。該節點對端節點的出線度會因為消去該節點而改變，因此消去該節點后，應重新計算對端節點的出線度。

b. 對電網循環查找出線度為2的節點，按消去該節點所產生的注入元素最少進行優先編號，產生注入元素相同的節點進行隨機編號。消去該節點后，重新計算對端節點的出線度。

c. 對電網循環查找出線度為3的節點，按消去該節點所產生的注入元素最少進行優先編號，產生注入元素相同的節點進行隨機編號。消去該節點后，重新計算對端節點的出線度。

d. 當所有節點的出線度都大于等于4后，只按照出線度的多少進行編號，不再重新計算消去節點后對端節點的出線度(導納矩陣是稀疏矩陣，在節點出線度大于4時，計算消去該節點產生注入元素的時間過長，計算過程繁瑣)。該方法結合了半動態法和動態法編號的優點，充分利用了電力網絡的稀疏特性。該方法與半動態法相比，每次編號都是在最少出線度的相同節點中選擇消去該節點后注入元素最少節點進行編號，而不是在出線度相同的情況下隨機編號，所以新的非零注入元素小于半動態法，提高了矩陣的稀疏度，矩陣處理起來比半動態法容易；與動態法相比，優化效果相當，但是由于每次編號是在出線度最少的節點中考慮優先編號，而不是對整個電網所有節點進行消去，每次循環涉及的節點數量減少，循環次數大大降低，速度明顯提高。

3 算例分析與比較

3.1 算例分析

圖1為某電網系統等值電路(15個節點，20條支路)，以下分別采用動態優化法和以上提出的改進優化法對其進行節點編號優化，并分析優化結果。

選用動態法對該網絡的優化編號順序為：1、2、15、5、8、4、3、6、7、13、14、9、10、11、12。

圖1 電網系統等值電路

選用以上提出的改進優化法對該網絡進行優化編號的具體步驟為：

a. 查找出線度為1的節點，查找結果為1節點，消去1節點，計算對端節點2的出線度，得2的出線度為1，消去節點2，計算對端節點3的出線度為3。

b. 查找出線度為1的節點，查找結果為節點15，消去節點15，計算對端節點12的出線度，得12的出線度為3。此時網絡中無出線度為1的節點，得到優化后的拓撲結構見圖2。

圖2 節點1、2、15優化后的拓撲結構

c. 查找尚未編號節點中出線度為2的節點，查找結果為節點4、5、8、13、14。由于消去節點4、5、8、13、14，都產生一個注入元素，故可隨機編號，可選取5節點進行編號，消去節點5，計算對端節點3、8的出線度。

d. 由于上一步消去后，節點3、8的出線度都不變，因此出線度為2的節點為4、8、13、14。由于消去節點8沒有注入元素，而消去節點4、13、14，均產生一個注入元素，所以消去節點8。然后計算可知，節點8對端節點3的出線度為2，節點6的出線度為3。此時優化拓撲結構見圖3。

e. 節點3、4、13、14的出線度為2，并且消去這4個節點的注入元素均為1，故可隨機編號，可選取4節點進行編號，消去節點4，計算對端節點3、7的出線度。

圖3 節點5、8優化后的拓撲結構

f. 節點7的出線度為3，節點3、13、14的出線度為2，由于消去節點13、14均產生一個注入元素，消去節點3無注入元素，故消去節點3。計算對端節點6、7的出線度。

g. 計算可知，節點6、7、13、14的出線度均為2，消去節點6、7無注入元素，消去節點13、14注入元素為1。故隨機消去節點6，計算對端節點7、9的出線度。

h. 計算可知，節點7的出線度為1，節點9的出線度為4，故消去節點7，計算得對端節點9的出線度3。此時優化拓撲結構見圖4。

圖4 節點4、3、6、7優化后的拓撲結構

i. 查找出線度為2的節點，查找結果為節點13、14，由于消去節點13、14均產生一個注入元素，故隨機消去節點13。

j. 計算對端節點9、14的出線度可知，節點9的出線度為3，節點14的出線度為2，故消去節點14。

k. 計算節點14對端節點9、12的出線度，可知節點9、12的出線度均為2。

l. 計算可知，消去節點9、12后分別產生的注入元素均為0，故隨機消去節點9。此時優化拓撲結構見圖5。

圖5 節點13、14、9優化后的拓撲結構

m. 計算對端節點10、11、12的出線度，可知節點10、11、12出線度均為2，消去這3個節點都無新的注入元素，故隨機消去節點10。

n. 計算對端節點11、12的出線度，可知節點11、12出線度均為1，故隨機消去節點11。

o. 消去節點12。

至此網絡節點編號全部形成，優化編號順序結果為：1、2、15、5、8、4、3、6、7、13。

3.2 計算量比較

通過以上的算例分析可知，以節點優化過程中需要進行消去運算的總的元素個數作為計算量，按照傳統的動態優化法，需要對75個元素進行消去運算，而以上提出的改進優化算法只需要對31個元素進行運算即可，減少的計算量為58.66%，而優化結果和動態優化法結果相同，可見該算法的優化效果明顯。

為論證該算法對高電壓等級和大電網的適用性，以寧夏電網的18節點、61支路的子網為例，用C++語言進行編程計算，其結果表明與傳統的動態節點編號優化法相比，采用以上提出的改進優化算法，計算時間可減少50%，而且隨著電網節點和支路數以及拓撲復雜度的增加，其優化效果更加明顯。

4 結束語

傳統的電力網絡節點編號優化方法中，由于靜態優化法優化快，編程簡單，但優化效果差，半動態法和動態法優化效果明顯，但過程較復雜，在實際應用中受到一定限制。以上根據電力網絡節點編號優化問題的特點，設計了一套結合半動態法和動態法優點的改進優化算法，并進行了實例驗證，結果顯示，該方法在優化效果和時間上較傳統方法有了很大的提高，可以達到理想的優化效果，對大規模復雜電網的計算機輔助分析計算具有重要的參考價值。

參考文獻：

[1] 羅 軍，于歆杰．基于遺傳算法的稀疏節點優化編號方法[J]．電網技術，2006，30(22)：54-58．

[2] 樂全明，呂飛鵬，王菊萍，等．形成節點阻抗矩陣的節點編號順序優化算法[J]．電網技術，2006，30(6)：88-91．

[3] 彭春華，徐雪松．基于蟻群算法的電力網絡節點編號多方案優化[J]．電力系統及其自動化學報，2007，19(2)：60-65．

[4] 徐得超，李亞樓，郭 劍，等．消去樹理論及其在潮流計算中的應用[J]．電網技術，2007，31(22)：12-16．