基于改進(jìn)QGA 的有/無(wú)人機(jī)編隊(duì)多任務(wù)聯(lián)盟生成*

薄 寧，李相民，唐嘉鈺，龐 威，代進(jìn)進(jìn)

（1.海軍航空大學(xué)，山東 煙臺(tái) 264001；2.解放軍91213 部隊(duì)，山東 煙臺(tái) 264000；3.解放軍31102 部隊(duì)，南京 210000）

0 引言

隨著無(wú)人機(jī)技術(shù)的不斷發(fā)展，無(wú)人機(jī)與有人機(jī)混合編隊(duì)共同執(zhí)行任務(wù)將成為無(wú)人機(jī)作戰(zhàn)運(yùn)用的一種新型樣式［1］。任務(wù)分配是有/無(wú)人機(jī)編隊(duì)作戰(zhàn)指揮控制過(guò)程的關(guān)鍵步驟。受資源或能力所限，復(fù)雜任務(wù)一般難以由單架飛機(jī)獨(dú)立完成，采用聯(lián)盟方法成為一種新的解決思路。

聯(lián)盟方法由Shehory 等人提出［2］，近年來(lái)已成為解決多智能體系統(tǒng)（Multi Agent System，MAS）中任務(wù)分配問(wèn)題熱點(diǎn)方法之一［3］，并應(yīng)用于求解軍事領(lǐng)域有關(guān)問(wèn)題［6］。文獻(xiàn)［8］使用分階次優(yōu)聯(lián)盟快速組建算法（MSOCFA）求解無(wú)人機(jī)協(xié)同搜索聯(lián)盟組建問(wèn)題，但其本質(zhì)上仍是單聯(lián)盟形成問(wèn)題。文獻(xiàn)［9］使用拍賣(mài)算法求解有/無(wú)人作戰(zhàn)智能體聯(lián)盟問(wèn)題，但所建模型中缺少任務(wù)完成時(shí)限等時(shí)間約束。在問(wèn)題求解方法上，多采用以拍賣(mài)算法、合同網(wǎng)等方法為代表的分布式求解方法［7，10］，雖可以克服集中式方法中心節(jié)點(diǎn)計(jì)算負(fù)載大的缺點(diǎn)，但由于需進(jìn)行多輪信息協(xié)同，通信開(kāi)銷(xiāo)較大，對(duì)通信傳輸能力要求較高［10］。

本文采用一種改進(jìn)的QGA 算法對(duì)有/無(wú)人機(jī)編隊(duì)多任務(wù)聯(lián)盟生成問(wèn)題進(jìn)行集中式求解。根據(jù)有/無(wú)人機(jī)協(xié)同執(zhí)行任務(wù)特點(diǎn)，確定問(wèn)題的約束條件與目標(biāo)函數(shù)，建立優(yōu)化問(wèn)題數(shù)學(xué)模型；從多分組并行演化、觀測(cè)值修正、動(dòng)態(tài)旋轉(zhuǎn)角調(diào)整3 個(gè)方面對(duì)原始QGA 算法進(jìn)行改進(jìn)用于問(wèn)題求解，提高算法搜索效率，并結(jié)合實(shí)際算例對(duì)設(shè)計(jì)的方法進(jìn)行仿真分析。

1 問(wèn)題描述與要素定義

1.1 問(wèn)題描述

有/無(wú)人機(jī)編隊(duì)指控系統(tǒng)根據(jù)編隊(duì)使命形成了多個(gè)任務(wù)。由有人機(jī)和無(wú)人機(jī)形成多個(gè)任務(wù)聯(lián)盟，對(duì)應(yīng)完成多個(gè)不同的作戰(zhàn)任務(wù)。聯(lián)盟生成問(wèn)題的目標(biāo)是求解確定聯(lián)盟中各作戰(zhàn)智能體的數(shù)量，使聯(lián)盟能力與任務(wù)需求可以有效匹配，并按照一定的準(zhǔn)則使得效果最優(yōu)。

