基于改進人工蜂群算法的多無人機滅火任務規劃

張小孟，胡永江，李文廣，龐強偉，袁國剛

（1.陸軍工程大學 無人機工程系，石家莊 050003；2.31700 部隊，遼陽 111000）

隨著無人機技術的快速發展，其在情報搜集、電子偵察、指控通信、戰損評估等軍事領域，以及災情預警、事故救援、消防滅火等民用領域都發揮著越來越重要的作用。無人機運用模式也逐漸由單機向多機協同方向發展[1]，其中滅火救援是多無人機應用的一個重要方面[2]。受到用火習俗以及氣候等多種因素的影響，山火災害特別容易在短時間內集中爆發。當一個區域同時爆發多處山火時，需要迅速地根據各個火點的火情及位置情況，對其進行滅火救援，而使用無人機投放滅火彈對山火火點進行滅火是一種快速高效的滅火方法。

在火情高發期，通過使用多個無人機共同對多個火點目標投放滅火彈，可以快速實現對多個火點火情的控制。無人機投放滅火彈需要針對具體的任務需求，為各無人機合理分配火點目標，使各無人機以較小的代價完成滅火救援任務，該過程即為多無人機對多火點火場滅火救援任務規劃過程。

目前在多無人機任務規劃過程中,關于無人機航路的可行性以及避險問題規劃的研究已相對成熟[3-7]。但對于高效救援多個不同價值目標時的任務規劃問題，還有一定的研究空間。針對多無人機對多目標任務規劃問題，文獻[8]建立了混合整數線性規劃模型，文獻[9]建立了多目標優化問題模型，文獻[10]建立了多旅行商問題模型。根據這些模型，文獻[11]提出了一種改進量子粒子群算法，文獻[12]通過引入Metropolis 準則的方式提出改進人工蜂群算法，文獻[13]設計了一種蝗蟲仿生算法，但是這些算法局限于傳統單一約束問題，無法求解多約束的實際問題，算法的普適性很差。文獻[14]提出了一種基于整數編碼的多種群混合遺傳算法(Multi-Population Hybrid Genetic Algorithm,MPHGA)，該算法的收斂性較強，且任務規劃效果較好，但該算法僅適用于目標價值固定的情況，對于目標價值變化的情況普適性較差。

上述方法在一定程度上能夠解決多無人機對多目標的任務規劃問題，但在解決多無人機對多火點火場滅火救援任務規劃問題時仍存在以下幾點不足：1）忽略了火點目標救援價值的時變性對任務規劃效果的影響[15]。在實際應用中，不同的目標對救援效果有著不同的影響，甚至在救援過程的不同時期，同一個目標產生的影響也是不同的，即目標對整體救援態勢的影響是隨時間變化的。在任務規劃的過程中必須考慮目標價值的時變性，進而增強任務規劃的可靠性。2）沒有考慮救援資源的有限性[16]。在實際滅火救援過程中，可用的無人機數量和掛載滅火彈的數量有限，可能無法保證對所有目標實施救援，指揮者需要根據目標實際價值和位置情況進行綜合決策。因此在救援資源有限的條件下，任務規劃必須考慮指揮者的綜合決策，以保證用有限的救援資源，收到盡可能大的救援效益。3）未考慮實際情況對任務規劃算法的約束性[14]。在多無人機對多火點火場滅火救援任務規劃過程中，由于無人機掛載滅火彈數量和任務無人機的航程有限，尋優過程中的所有可行解都需要滿足載彈量和無人機航程限制，才能保證算法收斂的準確性和快速性，防止無用解占用規劃資源。

針對以上問題，本文提出了一種多無人機對多火點火場滅火救援任務規劃方法。首先，在考慮火點目標價值時變性的基礎上，建立了目標價值隨時間變化的多無人機任務規劃模型，可實現根據指揮者的決策意圖來進行合理救援。然后，在標準人工蜂群算法的基礎上引入了整數編碼以及三種算子操作，用來解決有約束的任務規劃問題。最后，進行了仿真實驗。結果表明該任務規劃算法具有尋優能力強、尋優效率高的優點，不僅可以有效解決目標價值隨時間變化的任務規劃問題，而且可以在無人機數量不能滿足對所有火點目標進行飽和救援的情況下，根據指揮者的決策意圖進行有效的任務規劃。

