基于優(yōu)化蟻群算法的輸電線路徑規(guī)劃研究

苗作華，王夢婷，湯 陽，王 彪，王成功

（1.武漢科技大學資源與環(huán)境工程學院，湖北武漢 430081；2.冶金礦產(chǎn)資源高效利用與造塊湖北省重點實驗室，湖北武漢 430081；3.中鋼集團武漢安全環(huán)保研究院有限公司，湖北武漢 430081；4.北京道亨軟件股份有限公司，北京 100012）

0 引言

輸電線路徑規(guī)劃是高壓輸電線路設(shè)計中的一個重要過程[1]，其最終目標是在線路起止點間選出一條安全可靠、環(huán)境友好、經(jīng)濟合理的綜合最優(yōu)線路[2]。傳統(tǒng)的輸電線路徑規(guī)劃主要是根據(jù)經(jīng)驗以及現(xiàn)有的線路在圖紙上選取出幾條合適的線路，再進行實地考察，進一步調(diào)整線路以便確定最終線路。由于輸電線路的地形地貌較為復雜，規(guī)劃圖紙中無法展現(xiàn)精確、實時的地貌特征，使得整個規(guī)劃設(shè)計過程存在工作量大，準確率低等問題[3-4]。因此，借助現(xiàn)代科學技術(shù)完成線路規(guī)劃工作[5-6]，使輸電線路徑規(guī)劃更加智能化，是輸電線路徑規(guī)劃發(fā)展的必然趨勢。

由于涉及多種不同量綱的影響因素，因此輸電線規(guī)劃是一個大規(guī)模的非線性組合優(yōu)化問題。傳統(tǒng)數(shù)學優(yōu)化方法已經(jīng)不能滿足規(guī)劃要求[7]，為提高輸電線路徑規(guī)劃性能，涌現(xiàn)出眾多人工智能啟發(fā)式方法，比如蟻群算法（Ant Colony Optimization，ACO）、遺傳算法（Genetic Algorithm，GA）、模擬退火算法（Simulated Annealing Algorithm，SAA）以及地理信息系統(tǒng)與智能算法的結(jié)合等[8-10]，與傳統(tǒng)規(guī)劃方法相比，這類啟發(fā)式規(guī)劃方法打開了路徑規(guī)劃的新世界，能在較短的時間內(nèi)以較高的搜索效率得到合理的規(guī)劃結(jié)果。這些具有啟發(fā)式思想的規(guī)劃方法已經(jīng)被諸多學者應(yīng)用于輸電線規(guī)劃中并證實其有效性。石經(jīng)緯[11]以地理信息系統(tǒng)（Geographic Information System，GIS）作為平臺對影響輸電線的地理因素進行分類，運用層次分析法建立輸電線路徑自選結(jié)構(gòu)圖，并通過蟻群算法進行了優(yōu)化，運用多種方法形成了路徑自選系統(tǒng)。謝景海提出輸電線路徑規(guī)劃應(yīng)考慮地理與環(huán)境等因素，使用GIS 處理RS 獲取的規(guī)劃區(qū)遙感圖像，并采用蟻群算法進行路徑規(guī)劃[12]。使用云平臺將海量數(shù)據(jù)三維數(shù)字化，并聯(lián)合GIS 技術(shù)建立成本評估模型，為Q-learning 進行路徑規(guī)劃打下基礎(chǔ)[13]。蘇海鋒和許道林[14]等利用層次分析法和蟻群算法，對路徑成本值進行計算以及路徑的規(guī)劃，實現(xiàn)了規(guī)劃中障礙識別和避讓的功能。董翔宇[15]用柵格法構(gòu)建路徑規(guī)劃仿真環(huán)境，結(jié)合蟻群與人工勢場算法進行巡檢機器人路徑規(guī)劃。李杰[16]針對規(guī)劃區(qū)的特征劃分不同類型的單元格，對禁忌搜索算法進行改進，進行路徑規(guī)劃，一定程度上加快輸電線規(guī)劃效率以及減少工程成本。上述研究只是將智能工具與智能算法當成一個處理以及分析數(shù)據(jù)的手段，并沒有具體將輸電線規(guī)劃問題與現(xiàn)代智能技術(shù)深層次的相結(jié)合。

在此背景下，本文充分利用地理信息系統(tǒng)與蟻群算法在路徑搜索中的優(yōu)勢，針對輸電線路徑規(guī)劃方案中縮短路徑長度、規(guī)避障礙物以及改善線路迂回情況三大難點，提出了相對應(yīng)的優(yōu)化機制。采用蟻群算法與GIS 結(jié)合的方式，以ArcGIS 作為輸電線路路徑選擇的地理信息數(shù)據(jù)采集和分析平臺，用模糊層次分析法整合地理圖層并確定綜合圖層，建立了基于優(yōu)化蟻群算法的輸電線自動規(guī)劃路徑模型。

