劉啟蒙，楊 鑒，戈文江

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

0 引言

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

1 傳統(tǒng)優(yōu)化算法簡介

1.1 靜態(tài)優(yōu)化法

根據(jù)導(dǎo)納矩陣消去過程可知，導(dǎo)納矩陣小行號的非零元素越少，消去過程中注入新的非零元素越少。導(dǎo)納矩陣的行號就是網(wǎng)絡(luò)的節(jié)點號，其每行的非零元素就是相應(yīng)節(jié)點所連接的支路數(shù)(非對地支路)，因此按照連接支路最少的節(jié)點順序編號，就是靜態(tài)優(yōu)化法。編號前，統(tǒng)計網(wǎng)絡(luò)各節(jié)點連接支路數(shù)，支路少的優(yōu)先編號，若支路相同，則順序編號。靜態(tài)優(yōu)化法的主要特點是優(yōu)化快，編程簡單，但優(yōu)化效果差。

1.2 半動態(tài)優(yōu)化法

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

1.3 動態(tài)優(yōu)化法

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

2 優(yōu)化算法的改進

以下根據(jù)電力網(wǎng)絡(luò)節(jié)點編號優(yōu)化問題的特點，設(shè)計了一套結(jié)合動態(tài)法和半動態(tài)法優(yōu)點的改進優(yōu)化方法，來完成節(jié)點編號優(yōu)化。

a. 對電網(wǎng)循環(huán)查找出線度(節(jié)點連接支路數(shù))為1的節(jié)點，對該節(jié)點進行優(yōu)化編號(因為消去該節(jié)點不會產(chǎn)生新的注入元素)，消去該節(jié)點。該節(jié)點對端節(jié)點的出線度會因為消去該節(jié)點而改變，因此消去該節(jié)點后，應(yīng)重新計算對端節(jié)點的出線度。

b. 對電網(wǎng)循環(huán)查找出線度為2的節(jié)點，按消去該節(jié)點所產(chǎn)生的注入元素最少進行優(yōu)先編號，產(chǎn)生注入元素相同的節(jié)點進行隨機編號。消去該節(jié)點后，重新計算對端節(jié)點的出線度。

c. 對電網(wǎng)循環(huán)查找出線度為3的節(jié)點，按消去該節(jié)點所產(chǎn)生的注入元素最少進行優(yōu)先編號，產(chǎn)生注入元素相同的節(jié)點進行隨機編號。消去該節(jié)點后，重新計算對端節(jié)點的出線度。

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

3 算例分析與比較

3.1 算例分析

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

選用動態(tài)法對該網(wǎng)絡(luò)的優(yōu)化編號順序為：1、2、15、5、8、4、3、6、7、13、14、9、10、11、12。

圖1 電網(wǎng)系統(tǒng)等值電路

選用以上提出的改進優(yōu)化法對該網(wǎng)絡(luò)進行優(yōu)化編號的具體步驟為：

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

b. 查找出線度為1的節(jié)點，查找結(jié)果為節(jié)點15，消去節(jié)點15，計算對端節(jié)點12的出線度，得12的出線度為3。此時網(wǎng)絡(luò)中無出線度為1的節(jié)點，得到優(yōu)化后的拓?fù)浣Y(jié)構(gòu)見圖2。

圖2 節(jié)點1、2、15優(yōu)化后的拓?fù)浣Y(jié)構(gòu)

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

d. 由于上一步消去后，節(jié)點3、8的出線度都不變，因此出線度為2的節(jié)點為4、8、13、14。由于消去節(jié)點8沒有注入元素，而消去節(jié)點4、13、14，均產(chǎn)生一個注入元素，所以消去節(jié)點8。然后計算可知，節(jié)點8對端節(jié)點3的出線度為2，節(jié)點6的出線度為3。此時優(yōu)化拓?fù)浣Y(jié)構(gòu)見圖3。

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

圖3 節(jié)點5、8優(yōu)化后的拓?fù)浣Y(jié)構(gòu)

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

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

h. 計算可知，節(jié)點7的出線度為1，節(jié)點9的出線度為4，故消去節(jié)點7，計算得對端節(jié)點9的出線度3。此時優(yōu)化拓?fù)浣Y(jié)構(gòu)見圖4。

圖4 節(jié)點4、3、6、7優(yōu)化后的拓?fù)浣Y(jié)構(gòu)

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

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

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

l. 計算可知，消去節(jié)點9、12后分別產(chǎn)生的注入元素均為0，故隨機消去節(jié)點9。此時優(yōu)化拓?fù)浣Y(jié)構(gòu)見圖5。

圖5 節(jié)點13、14、9優(yōu)化后的拓?fù)浣Y(jié)構(gòu)

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

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

o. 消去節(jié)點12。

至此網(wǎng)絡(luò)節(jié)點編號全部形成，優(yōu)化編號順序結(jié)果為：1、2、15、5、8、4、3、6、7、13。

3.2 計算量比較

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

為論證該算法對高電壓等級和大電網(wǎng)的適用性，以寧夏電網(wǎng)的18節(jié)點、61支路的子網(wǎng)為例，用C++語言進行編程計算，其結(jié)果表明與傳統(tǒng)的動態(tài)節(jié)點編號優(yōu)化法相比，采用以上提出的改進優(yōu)化算法，計算時間可減少50%，而且隨著電網(wǎng)節(jié)點和支路數(shù)以及拓?fù)鋸?fù)雜度的增加，其優(yōu)化效果更加明顯。

4 結(jié)束語

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

參考文獻：

[1] 羅 軍，于歆杰．基于遺傳算法的稀疏節(jié)點優(yōu)化編號方法[J]．電網(wǎng)技術(shù)，2006，30(22)：54-58．

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

[3] 彭春華，徐雪松．基于蟻群算法的電力網(wǎng)絡(luò)節(jié)點編號多方案優(yōu)化[J]．電力系統(tǒng)及其自動化學(xué)報，2007，19(2)：60-65．

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