基于改進蟻群算法的無人機集群任務規(guī)劃?

宋霏羽 夏學知

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

1 引言

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

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

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

2 基于交叉避免的蟻群算法設計

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

2.1 交叉檢測

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

2.2 交叉消除

消除交叉的過程實際上可以簡化成將有交叉的那個部分的路徑的起點和終點中間的所有點進行顛倒。這次的改變可以增加一次迭代優(yōu)化能力，增加了解的多樣性，這在遺傳算法領域相當于是基因變異，在一定程度上能跳出局部最優(yōu)解。因為蟻群算法一定程度上是正反饋的算法，在算法后期由于解空間路徑的信息素濃度遠大于非解空間路徑的信息素濃度，而很容易陷入局部最優(yōu)，通過以上的改進，可以在減少運行時間的同時增強跳出局部最優(yōu)解的能力。

2.3 蟻群算法流程

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

2）從開始的任務點出發(fā)，選擇下一個要訪問的任務點。

（1）找出已經訪問過，后續(xù)禁止再訪問的任務點；

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

（3）使用輪盤賭選擇要去的任務點。

3）找出當前代最好的解決方案

（1）計算每只螞蟻的路線長度；

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

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

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

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

3 實驗結果

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

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

4 結語

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