基于多策略GWO 算法的不確定環境下異構多無人機任務分配

張安，楊咪，畢文豪，張百川，王雨農

西北工業大學 航空學院，西安 710072

隨著軍事領域的不斷發展，無人機得到了廣泛的應用［1-3］，但在執行復雜戰場環境下的各類任務時，往往需要多架無人機相互協作完成，以發揮更好的綜合作戰效能［4-5］。現有的大多數多無人機任務分配問題都建立在任務環境靜態且確定的基礎上，未考慮如無人機自身性能不穩定，目標執行時長不明確，以及威脅、天氣等對任務分配過程中參數的影響，導致預先制定的確定條件下的“最優”任務分配方案往往無法獲得預想的結果，甚至無法完成［6-7］。因此，如何在對異構多無人機任務分配時提前考慮不確定性因素對任務分配結果的影響，以提高分配方案的魯棒性，已成為解決實際戰場環境下異構多無人機任務分配問題的關鍵［7］。

目前考慮不確定因素影響的異構多無人機任務分配研究相對匱乏，通常將不確定條件下的任務分配問題看作為優化問題，并采用隨機規劃、魯棒優化和模糊規劃等［8］方法進行求解。隨機規劃作為一種常用的處理不確定性的方法，其引入以概率分布函數描述的不確定性隨機變量，并通過建立有關目標函數的隨機變量模型，采用不同優化算法進行求解［9］，在求解不確定下的任務分配問題時得到了廣泛應用，如文獻［10］以兩階段隨機規劃模型的形式研究了具有隨機速度和隨機時間窗的異構無人機協同多任務分配問題。但隨機規劃方法應用的前提是需要估計不確定參數的分布情況，且估計的分布需要與實際分布足夠接近，然而在實際戰場中不確定事件的發生概率難以獲得。因此有學者提出利用魯棒優化方法求解不確定環境下的多無人機任務分配問題，通過控制決策保守參數，將不確定的優化模型轉換為確定的線性規劃模型，由于不用假設不確定參數的分布，比隨機規劃模型更容易求解［11］。文獻［12］針對顧客需求不確定下的無人機調度問題，提出了一種兩階段魯棒優化模型，其求解效果優于隨機規劃；文獻［13］考慮無人機飛行油耗參數等不確定性，利用魯棒優化方法構建原模型的魯棒對等形式，實現了任務分配魯棒性和最優性之間的有效平衡；文獻［14］提出了一個魯棒優化模塊以提高時間成本不確定下任務分配方案的魯棒性。但魯棒優化方法所求解的任務分配方案存在過度保守的問題，難以權衡系統性能和對不確定性的保護。而模糊規劃方法在求解不確定條件下的任務分配問題時，其不確定參數以模糊集的形式描述，僅需根據先驗知識選取不確定變量的隸屬函數即可，強調的是約束滿足的可能性，其求解思路為將模糊規劃的目標函數和約束條件轉化為一般形式的規劃模型，從而求解獲得模糊最優解。如文獻［15］針對執行時間不確定情況下的資源調度問題，基于模糊規劃理論建立了時間-成本約束條件下的模糊資源調度模型，并提出一種改進的混沌蟻群算法對模型進行求解。文獻［16］針對帶模糊需求與模糊時間窗的車輛路徑問題，構建了基于可信性測度理論的多目標模糊機會約束模型，并利用改進的混合遺傳算法進行求解。文獻［17］提出了一種基于模糊的資源再分配調度模型，將未完成的任務重新分配。文獻［18］針對無人機協同對地攻擊問題中目標威脅的模糊性，建立一種多階段的模糊多目標任務分配規劃模型，并提出基于多策略融合粒子群算法的納什均衡求解方法。

本文針對具有不確定任務持續時間、目標的消失時間和無人機航行速度等不確定信息，以及多項復雜約束的異構多無人機任務分配問題，首先基于模糊可信性理論，構建以最小化總成本為優化目標的模糊機會約束規劃模型，最后提出一種多策略融合的灰狼優化算法（Multi-Strategy Integrated Grey Wolf Optimization， IMSGWO），引入自適應控制參數調整策略、自適應慣性權重策略、最優學習策略和跳出局部最優策略等，提高算法的搜索能力。本文方法無需提前估計不確定變量的分布律，只需簡單估計不確定變量的隸屬函數即可。通過對不同測試問題的仿真實驗和算法比較驗證了IMSGWO 算法的有效性和魯棒性。

1 不確定環境下的異構多無人機任務分配模型

1.1 問題描述

