宣麗萍， 李 崢

(1.華南師范大學(xué) 數(shù)據(jù)科學(xué)與工程學(xué)院， 廣東 汕尾 516600； 2.黑龍江科技大學(xué) 電氣與控制工程學(xué)院， 哈爾濱 150022)

0 引 言

我國(guó)部分礦產(chǎn)資源儲(chǔ)藏量處于世界前列。豐富的礦產(chǎn)資源是強(qiáng)大的綜合國(guó)力的體現(xiàn)，但同時(shí)也給國(guó)家相關(guān)部門的監(jiān)督、管理帶來(lái)了不小的困難和挑戰(zhàn)。將無(wú)人機(jī)應(yīng)用到采礦領(lǐng)域是對(duì)該技術(shù)的一種新探索，也是對(duì)傳統(tǒng)礦區(qū)管理技術(shù)的革新[1-2]。無(wú)人機(jī)巡檢最早應(yīng)用與電力行業(yè)，劉壯等[3]詳細(xì)總結(jié)了近年來(lái)無(wú)人機(jī)輸電線路巡檢方面的研究，闡述了無(wú)人機(jī)高壓線路巡檢技術(shù)的應(yīng)用優(yōu)勢(shì)及其發(fā)展現(xiàn)狀。彭向陽(yáng)等[4]提出了大型無(wú)人直升機(jī)電力巡檢技術(shù)研究、裝備研制和示范應(yīng)用方面的實(shí)用化目標(biāo)和策略。無(wú)人機(jī)電力巡檢技術(shù)為其在礦區(qū)的應(yīng)用提供了寶貴經(jīng)驗(yàn)。張力等[5]設(shè)計(jì)了一種基于超聲波測(cè)距的井下煤礦四旋翼巡檢無(wú)人機(jī)，能夠?qū)崟r(shí)獲取井下環(huán)境信息并通過(guò)無(wú)線網(wǎng)絡(luò)將采集到的數(shù)據(jù)和視頻信息實(shí)時(shí)回傳至控制臺(tái)。徐金鑫[6]對(duì)無(wú)人機(jī)露天礦區(qū)巡檢控制方式進(jìn)行了深入研究。綜上所述，無(wú)人機(jī)在煤礦應(yīng)用領(lǐng)域具有巨大的優(yōu)勢(shì)和潛能，筆者將根據(jù)某煤礦的建筑平面圖，對(duì)傳統(tǒng)蟻群算法進(jìn)行改進(jìn)，設(shè)計(jì)出的礦區(qū)巡檢路徑規(guī)劃策略，通過(guò)仿真實(shí)驗(yàn)對(duì)比算法改進(jìn)前后巡檢性能的差異，驗(yàn)證改進(jìn)后算法的優(yōu)越性。

1 巡檢目標(biāo)路徑的規(guī)劃

1.1 巡檢目標(biāo)的確定

礦區(qū)位于安徽省境內(nèi)，該煤礦圍墻內(nèi)工業(yè)場(chǎng)地占地面積為27.775 km2，其中，礦井占地面積為19.135 km2。根據(jù)圖紙上標(biāo)注的建筑單位及其方位信息，共選擇了20個(gè)主要單位作為巡檢對(duì)象，將目標(biāo)單位質(zhì)點(diǎn)化，巡檢目標(biāo)方位與距離信息如圖1 所示。

圖1 巡檢目標(biāo)方位Fig. 1 Patrol target orientation

1.2 數(shù)學(xué)模型的建立

巡檢目標(biāo)方位圖確定后，需要為無(wú)人機(jī)設(shè)計(jì)一條巡視路線，從初始點(diǎn)出發(fā)，在多個(gè)點(diǎn)之間進(jìn)行無(wú)人機(jī)巡航，在規(guī)定時(shí)間內(nèi)返回出發(fā)點(diǎn)。根據(jù)上述要求需要找出合理的巡航路徑，使其在規(guī)定時(shí)間內(nèi)無(wú)人機(jī)巡航的點(diǎn)盡可能的多[7]。假設(shè)無(wú)人機(jī)可短時(shí)間垂直升空的充電四旋翼式飛行器，且對(duì)巡檢時(shí)間和巡檢速度等有限制。為在規(guī)定時(shí)間內(nèi)巡航多個(gè)地點(diǎn)，要求對(duì)其路徑進(jìn)行科學(xué)規(guī)劃達(dá)到目標(biāo)函數(shù)最優(yōu)，其數(shù)學(xué)模型為

(1)

