基于多種群遺傳算法的多UUV 任務(wù)分配方法

范學滿,薛昌友,張會

(海軍潛艇學院,山東 青島,266199)

0 引言

利用搭載傳感器載荷的無人水下航行器(unmanned undersea vehicle,UUV)執(zhí)行對海偵察任務(wù)是UUV 典型應用方向之一。單個UUV 在巡航時間、載荷數(shù)量以及種類等方面制約了其偵察能力,往往需要多UUV 協(xié)同作戰(zhàn)。此時,根據(jù)任務(wù)的復雜度、UUV 數(shù)量以及任務(wù)完成能力等因素,對任務(wù)進行合理地分配,對于提高任務(wù)執(zhí)行效率至關(guān)重要[1]。

任務(wù)分配是海戰(zhàn)場多UUV 協(xié)同作戰(zhàn)的重要研究內(nèi)容之一,其目的是在實現(xiàn)各技術(shù)、戰(zhàn)術(shù)指標的前提下,根據(jù)目標狀態(tài)和戰(zhàn)場態(tài)勢,將任務(wù)分配給各UUV,使得整個多UUV 系統(tǒng)的整體作戰(zhàn)收益最大,付出的代價最小[2]。目前,常用的任務(wù)分配算法主要有基于市場機制的分配方法、指派方法和啟發(fā)式算法等。其中:基于市場機制的方法受市場經(jīng)濟學啟發(fā)提出,是基于買賣雙方的需求與能力,通過競爭與交換完成分配,又細分為拍賣算法和合同網(wǎng)算法等[3];指派方法是基于任務(wù)需求和約束條件,依據(jù)特定的指派原則確定任務(wù)分配方案[4];啟發(fā)式算法是受大自然運行規(guī)律或面向具體問題的經(jīng)驗、規(guī)則啟發(fā)出來的方法,相比另外2 種算法,具有高魯棒性和求解高度復雜非線性問題的能力,已成為解決任務(wù)分配問題的主流方法。遺傳算法就是典型的啟發(fā)式算法[5]。

文獻[6]～[9]利用多種群遺傳算法求解多目標多約束問題,通過為不同的種群分配不同概率的重組和變異算子,并行實現(xiàn)多樣化的搜索結(jié)果;通過在各種群內(nèi)部引入“精英保留”策略,改進遺傳算法的全局收斂能力;通過設(shè)置種群間的個體遷移操作,實現(xiàn)協(xié)同進化。但對于復雜、大規(guī)模約束問題仍存在收斂過慢、進化不充分等問題。為了解決上述問題,文中提出一種人機融合的多種群遺傳算法用于多UUV 協(xié)同偵察任務(wù)分配,一方面,針對多UUV 協(xié)同任務(wù)分配的多約束特性,引入人類先驗知識進行種群初始化,提升初代種群的個體質(zhì)量,加速算法收斂;另外,針對可行性法則處理多約束條件時,存在多代種群極易缺乏甚至沒有滿足約束個體的問題,引入“遺忘策略”彌補可能出現(xiàn)的進化不徹底問題。并針對多基地、多目標、多約束的多UUV 協(xié)同偵察任務(wù)分配問題開展上述研究,通過與單種群遺傳算法對比,驗證了文中算法的有效性和魯棒性。

1 多UUV 協(xié)同偵察任務(wù)分配模型

1.1 模型假設(shè)

多UUV 協(xié)同偵察任務(wù)分配問題是一個典型的多約束、多參數(shù)的非確定多項式(non-deterministic polynomial,NP)問題,該問題涉及系統(tǒng)結(jié)構(gòu)、單UUV、任務(wù)目標和外界環(huán)境等多因素,針對不同因素的模型求解策略有較大不同。文中基本假設(shè)如下:

1) 任務(wù)目標事先確定,環(huán)境因素已知且不發(fā)生重大變化;

2) UUV 經(jīng)過目標,任務(wù)即完成;

3) 每個偵察任務(wù)由單個UUV 即可完成;

4) 目標位置已知且靜止,對UUV 不構(gòu)成威脅;

5) 各UUV 位于不同的基地;

6) 單個UUV 可搭載多種偵察載荷。

