不確定條件下基于煙花算法的無人機任務分配

余稼洋,郭建勝,張曉豐,解 濤,姚 賽

(空軍工程大學 裝備管理與無人機工程學院, 西安 710051)

0 引言

現代戰爭逐步呈現出“無人化”趨勢,無人機因其速度快、零傷亡、全天候等優點廣泛應用于軍事領域,對空戰模式產生革命性的影響[1]。如何在復雜戰場環境下,對無人機作戰任務進行分配,使之在滿足限定條件下,得到決策者滿意的任務分配方案,成為當前無人機應用領域研究的一個熱點。

目前,絕大多數無人機任務分配問題的研究都基于參數確定這一假設。但是,受虛假情報、惡劣天氣等不確定因素影響,無人機任務分配過程中的油耗量、飛行時間、飛行威脅等不可測,造成確定條件下的任務分配方案失去最優性。模糊集理論、魯棒優化理論和概率論是解決不確定問題的常用方法,但是模糊集在數學上不具有自洽性[2],魯棒優化求解的結果相對保守[3],應用概率論的前提是不確定變量的概率分布可以獲取,但在實際作戰環境中缺乏采樣數據,需要根據相關領域專家對不確定變量進行評估以獲取相關參數信息。為此,Liu[4-5]提出了不確定理論,并有相關學者開展了大量理論和應用研究[6-8],無人機任務分配問題涉及較少。因此,本文中主要研究帶時間窗的不確定無人機多目標任務分配問題。由于目標函數和約束中均包含不確定變量,傳統的優化方法無法解決此問題。本文中基于不確定理論,建立一種新的不確定無人機任務分配模型,分別引入期望值準則和機會約束將帶有不確定變量的模型轉為確定型優化模型。

當前求解任務分配問題的方法主要有窮舉法、約束規劃法、圖論法、列表法及聚類法等,但這些方法在計算實時性、準確性等方面仍有較大提升空間。煙花算法(fireworks algorithm,FWA)是譚營于2010年提出的一種智能算法,主要用于求解連續空間的單目標優化問題,其被證明具有良好的優化性能[9]。文獻[10]中引入量子的思想,提出了一種自適應旋轉角的量子煙花算法;文獻[11]中將遺傳算法和煙花算法結合,并增加模擬退火流程;文獻[12]中引入維度方差、禁忌搜索策略和輪盤賭策略改進變異算子和選擇算子。文獻[10-12]中對算法的搜索速度和求解精度做出大量貢獻,但只能解決單目標優化問題。為將煙花算法應用到多目標優化問題上,文獻[13]中以各目標適應度值乘積大小判斷解的優劣以確定火花爆炸半徑及數量,并引入Pareto優越理論改進選擇策略;文獻[14]中以規范后的各目標適應度值之和判斷解的優劣以確定火花爆炸半徑及數量;文獻[15]中引入Pareto優越理論和精英反向學習策略改進算法的選擇策略,以上文獻雖成功的將煙花算法拓展到多目標優化問題求解中,但簡單地以各目標適應度值乘積或求和來確定爆炸算子中火花半徑和數量,可能造成煙花盲目搜索,降低搜索效率;此外,算法在求解精度上仍有較大提升空間。因此,本文中采用冪律分布函數改進爆炸算子,以適應度等級確定火花爆炸半徑和數量;此外,引入Levy變異算子并結合多目標優化理論和兩階段搜索策略提出了一種兩階段搜索的多目標煙花算法(MLFWA),避免了算法的盲目搜索和早熟收斂,有效提高了算法搜索速度和全局搜索能力。最后通過實例仿真驗證了算法和模型的有效性和可行性。

1 不確定條件下無人機任務分配問題

無人機打擊任務分配問題是指無人機從基地出發,在相關約束條件下以最小的代價實現對所有任務目標的火力打擊,并回到基地的過程。該問題可表示為無向完全圖G={V+,E+}上的不確定整數規劃問題。

1.1 模型構建

1.1.1目標函數

實際戰場環境中,無人機在路徑(i,j)上受電磁干擾、地形等帶來的威脅ηij和飛行時間tij無法準確得知,兩者均為不確定變量。在任務分配問題中,決策者希望無人機以最小代價完成任務。一方面,需要降低無人機受到的威脅代價F1。假設ηij是滿足正態分布的一系列獨立不確定變量,即ηij～N(eij,σij)。故威脅代價F1可表示為

