多無人艇協(xié)同目標(biāo)分配算法研究

曹 璐

（中國(guó)船舶重工集團(tuán)有限公司第七一〇研究所，湖北 宜昌 443003）

0 引言

在未來戰(zhàn)爭(zhēng)中，面對(duì)動(dòng)態(tài)復(fù)雜的環(huán)境、不可預(yù)知的潛在危險(xiǎn)和多樣化的任務(wù)使命，單一無人艇受限于自身搭載的有限的載荷與系統(tǒng)，顯得勢(shì)單力薄。與此同時(shí)，由多艘無人艇聯(lián)合起來構(gòu)成的協(xié)同系統(tǒng)，具有更強(qiáng)的魯棒性、通信能力、機(jī)動(dòng)性、靈活性、更高的作業(yè)效率和更廣的作業(yè)范圍?？紤]到現(xiàn)代戰(zhàn)爭(zhēng)對(duì)于多兵種、多武器、多方位的綜合協(xié)同作戰(zhàn)需要，多無人艇協(xié)同系統(tǒng)可完善無人作戰(zhàn)系統(tǒng)的發(fā)展使用[1]。協(xié)同目標(biāo)分配是多無人艇協(xié)同系統(tǒng)中的關(guān)鍵技術(shù)，其目的是充分發(fā)揮各無人艇的優(yōu)勢(shì)，實(shí)現(xiàn)資源的優(yōu)化配置，提高無人艇的戰(zhàn)場(chǎng)動(dòng)態(tài)適應(yīng)能力以及整體作戰(zhàn)效能。

雖然國(guó)內(nèi)外學(xué)者運(yùn)用不同方法對(duì)協(xié)同目標(biāo)分配進(jìn)行了研究，但還是存在一些不足，如基于整數(shù)規(guī)劃模型的算法在求解大規(guī)模組合優(yōu)化問題時(shí)存在時(shí)間、空間復(fù)雜性等不足[2]；遺傳算法由于其本質(zhì)上的隨機(jī)性導(dǎo)致其在大規(guī)模組合優(yōu)化問題的求解中效率和精度不高[3]；基于合同網(wǎng)方法的優(yōu)化能力建立在協(xié)商和競(jìng)爭(zhēng)的基礎(chǔ)上，當(dāng)問題規(guī)模較大時(shí)會(huì)導(dǎo)致協(xié)商通信量大大增加[4]。貝葉斯優(yōu)化算法通過構(gòu)造和學(xué)習(xí)貝葉斯網(wǎng)絡(luò)來替代傳統(tǒng)遺傳算法的交叉重組和變異等操作，實(shí)現(xiàn)對(duì)解空間的指導(dǎo)性搜索和連鎖學(xué)習(xí)，已經(jīng)在多目標(biāo)分配上得到應(yīng)用[5-6]。但隨著問題規(guī)模的增加，貝葉斯優(yōu)化算法計(jì)算量和空間占用量會(huì)急劇增加。DBOA采用決策圖增強(qiáng)對(duì)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的表達(dá)和學(xué)習(xí)，減小計(jì)算量和空間占用量，具有更強(qiáng)的局部搜索能力。因此，本文根據(jù)多無人艇協(xié)同目標(biāo)分配問題的特點(diǎn)，在分析多約束多目標(biāo)優(yōu)化問題的基礎(chǔ)上，提出了一種基于DBOA的多無人艇協(xié)同目標(biāo)分配方法。

1 決策圖貝葉斯優(yōu)化算法

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