1.2 要素定義

為便于問(wèn)題建模，在借鑒文獻(xiàn)［10］的基礎(chǔ)上，對(duì)有/無(wú)人機(jī)作戰(zhàn)智能體、作戰(zhàn)聯(lián)盟、作戰(zhàn)任務(wù)等關(guān)鍵要素，作出定義和說(shuō)明。

2 聯(lián)盟生成問(wèn)題建模

作戰(zhàn)聯(lián)盟生成優(yōu)化問(wèn)題建模時(shí)，優(yōu)化目標(biāo)選取需要考慮任務(wù)執(zhí)行收益、付出代價(jià)等因素，考慮的約束主要有完成時(shí)限、任務(wù)時(shí)序、任務(wù)時(shí)窗、飛行時(shí)間、執(zhí)行任務(wù)數(shù)量等約束。因此，首先給出涉及到的各因素參數(shù)的計(jì)算方法，再形成聯(lián)盟生成優(yōu)化問(wèn)題模型。定義有/無(wú)人機(jī)編隊(duì)任務(wù)分配決策矩陣：

2.1 聯(lián)盟收益

2.1.1 無(wú)時(shí)窗約束任務(wù)收益Cj執(zhí)行Tj得到的任務(wù)收益根據(jù)下式計(jì)算：

其中，Suc（Tn，Ψ，A）為任務(wù)完成判斷函數(shù)，當(dāng)任務(wù)Tn在分配決策Ψ 下滿(mǎn)足完成條件時(shí)，取值為1，否則為0。

2.1.2 時(shí)窗約束任務(wù)收益

對(duì)于時(shí)間窗約束處理，通常采用將任務(wù)收益表示為到達(dá)時(shí)刻的函數(shù)形式［11］，難以準(zhǔn)確反映任務(wù)執(zhí)行過(guò)程時(shí)間對(duì)任務(wù)效果的影響。本文采用實(shí)際執(zhí)行時(shí)間窗與任務(wù)需求時(shí)間窗重合度來(lái)表示時(shí)窗任務(wù)的完成效果影響概率，即：

2.1.3 總收益

2.2 聯(lián)盟成本

聯(lián)盟付出成本是指聯(lián)盟Cj在執(zhí)行Tj時(shí)，聯(lián)盟內(nèi)成員被毀傷的總代價(jià)期望值，即：

2.3 目標(biāo)函數(shù)

形成的多任務(wù)聯(lián)盟應(yīng)使得任務(wù)完成收益最大，代價(jià)最小，且完成時(shí)間盡可能小。因此，定義有/無(wú)人機(jī)聯(lián)盟形成問(wèn)題目標(biāo)函數(shù)如下：

2.4 約束條件

2.4.1 任務(wù)資源約束

每個(gè)任務(wù)的資源能力需求向量的分量應(yīng)大于形成聯(lián)盟的能力向量分量，即：

2.4.2 智能體加入聯(lián)盟數(shù)量約束

每個(gè)智能體加入的聯(lián)盟總數(shù)不得超過(guò)加入聯(lián)盟上限NMAX_C，即：

2.4.3 聯(lián)盟指揮控制能力約束

是指任一個(gè)聯(lián)盟中，決策能力值總和應(yīng)大于等于0，即：

2.4.4 平臺(tái)飛行時(shí)間約束

僅對(duì)無(wú)人機(jī)飛行時(shí)間進(jìn)行限定。每架無(wú)人機(jī)執(zhí)行任務(wù)總用時(shí)應(yīng)小于剩余可飛時(shí)間：

2.4.5 任務(wù)組完成時(shí)限約束

任意一任務(wù)的結(jié)束時(shí)間應(yīng)小于等于任務(wù)集合T規(guī)定的完成時(shí)限tend，即：

其中，tend為要求的任務(wù)組完成時(shí)限。