本文考慮不確定戰場空間下，多架異構無人機協同對待摧毀目標執行偵察與打擊任務的分配問題，其中任務持續時間、目標的消失時間和無人機的航行速度是不確定的，用三角模糊數表征。戰場中不存在禁飛區、地形障礙和突發威脅等，且所有無人機飛行高度相同并具有相同的全局戰場信息。要求在滿足任務時序約束和時間窗約束的情況下，優化出一個任務分配方案，在上述不確定條件下，使任務的失敗率更低，提高任務分配方案的魯棒性。

1） 異構無人機參數描述

設有3 種類型的無人機（偵察類、打擊類和察打一體類）共M架U=[U1，U2，...，UM]，其中偵察類無人機UD只能執行目標偵察任務，打擊類無人機UA只能執行目標打擊任務，而察打一體類無人機UI可執行偵察和打擊任務2 種任務。

用多元組＜Uidi，Utypei，Uvali，ATi，Uposi，vi＞表示無人機i的屬性，其所代表的內容分別為無人機i的編號、類型、無人機本身的價值、打擊目標的概率、無人機的位置、無人機的巡航速度。用三角模糊數v?i=[v1i，v2i，v3i]表示無人機i的巡航速度，無人機在執行任務過程中的巡航速度為恒定。本文假設無人機執行偵察任務時不消耗資源，且察打一體類無人機和打擊類無人機都攜帶足夠多的打擊資源以完成所有目標的打擊任務，即本文不考慮資源對任務分配方案的影響。

2） 目標參數描述

設二維不確定戰場環境中有N個目標，用T=[T1，T2，...，TN]表示，由于需對每個目標執行偵察任務和打擊任務，即戰場環境中有2N個任務。

式中：Tjh為目標j的第h類任務（h=1，2），h=1 表示偵察任務，h=2 表示打擊任務，每個目標在完成偵察任務之后才能執行打擊任務。

1.2 模糊變量處理

與確定的任務環境相比，不確定的任務持續時間、目標的消失時間和無人機的航行速度使任務分配問題中的時間窗約束和時序約束更難以處理。因此，本文基于模糊可信性理論構建模糊機會約束規劃模型對上述不確定變量進行處理。

1.2.1 模糊可信性理論

式中：cr∈[0，1]，cr越大表示?的可能性越大，通過引入偏好值來表征決策者的態度，利用來約束?的可信度大小。越小，則決策者越傾向于冒著失敗的風險去基于?的條件做決策，相反，越大，表明決策者寧愿重新做出決策，也不愿意基于λ?≤θ?的條件做決策。

1.2.2 時間窗約束

設某無人機i完成其待執行的任務序列ai中的前k-1 個任務，則無人機i到達第k個任務位置的時間為

即到達第k個任務的時間為前k-1 個任務的執行時間與無人機從起點依次達到前k個任務位置的旅行時間之和。

當無人機i執行其任務列表中第k個任務時，基于可信性理論，其到達任務k的時間小于任務k的最晚開始時間sk的可信度記為cr1，且cr1∈[0，1]，cr1越大表示無人機Ui到達任務k的時間早于任務k的消失時間的可能性越大，即滿足任務k的時間窗約束的可能性越大。

1.2.3 時序約束

對于目標j，設Tj1=ai1L1，Tj2=ai2L2，即其偵察任務Tj1分配給無人機i1任務列表的第L1位置執行，打擊任務Tj2由無人機i2任務列表的第L2位置執行，則可得到Tj1的任務完成時間為

則為滿足任務的時序約束，基于可信性理論，目標j的偵察任務Tj1的完成時間小于打擊任務Tj2的開始時間的可信度為記為cr2，且cr2∈[0，1]，cr2越大表示目標j的偵察任務完成時刻小于打擊任務開始時刻的可能性越大，即滿足目標j的時序約束的可能性越大。

1.3 收益與代價函數

異構多無人機摧毀目標的代價包括2 個方面：① 無人機執行任務過程中存在的威脅代價C1；② 無人機完成自身任務集的航程代價C2。

設第i架無人機經過目標j后的存活概率為PSi，則PKi=1-PSj，PKj為目標j擊毀無人機的概率。因此，單架無人機i執行m個任務產生的威脅代價為

在不考慮路徑障礙的假設下，無人機傾向于完成距離自身位置較近的任務，使得相應的飛行油耗較少。航程代價可表述為

式中：Dmax，j為所有無人機相距任務j的最遠距離，即

異構多無人機摧毀目標的收益指對目標造成毀傷的價值，定義為目標的價值與毀傷概率，其大小體現了目標的重要程度和無人機的執行能力，能夠在決策優化時引導最終分配結果趨向于作戰效能最大化。設第i架無人機執行任務j的摧毀概率為Ati，則摧毀目標的收益為