(1)

(2)

(3)

(4)

其中:λ為延遲懲罰系數;i為無人機的前序任務。

1.1.2約束條件

無人機打擊任務分配約束主要包含以下3類。

1) 燃油約束

受限于無人機性能,單架無人機攜帶燃油數是一定的。受飛行高度、速度等因素影響,無人機在路徑(i,j)上的單位飛行距離油耗εij無法確定,為不確定變量。為確保無人機能夠安全返航,必須滿足

(5)

式中,Ak為單架無人機攜帶的燃油總量。

2) 任務協同約束

對于每個目標,其打擊任務只能被一架無人機執行,即

(6)

3) 路徑起止約束

每架無人機都是從基地出發執行任務,最終返回基地,故路徑起止約束為

(7)

1.2 模型等價轉換

顯然,模型中求解空間的不等式約束及目標函數中均包含不確定變量,無法確定可行解集和實現尋優,屬于不確定規劃問題。

期望值是不確定變量的重要統計特征,期望值模型是不確定規劃的常用處理方法。Liu[4]引入不確定機會約束,以最小化目標函數的期望值為準則,構建了期望值模型以解決不確定規劃問題。式(8)是期望值模型的數學表達式。

(8)

其中,M{Gi(x,ξ)≤0}≥αi是置信度水平為α的不確定機會約束,確保了模型有確定的可行解集。由此,無人機打擊任務分配期望值模型為

(9)

2 兩階段搜索的多目標煙花算法

2.1 多目標煙花算法

2.1.1編碼方式及初始化

在無人機打擊任務分配問題中,每個煙花均代表一種可行的任務分配方案。煙花xi的長度為n,即需打擊目標數,以確保每個任務均能分配到無人機且不會重復分配。本文中采取半連續編碼,整數部分表示執行任務的無人機編號,根據小數部分值大小確定無人機執行任務的順序。以2架無人機打擊5個目標為例,煙花(1.7,2.5,1.3,2.1,2.7)表示無人機1依次打擊目標3、1,無人機2依次打擊目標5、2、4。

然后,根據煙花數量N初始化解空間,并計算初始解的適應度值。煙花的初始解產生方式為

xi=xmin+(xmax-xmin)rand(0,1)

(10)

其中:xi=(xi1,xi2,…,xin)為第i個煙花的位置;xij為第i個煙花在第j維度上的值;xmax和xmin表示火花的上下界。

2.1.2爆炸算子

傳統FWA中,煙花產生的火花數和振幅依賴于煙花種群的適應度值,且煙花間差異不可控。雖然其限制了極端煙花產生的火花數,但未考慮其對種群中其他煙花的火花數的影響。此外,在多目標問題中,帕累托解不分優劣,無法得到最大和最小適應度值,故無法簡單地根據適應度值大小計算煙花產生的火花數及振幅。故考慮使用冪律分布函數,按照煙花適應度值高低將搜索種群劃分為若干等級,以此計算煙花產生的火花數

(11)

式中:k為煙花的適應度等級;a為分布形狀系數,其值越大,高適應度值的煙花產生的火花數越多。

2.1.3變異算子

煙花算法采用高斯變異以增加種群多樣性。但高斯變異擾動范圍較小,且其變異范圍為整個實數區間,對于搜索范圍為正實數區間的任務分配問題會造成重復搜索,大大降低了變異效率。

圖1和圖2給出了Levy分布、柯西分布和高斯分布的概率密度函數和分布函數,可以看出Levy分布的波峰更高,尾翼更寬,且其變異范圍為正實數區間,增大了算法的搜索范圍及搜索效率。Levy分布的概率密度函數及分布函數分別為

圖1 3種分布的概率密度函數曲線Fig.1 Probability density function curves for each distribution

圖2 3種分布的分布函數曲線Fig.2 Distribution function curves for each distribution

(12)

F(X;u;c)=P{X≤x}=

(13)

其中:u為位置參數,影響分布曲線的左右平移,函數定義域為[u,+∞];c為標度參數,其數值越小,Levy分布的波峰越高,尾翼越寬。

引入Levy變異算子的火花變異公式為

x′ik=round(β×xik)

(14)

其中, β為服從Levy分布的隨機數。

2.1.4映射

考慮到部分煙花爆炸和變異產生的火花值可能會超出可行域,考慮使用模運算將超出可行域的火花映射到可行域內

