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

劉夏婷，傅 強

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

0 引言

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

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

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

1 模型建立

1.1 問題描述

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

1.2 評價指標

1.2.1 威脅代價

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

1.2.2 任務收益

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

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

1.2.3 航行代價

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

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

1.3 總收益適應度目標函數(shù)

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

1.4 約束條件

1.4.1 任務時序約束

1.4.2 無人機執(zhí)行任務約束

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

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

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

2.1 經(jīng)典麻雀搜索算法

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

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

跟隨者的位置更新：

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

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

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

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

2.2.1 利用Logistic映射初始化種群

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

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

2.2.2 利用Pareto最優(yōu)解求解多目標優(yōu)化問題

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

多目標優(yōu)化定義如下：

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

3 算法流程

具體算法流程如下：

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

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

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

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

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

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

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

4 仿真實驗

4.1 實驗參數(shù)設置

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

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

表1 無人機的基本參數(shù)

表2 目標參數(shù)設置

經(jīng)多次實驗數(shù)據(jù)對比，取適應度函數(shù)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的偵察任務。每個無人機的任務均為唯一，且每個目標的偵察、攻擊、評估任務均被完成。

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

圖1 算法適應度曲線

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

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

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

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

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

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

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

5 結語

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