1.4 任務分配模型

異構多無人機在具有不確定任務持續時間、目標消失時間和無人機航行速度等信息的環境下的任務分配問題為多目標模糊機會約束模型，首先通過線性加權和法將問題轉化為單目標的模糊機會約束模型，并采用線性尺度變換法將各量綱轉化為［0，1］集合內的數值。通過設置不同的權重向量來平衡各個因素對分配結果的影響程度，其中權重ω1、ω2和ω3分別代表攻擊目標所產生的威脅代價C1的權重，航程代價C2的權重，以及摧毀目標所獲得收益C3的權重，不同的權重取值反映了指揮決策人員的不同決策偏好。由此，基于模糊可信性理論，異構多無人機在上述不確定環境下的任務分配問題的模糊機會約束規劃模型為

約束條件為

式（13）表示無人機到達每個任務的時刻早于對應目標消失時間的可信度不小于主觀偏好值；式（14）表示每個目標的偵察任務的完成時間早于打擊任務的開始時間的可信度不小于主觀偏好值，本文設置式（15）確保每個目標的偵察和打擊任務都能被執行；式（16）確保每個任務只能被執行1 次；式（17）表示每個無人機的航程約束，Vmaxi為無人機i的最大航程，式（18）表示決策變量xijh的取值。

2 IMSGWO 求解不確定環境下的多無人機任務分配問題

2.1 基本IGWO 算法

灰狼優化算法（Grey Wolf Optimization，GWO）是一種新型群體智能優化算法［19］，模擬了灰狼的社會等級制度和獵食行為，具有實現簡單、收斂速度快和全局搜索能力強等優點。為提高基本GWO 算法中的群體多樣性、平衡算法的開發和探索能力，并避免過早收斂，文獻［20］受啟發于狼群中單獨狩獵的社會行為，于2021 年提出了改進的灰狼優化算法（Improved Grey Wolf Optimization，IGWO），利用基于維度學習的狩獵（Dimension Learning-based Hunting，DLH）搜索策略，通過選擇和更新步驟進一步提高了算法的搜索效率。

IGWO 將狼群中每一個灰狼個體都視為一個潛在解，并通過初始化、移動、選擇與更新等3個階段完成問題的求解：

1） 初始化

N個灰狼被隨機分布在給定范圍［lj，uj］ 的搜索域中：

第i個灰狼在第t次迭代時的位置表示為：Xi(t)=[Xi1，Xi2，…，XiD]，其中D為問題的維度。整個灰狼群的位置被存在矩陣PopN×D中，每個灰狼Xi(t)的適應度值記為f(Xi(t))。

2） 移動

首先根據適應度值將最好的3 只灰狼依次記為α、β、δ，其余的灰狼記為ω狼，并將灰狼在移動過程中的包圍行為建模如下：

式中：A和C為系數，控制參數a在迭代過程中由2 線性遞減到0；r1和r2是在［0，1］中的隨機向量；MaxIter 為最大迭代次數。

首先計算出狼群內個體與α、β、δ的距離，然后綜合判斷出個體向獵物移動的方向。

式中：Dα、Dβ、Dδ表示當前候選灰狼與α、β、δ狼之間的距離；Xα、Xβ、Xδ為α、β、δ狼的位置，C1、C2、C3和A1、A2、A3由式（20）得到。

3） 選擇與更新

除了灰狼群中的群體狩獵之外，單獨狩獵也是另一種重要的行為，因此IGWO 提出基于DLH 的搜索策略。首先為每只灰狼構建一個鄰域，并且此鄰域中的灰狼之間可以共享信息，通過向鄰居灰狼學習，得到另一個候選位置；然后通過比較基本GWO 算法與DLH 搜索策略所求得的新位置候選解的適應度值，選擇較優的位置更新為下一迭代過程中的獵物的位置X（t+1）。

首先采用歐氏距離計算灰狼i的當前位置X（it）與Xi～GWO(t+1)之間的距離Ri(t)

然后構建Xi(t)的鄰居灰狼群為

并且通過式（26）完成多鄰居學習

即DLH 搜索策略所求得的新位置Xi～DLH(t+1)的第d維是通過學習鄰居灰狼Xn(t)和狼群中任意灰狼Xr(t)得到的。

在對所有灰狼個體完成DLH搜索后，比較2 個候選對象Xi～GWO(t+1)和Xi～DLH(t+1)，并更新獵物的最新位置：