傳統(tǒng)進(jìn)化算法通過基因的微觀操作實(shí)現(xiàn)群體的進(jìn)化，BOA通過建立優(yōu)選解的概率模型來描述隨機(jī)變量之間的概率依賴關(guān)系，從宏觀上指導(dǎo)種群的進(jìn)化，因此可以捕獲變量關(guān)系結(jié)構(gòu)、確認(rèn)并操作關(guān)鍵構(gòu)造塊，避免了微觀操作對(duì)構(gòu)造塊的破壞，具有較強(qiáng)的求解高階構(gòu)造塊問題的能力[8]。但隨著問題規(guī)模的增加，計(jì)算量和空間占用量會(huì)急劇增加，導(dǎo)致BOA無法求解，而基于決策圖的貝葉斯優(yōu)化算法有著更強(qiáng)的局部搜索能力，能夠減小計(jì)算量和空間占用量[9]。

圖1 貝葉斯優(yōu)化算法示意圖Fig.1 Schematic diagram of Bayesian optimization algorithm

DBOA采用決策圖增強(qiáng)對(duì)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的表達(dá)和學(xué)習(xí)，由此可以減少大量參數(shù)的存儲(chǔ)。決策圖是一有向無環(huán)圖，用來代表變量的條件概率分布，每一個(gè)變量Xi對(duì)應(yīng)一個(gè)決策圖Gi，Gi中非葉節(jié)點(diǎn)為Xi的父節(jié)點(diǎn)，葉節(jié)點(diǎn)保存Xi的條件概率。決策圖貝葉斯網(wǎng)絡(luò)的建立僅通過修改所有變量的決策圖來實(shí)現(xiàn)，不但簡(jiǎn)化了過程，而且還避免了對(duì)貝葉斯網(wǎng)絡(luò)的直接操作而影響網(wǎng)絡(luò)的質(zhì)量。

2 協(xié)同目標(biāo)分配數(shù)學(xué)模型

多無人艇協(xié)同目標(biāo)分配是以整個(gè)無人艇編隊(duì)的整體作戰(zhàn)效能最優(yōu)為目標(biāo)的，而無人艇的消耗（USV Attrition）、目標(biāo)價(jià)值的毀傷（Target Value Damage，TVD）和執(zhí)行任務(wù)預(yù)計(jì)耗費(fèi)時(shí)間（Task Expending Time，TET）是評(píng)價(jià)作戰(zhàn)效能的主要指標(biāo)。本文首先分析了影響這3項(xiàng)指標(biāo)的關(guān)鍵因素，分別建立了無人艇消耗模型、目標(biāo)價(jià)值毀傷模型和任務(wù)耗費(fèi)時(shí)間模型。然后通過量綱轉(zhuǎn)換和加權(quán)求和，將多目標(biāo)優(yōu)化問題轉(zhuǎn)換為單一目標(biāo)函數(shù)，得出了無人艇優(yōu)勢(shì)函數(shù)。由于作戰(zhàn)過程中無人艇內(nèi)部存在著協(xié)作關(guān)系，因此建立了無人艇整體優(yōu)勢(shì)函數(shù)，進(jìn)而得到了多無人艇協(xié)同目標(biāo)分配數(shù)學(xué)模型。

1）USV消耗模型。

在USV對(duì)目標(biāo)進(jìn)行打擊的同時(shí)，目標(biāo)也對(duì)其進(jìn)行反擊，造成了USV的消耗。設(shè)第u艘USV打擊目標(biāo)t的生存概率為PSut，則USV的消耗模型為

2）目標(biāo)價(jià)值毀傷模型。

綜合考慮目標(biāo)的價(jià)值、確認(rèn)概率、殺傷概率、USV相對(duì)于目標(biāo)的生存概率，則使用第u艘USV攻擊目標(biāo)t時(shí)，目標(biāo)價(jià)值毀傷模型為

式中：Pc表示USV準(zhǔn)確到達(dá)任務(wù)區(qū)域、發(fā)現(xiàn)目標(biāo)以及正確識(shí)別出目標(biāo)的概率；PK表示 USV對(duì)目標(biāo)的殺傷概率；Vt表示摧毀目標(biāo)t獲得的收益。

3）耗費(fèi)時(shí)間模型。