1.2 符號描述

1.3 約束條件

由于協(xié)同偵察任務(wù)的復雜性,可以將任務(wù)集合中的任務(wù)分為獨立任務(wù)和協(xié)同任務(wù)2 類。其中,獨立任務(wù)是只與其自身約束相關(guān)的任務(wù);協(xié)同任務(wù)是除自身約束外,相互間還存在時間或功能約束的任務(wù)。任務(wù)自身約束主要包括時間約束和載荷約束等,任務(wù)之間的約束主要包括時序約束和使能約束等,另外UUV 自身約束主要包括物資約束和最大工作時間約束等[2]。

1) 偵察次數(shù)約束

對任意目標j∈M最多進行一次偵察,避免重復偵察。

2) 重返基地約束

對任意UUVi∈V,若執(zhí)行偵察任務(wù),需滿足從基地出發(fā)并返回原基地的要求。

3) 任務(wù)時間約束

如果對目標j的偵察任務(wù)必須在固定的時間窗口內(nèi)開始,表示該任務(wù)具有時間約束。過早或過晚到達任務(wù)點位置,則無法執(zhí)行偵察,需要等待至滿足時間約束方可執(zhí)行。

4) 任務(wù)載荷約束

對目標j進行偵察的UUVi需要滿足目標j的任務(wù)載荷類型要求,即。

5) 時序約束

如果必須同步或按順序依次完成對任務(wù)目標i和目標j的偵察,表示目標i與目標j之間存在時序約束,記為S equence(i,j)。必須在目標i被偵察之前完成的任務(wù)稱為目標i的緊前任務(wù),必須在目標i被偵察之后立即執(zhí)行的任務(wù)稱為目標i的緊后任務(wù),與目標i具有時序約束的任務(wù)構(gòu)成集合記為Sseq(i)。具有時序約束的任務(wù)通常需要遵循嚴格的執(zhí)行順序。例如,假設(shè)共7 個待執(zhí)行的任務(wù),其中任務(wù)1 為任務(wù)4 的緊前任務(wù),任務(wù)7 為任務(wù)4 的緊后任務(wù),使用有向圖表示任務(wù)的執(zhí)行序列,則圖1 為可行解,而圖2 為非可行解。

圖1 滿足時序約束的可行解有向圖Fig.1 Directed graph of feasible solutions satisfying temporal constraints

圖2 違反時序約束的非可行解有向圖Fig.2 Directed graph of infeasible solutions violating temporal constraints

6) 使能約束

如果任務(wù)i不完成,則任務(wù)j無法完成,即任務(wù)j的完成依賴于任務(wù)i的實現(xiàn),表示任務(wù)i對任務(wù)j具有使能約束,記為Enable(i,j),對任務(wù)j具有使能約束的任務(wù)集合記為Sena(j)。使能約束與時序約束相似,但比時序約束的要求寬松。例如,假設(shè)共7 個待執(zhí)行的任務(wù),其中任務(wù)1 對任務(wù)4 具有使能約束,任務(wù)4 對任務(wù)7 具有使能約束,則圖1和圖2 均為滿足使能約束的可行解,可見只要目標任務(wù)在其使能任務(wù)之后完成即符合要求。

7) 航程約束

對任意UUVi∈V,執(zhí)行任務(wù)的總航程不能超過其最大航程。

1.4 目標函數(shù)

多UUV 協(xié)同偵察任務(wù)分配的目的是將任務(wù)分配給具體的UUV 執(zhí)行,保證每個任務(wù)只分配給一個UUV,為了使多UUV 系統(tǒng)的整體偵察效能最佳,需要滿足以下4 個目標。

1) 任務(wù)收益最大化

各UUV 完成偵察任務(wù)后,整體收益(Reward)為最大,即

式中:Si為分配給UUVi的任務(wù)子集;Reward(Si)為UUVi完成任務(wù)集Si所得的收益。

2) 任務(wù)代價最小化

各UUV 完成偵察任務(wù)后,整體代價(Cost)為最小,即

式中,Cost(Si) 為 UUVi完成任務(wù)集Si所付出的代價,此處代價是主要指航行距離。

3) 任務(wù)完成時間最小化

