基于改進(jìn)人工魚群算法的無人機(jī)紅外巡檢線路規(guī)劃

王紅星， 黃鄭， 錢波， 徐淇， 李波

(1.江蘇方天電力技術(shù)有限公司，江蘇，南京 211102;2.國(guó)網(wǎng)江蘇省電力有限公司常州供電分公司，江蘇，常州 213000)

0 引言

輸電線路作為保障電力運(yùn)行的重要設(shè)備，加強(qiáng)對(duì)線路的巡檢尤為重要。傳統(tǒng)的輸電線路巡檢主要包括人工巡視、直升機(jī)巡視等，但由于輸電線路廣、巡檢地形復(fù)雜，給人工巡檢帶來極大的難度和不確定性，如采用直升機(jī)巡檢，費(fèi)用也相對(duì)較高。因此，無人機(jī)紅外巡檢開始進(jìn)入電力公司視野，并成為當(dāng)前輸電線路巡檢重要方式。通過無人機(jī)巡檢，可克服復(fù)雜地形和困難天氣因素的影響，基本實(shí)現(xiàn)全天候24 h的巡檢，但在無人機(jī)紅外巡檢中，核心問題為無人機(jī)路徑規(guī)劃。常用的無人機(jī)紅外巡檢路徑規(guī)劃包括A*算法、Apf算法，如：曹建秋等[1]采用改進(jìn)變異灰狼算法對(duì)無人機(jī)路徑規(guī)劃進(jìn)行優(yōu)化，得到航跡代價(jià)小、效果穩(wěn)定的無人機(jī)飛行路徑，但該方法存在計(jì)算量大的問題；王瓊等[2]采用Apf算法獲得了反饋性強(qiáng)的無人機(jī)航跡，但該方法在環(huán)境復(fù)雜的情況下容易出現(xiàn)局部極小值問題，因此無人機(jī)航線品質(zhì)無法得到保證。近些年來，人工魚群算法被廣泛應(yīng)用于路徑優(yōu)化，如賀風(fēng)婷等[3]、郭凡等[4]、陳靜靜等[5]、李新利等[6]、馬娜等[7]，由此可以看出人工魚群算法在路徑優(yōu)化方面受到熱捧。考慮到無人機(jī)巡檢中面臨威脅和最短路徑需求，本研究結(jié)合人工魚群算法的基本原理、優(yōu)勢(shì)以及缺陷，提出一種改進(jìn)人工魚群算法的無人機(jī)紅外巡檢航點(diǎn)規(guī)劃方法，從而在提高紅外巡檢航點(diǎn)精度的同時(shí)，減少巡檢威脅。

1 人工魚群算法基本原理

人工魚群算法是參考魚群聚群、覓食、追尾、隨機(jī)行為而衍生的一種智能尋優(yōu)算法，具有收斂速度快、操作方便、邏輯簡(jiǎn)單的特點(diǎn)。人工魚群算法原理是根據(jù)人工魚當(dāng)前狀態(tài)來選擇行為，包括自身當(dāng)前所處位置的的食物含量和食物感知分布，進(jìn)而改善自己的狀態(tài)[8]。通過以上行為選擇，人工魚最終會(huì)落在幾個(gè)主要的局部極值點(diǎn)上，而求解極大值的過程則是執(zhí)行魚群算法的覓食、追尾、聚群等，然后比較各自環(huán)境中食物的含量，進(jìn)而選擇下一步的行為。在魚群算法迭代過程中，若其尋優(yōu)結(jié)果的最優(yōu)解相較于公告牌信息有進(jìn)步，則公告牌記錄最優(yōu)解信息并進(jìn)行保存，反之則保留當(dāng)前公告牌信息，通過保留每次迭代運(yùn)算最優(yōu)解，實(shí)現(xiàn)輸出的最終解，即為最優(yōu)解。具體執(zhí)行步驟：

1)初始化魚群規(guī)模N、個(gè)體的初始位置、步長(zhǎng)step、擁擠度因子δ、人工魚視野visual、重復(fù)次數(shù)try-number等參數(shù)；

2)計(jì)算魚群中所有個(gè)體的適應(yīng)度值，并賦予最優(yōu)個(gè)體公告牌；

3)評(píng)價(jià)魚群中所有個(gè)體，并對(duì)其執(zhí)行魚群聚群、覓食等行為，同時(shí)更新個(gè)體，生成新的魚群；

4)評(píng)價(jià)新魚群中的所有個(gè)體，若其中存在個(gè)體優(yōu)于公告牌，則用該個(gè)體替代公告牌；

5)判斷是否滿足終止條件，若滿足最優(yōu)解在誤差范圍內(nèi)或達(dá)到最大迭代次數(shù)，則結(jié)束算法，反之則返回步驟3)，算法繼續(xù)。

以上步驟如圖1所示。

