遞歸法在變電站選址定容運輸模型中的應(yīng)用

金義雄，崔德義

（上海電力學(xué)院電力與自動化工程學(xué)院，上海 200090）

隨著城市的不斷建設(shè)和改造，對其進(jìn)行良好的電網(wǎng)規(guī)劃越來越重要.這主要是因為城市的電網(wǎng)規(guī)劃能夠直接影響低壓配電網(wǎng)結(jié)構(gòu)和未來系統(tǒng)線路走向，從而影響供電的可靠性和運行的經(jīng)濟(jì)性［1-5］.

電網(wǎng)規(guī)劃中，變電站地址的選擇是影響城市配電網(wǎng)運行結(jié)構(gòu)的主要因素之一，其建設(shè)和改造對整個電力部門的經(jīng)濟(jì)效益有重要影響.本文著重描述了在變電站選址定容中，將遞歸方法和重心算法相結(jié)合并進(jìn)行應(yīng)用的過程，提出了將遺傳算法與這兩種方法相結(jié)合的新設(shè)想.

1 變電站數(shù)學(xué)模型和組合過程

1.1 數(shù)學(xué)模型

變電站選址定容的目的是在確定負(fù)荷分布的情況下，確定各個變電站的容量、位置，以及供電范圍，以達(dá)到投資最小和年運行費用最低.

決定變電站選址定容投資的適應(yīng)度函數(shù)為：

1.2 組合過程

表1 變電所主變壓器單組容量

2 運輸模型及其遞歸過程

變電站選址定容過程中，如何在確定了變電站的個數(shù)后，根據(jù)變電站的供電能力大小、負(fù)荷大小，以及供電距離之間的關(guān)系，合理地進(jìn)行電能分配和供電是一個值得探討的問題.我們可以首先利用運輸模型的線性規(guī)劃法對現(xiàn)有的已知條件通過編程進(jìn)行安排，然后結(jié)合重心法對結(jié)果進(jìn)行不斷的調(diào)整和校正.與人工算法相比，編程的優(yōu)點是速度快、精度高、效率好，但由于計算機(jī)對圖形不敏感，難以實施路徑搜索，筆者利用計算機(jī)對數(shù)字較敏感的特點，運用遞歸算法很好地解決了這一難題［5-8］.

2.1 運輸模型

運輸模型的工作過程如下：首先根據(jù)隨機(jī)分配的n個變電站和已知條件列出一個矩陣，矩陣的內(nèi)容包括變電站的個數(shù)、供電能力、負(fù)荷大小，以及各變電站與各負(fù)荷之間的距離，利用運輸模型算法得到初始矩陣，并利用位勢法產(chǎn)生檢驗表，通過檢驗表負(fù)數(shù)值的位置確定初始方案表的起始搜索位置;然后進(jìn)行閉合路徑搜索，找出路徑中最小的非負(fù)值a，對每一個路徑上的點進(jìn)行交叉加a或減a的操作，再利用位勢法產(chǎn)生檢驗表，看表中是否有負(fù)值;最后以此類推，直到檢驗表中沒有負(fù)值為止.此時，整個運輸模型過程結(jié)束［6］.運輸模型流程見圖1.

圖1 運輸模型流程

2.2 遞歸過程

我們發(fā)現(xiàn)，在搜索閉合路徑的過程中，用計算機(jī)實現(xiàn)很困難，這會對程序的銜接和進(jìn)一步計算帶來很大的阻礙.這是由于計算機(jī)對圖形不敏感所造成的，而筆者運用遞歸算法很好地解決了路徑搜索問題.遞歸算法分為遞推和回歸兩個步驟.遞推表示搜索到下一節(jié)點時該節(jié)點可再次調(diào)用此函數(shù)進(jìn)行類似的函數(shù)操作.回歸表示當(dāng)一次遞歸不滿足要求時，返回上一層調(diào)用，并重新進(jìn)行搜索.另外，在搜索過程中，不能終止程序，需要一直返回，直到跳出函數(shù)為止.

具體的遞歸過程如下：首先對于每一個矩陣的元素都設(shè)定一個結(jié)構(gòu)體，結(jié)構(gòu)體包含了每一個矩陣元素值所需要的信息，包括一個能代表矩陣元素的上、下、左、右4個方向信息的數(shù)組值，用1表示此方向已搜索過，0表示未搜索過.對于第一個元素設(shè)置一個node元素，然后對于每一個下次搜索得到元素的node值遞加1.這樣在最后顯示結(jié)果時可以清楚地顯示路徑的搜索順序［7-9］.整個遞歸模型的流程如圖2所示.

圖2 遞歸模型流程