各UUV 協(xié)同完成偵察任務(wù)的時間(Time)為最小,即讓各UUV 完成任務(wù)的最長時間最小化,即

式中,Time(Si)為UUVi完成任務(wù)集Si所花費的時間。

4) 任務(wù)負載均衡化

各UUV 的任務(wù)負載(Load)趨于均衡,文中用各UUV 任務(wù)分配數(shù)的標準差表征任務(wù)負載

式中,|Si|為分配給UUVi的任務(wù)數(shù)。

這是一個多目標優(yōu)化問題,需要根據(jù)指揮人員的決策意圖確定各個指標的相對權(quán)重,通過加權(quán)求和轉(zhuǎn)化為單目標優(yōu)化問題。綜合考慮上述優(yōu)化目標,將多UUV 系統(tǒng)的整體效能定義為

式中,wi為大于等于0 的實數(shù),表示第i項優(yōu)化目標的權(quán)重,i=1,2,3,4。

1.5 任務(wù)分配模型

綜上可得,多UUV 協(xié)同偵察的任務(wù)分配方案需滿足式(7)～式(13)的約束,使-U最小化,從而求得多UUV 協(xié)同偵察任務(wù)分配方案。

偵察次數(shù)約束

重返基地約束

式中,0 代表UUV 的出發(fā)基地。

任務(wù)時間約束

任務(wù)載荷約束

任務(wù)使能約束

任務(wù)時序約束

最大航程約束

通過求解min -U可確定各UUV 的偵察任務(wù)序列

式中,ni為UUVi需要執(zhí)行的任務(wù)個數(shù)。

2 基于多種群遺傳算法的任務(wù)分配方法

基于“不把雞蛋放在同一籃子”的集成學習思想[10],選擇多種群協(xié)同進化遺傳算法求解多UUV協(xié)同偵察任務(wù)分配問題。通過種群遷移,使得種群間能夠共享優(yōu)秀基因,實現(xiàn)高質(zhì)量自進化;借助移民算子協(xié)同進化,促進了種群間的信息交換,達到協(xié)同進化目的;通過精英保留操作保存各種群每個進化代中的最優(yōu)個體,并作為判斷算法收斂的依據(jù),提高全局收斂能力;通過“人機融合”提升初代種群質(zhì)量,加速算法收斂;引入“遺忘策略”彌補可能出現(xiàn)的進化不徹底問題。

2.1 編碼策略

常用的遺傳編碼策略有格雷碼、實整數(shù)編碼、排列編碼等,文中采用排列編碼。一個種群由多條染色體構(gòu)成,可用二維矩陣表示

式中:Nind為種群的規(guī)模,即種群的個體數(shù);Lind為種群個體的染色體長度,Lind=Nm+Nv-1。

Chrom中每行對應一條染色體,個體染色體采用“排列編碼”方式,每條染色體對應1～Lind的一種全排列,第i條染色體對應如下行向量

式中,gi,j∈{1,2,3,···,Nm+Nv-1}且gi,j≠gi,j,j≠k。其中,1,2,···,Nm對應任務(wù)目標的編號;Nm+1,Nm+2,···,Nm+Nv-1為各分割點標記,用于分割染色體得到各UUV 的任務(wù)序列。

例如,當目標數(shù)Nm=13,UUV數(shù)目Nv=3 時,圖3 給出了一條染色體結(jié)構(gòu)實例。

圖3 UUV 協(xié)同任務(wù)分配方案Fig.3 Allocation scheme of collaborative task for UUV

如圖3 所示,該染色體對應一個任務(wù)分配方案:UUV 1 的任務(wù)執(zhí)行序列為0→2→5→7→12→0;UUV 2 的任務(wù)執(zhí)行序列為0→1→6→10→9→4→0;UUV 3 的任務(wù)執(zhí)行序列為0→8→13→11→3→0。0 代表UUV 各自的出發(fā)基地。

2.2 種群初始化

與經(jīng)典遺傳算法不同的是,種群初始化除了完成進化代數(shù)、種群規(guī)模、交叉概率及重組概率等超參數(shù)的設(shè)置外,還引入人類的先驗知識,構(gòu)造出2 條左右比較優(yōu)秀的染色體,作為協(xié)同進化的基準,提升初代種群的個體質(zhì)量,引導算法更快、更好地收斂。