1 多目標救援模型

1.1 問題描述

假設在進行滅火任務之前，通過前期對區域火情的分析，已確定各個火點目標的位置信息、目標價值以及價值隨時間變化情況等。在實施滅火任務過程中，各無人機均從地面站起飛，根據任務規劃結果有序完成對指定火點目標的救援任務，并在任務結束后回到地面站。

多無人機對多火點火場滅火救援任務規劃問題可描述為：給定待救援的火點目標集合target = {T1,T2…TNt}和Nu架滅火無人機UAVi(i=1,2…Nu)，所有待救援目標的價值集合為Value = {V1,V2…VNt}，各個目標價值隨時間改變情況的集合為Change = {C1,C2…CNt}。

在選定地面站位置的條件下，設計一種可通過調節整體任務價值和路徑代價的權重系數來實現指揮員決策意圖的任務規劃方法。同時在救援資源有限的情況下實現救援目標價值的最大化，增強規劃方法的普適性。

1.2 目標函數

多無人機執行對多火點火場滅火救援任務需要在獲取盡可能大的救援總收益同時，盡可能地減小無人機的滯空時間，降低任務執行過程中的能量損耗，即需要在目標總收益與無人機總滯空時間之間進行綜合優化。

在無人機實施目標救援的過程中，設Xi j為決策變量，其取值為1 時表示無人機UAVi對救援目標Tj實施救援，0 表示不實施救援。

（1）救援目標的總收益。假設目標價值隨時間的改變情況為目標價值關于時間的負指數函數，則總價值收益為：

其中C j=e-d jt為目標價值隨時間變化的函數，dj為目標Tj隨時間的衰減的系數；ti為無人機UAVi從離開基地到救援目標Tj時所經歷的時間。

（2）總滯空時間。隨著無人機在執行滅火任務過程中滯空時間的增長，火情引起的強上升氣流及強熱輻射對無人機造成損傷的概率增加，能量損耗增多，因此要求無人機總滯空時間要盡可能的短，即：

其中pathi為第i架無人機UAVi執行滅火任務所分配到的目標序列時所需的路徑代價，vi為UAVi的巡航速度。

（3）目標函數?？紤]到指揮員需要根據救援目標總收益與總滯空時間進行綜合決策，目標函數通過分配不同的權重將多目標尋優問題轉換為單目標尋優問題。

其中p，q為權重系數，β為補償系數（使兩個目標函數處于同一數量級）。

1.3 約束條件

（1）單架無人機執行任務的能力約束：

其中Bi為第i架無人機UAVi的最大掛載滅火彈數量。

（2）無人機的航程約束。受無人機機載能源的限制，無人機的航程不能超過自身最大航程Di，則

（3）目標價值約束。無人機執行任務的最大價值之和不能超過所有目標的總價值：

2 預先路徑規劃

由于在任務區域內可能存在障礙物、火情引起的強上升氣流及強熱輻射等因素產生的禁飛區影響無人機飛行，為了確保無人機在任務區域內有可飛路徑，在進行任務規劃之前，需要對無人機的可飛路徑進行預先規劃，以增強任務規劃的可行性及準確性。

可飛路徑的預先規劃首先需要用柵格法在任務區域內建立包含目標位置和禁飛區的路徑規劃空間模型，然后利用A 星算法求得初始較優路徑，最后在上述求得的較優路徑的基礎上，利用遺傳算法求得最優路徑。通過以上算法獲取無人機基地到每個目標點和任意兩目標點之間的可飛路徑，并準確計算得到所有路徑代價矩陣，為任務規劃提供有效依據。預先路徑規劃流程如圖1所示。

圖1 預先路徑規劃流程圖Fig.1 Flow chart of advance path planning

3 改進的人工蜂群算法

3.1 標準人工蜂群算法

