湛 佳，謝文俊，郭 慶，毛 聲

（空軍工程大學裝備管理與無人機工程學院，西安 710051）

0 引言

多無人機協(xié)同偵察將是未來無人機遂行任務(wù)的一種重要樣式，其核心問題是多無人機偵察調(diào)度問題。由于某些待偵察目標出現(xiàn)的時刻具有不確定性和動態(tài)性，導(dǎo)致多無人機偵察調(diào)度問題十分復(fù)雜。最新的研究成果——不確定理論為無人機偵察動態(tài)目標問題研究提供了新的理論工具。該理論是對實際應(yīng)用中的專家信度進行分析的新興理論，對于先驗知識不足、缺乏大量實驗樣本的問題決策具有重要意義。

文獻[1]將任務(wù)分配的代價和收益作為總體目標函數(shù)，并基于投標過程對任務(wù)進行分配。文獻[2]對作戰(zhàn)時間和飛行距離等指標進行加權(quán)，基于攻擊任務(wù)的最大價值構(gòu)建了單目標優(yōu)化問題模型，并采用多子群蟻群算法求解，但忽略了航程的威脅代價。文獻[3]基于二進制粒子群算法完成任務(wù)分配過程。文獻[4]采用整數(shù)域改進粒子群優(yōu)化算法對目標進行分配。人工蜂群（Artificial Bee Colony，ABC）算法其原理是模仿蜂群覓食過程的智能行為，是基于群體的啟發(fā)式優(yōu)化算法[5]。ABC算法與差分進化算法、粒子群優(yōu)化算法和遺傳算法相比較，進化的依據(jù)為適應(yīng)度函數(shù)，具有控制參數(shù)少、操作簡單、魯棒性較強和搜索精度較高等特點，求解質(zhì)量相對較好[6]。但基本ABC算法存在“早熟”的收斂性缺陷，存在開發(fā)能力不足，收斂速度較慢等缺點[7]。文獻[8]對傳統(tǒng)人工蜂群算法進行改進，提高了算法的收斂速度和全局搜索能力。文獻[9]將ABC算法與遺傳算子相結(jié)合，對可行解進行鄰域搜索，算法的搜索能力得到提高。文獻[10]設(shè)計了一種基于粒子群的ABC算法，通過將全局搜索和局部搜索相結(jié)合來尋找最優(yōu)解。文獻[11]針對基本ABC算法容易陷入早熟收斂的缺點，改進了候選食物源的生成方法，增強了ABC算法的全局搜索能力。文獻[12]將多種搜索策略相結(jié)合，不同策略的解通過競爭產(chǎn)生新的解，算法的局部搜索能力得到增強。文獻[13]將ABC算法的全局搜索能力和ACO算法的局部搜索能力相結(jié)合得到一種ACO-ABC混合算法，以尋求最優(yōu)解。文獻[14]設(shè)定最優(yōu)鄰域解僅在多次未更新的情況下才能替換當前解，使有潛力的可行解得以保留。

針對動態(tài)目標出現(xiàn)時刻的不確定性，本文在傳統(tǒng)人工蜂群算法的基礎(chǔ)上，設(shè)計了一種改進的雙重進化人工蜂群算法。該算法以模型的目標函數(shù)作為指引，同時針對適應(yīng)值函數(shù)，在全局搜索中對局部最優(yōu)解進行處理，利用不同局部搜索算子的優(yōu)點，加快了算法搜索速度，豐富了可行解的多樣性。最后通過仿真實驗表明，該算法能在動態(tài)條件下完整偵察到所有目標，取得最大偵察收益，并且其調(diào)用的無人機數(shù)量以及飛行距離最小，使得總飛行代價最小，實驗驗證了該算法能有效解決多無人機偵察調(diào)度問題。

1 多UAV協(xié)同偵察數(shù)學模型

1.1 問題描述

