基于改進型遺傳算法的多無人機任務分配

徐賓王，寧 芊

（四川大學電子信息學院，成都 610000）

0 引言

無人機（unmanned aerial vehicle, UAV）因其成本低、靈活性高、隱蔽性強而被廣泛應用于戰場偵察、聯合攻擊、應急救援等行動［1-2］。無人機集群相對于單架無人機在執行任務上有更多的優勢，可以執行更多樣化的任務，以及更高效地進行大范圍搜索［3］。

對于無人機航跡規劃問題，優化算法可分為兩類［4］。第一類是傳統優化算法，例如動態規劃算法、A*算法、Dijkstra 算法、隨機搜索樹算法等［5-10］，該類算法為確定算法，搜索解空間范圍較大、效率較低，只適合場景和約束簡單的情況；第二類是群智能優化算法，例如遺傳算法、粒子群算法、蟻群算法、差分進化算法等［11-15］，該類算法往往具有顯式的并行性，因此搜索解的效率更高，另外有較好的魯棒性和收斂性等優勢。群智能優化算法存在產生劣質搜索過程的問題，在算法上針對該問題進行優化能有效提升算法性能。

無人機個體任務分配是一個無人機集群行為決策所需面臨的重要問題。相比于單架無人機，多無人機協同任務分配需要建立更加復雜的數學模型，解決隨之帶來的復雜度提升問題非常重要。在軍用場景中往往存在探測雷達和攻擊武器等兩種對我方無人機偵察活動的威脅，該類威脅在大部分研究中往往被設置為靜態威脅，實際上也存在威脅為動態的情況［16］，對于該情況算法應采取不同的處理方式。

目前群智能算法，例如蟻群算法（ACO）、遺傳算法（GA）、粒子群算法（PSO）等，是用于解決無人機任務規劃問題的主流算法，但在算法收斂速度、搜索解的效率、算法運行速度等方面，傳統的群智能算法仍存在改進的空間。Han 等［17］提出了一種避免近親繁殖的機制和一種分層變異規則來解決局部極值問題，還提出了突發威脅對策機制，以提高算法在檢測到突發威脅后快速收斂的能力。Roberge 等［18］提出利用圖像處理單元對遺傳算法加速的方法，結果表明其算法速度相較于在CPU上提升約48倍。

通過對相關文獻的分析，在以下幾個方面還可以再做改進：

（1）在三維空間中對無人機任務進行分配，考慮雷達火力等威脅以及地形約束；

（2）設置動態威脅，在算法上針對隨時間變化的威脅做出優化。

1 問題建模

1.1 問題描述

假設有n個基地，這些基地需要派出無人機執行偵察任務，一共需要偵察m個任務點（Mission Point），空間中存在地形障礙，敵方探測雷達，敵方火力覆蓋區域等威脅。將m個任務點按照整體代價較小的方式分配給n個基地，每個基地的無人機從基地點出發按照該分配方式的順序依次遍歷為其分配的若干任務點。

基地任務點分配結果和順序可通過零一矩陣的方式來進行描述：

AssignResult={Aijk}N×M×M，其中有i∈[0,n)和j,k∈[0,m)。

其中：Aijk= 1 代表第i個基地第j個選擇遍歷的任務點為k；反之如果其等于0，則代表該基地遍歷到第j個點時沒有選擇任務點k。

該矩陣需要滿足以下三個約束：

（3）同一個任務點在同一個基地的多次選擇遍歷時只能被選擇一次，需滿足

第i個任務點分配結果的代價為

該式表示無人機從基地點bi出發依次經過m個任務點pj后返回基地點bi的代價，其中pj為分配矩陣{Aijk}N×M×M中索引為i的基地點選中的為矩陣中值為1 的任務點；Cpq代表點p和點q兩點線路的代價，并且遍歷順序為索引j從小到大的順序。

該分配方式的總代價為

算法優化目標為總代價最小，即：

對以上問題做出如下假設前提：

（1）環境信息已經提前獲得，雷達和火力為動態威脅，其運動規律已知；

（2）任務點位置固定，需完成對所有任務點的遍歷，且同一個任務點只偵察一次；

（3）每個基地派出的無人機速度恒定，完成任務點的遍歷后需返回原基地。

1.2 代價函數模型

任意兩點連線間代價由兩部分構成，靜態代價，如地形和航程所帶來的代價；動態代價，如雷達和火力帶來的代價。由于動態代價存在較強的時序性，因此無法在確定具體的基地任務點分配方式之前計算出該情況下的動態代價。

對于靜態代價，可以采用將任意兩點間代價提前計算出的方式，把計算出的數據做成一張路徑——代價表，之后在需要任意兩點間代價時可以直接查詢該表。靜態代價由路徑長度產生的航程代價（Voyage cost）構成，該代價可由兩點間歐式距離計算得到。

