基于AC-DSDE進化算法多UAVs協同目標分配

黃 剛 李軍華

多無人機協同目標分配優化問題(Multi-UAV cooperative target allocation optimal problem,MUCTAOP)是指在復雜任務環境中,為無人機編隊分配一個或一組有序任務,即對有限的UAVs 資源進行合理的分配,同時編隊整體效率達到最優[1].文獻[2?4]指出多機協同目標分配優化問題具有協同性較高、計算難度大、復雜度高等特點.在目標分配過程中,既要考慮飛行器的性能差異、戰場勢態的復雜性、任務執行權重等因素;還需要考慮可行的飛行代價、合理的分配算法及各種協同約束條件.

近年來,為了解決多機協同目標分配問題,研究者們提出了很多優秀算法.這些協同目標分配算法主要可以分為三類:

1) 基于數學規劃法的協同目標分配

數學規劃法是解決集中式分配問題的經典方法;在處理維數較低的分配情況時,該方法簡單靈活,求解速度較快;但在處理維數較高的情況時,求解的難度呈指數級增長,且要求已知研究對象所有的信息,將復雜作戰環境信息過度簡化,因此僅適合低維的簡單任務環境問題求解.例如匈牙利算法[5]、混合整數線性規劃法(Mixed integer linear programming,MILP)[6]、動態規劃法[7].

2) 基于協商法的協同目標分配

協商法能夠有效解決分布式目標分配問題,該類算法計算靈活,可以將不同層次的分配問題,在各個節點上進行分布處理.但在復雜任務環境中,隨著分配規模的增大,系統的魯棒性較差;同時,對協同約束的處理能力較差,致使其實現效果偏差較大.例如基于合同網的協商算法(Contract net based negotiation algorithm,CNBNA)[8],基于共識捆綁算法(Consensus-based bundle algorithm,CBBA)[9].

3) 基于進化算法的協同目標分配

該類算法是建立在自然選擇與群體遺傳基礎上的尋優算法,實質上遵循“優勝劣汰”和“適者生存”的思想,具有較高魯棒性和廣泛適用性.但是該類算法容易出現局部最優解,收斂速度較慢,以及停滯等現象[10?13].例如遺傳算法[14]、粒子群算法[15]、蟻群算法[16]、差分進化算法[17]等.

由于人們對無人機系統需求不斷提高,尤其是三維真實環境和異構多無人機體系構建,使該領域的研究更注重復雜高精,密切貼合實際等要求.數學規劃法與協商法在目標分配過程中都簡化了三維真實環境.進化算法靈活的編碼結構適合復雜三維問題的建模和求解[18].因此,進化算法逐漸成為多機協同目標分配研究方法之一.其中差分進化算法(Differential evolution algorithm,DE)運行穩定、收斂速度較快、空間復雜度較低,在處理高維問題中顯示出較好的結果.因此,本文重點研究基于DE的多無人機協同目標分配.

盡管DE 算法已經很好地處理多無人機協同目標分配問題,但在處理高維復雜環境下多機協同目標分配仍然存在如下難點:

1) 現用的進化策略進行目標分配求解時,往往只關注優化的某一個方面,選擇適合探索(尋找更多全局最優區域)和開發(加速收斂到最優區域速度)的適當繁衍方案是一個兩難選擇.例如,具有高隨機性的變異方案側重于探索,而貪婪的變異方案側重于開發,這就導致了在解決組合優化問題時存在不足.針對不同策略的改進和混合,以平衡探索性與開發性也是目前的一個難點.

2) 如何構建符合實際問題約束函數,文獻[14,17?18]采用了大量的約束,但文獻中仍假設無人機具有相同航程,不變的速度;雖然簡化了問題的復雜度,但忽略了實際戰場中異構UAV 自身不同的性能.因此構建合理實際的約束函數才更符合真實優化目標的需要.

為解決這些難點,本文提出適用于三維環境下多無人機協同目標分配的近似聚類混合雙策略差分進化算法(Approximate clustering dual-strategy differential evolution algorithm,AC-DSDE).該方法有助于平衡種群的多樣性與收斂性;然后,結合歸檔技術的代間變異方法取代原來的隨機滅絕,以增加搜索覆蓋范圍的可控性;最后,構建加權混合適應度函數,在文獻[22]的基礎上,限制無人機載彈量,即限制無人機可執行的任務數.其方法的主要特征和優點描述如下:

