求解無人機ISR任務分配問題的離散螢火蟲算法*

康旭超，何廣軍，陳 峰，李興格

(1 空軍工程大學研究生院，西安 710051；2 空軍工程大學防空反導學院，西安 710051)

0 引言

情報偵察和戰場監視是無人機系統主要的作戰任務之一。在實戰中，它面臨著信息不確定性、計算復雜性、時間緊迫性的嚴峻挑戰，要求無人機系統能夠在有限時間內完成任務分配軌跡的優化決策。近年來，遺傳算法、蟻群算法等智能算法相繼出現，為解決多目標任務分配尋優問題提供了解決方法[1,3-4,14]。但對于存在多個情報偵察監視(intelligence surveillance reconnaissance，ISR)任務地點的無人機任務分配問題，隨著任務地點的增多，組合優化規模會出現爆炸增長，無論哪種算法都不可能找到滿足所有目標的最優解，只能在一定時間內找到近似最優解，因此如何能用較短的時間找到近似最優解的任務點規劃路線一直是研究的熱點和難點[2,5,8,17]。

2009年，劍橋學者楊新社根據自然界中螢火蟲的發光行為提出了螢火蟲算法(FA)，這種螢火蟲算法對于解決連續變量的尋優問題具有較好的性能，但無法解決離散問題[6-7]。為了拓展其應用領域，提高算法的運行速度，使算法能夠盡快地收斂于近似最優解，針對多目標規劃問題，文中重新定義了螢火蟲移動機制，提高了收斂速度，引入了變步長移動和多鄰域搜索機制，增加了種群多樣性，便于找到全局最優解。

1 無人機ISR任務分配建模

無人機 ISR 任務分配問題可以定義如下：給定一系列 ISR 任務點，確定一條無人機飛行路徑，在給定的約束條件下，使得無人機從基地出發，在滿足目標要求的情況下遍歷所有任務點，最后再回到基地。在任務分配時，往往需要考慮多個目標，每條路徑都會在一部分目標函數上達到最優。因此，無人機 ISR 任務分配問題實際上是一個多目標規劃問題。根據作戰任務和要求，可以建立如下無人機ISR 任務分配模型。

(1)

2 標準螢火蟲算法

螢火蟲算法(firefly algorithm)源自在夜間模擬自然界中的螢火蟲的自然現象，螢火蟲通過自身散發熒光素與周圍同伴進行交流。一般來說，螢火蟲總會向熒光亮度比其自身亮的螢火蟲方向移動，最終許多螢火蟲會聚集在明亮的螢火蟲周圍[9-11]。

標準的螢火蟲算法使用歐幾里德距離計算方法定義螢火蟲i、j之間的距離

(2)

式中:xi、xj分別代表螢火蟲i、j的空間位置坐標。

螢火蟲主要靠散發熒光素吸引周圍同伴，熒光亮度決定了螢火蟲的移動方向，而螢火蟲的熒光亮度隨螢火蟲間距離的增加逐漸減小，定義熒光亮度

Iij=Iie-γrij

(3)

式中:Iij表示螢火蟲i相對于螢火蟲j的熒光亮度;Ii為螢火蟲i的最大熒光亮度，與我們所設立的目標函數值有關;γ為熒光素揮發系數。

螢火蟲在一定范圍內搜索亮度較自身大的螢火蟲并向其移動，其移動的步長由吸引度決定，吸引度越大，移動步長越大。定義螢火蟲間吸引度

βij=βie-γrij2

(4)

式中:βij表示螢火蟲i對螢火蟲j的吸引度;βi表示螢火蟲i的最大吸引度，同樣與所設立的目標函數值有關。

確定了移動方向和移動步長，螢火蟲便通過向熒光亮度更亮的螢火蟲移動，不斷更新自身位置坐標，達到尋優的目的。定義螢火蟲i向螢火蟲j移動的位置變換

xi=xi+βij(xj-xi)+α(φ-0.5)

(5)

式中:α為步長因子，α為在[0 1]區間的隨機數。式子表示螢火蟲i沿著螢火蟲j的方向移動不大于相距距離的步長；α(φ-0.5)是擾動項，目的是增加種群的多樣性，防止算法過早的陷入局部最優[18]。

3 離散螢火蟲算法

3.1 算法描述

標準的螢火蟲算法對于解決連續變量的尋優問題[12,16]有較好的效果；對于離散問題，通常先編碼再求解。針對無人機ISR任務分配問題，編碼方式定義如下：

設螢火蟲種群數為m，對n個ISR任務點進行編號x(x=1,2,…,n)，第k只螢火蟲代表一個編號序列Πk(X) (k=1,2,…,m)，表示無人機飛行路徑，其中X={1,2,…,n}為數字排列。

對螢火蟲的移動方向和移動距離問題需要重新定義，為了方便描述，引入交換子，其概念如下[15]：

螢火蟲移動方式定義為：若螢火蟲i向螢火蟲j移動，則Πi(X)向Πj(X)變換。文中采用順序交換的方法，首先判斷Πi(X)與Πj(X)的起始任務點是否相同，即Πi(1)是否等于Πj(1)，若相等，則Πi(1)不發生改變，交換子q1=(1,1)；若不相等，則通過一步交換子計算，更新Πi(1)，使Πi(1)=Πj(1)。同理，依次判斷Πi(a)是否等于Πj(a) (a=1,2,3,…,n)，得到交換子qa并更新Πi(a)，使Πi(a)=Πj(a)。令實際引起序列變換的交換子個數作為螢火蟲之間的距離。一個n維的序列按照順序交換的方法會產生n個交換子，實際引起序列變化的交換子個數為n*(n*≤n)，螢火蟲之間的距離：

