宋霏羽 夏學(xué)知

（武漢數(shù)字工程研究所 武漢 430205）

1 引言

多無人機(jī)協(xié)同任務(wù)規(guī)劃是指多架無人機(jī)對多個(gè)目標(biāo)進(jìn)行偵察，以最小化出動(dòng)無人機(jī)架次，任務(wù)執(zhí)行時(shí)間最短和油耗成本最小為目標(biāo)函數(shù)構(gòu)建數(shù)學(xué)模型進(jìn)行求解［1］。分配問題是UAV異構(gòu)多模式，且約束條件復(fù)雜的最優(yōu)化NP問題［2］。目前研究中大都將多UAV協(xié)同偵察任務(wù)規(guī)劃系統(tǒng)模型轉(zhuǎn)化為經(jīng)典問題，如多旅行商問題（MTSP），車輛路徑問題（VRP）［3］。

在以往對于任務(wù)分配問題求解算法的研究中，絕大多數(shù)文獻(xiàn)都是采用人工智能算法進(jìn)行求解，這類算法雖然操作簡單，易于實(shí)現(xiàn)，但是很難保證收斂到全局最優(yōu)解［4～8］?；跀?shù)學(xué)規(guī)劃的啟發(fā)式算法克服了這些缺點(diǎn)，常見的啟發(fā)式算法有遺傳算法，禁忌算法，蟻群算法等，目前這些算法都取得了很大的進(jìn)展。由于路徑規(guī)劃是一個(gè)多約束的組合優(yōu)化問題，各個(gè)約束之間存在交叉重疊，目前常用的算法在路徑規(guī)劃中各有所長，但也有一些弱點(diǎn)。比如新興算法計(jì)算速度塊，準(zhǔn)確率相對較高，但在迭代過程中易停滯陷入局部最優(yōu)。所以，實(shí)際應(yīng)用中一般會(huì)根據(jù)具體的問題改進(jìn)算法［9～11］。

蟻群算法作為一種元啟發(fā)式算法，可以非常高效地解決路徑規(guī)劃問題。但蟻群算法也存在一些缺陷，如容易陷入局部最優(yōu)解，初期收斂速度慢，運(yùn)行時(shí)間長等。本文將針對以上缺點(diǎn)，對蟻群算法進(jìn)行改進(jìn)，使最后的算法性能更好，具有普適性和可推廣性。

2 基于交叉避免的蟻群算法設(shè)計(jì)

為了使無人機(jī)集群并行執(zhí)行任務(wù)所需要的時(shí)間最短，也就是要找出單個(gè)無人機(jī)最長執(zhí)行任務(wù)的路徑距離，并使這個(gè)路徑距離最小化。因此，可以把問題抽象為優(yōu)化局部路徑，那么可以優(yōu)化整個(gè)路徑。如果路徑中存在交叉，則這條路徑一定不是一個(gè)最優(yōu)路徑。這個(gè)結(jié)論啟發(fā)我們找到存在交叉的路徑并將該交叉解開，就可以減少整條路徑的長度。利用蟻群算法來尋找最優(yōu)航線，但在進(jìn)行最優(yōu)航線規(guī)劃時(shí)，易陷入局部最優(yōu)［12］。

2.1 交叉檢測

假設(shè)存在交叉的路徑中這兩條路徑的四個(gè)點(diǎn)分別是A(xa，ya)，B(xb，yb)，C(xc，yc)，D(xd，yd) ，并 且它們的交點(diǎn)是O(xo，yo)。因此有下面的線性方程組：

2.2 交叉消除

消除交叉的過程實(shí)際上可以簡化成將有交叉的那個(gè)部分的路徑的起點(diǎn)和終點(diǎn)中間的所有點(diǎn)進(jìn)行顛倒。這次的改變可以增加一次迭代優(yōu)化能力，增加了解的多樣性，這在遺傳算法領(lǐng)域相當(dāng)于是基因變異，在一定程度上能跳出局部最優(yōu)解。因?yàn)橄伻核惴ㄒ欢ǔ潭壬鲜钦答伒乃惴ǎ谒惴ê笃谟捎诮饪臻g路徑的信息素濃度遠(yuǎn)大于非解空間路徑的信息素濃度，而很容易陷入局部最優(yōu)，通過以上的改進(jìn)，可以在減少運(yùn)行時(shí)間的同時(shí)增強(qiáng)跳出局部最優(yōu)解的能力。