在戰(zhàn)場環(huán)境中，存在n個待偵察目標，用0表示基地，相應(yīng)的數(shù)字表示對應(yīng)的偵察目標，則組成節(jié)點集，用dij表示任意兩節(jié)點（i，j）之間的距離。一個具有同質(zhì)性的無人機偵察分隊K位于基地，每架無人機具有相同的有效偵察載荷量Q。用qi表示每個偵察目標所消耗的偵察載荷量。此外，無人機存在一個續(xù)航時間。對于每個待偵察目標i，都存在一個偵察時間窗。在執(zhí)行任務(wù)的每個時間點t，偵察目標分為以下兩類：

1.2 收益值計算

即動態(tài)目標j在 ∈[t+1，Li]中所有時刻 出現(xiàn)的信度的和值。

1.3 目標函數(shù)

其中，Cp與C0為常數(shù)，xijk為｛0，1｝變量，若第 k 架無人機從節(jié)點i前往節(jié)點j，xijk=1，否則xijk=0，dij為節(jié)點i與j之間的距離；目標函數(shù)第1項為總偵察收益，第2項為無人機總飛行距離，第3項為無人機固有飛行代價。無人機若能偵察到所有目標，則其總偵察收益最大，若完成偵察任務(wù)所調(diào)用的無人機數(shù)量及其飛行距離最少，那么目標函數(shù)的總飛行距離以及固有飛行代價最小，所以優(yōu)化的總目標在于利用最少數(shù)量的無人機和最小化飛行總里程完成偵察任務(wù)。

1.4 約束條件

無人機對單個目標至多完成一次偵察，其約束條件為：

允許無人機在最早可偵察時刻之前到達目標區(qū)域，其約束條件為：

無人機必須在可偵察時間窗結(jié)束之前開始偵察，其約束條件為：

為了保證時間連續(xù)性，其約束條件為：

其中，C為足夠大的常數(shù)，基于第k架無人機到達目標點i的時刻aik，以及該目標點所需偵察時間si，即可計算離開時間；

為了保證無人機從基地出發(fā)到第1個目標點的時間連續(xù)性，其約束條件為：

為了保證無人機返回基地的時間連續(xù)性，其約束條件為：

綜上所述，每個決策階段的偵察調(diào)度模型如下所示：

2 調(diào)度方案求解

2.1 終止條件

一般條件下，若算法完成了設(shè)定的迭代次數(shù)，則可判定終止。除此之外，也可以通過判斷算法在全局搜索過程中產(chǎn)生的解是否迅速收斂作為算法終止的條件。這種方法可以避免以迭代次數(shù)作為終止條件產(chǎn)生的冗余迭代，在動態(tài)場景下具有較好的應(yīng)用效果，缺點是由于迭代次數(shù)不夠，可能導(dǎo)致算法在全局搜索過程中未能發(fā)揮最佳效能。

2.2 解的編碼方式

用數(shù)字表示相應(yīng)的目標，其中0表示基地。序列首尾數(shù)字均為0，表示無人機從基地出發(fā)，再返回基地；數(shù)字排列的順序代表的是無人機執(zhí)行任務(wù)中偵察目標的順序。將各子序列首尾相接，構(gòu)成一個完整序列，用此方式來表示一個可行解。各無人機型號不同時，序列中第i個子序列代表第i架無人機的偵察子方案；否則取消這一對應(yīng)關(guān)系，全序列僅表示存在這樣的一個偵察方案，以避免冗余。

以15個目標，3架無人機為例，一種可能的調(diào)度方案的表示如圖1所示。

圖1 調(diào)度方案示例

為方便文中敘述，用 vk（i）表示第 k架無人機到達的第i個節(jié)點，rk表示其對應(yīng)子序列的節(jié)點總數(shù)，則該UAV的偵察方案也可用節(jié)點集表示，其中初始節(jié)點和終止

節(jié)點均為基地。

2.3 初始化

1）基地設(shè)為v1（1），最低代價設(shè)LC為無窮，設(shè)置無人機數(shù)量上限為#veh，初始化最佳方案序列X=｛v1（1）｝。