2.3 適應度函數(shù)與約束處理

適應度函數(shù)用于評價個體的優(yōu)劣程度。多種群遺傳算法將個體適應度大小作為進化迭代的依據(jù),適應度越大,個體越接近最優(yōu)解。由于文中目標函數(shù)為極大型,因此取式(5)作為適應度函數(shù)。

常用的處理約束條件的方法有罰函數(shù)法和可行性法則[11]。其中,罰函數(shù)法的思想是通過在目標函數(shù)中引入懲罰項將約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題進行逼近求解;可行性法則是通過計算每個個體違反約束的程度,引導種群向滿足約束的方向進化。罰函數(shù)法雖然簡便,但對于多約束條件問題容易找不到可行解,因此文中選擇可行性法則。利用可行性法則進行處理,每個種群對應一個違反約束程度矩陣,記為

式中:Nind為種群的規(guī)模;N2為約束條件個數(shù),2.3節(jié)中的7 個約束,其中前2 個約束通過編碼策略可得到滿足,因此只需要考慮后5 個約束,即N2=5。

CV中每一行對應種群的一個個體,每一列對應一個約束,cvij∈{0,1}當取值為0 時表示滿足約束,反之表示違反約束。

2.4 局部遺傳算子

遺傳算子主要包括局部遺傳算子和全局遺傳算子。其中:局部遺傳算子是指子種群內(nèi)部染色體之間交互信息的遺傳操作;全局遺傳算子是指不同子種群之間信息交互的遺傳操作。局部遺傳算子主要包括選擇、交叉和變異等操作[11]。文中使用二進制錦標賽選擇算子。

2.5 全局遺傳算子

全局遺傳算子主要包括移民算子、精英保留算子[6]和遺忘策略。

1) 移民算子

移民算子是用源種群的最優(yōu)個體代替目標種群的最劣個體,通過種群間信息交換實現(xiàn)協(xié)同進化目的。

2) 精英保留算子

精英保留算子是選出各種群中的最優(yōu)個體,并將其放入精英種群加以保存,保證各種群的最優(yōu)個體不被破壞。

同時,精英種群與最大進化代數(shù)一起作為判斷算法終止的依據(jù)。設(shè)置進化停滯判斷閾值TrappedValue、進化停滯計數(shù)器最大上限值MaxTrappedCount 和最大進化代數(shù)MaxGen。當相鄰兩代精英個體的適應度之差小于TrappedValue,則判定進化陷入停滯;若連續(xù)MaxTrappedCount 代陷入進化停滯,則終止進化;在沒有因停滯而終止的情況下,當進化代數(shù)達到MaxGen 時則終止進化。

3) 遺忘策略

利用CV矩陣判斷種群中是否有滿足約束條件的個體,當沒有或僅有極少數(shù)個體滿足約束條件時,說明此次進化沒有達到預期效果。針對這種情況,當某一代的滿足約束個體少于MinNum時,進化記錄器將不對這一代種群進行記錄,同時進化代數(shù)-1,這意味著后面需要多進化一代作為補償,從而使優(yōu)化結(jié)果更加充分。MinNum 為超參數(shù),文中取 M inNum=1。

2.6 多種群遺傳算法流程

綜合種群初始化、個體評價、局部遺傳算子和全局遺傳算子等操作,可得多種群遺傳算法的執(zhí)行流程如圖4 所示。

圖4 多種群遺傳算法流程圖Fig.4 Flow chart of multi-population genetic algorithm

首先,進行多種群進化參數(shù)的初始化,主要包括各種群的規(guī)模、交叉概率、變異概率以及與終止進化相關(guān)的判斷閾值等參數(shù);然后,各個種群獨立進行選擇、重組、變異,得到各種群的子代,并將父代和子代個體合并;隨后,對所有種群的所有個體進行統(tǒng)一的適應度評價,并完成移民、約束條件判斷、精英保留等全局操作;最后,若滿足停止條件則停止,否則繼續(xù)執(zhí)行。

3 仿真實驗

3.1 想定設(shè)計

