基于改進麻雀搜索算法的多無人機任務分配

劉夏婷，傅 強

（中國民用航空飛行學院飛行技術學院，廣漢 618307）

0 引言

無人機（unmanned aerial vehicle，UAV）擁有成本低、自主程度高、機動靈活等優點，被廣泛應用于服務、農業、軍事等領域［1-3］。在復雜環境下為了完成多樣變化的無人機任務，使用攜帶不同功能的集群無人機執行任務已成為重要方式。對于多無人機任務分配問題，構建的問題模型和使用的智能算法是至關重要的。

文獻［4］提出一種混合粒子群算法，創新性地提出對多攻擊任務死鎖檢測和修復算法，對任務重分配使用匹配策略思想，可有效解決協同攻擊任務重分配問題。文獻［5］對多無人機的偵察任務分配問題進行研究，使用蟻群算法模擬多種不同載荷情況，其求解的分配方案更加貼合實際情況。文獻［6］使用量子遺傳算法進行全局任務分配，同時加入混合蛙跳優化策略，跳出局部極值并減少了算法的整體迭代次數。文獻［7］使用改進蟻群算法對任務分配和路徑規劃聯合優化，新增加無人機編隊數量約束，并引入信息素更新以保證資源的充分利用。文獻［8］提出基于并行機制的多目標灰狼算法，在算法中引入分層編碼和檔案室共享策略，可有效提高求解速度和收斂能力。文獻［9］在基礎的布谷鳥算法中通過調整自適應步長以及加入模擬退火算法，使算法不容易陷入局部最優。

針對多無人機任務分配問題，本文提出基于Logistics混沌的多目標麻雀搜索算法，構建任務分配目標函數，對麻雀搜索算法進行改進并優化，可高效快速地求解任務分配目標函數。

1 模型建立

1.1 問題描述

本文主要研究在模擬的二維戰場空間內，我方多無人機對地面目標完成評估、偵察、攻擊三項任務。無人機均從同一確定基地起飛。假設無人機數量NV，其集合為V={V1,V2,V3,…,VNV}，移動的空中目標數量為NT， 集合為T={T1,T1,T3,…,TNT}，每個目標需完成三項任務，即評估、偵察和攻擊，其任務數量為NU，任務集合為U={reconnoitre,attack,estimate} ，NU=3。在模擬的二維平面內，無人機i對應的位置為（xi,y）i，目標j對應的位置為（xj,y）j。其相對距離可表示為分別考慮無人機執行任務時的威脅代價，執行偵察、評估、攻擊任務帶來的收益，完成任務的航行距離，以這三個評價指標為基礎綜合建立多無人機任務分配目標函數。

1.2 評價指標

1.2.1 威脅代價

威脅代價是指無人機在執行任務時，任務目標對無人機造成無人機損毀付出的代價。假設無人機i的價值為valuei，目標j對無人機i的威脅概率為Sij，即無人機執行任務后的生存概率為(1 -Sij)。經過所有目標后，無人機產生的執行代價計算如下：

1.2.2 任務收益

當無人機依次完成偵察、攻擊、評估三項任務時，根據無人機的偵察能力指數、對目標的毀傷概率、評估能力分別得到收益P1ij、P2ij、P3ij。

因此，無人機完成任務的總收益為

1.2.3 航行代價

航程代價是指無人機到達執行任務位置時所需的距離代價，本文采用直線度量。

Dis（Tij）指無人機i到目標j的距離，dmax指無人機執行偵察任務的最遠距離。

1.3 總收益適應度目標函數

式（8）中Wi為權重系數，且W1+W2+W3= 1。

1.4 約束條件

1.4.1 任務時序約束

1.4.2 無人機執行任務約束

（1）目標的三種任務可被不同無人機執行，且一架無人機只能執行該點的一種任務。

（2）所有任務均被完成。

2 改進多目標麻雀搜索算法

2.1 經典麻雀搜索算法

在麻雀搜索算法中，有發現者、跟隨者和警戒者三類。警戒者所占種群比例10%～20%，發現者和跟隨者所占比例是不確定的。其中發現者的主要職責是尋找食物所在的方向和位置，跟隨者是跟隨發現者進行覓食，警戒者負責對覓食區域的監視。為獲得生存的資源，該算法通過在尋找食物過程中不斷更新三者的位置完成。發現者的位置更新方式如下：

其中，表示在第t代中第i只麻雀在第j維的位置，R2表示報警值。

跟隨者的位置更新：

其中，表示第t代適應度最差的個體位置，表示第t+1 代中適應度最佳的個體位置。A+=AT(AAT)-1。

警戒者位置更新方式如下：

其中，表示第t代中全局最優位置，β為控制步長。fi表示當前個體的適應度值，fg和fw表示目前全局最優和最差個體的適應度值。

2.2 改進多目標麻雀搜索算法