通常USV到達(dá)目標(biāo)區(qū)域越早，發(fā)現(xiàn)和打擊目標(biāo)就越早，所以用到達(dá)時(shí)間來近似估計(jì)USV執(zhí)行任務(wù)耗費(fèi)的時(shí)間，USV到達(dá)目標(biāo)的時(shí)間與其和目標(biāo)間的距離成正比。設(shè)第u艘USV與目標(biāo)t間的距離為Dut，則耗費(fèi)時(shí)間模型為

式中，Dmax為USV與目標(biāo)間最遠(yuǎn)（最長(zhǎng)到達(dá)時(shí)間）距離。

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

4）USV整體優(yōu)勢(shì)函數(shù)。

將多目標(biāo)決策問題轉(zhuǎn)換為單目標(biāo)優(yōu)化問題的常用方法是加權(quán)求和，即為各子目標(biāo)函數(shù)賦予相應(yīng)的權(quán)值，權(quán)值的大小體現(xiàn)了各子目標(biāo)函數(shù)的重要程度，因此，本文采用這一方法將多目標(biāo)優(yōu)化問題轉(zhuǎn)換為單目標(biāo)最優(yōu)化問題。將各量綱轉(zhuǎn)化為[0,1]集合內(nèi)的數(shù)值，令目標(biāo)的價(jià)值V取0～1之間的數(shù)值。因此，USV優(yōu)勢(shì)函數(shù)為

式中，ω1、ω2、ω3為權(quán)系數(shù)，反映了每個(gè)子目標(biāo)的重要程度。

在作戰(zhàn)過程中，不僅敵我雙方存在著沖突，而且己方內(nèi)部也存在著沖突。在合作的同時(shí)，各無人艇都會(huì)盡量取得對(duì)敵目標(biāo)較大的優(yōu)勢(shì)，但在實(shí)際應(yīng)用中，有時(shí)候一部分無人艇的優(yōu)勢(shì)獲得是以另一部分無人艇的態(tài)勢(shì)損失為代價(jià)的。因此，不僅要確定敵我雙方的權(quán)重，而且還需要確定己方內(nèi)部各無人艇的權(quán)重分配。對(duì)于己方內(nèi)部的權(quán)重分配采用多人層次分析法獲取，因此可以得到USV的整體優(yōu)勢(shì)函數(shù)為

式中，ωm是己方內(nèi)部各無人艇的權(quán)重。

5）協(xié)同目標(biāo)分配數(shù)學(xué)模型。

目標(biāo)分配的目的是使USV編隊(duì)的總體優(yōu)勢(shì)達(dá)到最大，從而形成合理的作戰(zhàn)方案。目標(biāo)分配不但要有衡量分配方案優(yōu)劣的標(biāo)準(zhǔn)，而且還需要滿足一定的限制條件，由此可得多無人艇協(xié)同目標(biāo)分配模型為

3 基于DBOA的協(xié)同目標(biāo)分配

通過建立協(xié)同目標(biāo)分配的數(shù)學(xué)模型，并采用二進(jìn)制編碼方案，以整體優(yōu)勢(shì)函數(shù)作為適應(yīng)度函數(shù)，即將USV消耗最小、價(jià)值毀傷最大以及任務(wù)耗費(fèi)時(shí)間最短作為待優(yōu)化的性能指標(biāo)，得到了基于DBOA的多無人艇協(xié)同目標(biāo)分配的基本步驟：

1）根據(jù)多無人艇協(xié)同目標(biāo)分配的數(shù)學(xué)模型確立相關(guān)參數(shù)；

2）生成各艘無人艇對(duì)相應(yīng)目標(biāo)的優(yōu)勢(shì)函數(shù)值，從而得到無人艇優(yōu)勢(shì)矩陣；

3）計(jì)算無人艇編隊(duì)內(nèi)部的權(quán)重，在優(yōu)勢(shì)矩陣的基礎(chǔ)上生成多無人艇整體優(yōu)勢(shì)函數(shù)；