假設(shè)共有4 個可用的UUV 和15 個待偵察的目標,隨機分布在50 n mile × 50 n mile 的正方形任務(wù)海域里,以正方形的中心為原點構(gòu)建直角坐標系,UUV 和目標位置可用橫縱坐標表示,如圖5 所示。

圖5 目標和UUV 初始態(tài)勢分布圖Fig.5 Initial distribution of targets and UUVs

1) 任務(wù)載荷約束

共有4 種任務(wù)載荷,其中UUV 2、UUV 3 和UUV 4 均搭載了4 種載荷,UUV 1 搭載了除載荷2 之外的另外3 種載荷。15 個偵察目標對任務(wù)載荷的需求如圖6 所示。

圖6 偵察目標對載荷種類需求曲線Fig.6 Demand curve of targets to load types

由圖6 可見,目標10 和目標14 需要第2 種任務(wù)載荷才能完成偵察,因此不能將目標10 和14 分配給UUV 1 執(zhí)行。

2) 任務(wù)時間約束

對7 號目標添加任務(wù)開始時間約束,規(guī)定對7 號目標的偵察必須在90～150 min 之間開始。

3) 任務(wù)時序約束

對任務(wù)2、任務(wù)5 和任務(wù)4 施加任務(wù)時序約束,將任務(wù)2 設(shè)置為任務(wù)5 的緊前任務(wù),將任務(wù)4 設(shè)置為任務(wù)5 的緊后任務(wù)。

4) 任務(wù)使能約束

對任務(wù)3 和任務(wù)6 施加使能約束,令任務(wù)6 對任務(wù)3 具有使能約束,即任務(wù)6 必須在任務(wù)3 完成后才能開始。

5) 最大航程約束、

設(shè)置4 個UUV 的最大航程均為120 n mile。

6) UUV 速度與任務(wù)收益矩陣

航速設(shè)置方面,2 號UUV 航速為8 kn,其余3 個UUV 的航速均為5 kn。任務(wù)收益矩陣如表1所示,表中:第i行第j列取值表示由UUVi偵察目標j可獲得的任務(wù)收益;×表示UUV 無法執(zhí)行對相應目標的偵察。

表1 任務(wù)收益矩陣Table 1 Task benefit matrix

3.2 算法參數(shù)設(shè)置

為了驗證多種群協(xié)同進化算法的可行性,將使用增強精英保留策略的單種群遺傳算法作為基線算法。軟件方面,使用python 開源進化算法工具箱Geatpy2[12]進行算法開發(fā);硬件配置為:Intel(R)_Core(TM)_i5-1035G1 CPU,主頻1.19 GHz,內(nèi)存8 GB。

1) 多種群協(xié)同進化算法主要參數(shù)設(shè)置

取最大進化代數(shù)MaxGen=200;進化停滯判斷閾值TrappedValue=10-8;進化停滯計數(shù)器最大上限值MaxTrappedCoun=100;種群數(shù)量為4,各種群的染色體數(shù)量均為150,各種群的交叉概率分別為0.6,0.7,0.8 和0.9,各種群的變異概率分別為0.05,0.1,0.15 和0.2。

另外,利用人類經(jīng)驗構(gòu)造滿足部分約束的染色體引導種群進化。對于任務(wù)載荷約束、時序約束、使能約束這類定性約束直觀上很容易判斷,同時結(jié)合目標在圖上的分布態(tài)勢,構(gòu)造3 條初始化染色體分別為:[7,3,6,16,2,5,4,13,17,1,10,8,18,12,9,11,15,14];[2,5,4,16,7,3,12,6,17,10,13,8,18,9,15,14,1,11];[3,7,6,16,2,5,4,11,17,14,12,9,15,13,18,1,10,8]。上述染色體并不是最優(yōu)的,甚至可能違反部分約束,但它們均滿足任務(wù)載荷約束、時序約束和使能約束,以它們做引導可以提高初代種群質(zhì)量。

2) 單種群遺傳算法主要參數(shù)設(shè)置

單種群遺傳算法最大進化代數(shù)為200;染色體數(shù)量為600;交叉概率為0.7;變異概率為0.1;并采用與多種群協(xié)同進化算法相同的初始化和遺忘策略設(shè)置。