1 研究思路

輸電線路徑規(guī)劃過程復雜，涉及多種地理信息因素，本文在構(gòu)建輸電線路徑規(guī)劃模型之前，可將全過程系統(tǒng)化，為國家電網(wǎng)建設(shè)路徑規(guī)劃過程提供參考。整個路徑規(guī)劃方法共包括三部分，首先借助ArcGIS 工具處理點、線、面三種源數(shù)據(jù)，并生成綜合柵格圖；其次，使用模糊層次分析法（Fuzzy Analytic Hierarchy Process，F(xiàn)AHP）將綜合柵格圖中的影響因素量化并得到綜合成本矩陣；最后路徑搜索階段，借助MATLAB 工具，在輸電線綜合成本矩陣的基礎(chǔ)上，進行路徑規(guī)劃的更新迭代，得到最終的最優(yōu)路徑。具體路徑規(guī)劃方法研究步驟如圖1 所示。

1.1 綜合圖層構(gòu)建

通過ArcGIS 采集和處理影響輸電線路徑規(guī)劃的成本圖層，包括可通過型成本圖層與障礙型成本圖層，綜合圖層為二者圖層信息疊加而成，為輸電線路徑規(guī)劃做基礎(chǔ)準備工作。

使用柵格表示的方法，在ArcGIS 中將規(guī)劃區(qū)域中的各個圖層柵格化，每個柵格都有各自的屬性，其中包括柵格的位置信息、大小信息以及成本信息。柵格的成本信息主要為輸電線路建設(shè)的成本，考慮不同地理信息因素對建設(shè)線路的影響程度，將柵格成本分為五個等級，具體柵格成本等級分類見表1[14]。

表1 柵格成本等級表Table 1 Grid cost grade table

柵格圖層與成本圖層關(guān)聯(lián)，賦予每個柵格綜合成本信息。綜合成本信息由多個成本圖層按照不同的權(quán)重系數(shù)累加而成，其中成本圖層包括可通過型成本圖層與障礙型成本圖層。圖2 所示為10×10的單元柵格，其中灰色柵格代表可通過型，柵格中數(shù)字為具體成本，黑色柵格為不可通過型，代表障礙物。

圖2 柵格成本表示Fig.2 Grid cost representation

1.2 綜合圖層權(quán)重計算

輸電線路徑搜索的最終目標是得到安全可靠、環(huán)境友好、經(jīng)濟合理的輸電線路。為一定程度上提高輸電線路徑規(guī)劃方法的準確性，需在規(guī)劃過程中綜合考慮多方面因素，即線路長度、地形地貌、交通運輸、施工條件以及地方規(guī)劃等，這些因素量綱各不相同，無法統(tǒng)一評估。因此，我們針對GIS 柵格數(shù)據(jù)表示的路徑選擇區(qū)域的各類圖層信息，使用模糊層次分析法（Fuzzy Analytic Hierarchy Process，F(xiàn)AHP）綜合量化圖層信息，將專家主觀判斷的影響因素進行量化。如軍事禁區(qū)、自然保護區(qū)等區(qū)域，無法以任何形式跨越，作為障礙物；對于可以跨越的地區(qū)，根據(jù)該地區(qū)相關(guān)地理信息，綜合評估總成本值，采用模糊層次分析法進行圖層權(quán)重計算，具體步驟依次如下：構(gòu)造模糊判斷矩陣、確定初始權(quán)重、去模糊化、確定最終權(quán)重。

2 優(yōu)化蟻群算法的路徑規(guī)劃模型

2.1 傳統(tǒng)蟻群算法

蟻群算法是Dorigo 提出的一種分布式智能仿生算法[17-19]，其靈感來源于大自然中螞蟻群體尋找食物過程中能形成一條最優(yōu)路徑的現(xiàn)象，螞蟻在尋找路徑過程中，會釋放“信息素”，在螞蟻移動的過程中，有“信息素”的釋放也有“信息素”的揮發(fā)。該算法根據(jù)“信息素濃度”判斷下一移動的位置，具有隨機性[20]，具體表達見式（1），即在t時刻，螞蟻k從位置i去往位置j的移動概率為：

