改進禁忌搜索算法的線路規(guī)劃算法優(yōu)化設計

李 杰 金超未 帕爾哈提·克衣木 羅瑞雪

(國網(wǎng)新疆電力有限公司信息通信公司 烏魯木齊 830000)

1 引言①

傳統(tǒng)的輸電線路規(guī)劃是根據(jù)地理圖紙規(guī)劃大致的方案，然后進行實地考察來確定最終的方案。這種方法主要依靠設計人員的經(jīng)驗，但是由于地圖數(shù)據(jù)需要人為進行更新，造成了數(shù)據(jù)更新不及時，會導致設計人員判斷錯誤，同時輸電線路的影響因素很多，導致工作強度大、時間久，從而影響到輸電線路規(guī)劃的進度。隨著國家大力推進智能電網(wǎng)設計，地理信息系統(tǒng)(Geographic information system，GIS)和計算機系統(tǒng)被廣泛地應用到電力系統(tǒng)中，給輸電線路規(guī)劃提供了新的思路，文獻[1]中對10 kV 配網(wǎng)的輸電線路規(guī)劃需要注意的問題進行了說明，但是沒有解決人工規(guī)劃效率慢的問題。文獻[2]中提出一種優(yōu)化算法，根據(jù)設置禁忌條件來求解最優(yōu)路徑，但是由于線路規(guī)劃數(shù)據(jù)規(guī)模大，算法耗時太長。

基于以上內(nèi)容，對輸電線路的路徑選擇算法進行優(yōu)化，采用禁忌搜索算法建立最優(yōu)線路求解模型，根據(jù)規(guī)劃區(qū)內(nèi)的地理信息因素對規(guī)劃區(qū)進行單元格劃分和成本預算，得到一個成本最優(yōu)、建設難度最小的線路。并針對搜索時間過長和拐點過多等缺陷，提出跨越式鄰域和雙向搜索方法來縮短算法的計算次數(shù)，采用拐點處理機制來減少拐點數(shù)量。

2 輸電線路優(yōu)化

2.1 輸電線路概念

發(fā)電廠發(fā)出的電傳輸?shù)接脩粜枰ㄔO大規(guī)模的線路，這部分線路都可以稱作輸電線路[3]。發(fā)電廠的電經(jīng)過變壓站升壓輸送到高壓輸電網(wǎng)，再經(jīng)過降壓和配電才能到達用戶家里進行使用，所以輸電線路可以分為配電線路和送電線路。通常，配電線路電壓小于10 kV，其中低壓配電線路電壓為1 kV 以下，高壓配電線路電壓為1～10 kV；送電線路電壓為35 kV 及以上，其中高壓送電線路電壓為35～220 kV，超高壓送電線路電壓為330～500 kV[4]。

2.2 輸電線路設計需要注意的因素

輸電線路在設計規(guī)劃時要注意地理位置因素，主要有以下幾個方面[5]。

(1) 避讓區(qū)域。輸電線路在設計時要注意避開軍事管理區(qū)、自然保護區(qū)以及一些易燃易爆的廠房和倉庫。

(2) 自然環(huán)境。盡量選擇空曠的平地進行建設，注意自然生態(tài)環(huán)境，減少樹木的砍伐。

(3) 由于高壓線路會產(chǎn)生電磁感應，對人和動物會造成一定的傷害，所以在建造過程中要遠離建筑物和人群。

(4) 設計過程中要盡量避開坡度較大的地方，選擇坡度小于30°的地方建造桿塔，同時在設計時對原有線路進行改造和升級，不僅可以減少建設時間，還能節(jié)約一定成本。

2.3 輸電線路優(yōu)化的目標

輸電線路優(yōu)化的目標是在滿足用戶用電需求、符合行業(yè)標準、保證供電安全穩(wěn)定性的前提下，在輸電線路的起點和終點之間規(guī)劃出一條成本最低的線路，同時要考慮建設的復雜程度、行業(yè)的發(fā)展，還要注意保護好自然環(huán)境，避免大面積破壞和重建[6]。

3 線路規(guī)劃算法模型

3.1 劃分單元格

輸電線路規(guī)劃中單元格可以劃分為兩大類，不可跨越地區(qū)(A)和可跨越地區(qū)(B)，對于可跨越地區(qū)，要綜合考慮該地區(qū)的各種因素來確定成本，采用模糊層次分析法建立分析模型來確定單元格的成本[7]。

根據(jù)地理信息因素對成本的影響，可以引入評分系統(tǒng)對影響可跨越地區(qū)成本的因素進行評分，根據(jù)以往的經(jīng)驗評分結果如表1 所示。

表1 因素評分

對地理信息層次進行劃分，如圖1 所示。