然后繼續迭代移動和選擇與更新階段，直至到達最大迭代次數，算法停止。

2.2 改進策略

對IGWO 算法進行分析可知，通過最優解、優解及次優解確定獵物的位置雖然可使算法具有更明確的指向性，在迭代初期的收斂速度較快，但在優化后期會導致種群多樣性降低，優化效果不穩定，易陷入局部最優。同時，算法的控制參數與位置更新策略沒有考慮種群的實時變化情況，在一定程度上減緩了算法的收斂速度。

針對上述問題，本文提出了一種多策略融合的灰狼優化（Multi-strategy Integrated Grey Wolf Optimization，IMSGWO）算法，首先采用自適應調整策略來調整算法中的控制參數，提高算法的收斂速度，然后通過學習種群的最優信息來控制算法的搜索方向，同時為了保持種群多樣性，采用自適應策略更新最優學習策略中的慣性權重，并改進IGWO 算法中的選擇與更新階段以跳出局部最優。

1） 自適應控制參數調整策略

在IGWO 算法中，控制參數a可調節全局與局部最優搜索的切換。當a較大時搜索步長較大，利于全局搜索，隨著迭代次數的增加，控制參數a線性遞減，當a較小時搜索步長減小，有利于全局最優值的確定。為進一步提高算法的收斂速度，本文采用自適應調整策略，即綜合考慮了當前迭代次數t和當前灰狼個體的適應度值f（it）來確定控制參數ai的大小，

式中：fmin(t)和favg(t)分別為當前灰狼群體的最小適應度值和平均適應度值。式（28）表示，若當前灰狼個體適應度值f（it）小于狼群的平均適應度值favg(t)時，a將由當前迭代次數和當前個體的適應度值大小確定，以提高算法的收斂速度。當fi(t)＞favg(t)時，則控制參數a只由當前迭代次數決定。這一策略既能保證了狼群中每個灰狼根據個體情況確定a，又能保證算法在迭代初期有較好的全局搜索能力，同時具有較好的尋優能力。

2） 最優學習位置更新策略

為使得狼群的下一個位置不比當前的位置差，在搜索的過程中不斷趨于更優的位置，提高算法的局部搜索能力和搜索精度，本文提出采用最優學習策略來更新灰狼的位置

式中：Vi(t)為灰狼i的當前速度；ψ(t)為自適應慣性權重；Pibest為灰狼i的最優位置；Pi(t)為灰狼i的當前位置；Xα(t)為當前灰狼群中的最優位置；ξ1、ξ2與ξ3為［0，1］之間的隨機數；γ1與γ2為常數，本文中設為γ1=γ2=2。

3） 自適應慣性權重策略

如果算法在迭代收斂過程中灰狼彼此接近，則聚集度會增加，使得灰狼群的多樣性降低并陷入局部最優。為提高算法在尋優過程中的多樣性，本文引入生物學中表示種群聚集度的指標，采用自適應策略更新慣性權重ψ(t)

式中：k為常數；H（t）為種群聚集度；Fδ(t)為灰狼群適應度的方差。自適應慣性權重ψ（t）主要由式（32）中的聚集度H（t）決定，可通過增加聚集度來弱化灰狼群跟蹤局部最優或者全局最優的能力，使得灰狼群在尋優過程中保持多樣性。

4） 跳出局部最優策略

IGWO 算法在搜索初期具有較好的收斂速度，全局搜索能力較強，然而隨著迭代次數的增多，種群位置變化率降低，因此利用式（33）來幫助種群跳出局部最優：

式中：ε為退火系數，取值為［0.9，1］；T（t+1）為退火溫度；ΔF為2 種策略所得解的適應度差值。本文設置即使當DLH 搜索策略所得解的適應度值大于式（23）中原始IGWO 所得解的適應度值時，仍然有一定概率接受DLH 搜索所得的較差解。

2.3 任務序列編碼

在IMSGWO 算法中，每個灰狼就是一個備選解，通過種群搜索和位置更新來尋求問題的最優解。為滿足在具有不確定任務持續時間、目標消失時間和無人機航行速度的環境下，異構多無人機任務分配問題中偵察任務與打擊任務的時序約束、一架無人機同一時刻只能執行一個任務的約束，以及無人機類型與任務類型的匹配約束，本文采用基于實數向量的編碼方法，建立灰狼位置與任務分配解的映射關系，其中，灰狼位置的維度與任務的數目相同，并為目標數目的2 倍。灰狼位置的整數部分［X］表示此任務對應的無人機編號，整數部分相同的任務被分配給同一架無人機執行。本文通過限制每個維度上灰狼位置的整數部分的上下界來保證異構多無人機的能力與任務類型匹配，如灰狼位置中對應各目標偵察任務的整數部分取值可為任意可執行偵察任務的無人機編號，打擊任務同理。灰狼位置的小數部分｛X｝表示該任務在無人機任務列表中的有限順序，小數部分越小表示越早執行此任務，如表1 所示。對表中的灰狼位置解碼后可得到無人機U1、U2、U3的任務序列分別為：T3，1→T2，1、T3，2→T1，1、T1，2→T2，2。

