多無人艇協同目標分配算法研究

曹 璐

（中國船舶重工集團有限公司第七一〇研究所，湖北 宜昌 443003）

0 引言

在未來戰爭中，面對動態復雜的環境、不可預知的潛在危險和多樣化的任務使命，單一無人艇受限于自身搭載的有限的載荷與系統，顯得勢單力薄。與此同時，由多艘無人艇聯合起來構成的協同系統，具有更強的魯棒性、通信能力、機動性、靈活性、更高的作業效率和更廣的作業范圍。考慮到現代戰爭對于多兵種、多武器、多方位的綜合協同作戰需要，多無人艇協同系統可完善無人作戰系統的發展使用[1]。協同目標分配是多無人艇協同系統中的關鍵技術，其目的是充分發揮各無人艇的優勢，實現資源的優化配置，提高無人艇的戰場動態適應能力以及整體作戰效能。

雖然國內外學者運用不同方法對協同目標分配進行了研究，但還是存在一些不足，如基于整數規劃模型的算法在求解大規模組合優化問題時存在時間、空間復雜性等不足[2]；遺傳算法由于其本質上的隨機性導致其在大規模組合優化問題的求解中效率和精度不高[3]；基于合同網方法的優化能力建立在協商和競爭的基礎上，當問題規模較大時會導致協商通信量大大增加[4]。貝葉斯優化算法通過構造和學習貝葉斯網絡來替代傳統遺傳算法的交叉重組和變異等操作，實現對解空間的指導性搜索和連鎖學習，已經在多目標分配上得到應用[5-6]。但隨著問題規模的增加，貝葉斯優化算法計算量和空間占用量會急劇增加。DBOA采用決策圖增強對貝葉斯網絡結構的表達和學習，減小計算量和空間占用量，具有更強的局部搜索能力。因此，本文根據多無人艇協同目標分配問題的特點，在分析多約束多目標優化問題的基礎上，提出了一種基于DBOA的多無人艇協同目標分配方法。

1 決策圖貝葉斯優化算法

貝葉斯優化算法（Bayesian Optimization Algorithm，BOA）是一種分布估計算法，是在遺傳算法（Genetic Algorithm，GA）的基礎上發展起來的一種優化算法[7]。其主要思想是把自然進化算法和構造性數學分析方法相結合，以指導對問題空間的有效搜索。與遺傳算法不同的是，該算法不是采用交叉和變異的方法來產生新的個體，而是采用貝葉斯網絡對上一代群體中的優秀個體集合進行描述，估計變量之間的概率分布關系，然后根據此概率分布產生新的子集，用新的子集替換上一代群體中的部分個體形成新一代群體，如此反復，直到滿足算法的終止條件。具體過程如圖1所示。

傳統進化算法通過基因的微觀操作實現群體的進化，BOA通過建立優選解的概率模型來描述隨機變量之間的概率依賴關系，從宏觀上指導種群的進化，因此可以捕獲變量關系結構、確認并操作關鍵構造塊，避免了微觀操作對構造塊的破壞，具有較強的求解高階構造塊問題的能力[8]。但隨著問題規模的增加，計算量和空間占用量會急劇增加，導致BOA無法求解，而基于決策圖的貝葉斯優化算法有著更強的局部搜索能力，能夠減小計算量和空間占用量[9]。

圖1 貝葉斯優化算法示意圖Fig.1 Schematic diagram of Bayesian optimization algorithm

DBOA采用決策圖增強對貝葉斯網絡結構的表達和學習，由此可以減少大量參數的存儲。決策圖是一有向無環圖，用來代表變量的條件概率分布，每一個變量Xi對應一個決策圖Gi，Gi中非葉節點為Xi的父節點，葉節點保存Xi的條件概率。決策圖貝葉斯網絡的建立僅通過修改所有變量的決策圖來實現，不但簡化了過程，而且還避免了對貝葉斯網絡的直接操作而影響網絡的質量。

2 協同目標分配數學模型

多無人艇協同目標分配是以整個無人艇編隊的整體作戰效能最優為目標的，而無人艇的消耗（USV Attrition）、目標價值的毀傷（Target Value Damage，TVD）和執行任務預計耗費時間（Task Expending Time，TET）是評價作戰效能的主要指標。本文首先分析了影響這3項指標的關鍵因素，分別建立了無人艇消耗模型、目標價值毀傷模型和任務耗費時間模型。然后通過量綱轉換和加權求和，將多目標優化問題轉換為單一目標函數，得出了無人艇優勢函數。由于作戰過程中無人艇內部存在著協作關系，因此建立了無人艇整體優勢函數，進而得到了多無人艇協同目標分配數學模型。

1）USV消耗模型。

在USV對目標進行打擊的同時，目標也對其進行反擊，造成了USV的消耗。設第u艘USV打擊目標t的生存概率為PSut，則USV的消耗模型為

2）目標價值毀傷模型。

綜合考慮目標的價值、確認概率、殺傷概率、USV相對于目標的生存概率，則使用第u艘USV攻擊目標t時，目標價值毀傷模型為

式中：Pc表示USV準確到達任務區域、發現目標以及正確識別出目標的概率；PK表示 USV對目標的殺傷概率；Vt表示摧毀目標t獲得的收益。

3）耗費時間模型。

通常USV到達目標區域越早，發現和打擊目標就越早，所以用到達時間來近似估計USV執行任務耗費的時間，USV到達目標的時間與其和目標間的距離成正比。設第u艘USV與目標t間的距離為Dut，則耗費時間模型為