(15)

式中:| |表示絕對值運算;mod表示模運算。

2.1.5選擇

對于多目標優化問題,解集質量和解集的覆蓋范圍是判斷帕累托解優劣的標準[16]。算法迭代過程中選取適應度值好、分布分散的煙花更有利于尋優。首先建立容量為W的外部檔案室,用以存儲迭代過程中產生的煙花;其次,根據Pareto優越理論用非支配排序法將煙花劃分為不同的非支配等級[17],針對同一等級煙花,根據式(16)計算煙花的擁擠度距離,非支配等級越小,距離越大,煙花越好,即任務分配方案越好,選取最優的N個煙花作為下次迭代的初始煙花種群。若檔案室中煙花的數量超出上限W時,按照非支配排序和擁擠度距離選擇最優的W個煙花留在檔案室,刪除多余煙花

(16)

式中:u為當前煙花鄰域內煙花數;dmin和dmax為煙花種群最近和最遠距離。相較于傳統擁擠度計算方法,式(16)能夠反映出當前煙花在種群中的整體分布,能夠更好地度量煙花的領域分布,有利于在整體和局部上保證煙花的多樣性。

2.2 兩階段搜索策略

為更好更快得到帕累托解,提出一種兩階段搜索方式,如圖3所示。第一階段為快速搜索階段,其目的為加速搜索;第二階段是尋優搜索階段,其目的為提高解的多樣性。

圖3 兩階段搜索示意圖Fig.3 Two-stage search diagram

2.2.1快速搜索階段

第一階段主要目的是加快算法搜索速度,使種群迅速接近帕累托前沿,故用當前種群到實際帕累托前沿的距離指導算法搜索。但在實際中,絕大多數多目標優化問題的帕累托解不易獲取,無法準確計算種群到帕累托前沿的距離。故考慮引入一個參考點,用當前種群到參考點的距離代替其到真實帕累托解的實際距離,以指導算法搜索。

參考點一般選取搜索域的邊界或搜索域外的點,否則會造成搜索種群無法接近帕累托前沿。如圖4所示,x1,x2,x3,x4,x5為搜索種群,A、B、C、D表示不同的參考點。其中A和B位于搜索域內,C位于搜索域邊界,D位于搜索域外。當選取B、C、D作為參考點時,種群會朝著帕累托前沿搜索;當選取A作為參考點時,粒子x1,x2朝著帕累托前沿搜索,但粒子x3,x4,x5逐漸遠離帕累托前沿,造成搜索效率降低。

圖4 不同位置參考點搜索過程示意圖Fig.4 Schematic diagram of reference point search process at different locations

2.2.2尋優搜索階段

第一階段雖然加速了種群對帕累托解的逼近,但也導致種群過度集中(見圖3)。為使算法能夠快速找到具有多樣性的解,需要增強算法在單次搜索過程中的搜索范圍,故將傳統FWA中的高斯變異算子換為變異范圍更廣的Levy變異算子。

2.2.3搜索轉換策略

當快速搜索的種群收斂時,需要自動進入尋優搜索階段,如何設計合適的搜索階段轉換指標是該算法的關鍵問題之一?？紤]以子代個體支配父代個體數的均值作為階段轉換指標。當子代個體能夠支配較多父代個體,認為當前種群在快速接近帕累托解;否則,認為當前種群的搜索正在收斂。當滿足式(17)時,可以認定種群搜索已經收斂。

ui<α

(17)

式中:ui為子代個體能夠支配父代個體數的均值;α為指標轉換閾值。不同閾值對算法的影響將在第4節詳細說明。

3 實例仿真

3.1 評價指標

多目標算法的性能比較往往比較困難,需要考慮解集質量、算法求解效率、魯棒性等諸多方面。本文中選取超體積指標(Hypervolume,HV)評價算法優劣。HV度量了解集的空間覆蓋情況,能同時衡量算法的多樣性和收斂性。HV值越大,表明帕累托前沿分布越均勻,收斂性越好[16]。HV的計算公式為

HV(A)=[1-f1(xi)][1-f2(xi)]+

(18)

其中,fm(xi)表示解xi的第m個目標函數值。將目標函數值范圍進行歸一化,則有HV(A)∈[0,1]且越接近1表示解集質量越高。

3.2 算法測試