標準人工蜂群算法（Artificial Bee Colony，ABC）包括三個組成部分，即蜜源位置、花蜜量和三種蜜蜂（雇傭蜂、跟隨蜂和偵察蜂）[17]。每個蜜源位置代表了需要優化問題的一個可行的解決方案，其花蜜量對應于解決方案的質量即適應度值。每一種蜜蜂都會執行一個特定的操作來產生新的候選蜜源位置。雇傭蜂也稱為引領蜂，其存儲有某一蜜源的相關信息，并且可以在蜜源周圍搜尋新的蜜源；跟隨蜂在蜂巢中通過雇傭蜂分享的信息尋找相關蜜源，偵察蜂是在雇傭蜂和跟隨蜂都找不到更好的鄰近蜜源時，進行隨機搜索以尋找新的蜜源位置。因此，標準ABC 算法將雇傭蜂和跟隨蜂視為執行局部搜索，而偵察蜂則執行全局搜索。

3.2 改進的ABC 算法

標準ABC 算法只能用于求解無約束連續問題，針對有約束的無人機任務規劃問題，本章采取一種基于整數編碼的改進人工蜂群算法，用以解決有約束的任務規劃問題，其核心包括種群初始化、改進雇傭蜂階段、改進跟隨蜂階段以及改進偵察蜂階段。

3.2.1 種群初始化

根據無人機以及任務目標的序列信息，借鑒遺傳算法的編碼形式，隨機生成一個m=Nt+Nu-1 位的整數序列（M1,M2…Mm），代表一個蜜源位置。其中編碼值小于或等于Nt的為目標編碼；大于Nt的為無人機編碼，假設為Hj，則無人機真實序列號為：j=Hj-Nt+1。從左邊開始到第一個無人機編碼之前的編碼序列為UAV1救援序列，之后的兩個相鄰無人機編碼之間所對應目標編碼組成的序列為UAVj救援序列，UAVj為對應序列最左側編碼對應無人機序列，以此類推。

假設待救援目標數Nt=10，無人機數Nu=3，無人機的載彈量B=4，則m=12。如圖2所示，該編碼對應的UAV1救援序列為T2-T5-T9-T3-T10，UAV2救援序列為T4-T8-T7，UAV3救援序列為T1-T6。

圖2 初始蜜源編碼Fig.2 Initial honey source coding

因無人機載彈量有限，則兩個無人機編碼之間的目標編碼個數不能超過無人機最大載彈量，當判斷目標個數超出載彈量時，對當前的蜜源位置重新初始化，直至滿足條件，因圖2中，UAV1救援目標為5 個，超過載彈量B=4，不滿足條件，則重新生成蜜源序列，如圖3所示，新序列中各個無人機救援序列分別為：UAV1救援序列為T2-T5-T9-T3，UAV2救援序列為T1-T6，UAV3救援序列為T10-T4-T8-T7,均滿足載彈量要求。

圖3 載彈量約束編碼Fig.3 Payload constraint coding

考慮到無人機存在航程約束，當無人機從基地起飛經過救援目標序列再回到基地時出現路徑代價之和超過最大航程約束時，當前蜜源位置也需要重新初始化。

用以上編碼方式生成SN個整數序列作為改進ABC 算法初始化種群，其中SN是蜜源數量。

3.2.2 改進雇傭蜂階段

雇傭蜂通常在蜜源附近進行鄰域搜索。為了表示鄰域搜索的行為，引入逆向算子操作，其過程如圖4根據以下步驟進行：

圖4 逆向算子操作Fig.4 Reverse operator operation

步驟1 從1 到m（位置總數）之間隨機生成兩個整數r1和r2；

步驟2 將r1到r2之間的編碼序列反轉，得到新序列；

步驟3 檢驗新序列是否滿足載彈量和航程約束要求，若滿足則使用新序列碼作為新的蜜源，若不滿足則轉至步驟1。

為進一步提高鄰域搜索能力，雇傭蜂階段再引入交叉算子操作，用選擇的蜜源和現有最優蜜源做為雙親，創造出更好的后代，其操作過程如圖5按以下步驟進行。

