徐賓王，寧 芊

（四川大學(xué)電子信息學(xué)院，成都 610000）

0 引言

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

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

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

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

通過對相關(guān)文獻(xiàn)的分析，在以下幾個(gè)方面還可以再做改進(jìn)：

（1）在三維空間中對無人機(jī)任務(wù)進(jìn)行分配，考慮雷達(dá)火力等威脅以及地形約束；

（2）設(shè)置動(dòng)態(tài)威脅，在算法上針對隨時(shí)間變化的威脅做出優(yōu)化。

1 問題建模

1.1 問題描述

假設(shè)有n個(gè)基地，這些基地需要派出無人機(jī)執(zhí)行偵察任務(wù)，一共需要偵察m個(gè)任務(wù)點(diǎn)（Mission Point），空間中存在地形障礙，敵方探測雷達(dá)，敵方火力覆蓋區(qū)域等威脅。將m個(gè)任務(wù)點(diǎn)按照整體代價(jià)較小的方式分配給n個(gè)基地，每個(gè)基地的無人機(jī)從基地點(diǎn)出發(fā)按照該分配方式的順序依次遍歷為其分配的若干任務(wù)點(diǎn)。

基地任務(wù)點(diǎn)分配結(jié)果和順序可通過零一矩陣的方式來進(jìn)行描述：

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

其中：Aijk= 1 代表第i個(gè)基地第j個(gè)選擇遍歷的任務(wù)點(diǎn)為k；反之如果其等于0，則代表該基地遍歷到第j個(gè)點(diǎn)時(shí)沒有選擇任務(wù)點(diǎn)k。

該矩陣需要滿足以下三個(gè)約束：

（3）同一個(gè)任務(wù)點(diǎn)在同一個(gè)基地的多次選擇遍歷時(shí)只能被選擇一次，需滿足

第i個(gè)任務(wù)點(diǎn)分配結(jié)果的代價(jià)為

該式表示無人機(jī)從基地點(diǎn)bi出發(fā)依次經(jīng)過m個(gè)任務(wù)點(diǎn)pj后返回基地點(diǎn)bi的代價(jià)，其中pj為分配矩陣{Aijk}N×M×M中索引為i的基地點(diǎn)選中的為矩陣中值為1 的任務(wù)點(diǎn)；Cpq代表點(diǎn)p和點(diǎn)q兩點(diǎn)線路的代價(jià)，并且遍歷順序?yàn)樗饕齤從小到大的順序。

該分配方式的總代價(jià)為

算法優(yōu)化目標(biāo)為總代價(jià)最小，即：

對以上問題做出如下假設(shè)前提：

（1）環(huán)境信息已經(jīng)提前獲得，雷達(dá)和火力為動(dòng)態(tài)威脅，其運(yùn)動(dòng)規(guī)律已知；

（2）任務(wù)點(diǎn)位置固定，需完成對所有任務(wù)點(diǎn)的遍歷，且同一個(gè)任務(wù)點(diǎn)只偵察一次；

（3）每個(gè)基地派出的無人機(jī)速度恒定，完成任務(wù)點(diǎn)的遍歷后需返回原基地。

1.2 代價(jià)函數(shù)模型

任意兩點(diǎn)連線間代價(jià)由兩部分構(gòu)成，靜態(tài)代價(jià)，如地形和航程所帶來的代價(jià)；動(dòng)態(tài)代價(jià)，如雷達(dá)和火力帶來的代價(jià)。由于動(dòng)態(tài)代價(jià)存在較強(qiáng)的時(shí)序性，因此無法在確定具體的基地任務(wù)點(diǎn)分配方式之前計(jì)算出該情況下的動(dòng)態(tài)代價(jià)。

