苗作華，王夢(mèng)婷，湯 陽(yáng)，王 彪，王成功

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

0 引言

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

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

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

1 研究思路

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

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

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

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

表1 柵格成本等級(jí)表Table 1 Grid cost grade table

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

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

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

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

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

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

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

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

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

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

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

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

2.2.1 導(dǎo)向型機(jī)制

蟻群算法是一種仿生型算法，自然界螞蟻?zhàn)铋_始覓食時(shí)，即人工螞蟻開始搜索時(shí)，沒(méi)有具體的方向，僅依賴同伴在搜索食物時(shí)散發(fā)的信息素，通過(guò)信息素濃度來(lái)決定具體的搜索方向，所以在人工螞蟻搜索路徑時(shí)，往往會(huì)導(dǎo)致搜索時(shí)間長(zhǎng)容易產(chǎn)生路徑迂回等問(wèn)題。

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

圖3 初始搜索對(duì)比圖Fig.3 Initial search comparison diagram

2.2.2 升維型機(jī)制

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

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

圖4 “分布逼近”方法站點(diǎn)選取過(guò)程Fig.4 Site selection process with"distribution approximation"method

2.2.3 避讓型機(jī)制

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

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

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

3 實(shí)例研究

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

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

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

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

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

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

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

3）路徑搜索對(duì)比

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

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

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

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

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

4 結(jié)語(yǔ)

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

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