圖5 交叉算子操作Fig.5 Crossover operator operation

步驟1 從1 到m之間隨機生成兩個整數r1和r2；

步驟2 選擇r1和r2作為兩個交叉點；

步驟3 從步驟2 交換的數據中通過映射關系替換子代中的重復數，得到新序列；

步驟4 檢驗新序列是否滿足載彈量和航程約束要求，若滿足則使用新編碼序列作為新的蜜源，若不滿足則轉至步驟1。

使用逆向算子操作和交叉算子操作對雇傭蜂進行鄰域搜索，并在當前蜜源和新的鄰近蜜源之間進行貪婪選擇，以保證更好的蜜源被保留下來供進一步進化。貪婪選擇是基于蜜源的適應度值，計算公式為：

其中fi是模型的目標函數，fiti為適應度函數。

3.2.3 改進跟隨蜂階段

跟隨蜂是按輪盤賭方式在雇傭蜂種群中選擇的較優的種群，計算公式為：

跟隨蜂階段同樣根據收益率大小來選擇蜜源位置，使用逆向算子操作和交叉算子操作來進行鄰域搜索產生新的蜜源，收益率通過適應度值來表示。同雇傭蜂階段一樣，使用貪婪選擇保留更優蜜源。

3.2.4 改進偵察蜂階段

如果在有限的迭代次數內，雇傭蜂和跟隨蜂鄰域搜索沒有找到更優蜜源時，則將其作為偵察蜂。

通過在現有的最優蜜源的基礎上應用變異算子操作，使偵察蜂可以在全局范圍內發現新的蜜源，其操作過程如圖6按以下步驟進行。

圖6 變異算子操作Fig.6 Mutation operator operation

步驟1 從1 到m之間隨機生成一個整數r1；

步驟2 將所選序列碼中的r1位置的編碼隨機變異為另一位置的編碼，假設為r2位置，交換r1位置和r2位置，得到新序列；

步驟3 檢驗新序列是否滿足載彈量和航程約束要求，若滿足則使用新序列碼作為新的蜜源，若不滿足則轉至步驟1。

通過逆向算子操作，雇傭蜂可以生成新的鄰近蜜源，跟隨蜂可以通過鄰域搜索生成更多的蜜源，用來提高其局部搜索能力。通過交叉算子操作，可以進一步提高蜂群的局部搜索能力。通過變異算子操作，偵察蜂可以根據當前最優解生成新的蜜源，防止搜索陷入局部最優。

為了提高收斂速度和解的多樣性，逆向算子操作和交叉算子操作是在滿足逆向概率Pr和交叉概率Pc（0 ＜Pr，Pc＜ 1）的情況下進行的，而變異算子操作是在偵察蜂階段進行的，只有當雇傭蜂和跟隨蜂在有限次迭代內都無法找到更優的蜜源時，變異算子操作才被激活。

3.3 算法步驟

改進ABC 算法步驟如圖7所示。

圖7 改進ABC 算法流程圖Fig.7 Improved ABC algorithm flowchart

步驟1：種群初始化。設置初始化參數，對初始蜜源編碼，生成初始種群；

步驟2：改進雇傭蜂階段。使用帶概率的逆向算子、交叉算子操作對每個雇傭蜂進行鄰域搜索，使用貪婪選擇保留更好的解；

步驟3：選擇產生跟隨蜂。按輪盤賭方式選擇較優種群作為跟隨蜂種群；

步驟4：改進跟隨蜂階段。同雇傭蜂一樣，使用帶概率的逆向算子、交叉算子操作對每個跟隨蜂進行鄰域搜索，使用貪婪選擇保留更好的解；

步驟5：判斷是否產生偵察蜂。如果產生，對當前最佳蜜源實施變異算子操作進行全局搜索；

步驟6：判斷是否滿足終止條件。若滿足則輸出最優解，否則轉至步驟2。

3.4 收斂性分析