探測雷達覆蓋范圍和火力覆蓋范圍滯留代價采用同一計算方法。假設有M個雷達，設某一個雷達為Raday，該作用范圍為R，此時的威脅代價為Threatxy，已知雷達中心坐標隨時間函數，即可采用空間中兩點間距離公式求出路徑點Rx到雷達中心點RPxy距離為Dxy，有：

該路徑點的總代價Threatx為

該路徑總威脅代價ThreatCost為

設兩點間總代價為TotalCost，探測雷達滯留代價為DetectorCost，攻擊雷達滯留代價為WeaponCost，加以權重則有：

對于一個基地（Base）而言，算法可能為其分配多個任務點（Mission Point），設為該基地分配了K個任務點，基地的無人機依次遍歷這K個任務點再回到基地，一共產生K條路徑。

此時這種分配給該基地這些任務點的方式總代價為這K條路徑代價的總和，對于多個基地則將每個基地所分配任務點的代價累加起來，即可得到總代價。

1.3 任務約束

算法為無人機基地分配任務點時需要考慮無人機的物理特性，因此存在以下約束使算法運行結果符合實際情況：

（1）地形障礙約束。

無人機實飛路線不能穿越地形，即在同樣的橫縱坐標情況下，無人機高度應高于地面，設無人機t時刻坐標為(xU(t),yU(t),zU(t))，地形函數為zT=terrian(x,y)，則應滿足如下約束：

（2）最大航程約束。

為了確保無人機的燃油儲備能夠支持無人機完成所有規劃任務點的偵察任務，各個基地間需要協同規劃，均勻分配任務點，即任意基地i執行偵察任務的飛行總距離LiS和無人機最大航程Lmax間滿足如下約束：

（3）最大轉彎角約束。

由于無人機本體性能限制，無人機實飛過程中完成大轉角動作非常困難，為規劃出實際可行的任務點遍歷方式，空間中兩相鄰航路段間的夾角α和最大轉彎角αmax滿足約束條件：

為將問題轉化為無約束組合優化問題，引入懲戒因子ζ，設Pi為基地i不滿足約束的路徑點個數，基地i的懲戒代價滿足

算法優化目標為

1.4 環境模型

為符合無人機實踐飛行的環境，采取函數擬合山區地形的方式對地形等靜態威脅進行建模，地形建模基于文獻［19］所提出的函數模擬法。

雷達和火力的覆蓋模型如下：

其中：Si表示第i個雷達或火力的覆蓋范圍的點集，為一個球體的范圍；Ri為該雷達的輻射范圍；(xRi,yRi,zRi)為該雷達的中心點坐標。

雷達或火力武器的運動軌跡假設為空間中圓形軌道，方程如下：

其中：TRi為運動軌跡的半徑；(xRi,yRi,zRi)為運動軌跡的中心坐標；t是參數方程的自變量取值，范圍為[ 0,2π ]。

2 改進型遺傳算法

2.1 遺傳算法流程

遺傳算法受自然界生物的進化過程啟發，通過程序模擬生物染色體的交叉變異以及淘汰過程來解決尋優問題，本文采取的染色體編解碼方式同文獻［20］，遺傳算法的整體流程如下：

（1）初始化起始種群染色體；

（2）計算初始種群個體適應度；

（3）選擇當前種群個體進行染色體交叉變異產生子代種群；

（4）計算子代種群個體適應度；

（5）將子代種群作為當前種群，并判斷是否迭代到一定次數或者種群適應度停止變化代數是否達到閾值，如果是，則停止迭代返回結果；否則回到第三步。

2.2 分組并行緩存優化算法

遺傳算法并行性體現于個體適應度計算，并且該部分是遺傳算法較為耗時的部分。采用多線程的方式并發計算種群適應度能夠使算法運行時間大大減少。

定義一個基地的任務點及其遍歷順序為該基地的分組，在計算種群適應度時，先將該種群中所有基地的所有不同分組統計出來，再來利用多線程并發計算每個分組的代價。將并發的方式從并發計算個體適應度變為并發計算分組代價，即可消除在計算當前種群的適應度時的計算冗余。

上述方法不能解決不同代種群分組計算的冗余問題。本文建立了一個分組代價緩存機制，緩存的鍵為基地分組，值為該基地分組的代價。在計算每一代種群的適應度時確定當前基地分組是否命中緩存，未命中則記錄下當前基地分組，在遍歷完所有個體的基地分組后得到仍需要計算的基地分組，之后再并行計算這些基地分組的代價，計算完后將這些基地分組代價寫入分組代價緩存中。計算流程如圖1所示。

圖1 分組代價計算流程