(2)

式中：0,N+1——出發(fā)點(diǎn)和返回點(diǎn)(同一個(gè)點(diǎn)，方便模型計(jì)算)；

V——N個(gè)目標(biāo)點(diǎn)的集合；

V0——目標(biāo)和0點(diǎn)集合；

VN+1——無(wú)人機(jī)和N+1點(diǎn)的集合；

dij——i到j(luò)的距離；

Ti——到達(dá)i的時(shí)間；

xij——0或1變量，表示是否存在；

v——無(wú)人機(jī)飛行速度；

T——最大巡航時(shí)間。

由式(1)可知，其表示希望在規(guī)定時(shí)間內(nèi)盡可能的巡視更多的目標(biāo)地點(diǎn)。式(2)為約束條件，其表示使用一架無(wú)人機(jī)進(jìn)行巡檢，每個(gè)點(diǎn)最多被巡航一次，保證流量守恒，同時(shí)，巡檢必須在規(guī)定時(shí)間內(nèi)完成巡航任務(wù)等約束。

1.3 改進(jìn)型蟻群算法的礦區(qū)巡檢路徑規(guī)劃

針對(duì)傳統(tǒng)蟻群算法易造成局部最優(yōu)和計(jì)算時(shí)間長(zhǎng)的不足[8-11]，在算法改進(jìn)時(shí)調(diào)整思路，不要求所有螞蟻都找到最佳路徑，只要一只螞蟻找到最優(yōu)路徑即可，同時(shí)，對(duì)信息素的權(quán)衡標(biāo)準(zhǔn)進(jìn)行調(diào)整，借助輪盤賭算法，通過(guò)該方法及時(shí)調(diào)整不同巡檢目標(biāo)之間的轉(zhuǎn)換狀態(tài)，當(dāng)某個(gè)目標(biāo)適應(yīng)值越高，就說(shuō)明該目標(biāo)地點(diǎn)被選中的可能性越大，最后進(jìn)行較優(yōu)路徑結(jié)點(diǎn)交叉操作，當(dāng)陷入局部最優(yōu)時(shí)，通過(guò)來(lái)自不同目標(biāo)地的路徑進(jìn)行交叉操作來(lái)更新路徑，提高搜索效率。

利用蟻群算法進(jìn)行路徑規(guī)劃時(shí)，構(gòu)建合理的路徑供螞蟻選擇，當(dāng)t=0時(shí)，所有路線上均含有同等濃度的信息素。螞蟻由目標(biāo)地i移動(dòng)到目標(biāo)地j的概率為

(3)

式中：τij——i、j連線上的信息素量；

Ak——螞蟻下一步可去城市的集合；

i、j——起點(diǎn)和終點(diǎn)；

在具體運(yùn)算時(shí)，假設(shè)某個(gè)路線被選定，立即重新計(jì)算信息素的分布情況，第一次巡檢時(shí)將設(shè)定一個(gè)初始濃度，當(dāng)一條路線巡檢過(guò)之后，信息素濃度就會(huì)相應(yīng)上升或下降，經(jīng)反復(fù)迭代計(jì)算之后，所有目標(biāo)點(diǎn)的濃度值均處在合理區(qū)間。初始濃度超出一定的閾值，線路更新時(shí)極易出現(xiàn)“早熟”現(xiàn)象，最快搜索到的線路有可能并不是最短的，反復(fù)搜索又會(huì)使時(shí)間增加。每次迭代后，所產(chǎn)生的信息素計(jì)算方法為

(4)

式中，ρ——自適應(yīng)調(diào)整系數(shù)。

傳統(tǒng)蟻群算法的實(shí)現(xiàn)往往容易受多種外界環(huán)境變化的干擾，引入自適應(yīng)調(diào)整系數(shù)ρ優(yōu)化傳統(tǒng)蟻群算法，處理傳統(tǒng)算法在實(shí)現(xiàn)時(shí)存在的收斂慢、容易產(chǎn)生局部循環(huán)等問(wèn)題。自適應(yīng)調(diào)整公式為

(5)

式中，C——隨機(jī)常數(shù)。

同時(shí)，在算法改進(jìn)中引入輪盤賭算法，即將輪盤算子更新方法加入到蟻群信息素轉(zhuǎn)移函數(shù)中，可以提高函數(shù)收斂速度，計(jì)算方法為

(6)

式中：q——任一只螞蟻經(jīng)第k個(gè)目標(biāo)至第k+1個(gè)目標(biāo)中間所有的連接線的數(shù)量， 即集合i、j子區(qū)間的個(gè)數(shù)；