圖1 人工魚群算法實(shí)現(xiàn)流程圖

2 人工魚群算法改進(jìn)

無人機(jī)紅外巡檢可認(rèn)為是在一定范圍內(nèi)尋找最優(yōu)路徑，所以可將魚群算法應(yīng)用到無人機(jī)紅外巡檢路線規(guī)劃中。研究[9-10]認(rèn)為，由于魚群算法自身后期收斂速度慢、收斂精度低等，容易導(dǎo)致算法陷入局部收斂，難以獲得全局最優(yōu)解。因此，本文對(duì)魚群算法進(jìn)行改進(jìn)，通過引入自適應(yīng)策略改進(jìn)人工魚視野，以提高算法的收斂速度及收斂精度，通過引入人工魚群進(jìn)化策略，保證算法子代個(gè)體質(zhì)量，確保算法整體的搜索精度。

2.1 自適應(yīng)策略的人工魚視野

人工魚視野決定魚群的收斂速度。根據(jù)魚群算法特性和領(lǐng)域?qū)W習(xí)思想，提出采用式(1)的人工魚群視野自適應(yīng)改進(jìn)策略：

(1)

通過上述改進(jìn)看出，人工魚的視野隨人工魚的適應(yīng)度值進(jìn)行動(dòng)態(tài)調(diào)整。人工魚群在genuc代內(nèi)，其自適應(yīng)度值不斷變化，視野也隨之動(dòng)態(tài)調(diào)整，通過這種動(dòng)態(tài)調(diào)整，魚群向最優(yōu)解靠近，并進(jìn)行精細(xì)搜索；達(dá)到genuc代后，人工魚自適應(yīng)度值維持穩(wěn)定，即人工魚視野保持不變，說明此時(shí)魚群可能已經(jīng)陷入局部收斂，應(yīng)進(jìn)行全局大范圍的重新搜索，并將genuc代的人工魚視野值設(shè)定為重新搜索的視野初始值。

2.2 人工魚群進(jìn)化策略

考慮到無人機(jī)紅外巡檢的復(fù)雜度和計(jì)算量，參考馬梓元等的思路，引入人工魚群進(jìn)化策略，在該策略中，采用無性繁殖淘汰每代進(jìn)化中較差的個(gè)體，保留較優(yōu)的個(gè)體，確保算法整體搜索精度。具體步驟是在聚群、追尾、覓食等行為步驟后，根據(jù)每代人工魚適應(yīng)度值對(duì)人工魚個(gè)體進(jìn)行優(yōu)劣排序，然后篩選、淘汰適應(yīng)度值較低的人工魚個(gè)體，最后選擇適應(yīng)度值較高的人工魚個(gè)體，以替代淘汰的人工魚個(gè)體。具體改進(jìn)如圖2所示。

圖2 人工魚群算法進(jìn)化策略改進(jìn)

通過圖2的改進(jìn)，可保證算法中的子代個(gè)體質(zhì)量，確保整體搜索精度。

3 基于改進(jìn)魚群算法的無人機(jī)紅外巡檢路徑規(guī)劃

3.1 威脅模型構(gòu)建

無人機(jī)紅外巡檢航線規(guī)劃中，由于實(shí)際環(huán)境存在障礙物，需在避開障礙物的前提下按照規(guī)劃路徑進(jìn)行飛行。設(shè)無人機(jī)從原點(diǎn)出發(fā)，在飛行中有n個(gè)半徑不同的圓形障礙物區(qū)間，具體如圖3所示。根據(jù)障礙區(qū)間半徑、起點(diǎn)與目標(biāo)點(diǎn)距離、輸出的標(biāo)準(zhǔn)精度，將路徑分為n-1段。采用二維符號(hào)xi、yi表示路徑點(diǎn)，則每個(gè)航跡點(diǎn)的橫坐標(biāo)可表示為(x1,…,xn)，縱坐標(biāo)yi則表示航跡規(guī)劃的任務(wù)。

圖3 無人機(jī)紅外巡檢路線規(guī)劃威脅模型

為與實(shí)際情況更為貼合，將無人機(jī)的飛行區(qū)域網(wǎng)格劃分為10*8。在飛行區(qū)域內(nèi)設(shè)置6個(gè)障礙物，用圓形表示，其中心點(diǎn)坐標(biāo)和威脅半徑如表1所示。

表1 障礙物位置

無人機(jī)紅外巡檢的起點(diǎn)為坐標(biāo)原點(diǎn)(0,0)，目標(biāo)點(diǎn)坐標(biāo)為(90,34)。設(shè)從原點(diǎn)到終點(diǎn)總需經(jīng)過n個(gè)中間點(diǎn)，那么無人機(jī)飛行路徑的長(zhǎng)度則可以表示為

R={S,(x1,y1),…,(xn,yn),E}

(2)

