基于改進遺傳算法的多無人機協(xié)同任務(wù)規(guī)劃

趙民全

(解放軍92785部隊，遼寧 葫蘆島 125208)

0 引 言

多無人機協(xié)同任務(wù)規(guī)劃是針對2架及2架以上的無人機在復(fù)雜戰(zhàn)場環(huán)境中協(xié)同執(zhí)行任務(wù)時，處理無人機之間的配合和以代價最小、算法最優(yōu)、路徑最短為目標來進行任務(wù)規(guī)劃的技術(shù)。相較于單一無人機作戰(zhàn)，多無人機協(xié)同作戰(zhàn)有著更好的任務(wù)處理靈活性，并且通過相互配合，可以增加攻擊和防御能力，提高打擊效率和偵察成功率。

該技術(shù)的研究重點多集中于網(wǎng)絡(luò)化情況下聯(lián)合無人空戰(zhàn)系統(tǒng)協(xié)同作戰(zhàn)[1]。如自治編隊混合主動控制項目(MICA)[2]包括了無人機協(xié)同任務(wù)規(guī)劃、協(xié)同跟蹤、編隊控制等研究方向；異構(gòu)無人機群實時協(xié)同與控制項目[3]是研究異構(gòu)無人機協(xié)同控制及任務(wù)分配的技術(shù)，其理念就是將偵察區(qū)域劃分為多個分區(qū),一架無人機完成一個分區(qū)的任務(wù),分別建立單個的旅行商問題模型，再采用模擬退火算法進行進一步的優(yōu)化；文獻[4]則是將無人機看作多個智能體，利用它們之間的交互對任務(wù)進行最優(yōu)規(guī)劃。

采用多旅行商問題建立多無人機協(xié)同規(guī)劃模型，基于改進遺傳算法對多無人機任務(wù)進行規(guī)劃，采用模擬退火算法與基本遺傳算法相結(jié)合的方式對遺傳算法進行改進設(shè)計，并進行仿真驗證分析。

1 多旅行商問題建模

多旅行商問題(MTSP)[5-6]是旅行商問題(TSP)的進一步發(fā)展，是一種典型的組合優(yōu)化問題，是解決在多名旅行商要拜訪多個地點時，如何能快速找到逐次抵達各地點一次后再回到起點的最短路徑問題。模型設(shè)計以點0作為起始點，表示旅行商的始發(fā)地，點1到點L分別表示不同的城市，m個旅行商從城市0出發(fā)分別去逐個拜訪,每一個城市都僅有一個旅行商到達,最后全部回到出發(fā)城市0。

建立多旅行商問題模型：

(1)

式(1)為目標函數(shù)式，為m個旅行商的總路程最小值，其中：

(2)

式(2)表示旅行商各自的路程，其中Cij表示旅行商經(jīng)過對應(yīng)弧段(i,j)用去的時間。

限定條件為：

(3)

式(3)表示從指定城市0出發(fā)，所有城市有且只有一個旅行商進行一次訪問。

2 基于遺傳算法的多無人機任務(wù)規(guī)劃

遺傳算法[7]是一種能有效求解最優(yōu)化問題的算法，是遵循自然界“優(yōu)勝劣汰”法則的方法。首先形成一組初始解群，然后通過選擇、交叉和變異等遺傳操作產(chǎn)生新一組滿足設(shè)定目標的候選解，循環(huán)開展適應(yīng)度評價、選擇、交叉和變異遺傳等操作，逐步迭代優(yōu)化，直至得到最優(yōu)目標解。

在使用遺傳算法建模上，我們對適應(yīng)度函數(shù)復(fù)制、交叉和變異等指標操作進行如下選擇和設(shè)定。

適應(yīng)度函數(shù)一般要求非負,這里通過變換將多重旅行商問題的目標函數(shù)變?yōu)檫m應(yīng)度函數(shù)。復(fù)制選擇上采用輪盤賭策略法，交叉在遺傳操作中起核心作用，可增強遺傳算法搜索能力。這里采用基本遺傳算法部分匹配交叉算子，其中變異在遺傳操作中是用來維持群體的多樣性的，對于多旅行商問題而言，染色體變異可以通過交換2個隨機位置上的基因來實現(xiàn)。

偵察無人機數(shù)量N為8時，假設(shè)需要偵察300 m×450 m的區(qū)域，進行仿真后可獲得基本遺傳算法規(guī)劃效果如圖1所示[8]。