對于靜態(tài)代價(jià)，可以采用將任意兩點(diǎn)間代價(jià)提前計(jì)算出的方式，把計(jì)算出的數(shù)據(jù)做成一張路徑——代價(jià)表，之后在需要任意兩點(diǎn)間代價(jià)時(shí)可以直接查詢該表。靜態(tài)代價(jià)由路徑長度產(chǎn)生的航程代價(jià)（Voyage cost）構(gòu)成，該代價(jià)可由兩點(diǎn)間歐式距離計(jì)算得到。

探測雷達(dá)覆蓋范圍和火力覆蓋范圍滯留代價(jià)采用同一計(jì)算方法。假設(shè)有M個(gè)雷達(dá)，設(shè)某一個(gè)雷達(dá)為Raday，該作用范圍為R，此時(shí)的威脅代價(jià)為Threatxy，已知雷達(dá)中心坐標(biāo)隨時(shí)間函數(shù)，即可采用空間中兩點(diǎn)間距離公式求出路徑點(diǎn)Rx到雷達(dá)中心點(diǎn)RPxy距離為Dxy，有：

該路徑點(diǎn)的總代價(jià)Threatx為

該路徑總威脅代價(jià)ThreatCost為

設(shè)兩點(diǎn)間總代價(jià)為TotalCost，探測雷達(dá)滯留代價(jià)為DetectorCost，攻擊雷達(dá)滯留代價(jià)為WeaponCost，加以權(quán)重則有：

對于一個(gè)基地（Base）而言，算法可能為其分配多個(gè)任務(wù)點(diǎn)（Mission Point），設(shè)為該基地分配了K個(gè)任務(wù)點(diǎn)，基地的無人機(jī)依次遍歷這K個(gè)任務(wù)點(diǎn)再回到基地，一共產(chǎn)生K條路徑。

此時(shí)這種分配給該基地這些任務(wù)點(diǎn)的方式總代價(jià)為這K條路徑代價(jià)的總和，對于多個(gè)基地則將每個(gè)基地所分配任務(wù)點(diǎn)的代價(jià)累加起來，即可得到總代價(jià)。

1.3 任務(wù)約束

算法為無人機(jī)基地分配任務(wù)點(diǎn)時(shí)需要考慮無人機(jī)的物理特性，因此存在以下約束使算法運(yùn)行結(jié)果符合實(shí)際情況：

（1）地形障礙約束。

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

（2）最大航程約束。

為了確保無人機(jī)的燃油儲(chǔ)備能夠支持無人機(jī)完成所有規(guī)劃任務(wù)點(diǎn)的偵察任務(wù)，各個(gè)基地間需要協(xié)同規(guī)劃，均勻分配任務(wù)點(diǎn)，即任意基地i執(zhí)行偵察任務(wù)的飛行總距離LiS和無人機(jī)最大航程Lmax間滿足如下約束：

（3）最大轉(zhuǎn)彎角約束。

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

為將問題轉(zhuǎn)化為無約束組合優(yōu)化問題，引入懲戒因子ζ，設(shè)Pi為基地i不滿足約束的路徑點(diǎn)個(gè)數(shù)，基地i的懲戒代價(jià)滿足

算法優(yōu)化目標(biāo)為

1.4 環(huán)境模型

為符合無人機(jī)實(shí)踐飛行的環(huán)境，采取函數(shù)擬合山區(qū)地形的方式對地形等靜態(tài)威脅進(jìn)行建模，地形建模基于文獻(xiàn)［19］所提出的函數(shù)模擬法。

雷達(dá)和火力的覆蓋模型如下：

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

雷達(dá)或火力武器的運(yùn)動(dòng)軌跡假設(shè)為空間中圓形軌道，方程如下：

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

2 改進(jìn)型遺傳算法

2.1 遺傳算法流程

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

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

（2）計(jì)算初始種群個(gè)體適應(yīng)度；

（3）選擇當(dāng)前種群個(gè)體進(jìn)行染色體交叉變異產(chǎn)生子代種群；

（4）計(jì)算子代種群個(gè)體適應(yīng)度；