fij——第i個(gè)和第j個(gè)子區(qū)間解的適應(yīng)度；

采用式(6)設(shè)定初始值C，自適應(yīng)調(diào)整揮發(fā)系數(shù)ρ。改進(jìn)型蟻群算法的礦區(qū)巡檢路徑規(guī)劃具體算法步驟分為9步。

步驟1初始化螞蟻參數(shù)M，文中設(shè)置為50只螞蟻，新建一個(gè)50×n的矩陣作為禁忌表，其中，n為巡航點(diǎn)的個(gè)數(shù)，n=20，將起始禁忌表設(shè)為空集，在禁忌表中的第i行第j列的數(shù)據(jù)為o則表示第i只螞蟻訪問(wèn)的第j個(gè)點(diǎn)為o。

步驟2生成初始解，文中設(shè)計(jì)生成種群規(guī)模為50的初始解，鑒于文中數(shù)據(jù)特點(diǎn)，一共有20個(gè)巡視點(diǎn)，首先生成一個(gè)50×20的矩陣，且每行的第一個(gè)數(shù)據(jù)為設(shè)定的出發(fā)點(diǎn)，在生成初始解時(shí)第一個(gè)解設(shè)置為從1到20的順序巡視路線(除了出發(fā)點(diǎn)之外的19個(gè)點(diǎn)順序排列)，第二條路徑是從20到1的逆序巡視路線，其他的48條初始解通過(guò)將20個(gè)點(diǎn)隨機(jī)排序生成，進(jìn)行下一步操作。

步驟3構(gòu)造可行解，首先將出發(fā)點(diǎn)加入第k行第1列的禁忌表中，初始k為1。

步驟4采用式(6)通過(guò)信息素濃度大小使用輪盤賭機(jī)制，根據(jù)信息素濃度大小作為各個(gè)點(diǎn)的權(quán)重判斷各個(gè)節(jié)點(diǎn)被選擇的概率，按照新?tīng)顟B(tài)轉(zhuǎn)移概率選擇下一個(gè)節(jié)點(diǎn)加入禁忌表，加入禁忌表中的點(diǎn)為下一個(gè)巡航位置。

步驟5根據(jù)式(2)判斷無(wú)人機(jī)是否能夠在規(guī)定時(shí)間返回出發(fā)點(diǎn)，從而確定螞蟻周游是否結(jié)束，若周游結(jié)束，無(wú)人機(jī)無(wú)法在規(guī)定時(shí)間內(nèi)返回出發(fā)點(diǎn)，則將剛選擇的點(diǎn)踢出路徑，并在路徑中加上初始點(diǎn)用來(lái)表示無(wú)人機(jī)返回出發(fā)點(diǎn)，該螞蟻的行駛路徑設(shè)計(jì)完成，螞蟻k=k+1表示為下一只螞蟻設(shè)計(jì)路徑，并返回步驟5，否則返回到步驟4繼續(xù)搜索下一個(gè)點(diǎn)進(jìn)行巡航。

步驟6判斷螞蟻k是否等于M+1，即判斷是否所有螞蟻都設(shè)計(jì)了路徑，是則進(jìn)行下一步驟，否則返回到步驟3。

步驟7根據(jù)式(1)計(jì)算在規(guī)定時(shí)間內(nèi)巡航的點(diǎn)的個(gè)數(shù)，計(jì)算禁忌表中每行非零的個(gè)數(shù)再減去1，并對(duì)其排序，然后根據(jù)式(4)、(5)對(duì)選出的50條路徑的巡航線路進(jìn)行信息素更新，未被選中的路徑也會(huì)更新信息素，未被選中的路徑信息素會(huì)逐步揮發(fā)，被選中的路徑次數(shù)信息素濃度增加越大，因此，下次被選中的概率也越大。

步驟8將本輪迭代的最優(yōu)解跟當(dāng)前最優(yōu)解進(jìn)行對(duì)比，若巡邏點(diǎn)更多，則更新最優(yōu)解；若巡邏點(diǎn)數(shù)量相同，則比較巡邏時(shí)間，巡邏時(shí)間較少的為優(yōu)。

步驟9判斷是否滿足結(jié)束條件，迭代次數(shù)是否達(dá)到限制，文中設(shè)置迭代次數(shù)400次；或者在規(guī)定迭代次數(shù)內(nèi)最優(yōu)解未發(fā)生變化，是則結(jié)束輸出結(jié)果，否則進(jìn)行較優(yōu)路徑節(jié)點(diǎn)交叉操作，然后判斷是否滿足結(jié)束條件，是則輸出結(jié)果，否則返回到步驟1，進(jìn)行下一輪迭代， 直至循環(huán)結(jié)束。具體算法流程如圖2所示。

