基于自適應樽海鞘算法的多無人機任務分配

張森悅, 隋學梅, 李一波

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

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

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

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

1 CMTAP模型建立

1.1 模型描述

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

1.2 約束條件

(1)

(2)

其中dij為優勢概率.無人機i和目標j的相對距離Dij表示為

(3)

無人機i和目標j的相對速度Vij表示為

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

(4)

任務數量約束： 任務數量約束確保每個目標的每個任務都被執行, 可表示為

(5)

任務時序約束： 任務時序約束確保目標j按照偵查、 攻擊、 評估的順序執行, 可表示為

(6)

1.3 評價指標

CMTAP模型的目標函數是構建執行代價函數J1和時間代價函數J2, 執行代價是無人機對目標作戰時的損耗, 時間代價是完成所有任務所需的時間.

1.3.1 執行代價

用J1表示無人機i執行目標j的任務k時的執行代價, 可表示為

(7)

其中Wi表示損傷代價.

1.3.2 時間代價

用J2表示執行任務結束的時間代價, 以執行最后一個任務的無人機為整個團隊的時間, 時間代價的單位為s, 可表示為

(8)

1.3.3 總體目標函數

總體目標函數可表示為

minJ=J1+J2,

(9)

服從于

(10)

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

2 算法設計

2.1 經典樽海鞘算法

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

(11)

(12)

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

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

(13)

其中c2和c3為[-1,1]內的隨機數,l表示當前迭代次數,L表示最大迭代次數.

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

2.2 自適應樽海鞘算法

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

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

2.2.1 種群初始化

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

2.2.2 位置更新

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

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

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

符號?的計算過程如圖3所示, 具體流程如圖4所示, 其結果與優勢概率有關, 例如：

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) 跟隨者.跟隨者位置按下式進行更新:

(16)

2.2.3 自適應算子

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

(17)

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

3 算法流程

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

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

算法描述如下, 其中UAV數目設為m, 目標數目設為n, 迭代次數設為M, 種群數量設為N.

算法1SA-MSSA.

輸入： UAV數目m, 目標數目n, 迭代次數M, 種群數量N;

輸出： 最佳任務分配結果, 最優適應度(食物源F);

步驟1) it=0;

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

循環:

步驟3) 根據自適應算子公式確定領導者和跟隨者數量;

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

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

步驟6) it=it+1;

直到it>M;

輸出： 最佳任務分配結果和食物源F;

算法結束.

4 仿真與分析

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

表1 仿真參數設置

4.1 分配結果分析

UAV的作戰區域為5 km×5 km[30], 5架UAV和3個目標, 不同屬性信息分別列于表2和表3, 其中x和y分別表示無人機和目標的初始位置,θ為離軸角,V為速度,W為無人機的價值. 表4為無人機優勢概率統計結果.

表2 UAV屬性信息

表3 目標屬性信息

表4 無人機的優勢概率

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

圖6 任務分配結果Fig.6 Result of task assignment

圖7 任務執行情況示意圖Fig.7 Schematic diagram of task execution

4.2 算法性能分析

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

表5 不同規模下4種算法的代價

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

表6 不同規模下4種算法的適應度值

續表6

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

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

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

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

4.3 算法收斂性分析

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

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

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

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