2.5 聯(lián)盟生成問(wèn)題數(shù)學(xué)模型

綜合式（6）、式（8）～式（14），可得有/無(wú)人機(jī)編隊(duì)多任務(wù)聯(lián)盟生成數(shù)學(xué)模型：

3 問(wèn)題求解

所建問(wèn)題模型是一個(gè)復(fù)雜的組合優(yōu)化問(wèn)題，傳統(tǒng)仿生智能算法用于求解此類(lèi)問(wèn)題時(shí)存在收斂速度較慢、易陷入局部最優(yōu)等問(wèn)題。文獻(xiàn)［12］將量子比特和量子旋轉(zhuǎn)門(mén)引入到遺傳算法中，提出了QGA算法，具有收斂速度快，全局尋優(yōu)能力強(qiáng)等特點(diǎn)，近年來(lái)得到了廣泛的研究應(yīng)用與改進(jìn)［13］。傳統(tǒng)QGA算法存在演化目標(biāo)單一、量子旋轉(zhuǎn)角取值不靈活等不足。本文采用建立多個(gè)獨(dú)立的初始種群，每個(gè)種群分別進(jìn)行QGA 尋優(yōu)操作；然后根據(jù)問(wèn)題約束進(jìn)行觀測(cè)值修正，提高可行解搜索效率，并建立量子旋轉(zhuǎn)角動(dòng)態(tài)調(diào)整機(jī)制，改進(jìn)原算法中固定旋轉(zhuǎn)角的不足，從而改進(jìn)QGA 算法求解本文問(wèn)題求解效率。

3.1 染色體編碼

3.2 并行量子演化計(jì)算

假設(shè)分組數(shù)量為Nq_team，首先隨機(jī)生成種群規(guī)模為NSEED_MAX的關(guān)于Ψ 初始種群W={Ψ1，Ψ2，…，ΨNSEED_MAX}，然后將NSEED_MAX個(gè)初始量子染色體平均分配至每個(gè)分組中，每個(gè)分組單獨(dú)運(yùn)行QGA 算法，旋轉(zhuǎn)角確定時(shí)依據(jù)的目標(biāo)狀態(tài)為各分組自身單獨(dú)的目標(biāo)狀態(tài)。每隔一定迭代次數(shù)，分組之間通過(guò)優(yōu)秀染色體交換和演化目標(biāo)互換兩種方式實(shí)現(xiàn)交互，達(dá)到共同加快收斂速度的目的。

3.3 觀測(cè)值修正

3.4 動(dòng)態(tài)量子旋轉(zhuǎn)角機(jī)制

原始QGA 算法中，當(dāng)前狀態(tài)、目標(biāo)狀態(tài)以及兩者觀測(cè)值的適應(yīng)度值確定后，θi是固定值，搜索過(guò)程不夠靈活。采用動(dòng)態(tài)量子旋轉(zhuǎn)角調(diào)整機(jī)制［16］對(duì)文獻(xiàn)［12］設(shè)計(jì)的θi取值查詢(xún)表中Δθi項(xiàng)進(jìn)行改進(jìn)：

其中，Δθ 為固定角，ξ 為［0，1］之間的常系數(shù)，n 為當(dāng)前迭代次數(shù)，LoopNum 為最大迭代次數(shù)。θi使用改進(jìn)后的查詢(xún)表進(jìn)行取值。在迭代初期，θi絕對(duì)值較大，可以進(jìn)行快速大范圍搜索，隨著迭代的不斷進(jìn)行，θi絕對(duì)值不斷變小，同時(shí)各染色體不斷向最優(yōu)解靠近，有利于在最優(yōu)解附近展開(kāi)精細(xì)搜索。

3.5 算法流程

改進(jìn)的QGA 實(shí)現(xiàn)步驟如下：

