面向艦艇編隊(duì)的無人機(jī)集群物資補(bǔ)給規(guī)劃研究

郭文強(qiáng), 李子展, 候勇嚴(yán), 薛博豐

(1.陜西科技大學(xué) 電子信息與人工智能學(xué)院, 陜西 西安 710021; 2.陜西科技大學(xué) 電氣與控制工程學(xué)院, 陜西 西安 710021)

0 引言

艦艇編隊(duì)作為海上軍事力量的直接體現(xiàn),為其提供必要的物資保障對(duì)于增強(qiáng)艦艇編隊(duì)的作戰(zhàn)能力、擴(kuò)大艦艇編隊(duì)的作戰(zhàn)半徑來說是不可或缺的.如何合理規(guī)劃物資補(bǔ)給路徑,提高物資補(bǔ)給效率,對(duì)于提升艦艇編隊(duì)作戰(zhàn)能力具有重大意義[1].無人機(jī)基于其自身的多功能、高移動(dòng)、易部署和低成本等優(yōu)勢(shì),被用作空天地海一體化網(wǎng)絡(luò)架構(gòu)中空域輔助平臺(tái),在越來越多的場(chǎng)景中承擔(dān)重要角色[2].

驅(qū)逐艦、護(hù)衛(wèi)艦、航母等構(gòu)成的艦艇編隊(duì)中的補(bǔ)給艦,其特點(diǎn)是噸位較大(以美軍供應(yīng)級(jí)支援艦為例,該級(jí)艦滿載排水量近5萬噸)、專業(yè)艙室多、所帶物資齊全、補(bǔ)給設(shè)施配套,既有淡水、糧食、蔬菜、水果等生活物資,也有柴油、航空燃油、彈藥等作戰(zhàn)物資,還有各種用于應(yīng)急搶修的備品、備件.它能在通過“吞吐”大量物資,對(duì)各類艦艇進(jìn)行補(bǔ)給.

規(guī)模較大的艦艇編隊(duì)遠(yuǎn)航,需要的補(bǔ)給艦往往不止一艘.目前針對(duì)艦艇編隊(duì)的物資補(bǔ)給規(guī)劃研究主要利用“補(bǔ)給艦”對(duì)艦艇進(jìn)行補(bǔ)給,同時(shí)構(gòu)建約束規(guī)劃模型并對(duì)其進(jìn)行求解得出最優(yōu)補(bǔ)給方案.文獻(xiàn)[1]構(gòu)建了以補(bǔ)給艦艇數(shù)量最少和補(bǔ)給時(shí)間最短為目標(biāo)的多目標(biāo)約束規(guī)劃模型,并利用改進(jìn)后的遺傳算法對(duì)其進(jìn)行求解;文獻(xiàn)[3]構(gòu)建了以最小化補(bǔ)給成本為目標(biāo),以補(bǔ)給水平為約束的分段式補(bǔ)給模型;文獻(xiàn)[4]建立了以最大化作戰(zhàn)效能為目標(biāo)的補(bǔ)給規(guī)劃模型并使用模擬退火算法對(duì)其進(jìn)行求解.然而,在浪、風(fēng)、涌等復(fù)雜海況下,艦艇操作難度大,稍有不慎就會(huì)出現(xiàn)撞船事故[5].

相較補(bǔ)給艦,無人機(jī)作為一種補(bǔ)給裝置,其智能性與安全性水平不斷快速提升,裝置結(jié)構(gòu)易于標(biāo)準(zhǔn)化,批量化設(shè)計(jì)、生產(chǎn)使其造價(jià)較低,可減少補(bǔ)給設(shè)備種類、降低補(bǔ)給成本、方便操作與維修的同時(shí),另外無需要飛行人員,所以最大可能地保障了人的生命安全.上述突出的優(yōu)點(diǎn)可使無人機(jī)保障系統(tǒng)達(dá)到最佳補(bǔ)給效果.

但現(xiàn)有文獻(xiàn)中利用無人機(jī)集群對(duì)艦艇編隊(duì)進(jìn)行物資補(bǔ)給的研究較少,使用無人機(jī)進(jìn)行物資補(bǔ)給具有在特殊環(huán)境下可以實(shí)現(xiàn)人員零傷亡、自身極強(qiáng)的隱蔽性等優(yōu)勢(shì).本文探討了利用無人機(jī)集群針對(duì)艦艇編隊(duì)進(jìn)行物資補(bǔ)給規(guī)劃的問題,使用非線性自適應(yīng)遺傳算法(Nonlinear Adaptive Genetic Algorithm ,NLAGA)對(duì)構(gòu)建的多約束條件下的物資補(bǔ)給規(guī)劃模型進(jìn)行求解,得到所需的無人機(jī)群數(shù)量、最優(yōu)補(bǔ)給路徑以及最小時(shí)間成本.