圖2中，“確定搜索方向”這一步是指搜索方向分為橫向搜索和縱向搜索交叉進(jìn)行，進(jìn)行到下一次遞歸時搜索方向需要變向.另外，初始方向可自定義，例如當(dāng)此次搜索是橫向搜索時，可以設(shè)定初始方向搜索為左邊搜索，則第2種方向即為右邊搜索.縱向搜索采用類似方法.

3 算例分析

為了驗證運輸模型及遞歸算法應(yīng)用的正確性，筆者進(jìn)行了算例分析.在此算例中，假設(shè)由3個變電站A1，A2，A3及4個負(fù)荷區(qū)塊B1，B2，B3，B4組成的產(chǎn)銷平衡運輸模型，其供電距離見表2.

表2 變電站負(fù)荷產(chǎn)銷平衡供電距離km

利用運輸模型和位勢法，得出初始方案和檢驗表，如表3和表4所示.

表3 初始方案MW

表4 檢驗方案MW

從表4的負(fù)值所在位置確定表3的遞歸開始位置，將表3的矩陣輸入計算機(jī)，形成矩陣，并設(shè)置起始搜索點為（1，3）（注意，計算機(jī)中數(shù)組的起始位是從零開始的）.開始搜索后，第一個值只能橫向搜素（初始搜索方向），先搜索左邊，遇到1值，然后判斷此值是不是起點.當(dāng)判斷為否時，則轉(zhuǎn)換搜索方向，向上方搜索，發(fā)現(xiàn)4值，繼續(xù)判斷此值是否為起點.不是，則繼續(xù)搜索，這個不斷進(jìn)行搜索的過程就是遞歸過程.通過不斷遞歸，最后可以找到（0，3）位置的3值，往下搜索，即可搜索到起始點0值，遞歸過程開始返回.搜索順序依次為0－1－4－3.每搜索一次，其節(jié)點數(shù)增加1.在返回過程中，需要不斷地使用return語句，逐層返回，直到返回至第一層，整個遞歸算法結(jié)束.程序的運行結(jié)果為：

閉合路徑矩陣的數(shù)字1到4表示的是搜索路徑的順序，當(dāng)搜索到第4個節(jié)點時，向下搜索會又碰到第1個節(jié)點.此時并沒有把第1個節(jié)點標(biāo)記為7，仍然保持為1.然后在閉合回路中找到最小值，按閉合回路的路徑依次加上和減去這個最小值，以形成新的方案表.最后再利用位勢法形成檢驗表，發(fā)現(xiàn)表中所有值為正，則表明該初始方案為最優(yōu)方案.確定變電站的分配方案以后，再根據(jù)式（1）和式（2）計算出C1和C2，從而可以最終確定變電站的容量和位置.

4 結(jié)語

遞歸算法很好地解決了計算機(jī)對圖形不敏感的問題，并且可以一次搜索出所有的閉合路徑.

遺傳算法是目前廣為使用的一種現(xiàn)代啟發(fā)式尋優(yōu)方法.考慮到使用遺傳算法能解決計算問題，遞歸算法能解決路徑搜索問題，可以將兩者有效地結(jié)合起來，這為解決變電站選址定容問題提供了一條新思路.

［1］段剛，余貽鑫.電力系統(tǒng)NP難問題全局優(yōu)化算法的研究［J］.電力系統(tǒng)自動化，2001，25（5）：14-18.

［2］胡純德，祝延軍，高隨祥.一種求解旅行商問題的新型單親遺傳算法［J］.計算機(jī)工程與應(yīng)用，2004，35（1）：37-40.

［3］陳慧琴，劉剛.用整數(shù)編碼的單親遺傳求解組合優(yōu)化問題［J］.武漢理工大學(xué)學(xué)報，2004，27（2）：241-243.

［4］張崇見，余貽鑫，嚴(yán)雪飛.中壓配電變壓器優(yōu)化規(guī)劃［J］.電力系統(tǒng)自動化，1999，23（1）：27-30.

［5］李茂軍，朱陶業(yè)，童調(diào)生.單親遺傳算法和傳統(tǒng)遺傳算法的比較研究［J］.系統(tǒng)工程，2001，19（1）：61-65.

［6］《運籌學(xué)》教材編寫組.運籌學(xué)［M］.北京：清華大學(xué)出版社，2005：78-91.

［7］王成山，魏海洋，肖峻.變電站選址定容兩階段優(yōu)化規(guī)劃方法［J］.電力系統(tǒng)自動化，2005，29（4）：62-66.

［8］王成山，劉濤，謝瑩華.基于混合遺傳算法的變電站選址定容［J］.電力系統(tǒng)自動化，2006，30（6）：30-34.

［9］閆麗梅，許愛華，任爽，等.一種變電站選址的新方法［J］.高電壓技術(shù)，2007，33（9）：75-79.

（編輯蘇娟）