假設人工蜂群中蜂群個體的更新概率為P，由改進人工蜂群算法中蜂群個體的逆向算子操作和交叉算子操作概率（0 ＜Pr，Pc＜ 1）,可知P∈(0,1)，因此，蜂群個體的每一步更新概率都小于1，且更新過程中構成 Markov 鏈，即任意解間依概率可達，并對其它蜂群個體的更新不產生影響（獨立同分布）。同時，蜂群的種群序列是單調的。由上述理論分析及依概率收斂定理可知，該算法滿足依概率1 收斂到全局最優解的充要條件。

4 仿真實驗

仿真實驗平臺為Inter Core i5-7300HQ CPU,8GB,64 位Win10 操作系統惠普筆記本。編程工具為Matlab R2017b（64 位）。

4.1 參數設置

假設某基地機場有3 架無人機，現有30 個待救援的火點目標，每架無人機的最大載彈量為6，無人機參數如表1，目標位置參數如表2，目標的價值及衰減參數情況如表3。為直觀反映任務規劃效果，在仿真實驗中將無人機基地到每個火點目標和任意兩個火點目標之間的直線路徑作為可飛路徑，距離作為路徑代價。

由表1、2、3 可得出目標和無人機位置參數如圖8所示，其中初始價值大于0.5 的為重要目標，其余為一般目標。

表1 無人機參數Tab.1 UAV parameters

表2 目標位置參數Tab.2 Target position parameters

表3 目標的價值及衰減參數Tab.3 Target value and attenuation parameters

圖8 無人機和目標位置Fig.8 UAVs and target location

4.2 實驗結果及分析

實驗一：在目標價值不存在時變的情況下，對提出的改進ABC 算法有效性進行驗證。

如表2所示，重要目標有15 個，每架無人機的載彈量為6 發，需要3 架無人機完成任務。用改進ABC算法和文獻[11]提出的多種群遺傳算法（MPHGA）進行對比實驗。實驗次數為100 次，種群規模為100，最大迭代次數為100，改進ABC 算法中蜜源最大搜索次數limit為10，逆向概率Pc和交叉概率Pr均為0.85；MPHGA 算法中子種群數為4。仿真結果如圖9、圖10、圖11 所示，代價結果如表4所示。

圖9 改進ABC 算法救援路徑Fig.9 Rescue path of improved ABC algorithm

圖10 MPHGA 算法救援路徑Fig.10 Rescue path of MPHGA algorithm

圖11 兩種算法對比Fig.11 Comparison of two algorithms

表4 兩種算法對比Tab.4 Comparison of two algorithms

結果分析如下：

（1）由圖9，圖10 可得，兩種算法均能有效完成對所有重要目標的救援，驗證了所提算法的可行性。

（2）由表4兩種算法對比可得，在目標價值不存在時間衰減的情況下，所有被救援目標的總價值不變，主要影響因素為完成所有救援任務的時間代價，其中100 次仿真中MPHGA 算法的3 架無人機對15 個重點目標有效救援的總滯空時間平均為43 min，改進ABC算法則為42 min，滯空時間即完成任務時間降低了2.3%，說明改進ABC 算法的尋優能力優于MPHGA算法。

（3）由圖11 兩種算法有限次迭代的收斂狀況對比可得，改進ABC 算法平均在迭代12 次就達到了全局最優解；而MPHGA 算法在迭代79 次后最終陷入局部最優，得出次優解。改進算法的尋優時間僅為MPHGA 算法的15.2%，說明改進ABC 算法的尋優效率優于MPHGA 算法。

實驗二：在考慮目標價值時變的情況下，通過調整權重系數來反映決策者意圖，從而來驗證所提算法的普適性。

當無人機數量不能滿足救援所有目標的情況時，決策者就必須有取舍的去選擇救援一些更有價值的目標。因此，針對決策者對目標價值和滯空時間的權重要求，分別對權重系數分配不同時無人機救援任務規劃情況進行仿真，能夠更加體現算法在應對各種情況時的適用性，同時通過對比其仿真結果，也能夠為決策者提供最佳決策。

圖12 p = 1,q = 0 時改進ABC 算法救援路徑Fig.12 p = 1,q = 0 improved ABC algorithm rescue path