Step 1：參數(shù)初始化。令k=0，隨機(jī)生成Nq_team個(gè)種群規(guī)模為Nper_team的關(guān)于φ（Ψ）的初始種群。

Step 2：對(duì)于每個(gè)分組中的每個(gè)染色體個(gè)體，分別執(zhí)行多次觀測(cè)，選擇適應(yīng)度值最高的觀測(cè)作為狀態(tài)Ψ（0）。

Step 3：從所有染色體的Ψ（0）中為每個(gè)種群選擇最高適應(yīng)度值的觀測(cè)作為演化目標(biāo)。

Step 4：判斷是否滿(mǎn)足退出條件，若滿(mǎn)足，則退出；否則轉(zhuǎn)Step 5。

Step 5：k=k+1。

Step 6：判斷是否滿(mǎn)足染色體和演化目標(biāo)交換條件，若滿(mǎn)足，執(zhí)行染色體移民和演化目標(biāo)交換，并進(jìn)行種群更新。轉(zhuǎn)Step 7。

Step 7：對(duì)于每個(gè)分組中的每個(gè)染色體個(gè)體，分別執(zhí)行一次觀測(cè)，得到一個(gè)狀態(tài)Ψ（k）。

Step 8：計(jì)算所有觀測(cè)的適應(yīng)度值。

Step 9：記下最優(yōu)個(gè)體及對(duì)應(yīng)的適應(yīng)度值。

Step 10：對(duì)每個(gè)染色體進(jìn)行量子旋轉(zhuǎn)門(mén)操作，得到更新的種群。

Step 11：更新各種群演化目標(biāo)及全局最優(yōu)適應(yīng)度值。轉(zhuǎn)Step 4。

改進(jìn)的QGA 算法流程如圖1 所示。

圖1 改進(jìn)的QGA 算法流程

4 案例仿真與結(jié)果分析

采用計(jì)算機(jī)仿真驗(yàn)證提出的有/無(wú)人機(jī)編隊(duì)多任務(wù)聯(lián)盟生成方法的性能。計(jì)算機(jī)基本配置為：Intel Pentium（R）Dual E2180 2 GHz，2 G 內(nèi)存，Windows XP操作系統(tǒng)。仿真平臺(tái)軟件及版本為matlab 2014a。

4.1 初始參數(shù)設(shè)定

假定任務(wù)背景為有/無(wú)人機(jī)編隊(duì)對(duì)敵方防空陣地、機(jī)場(chǎng)、指揮所、移動(dòng)目標(biāo)等多個(gè)地面目標(biāo)實(shí)施攻擊。戰(zhàn)場(chǎng)區(qū)域?yàn)?00 km×200 km 的矩形區(qū)域。無(wú)人機(jī)待戰(zhàn)集結(jié)區(qū)中心坐標(biāo)為（20，20），有人機(jī)待戰(zhàn)機(jī)場(chǎng)坐標(biāo)為（-40，40），單位為km。每個(gè)待攻擊目標(biāo)對(duì)應(yīng)一個(gè)任務(wù)，分別編號(hào)為T(mén)1～T8。假定任務(wù)序列已預(yù)先規(guī)劃，如圖2 所示。

圖2 任務(wù)間的時(shí)序關(guān)系

各任務(wù)屬性如表1 所示。

表1 作戰(zhàn)任務(wù)屬性

假設(shè)共有8 架有人機(jī)、16 架無(wú)人機(jī)可供分配使用。有人機(jī)或無(wú)人機(jī)掛載有反輻射導(dǎo)彈、對(duì)地攻擊武器類(lèi)型1、對(duì)地攻擊武器類(lèi)型2、偵察搜索設(shè)備類(lèi)型A、偵察搜索設(shè)備類(lèi)型B、目標(biāo)指示設(shè)備等類(lèi)型載荷，載荷類(lèi)型分別為r1CA～r6CA。作戰(zhàn)智能體屬性如下頁(yè)表2 所示。