1) 首先,根據父代種群適應度值將個體分成“開發性個體”與“探索性個體”兩個子種群,“探索性個體”能夠有效識別問題空間中的最優解區域;“開發性個體”能夠加速優化收斂的速度.通過這種方式,在進化過程中可以根據不同性質的個體指導種群的進化.其次,采用混合雙策略變異方案,使每個個體根據搜索進程,動態調整變異策略,有助于探索性與開發性達到平衡.然后,結合歸檔技術與代間變異率來儲存一定數量的較優收斂的個體,避免進化過程中種群的隨機變異,導致已經搜索到的優解變得無效;同時建立選擇概率函數,選擇一定數量的“探索性個體”與“開發性個體”,有助于收斂的過程中跳出局部最優解.

2) 構建加權混合適應度函數,將估計航程代價、航程時間和約束違背量之和作為適應度函數;加入載彈量約束,限制無人機巡游模式中執行目標數,將問題的約束作為懲罰函數應用于進化算法的重要評價階段,使得運行過程更加符合真實的戰爭環境.

1 相關工作

1.1 差分進化算法

差分進化(Differential evolution algorithm,DE)算法[17]類似于很多經典的進化算法,是一種高效的全局優化算法.種群中每個個體對應一個解向量,通過不同的突變策略產生新的個體,交叉算子根據個體與目標個體進行混合,生成實驗個體;選擇算子根據實驗個體的適應度值與目標個體的適應度值相比較,決定下一代個體.在算法終止前,變異、交叉和選擇構成了DE 的主循環.

1.1.1 初始化種群

在解空間中隨機均勻生成NP個個體:

式(1)與式(2)中NP代表種群的大小,D表示解空間的維度,表示種群中第i個“個體”的第j個“基因”的下界,表示種群中第i個“個體”的第j個“基因”的上界,xj,i(0) 表示第0 代中第i個“個體”的第j個“基因”,rand(0,1)表示在(0,1)區間內均勻分布的隨機數.

1.1.2 變異

初始化種群后,DE 算法通過變異算子從種群中隨機選取兩個個體作差,所得的差向量加權后與第三個個體求和產生變異個體;其中,針對不同的問題有不同的變異策略,這些變異策略影響著種群的進化.下面列出了5 種常用的變異策略:

1) DE/rand/1

式(3)～ 式(7)中,r1,r2,r3,r4,r5 是在[1,N]中隨機選取的5 個整數且r5,xi(g) 表示第g代種群中第i個個體,xj,best(g)表示第g代種群中最好的個體,vj,i(g+1) 表示變異個體.參數F是縮放因子,F值的大小直接影響算法的全局尋優能力.F越小,算法對覆蓋問題空間精細搜索能力更好,但收斂速度會變慢.F越大,收斂速度更快,算法能夠跳出局部最優,但可能出現丟解的情況;同時F值的大小影響種群的多樣性[17].

1.1.3 交叉

在變異之后,DE 通常執行二項式交叉操作,交叉是由交叉率CR決定,其從xj,i(g) 和vj,i(g+1) 進行部分交換以形成新的試驗向量uj,i(g+1) :

式(8)中,CR是交叉率,決定子代、父代與中間變異體之間交換個體基因大小程度.CR的值越大,種群的多樣性隨之增加;CR的值越小,種群的多樣性也會減少,不利于全局尋優.

1.1.4 選擇

DE 采用貪婪算法來選擇進入下一代種群的個體,該算子從試驗向量uj,i(g+1) 和原始向量xj,i(g)中選擇更好的個體進入下一代:

式(9)中,f(x) 是根據具體問題構建的適應度函數.例如,構建目標函數,對于求最大化問題時,具有較高適應值的向量被選擇到下一代.

1.2 MUCTAOP

