劉勝，張豪，晏齊忠，張志鑫，申永鵬

(1.鄭州輕工業(yè)大學，鄭州 450002；2. 河南中煙工業(yè)有限責任公司南陽卷煙廠，河南 南陽 473007)

0 引言

近年來我國在經(jīng)濟與基礎建設領(lǐng)域發(fā)展迅猛，電力工業(yè)作為國家發(fā)展的支柱，其規(guī)模在不斷擴大、自動化程度在不斷提高[1 - 3]，變電站數(shù)量也隨之不斷增多，無人或少人值守變電站成為變電站發(fā)展的主流趨勢[4]。傳統(tǒng)人工巡檢存在勞動強度大、巡檢效率低、受環(huán)境因素限制等問題，已無法滿足當下對供電質(zhì)量的高要求[5]。引進智能巡檢機器人在滿足安全高效的同時，也克服了傳統(tǒng)人工巡檢的問題與不足。

路徑規(guī)劃是實現(xiàn)機器人自動導航的關(guān)鍵，進行路徑規(guī)劃的目的是在規(guī)定約束下為機器人選擇一條盡可能歷程最短、效率最高的無碰撞行動路線[6 - 7]。對于路徑規(guī)劃算法的研究，傳統(tǒng)的蒙特卡羅模擬和迪杰斯特拉算法等貪心算法可以確保最優(yōu)解，但在復雜條件下運算量過大[8 - 11]；隨后人們提出了改進的蟻群算法和遺傳算法此類啟發(fā)式算法可以解決運算量過大的問題但仍存在收斂精度低、易落入局部最優(yōu)解并且迭代復雜的問題[12 - 16]。

針對上述問題，張麗珍等通過建立節(jié)點間最優(yōu)代價函數(shù)，設立“虛擬終點”，從而避免了盲目搜索，縮小了搜索空間，但易陷入局部最優(yōu)[17]。孟冠軍等選擇在蟻群算法中加入全局距離參數(shù)，通過在運行過程中不斷交叉操作以得到最快求解速度，該方法雖然降低了算法的運行時間，但所得結(jié)果并沒有明顯改進[18]。琚澤立等引入曼哈頓距離、重置信息素揮發(fā)機制以及設置蟻群自適應路徑長度改進蟻群算法，得到了很好的路徑結(jié)果，但在改進過程中也增加了算法運行的復雜性[19]。劉杰等引入自適應信息素揮發(fā)系數(shù)，實現(xiàn)了隨機漫游的效果，避免搜索陷入停滯[20]。張凡等引入JPS算法，并優(yōu)化調(diào)點數(shù)量，提高搜索效率，但未考慮提高算法運算速度[21]。薛陽等則引入蜂群算法，借助“觀察蜂”和“偵查蜂”的概念完善解的適應度，這樣很好地規(guī)避了局部最優(yōu)的困境[22]。陳志等通過算法初期信息素不均勻分配避免盲目搜索，使用偽隨機狀態(tài)轉(zhuǎn)移規(guī)則選擇路徑，同時利用動態(tài)懲罰方法解決死鎖問題[23]。

本文結(jié)合模擬退火算法與蟻群算法提出了改進的蟻群-模擬退火(ant colony optimization-simulated annealing，ACO-SA)算法，通過提高蟻群前期的全局搜索能力、改善信息素分布與更新、引入回火機制避免局部最優(yōu)、提高搜索效率。并通過仿真實驗驗證其準確性與有效性。

1 環(huán)境模型

本文采用柵格法模擬機器人工作環(huán)境，將變電站環(huán)境分解為一系列大小相等的網(wǎng)絡單元，單元格大小以巡檢機器人尺寸為標準。

假設巡檢環(huán)境為長為L，寬為W的規(guī)則場地，將環(huán)境平均劃分為m×n個長度、寬度分別為l、w的柵格，用Nxy表示每個小柵格，整個環(huán)境空間記為Φ，Φ的表達式如式(1)所示。

Φ=∑Nxy|(x∈[1,m],y∈[1,n])

(1)

每個柵格有無障礙信息表達如式(2)所示。

(2)

式中：Nxy為每個柵格的狀態(tài)信息，取值為0表示無障礙區(qū)可自由通行，取值為1表示有障礙區(qū)禁止通行。在參考了現(xiàn)實變電站布局后，建立多個二值化柵格數(shù)組表示機器人巡檢環(huán)境，同時設置小柵格為1×1，模型如圖1所示。

圖1 柵格模型Fig.1 Raster model

