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

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

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

1 引言①

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

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

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

2.1 輸電線路概念

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

2.2 輸電線路設(shè)計(jì)需要注意的因素

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

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

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

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

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

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

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

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

3.1 劃分單元格

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

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

表1 因素評(píng)分

對(duì)地理信息層次進(jìn)行劃分，如圖1 所示。

圖1 地理信息層次

主要?jiǎng)澐譃槿龑樱谝粚訛槟繕?biāo)層代表單元格的成本值，第二層為準(zhǔn)則層，由導(dǎo)線成本、基礎(chǔ)設(shè)施成本、桿塔成本和施工成本組成，成本根據(jù)天氣和地理因素的變化會(huì)有所不同。第三層為第二準(zhǔn)層層，影響著準(zhǔn)則層，并且影響程度不同[8]。

采用評(píng)分矩陣來計(jì)算單元格的成本值[9]

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

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

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

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

表2 單元格屬性

3.2 線路規(guī)劃模型

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

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

(2) 判斷初始解。因?yàn)槌跏冀馐请S機(jī)產(chǎn)生的，具有不確定性，所以要對(duì)其進(jìn)行判斷，滿足條件則輸出結(jié)果，不滿足則進(jìn)行下一步。

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

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

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

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

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

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

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

圖2 改進(jìn)前的鄰域選擇

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

圖3 改進(jìn)后的鄰域選擇

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

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

圖4 方向引導(dǎo)因子

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

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

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

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

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

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

圖5 搜索示意圖

圖6 改進(jìn)算法流程

與之前的算法相比，改進(jìn)后的算法的因?yàn)椴捎昧丝缭绞洁徲蚝屯瑫r(shí)從起點(diǎn)終點(diǎn)出發(fā)，縮短了數(shù)據(jù)處理速度，同時(shí)引進(jìn)拐點(diǎn)處理機(jī)會(huì)，讓最終的線路成本更小。

5 試驗(yàn)仿真

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

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

圖7 單元格劃分

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

圖8 單元格成本

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

采用Matlab 仿真軟件對(duì)上述的搜索禁忌算法和改進(jìn)算法分別進(jìn)行路徑搜索，仿真搜索結(jié)果如下。

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

(2) 改進(jìn)算法結(jié)果：103→91→66→30→15。

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

表3 算法對(duì)比

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

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

圖9 拐角處理機(jī)制對(duì)比示意圖

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

6 結(jié)論

針對(duì)已有的禁忌搜索算法的不足，對(duì)其進(jìn)行相應(yīng)的改進(jìn)，并得出以下結(jié)論。

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

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

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

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