電網(wǎng)節(jié)點(diǎn)編號(hào)優(yōu)化算法的改進(jìn)

劉啟蒙，楊 鑒，戈文江

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 算例分析與比較

3.1 算例分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 計(jì)算量比較

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

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

4 結(jié)束語

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

參考文獻(xiàn)：

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

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

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

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