使用大小相等的柵格劃分柵格空間，并用柵格數(shù)組表示運行環(huán)境，簡單的建模過程大大降低了模型的復雜度，同時具備區(qū)分運動空間與障礙物的能力，滿足路徑規(guī)劃的實驗需求。此外，柵格法滿足本文所采用的八叉樹搜索策略，即機器人在搜索過程中可以朝附近8個方向的相鄰柵格之間移動，機器人移動模型如圖2所示。

圖2 巡檢機器人移動模型Fig.2 Mobile model of inspection robot

2 ACO算法和SA算法

ACO算法模擬自然環(huán)境中蟻群覓食時的探索過程，是一種尋找最優(yōu)路徑的啟發(fā)式算法[24]。其原理是螞蟻們在探索過程中沿途分泌信息素，隨著蟻群多次往返，信息素不斷積累、揮發(fā)，最后信息素濃度最高的路徑即為最短路徑。

信息素濃度是蟻群選擇路徑的關(guān)鍵依據(jù)，為了加速路徑篩選設定信息素揮發(fā)機制，當所有螞蟻完成一次往返后對全局信息素含量進行更新，具體規(guī)則見式(3)。

τij(t+1)=(1-ρ)τij(t)+ρΔτij(t)

(3)

式中：τij(t)為返途中螞蟻在節(jié)點i到節(jié)點j之間的路徑上所留下的全局信息素含量；ρ為信息素揮發(fā)因子，ρ∈(0,1)代表信息素在自然條件下的揮發(fā)情況，1-ρ為信息素殘留因子；Δτij(t)為本次往返途中螞蟻k在節(jié)點i到節(jié)點j之間的路徑上所留下的信息素含量，其數(shù)學表達式如式(4)所示。

(4)

式中m為環(huán)境地圖最大柵格數(shù)。

螞蟻對于路徑的選擇不僅與信息素濃度有關(guān)，在選擇下一節(jié)點時會優(yōu)先考慮相鄰的節(jié)點，對此定義螞蟻在兩節(jié)點間的啟發(fā)函數(shù)ηij以表達螞蟻從所在節(jié)點i到達下一節(jié)點j的期望程度，詳見式(5)。

(5)

(6)

式中：dij為節(jié)點i與節(jié)點j直接的歐幾里得距離；ix、iy、jx、jy分別為兩節(jié)點的橫縱坐標。

(7)

式中：A為螞蟻下一步可訪問的節(jié)點集合；τij(t)為節(jié)點i與j之間的信息素含量；ηij為啟發(fā)函數(shù)；α為信息素啟發(fā)因子，α值越大則在選擇路徑時信息素的影響就越大，螞蟻們就越傾向于選擇較多螞蟻走過的路徑；β為期望因子，β值越大則在選擇路徑時啟發(fā)式信息的影響就越大，螞蟻們更傾向于移動至相鄰最近的節(jié)點；C為該時刻未訪問的節(jié)點集合；S為集合C中的一節(jié)點。

根據(jù)以上條件，利用經(jīng)典蟻群算法在本文所建立的柵格環(huán)境(圖1)中進行路徑規(guī)劃，其結(jié)果如圖3—4所示。

圖3 經(jīng)典蟻群算法規(guī)劃路線Fig.3 Classic ant colony algorithm for route planning

結(jié)合圖3和圖4可知，傳統(tǒng)蟻群算法在迭代至30次左右時陷入局部最優(yōu)導致算法處于死鎖狀態(tài)，之后迭代冗余無法得到最優(yōu)結(jié)果。

圖4 經(jīng)典蟻群算法收斂曲線Fig.4 Convergence curve of classical ant colony algorithm

模擬退火算法模擬熱力學中金屬退火過程[25]，隨著溫度由高降低(退火過程)，粒子隨機運動概率逐漸降低，并最終達到穩(wěn)定熱平衡狀態(tài)。

運用模擬退火算法進行路徑規(guī)劃實際上是一個組合優(yōu)化的過程，即從所有可行解中挑選出最優(yōu)狀態(tài)下的解。首先設定Ω={S1,S2,…,Sn}代表所有可行解構(gòu)成的解空間，用C(Si)代表解Si所對應的目標函數(shù)的值，最終最優(yōu)解S*應滿足對于所有Si∈Ω都能滿足C(S*)≤C(Si)。

隨機生成一組可行解 記為初始解狀態(tài)，并計算得到該解的目標函數(shù)值C(Si),隨后采用Metropolis抽樣法獲取新的可行解S′,計算目標函數(shù)的增量，并以如下標準判斷是否接收S′作為新的當前解，數(shù)學表達式如式(8)所示。