圖2 改進(jìn)型蟻群算法流程Fig. 2 Improved ant colony algorithm

2 仿真與結(jié)果分析

四旋翼無(wú)人機(jī)巡航速度為20 km/h，巡航時(shí)間未定。文中分別設(shè)定巡航5、7、10 min，對(duì)比改進(jìn)型蟻群算法和傳統(tǒng)蟻群算法的結(jié)果，分析算法的優(yōu)越性。當(dāng)巡檢時(shí)間為5 min，出發(fā)點(diǎn)為1號(hào)位置時(shí)，通過(guò)改進(jìn)后蟻群算法和傳統(tǒng)蟻群算法得出結(jié)果如圖3所示。從圖3可知，改進(jìn)后蟻群算法所獲得的結(jié)果明顯較傳統(tǒng)蟻群算法的巡航路徑更加簡(jiǎn)潔，巡檢路線未出現(xiàn)交叉，從數(shù)據(jù)可以看出，在規(guī)定時(shí)間內(nèi)改進(jìn)型蟻群算法巡視了18個(gè)目標(biāo)地，傳統(tǒng)蟻群算法巡視目標(biāo)地個(gè)數(shù)為17個(gè)，改進(jìn)后算法性能更優(yōu)越。

當(dāng)巡檢時(shí)間為7 min，結(jié)果如圖4所示。從圖4可知，改進(jìn)型蟻群算法獲得結(jié)果能巡視20個(gè)目標(biāo)地，但傳統(tǒng)蟻群算法只能巡視19個(gè)目標(biāo)地，同時(shí)，改進(jìn)后算法巡視總長(zhǎng)度為2 077 m，而未改進(jìn)時(shí)算法的結(jié)果巡視總長(zhǎng)度為2 079 m，可以看出，改進(jìn)型蟻群算法所求結(jié)果更加精確。

圖3 5 min巡檢路線Fig. 3 5 min inspection route

圖4 7 min巡檢路線Fig. 4 7 min inspection route

當(dāng)巡檢時(shí)間增加到10 min時(shí)，四旋翼無(wú)人機(jī)已經(jīng)能做到巡檢完所有地點(diǎn)并返回出發(fā)點(diǎn)，因此，此時(shí)比較的就是哪一種巡檢策略能更短的時(shí)間內(nèi)巡視完所有的目標(biāo)地，具體結(jié)果如圖5所示。

圖5 10 min巡檢路線Fig. 5 10 min inspection route

從圖5可知，兩種算法都能設(shè)計(jì)出合理路線將所有目標(biāo)地巡檢一遍，但是改進(jìn)型蟻群算法飛行距離為2 108 m，而傳統(tǒng)蟻群算法的路徑需要飛行2 178 m。

3 結(jié) 論

(1) 當(dāng)巡檢時(shí)間為5 min，初始位置均為信號(hào)樓時(shí)，改進(jìn)后蟻群算法所獲得的巡檢路線圖明顯較傳統(tǒng)蟻群算法更加簡(jiǎn)潔，且算法改進(jìn)后巡檢路線未出現(xiàn)交叉，仿真表明，在規(guī)定時(shí)間內(nèi)改進(jìn)型蟻群算法比改進(jìn)前多巡檢1個(gè)目標(biāo)地，綜合對(duì)比改進(jìn)后算法性能更優(yōu)越。

(2) 當(dāng)巡檢時(shí)間為7 min，初始位置均為信號(hào)樓時(shí)，在規(guī)定時(shí)間內(nèi)改進(jìn)型蟻群算法比改進(jìn)前多巡檢1個(gè)目標(biāo)地，同時(shí)，改進(jìn)后算法巡視總長(zhǎng)度比改進(jìn)前少2 m，改進(jìn)型蟻群算法所求結(jié)果更加精確。當(dāng)巡檢時(shí)間為10 min，初始位置均為信號(hào)樓時(shí)兩種算法都能設(shè)計(jì)出合理路線將所有目標(biāo)地有巡檢一遍，但是改進(jìn)型蟻群算法飛行距離為2 108 m，而傳統(tǒng)蟻群算法的路徑需要飛行2 178 m,改進(jìn)型蟻群算法飛行距離更短。