多無人機協同目標分配最優問題,旨在多任務分配過程中求解最小的航程代價.文獻[18]指出多機協同目標分配是一個多模式、多約束、計算難度大,雜度呈幾何級增長的最優化NP 問題.這就要求必須對目標分配問題進行統一建模,明確飛行器執行的層次和階段,才能獲得較好的分配結果.

Ramirez 等[2]提出了加權隨機策略生成突變的新個體,該策略將搜索的重點放在找到解空間中最好的解,雖然提高了收斂速度,但忽略了種群的多樣性.Ramirez-Atencia 等[19]提出多目標遺傳算法解決協同分配問題,該方法通過變量兩兩組合(飛行距離、飛行時間、飛行數量、燃料消耗),根據評級的方式,獲得了較好的分配方案.Wang 等[20]以智能體加速度作為控制輸入,考慮了限制加速度和速度的物理約束,提出了基于梯度的算法以最小化性能度量并確定最佳軌跡.魏政磊等[21]采用了灰狼優化(GWO)算法對多無人機任務分配模型進行求解,該方法在二維仿真場景中取得了較好的效果,但未考慮三維復雜場景.Zhao 等[22]研究了三維環境中多機協同統一分配方法.建立仿真戰場環境,在研究三維環境中多無人機協同目標分配具有較好的指導作用;因此本文在該建模的基礎上進行擴展,加入了無人機載彈約束,即限定了無人機可執行目標點的個數.

MUCTAOP 的場景具體描述為在復雜的三維環境中攻擊一組目標的一組無人機N={U1,U2,···,Un}.該問題的目的是找到一組分配序列M={T1,T2,···,Tm},其具有最短的估計航程代價、最短的飛行時間和最小的約束違背.其典型的場景和仿真環境如圖1 所示.

圖1 中三維仿真場景包含10 架UAVs 和10 個目標點,圓圈代表無人機的位置坐標,五角星代表目標點的位置坐標,威脅障礙物包括山地形與雷達輻射區(半球型)的結合.無人機與目標點的對應關系由垂直切面與山地形的交線和可飛行航跡組成,即為圖中顯示的實線部分.

圖1 MUCTA 在三維任務環境中的場景Fig.1 Simulation diagram of MUCTA in a three-dimensional environment

2 AC-DSDE For MUCTAOP

2.1 隨機分組和自選分組

在解決多機協同目標分配時,種群中的個體即為備選解,備選解的優劣直接影響搜索算法尋優效率的高低.因此在進化之前需要對種群進行有效地劃分.劃分方法有兩種:隨機分組和自選分組;種群中個體隨機分組,旨在種群中的個體盡可能探索到種群的未知區域,對空間有較大的覆蓋性.但是該方法不能快速搜索到最優解,甚至出現不收斂的現象.例如Crowding 聚類小生境方法[24],該方法引入了新的參數CS(聚類大小),設置參考點R,在種群中找到最近的個體X到R,X及其最近的CS?1 個體形成新的子種群,流程如算法2 所示:

自選分組方法如Speciation 聚類小生境方法[24?25].本文結合該方法引入父代種群的適應度值,從每一代中,選取整數作為聚類大小CS,小生境數為NP/CS.將父代種群適應度值進行排序,最好的個體定義為參考點,參考點及其近鄰CS?1 個個體形成新的子種群,流程如算法3 所示:

從“探索性”子種群中挑選個體可以幫助保持種群的多樣性,從“開發性”子種群中選擇個體可以幫助快速收斂到最優個體.具體操作方法如下:將整個種群劃分為若干個子種群,然后根據個體的適應度將每個子種群細分為數量相等的部分.如圖2 所示,父代種群中包含“探索性個體”和“開發性個體”,首先將父代種群進行排序,設定聚類大小為CS=2,形成兩個子種群.

2.2 動態混合進化策略

上節已經將種群劃分成“探索性”與“開發性”兩種不同的子種群.探索初期,隨機搜索的探索性應該比精細化搜索的開發性比重大,選用DE/rand/2 快速識別空間中最優解的區域,然后選用DE/best/2 優化收斂的速度,確保在搜索的最后階段,精細搜索趨于主導地位.因此,探索性與開發性得到了平衡,算法的整體性能得到了提高.混合策略產生新個體如式(10)所示:

此外,之前曾分析過縮放因子F值的大小直接影響算法的全局尋優能力.F越小,算法對覆蓋問題空間精細搜索能力更好,但收斂速度會變慢.F越大,收斂速度更快,算法能夠跳出局部最優;因此,在產生新個體的過程中,設定動態縮放因子Fd代替靜態縮放因子F非常重要.Fd設置如式(11)所示:

圖2 個體分組Fig.2 Individual grouping

2.3 歸檔技術

本節結合了代間變異率與歸檔技術取代了原先的隨機重置,以增加搜索范圍的可控性.在進化過程中,最優解在整個種群中反映的信息量較低,隨著迭代次數的增加而極可能被覆蓋,使之前的搜索變得無效,導致信息的不連貫和資源浪費.因此在世代間滅絕操作時,建立合理的選擇算子概率模型與使用歸檔技術非常有必要.在存檔中保存當前種群中一定數量的較優個體,將其它的普通個體全部重置,直到搜索結束.保存收斂的個體和代間變異可能找到的最優解,避免種群突變帶來的資源浪費.

選擇算子概率如式(12)所示,適應度越大的個體被選中的概率越大,同時設置代間變異率(Intergenerational mutation rate,IGMR)為0.3.該方法能避免進化過程中優秀個體的徹底消亡,在保持種群多樣性的同時,也加速了收斂速度.

圖3 (a)表示每代計算的個體適應度值,經過選擇算子計算后得出較好的收斂個體存儲在歸檔庫圖3 (b)中.

2.4 完整AC-DSDE 算法框架如下:

圖3 個體分組Fig.3 Individual grouping

2.5 目標分配模式

多機協同目標分配可按UAVs 和目標點對應數量進行分類.本文中取N,M分別代表無人機的數量與目標點的數量,按數量對應關系可分成以下三種不同的模式[22]:

1) 模式1:當N=M時,該模式任務分配關系較為簡單,每架UAV 分配一個目標點,每個目標點分配一架UAV,UAV 與目標點是一一對應的關系;該模式計算復雜度較低,求解的關鍵在于分配過程中如何避免目標競爭引發的沖突,如何利用協同降低毀傷概率,使總的適應度值最大.

2) 模式2:當N>M時,該模式任務分配關系較為復雜,每一個目標點可以分配多架無人機,每架無人必須執行一個目標點,UAVs 與目標點是多對一的關系;該模式對應關系不平衡,導致計算復雜度較高,問題求解的關鍵在于嚴格的時間約束導致多機協同困難.

3) 模式3:當N

2.5.1 分配模式統一建模

多機協同目標分配等同于運籌學中的指派問題.現假設有N架無人機,打擊M個分布在不同位置的目標.要求構建目標函數考慮航程距離最短、總飛行時間最少和約束違背最小,并且能夠統一處理N=M、N>M和N

其中,d(i,j)是無人機i到目標點j的距離,該距離利用垂直切面法估算航程代替直線,該方法雖然不是最短的航程,但是充分考慮了三維地形信息,比直線距離更接近最優航程;wj是目標j的權重且0

2.5.2 協同約束函數及協調關系:

1) UAV 與目標點決策變量約束:當N ≥M時,UAVs 數量大于等于目標點的數量,此時任務決策為:每架UAV 必須執行一個目標點,每個目標點必須被一架UAV 執行;當N

式(15)和式(16)分別表示了兩種不同決策對應的關系.

2) 最大航程約束D(km) :不同的模式下,最大航程代價指所有分配關系的估計航程代價的總和;該約束體現了各UAVs 自身性能,比如油耗、有效通信等.

式(17) 中d(i,j) 表示估計航程代價,Di表示各UAVs 的限定的最大航程距離;式(18)表示無人機i執行任務j,若無人機i超出其自身限定的最大航程距離將對其進行懲罰.

3) UAVs 最小/最大速度約束V(km/h) :

式(19) 中V(i)min表示無人機i的最小速度,V(i)max表示無人機i的最大速度;式(20)表示若無人機i超出限定的最小速度或者最大速度將對其進行懲罰.