4.2 仿真結(jié)果與分析

圖3 原始QGA 與改進(jìn)QGA 尋優(yōu)搜索結(jié)果對(duì)比

由圖3 可以看出，從收斂速度、解質(zhì)量上，改進(jìn)的QGA 算法均優(yōu)于經(jīng)典QGA 算法。兩種方法進(jìn)行100 次蒙特卡洛仿真后，求解最優(yōu)值情況統(tǒng)計(jì)結(jié)果分別如圖4、圖5 所示，其中最優(yōu)適應(yīng)度為0 表示未搜索到可行解。

表2 作戰(zhàn)智能體屬性

圖4 原始QGA 蒙特卡洛仿真結(jié)果

圖5 改進(jìn)QGA 蒙特卡洛仿真結(jié)果

由圖4、圖5 對(duì)比可以看出，改進(jìn)后的QGA 算法，從搜索得到最優(yōu)解適應(yīng)度最大值、搜索成功次數(shù)、最優(yōu)解均值3 個(gè)統(tǒng)計(jì)指標(biāo)上，均優(yōu)于原始QGA算法。二者關(guān)鍵性能參數(shù)具體統(tǒng)計(jì)結(jié)果對(duì)比如表3所示。

表3 原始QGA 與改進(jìn)QGA 統(tǒng)計(jì)結(jié)果對(duì)比

由表3 可以看出，兩者收斂時(shí)間均較長(zhǎng)，這是由于本文設(shè)定的問(wèn)題初始較為嚴(yán)苛，搜索過(guò)程中存在大量的非可行解；并且單次迭代中，任務(wù)執(zhí)行時(shí)間一項(xiàng)，計(jì)算較為復(fù)雜，計(jì)算量較大導(dǎo)致。改進(jìn)QGA算法2 次仿真中未搜索到可行解，說(shuō)明在條件較為嚴(yán)苛的離散變量規(guī)劃中，改進(jìn)的QGA 方法無(wú)法保證每次均能搜索到可行解。

改進(jìn)的QGA 算法求解得出的最優(yōu)聯(lián)盟生成結(jié)果如表4 所示。

表4 聯(lián)盟生成問(wèn)題求解結(jié)果

由表4 可以看出，所得結(jié)果中，每個(gè)聯(lián)盟均由2～3 個(gè)作戰(zhàn)智能體構(gòu)成，聯(lián)盟成員數(shù)量分布均衡。使用的作戰(zhàn)智能體數(shù)量總計(jì)為12 個(gè)，可以為其他后續(xù)任務(wù)保持能力冗余。每個(gè)聯(lián)盟并不要求有人作戰(zhàn)智能體和無(wú)人作戰(zhàn)智能體均加入，如任務(wù)T2即由無(wú)人機(jī)聯(lián)盟完成。所得結(jié)果與實(shí)際情況較為一致。

5 結(jié)論

1）本文提出的方法可以有效解決有/ 無(wú)人機(jī)編隊(duì)任務(wù)聯(lián)盟形成問(wèn)題，解質(zhì)量較高，與實(shí)際應(yīng)用較為符合，對(duì)其他相近問(wèn)題的求解也具有一定的參考借鑒意義。

2）由于單次迭代過(guò)程中計(jì)算內(nèi)容復(fù)雜性特點(diǎn)，算法整體計(jì)算時(shí)間較長(zhǎng)，較適用于使命預(yù)先規(guī)劃階段相關(guān)問(wèn)題求解。若應(yīng)用于實(shí)時(shí)規(guī)劃階段中，需在求解時(shí)間與解質(zhì)量上進(jìn)行折中。

3）該算法在條件較為嚴(yán)格的條件下，無(wú)法保證在可接受的求解時(shí)間內(nèi)每次均能搜索到可行解，下步將考慮通過(guò)與其他類(lèi)型搜索算法相結(jié)合，進(jìn)一步改進(jìn)算法的性能。