2.2.1 利用Logistic映射初始化種群

麻雀搜索算法尋優能力較好，但其結果具有較大的隨機性，且初始化種群麻雀個體的位置會影響算法結果的穩定性，因此在初始化種群階段利用Logistic 映射，在初期階段進行個體分類，隨著迭代次數變化提高了種群的多樣性，在一定程度上減小了算法陷入局部最優的概率。其數學表達公式如下：

其中，μ為Logistic 參數。為了保證映射得到的Xn始終位于［0,1］內，則μ∈［0,4］。x（t）為在t時刻種群占最大可能種群規模的比例。

2.2.2 利用Pareto最優解求解多目標優化問題

利用Pareto 多目標優化問題的主要思想是首先對不同目標優先級或權重進行明確，然后試圖找到優化條件在不同權重下各為最優解的一組解，然后根據決策者的偏好或應用場景決定選擇哪個解。

多目標優化定義如下：

其中，u∈Ω 為決策向量，Ω 為決策空間；y∈Y，為目標向量，Y為目標函數空間。

3 算法流程

具體算法流程如下：

步驟一：利用Logistic映射策略初始化種群、迭代次數，以及初始化捕食者和加入者比例；

步驟二：計算適應度值，并對結果排序；

步驟三：麻雀更新捕食者位置；

步驟四：麻雀更新加入者位置；

步驟五：麻雀更新警戒者位置；

步驟六：計算適應度值并更新麻雀位置；

步驟七：是否滿足停止條件，若滿足條件則結束，輸出結果；否則，重復執行步驟二至步驟六。

4 仿真實驗

4.1 實驗參數設置

本文對實驗場景構想如下：在多無人機任務分配過程中不考慮能源消耗、通信約束以及載荷約束。為方便計算，將無人機和目標均視為具有速度、角度、價值、概率等屬性的質點。仿真環境的區域設置為5 km×5 km的平面。無人機的初始位置從固定點（1.1）開始。

假設現有7 架無人機對4 個目標進行偵察、評估、攻擊任務，無人機的基本參數和目標參數及毀傷概率分別見表1、表2和表3。

表1 無人機的基本參數

表2 目標參數設置

經多次實驗數據對比，取適應度函數W1= 0.3,W2= 0.3,W3= 0.4。

4.2 實驗結果與分析

4.2.1 結果分析

無人機任務目標分配結果見表4所示。

從任務分配結果可以看出，無人機V1完成了T4與T2的評估任務，無人機V2完成了T2的偵察任務與T4的攻擊任務，無人機V3完成了T1的偵察任務，無人機V4完成了T2的攻擊任務與T3的評估任務，無人機V5完成了T1與T3的偵察任務，無人機V6完成了T1的評估任務與T3的攻擊任務，無人機V7完成了T4的偵察任務。每個無人機的任務均為唯一，且每個目標的偵察、攻擊、評估任務均被完成。

總收益適應度目標函數結果如圖1所示。

圖1 算法適應度曲線

由圖1 可知，改進麻雀搜索算法利用Pareto最優解求解多目標優化問題，獲得了更快的收斂速度，利用Logistic 映射在初期階段進行個體分類，隨著迭代次數變化的同時提高了種群的多樣性，一定程度上減小了算法陷入局部最優的概率。

4.2.2 不同場景下實驗結果及分析

為驗證算法的有效性，使用ISSA、SSA 和GA 三種算法求解不同場景下的多無人機任務分配問題。三種算法的最大迭代次數均設置為100，其他參數的設置均一樣。其目標迭代收斂曲線如圖2、圖3和圖4所示。

圖2 10無人機對5個目標的收斂曲線

圖3 13無人機對6個目標的收斂曲線

圖4 16無人機對7個目標的收斂曲線

從總體上看，三種算法迭代收斂的目標函數最終都會趨于一個穩定值。ISSA 算法的收斂值均小于其他兩種算法。從圖2可以看出，在目標數量較少的情況下，相比其他兩種算法，隨迭代次數增加，ISSA 算法可以在較短時間內經過較少的迭代次數達到穩定的目標函數值。在圖3 和圖4 中，當目標數量增加時，迭代初期三種算法目標函數值較為不穩定，上下波動，優化算法的搜索操作呈現不穩定的狀態；在迭代后期，各算法的搜索能力較為平穩，目標函數值也趨于穩定。因此，與GA 與SSA 相比，ISSA具有良好的收斂性能。

5 結語

本文以麻雀搜索算法為基礎，加入了Logistic映射策略來建立無人機任務分配模型，利用Pareto 多目標優化問題的主要思想對目標的威脅代價、航程代價、任務收益進行權重分配，多次試驗找到最優解。仿真結果表明，本文研究的模型合理有效，且應用在不同的場景下也有較大優勢，通過算法的改進不僅加強了種群多樣性，同時提高了算法的收斂精度以及搜索效率。