遞歸法在變電站選址定容運輸模型中的應用

金義雄，崔德義

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

隨著城市的不斷建設和改造，對其進行良好的電網規劃越來越重要.這主要是因為城市的電網規劃能夠直接影響低壓配電網結構和未來系統線路走向，從而影響供電的可靠性和運行的經濟性［1-5］.

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

1 變電站數學模型和組合過程

1.1 數學模型

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

決定變電站選址定容投資的適應度函數為：

1.2 組合過程

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

2 運輸模型及其遞歸過程

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

2.1 運輸模型

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

圖1 運輸模型流程

2.2 遞歸過程

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

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

圖2 遞歸模型流程

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

3 算例分析

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

表2 變電站負荷產銷平衡供電距離km

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

表3 初始方案MW

表4 檢驗方案MW

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

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

4 結語

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

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

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

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

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

［4］張崇見，余貽鑫，嚴雪飛.中壓配電變壓器優化規劃［J］.電力系統自動化，1999，23（1）：27-30.

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

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

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

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

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

（編輯蘇娟）