(8)

式中：P為隨機數(shù)，P∈[0,1]；Pt為接收概率，與時間t成反比，如式(9)所示。

(9)

之后重復操作迭代500次后降低溫度，在新的溫度條件下尋求新解，當滿足終止條件后，結(jié)束退火過程并輸出最優(yōu)解。其中t時刻下溫度T=αtT0，T0為初始溫度。

3 改進算法

3.1 啟發(fā)函數(shù)的改進

傳統(tǒng)蟻群算法在設定啟發(fā)式信息時僅用節(jié)點間距離的反比來構(gòu)建啟發(fā)函數(shù)，以此模擬螞蟻選擇最短距離路徑的效果，這樣在理論上確保了螞蟻們會優(yōu)先選擇段距離路徑，但是未考慮當前節(jié)點與下一節(jié)點的位置關(guān)系，同時在后期搜索過程中啟發(fā)信息的影響程度將遠低于信息素，為此我們重新定義啟發(fā)函數(shù)如式(10)所示。

(10)

(11)

式中：djb為節(jié)點j到終點b的歐幾里得距離；Lmax為最大迭代次數(shù)；?為使啟發(fā)函數(shù)動態(tài)變化而引入的參數(shù)，其值隨著迭代次數(shù)的增加由大變小；L為當前迭代次數(shù)。由于前期增大了啟發(fā)函數(shù)的比重，避免了螞蟻搜索路徑的盲目性，加快收斂速度，同時不會干擾后期路徑選擇的準確性。在其他參數(shù)不變的情況下，僅改變啟發(fā)函數(shù)完成10組對照實驗，實驗結(jié)果如圖5所示。

圖5 改進啟發(fā)函數(shù)驗證Fig.5 Verification of improved heuristic function

由圖5可知，我們在同一柵格環(huán)境進行10次重復試驗，可以看出在運用改進啟發(fā)函數(shù)后，迭代次數(shù)明顯下降。

3.2 初始信息素改進

在經(jīng)典蟻群算法中，初始時全局信息素處于同一水平，這使得螞蟻們前期處于盲目搜索狀態(tài)，導致算法運行時間增加。為了提高算法收斂速度，本文給出了初始信息素的確定公式，如式(12)所示。

(12)

式中：a、i、j、b分別表示起始點、當前節(jié)點、下一節(jié)點、終點；dab、dai、dij、djb為各點之間的歐幾里得距離；λ為平衡系數(shù)。20×20柵格環(huán)境中初始信息素濃度如圖6所示。

圖6 初始信息素濃度Fig.6 Initial pheromone concentration

以顏色深度表示初始信息素濃度，從圖6可以看出，初始信息素濃度是以始末連線為中心，沿中垂線向外呈正態(tài)分布且濃度逐漸降低。這使得初始條件下各節(jié)點由于位置不同信息素分布不均勻，避免了螞蟻在初期盲目探索，提高了搜索效率。

3.3 初始信息素改進

在經(jīng)典蟻群算法中信息素揮發(fā)因子通常為常數(shù)，這使得信息素的更新無法滿足我們對算法收斂速度與全局最優(yōu)的要求。對此本文給出信息素動態(tài)揮發(fā)因子見圖7，此時ρ的值隨著迭代次數(shù)的增加而減小。ρ的數(shù)學表達式如式(13)所示。

圖7 兩種ρ函數(shù)對比Fig.7 Comparison of the two ρ functions

ρ=ce-t1/2

(13)

式中：t為算法運行時間；c為平衡系數(shù)，其值可變以確保函數(shù)可進行自適應變化。

改進后的信息素更新機制前期ρ值較大可以擴大搜索范圍，后期ρ值較小以便快速篩選出優(yōu)勢路徑。為驗證改進的可行性，在其他條件不變的前提下，使用不同信息素揮發(fā)因子進行對照實驗，實驗結(jié)果如圖8所示。

圖8 改進信息素揮發(fā)機制驗證Fig.8 Verification of improved pheromone volatilization mechanism

3.4 初始信息素改進

為了避免局部最優(yōu)我們引入模擬退火算法中的回火機制，螞蟻選擇下一節(jié)點j時的選擇函數(shù)見式(14)。

(14)

(15)

4 改進算法

為驗證改進算法的有效性，使用MATLAB R2016a進行計算機仿真實驗，具體實驗環(huán)境為Windows 10操作系統(tǒng)，CPU為core i5 8th gen，8 G內(nèi)存。為驗證ACO-SA算法的優(yōu)越性，將仿真結(jié)果與經(jīng)典蟻群算法進行比較。