圖1 N=8時遺傳算法四次求解仿真曲線

實驗結(jié)果數(shù)據(jù)如表1所示。

表1 N=8時遺傳算法仿真數(shù)據(jù)

可見當無人機數(shù)量為8架時，基本遺傳算法能夠基本完成對多無人機任務(wù)規(guī)劃問題的求解，給無人機分配目標位置使得每架無人機走過的路程開始不太均勻，幾次實驗中優(yōu)化出的最短飛行距離和迭代次數(shù)的結(jié)果很接近，但求出最短距離和迭代次數(shù)數(shù)值都較高，優(yōu)化效果有待提高。

3 基于改進遺傳算法的多無人機任務(wù)規(guī)劃

從遺傳算法實例仿真結(jié)果可以看出，其存在算法收斂性能差、找最優(yōu)解時間長等不足之處。為使遺傳算法得到更好的應(yīng)用，需要在改善算法搜索能力和提高算法收斂速度等方面加以改進。

現(xiàn)將模擬退火算法的Metorpolis準則[9-10]引入遺傳算法中,該算法是基于對溫度控制過程的模擬，用冷卻進度表來控制算法的進程，通過控制遺傳算法子代染色體的選擇來實現(xiàn)。隨著進化過程的進行,算法在控制參數(shù)T逐步趨向于零時最終獲取相對于全局的最優(yōu)解。該方法使解的收斂從局部最優(yōu)中跳出,最終達到全局收斂，同時實現(xiàn)了算法收斂速度的提升。

3.1 混合算法

模擬退火部分采用Metorpolis準則，采取內(nèi)外雙層循環(huán)模式，內(nèi)循環(huán)終止準則選用連續(xù)若干次搜索得到新解的變化較小；外循環(huán)終止準則選用最優(yōu)解在算法運行過程中在較長迭代次數(shù)內(nèi)保持不變，得到交叉退火之后的新種群：

(4)

(5)

式中：Pi為接受第i個新個體的概率；Pj為接受第j個新個體的概率；si,sj為第i,j個原始個體序號；ci,cj為第i,j個新個體序號；fit(*)為適應(yīng)度函數(shù)；T為控制參數(shù)。

通過遺傳變異算子進行子代路徑變異操作獲得新個體，最后得到變異退火之后的新種群：

(6)

式中：i為變異前狀態(tài)；i′為變異后狀態(tài)。

根據(jù)溫度終止條件判斷是否需要重復(fù)以上步驟，通過逐步迭代獲得最優(yōu)解。

3.2 實例仿真結(jié)果

無人機數(shù)量N為8時，假設(shè)需要偵察300 m×450 m的區(qū)域，混合模擬退火遺傳算法規(guī)劃效果如圖2所示。

圖2 N=8時改進遺傳算法四次求解仿真結(jié)果

實驗結(jié)果數(shù)據(jù)如表2所示。

表2 N=8時改進遺傳算法仿真數(shù)據(jù)

可見當無人機數(shù)量為8架時，改進遺傳算法能夠完成對多無人機任務(wù)規(guī)劃問題的求解，優(yōu)化出的最短飛行距離和迭代次數(shù)的結(jié)果很接近，求出的最短距離較小，以總飛行路程值來看，優(yōu)化效果比較良好。對比2次仿真結(jié)果可知：在約束條件不變的情況下，混合模擬退火遺傳算法求得的最優(yōu)值即最短飛行距離比基本遺傳算法都有明顯的優(yōu)化，迭代次數(shù)上更少，即優(yōu)化時間更短。由此得出，混合模擬退火遺傳算法確實使基本遺傳算法在尋得最優(yōu)解的能力上得到優(yōu)化。

4 結(jié)束語

本文以飛行時間最短作為優(yōu)化目標，建立了組合優(yōu)化模型，采用遺傳算法進行求解，并用多旅行商問題對模型進行修正，進而采用混合模擬算法和遺傳算法相結(jié)合的策略對傳統(tǒng)遺傳算法進行改進，將模擬退火算法與遺傳算法過程整合成一個雙循環(huán)，由模擬退火算法判定是否保留該解。最后，改進后的遺傳算法仿真實驗表明：基于模擬退火算法對遺傳算法的改進是可行的，具有一定的工程應(yīng)用價值。