表1 任務序列編碼Table 1 Task sequence coding example

2.4 IMSGWO 求解不確定環境下異構多無人機任務分配問題流程

利用IMSGWO 算法求解具有不確定任務執行時長、目標消失時間和無人機航行速度的環境下的異構多無人機任務分配問題流程如圖1 所示，其中虛線框圖表示本文改進的內容，并歸納如下步驟：

圖1 IMSGWO 算法流程圖Fig.1 Flow chart of IMSGWO algorithm

步驟1初始化灰狼種群。根據無人機和目標的信息確定灰狼位置的維度及搜索域的上下界［lj，u］j，確定搜索空間的灰狼個數N和最大迭代次數MaxIter，并根據式（19）將N個灰狼隨機分布在給定范圍的搜索域中，初始化相關控制參數。

步驟2對灰狼種群的位置進行解碼，判斷是否越界，即是否滿足約束條件式（13）～式（18）。若滿足，則轉步驟3，或不滿足，則對越界位置進行調整，更新灰狼位置。

步驟3根據式（12）計算種群中每個灰狼的適應度，確定當前最優解Xα、優解Xβ和次優解Xδ。

步驟4利用式（28）自適應調整控制參數a，式（20）計算系數A和C，并根據式（21）～式（23）計算X（t+1）。

步驟5并通過式（29） ～式（32）確定自適應慣性權重并學習種群的最優搜索方向，得到學習后的解為Xi～GW（Ot+1）。

步驟6根據式（24） ～式（25）構造鄰居灰狼群，并通過式（26）構造Xi～DL（Ht+1）.

步驟7根據式（33）選擇并更新種群的位置，以跳出局部最優。

步驟8判斷算法是否滿足終止條件，若滿足則輸出當前最優位置，并經解碼后得到上述不確定環境下最優的異構多無人機任務分配方案，算法結束；否則轉步驟2 繼續搜索。

3 算法驗證及結果分析

3.1 參數設置及實驗環境

本文算法參數設置如下：最大迭代次數為MaxIter=500，種群規模Popsize=30。本文所有算法和測試程序均采用MATLAB R2017a 編程實現仿真，操作系統為Windows 10，CPU 為AMD Ryzen 7 PRO，主頻為1.70 GHz，內存為16 GB。

3.2 數值實驗及分析

實驗1為驗證IMSGWO 算法求解任務執行時長、目標消失時間和無人機航行速度等不確定信息下異構多無人機任務分配問題的可行性，本文假定4 架無人機在10 km×10 km 的作戰區域中對10 個敵方目標執行偵察任務與打擊任務，即M=4，N=10，設置決策者偏好值cr=0.8，表2 與表3 分別為無人機與任務的屬性表。

表2 無人機屬性Table 2 Basic information of UAVs

表3 任務屬性Table 3 Basic information of tasks

IMSGWO 算法求解過程中適應度變化曲線如圖2 所示，可看出由于算法中引入了自適應控制參數調整策略、自適應慣性權重策略與最優學習策略，因此算法的收斂速度較快，在迭代次數t=15 時即可得到可行解。且由于加入了跳出局部最優策略，使IMSGWO 算法能在迭代后期（迭代次數t＞350）能夠多次跳出局部最優，具有較好的尋優能力。最終得到無人機分配信息和任務分配信息分別如表4 和表5 所示。

圖2 IMSGWO 算法適應度變化曲線Fig.2 Fitness curve of IMSGWO

表4 無人機分配信息Table 4 Schedules information of UAVs

表5 任務分配信息Table 5 Allocation information of tasks

其中表4 中記錄了每架無人機執行任務的序列以及行駛距離，表5 記錄了執行每個目標的偵察任務與打擊任務的無人機編號，以及每個目標滿足時間窗約束和時序約束的可信度。可以看出，所有任務都被分配，且都滿足上述2 個約束的可信度都可大于給定偏好值cr=0.8 的要求。除此之外，表5 用三角模糊數表示了所有任務的開始執行時刻。因此，此實驗驗證了IMSGWO 算法在求解具有任務時間窗不確定、任務執行時間不確定和無人機巡航速度不確定等條件下的任務分配問題時的可行性。