圖1 地理信息層次

主要劃分為三層，第一層為目標層代表單元格的成本值，第二層為準則層，由導線成本、基礎設施成本、桿塔成本和施工成本組成，成本根據(jù)天氣和地理因素的變化會有所不同。第三層為第二準層層，影響著準則層，并且影響程度不同[8]。

采用評分矩陣來計算單元格的成本值[9]

式中，x ij為n×m矩陣，表示第i個單元格的第j個地理影響因素的評分，矩陣的大小根據(jù)單元格的和影響因素數(shù)量來決定，m為地理影響因素數(shù)量，n為單元格的數(shù)量。

由于評分沒有標準，無法進行有意義的評分，采用比較矩陣來解決問題[10]，即兩個地理影響因素相互對比，將地理因素兩兩對比，可得式中，aij為n×n矩陣，表示第i個地理影響因素對j個地理影響因素的影響程度，采用表1 的數(shù)據(jù)來表示比較結果。

對矩陣A的行元素求和，得到模糊一致矩陣[11]

采用GIS 和RS 技術來進行地理信息的采集和處理[14]，分為A、B 兩類單元格。通過上述計算能夠獲得單元格建設的成本值，再加上單元格的位置信息，得到如表2 所示的單元格屬性表。

表2 單元格屬性

3.2 線路規(guī)劃模型

采用禁忌搜索算法來建立輸電線路規(guī)劃模型，禁忌搜索線路優(yōu)化算法中最常用的一種人工智能算法，能夠模仿人類的記憶功能，被廣泛運用到線路規(guī)劃中[15]。算法流程如下所示。

(1) 初始化設置。禁忌表T設置為空，設定算法的參數(shù)和初始解n，這里采用隨機產(chǎn)生的方式[16]。

(2) 判斷初始解。因為初始解是隨機產(chǎn)生的，具有不確定性，所以要對其進行判斷，滿足條件則輸出結果，不滿足則進行下一步。

(3) 確定候選解。由于初始解不滿足設定的條件，所以要進行計算來確定候選結果，即計算當前解的鄰域范圍內(nèi)滿足設定要求的解的集合。

(4) 判斷候選解。根據(jù)設定的特赦條件來判斷候選解是否滿足對應的條件，若滿足，則用候選解集合里的最優(yōu)解來代替當前解作為新的當前解，并替換禁忌表內(nèi)容。然后轉(zhuǎn)至第二步，若不滿足，則進行下一步。

(5) 選擇候選解。即選擇候選解集中的最優(yōu)解來替換當前解，并替換禁忌表內(nèi)容。

(6) 繼續(xù)執(zhí)行第(2)步。

4 線路規(guī)劃算法改進

根據(jù)劃分的單元格，采用上述模型能夠從確定好的起點和終點得到一條滿足條件的最優(yōu)輸電線路。但是由于輸電線路的影響因素過多，算法的時間會大幅度增加，就失去了算法效率高的特點。因此，需要對上述得到模型進行改進和完善，主要有以下幾種方式[17]。

(1) 跨域式鄰域。在上述算法中，在利用鄰域函數(shù)求解鄰域范圍內(nèi)的解的集合時，選擇的是以當前位置為中心的8 個單元格[18]，如圖2 所示。

圖2 改進前的鄰域選擇

這種方式一般用來處理少量數(shù)據(jù)，隨著數(shù)據(jù)規(guī)模的變大，這種方式的處理速度也會變慢，因此引入跨越式鄰域來解決處理速度慢的問題，改進后的鄰域選擇如圖3 所示。

圖3 改進后的鄰域選擇

改進之后的鄰域選擇機制能夠縮短數(shù)據(jù)的計算次數(shù)，通過圖3 中陰影部分的面積，可以看到，改進后的鄰域選擇范圍更寬，使得需要計算的區(qū)域增加，相應的計算量也應增加，采用固定的跨越式鄰域可能會出現(xiàn)沒有最優(yōu)解的情況，這時可以考慮縮小或者增大跨越距離[19]。

(2) 雙向搜索。為了解決算法運算時間多長問題，采用起點和終點同時開始搜索的方式來縮短算法的運算時間，這種方式可能會出現(xiàn)無法相遇的情況，為此引入方向引導因子[20-21]，如圖4 所示。

圖4 方向引導因子

其中，線段1 為當前位置與終點的連線，線段2 為當前位置與相鄰單元格A 的連線，線段3 為當前位置與相鄰單元格B 的連線。θ1表示線段1 和線段2 的夾角，θ2表示線段1 和線段3 的夾角。

令方向控制因子為f，則有