式中：i，j分別為起點和終點；ηij(t)=1/dij為兩點i，j路徑距離的倒數(shù)；ηis(t)=1/dis為兩點i，s路徑距離的倒數(shù)，其中s∈allowedk；τij(t)為t時由i到j(luò)的信息素濃度；τis(t) 為t時由i到s的信息素濃度，其中s∈allowedk；allowedk為鄰接矩陣中不包含障礙物和禁忌節(jié)點集合。

信息素的增加與消散有三種不同的更新原則，即由Dorigo 等[21]提出的蟻量模型、蟻密模型和蟻周模型。相對于蟻量、蟻密模型利用的局部信息，蟻周模型利用的全局信息有著更好的信息更新策略，因此本文選用蟻周模型進行信息素的更新，如式（2）所示：

式中：Q為信息素的強度增加系數(shù)[22]；Q/Lk為每單位長度信息量；為螞蟻k在位置（i，j）上釋放的信息素增加量。

2.2 優(yōu)化蟻群算法

在路徑搜索中，針對輸電線路徑規(guī)劃方案中縮短路徑長度、規(guī)避障礙物以及改善線路迂回情況三大難點，本文提出相應(yīng)的優(yōu)化機制，即提出基于優(yōu)化蟻群算法的輸電線規(guī)劃方法。優(yōu)化蟻群算法融合導向與綜合成本型機制，在微觀上具體表現(xiàn)為導向型、升維型以及避讓型三大功能。

2.2.1 導向型機制

蟻群算法是一種仿生型算法，自然界螞蟻最開始覓食時，即人工螞蟻開始搜索時，沒有具體的方向，僅依賴同伴在搜索食物時散發(fā)的信息素，通過信息素濃度來決定具體的搜索方向，所以在人工螞蟻搜索路徑時，往往會導致搜索時間長容易產(chǎn)生路徑迂回等問題。

為避免這些問題的發(fā)生，在人工螞蟻搜索過程中加入方向引導因子，如圖3 所示。在人工螞蟻搜索路徑時，初始化各個位置的信息素，其中起點指向終點方向上的位置信息素略大于其他方向的，使人工螞蟻在搜索時，將指向性的向終點搜索，避免過多路徑迂回情況的發(fā)生，在很大程度上縮短了人工螞蟻在初始搜索時的時間。

圖3 初始搜索對比圖Fig.3 Initial search comparison diagram

2.2.2 升維型機制

傳統(tǒng)輸電線路選址，往往是從A 地區(qū)為起點，B地區(qū)為終點進行線路規(guī)劃，中間將跨越多個地區(qū)。為了準確計算輸電線路選址的成本要求較高分辨率的柵格數(shù)據(jù)，決定了模型處理的柵格數(shù)據(jù)地圖數(shù)據(jù)量較大。如果直接針對柵格地圖數(shù)據(jù)進行選址，處理的數(shù)據(jù)量過大，耗費時間較長，甚至得不到最優(yōu)解[23-24]。

針對柵格數(shù)據(jù)地圖數(shù)據(jù)量較大的問題，本文提出了降低輸電線地圖柵格維度的解決辦法，即構(gòu)成柵格數(shù)據(jù)集的像元尺寸變大。為使輸電線路徑成本值最低，需在路徑起止點之間確定最佳的路徑轉(zhuǎn)角，因此引入輔助中間點定位作為路徑轉(zhuǎn)角選擇的方法。該方法引入了像元作為輔助節(jié)點，實現(xiàn)了整體路徑的局部搜索，降低了搜索范圍的存儲空間，進一步實現(xiàn)了高效率低成本的目的，具體做法如圖4 所示。

圖4 “分布逼近”方法站點選取過程Fig.4 Site selection process with"distribution approximation"method

2.2.3 避讓型機制

傳統(tǒng)蟻群算法選址，由層次分析法得到各因子的權(quán)重，并通過柵格計算器計算，可以得到綜合成本圖層。綜合成本圖層包括可通過型成本圖層與不可通過型成本圖層。為判斷二者圖層區(qū)別，通過設(shè)置不可通過區(qū)為較高成本值來判定，即設(shè)置不可通過型圖層柵格值為“9999”。該方法在應(yīng)用中，計算機計算量大，也不能使路線完全避讓不可通過型柵格。

因此，引入單位矩陣，其中0 代表可通過柵格，即圖5b 中白色柵格，1 代表不可通過柵格，即圖5b中黑色柵格。進一步對單位矩陣進行鄰接處理，計算出每個柵格中可通過的柵格位置，并與成本圖層疊加，得到綜合圖層中所有可通過的柵格成本，便于后續(xù)路徑規(guī)劃，具體操作步驟如圖5 所示。