實驗2為驗證無人機數量和目標數量變化對IMSGWO 算法性能的影響，本文分別在目標數量固定（N=10）且無人機數量增加（M=4，6，8），和無人機數量固定（M=4）且目標數量增加（N=8，10，12）的不同任務載荷（任務數量/無人機數量）設置下下測試IMSGWO 算法的求解性能，其求解過程中的平均適應度值變化曲線如圖3 和圖4 所示。

圖4 目標數量增加時IMSGWO 平均適應度變化曲線Fig.4 Average fitness curves of IMSGWO with increasing number of targets

從圖3 中可以看出本文所提的IMSGWO 算法在上述所有設置下都可獲得可行解，并且隨著無人機數量的增加，IMSGWO 算法的適應度值下降減慢，即收斂速度逐漸減慢。由本文所提出的編碼方式（表1）可知，當目標數量一定時，無人機數量越多則搜索域越廣，導致算法的求解速度變慢。除此之外，圖3 顯示最終分配方案的適應度值也隨著無人機數量不斷增加，這是由于當目標數量一定時，無人機執行任務所獲得的總收益相差不大，但航程代價與威脅代價卻隨著無人機數量增加而不斷增加，導致最終任務分配方案的適應度值不斷增加。

從圖4 中可看出當無人機數量一定時，IMSGWO 算法的收斂速度隨目標數目的增加逐漸減慢，這是由于目標數量的增加導致灰狼位置編碼的維度也線性增加，因此在求解同時滿足所有目標的時序約束和時間窗約束時求解難度增大，使得算法需要更多的迭代循環尋找可行解。除此之外，隨著目標數量的不斷增加，平均每架無人機所需要執行的任務數量增加，使得無人機的任務列表完成時間和航程代價都隨之增加，因此本文所提算法所求得的最終適應度值也隨著目標數量而不斷增加。

實驗3為驗證所提算法的優越性，本文考慮3 組任務載荷遞增的設置：M=6、N=8，M=4、N=10 和M=4、N=12，并將IMSGWO 與3 種經典單目標優化算法PSO、GWO、IGWO，以及一種多目標優化算法MOPSO 在3 種任務載荷設置下獨立運行10 次。其中PSO 算法的慣性權重為w=0.9，學習因子c1=c2=2，最大速度Vmax=3；MOPSO 的慣性權重w=0.9，學習因子c1=c2=2，存檔規模Archive_Size=30，每個維度的網格數grid_size=10，約束因子α=0.1， 最大速度Vmax=3，突變因子μ=0.1。MOPSO 作為經典的多目標優化算法，為便于與其他單目標優化算法進行比較，本文利用式（12）來評價粒子的性能，即用相同的權重ω1，ω2和ω3來計算每個粒子的適應度值。若MOPSO 不能尋得最優解，則選擇種群中適應度值最小的粒子作為最終解，若有可行解存在存檔Archive 中，則統計Archive 中所有可行解的平均適應度值作為當前隨機運行的最終適應度值，并選擇Archive 中適應度值最小的粒子作為最終的任務分配方案。最終任務分配結果的平均值統計記錄在表6 中，最優結果用粗體表示，其中BST、AVG、WST、STD 與AVGIter 分別表示算法隨機運行10 次所得任務分配方案結果的適應度的最優值、平均值、最差值、標準差和首次得到可行解的迭代次數，AVGDis 和AVGComTime 分別為10 次任務分配方案中所有無人機行駛距離的平均值和任務列表完成時間的平均值，由于每個無人機的任務列表完成時間表示為三角模糊數，因此利用最可能的估計值來計算所有無人機任務列表完成時間的平均值。

表6 5 種算法在3 種不同設置下的性能比較Table 6 Comparison of performance of five algorithms with three different settings