（5）將子代種群作為當(dāng)前種群，并判斷是否迭代到一定次數(shù)或者種群適應(yīng)度停止變化代數(shù)是否達(dá)到閾值，如果是，則停止迭代返回結(jié)果；否則回到第三步。

2.2 分組并行緩存優(yōu)化算法

遺傳算法并行性體現(xiàn)于個(gè)體適應(yīng)度計(jì)算，并且該部分是遺傳算法較為耗時(shí)的部分。采用多線程的方式并發(fā)計(jì)算種群適應(yīng)度能夠使算法運(yùn)行時(shí)間大大減少。

定義一個(gè)基地的任務(wù)點(diǎn)及其遍歷順序?yàn)樵摶氐姆纸M，在計(jì)算種群適應(yīng)度時(shí)，先將該種群中所有基地的所有不同分組統(tǒng)計(jì)出來，再來利用多線程并發(fā)計(jì)算每個(gè)分組的代價(jià)。將并發(fā)的方式從并發(fā)計(jì)算個(gè)體適應(yīng)度變?yōu)椴l(fā)計(jì)算分組代價(jià)，即可消除在計(jì)算當(dāng)前種群的適應(yīng)度時(shí)的計(jì)算冗余。

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

圖1 分組代價(jià)計(jì)算流程

2.3 競爭策略

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

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

3 算法仿真

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

表1 雷達(dá)和武器信息

表2 代價(jià)權(quán)重

表3 基地任務(wù)點(diǎn)坐標(biāo)

3.1 改進(jìn)型遺傳算法結(jié)果

最終規(guī)劃出的任務(wù)分配效果三維圖和俯視圖分別如圖2和圖3所示，其中網(wǎng)格線部分為雷達(dá)和武器作用范圍，圓形實(shí)線部分為相應(yīng)雷達(dá)武器的運(yùn)動(dòng)軌道。

圖2 基地任務(wù)點(diǎn)分配結(jié)果三維圖

圖3 基地任務(wù)點(diǎn)分配結(jié)果俯視圖

根據(jù)規(guī)劃結(jié)果可以看出，算法輸出解得到的基地任務(wù)點(diǎn)分配方式能夠避免因穿越地形產(chǎn)生繞行代價(jià)，并且能夠在一定程度上減少在雷達(dá)和火力范圍內(nèi)的滯留時(shí)間。

3.2 算法對比

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

表4 遺傳算法參數(shù)

表5 模擬退火算法參數(shù)

由于改進(jìn)型遺傳算法相較于原遺傳算法有兩點(diǎn)不同，所以本文設(shè)置了三組對比實(shí)驗(yàn)，分別為原始遺傳算法（GA）、緩存優(yōu)化型遺傳算法（Cache Optimized GA）和緩存加機(jī)制優(yōu)化型遺傳算法（Cache And Mechanism Optimized GA），從運(yùn)行時(shí)長、輸出解適應(yīng)度以及尋優(yōu)能力三個(gè)方面比較這三種算法。在該平臺(tái)分別運(yùn)行三種算法各10次，結(jié)果見表6和表7。

表6 算法運(yùn)行時(shí)長

表7 算法輸出解適應(yīng)度

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

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

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

圖4 算法解適應(yīng)度迭代曲線

4 結(jié)語

本文針對場景中存在動(dòng)態(tài)威脅情況下GA 速度過慢、收斂性較差等局限性，提出一種基于緩存命中策略和機(jī)制優(yōu)化型GA，通過實(shí)驗(yàn)對比可以得出以下結(jié)論：

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

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

（3）設(shè)計(jì)的算法具有較好的性能，能夠有效解決在有動(dòng)態(tài)威脅的復(fù)雜場景偵察任務(wù)分配問題。

在以下方面還能做出改進(jìn)：

（1）對未知威脅的應(yīng)對；

（2）設(shè)置不同類型的任務(wù)，不同類型任務(wù)間存在一定約束，同類型任務(wù)點(diǎn)存在一定優(yōu)先級。