4）輸出參數(shù)集及其對應(yīng)的最佳方案集。

2.4 適應(yīng)值

適應(yīng)值函數(shù)fitD按式（10）計算：

其中，γ為自適應(yīng)約束系數(shù)，在一次局部搜索過程中，γ的值隨搜索過程動態(tài)變化，若在較優(yōu)解中，違反載荷量約束解的數(shù)目超過總數(shù)的一半，則；否則，其中φ為常數(shù)。γ越小，對可行解的限制越小，搜索范圍就越大；γ越大，對可行解的限制越大，搜索范圍就越小。

2.5 選擇和跟隨

在雇傭蜂階段進行之后，跟隨蜂通過概率pi對雇傭蜂找到的蜜源進行選擇，pi根據(jù)輪盤賭方法計算，如式（11）所示：

其中，N為解的數(shù)量。

2.6 雙重進化過程

在跟隨蜂和雇傭蜂階段，該算法均進行了局部搜索，搜索過程中均采用雙重進化方法[16]。其具體操作過程如下：

1）半隨機式最優(yōu)插入點算子，如圖2所示。

①隨機選取插入點r1，插入位置記為r2；

②r2遍歷所有可行的插入位置，生成新的可行方案，并計算各可行方案的適應(yīng)值；

③找到使適應(yīng)值最小的可行方案，并將r1處的目標插入到該位置。

圖2 半隨機最優(yōu)式插入點算子

2）半隨機式最優(yōu)逆轉(zhuǎn)序列算子，如圖3所示。

①隨機選取子序列的一端記為r1，子序列的另一端記為r2；

②r2遍歷可行子序列的另一端，將r1、r2確定的子序列逆轉(zhuǎn)，生成新的可行方案，并計算各可行方案的適應(yīng)值；

③找到使適應(yīng)值最小的可行方案，并將子序列逆轉(zhuǎn)。

圖3 半隨機最優(yōu)逆轉(zhuǎn)序列算子

這一搜索過程較為快速和高效，計算量較小，在文中將其命名為基于重新構(gòu)建方案的局部搜索方法。

偵察動態(tài)不確定目標的多無人機偵察調(diào)度方案求解流程如下頁圖4所示。在目標數(shù)據(jù)更新之后，優(yōu)先采用快速局部搜索方法；如果這一方法達到收斂（最優(yōu)解經(jīng)過βLimit次迭代未更新），而動態(tài)目標仍未出現(xiàn)，則一直采用基于重新構(gòu)建方案的局部搜索方法，基于待偵察目標集制定當前偵察方案。

3 實驗結(jié)果及分析

3.1 應(yīng)用場景想定

本文將UAV對某海域島礁的偵察監(jiān)視設(shè)定為任務(wù)背景，假設(shè)基地位于島礁集群的中點（經(jīng)度114.60°，緯度9.47°）。各個目標以及目標與基地兩兩之間的距離通過歐式空間距離確定；具體結(jié)果利用高斯坐標轉(zhuǎn)換進行計算，采用是西安1980參考橢球和三度帶投影。本文假定，原50個島礁中，有5個島礁附近會有非法船只出現(xiàn)，作為動態(tài)不確定目標，其基本設(shè)置如下頁表1所示。

表1中出現(xiàn)時刻所服從的不確定分布是依據(jù)已知信息和戰(zhàn)場經(jīng)驗估計而來，具體內(nèi)容為其出現(xiàn)時刻服從的不確定分布；持續(xù)時間為對方艦船在爭議海域停留的時間。設(shè)定飛行速度為144 km/h，飛行單位距離所耗時間為確定值，要求對多無人機進行動態(tài)調(diào)度，使得無人機使用數(shù)量最少，總飛行代價最低，同時盡可能完成所有目標的偵察。

3.2 仿真試驗

圖4 算法流程圖

表1 動態(tài)不確定目標信息