由表6 可知，本文所提的算法在3 種不同任務載荷設置下的最優適應度值BST，平均適應度值AVG 和最差適應度值WST 都優于其他四種算法，證明了本文所提IMSGWO 算法具有更好的尋優能力。由WST 值可知PSO 算法在3 種任務載荷設置下都存在無法找到可行解的情況（即適應度值＞10），并且GWO 算法和MOPSO 算法在較高的任務負載情況（M=4，N=12）下也存在無法找到可行解的情況，但IMSGWO 算法和IGWO 算法在所有情況下均能尋得可行解，且只在M=4，N=10 的設置下，IMSGWO 算法適應度值標準差STD（0.026 7）略高于GWO 算法（0.011 8），而在其他2 種設置下其STD 都為最優，證明所提算法具有較好的穩定性。由于PSO、GWO 和MOPSO 存在不能求得可行解的情況，因此只統計能夠求得可行解時的首次獲得可行解的迭代次數AVGIter，可看出，盡管IMSGWO 算法在3 種情況下的AVGIter 都略大于IGWO，但仍小于其他3 種算法，證明所提算法有較快的收斂速度。除此之外，IMSGWO 算法在3 種不同任務載荷設置下所得任務分配方案的無人機平均總行駛距離AVGDis 和平均任務列表完成時間AVGCom-Time 都與最優值相差不足2.5%，表示5 種算法求得任務分配方案的平均時間代價和航程代價接近。同時可注意到，隨著任務載荷的增加，每架無人機平均需要完成任務的數量增加，無人機行駛的航程距離和無人機完成任務列表的時間都不斷增加。

5 種算法在3 種不同任務載荷設置下求解過程中的平均適應度值變化曲線如圖5 所示。從圖中可以看出，由于PSO 算法在迭代過程中易陷入局部最優，存在無法成功求得可行解的情況，因此其平均適應度值遠高于其他4 種算法。由于MOPSO 獲得可行解并存儲在Archive 中，當存在其他可行解支配Archive 中任一可行解時，則算法的平均適應度值更新一次，因此如圖5 所示，MOPSO 算法在迭代前期平均適應度值的變化次數多于其他4 種算法。除此之外，由于慣性權重的設置不同，MOPSO 算法尋得的非支配解并不一定是式（12）評價下的更優解，因此MOPSO 算法在迭代過程中其平均適應度值并不總是下降。在前2 種任務載荷設置下MOPSO 算法的求解速度較快，但在迭代后期容易陷入局部最優，導致最終適應度值高于GWO、IGWO 和IMSGWO算法，并且在M=4、N=12 的載荷設置下存在無法求得可行解的情況。除此之外，GWO 算法在3種任務載荷設置中不僅收斂速度較慢，且最終適應度值也較高，算法求解能力不強。IGWO 算法由于在GWO 算法的基礎上添加了DLH 搜索策略，與PSO 算法和GWO 算法相比不僅收斂速度較快，最終適應度值也低，具有較好的求解能力；而本文提出的IMSGWO 算法在IGWO 算法的基礎上進一步添加了自適應控制參數調整策略、自適應慣性權重策略、最優學習策略和跳出局部最優策略，使得算法不僅在前期的收斂速度與IGWO 算法接近，且其最終平均適應度值遠低于其他4 種算法，并且能夠在迭代后期（t＞450）多次跳出局部最優，具有較好的尋優能力。充分證明了本文所提出的融合多種改進策略的IMSGWO 算法與其他4 種算法相比，在求解具有不確定任務執行時長、不確定目標消失時間和不確定無人機航行速度等信息的異構多無人機任務分配問題時具有更好的性能。除此之外，根據表1 所提出的編碼方式，隨著任務載荷的增加，算法的求解難度也不斷增加，導致5 種算法都需要通過更多次的迭代來進一步尋求更優的分配結果。

圖5 3種任務載荷設置下5種算法平均適應度值變化曲線Fig.5 Average fitness curves of five algorithms with three different settings

實驗4為驗證決策者偏好值對不確定任務執行時長、不確定目標消失時間和不確定無人機航行速度等信息下的異構多無人機任務分配方案效果的影響，圖6 統計了決策者偏好值cr按幅度0.1遞增時IMSGWO 算法在3 種不同任務載荷設置下隨機運行10 次的分配方案的適應度值和平均任務完成時間。除此之外，由于本文中不確定信息=(λ1，λ2，λ3)的上下界λ1和λ3由λ2和不確定程度χ確定，即λ1=(1-χ)λ2，λ3=(1+χ)λ2，為驗證不確定信息的不確定程度對任務分配方案性能的影響，圖7統計了不確定程度為低中高，即χ分別為0.1、0.3、0.5 時，IMSGWO 算法隨機運行10 次的任務分配方案的適應度值和平均任務完成時間。

圖6 3 種不同設置下偏好值cr遞增時的平均任務完成時間與平均適應度值信息Fig.6 Average task completion time and average fitness with increasing preference value cr and three different settings

圖7 3 種不同設置下不確定程度χ 遞增時的平均任務完成時間與平均適應度值信息Fig.7 Average task completion time and average fitness with increasing uncertain degree χ and average three different settings

