張森悅, 隋學(xué)梅, 李一波

(1. 沈陽航空航天大學(xué) 人工智能學(xué)院, 沈陽 110136; 2. 沈陽航空航天大學(xué) 自動化學(xué)院, 沈陽 110136)

隨著無人機(jī)(unmanned aerial vehicle, UAV)發(fā)展的日漸完善, 其在相關(guān)領(lǐng)域中的應(yīng)用越來越廣泛. 為彌補(bǔ)單一無人機(jī)作戰(zhàn)缺陷, 多無人機(jī)協(xié)同系統(tǒng)已逐漸成為主流. 針對多無人機(jī)協(xié)同任務(wù)分配問題, 目前已有許多研究成果, 如混合整數(shù)線性規(guī)劃[1]、 多旅行商[2]、 多UAV協(xié)同任務(wù)分配(cooperative multiple task assignment problem, CMTAP)[3]等模型, 其中CMTAP模型適用于求解UAV執(zhí)行有序任務(wù)的問題. 目前任務(wù)分配算法主要分為兩類： 進(jìn)化和群智能算法. 遺傳算法(genetic algorithm, GA)[3-4]是最經(jīng)典的進(jìn)化算法, 其通過交叉和變異算子求解問題[5-6], 但算法易陷入早熟. 群智能算法是模仿生物的行為特點(diǎn)而產(chǎn)生的啟發(fā)式尋優(yōu)算法, 其中較經(jīng)典的有蟻群算法[7]、 人工蜂群算法[8]、 粒子群優(yōu)化算法(particle swarm optimization, PSO)[9]等. 但這些算法也有易陷入局部最優(yōu)解、 初期收斂速度慢、 運(yùn)行時間長等缺點(diǎn). 近年來, 如灰狼優(yōu)化算法[10-12]、 蝗蟲優(yōu)化算法[13-14]、 鯨魚算法[15-16]等新興仿生算法相繼被提出, 但研究表明, 這些算法仍存在種群多樣性差、 收斂精度低的問題.

Mirjalili等[17]根據(jù)樽海鞘種群在海洋內(nèi)集群覓食的行為特點(diǎn)提出了樽海鞘算法(salp swarm algorithm, SSA) , 該算法將樽海鞘鏈分為領(lǐng)導(dǎo)者和跟隨者, 領(lǐng)導(dǎo)者是整個鏈的頭部, 跟隨者是整個鏈的尾部. 領(lǐng)導(dǎo)者一直向食物方向移動, 跟隨者緊跟領(lǐng)導(dǎo)者. 模擬這種生物的捕食方式, 提出了樽海鞘算法解決尋優(yōu)問題, 并已成功應(yīng)用于各領(lǐng)域[18-20]. 經(jīng)典的SSA算法用于解決連續(xù)域的優(yōu)化問題, 但卻無法解決離散問題. Walaa等[21]提出了一種改進(jìn)的樽海鞘算法(modified salp swarm algorithm, MSSA), 將該算法應(yīng)用于解決任務(wù)分配問題, 并通過實驗驗證了該算法相對于其他算法具有明顯的優(yōu)勢. 與其他群智能算法類似, 樽海鞘算法也易陷入局部最優(yōu)解[22-23].

針對MSSA算法存在易陷入局部最優(yōu)的缺陷, 本文提出一種用于解決多無人機(jī)任務(wù)分配問題的自適應(yīng)樽海鞘算法(self-adaptive modified salp swarm algorithm, SA-MSSA). 該算法修改了樽海鞘領(lǐng)導(dǎo)者位置更新公式, 在其中考慮每一代的父代位置和食物源對子代位置更新的影響. 同時為提高算法前期的全局搜索能力, 在算法中考慮加入自適應(yīng)算子, 動態(tài)調(diào)整前后期每一代需要的領(lǐng)導(dǎo)者和跟隨者的比例. 仿真實驗結(jié)果表明, 本文算法具有脫離局部最優(yōu)的能力, 提升了收斂性能和求解速度, 適應(yīng)度也大幅度提高, 成功解決了多無人機(jī)的任務(wù)分配問題.

1 CMTAP模型建立

1.1 模型描述

假設(shè)共有m架無人機(jī)U={U1,U2,…,Um},n個作戰(zhàn)目標(biāo)T={T1,T2,…,Tn}, 每個目標(biāo)需要依次完成偵查、 攻擊和評估3個任務(wù),MT={Classify(C),Attack(A),Verify(V)}[24],NT為任務(wù)數(shù)量, 這里NT=3×n.一般情況下假設(shè)n≠m, 分配目的是通過合理安排, 使m架UAV以最小的代價完成NT個任務(wù).

1.2 約束條件

(1)

(2)

其中dij為優(yōu)勢概率.無人機(jī)i和目標(biāo)j的相對距離Dij表示為