1 面向艦艇編隊(duì)的物資補(bǔ)給規(guī)劃模型

1.1 問題描述

假設(shè)現(xiàn)有一個(gè)由M架無人機(jī)組成的無人機(jī)集群,計(jì)劃利用其對(duì)某艦艇編隊(duì)進(jìn)行彈藥補(bǔ)給(該艦艇編隊(duì)由N艘艦艇組成).規(guī)定所有無人機(jī)均從補(bǔ)給中心起飛,并且每架無人機(jī)的補(bǔ)給能力有限,無人機(jī)的補(bǔ)給路線長(zhǎng)度滿足各自通航距離.同時(shí),由于通行時(shí)刻不同導(dǎo)致同一路徑上無人機(jī)的行駛速度也不同.無人機(jī)從物資補(bǔ)給中心出發(fā),在規(guī)定時(shí)間窗內(nèi)對(duì)艦艇編隊(duì)進(jìn)行補(bǔ)給,完成對(duì)所有艦艇的補(bǔ)給后返回物資補(bǔ)給中心.每個(gè)艦艇都有設(shè)定的服務(wù)時(shí)間窗(僅在此時(shí)間范圍內(nèi)能進(jìn)行補(bǔ)給作業(yè))和不同的物資需求量,目標(biāo)是確定無人機(jī)群所需無人機(jī)數(shù)量,并確定補(bǔ)給路線,用最少的時(shí)間完成所有補(bǔ)給任務(wù),實(shí)現(xiàn)補(bǔ)給成本最優(yōu)的目標(biāo).

1.2 無人機(jī)飛行時(shí)間成本

無人機(jī)在執(zhí)行任務(wù)時(shí)的飛行時(shí)間與無人機(jī)的飛行速度以及艦艇之間的距離相關(guān).飛行時(shí)間Tf為:

(1)

1.3 補(bǔ)給作業(yè)時(shí)間成本

到達(dá)艦艇后的物資準(zhǔn)備時(shí)間Tp為:

(2)

式(2)中:pi為艦艇i的物資準(zhǔn)備時(shí)間.

補(bǔ)給花費(fèi)時(shí)間Ts為:

(3)

式(3)中:si為無人機(jī)在艦艇i的物資補(bǔ)給作業(yè)所花費(fèi)的時(shí)間.

綜上,無人機(jī)的總補(bǔ)給作業(yè)時(shí)間成本Tw為:

Tw=Tf+Tp+Ts

(4)

1.4 時(shí)間懲罰成本

(5)

令M2表示延誤到達(dá)的懲罰系數(shù),則延誤到達(dá)的時(shí)間懲罰成本為:

(6)

因此考慮無人機(jī)允許補(bǔ)給作業(yè)時(shí)間窗的時(shí)間懲罰成本Tpc為:

Tpc=Cae+Cal

(7)

1.5 面向艦艇編隊(duì)的無人機(jī)物資補(bǔ)給規(guī)劃模型

考慮將無人機(jī)的作業(yè)時(shí)間以及時(shí)間窗約束而產(chǎn)生的懲罰成本,同時(shí)將無人機(jī)作業(yè)時(shí)間窗、安全返航、物資需求量與無人機(jī)總最大載重量等約束條件,本文構(gòu)建的面向艦艇編隊(duì)的無人機(jī)物資補(bǔ)給規(guī)劃模型如下:

(8)

2 求解補(bǔ)給規(guī)劃問題的NLAGA算法

對(duì)于每架無人機(jī)來說,補(bǔ)給任務(wù)可視為帶時(shí)間窗限制的車輛路徑規(guī)劃問題,此類問題已被證明是NP(non-deterministic polynomial,非確定性多項(xiàng)式)[8]難題.啟發(fā)式算法是目前解決NP難題的有效方法之一[9].在這些啟發(fā)式算法中,遺傳算法(Genetic Algorithm ,GA)和改進(jìn)的遺傳算法因其快速收斂而被廣泛采用,故本文采用遺傳算法對(duì)物資補(bǔ)給規(guī)劃路徑進(jìn)行染色體(基因)編碼,并對(duì)物資補(bǔ)給規(guī)劃模型進(jìn)行求解.