為驗證MLFWA的有效性,在ZDT和DTLZ系列[18]多目標測試函數上驗證算法性能,選取多目標遺傳算法(NSGA-Ⅱ)、基于分解的多目標進化算法(MOEA/D)和多目標粒子群算法(MOPSO)作為對比。其中,DLZT系列測試函數的優化目標數和搜索變量數均可拓展,考慮到本文中研究的是雙目標優化問題,故優化目標數取2。各測試函數特性和問題維度如表1所示。各算法初始種群規模設為100,最大迭代次數為1 000次,外部檔案室的大小為50。

表1 各測試函數的相關參數及特性Table 1 Parameters and characteristics for each test function

為減少隨機因素對算法性能影響,各算法獨立運行50次,得到各算法HV的均值及方差,見表2。算法在測試函數上的帕累托前沿如圖5所示。結果表明,MLFWA算法求解的解集質量及算法穩定性要優于對比算法。

圖5 各算法在測試函數中的帕累托前沿Fig.5 The Pareto front for each algorithm in the test function

表2 各算法HV的均值和方差Table 2 The mean value and variance of HV for each algorithm

表3給出了不同α值下ZDT系列測試函數在階段轉換時的HV指標。結果表明,α值越小,進入尋優搜索階段的搜索種群質量更高。圖6給出不同α值下的MLFWA算法在ZDT1測試函數中第二階段初始解分布。

表3 不同α值ZDT系列測試函數的HV值Table 3 HV value of ZDT test functions with different α

圖6 ZDT1測試函數中不同α值第二階段初始解分布Fig.6 The initial solution distribution of different E values in the second stage in ZDT1 test function

3.3 實例仿真

為驗證本文中提出的任務分配模型及MLFWA算法,設計場景為4架無人機執行14個任務目標。采用NSGA-Ⅱ算法、MOEA/D算法、MOPSO算法和前文提到的MLFWA算法分別進行求解,各算法參數設置與4.2相同。為便于分析,將無人機和任務目標看作質點,在任務分配過程中不考慮無人機之間的通信約束。仿真區域設置為90 km×150 km的平面,各目標坐標及任務時間窗見表4所示。

表4 任務目標點參數Table 4 The parameters of targets

續表(表4)

為確保實驗結果的準確性,各算法重復運行50次,最大迭代次數為200。MLFWA和其他對比算法在任務分配實例上求解的解集分布如圖7所示。從圖7可以看出,本文中所提MLFWA在求解無人機多目標任務分配問題中解的質量要明顯優于NSGA-Ⅱ、MOEA/D、MOPSO算法。

圖7 各算法求解結果示意圖Fig.7 Schematic diagram of solution results for each algorithm

對各算法求解得到的目標函數值進行歸一化,計算得到各算法運行30次的HV均值和方差,如表5所示。從表5可以看出,MLFWA在實例中求解得到的解集HV均值要大于3種對比算法,說明了MLFWA求解得到的解集具有較好的多樣性和收斂性。但MLFWA的求解得到解集的HV值的方差要略大于MOEA/D、NSGA-Ⅱ算法,說明算法的穩定性略差于MOEA/D、NSGA-Ⅱ算法。由于多目標優化問題主要關注解集質量,故在提升算法求解質量的前提下,適當降低算法穩定是可取的。

表5 各算法的HV均值和方差Table 5 The mean and variance of HV for each algorithm

4 結論

針對不確定條件下無人機多目標任務分配問題,運用不確定理論將任務執行過程中的威脅、油耗、飛行時間等不確定變量進行量化處理,將其建模為確定型多目標優化問題。引入冪律分布函數和Levy變異算子,結合多目標優化理論和兩階段搜索策略提出了一種兩階段搜索的多目標煙花算法,克服了傳統煙花算法不能解決多目標問題的缺陷,并有效提高了算法的求解精度和效率。實驗結果表明,MLFWA能夠在滿足油耗等約束的前提下,有效找出最佳任務分配方案。

下一步工作主要包括以下幾個方面。從理論層面,考慮利用不確定性理論中的樂觀值、悲觀值準則直接求解多目標問題;從模型層面,考慮任務目標價值時變、戰場威脅改變、無人機戰損等因素細化模型,使之更貼近戰場實際;從算法層面,考慮多目標優化理論和智能算法如何更好的結合,以降低算法復雜度及增強算法尋優效率。