(3)

無人機(jī)i和目標(biāo)j的相對速度Vij表示為

Vij=|Vicosθi+Vjcosθj|.

(4)

任務(wù)數(shù)量約束： 任務(wù)數(shù)量約束確保每個目標(biāo)的每個任務(wù)都被執(zhí)行, 可表示為

(5)

任務(wù)時序約束： 任務(wù)時序約束確保目標(biāo)j按照偵查、 攻擊、 評估的順序執(zhí)行, 可表示為

(6)

1.3 評價指標(biāo)

CMTAP模型的目標(biāo)函數(shù)是構(gòu)建執(zhí)行代價函數(shù)J1和時間代價函數(shù)J2, 執(zhí)行代價是無人機(jī)對目標(biāo)作戰(zhàn)時的損耗, 時間代價是完成所有任務(wù)所需的時間.

1.3.1 執(zhí)行代價

用J1表示無人機(jī)i執(zhí)行目標(biāo)j的任務(wù)k時的執(zhí)行代價, 可表示為

(7)

其中Wi表示損傷代價.

1.3.2 時間代價

用J2表示執(zhí)行任務(wù)結(jié)束的時間代價, 以執(zhí)行最后一個任務(wù)的無人機(jī)為整個團(tuán)隊的時間, 時間代價的單位為s, 可表示為

(8)

1.3.3 總體目標(biāo)函數(shù)

總體目標(biāo)函數(shù)可表示為

minJ=J1+J2,

(9)

服從于

(10)

總體目標(biāo)函數(shù)約束滿足式(1),(5)，(6),(10), 目標(biāo)函數(shù)表示執(zhí)行代價和時間代價最小, 約束條件(10)確保一個任務(wù)只由一架無人機(jī)完成.

2 算法設(shè)計

2.1 經(jīng)典樽海鞘算法

樽海鞘算法[17]是模擬海洋生物樽海鞘的種群移動規(guī)律提出的, 要將該算法用于CMTAP求解[25], 可將樽海鞘鏈中的一個樽海鞘視為一個求解方案, 食物源表示當(dāng)前最好的分配結(jié)果, 確定合適的編碼方法, 然后通過領(lǐng)導(dǎo)者與跟隨者位置更新等操作不斷生成新的種群, 直到滿足約束條件.

(11)

(12)

若食物源定義為Fj(j=1,2,…,N), 范圍的上下界分別為ubj和lbj,c1,c2和c3是影響位置更新的系數(shù), 則

c1=2exp{-(4l/L)2},

(13)

其中c2和c3為[-1,1]內(nèi)的隨機(jī)數(shù),l表示當(dāng)前迭代次數(shù),L表示最大迭代次數(shù).

樽海鞘算法尋優(yōu)是通過位置更新迭代完成的, 式(11)更新領(lǐng)導(dǎo)者的位置, 式(12)更新跟隨者的位置, 整體向最優(yōu)解(食物源)迭代.移動過程中, 領(lǐng)導(dǎo)者進(jìn)行全局探索, 而跟隨者則進(jìn)行局部探索, 直到終止.

2.2 自適應(yīng)樽海鞘算法

為提高多無人機(jī)任務(wù)分配的收斂速度并克服陷入局部最優(yōu)的問題, 本文將樽海鞘算法和自適應(yīng)算子相結(jié)合, 提出一種自適應(yīng)樽海鞘算法.

圖1 編碼方式Fig.1 Method of coding

2.2.1 種群初始化

SA-MSSA算法的種群采用實數(shù)編碼的方式[26], 編碼長度為任務(wù)數(shù)目n.假設(shè)系統(tǒng)中有4架無人機(jī)、 6個任務(wù), 則其中一種編碼方式如圖1所示.

2.2.2 位置更新

1) 領(lǐng)導(dǎo)者.在MSSA算法中, 領(lǐng)導(dǎo)者尋優(yōu)過程若一開始就向全局最優(yōu)移動, 則可能導(dǎo)致全局尋優(yōu)不全面, 也易陷入局部最優(yōu)和收斂速度低的問題[21]. 本文將領(lǐng)導(dǎo)者位置更新公式修改為

圖2 P⊕S示例Fig.2 Example of P⊕S

符號⊕的計算過程如圖2所示.例如：

符號?的計算過程如圖3所示, 具體流程如圖4所示, 其結(jié)果與優(yōu)勢概率有關(guān), 例如：

P1?P2=(SO1(2,3),SO2(3,3),SO3(5,1)).

圖3 P1?P2示意圖Fig.3 Schematic diagram of P1?P2

圖4 P1?P2流程Fig.4 Flow chart of P1?P2

2) 跟隨者.跟隨者位置按下式進(jìn)行更新:

(16)

2.2.3 自適應(yīng)算子