遺傳算法本質(zhì)上是一種通過模擬自然進(jìn)化來搜尋最優(yōu)解的方法,其中交叉、變異概率(Pc、Pm)對(duì)算法的性能起著決定性的作用.傳統(tǒng)GA中交叉、變異概率為定值,在進(jìn)化后期容易對(duì)最優(yōu)解造成破壞,因此可能會(huì)導(dǎo)致早熟收斂現(xiàn)象的產(chǎn)生.文獻(xiàn)[10]提出了一種改進(jìn)的自適應(yīng)遺傳算法(Improved Adaptive Genetic Algorithm ,IAGA),其中交叉、變異概率計(jì)算方法如下:

(14)

(15)

式(14)、(15)中:fmax表示種群中染色體適應(yīng)度最大值,f代表交叉操作染色體中的適應(yīng)度值,fa代表種群染色體適應(yīng)度均值,f′代表待變異操作染色體的適應(yīng)度值,其它參數(shù)常取Pc1=0.9、Pc2=0.6、Pm1=0.1、Pm2=0.01.

IAGA可以通過自適應(yīng)調(diào)節(jié)概率來保留最優(yōu)解,在一定范圍可緩解GA早熟收斂現(xiàn)象.但在進(jìn)化中段,種群中染色體的交叉、變異概率普遍很低,從而可能導(dǎo)致交叉、變異操作失效,出現(xiàn)進(jìn)化停滯的現(xiàn)象.為了減少此類風(fēng)險(xiǎn),本文對(duì)IAGA進(jìn)行了進(jìn)一步的改進(jìn).

2.1 非線性概率函數(shù)

本文引入Sigmoid函數(shù)[11]設(shè)計(jì)了一類非線性的交叉概率和變異概率計(jì)算函數(shù),分別表達(dá)如下:

(16)

(17)

(18)

2.2 艦艇編隊(duì)的無人機(jī)物資補(bǔ)給規(guī)劃算法-NLAGA

基于非線性概率函數(shù)設(shè)計(jì)的補(bǔ)給規(guī)劃模型的NLAGA算法步驟如下:

第1步:確定各艦艇物資需求量Qi(i=1,2,…,N)、艦艇坐標(biāo)、艦艇補(bǔ)給時(shí)間窗、補(bǔ)給作業(yè)時(shí)間,懲罰系數(shù)M1、M2,輸入每架無人機(jī)的最大補(bǔ)給量、速度范圍,以及進(jìn)化算法操作系數(shù)A、B、C,最大迭代次數(shù)MaxGen和尋優(yōu)收斂誤差ε.

第2步:根據(jù)公式(8)至(13)描述的規(guī)劃模型,利用文獻(xiàn)[12]的方法將其表示為2N條補(bǔ)給規(guī)劃的初始染色體.

第3步:令迭代次數(shù)iter=1.

第4步:根據(jù)公式(8)計(jì)算每條染色體的適應(yīng)度函數(shù),并選擇目標(biāo)函數(shù)最小的Ztemp.

第5步:利用式(14)計(jì)算交叉概率并執(zhí)行交叉操作[13].

第6步:利用式(15)計(jì)算變異概率并執(zhí)行變異操作[12],形成新的染色體種群.

第7步:根據(jù)公式(8)計(jì)算每條染色體的適應(yīng)度Znew.

第8步:若Znew

第9步:若Znew-Z*<ε,則跳轉(zhuǎn)至第11步;否則iter=iter+1,執(zhí)行第10步.

第10步:若iter=MaxGen,進(jìn)入第11步;否則返回執(zhí)行第4步,繼續(xù)進(jìn)化尋優(yōu).

3 實(shí)驗(yàn)結(jié)果與分析

3.1 算法性能測(cè)試

為了驗(yàn)證NLAGA算法在求解補(bǔ)給規(guī)劃問題中的優(yōu)越性的性能,本文將無人機(jī)補(bǔ)給規(guī)劃問題抽象為帶時(shí)間窗約束的車輛路徑問題(VRPTW)并使用經(jīng)典的Solomen數(shù)據(jù)集[14]中r101的算例進(jìn)行測(cè)試.將NLAGA算法與文獻(xiàn)[13]中所提出的AGA算法以及IAGA算法進(jìn)行對(duì)比.

61個(gè)待補(bǔ)給點(diǎn)位置已知,所需物資量均為Qi=150 kg(i=1,2,…,61),時(shí)間懲罰系數(shù)M1=10、M2=100;無人機(jī)速度vmin=0 km/min,vmax=0.8 km/min,單架最大補(bǔ)給量50 kg;最大迭代次數(shù):MAXGEN=6 000;步長(zhǎng)λ=200;交叉、變異系數(shù):A=4、B=6、C=0.55;為了達(dá)到相同的迭代次數(shù),實(shí)驗(yàn)中將收斂誤差ε設(shè)為0.其它參數(shù)選擇參考同文獻(xiàn)[13].