3.3 實驗結(jié)果

1) 多種群協(xié)同進化算法實驗結(jié)果

當式(5)中4 個目標函數(shù)的權(quán)重均為1 時,多種群協(xié)同進化算法的任務(wù)分配結(jié)果如圖7 所示,UUV 1 的任務(wù)執(zhí)行序列為0→7→3→13→15→0;UUV 2 的任務(wù)執(zhí)行序列為0→11→2→5→4→0;UUV 3 的任務(wù)執(zhí)行序列為0→14→6→9→12→0;UUV 4 的任務(wù)執(zhí)行序列為0→1→10→8→0。

圖7 多種群協(xié)同進化算法任務(wù)分配結(jié)果示意圖Fig.7 Task assignment results of multi-population coevolution algorithm

該任務(wù)分配方案中,各UUV 的任務(wù)收益、航行距離、任務(wù)完成時間(考慮返程)和任務(wù)個數(shù)等信息如表2 所示。

表2 多種群協(xié)同進化算法各UUV 任務(wù)信息表Table 2 Information table of UUV tasks for multiple population coevolution algorithm

由圖7 和表2 可知,優(yōu)化所得的任務(wù)分配方案中,UUV 的任務(wù)負載較為均衡,航行軌跡沒有往復,符合節(jié)省能源的要求,經(jīng)驗證該方案滿足所有約束條件。另外,由于任務(wù)2、5、4 空間距離較遠并存在時序約束,優(yōu)化結(jié)果將它們分配給航速最快的2 號UUV 執(zhí)行,在滿足約束的同時可以兼顧任務(wù)完成時間,凸顯了算法的優(yōu)勢。

優(yōu)化過程運行到123 代時算法提前終止,用時29.92 s,最優(yōu)目標函數(shù)值為2467.35。

2) 隨機初始化多種群實驗結(jié)果

采用隨機初始化方式生成初代種群時,多種群協(xié)同進化算法的任務(wù)分配結(jié)果如圖8 所示,UUV 1 的任務(wù)執(zhí)行序列為0→7→3→8→0;UUV 2 的任務(wù)執(zhí)行序列為0→2→5→4→15→0;UUV 3 的任務(wù)執(zhí)行序列為0→12→9→6→10→0;UUV 4 的任務(wù)執(zhí)行序列為0→1→10→14→13→0。

圖8 隨機初始化多種群協(xié)同進化算法實驗結(jié)果示意圖Fig.8 Experimental results of multi-population coevolution algorithm with random initialization

該任務(wù)分配方案對應的任務(wù)信息如表3 所示。

表3 隨機初始化多種群協(xié)同進化算法信息表Table 3 Information table for multi-population coevolution algorithm with random initialization

優(yōu)化過程共運行167 代,用時32.61 s,最優(yōu)目標函數(shù)值為2755.98。

3) 未設(shè)置遺忘策略多種群實驗結(jié)果

不使用遺忘策略時,多種群協(xié)同進化算法的任務(wù)分配結(jié)果如圖9 所示,UUV 1 的任務(wù)執(zhí)行序列為0→7→3→8→0;UUV2的任務(wù)執(zhí)行序列為0→2→5→4→15→0;UUV3的任務(wù)執(zhí)行序列為0→14→9→6→11→0;UUV 4 的任務(wù)執(zhí)行序列為0→1→10→12→13→0。

圖9 無遺忘策略多種群協(xié)同進化算法實驗結(jié)果示意圖Fig.9 Experimental results of multi-population coevolution algorithm without forgetting strategy

該任務(wù)分配方案對應的任務(wù)信息如表4 所示。

表4 無遺忘策略多種群協(xié)同進化算法信息表Table 4 Information table for multi-population coevolution algorithm without forgetting strategy

優(yōu)化過程共運行200 代,用時36.65 s,最優(yōu)目標函數(shù)值為2717.77。

4) 單種群遺傳算法實驗結(jié)果