在UAV執(zhí)行任務(wù)過程中，針對本文設(shè)計任務(wù)的計算量和搜索深度，在不同的時間緊迫度情況下，結(jié)合HB-ABC與RC-ABC的局部搜索策略進行動態(tài)多UAV目標的偵察調(diào)度求解。實驗中，最大循環(huán)次數(shù)設(shè)置為1 000，β的值設(shè)定為3，Limit的值設(shè)定為20。由于實驗中動態(tài)目標出現(xiàn)的具體時刻不同，會影響偵察調(diào)度方案的指定。故選擇其中一種執(zhí)行的情況，利用STK軟件展示如圖5所示。從圖中可以看出，無人機對所有目標均進行了偵察，其總偵察收益達到最大。

圖5 偵察調(diào)度方案

為測試將RC-ABC算法和HB-ABC算法局部搜索策略相結(jié)合的有效性，分別單獨用這兩種ABC算法進行跟蹤，并與RC-HB-ABC算法比較最終跟蹤結(jié)果，其中RC-HB-ABC算法中與終止條件相關(guān)的參數(shù)β取3，且動態(tài)目標的權(quán)重遠大于已知目標。

實驗設(shè)計兩種不同的動態(tài)度進行測試，分別為10%，30%；即分別有總數(shù)量中10%，30%的目標是決策者在無人機開始偵察時僅擁有專家的不確定知識，而它們并未出現(xiàn)。隨機選取C101、C106、R101、R106、RC101、RC106 進行改動和實驗，實驗中，隨機選取原測試數(shù)據(jù)集中的點作為動態(tài)目標點，出現(xiàn)時刻在[0，Li]中生成。對每組動態(tài)測試數(shù)據(jù)，通過30次的運行選取最佳結(jié)果，結(jié)果如表2與表3所示。

表2 10%動態(tài)度下不同ABC算法結(jié)果比較

表3 30%動態(tài)度下不同ABC算法結(jié)果比較

由表2與表3可知，從優(yōu)化距離的角度來看，將兩種策略相結(jié)合取得的效果最佳。RC-ABC算法與HB-ABC算法依據(jù)測試集動態(tài)度的不同，優(yōu)化結(jié)果有差異；但整體上來看RC-HB-ABC算法在動態(tài)度測試問題中優(yōu)化結(jié)果相對較好。

為對結(jié)果進行具體評估，在10%動態(tài)度下，將3種跟蹤策略解決R103測試集的收斂曲線展示如圖6所示。由圖6可知，HB-ABC算法跟蹤策略收斂速度較快，但由于搜索深度不夠，解的質(zhì)量相對不是很理想，但在動態(tài)目標出現(xiàn)的緊迫度較高時能得到最好質(zhì)量的解；RC-ABC算法的局部搜索策略能夠進行較為深度的搜索，但搜索時間較長，在緊迫度較低的情況下能夠得到最好質(zhì)量的解；RC-HB-ABC算法的搜索策略結(jié)合了兩種搜索策略的優(yōu)點，一方面判斷使用哪一種具體策略的過程中計算量較小，因此，在時間緊迫度高的情況下收斂速度與HB-ABC的局部搜索策略幾乎相同；另一方面在搜索時間較長的情況下，由于是順次進行兩種搜索策略，在某些情況下還能求得比RC-ABC質(zhì)量更好的解。實驗結(jié)果驗證了所提出算法的有效性以及解決多無人機調(diào)度問題的可行性。

圖6 收斂曲線圖

4 結(jié)論

本文在構(gòu)建動態(tài)環(huán)境下多無人機調(diào)度問題模型的基礎(chǔ)上，設(shè)計了一種改進的雙重進化人工蜂群算法求解該模型。通過仿真實驗，證明該算法能在動態(tài)條件下完全偵察到所有目標，取得最大偵察收益，并且完成偵察任務(wù)所調(diào)用的無人機數(shù)量以及飛行距離最短，使飛行代價最小。最后將該算法與RC-ABC以及HB-ABC算法進行比較，實驗結(jié)果表明該算法能顯著提高收斂速度和全局尋優(yōu)能力。