在區(qū)域內(nèi)判斷路徑是否可行，首先是以區(qū)域內(nèi)的點(diǎn)為初始點(diǎn)，用一個(gè)數(shù)組保存障礙物的頂點(diǎn)信息，然后再用一組數(shù)組表示每條路徑與圓相切的頂點(diǎn)信息。設(shè)某路徑與障礙物圓相切，則cv加1，統(tǒng)計(jì)該路徑與障礙物相切的切點(diǎn)總數(shù)：

(3)

3.2 航線問題描述與模型構(gòu)建

無人機(jī)紅外巡檢路線規(guī)劃需避開障礙物和規(guī)劃最短路徑，因此路線距離的目標(biāo)函數(shù)可表示為：

(4)

由于橫坐標(biāo)x被平分為n等份，因此xi+1-xi為常數(shù)，且由劃分步數(shù)、X坐標(biāo)距離、每步坐標(biāo)間橫向距離決定。本研究將X坐標(biāo)距離數(shù)值設(shè)為90，步數(shù)設(shè)置為12，每步坐標(biāo)間的橫向距離為7.5，則xi+1-xi=7.5。

3.3 基于改進(jìn)人工魚群算法的最優(yōu)路徑求解

根據(jù)以上的模型和改進(jìn)的人工魚群算法，用人工魚群算法對(duì)目標(biāo)函數(shù)進(jìn)行求解。具體求解步驟：

(1)導(dǎo)入網(wǎng)格模型和障礙物的數(shù)據(jù)，生成無人機(jī)模擬路徑規(guī)劃模型；

(2)初始化人工魚群算法的各個(gè)參數(shù)，包括步長(zhǎng)、重復(fù)次數(shù)等；

(3)生成初始化魚群，執(zhí)行聚群、追尾和覓食行為，并利用步長(zhǎng)自適應(yīng)策略更新步長(zhǎng)；

(4)計(jì)算人工魚個(gè)體的適應(yīng)度值，利用個(gè)體進(jìn)化策略評(píng)估人工魚的行為，并選擇更為優(yōu)秀的個(gè)體執(zhí)行魚群行為；

(5)計(jì)算每個(gè)人工魚的適應(yīng)度，選擇適應(yīng)度最高的人工魚刷新公告板；

(6)判斷是否達(dá)到算法條件，若達(dá)到則輸出最優(yōu)路徑長(zhǎng)度，沒有則繼續(xù)(4)。

4 仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)置

仿真編程軟件采用MATLAB 2018a，魚數(shù)規(guī)模N=10，最大迭代數(shù)NC=300，移動(dòng)步長(zhǎng)step=0.4，δ=0.618，visual=1。

4.2 算法比較

為驗(yàn)證提出的改進(jìn)人工魚群算法的可行性和優(yōu)越性，分別采用改進(jìn)人工魚群算法、步長(zhǎng)自適應(yīng)人工魚群算法、傳統(tǒng)人工魚群算法進(jìn)行50次無人機(jī)紅外巡檢航點(diǎn)規(guī)劃仿真，得到圖4的路線規(guī)劃二維路徑圖和圖5的三維路徑規(guī)劃圖。

圖4 3種優(yōu)化算法下無人機(jī)紅外巡檢路徑二維圖

圖5 不同優(yōu)化算法下的無人機(jī)紅外巡檢路徑三維圖

3種優(yōu)化算法下航線的平均長(zhǎng)度和線路的平均長(zhǎng)度方差如表2和表3。

表2 不同算法的路線平均值

表3 不同算法仿真的路線方差

由表2可知，相較于傳統(tǒng)人工魚群算法和步長(zhǎng)自適應(yīng)人工魚群算法規(guī)劃的無人機(jī)紅外巡檢航線，提出的改進(jìn)人工魚群算法規(guī)劃的航線平均長(zhǎng)度更短，說明提出的算法更優(yōu)越、效率更高。

由表3可知，提出的改進(jìn)人工魚群算法的方差小于傳統(tǒng)人工魚群算法和步長(zhǎng)自適應(yīng)人工魚群算法方差，說明尋優(yōu)結(jié)果更接近真實(shí)值，即算法的穩(wěn)定性更好、尋優(yōu)效果更準(zhǔn)確。

5 總結(jié)

本研究提出的基于改進(jìn)人工魚群算法的無人機(jī)紅外巡檢規(guī)劃可準(zhǔn)確避開障礙物區(qū)間，且相較于傳統(tǒng)人工魚群算法，具有更短、更優(yōu)的規(guī)劃路徑，進(jìn)而縮短了檢修人員到達(dá)搶修地點(diǎn)的時(shí)間，提高了工作效率。但本研究的局限在于只是從仿真的角度改進(jìn)人工魚群算法在航點(diǎn)線路的優(yōu)化進(jìn)行研究，以上優(yōu)化效果還有待進(jìn)一步實(shí)際應(yīng)用論證。