如果方向因子f越大，則表示θ1，θ2越小，即移動的方向越接近終點，當禁忌表在搜索后逐漸增加時，會出現(xiàn)搜索范圍集中在目標范圍同一側(cè)的情況，因此，引入方向因子限制系數(shù)η， ∈(0,1)η，則有

式中，m為迭代次數(shù)。

(3) 拐角處理。在輸電線路建設中，如果拐點過多，就會建設大量桿塔和基礎設施，造成成本的大幅增長。在搜索時，會出現(xiàn)如圖5 所示的情況。

圖5 中陰影部分為不可跨越區(qū)域，假設從A點到E點需要規(guī)劃輸電線路，經(jīng)過算法的搜索規(guī)劃出了A→B→C→D→E方案，但是這樣拐點過多會造成成本的大幅度增加，為此引入拐點處理機制，比較AB和BC的斜率。如果斜率不同，表示三點未在同一直線上，此時可以判斷AC是否處于不可跨越區(qū)域，否則比較AC和AB+BC的成本選擇較小的成本線路。經(jīng)過改進和完善后的算法最終流程圖如圖6 所示。

圖5 搜索示意圖

圖6 改進算法流程

與之前的算法相比，改進后的算法的因為采用了跨越式鄰域和同時從起點終點出發(fā)，縮短了數(shù)據(jù)處理速度，同時引進拐點處理機會，讓最終的線路成本更小。

5 試驗仿真

采用基于Visual C#2010 和ArcGis10.0 開發(fā)的軟件平臺對上述算法進行仿真，其中硬件環(huán)境為interi5-9700h，運行內(nèi)存16 G，硬盤大小5 T。以變電站A 到變電站B 為例，在該區(qū)域進行路徑搜索。

采用ArcGis 軟件對規(guī)劃區(qū)內(nèi)的地理位置信息進行處理，采用上述分類，補充了風速、地形、冰覆蓋等因素，對規(guī)劃區(qū)進行單元格劃分，劃分結果如圖7 所示。

圖7 單元格劃分

圖7 中，A、B 是兩個變電站，要在其中間建設輸電線路，將規(guī)劃區(qū)域劃分為m×n的單元格，采用上述的成本計算方式來計算每個單元格的成本值，由于單元格數(shù)量較多，截取一部分，得到如圖8 所示的單元格成本圖。

圖8 單元格成本

圖8 中的數(shù)字字母，第一行表示單元格序號，第二行表示單元格成本，第三行字母表示變電站，只有一行數(shù)字的表示不可跨越地區(qū)，數(shù)字表示單元格序號。

采用Matlab 仿真軟件對上述的搜索禁忌算法和改進算法分別進行路徑搜索，仿真搜索結果如下。

(1) 基本算法結果：103→90→77→78→65→80→67→54→55→41→42→28→29→15。

(2) 改進算法結果：103→91→66→30→15。

對兩種算法的路徑拐點、成本值、所需時間進行計算，將得到的數(shù)據(jù)進行整理得到表 3 的數(shù)據(jù)對比。

表3 算法對比

從表3 數(shù)據(jù)可以看出，改進禁忌搜索算法的拐點數(shù)和迂回數(shù)減少，得到的規(guī)劃線路也更合理，同時也減少了桿塔的使用，降低了成本，另外改進算法在搜索時間上也要比之前的算法更短，從而體現(xiàn)了計算機算法的優(yōu)勢。

在檢驗所提拐角處理機制的有效性時，通過設置不同的拐點數(shù)，將利用拐角處理機制和未利用拐角處理機制進行對比分析，則正確率如圖9 所示。

圖9 拐角處理機制對比示意圖

在進行對比試驗時，采用拐角處理機制和未采用拐角處理機制分別進行對比分析，未采用拐角處理機制也即是通過常規(guī)人工作業(yè)的方式，比如采用目測方式，在90 s 的時間內(nèi)，發(fā)現(xiàn)本研究方法比傳統(tǒng)技術的方法準確率高。

6 結論

針對已有的禁忌搜索算法的不足，對其進行相應的改進，并得出以下結論。

(1) 起點和終點同時進行搜索可以減少算法的搜索時間，但是要引入方向因子來確保能夠合并。

(2) 跨越式確定鄰域也能減少算法的搜索時間，但是需要注意跨越距離要隨著鄰域函數(shù)結果進行改變。

(3) 拐點處理機制能夠減少路線的拐點數(shù)量和迂回數(shù)量，使得路線規(guī)劃更加合理，同時減少了桿塔的使用，降低了成本。

利用實驗室設備對算法進行了仿真驗證，驗證結果表明了改進算法的有效性，具有良好的應用前景，但是由于處于實驗室環(huán)境，數(shù)據(jù)規(guī)模較小，研究還需要進一步的改進和完善。