圖5 綜合成本柵格圖形成過程Fig.5 Formation process of comprehensive cost raster chart

3 實例研究

根據(jù)本文提出的融合導向與綜合成本型機制的優(yōu)化蟻群算法用ArcGIS 處理柵格數(shù)據(jù)，以及MATLAB 作為開發(fā)平臺，開發(fā)了輸電線路路徑自動搜索程序。實驗測試區(qū)包括某省綏陽、遵義、鳳崗、湄潭、余慶5 縣（數(shù)據(jù)來源：數(shù)據(jù)禾，https://www.databox.store/Home/Index），南北跨度38.74 km，東西跨度24.59 km。該區(qū)域構(gòu)造復雜，地貌多樣，其中坡度、高程、土地覆蓋、公路、水系和居民地為成本型圖層，自然保護區(qū)為避讓圖層。下面針對該測試區(qū)域進行路徑搜索。

1）原始地理信息處理以及柵格化

原始成本型圖層包括點、線、面3 種要素。在使用MATLAB 進行路徑搜索前，首先需利用ArcGIS 處理原始成本型圖層。其中針對點要素以及線要素，先計算圖中每個像元到最近源的歐氏距離，進一步根據(jù)面圖層以及點、線要素的歐氏距離圖層進行等級分類。將柵格值按分級得分，即1，2，3，4 和5 來賦值，如圖6 為測試區(qū)內(nèi)地形、高程和坡度等成本型地理信息數(shù)據(jù)等級分類后的柵格圖。

圖6 重分類柵格圖Fig.6 Reclassified grid

2）綜合權(quán)重確定

考慮到各個地理信息因素的影響程度不同，選用Delphi 法[25]，由專家對地理信息因素進行兩兩重要性比較，重要程度采用1—9 標度定量表示，并采用三角模糊數(shù)表征其不確定性，得到各因素的模糊判斷矩陣，如表2 所示，最后計算得出各個影響因素的權(quán)重值[26]。

表2 影響因素權(quán)重判斷矩陣Table 2 Influence factor weight judgment matrix

3）路徑搜索對比

為了驗證本文方法的有效性，將上述地圖數(shù)據(jù)生成大小為500 m×500 m（柵格規(guī)模為[51×30]）的柵格。分別采用傳統(tǒng)蟻群算法和優(yōu)化蟻群算法對同一研究區(qū)域柵格圖進行路徑搜索，得到不同算法規(guī)劃路徑圖對比與不同算法最短路徑收斂對比。

在如圖6 所繪制的柵格圖中開展路徑規(guī)劃仿真實驗，仿真實驗初始條件如表3 所示。依據(jù)仿真實驗結(jié)果得到如圖7 所示的路徑對比圖以及最短路徑收斂對比圖。

表3 算法仿真結(jié)果對比Table 3 Comparison of algorithm simulation results

圖7 算法運行結(jié)果對比Fig.7 Comparison of algorithm running results

由圖7 可知，2 種算法均能避開障礙區(qū)域，但是優(yōu)化后蟻群算法采用單位矩陣方法對障礙物進行識別，減少了計算機的運算量，提高了運行速度。同時，優(yōu)化后的蟻群算法在避免障礙物的同時，在方向因子的作用下，對終點有導向性，不會產(chǎn)生線路迂回，拐點個數(shù)也大幅度減少，使規(guī)劃路徑更為合理。優(yōu)化后的蟻群算法明顯優(yōu)于傳統(tǒng)算法，與優(yōu)化后的蟻群算法相對比，搜索速度更快效果更好。

4 結(jié)語

針對輸電線路徑規(guī)劃中數(shù)據(jù)量大、運行時間長、規(guī)劃不合理等難點，本文提出相應(yīng)的導向型、升維型和避讓型優(yōu)化機制，結(jié)合ArcGIS 平臺與MATLAB 軟件，提出了基于方向引導和綜合成本的蟻群優(yōu)化算法，以及自動規(guī)劃路徑模型。

選取某省局部地區(qū)為研究區(qū)域，以提出的模型完成了對實驗區(qū)域的路徑規(guī)劃工作，并與傳統(tǒng)蟻群算法運行結(jié)果進行了對比。仿真結(jié)果表明，本文提出的方向引導與綜合成本的蟻群算法，無論是在運行速度、路徑長度以及產(chǎn)生路徑拐點個數(shù)都明顯優(yōu)于傳統(tǒng)的蟻群算法，這證明了基于優(yōu)化蟻群算法模型的有效性和可行性。