當式(5)中4 個目標函數(shù)的權(quán)重均為1 時,單種群遺傳算法的任務(wù)分配結(jié)果如圖10 所示,UUV 1 的任務(wù)執(zhí)行序列為0→7→3→8→0;UUV 2 的任務(wù)執(zhí)行序列為0→2→5→4→15→0;UUV 3 的任務(wù)執(zhí)行序列為0→14→9→6→11→0;UUV 4 的任務(wù)執(zhí)行序列為0→1→10→12→13→0。

圖10 單種群遺傳算法任務(wù)分配結(jié)果示意圖Fig.10 Task assignment results of single population genetic algorithm

該任務(wù)分配方案對應的任務(wù)信息如表5 所示。

表5 單種群遺傳算法各UUV 任務(wù)信息表Table 5 Information table of UUV tasks for single population genetic algorithm

優(yōu)化過程共運行200 代,用時41.01 s,最優(yōu)目標函數(shù)值為2759.98。

5) 對比分析

對比表2 與表5 中的任務(wù)分配方案信息,多種群協(xié)同進化算法的尋優(yōu)結(jié)果除了在任務(wù)收益方面處于劣勢以外,在航向距離、任務(wù)完成時間以及最優(yōu)目標函數(shù)值等方面均占有優(yōu)勢,航向距離比單種群遺傳算法節(jié)省了36.35 n mile,任務(wù)完成時間節(jié)省279.29 min,所有UUV 的總航行時間節(jié)省662.53 min,最優(yōu)目標函數(shù)值改進292.63。另外,得益于并行計算和進化停滯判斷策略,多種群協(xié)同進化算法的耗時少11.09 s。

對比表2 與表3 中的任務(wù)分配方案信息,當引入人類先驗知識的多種群協(xié)同進化算法,除任務(wù)收益外,在航向距離和任務(wù)完成時間方面均占有優(yōu)勢,另外進化完成時間也減少約2.67 s。

對比表2 與表4 中的任務(wù)分配方案信息,設(shè)置遺忘策略多種群協(xié)同進化算法,在航向距離和任務(wù)完成時間方面均占有優(yōu)勢。另外,由于未設(shè)置遺忘策略,雖然進化200 代,但由于其中可能存在多代不含可行解的無效進化,因此并未實現(xiàn)完全進化。

綜上所述,通過多種群協(xié)同進化,借助并行化計算,可以在提高尋優(yōu)效率的基礎(chǔ)上,取得比單種群遺傳算法更好的尋優(yōu)結(jié)果。同時,引入人類先驗知識和遺忘策略,可以進一步加速收斂、促進進化。

另外,文中通過加權(quán)求和的方式將多目標優(yōu)化問題轉(zhuǎn)化為單目標優(yōu)化問題,這樣權(quán)重組合可以靈活滿足不同任務(wù)需求,使用偏好的方案優(yōu)選。例如,將第3 個目標函數(shù)權(quán)重設(shè)置為1,其余3 個目標函數(shù)權(quán)重設(shè)置為0,則對應任務(wù)完成時間最小化這一單目標優(yōu)化問題。利用多種群協(xié)同進化算法優(yōu)化所得的任務(wù)分配方案如圖11 所示。

圖11 多種群協(xié)同進化算法任務(wù)分配結(jié)果示意圖Fig.11 Task assignment results of multi-population coevolution algorithm

4 結(jié)束語

為了提升多目標、多基地、多約束條件下多UUV 協(xié)同偵察任務(wù)分配的方案質(zhì)量,針對經(jīng)典單種群遺傳算法過早收斂、效率不高等問題,提出一種人機融合的多種群協(xié)同進化算法。一方面,引入人類直覺、經(jīng)驗構(gòu)造較優(yōu)的初始染色體,作為啟發(fā)信息引導種群盡快找到全局最優(yōu)解;另外,利用多種群并行、協(xié)同搜索,提升算法魯棒性和全局尋優(yōu)能力。在典型場景下進行仿真對比實驗,實驗結(jié)果表明:多種群協(xié)同進化算法能夠提升協(xié)同任務(wù)分配的魯棒性,能夠提升任務(wù)分配方案的質(zhì)量。后續(xù)將在此基礎(chǔ)上,研究任務(wù)變更、UUV 個體故障等突發(fā)情況下的動態(tài)協(xié)同任務(wù)分配。