2.3 蟻群算法流程

1）初 始 化α，β，ρ，trailmatrix，antnum，cyclenum，L，H。

2）從開始的任務(wù)點(diǎn)出發(fā)，選擇下一個(gè)要訪問的任務(wù)點(diǎn)。

（1）找出已經(jīng)訪問過，后續(xù)禁止再訪問的任務(wù)點(diǎn)；

（2）綜合考慮信息素和啟發(fā)式函數(shù)計(jì)算每個(gè)任務(wù)點(diǎn)的出行概率；

（3）使用輪盤賭選擇要去的任務(wù)點(diǎn)。

3）找出當(dāng)前代最好的解決方案

（1）計(jì)算每只螞蟻的路線長度；

（2）找出最小的路徑長度；

（3）對最優(yōu)解交叉檢測，并重新計(jì)算長度，更新全局最優(yōu)路徑。

4）更新信息素濃度矩陣。

5）輸出全局最優(yōu)解。

3 實(shí)驗(yàn)結(jié)果

為了比較蟻群算法的準(zhǔn)確性，我們把改進(jìn)的蟻群算法的運(yùn)行結(jié)果和Lingo 17的運(yùn)行結(jié)果進(jìn)行比較。以下結(jié)論都是基于改進(jìn)蟻群算法運(yùn)算了8次取其中最好的結(jié)果，而且所有問題也被Lingo 17使用精確算法求解相關(guān)的優(yōu)化模型計(jì)算了一次。蟻群算法的參數(shù)設(shè)置：螞蟻數(shù)量為7，初始信息素濃度為1，揮發(fā)率ρ為0.2，迭代次數(shù)為100，α系數(shù)為1，β系數(shù)為5。蟻群算法使用Python在Pycharm上進(jìn)行實(shí)現(xiàn)，而Lingo 17解決優(yōu)化模型的計(jì)算平臺是阿里云的云計(jì)算平臺。從表1看到，由于蟻群算法是一種啟發(fā)式算法，而Lingo是精確算法，因此在運(yùn)行時(shí)間上蟻群算法的運(yùn)行時(shí)間遠(yuǎn)小于Lingo的運(yùn)行時(shí)間，而由于對蟻群算法引入了交叉檢測機(jī)制，使其能有效克服前期尋優(yōu)效果差和后期易局部收斂的缺點(diǎn)，因此改進(jìn)蟻群算法能獲得與Lingo相近的目標(biāo)結(jié)果。這個(gè)結(jié)果顯示出我們算法精度的優(yōu)良和運(yùn)行效率的良好。

表1 蟻群算法結(jié)果和Lingo優(yōu)化模型結(jié)果比較

4 結(jié)語

在本文中，我們運(yùn)用改進(jìn)的蟻群算法求解多UAV并行任務(wù)分配問題，重點(diǎn)對蟻群參數(shù)，適應(yīng)度函數(shù)和交叉的路徑檢測消除進(jìn)行詳細(xì)設(shè)計(jì)。以任務(wù)執(zhí)行時(shí)間最小為優(yōu)化目標(biāo)，解決目標(biāo)函數(shù)為最小化最長路徑的UAV群體并行任務(wù)分配的問題。首先討論了該蟻群算法的設(shè)計(jì)和交叉避免的算法流程。其次用eil51這個(gè)基準(zhǔn)數(shù)據(jù)集產(chǎn)生了四個(gè)不同規(guī)模的測試問題，并利用python進(jìn)行仿真。最后，解決了所有問題并且把得到的結(jié)果和Lingo產(chǎn)生的最優(yōu)解進(jìn)行比較。可以看出，大多數(shù)情況下，和最優(yōu)解結(jié)果比起來，蟻群算法提供的解的精度丟失不大，但蟻群算法所需要的運(yùn)行時(shí)間卻非常小。最后的測試結(jié)果顯示改進(jìn)后的算法雖然精度平均丟失4.07%，但運(yùn)算速度提高了96.4%。表明該算法能夠?qū)AV群體并行任務(wù)分配的問題成功求解，從而極大提高任務(wù)的執(zhí)行效率。