4) 最大航行時間約束T(h) :表示協同分配結果中執行目標耗費時間最長的無人機,最大航行時間也是規劃完成的標志.

根據式(17)最大航程約束與式(19)最大、最小速度約束,可以計算出最大航行時間;式(22)表示若無人機i實際航行時間超出其限定的最大航行時間將對其進行懲罰.

5) UAVs 最大載彈量約束Umissile:該約束體現了UAVs 最大載彈量.即在模式3)中,單架無人機在巡游過程中執行任務數量不可以超過其有效地載荷量.

式(23)表示無人機i的載彈量應小于其最大的載彈量;式(24)表示若無人機i的載彈量超過其最大載彈量將對其進行懲罰.

6) 目標點之間的時序約束Tsort:該約束體現了目標點之間的執行順序,重要的目標點必須優先執行,其他目標點根據其約束依次執行;

式(25)表示目標點j必須晚于目標點j+τ執行,τ為正整數.式(26)表示若目標點Tj,Tj+τ不符合限定執行次序則進行懲罰.

7) 等待時間約束Twait:為了確保模式一與模式二中部分UAVs 同時到達指定目標,允許部分UAVs 等待一段時間后再出發.

式(27) 限定各無人機到達目標的等待時間;式(28)表示各目標點被攻擊時間的交集不可超過時間段σ,通常σ時間段認為是極小的,可根據真實戰場勢態進行調整.

該模型針對三種不同分配模式建立了統一的分配關系.將航程代價、時間代價與約束違背量之和作為適應度函數.在進化前,建立UAVs 與目標點的估計航程代價庫,進化時通過查找估計航程代價矩陣,可以大幅提高計算效率.

3 實驗結果和分析

為驗證改進后的AC-DSDE 算法處理MUCTAOP 有效性,本文在Matlab R2016a 進行多組仿真實驗.實驗包括以下部分:1) 選取數量較少的UAVs 和目標點驗證改進算法的有效性;2) 選取數量較多的UAVs 和目標點驗證改進算法能夠有效處理復雜環境下目標分配;3) 將改進的AC-DSDE與同類算法進行比較.

表1 中“Upos”、“Tpos”、“Rpos”分別表示無人機、目標點和雷達的坐標;“W”表示各目標點的權重;

表2 設定了兩組不同實驗參數.“Un”表示UAVs 的數量,“Tn”表示目標點的數量,“Pn”表示種群的規模,“Gen”代表進化迭代次數.因為差分進化算法是隨機搜索算法,為了驗證解的一致性,本文設置“Num”參數對同一情境下進行多次實驗.

3.1 驗證改進算法的有效性

圖4 顯示了實驗1 分配結果,其中圓圈代表UAVs 的三維坐標,星形代表目標點三維坐標;同時,本文將每個坐標進行編號,以便后續統計分配數據.從圖中看出基于AC-DSDE 算法的多機協同分配能夠在多雷達區域和目標點隨機分布的三維環境中,充分結合了整體山地形,有效地處理三種不同模式下的分配問題.

表3 表示實驗1 中三種不同模式下無人機與目標點最優分配的結果;其中UAV 表示UAVs 分配序列,Target 表示對應的目標點分配序列,Cost 是UAV 與Target 對應的總航程代價,包含了航行距離、飛行時間等.同時,仿真數據均符合三種模式無人機與目標點之間的對應關系.圖4 與表3 表明了改進的AC-DSDE 算法能夠有效處理三種不同的模式,并找到相對應的分配方案.

3.2 驗證算法處理復雜環境的有效性

為驗證算法處理復雜環境的有效性,本節中選取了5 個評價指標對算法的性能進行評價:

表1 實驗初始數據Table 1 Initialization of experimental data

表2 兩組實驗進化參數的設定Table 2 Setting of experimental evolution parameters of two groups

3) 最優代價Cbest:多組實驗中最小代價值;

4) 約束違背:最優解中約束違背量總和占最優代價的百分比,該評價指標衡量了算法的協同性能.

5)“優解”表示陷入局部最優的次數和當前優于平均代價的次數占實驗總次數的百分比.