仿真平臺(tái)為Matlab版本R2016a,所有測(cè)試都在配置了2.3 GHz Intel Core i10處理器和8.0 GB內(nèi)存、Windows 10系統(tǒng)的計(jì)算機(jī)上進(jìn)行.

為了減少隨機(jī)性對(duì)實(shí)驗(yàn)結(jié)果的影響,實(shí)驗(yàn)中將不同求解方法獨(dú)立運(yùn)行15輪,記錄其均值.求解后該補(bǔ)給任務(wù)均需15架無人機(jī)參與補(bǔ)給任務(wù),得到目標(biāo)函數(shù)值變化曲線如圖1所示.

圖1 目標(biāo)函數(shù)值變化曲線

不同算法求解的最優(yōu)值、均值以及方差,分別如表1、表2、表3所示.

表1 不同算法求解的目標(biāo)函數(shù)最優(yōu)值

表2 不同算法求解的目標(biāo)函數(shù)的均值

表3 不同算法求解的目標(biāo)函數(shù)的方差

由圖1可看出,在本實(shí)驗(yàn)中,不同算法求解在迭代至3 500輪時(shí)尋優(yōu)過程趨于穩(wěn)定.在相同迭代次數(shù)時(shí),由表1至表3可知,利用NLAGA得到的最優(yōu)解及其均值、方差均優(yōu)于AGA和IAGA方法.

分析可知:在計(jì)算機(jī)模擬隨機(jī)取值條件下,NLAGA中的非線性概率函數(shù)可以在進(jìn)化中段,通過本文設(shè)計(jì)的非線性函數(shù)的拉伸,擴(kuò)大了概率的取值范圍,有利于采樣到更豐富的交叉和變異概率值,提高了算法在求解空間的尋優(yōu)探索能力,有利于保留最優(yōu)解,有效避免了進(jìn)化停滯的現(xiàn)象.

3.2 面向艦艇編隊(duì)的無人機(jī)物資補(bǔ)給規(guī)劃實(shí)驗(yàn)與分析

本實(shí)驗(yàn)針對(duì)某艦艇編隊(duì)的補(bǔ)給規(guī)劃任務(wù)進(jìn)行了求解.假設(shè)該艦艇編隊(duì)的待補(bǔ)給艦艇數(shù)量為15艘.補(bǔ)給中心的相對(duì)坐標(biāo)為(660,750)km,現(xiàn)利用相同性能的無人機(jī)執(zhí)行補(bǔ)給規(guī)劃任務(wù),飛行速度為vmin=0 km/min,vmax=0.8 km/min,此外假設(shè)每艘艦艇所需的物資準(zhǔn)備時(shí)間pi均為5 min(i=1,2,…,N),其他參數(shù)如表4所示.利用本文提出的NLAGA算法求解該問題,將收斂誤差ε設(shè)為0.001,其他參數(shù)取值同3.1.

表4 補(bǔ)給任務(wù)相關(guān)參數(shù)

利用本文提出的NLAGA算法解算出完成該補(bǔ)給規(guī)劃任務(wù)需要5架無人機(jī),完成補(bǔ)給規(guī)劃任務(wù)最短耗時(shí)為291.309 1 min.

完成本次補(bǔ)給規(guī)劃任務(wù)的無人機(jī)群最優(yōu)補(bǔ)給路徑、目標(biāo)函數(shù)值及規(guī)劃耗時(shí)的變化分別如圖2和圖3所示.

圖2 無人機(jī)補(bǔ)給路徑示意圖

圖3 目標(biāo)函數(shù)值及規(guī)劃耗時(shí)變化曲線

4 結(jié)論

本文針對(duì)無人機(jī)集群對(duì)艦艇編隊(duì)的物資補(bǔ)給規(guī)劃問題,以艦艇補(bǔ)給時(shí)間窗、無人機(jī)最大載重量等為約束條件,構(gòu)建了無人機(jī)集群補(bǔ)給規(guī)劃模型.在自適應(yīng)遺傳算法的基礎(chǔ)上,設(shè)計(jì)了非線性的交叉概率函數(shù)和變異概率函數(shù),并提出了一種無人機(jī)物資補(bǔ)給規(guī)劃算法NLAGA.實(shí)驗(yàn)結(jié)果表明:NLAGA法的性能要優(yōu)于AGA和IAGA方法,可有效地解決無人機(jī)集群對(duì)艦艇編隊(duì)的物資補(bǔ)給規(guī)劃問題,為實(shí)現(xiàn)艦艇編隊(duì)的物資補(bǔ)給提供科學(xué)的決策支持.