rij=n*

(6)

βij=rand(1,n)

(7)

螢火蟲i的位置更新公式為：

Ai(t+1)=Ai(t)°(a1,a2,…,aβij)

(8)

為了減小算法的計算量和復雜程度，采用逐個螢火蟲尋求最優的方式，選取一只螢火蟲依次向所有比其更優的螢火蟲方向移動，即每一次迭代完成一只螢火蟲的尋優，通過m次迭代完成m只螢火蟲的尋優，最終尋得全局最優解。為了避免算法計算過程中過早取得局部最優解，增加了多鄰域搜索機制，設螢火蟲Πi為一個n維序列，文中定義了如下幾種搜索機制：

①隨機變異搜索

②隨機插值搜索

③隨機逆轉搜索

3.2 算法步驟

Step1 初始化螢火蟲種群數m、熒光素揮發系數γ、最大迭代次數M及每個螢火蟲序列Πk(k=1,2，…,m);

Step2 選取目標函數作為螢火蟲Πk的最大熒光亮度Ik(k=1,2,…，m)，并計算螢火蟲i與螢火蟲j的相對熒光亮度Iij(i=1,2,…，m;j=1,2,…，m)；

Step3 取螢火蟲Π1，計算Π1變換為Π2的交換子集合Q12及交換子個數n，Q12={q1,q2,…，qn}，確定Π1與Π2的空間距離r12;

Step4根據式(3)計算Π2對于Π1的相對熒光亮度I21，判斷I21是否大于Π1的最大熒光亮度I1，若是，則第1只螢火蟲向第2只螢火蟲移動，移動步長按照式(6)計算取得;

Step5 更新第1只螢火蟲序列Π1和最大熒光亮度I1;

Step6 判斷I31是否大于I1并決定是否移動，更新Π1和I1。以此類推，第1只螢火蟲Π1依次與Πk(k=1,2,…，m)的螢火蟲進行比較;

Step7 采用三種鄰域搜索機制對Π1的鄰域搜索s次，選取目標函數最優值作為第一只螢火蟲的尋優結果fbest=fbest(1)；

Step8 返回step3對第2只螢火蟲Π2進行同樣的操作，得到Π2的最優值fbest(2)，若fbest(2)優于fbest(1)，則fbest=fbest(2)。以此類推進行M次迭代可以得到M只螢火蟲的局部最優值，進而尋得全局最優值fbest。

4 仿真實驗與分析

以某型無人機的實際應用為背景，構建一個多目標無人機ISR任務分配實例。所有ISR任務點和無人機基地的坐標如表 1所示。

表1 所有 ISR 任務位置點坐標

本例中，無人機任務分配模型主要考慮3個決策目標，即無人機的任務執行時間(Time/hours)、無人機的任務威脅(Threat)以及無人機執行任務的耗油量(Fuel/tons)。

第一個決策目標設為：尋找一條完成任務時間最短的飛行序列。可建立以下具體目標函數

(9)

式中：v為無人機飛行速度，令v=350 km/h，n為任務點個數。

第二個決策目標設為：尋找一條受到敵方威脅最小的飛行序列。建立目標函數

(10)

式中：Δ為最大威脅系數，令Δ=0.8。

第三個考慮的決策目標設為：尋找一條飛行序列，使得無人機完成任務后消耗的耗油量最少。建立具體目標函數

(11)

在本例中，主要考慮無人機執行 ISR 任務的燃油約束條件，假定該型無人機的最大載油量為 7 t。于是，可得到具體的無人機ISR任務分配模型

(12)

采用線性加權法對多目標問題進行處理，三個決策目標重要性權重依次為λ1、λ2、λ3，假定權重比λ1∶λ2∶λ3=3∶1∶1，應用文中所提的離散螢火蟲算法進行仿真，結果如下。

表2 計算結果

圖1 無人機飛行序列示意圖

圖2 算法收斂曲線比較

由圖2仿真結果可知:相對于傳統的遺傳算法，文中提出的離散螢火蟲算法具有較快的收斂速度和較高的可靠性。

為了驗證變步長大小對尋求目標最優解的影響，分別對采用固定步長(步長為2、步長為10)和變步長時的算法進行仿真，如圖3所示。

仿真結果表明：步長較大時，算法雖然很快收斂，但容易陷入局部最優解；步長較小時，算法雖然能夠取得全局最優解，但收斂時間過長；采用變步長的方法，彌補了兩者的缺陷，既能尋得全局最優解又能在較短時間內收斂。

圖3 步長大小對目標函數尋優的影響

為了驗證多鄰域搜索對算法尋取全局最優值的影響，分別取鄰域搜索次數s=0(無鄰域搜索),s=1,s=2,s=3，如圖4所示。

仿真結果表明：s=0時，目標函數容易陷入局部最優解，增加多鄰域搜索的方法使得目標函數更容易取得全局最優值，且隨s的次數增加，算法的收斂性加快。

圖4 鄰域搜索次數對目標函數尋優的影響

5 總結

針對解決有多個ISR任務點的無人機任務分配問題，提出了一種解決離散問題的螢火蟲算法。重新定義了螢火蟲移動機制，通過引入交換子將目標尋優過程轉化為飛行序列的變化過程。采用逐個螢火蟲尋求最優的方式，減少計算量和復雜性。為防止過早陷入局部最優，采用變步長移動和多鄰域搜索的方法，增加了種群多樣性，提高了收斂速度。仿真結果表明:離散螢火蟲算法在種群規模較小、迭代次數較少的情況下能夠找到較為滿意的解，具有較好的收斂性和尋優性。