2.3 競爭策略

傳統遺傳算法在算法性能上存在改進空間，可通過改進遺傳算法機制使其尋優能力和收斂速度得到提升。傳統遺傳算法在運行時，當前種群中最優個體的適應度往往隨迭代次數震蕩上升，輸出解適應度隨迭代次數增長也比較緩慢，并且由于多旅行商問題搜索空間非常大，算法收斂也相對困難。

基于此，本文采用了改進的淘汰策略。傳統遺傳算法將子代種群直接作為下一代種群來進行迭代，進行隨機染色體交叉產生子代的適應度不一定比親代更高，原因可能是高適應度親代個體染色體對應某個基地任務點分組的代價較小，而染色體交叉操作破壞了該分組，因此傳統遺傳算法在進行解搜索時會產生劣質搜索過程。本文在產生下一代種群時，將親代種群和子代種群進行混合，將混合后種群按照適應度從高到低排序，再選擇所有適應度排名為前一半的個體，將其作為下一代種群個體。

3 算法仿真

為驗證算法的有效性和可行性，算法運行的平臺為64 位Windows 10，Intel Core i5-9300H CPU（2.40 GHz），16 GB RAM，算法基于C++11編寫，算法編譯器為Visual Studio 2017。場景設置為5 個基地，15 個任務點，空間中存在兩個探測雷達和攻擊雷達以及地形和山峰，四個雷達均沿與水平面平行的圓形軌道運動。具體信息見表1～表3。

表1 雷達和武器信息

表2 代價權重

表3 基地任務點坐標

3.1 改進型遺傳算法結果

最終規劃出的任務分配效果三維圖和俯視圖分別如圖2和圖3所示，其中網格線部分為雷達和武器作用范圍，圓形實線部分為相應雷達武器的運動軌道。

圖2 基地任務點分配結果三維圖

圖3 基地任務點分配結果俯視圖

根據規劃結果可以看出，算法輸出解得到的基地任務點分配方式能夠避免因穿越地形產生繞行代價，并且能夠在一定程度上減少在雷達和火力范圍內的滯留時間。

3.2 算法對比

此部分設置了遺傳算法與模擬退火算法的對比，以及遺傳算法自身在改進前后的對比。模擬退火算法（SAA）沒有種群概念，為保證與遺傳算法對比的公平性，對比實驗中設置400個模擬退火算法并行運行，參數設置見表4～表5。

表4 遺傳算法參數

表5 模擬退火算法參數

由于改進型遺傳算法相較于原遺傳算法有兩點不同，所以本文設置了三組對比實驗，分別為原始遺傳算法（GA）、緩存優化型遺傳算法（Cache Optimized GA）和緩存加機制優化型遺傳算法（Cache And Mechanism Optimized GA），從運行時長、輸出解適應度以及尋優能力三個方面比較這三種算法。在該平臺分別運行三種算法各10次，結果見表6和表7。

表6 算法運行時長

表7 算法輸出解適應度

從表6 實驗數據可以得出，模擬退火算法在運行時間上相較于原始遺傳算法有較小的優勢，但相較于最終緩存加機制優化型遺傳算法還有不小差距。遺傳算法在改進前后，10 次實驗取平均值，緩存優化相較于原始遺傳算法減少了約37%的運行時間，而機制優化則在這個基礎上再減少了約88%的運行時間，算法運行效率上的提升較為明顯。

可以看出模擬退火算法在輸出解適應度方面比遺傳算法差，搜索效率較差。遺傳算法自身改進前后對比方面，機制優化對最終輸出解適應度略有提升，緩存以及機制的優化使遺傳算法搜索解的效率顯著提升。

圖4 分別為最終改進后遺傳算法、原遺傳算法和模擬退火算法輸出解適應度隨種群迭代次數變化的情況，改進后的遺傳算法擁有優異的性能，能夠在較短的迭代次數內收斂到較優解上。

圖4 算法解適應度迭代曲線

4 結語

本文針對場景中存在動態威脅情況下GA 速度過慢、收斂性較差等局限性，提出一種基于緩存命中策略和機制優化型GA，通過實驗對比可以得出以下結論：

（1）基于分組和緩存思想的優化方式能夠有效減少算法運算時間，并且保證算法得到可行解適應度不會下降，為多旅行商問題等NP 難題提供了一種較為有效和通用的優化思路；

（2）淘汰機制優化后的GA 相比之前收斂速度更快，能夠收斂到適應度較好的輸出解；

（3）設計的算法具有較好的性能，能夠有效解決在有動態威脅的復雜場景偵察任務分配問題。

在以下方面還能做出改進：

（1）對未知威脅的應對；

（2）設置不同類型的任務，不同類型任務間存在一定約束，同類型任務點存在一定優先級。