式中，Dmax為USV與目標間最遠（最長到達時間）距離。

選取淀粉顆粒濃度分別為10%（m/V），OSA淀粉顆粒取代度為 1.43%，添加一定量的緩沖液配制淀粉顆粒分散液，油相比例分別為0.1、0.2、0.3、0.4、0.5，制備乳液，乳化方法同1.3.4。

4）USV整體優勢函數。

將多目標決策問題轉換為單目標優化問題的常用方法是加權求和，即為各子目標函數賦予相應的權值，權值的大小體現了各子目標函數的重要程度，因此，本文采用這一方法將多目標優化問題轉換為單目標最優化問題。將各量綱轉化為[0,1]集合內的數值，令目標的價值V取0～1之間的數值。因此，USV優勢函數為

式中，ω1、ω2、ω3為權系數，反映了每個子目標的重要程度。

在作戰過程中，不僅敵我雙方存在著沖突，而且己方內部也存在著沖突。在合作的同時，各無人艇都會盡量取得對敵目標較大的優勢，但在實際應用中，有時候一部分無人艇的優勢獲得是以另一部分無人艇的態勢損失為代價的。因此，不僅要確定敵我雙方的權重，而且還需要確定己方內部各無人艇的權重分配。對于己方內部的權重分配采用多人層次分析法獲取，因此可以得到USV的整體優勢函數為

式中，ωm是己方內部各無人艇的權重。

5）協同目標分配數學模型。

目標分配的目的是使USV編隊的總體優勢達到最大，從而形成合理的作戰方案。目標分配不但要有衡量分配方案優劣的標準，而且還需要滿足一定的限制條件，由此可得多無人艇協同目標分配模型為

3 基于DBOA的協同目標分配

通過建立協同目標分配的數學模型，并采用二進制編碼方案，以整體優勢函數作為適應度函數，即將USV消耗最小、價值毀傷最大以及任務耗費時間最短作為待優化的性能指標，得到了基于DBOA的多無人艇協同目標分配的基本步驟：

1）根據多無人艇協同目標分配的數學模型確立相關參數；

2）生成各艘無人艇對相應目標的優勢函數值，從而得到無人艇優勢矩陣；

3）計算無人艇編隊內部的權重，在優勢矩陣的基礎上生成多無人艇整體優勢函數；

4）進行DBOA參數設置，運用DBOA進行多無人艇協同目標分配。

因此，多無人艇協同目標分配 DBOA流程圖如圖2所示。

圖2 多無人艇協同目標分配DBOA流程Fig.2 DBOA flow of multi-USV cooperative target assignment

4 仿真及結果分析

4.1 仿真初始條件設定

仿真中設定無人艇數量為4，目標數量為4，為了計算的簡便，做出如下假設：1）無人艇的生存概率已知；2）無人艇能準確到達任務區域、發現并正確識別出目標，則Pc= 1；3）無人艇攜帶的武器對目標的殺傷概率為已知數；4）目標的價值已確定；5）通過USV自身的生存、對目標的殺傷、以及完成任務耗費時間三者的重要程度可以確定權值ω1、ω2、ω3。

4.2 仿真計算與分析

根據USV消耗模型、目標價值毀傷模型以及耗費時間模型可以計算出無人艇優勢函數值，從而得到無人艇相對目標的優勢矩陣，如表1所示。

表1 無人艇優勢矩陣Table1 USV superiority matrix

根據多人層次分析法可以確定4艘無人艇的權重分別為ωu1=0.157 9、ωu2=0.3158、ωu3=0.105 2、ωu4=0.421 1。在確定無人艇優勢矩陣以及內部權重的基礎上，經過 21步運行后尋找到最優分配結果，得到的最優分配結果編碼為0011010000100001。化成矩陣形式即目標3分配給USV1，目標4分配給USV2，目標2分配給USV3，目標1分配給USV4，最終的適應度值為0.273 46。圖3給出了各代群體中個體適應度的最大值、最小值與平均值，從圖中可以看出DBOA能夠快速找到個體適應度的最大值，個體適應度的平均值也呈現出快速上升的趨勢，具有良好的收斂性且速度快。

圖3 適應度變化曲線圖Fig.3 Fitness curve

為了說明DBOA的優越性，本文分別采用GA和 BOA對多艘無人艇協同目標分配問題進行求解。圖4給出了50代內3種算法在上述條件下對目標進行分配的最優解曲線，從圖中可以看出GA的運行速度最慢，而DBOA和BOA在運行速度上具有相當大的優勢，并且DBOA的進化代數更少，收斂速度最快。

圖4 DBOA和BOA、GA的最優值比較Fig.4 Comparison of optimal values among DBOA and BOA，GA

5 結束語

本文對多艘無人艇協同作戰過程中的協同目標分配問題進行了仿真研究。針對協同目標分配過程中的多參數、多約束條件，提出了基于 DBOA的協同目標分配方法。DBOA是一種處理多目標優化問題的有效方法，作為BOA的改進，不僅具有BOA較強的優化能力，避免逼近局部最優或早熟，而且通過決策圖增強了對貝葉斯網絡結構的表達，減少了存儲。因此，將 DBOA應用于多艘無人艇協同目標分配中，能快速對多約束條件下的多目標優化問題進行求解，并能反映多艘無人艇作戰的協同性與對抗性。