由圖6 可知，隨著偏好值cr逐步增加，3 種任務載荷設置下的平均無人機任務列表完成時間AVGComTime 即時間代價不斷增加，導致分配方案的適應度值總體逐步增加。這是因為當cr遞增時，決策者逐漸偏向于保守型，為盡可能減少目標時序約束被違反的可能，目標打擊任務的開始執行時刻會推遲，導致無人機的平均任務完成時間不斷增加，所得任務分配方案的適應度值也隨之增加。如圖7 所示，由于不確定程度χ的增加，為保證滿足所有目標的時序約束，任務的開始時刻被推后，致使無人機的平均任務完成時間增加，任務分配方案的適應度值也隨之增加。

實驗5在本文的研究中，任務持續時間、目標消失時間和無人機的航行速度等都為不確定信息，為驗證IMSGWO 算法所求解的任務分配方案在任務實際執行過程中的性能，首先利用隨機模擬算法［21］（Stochastic Simulation Algorithm， SSA）模擬上述不確定信息的實際值，然后為了以最小改動實現動態調整，本文利用分布式的性能影響算法（Performance Impact， PI）［22］中的任務包含階段，在不影響原有任務分配方案執行順序的前提下完成對失敗任務的重分配。具體地，PI 算法利用任務包含階段將失敗的任務循環插入類型相符的無人機任務列表中剩余任務間的所有位置，判斷插入位置是否滿足時序約束和時間窗約束，并利用無人機刪除失敗任務對任務分配方案整體的影響與不同無人機在不同位置添加任務的影響之間的差值，來衡量此任務重分配方案的性能，具體算法可參考文獻［22］。

為了不失一般性，在3 種的任務載荷設置下，統計3 種決策者偏好cr設置下和3 種不確定程度χ設置下的IMSGWO 算法所求任務分配方案的動態性能，如表7 與表8 所示。首先在每種設置下隨機生成20 種不同的目標和無人機信息，并在IMSGWO 算法求得滿足約束的可行解后，為每個可行解利用SSA 算法隨機生成20 組不確定信息的實際值，并統計此實際情況下，原任務分配方案需要重分配的比例RePer，以及成功重分配的比例ReSucPer。

表7 IMSGWO 算法在不同任務載荷和決策者偏好下所求任務分配方案的動態性能Table 7 Dynamic performance of IMSGWO with different settings and preference value

表8 IMSGWO 算法在不同任務載荷和不確定程度下所求任務分配方案的動態性能Table 8 Dynamic performance of IMSGWO with different settings and uncertain degrees

由表7 和表8 可知，當決策者偏好cr或者不確定程度χ一定時，隨著任務載荷的增加，IMSGWO 所求得的任務分配方案中有更多任務在實際執行過程中無法滿足約束，需要執行更多次的重分配以保證目標的成功完成，并且由于任務載荷增加使得每架無人機完成其任務列表的時間更長，導致添加失敗任務之后任務列表中其他任務的時序約束和時間窗約束無法滿足的可能性更大，從而使成功重分配的比例隨任務載荷的增加而降低。

除此之外，表7 的結果表明，當任務載荷一定時，決策者主觀偏好值cr的增加意味著決策者傾向于更保守的任務分配方案，即IMSGWO 所求得的任務分配方案能夠更大程度地規避不確定任務持續時間、目標消失時間和無人機航行速度帶來的影響，所有任務成功執行的概率更高，因此需要動態調整的任務分配方案的比例不斷降低。同時，當任務載荷一定時，決策者偏好增加會使IMSGWO 求得的任務分配方案有更多冗余時間，因此更容易處理失敗任務，重分配成功的比例隨偏好值的增加而增加。

如表8 所示，當不確定程度增加時，更多已分配的任務在實際執行過程中無法滿足時序約束和時間窗約束，因此在任務載荷一定時，需要重分配的比例隨不確定程度的增加而增加。同時，不確定程度的提高意味著無人機更容易利用冗余時間處理失敗任務，因此重分配成功的比例隨偏好值的增加而增加。

4 結 論

本文針對具有不確定任務執行時長、不確定目標消失時間和不確定無人機航行速度等不確定信息以及復雜約束的異構多無人機任務分配問題，首先將不確定信息作為模糊變量處理，并基于模糊可信性理論，首次構建以最小化總成本為優化目標的異構多無人機任務分配問題的模糊機會約束規劃模型，并設計了一種多策略融合的灰狼優化算法（IMSGWO）進行求解。實驗結果表明，所提算法可求解不確定環境下的異構多無人機任務分配問題，使分配方案對任務執行過程中的不確定性因素具有較好的抗干擾能力。未來將針對現實中存在的不確定任務資源需求、不確定任務位置等進行研究，并進一步改進求解算法。