其中,平均代價和最優代價都是綜合了航程代價、時間代價和各種約束違背量的適應度值.

表4 分別統計了實驗1 與實驗2 的數據,可以得出以下結論:

圖4 三維環境中實驗1 的仿真結果Fig.4 Simulation results of Experiment 1 in a three-dimensional environment

圖5 三維環境中實驗2 的仿真結果Fig.5 Simulation results of Experiment 2 in a three-dimensional environment

表3 實驗1 的分配結果Table 3 Assignment results of Experiment 1

圖6 實驗1 分配結果的單條收斂曲線Fig.6 Single convergence curve of Experiment 1 assignment results

1) 實驗1 算法運行時間較短,且能得到較好的分配結果,數據表明所提出的AC-DSDE 算法能夠有效地處理不同模式下的多無人機協同目標分配問題;

表4 兩組實驗分配結果的統計數據Table 4 Statistics of the results of the two groups of experimental assignments

圖7 實驗1 分配結果的單條和平均收斂曲線對比Fig.7 Comparison of the single and average convergence curves of the results of Experiment 1

2) 實驗2 盡管增加了UAVs 與目標點的數量,算法中的執行效率有所降低,但是AC-DSDE 在有效的時間內搜索到最優解.

3) 各模式中平均代價值與最優代價值接近,表明改進算法搜索的結果接近全局最優解.

4) 較小的協同違背率證明改進算法協同能力較強.較高的優解率說明了實驗發現最優解的可能性較大.

3.3 AC-DSDE 算法的性能

表5 AC-DSDE 與其他算法之間的比較Table 5 Comparison between AC-DSDE and other algorithms

圖8 不同算法的平均收斂曲線Fig.8 Average convergence curve of different algorithms

本節將從單次實驗收斂曲線與多組實驗平均收斂曲線進一步研究AC-DSDE 算法處理多無人機協同目標分配的性能.

1) 單次實驗收斂曲線與多組實驗平均收斂曲線

圖6 中實線表示單次實驗的收斂曲線,并且顯示改進算法進化迭代過程中的最優解以及代間變異隨機搜索到的最優解,分別用圓圈與星號表示.從收斂曲線可以看出代間變異不僅增加了種群的多樣性,而且找到了更多的優解.圖7 是單收斂曲線與平均收斂曲線的對比,單收斂曲線和平均收斂曲線具有相似的收斂趨勢,搜索前期能夠快速收斂到優解區域,后期能夠很快地收斂到最優解.因此ACDSDE 具有較好的收斂性能.

2) AC-DSDE 與同類目標分配算法之間的比較

本節將改進后的AC-DSDE 算法、DMDE 算法[22]與APC-DE 算法[26]進行比較.實驗所采用的進化參數、種群規模、迭代次數相同.表5 中,變量CR表示交叉率,變量MR 表示變異率,變量IGMR 為DE 算法的代間變異率.圖8 是不同算法的平均收斂曲線,表5 和圖8 顯示,AC-DSDE 算法總的航程代價值最小,收斂速度最快,執行時間最短.盡管其他兩種算法都能在一定的時間內找到最優解,但總的航程代價值較高且需要更長的執行時間.

4 總結

本文提出了基于AC-DSDE 混合雙策略差分進化算法以解決無人機協同目標優化分配.首先,為了提高算法的性能,提出了混合雙策略動態變異的方法.該方法根據不同類型的個體選用不同的變異策略,同時構建動態縮放因子Fd,解決目前進化過程中存在的探索性和開發性平衡的問題.然后結合歸檔技術與代間變異方法,在增加了種群的多樣性的同時,也保證了收斂個體不會隨著迭代次數消亡.最后擴展原有的約束條件,增加了UAVs 的載彈量約束,限制UAVs 可執行的目標個數.仿真實驗表明,該方法能夠有效快速地解決多無人機協同目標分配問題,且協同能力強.

對于下一步工作,將著重考慮差分進化算法在多無人機協同航跡規劃方法的研究,如何有效降低三維空間復雜度,獲得關鍵路徑點的集合,保證最終航跡是安全且可行.