MSSA算法迭代時, 種群的領(lǐng)導(dǎo)者固定為1, 其余為跟隨者[21], 會導(dǎo)致算法前期全局搜索能力不足, 后期局部搜索緩慢, 從而降低算法的整體精度. 針對此問題, SA-MSSA算法引入了自適應(yīng)算子[27], 使領(lǐng)導(dǎo)者和跟隨者的比例隨迭代過程變化, 前期領(lǐng)導(dǎo)者較多, 后期跟隨者較多, 自適應(yīng)算子中領(lǐng)導(dǎo)者的百分比r根據(jù)

(17)

進(jìn)行計算, 跟隨者的百分比為1-r.其中:b為比例系數(shù), 避免兩者比例偏差過大,e為擾動因子, 經(jīng)過實驗,b=0.75,e=0.2較合適; rand函數(shù)為(0,1)之間的隨機(jī)數(shù), 結(jié)合e對r進(jìn)行擾動; it為算法當(dāng)前迭代次數(shù);M為算法最大迭代次數(shù).

3 算法流程

本文提出的自適應(yīng)樽海鞘算法處理流程如圖5所示.

圖5 SA-MSSA算法流程Fig.5 Flow chart of SA-MSSA algorithm

算法描述如下, 其中UAV數(shù)目設(shè)為m, 目標(biāo)數(shù)目設(shè)為n, 迭代次數(shù)設(shè)為M, 種群數(shù)量設(shè)為N.

算法1SA-MSSA.

輸入： UAV數(shù)目m, 目標(biāo)數(shù)目n, 迭代次數(shù)M, 種群數(shù)量N;

輸出： 最佳任務(wù)分配結(jié)果, 最優(yōu)適應(yīng)度(食物源F);

步驟1) it=0;

步驟2) 初始化種群和食物源的位置(無限大), 根據(jù)總體目標(biāo)函數(shù)評估每個樽海鞘的適應(yīng)度；

循環(huán):

步驟3) 根據(jù)自適應(yīng)算子公式確定領(lǐng)導(dǎo)者和跟隨者數(shù)量;

步驟4) 根據(jù)跟隨者和領(lǐng)導(dǎo)者的位置更新公式分別修改子代每個樽海鞘的位置, 生成新的樽海鞘種群;

步驟5) 重新評估目前種群的適應(yīng)度, 更新食物源F和最佳任務(wù)分配結(jié)果;

步驟6) it=it+1;

直到it>M;

輸出： 最佳任務(wù)分配結(jié)果和食物源F;

算法結(jié)束.

4 仿真與分析

實驗所用計算機(jī)硬件配置為Intel Core(TM) i7-8750H CPU, NVDIA GeForce GTX 1060顯卡和16 GB內(nèi)存, 所有算法均在MATLAB R2018a平臺編譯運(yùn)行. 為驗證算法的性能, 本文設(shè)計3種不同場景, 分別為： 5架UAV和3個目標(biāo), 12架UAV和5個目標(biāo), 15架UAV和10個目標(biāo). 首先對本文SA-MSSA算法的性能進(jìn)行分析, 然后用SA-MSSA算法、 MSSA算法、 PSO算法和GA算法分別求解3種場景下的分配問題, 將不同算法的實驗結(jié)果進(jìn)行分析對比. 各算法的參數(shù)設(shè)置列于表1, 其中Pc和Pm分別為GA算法的交叉和變異概率,c11和c12為PSO算法的學(xué)習(xí)因子[28-29].

表1 仿真參數(shù)設(shè)置

4.1 分配結(jié)果分析

UAV的作戰(zhàn)區(qū)域為5 km×5 km[30], 5架UAV和3個目標(biāo), 不同屬性信息分別列于表2和表3, 其中x和y分別表示無人機(jī)和目標(biāo)的初始位置,θ為離軸角,V為速度,W為無人機(jī)的價值. 表4為無人機(jī)優(yōu)勢概率統(tǒng)計結(jié)果.

表2 UAV屬性信息

表3 目標(biāo)屬性信息

表4 無人機(jī)的優(yōu)勢概率

針對上述數(shù)據(jù), 采用基于SA-MSSA的UAV任務(wù)分配算法, 考慮實際的執(zhí)行順序列出任務(wù)分配結(jié)果如圖6所示, 任務(wù)執(zhí)行情況如圖7所示. 由圖6可見, 每個目標(biāo)的3個任務(wù)都被執(zhí)行. 由圖7可見, 每架消防無人機(jī)都至少執(zhí)行一個任務(wù), 圖中直線表示無人機(jī)執(zhí)行任務(wù)的軌跡. 因此, 在該仿真場景下, SA-MSSA算法得到的任務(wù)分配結(jié)果可行. 最終的任務(wù)分配方案為UAV1：T1(C); UAV2：T2(V); UAV3：T1(A)→T3(V); UAV4：T3(C,A)→T1(V); UAV5：T2(C,A).