4.1 算法實現(xiàn)

仿真實驗參數(shù)如表1所示。同時由于模擬過程若設定Tmin=0則需要過長時間運行，迭代次數(shù)過多使精度和時間上產(chǎn)生矛盾。因此設定的終止條件為T<0.000 1或最優(yōu)解保持不變。

表1 參數(shù)配置Tab.1 Parameter configuration

按圖9流程進行算法仿真。

圖9 ACO-SA算法流程Fig.9 Flow chart of ACO-SA algorithm

步驟1：構(gòu)建柵格地圖，設定初始參數(shù)，即螞蟻數(shù)量N、降溫系數(shù)、初始溫度、回火次數(shù)、迭代次數(shù)。

步驟2：設定不均勻初始信息素濃度，并設定啟發(fā)函數(shù)。

步驟3：派出螞蟻探索全圖，根據(jù)信息素濃度及啟發(fā)函數(shù)前往下一節(jié)點，所有螞蟻完成一次往返或無法行走時本次迭代結(jié)束。

步驟4：歷次迭代完成后，接受最短路徑，并更新全局信息素濃度。

步驟5：采用回火機制，與前一溫度時刻比較，若當前解(最短路徑長度)優(yōu)于上一解則接受新解，對于劣解根據(jù)公式得到接受概率，同時產(chǎn)生隨機數(shù)Y(取值范圍為[0,1])，若Y

步驟6：更新當前溫度，當?shù)螖?shù)或當前溫度滿足結(jié)束條件時退出循環(huán)，否則進入下一次迭代循環(huán)。

步驟7：輸出解集中的最優(yōu)解為最終路徑。

4.2 結(jié)果分析

根據(jù)上述算法步驟，本文分別建立場景1(20×20)、場景2(25×25)、場景3(30×30)柵格地圖，并逐步增加地圖環(huán)境復雜程度，檢驗算法的普適性。為了更直觀地驗證ACO-SA算法的可行性，將文獻[20]的改進蟻群算法與本文提出的融合算法進行對比。場景1、2、3的實驗結(jié)果分別如圖10—12所示。

圖10 場景1實驗結(jié)果Fig.10 Experimental results of scenario 1

圖11 場景2實驗結(jié)果Fig.11 Experimental results of scenario 2

圖12 場景2實驗結(jié)果Fig.12 Experimental results of scenario 2

ACO-SA算法、文獻[20]算法在3個場景中關(guān)于最優(yōu)路徑長度、算法運行時間、迭代次數(shù)的對比結(jié)果如表2所示。

表2 結(jié)果對比Tab.2 Comparison of results

結(jié)果顯示，在3個場景中相較于文獻[20]算法，ACO-SA路徑長度減少了8.44%、9.97%和10.27%，運算時間分別縮短了29.17%、35.45%和37.71%，迭代次數(shù)縮減了64.71%、22%和16.28%，由于采用新的信息素更新機制，ACO-SA算法的最優(yōu)路徑長度較經(jīng)典算法有明顯改進，并且轉(zhuǎn)移概率中增大啟發(fā)函數(shù)的作用，將隨機性選擇和確定性選擇相結(jié)合，使收斂速度更快，更穩(wěn)定。

5 結(jié)論

針對傳統(tǒng)蟻群算法在路徑規(guī)劃中存在的優(yōu)化能力差，收斂速度慢，易陷入局部最優(yōu)的問題，本文提出一種改進的ACO-SA算法，主要結(jié)論如下。

1)改進啟發(fā)函數(shù)，結(jié)合初始情況下蟻群選擇的隨機性與準確性，避免了前期的盲目搜索，加快了收斂速度。

2)采用不均勻的初始信息素分布策略，初始信息素濃度呈散落式分布，減少了路徑中的冗余抉擇，提高了搜索效率。使用動態(tài)函數(shù)重新定義信息素揮發(fā)因子，確保了后期的快速迭代。

3)引入模擬退火算法中的“回火”機制，借助Metropolis抽樣法增加優(yōu)勢的篩選范圍，避免陷入局部最優(yōu)的困境。

4)在柵格環(huán)境中與多種算法進行對比驗證，在結(jié)果、速度、效率等方面均優(yōu)于其他算法，證明了ACO-SA算法的可行性。

未來將深入研究巡檢機器人面對動態(tài)障礙及優(yōu)先到達情況下的協(xié)調(diào)算法，助推變電站巡檢機器人的實踐應用。