圖13 p = 1,q = 0 時MPHGA 算法救援路徑Fig.13 p = 1,q = 0 MPHGA algorithm rescue path

假設無人機的數量為3，改進ABC 算法中種群規模為100，最大迭代次數為200，蜜源最大搜索次數limit為10，逆向概率Pc和交叉概率Pr均為0.85，MPHGA 算法中子種群數為4。在權重系數為p= 1,q= 0；p=q= 0.5；p= 0,q= 1 時兩種算法的仿真結果如圖12、圖13、圖14、圖15、圖16、圖17 及表5。

圖14 p = q = 0.5 時改進ABC 算法救援路徑Fig.14 p = q = 0.5 improved ABC algorithm rescue path

圖15 p = q = 0.5 時MPHGA 算法救援路徑Fig.15 p = q = 0.5 MPHGA algorithm rescue path

圖16 p = 0,q = 1 時改進ABC 算法救援路徑Fig.16 p = 0,q = 1 improved ABC algorithm rescue path

圖17 p = 0,q = 1 時MPHGA 算法救援路徑Fig.17 p = 0,q = 1 MPHGA algorithm rescue path

表5 三種不同權重情況對比Tab.5 Comparison of three different weights

結果分析如下：

（1）分析圖12 及表5在p= 1，q= 0 時可以得出，決策者在不考慮滯空時間代價，只關注目標價值的情況下，無人機救援序列中沒有重點目標T8，因為其初始價值參數為0.6 較小，衰減參數為較大的0.9，并且離基地的距離較遠，其價值衰減嚴重，當無人機數量不足時，相對于其他重要目標救援的價值較小，進一步驗證了目標價值隨時間變化是決策者在進行任務規劃時必須要考慮的因素，圖14、圖15 中較遠的重要目標沒有被救援也間接說明了所提因素。

（2）分析圖16、圖17 及表5在p= 0，q= 1 時可以得出，決策者在不考慮目標價值大小，只關注滯空時間的情況下，算法按照無人機最大載彈就近救援任務目標，滯空時間最短，符合決策者意圖，驗證了算法的有效性。

（3）對比圖12、圖14、圖16 及圖13、圖15、圖17 和表5可得出，因目標函數中目標價值收益取負相關（即“-p”），則當目標價值收益權重系數p變小，而滯空時間權重系數q變大時，無人機對重點目標的救援數量呈現遞減趨勢，無人機救援目標總價值減小，又滯空時間權重系數q決定的總路徑代價在減小，使得無人機的飛行安全價值增加。說明兩種算法都可以有效根據決策者的意圖通過調整權重系數對救援任務進行規劃。

（4）分別對比圖12 和圖13、圖16 和圖17、圖14 和圖15 以及表5中兩種算法在權重系數相同情況下的相關數據可得，在只關注目標價值時所提算法目標總價值高于現有算法1.4%；只關注滯空時間時所提算法的滯空時間短于現有算法4.9%；當滯空時間和目標價值的權重系數都為0.5 時所提算法的滯空時間短于現有算法6.5%，同時目標總價值高于現有算法3.2%。說明所提改進ABC 算法的尋優能力高于現有的MPHGA 算法。

5 結 論

針對當前多無人機對多火點火場滅火救援任務規劃中，因目標價值時變而導致任務規劃效率低下的問題，提出了一種基于改進ABC 的任務規劃算法，并通過仿真實驗驗證了算法的有效性，主要得到以下結論：

（1）在考慮到目標價值時變性的基礎上，提出了一種目標價值隨時間變化的多無人機對多火點火場滅火救援任務規劃模型，該模型相對于現有模型具有更強的普適性。

（2）在目標價值非時變，且救援資源滿足任務要求的條件下，改進ABC 算法可以有效解決多無人機對多火點火場滅火救援問題，其尋優效率和尋優能力均優于現有的MPHGA 算法；

（3）當目標價值時變且救援資源不足時，在使用相同權重系數決策模型的條件下，改進ABC 算法與現有算法進行對比，目標總價值相對提高，滯空時間相對減少，驗證了所建模型的普適性以及所提算法的高效性。