4）進(jìn)行DBOA參數(shù)設(shè)置，運(yùn)用DBOA進(jìn)行多無人艇協(xié)同目標(biāo)分配。

因此，多無人艇協(xié)同目標(biāo)分配 DBOA流程圖如圖2所示。

圖2 多無人艇協(xié)同目標(biāo)分配DBOA流程Fig.2 DBOA flow of multi-USV cooperative target assignment

4 仿真及結(jié)果分析

4.1 仿真初始條件設(shè)定

仿真中設(shè)定無人艇數(shù)量為4，目標(biāo)數(shù)量為4，為了計(jì)算的簡(jiǎn)便，做出如下假設(shè)：1）無人艇的生存概率已知；2）無人艇能準(zhǔn)確到達(dá)任務(wù)區(qū)域、發(fā)現(xiàn)并正確識(shí)別出目標(biāo)，則Pc= 1；3）無人艇攜帶的武器對(duì)目標(biāo)的殺傷概率為已知數(shù)；4）目標(biāo)的價(jià)值已確定；5）通過USV自身的生存、對(duì)目標(biāo)的殺傷、以及完成任務(wù)耗費(fèi)時(shí)間三者的重要程度可以確定權(quán)值ω1、ω2、ω3。

4.2 仿真計(jì)算與分析

根據(jù)USV消耗模型、目標(biāo)價(jià)值毀傷模型以及耗費(fèi)時(shí)間模型可以計(jì)算出無人艇優(yōu)勢(shì)函數(shù)值，從而得到無人艇相對(duì)目標(biāo)的優(yōu)勢(shì)矩陣，如表1所示。

表1 無人艇優(yōu)勢(shì)矩陣Table1 USV superiority matrix

根據(jù)多人層次分析法可以確定4艘無人艇的權(quán)重分別為ωu1=0.157 9、ωu2=0.3158、ωu3=0.105 2、ωu4=0.421 1。在確定無人艇優(yōu)勢(shì)矩陣以及內(nèi)部權(quán)重的基礎(chǔ)上，經(jīng)過 21步運(yùn)行后尋找到最優(yōu)分配結(jié)果，得到的最優(yōu)分配結(jié)果編碼為0011010000100001?；删仃囆问郊茨繕?biāo)3分配給USV1，目標(biāo)4分配給USV2，目標(biāo)2分配給USV3，目標(biāo)1分配給USV4，最終的適應(yīng)度值為0.273 46。圖3給出了各代群體中個(gè)體適應(yīng)度的最大值、最小值與平均值，從圖中可以看出DBOA能夠快速找到個(gè)體適應(yīng)度的最大值，個(gè)體適應(yīng)度的平均值也呈現(xiàn)出快速上升的趨勢(shì)，具有良好的收斂性且速度快。

圖3 適應(yīng)度變化曲線圖Fig.3 Fitness curve

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

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

5 結(jié)束語

本文對(duì)多艘無人艇協(xié)同作戰(zhàn)過程中的協(xié)同目標(biāo)分配問題進(jìn)行了仿真研究。針對(duì)協(xié)同目標(biāo)分配過程中的多參數(shù)、多約束條件，提出了基于 DBOA的協(xié)同目標(biāo)分配方法。DBOA是一種處理多目標(biāo)優(yōu)化問題的有效方法，作為BOA的改進(jìn)，不僅具有BOA較強(qiáng)的優(yōu)化能力，避免逼近局部最優(yōu)或早熟，而且通過決策圖增強(qiáng)了對(duì)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的表達(dá)，減少了存儲(chǔ)。因此，將 DBOA應(yīng)用于多艘無人艇協(xié)同目標(biāo)分配中，能快速對(duì)多約束條件下的多目標(biāo)優(yōu)化問題進(jìn)行求解，并能反映多艘無人艇作戰(zhàn)的協(xié)同性與對(duì)抗性。