圖6 任務(wù)分配結(jié)果Fig.6 Result of task assignment

圖7 任務(wù)執(zhí)行情況示意圖Fig.7 Schematic diagram of task execution

4.2 算法性能分析

為驗證SA-MSSA算法求解CMTAP問題的能力, 本文將上述4種算法分別用于求解3種不同規(guī)模下的CMTAP問題, 所得結(jié)果列于表5. 其中, 規(guī)模S0503表示5架無人機(jī)和3個目標(biāo). 每種算法均進(jìn)行10次實驗, 并分別統(tǒng)計兩種代價的3項指標(biāo)： 最小值、 最大值和平均值.

表5 不同規(guī)模下4種算法的代價

由表5可見, SA-MSSA算法均獲得了較好的結(jié)果, 而且隨著規(guī)模變大, 算法的代價值也逐漸提高. 以S0503規(guī)模下4種算法的平均值為例, SA-MSSA算法的執(zhí)行代價相比于GA提高了10.02%, 與PSO算法相比提高了3.8%, 與MSSA算法幾乎一致； SA-MSSA算法時間代價相比于GA提高了96.58%, 與PSO算法相比提高了48.5%, 與MSSA算法相比提高了28.4%. 4種算法的適應(yīng)度值列于表6.

表6 不同規(guī)模下4種算法的適應(yīng)度值

續(xù)表6

由表6可見, 本文SA-MSSA算法在不同規(guī)模下都取得了最好的解, 適應(yīng)度值最好. 以S0503規(guī)模下4種算法的適應(yīng)度平均值為例, 本文算法相比于GA提高了93.2%, 與PSO算法相比提高了32.29%, 比MSSA算法提高了16.03%.

圖8 不同規(guī)模下3種算法的平均適應(yīng)度值變化曲線Fig.8 Change curves of average fitness values of three algorithms under different scales

實驗結(jié)果表明, 當(dāng)目標(biāo)數(shù)量增加時, SA-MSSA算法獲得的適應(yīng)度值相對于其他算法的優(yōu)勢更明顯, 代價更小. 這是因為當(dāng)規(guī)模較小時, 解的空間分布集中, 表現(xiàn)出較大的分散性, 導(dǎo)致時間代價的收斂數(shù)值較大； 而求解更大規(guī)模時, SA-MSSA算法能增強(qiáng)種群在迭代后期的多樣性, 增加可行解空間分布的多樣性, 提高整個算法跳出局部最優(yōu)的能力, 以更小的代價完成任務(wù).

本文將PSO算法、 MSSA算法及SA-MSSA算法的平均適應(yīng)度值進(jìn)行對比, 結(jié)果如圖8所示. 由圖8可見, 隨著問題規(guī)模的不斷增大, 3種算法間的差異顯著變大, SA-MSSA算法的優(yōu)勢更明顯. 上述實驗結(jié)果證明, 針對多無人機(jī)任務(wù)分配問題, 相對于GA算法、 PSO算法和經(jīng)典樽海鞘算法, 本文提出的自適應(yīng)樽海鞘算法的代價更小, 適應(yīng)度更好.

4.3 算法收斂性分析

為驗證SA-MSSA算法的收斂性, 使用4種算法在相同的仿真環(huán)境下迭代50次, 收斂曲線如圖9所示(GA算法數(shù)值過大, 故圖中未包含).

圖9 不同規(guī)模下3種算法的收斂曲線對比Fig.9 Comparison of convergence curves of three algorithms under different scales

由圖9可見, 無論何種規(guī)模下, SA-MSSA算法相比于PSO算法和MSSA算法代價均更小, 算法最后的收斂值更小, 收斂速度更快. 以S0503規(guī)模為例, 由圖9(A)中可見, 相比PSO算法在23次迭代處收斂和MSSA算法在15次迭代處收斂, SA-MSSA算法提前到了在7次迭代處收斂.

綜上所述, 針對多無人機(jī)任務(wù)分配問題, 本文基于樽海鞘算法, 提出了一種自適應(yīng)樽海鞘算法. 首先, 修改了領(lǐng)導(dǎo)者位置更新公式, 使領(lǐng)導(dǎo)者受上一代領(lǐng)導(dǎo)者和最優(yōu)解的影響; 然后, 在種群迭代更新過程中加入自適應(yīng)算子, 動態(tài)調(diào)整領(lǐng)導(dǎo)者和跟隨者的比例, 以提高前期的全局搜索和后期跳出局部極值的能力； 最后, 通過對4種算法的分配結(jié)果、 適應(yīng)度及收斂曲線進(jìn)行對比分析, 驗證了本文算法在不同規(guī)模的無人機(jī)任務(wù)分配時均獲得了更好的結(jié)果.