基于混沌自適應(yīng)螢火蟲算法的UAVs分配策略

宋阿妮 包賢哲 權(quán) 軼

(湖北工業(yè)大學電氣與電子工程學院 湖北 武漢 430068)

0 引 言

無人機(Unmanned Aerial Vehicle，UAV)以其快速、精準、低風險等優(yōu)勢已經(jīng)廣泛應(yīng)用于軍事[1]、農(nóng)業(yè)[2]、運輸?shù)阮I(lǐng)域[3-6]。戰(zhàn)場無人機作為新型作戰(zhàn)裝備在現(xiàn)代戰(zhàn)爭中起著不可代替的重要作用，在武裝打擊、敵情偵察、目標追蹤、山地搜索、危機預(yù)警、定點監(jiān)視等多種類任務(wù)方面能夠很好地代替人力，大幅度降低執(zhí)行任務(wù)風險并克服復雜地形障礙[7]。但隨著無人機數(shù)量激增，任務(wù)數(shù)量和復雜度不斷上升，尋常算法的分配運算時間大幅增加，無法滿足現(xiàn)代戰(zhàn)爭對作戰(zhàn)任務(wù)快速分配響應(yīng)的要求。所以如何在戰(zhàn)場任務(wù)數(shù)量和無人機基數(shù)較大的情況下合理分配任務(wù)獲得最高收益是當下無人機作戰(zhàn)任務(wù)分配研究熱點。很多學者嘗試引入各類智能優(yōu)化算法來解決此類問題[8]。其中螢火蟲優(yōu)化算法以其易于實現(xiàn)、優(yōu)化性能好、限制條件少等優(yōu)點，成為目前運用較為廣泛且應(yīng)用效果最好的方法[9]。

在螢火蟲算法研究中，Wang等[10]提出了一種隨機吸引的螢火蟲算法模型。該算法通過隨機選擇一個亮度更高的個體進行移動從而減少收斂時間和復雜度，但由于移動次數(shù)過少容易引起算法早熟。Zhou等[11]引入了概率參數(shù)p來控制螢火蟲的吸引頻率，此方法被稱為部分吸引模型。只有在個體亮度高于本體且概率參數(shù)同時滿足要求時才能移動，此方法有效地加快了收斂速度，但概率參數(shù)p的選定卻是一個難題。Wang等[12]提出了鄰域吸引模型，本體與一定范圍領(lǐng)域內(nèi)的個體進行比較，通過控制領(lǐng)域的大小，可以有效控制算法收斂速度，但個體周圍領(lǐng)域大小過于依賴問題特征。隨著算法研究的不斷深入，傳統(tǒng)螢火蟲算法存在著容易陷入局部最優(yōu)解和隨機移動造成的收斂速度過慢收斂精度不高的問題。

本文將傳統(tǒng)螢火蟲算法的移動步長改進為自適應(yīng)步長，在位置更新信息中加入全局歷史最優(yōu)值和自適應(yīng)慣性權(quán)重，采用變尺度混沌方法改進光吸收強度系數(shù)，提出混沌自適應(yīng)螢火蟲算法(Chaotic adaptive Firefly Algorithm,CAFA)，并應(yīng)用于多作戰(zhàn)無人機多任務(wù)分配問題。該算法有利于更精確地找到最優(yōu)分配方案，提高系統(tǒng)的響應(yīng)速度和機動性。

1 問題分析與模型建立

設(shè)定無人機作戰(zhàn)任務(wù)分配問題中，敵我雙方在交戰(zhàn)地域S=[0,s]×[0,s]內(nèi)，有n個不同類型任務(wù)M=(M1,M2,…,Mn)等待無人機執(zhí)行，需要從無人機基地派出Q架無人機完成交戰(zhàn)地域S內(nèi)的所有任務(wù)。為了躲避敵人雷達和監(jiān)控設(shè)備對無人機的探測減小其墜毀概率，設(shè)立圓形禁飛區(qū)Ρ，無人機禁止在此區(qū)域內(nèi)飛行，其實時位置(xVi,yVi)?P。上述無人機的任務(wù)分配調(diào)度問題可定義為一個優(yōu)化模型：一組無人機V={V1,V2,…,Vm}，一組待完成的任務(wù)M={M1,M2,…,Mn}，將任務(wù)風險指數(shù)、航程代價指數(shù)作為系統(tǒng)成本，任務(wù)完成潛力指數(shù)和執(zhí)行任務(wù)價值指數(shù)作為系統(tǒng)收益，通過模型評價指標以評價當前分配方案的優(yōu)劣，最終確定最佳分配方案。

1.1 任務(wù)風險指數(shù)

任務(wù)風險指數(shù)是指無人機在執(zhí)行任務(wù)時損毀的概率大小，設(shè)無人機Vi號執(zhí)行Mj號任務(wù)時的任務(wù)風險指數(shù)為：

(1)

式中：ValVi為無人機Vi號的價格成本；ThrMj為無人機完成任務(wù)Mj號發(fā)生損毀的概率大小；max{ValVi|1≤i≤m}是所有無人機中的最大價格成本。

1.2 航程損耗指數(shù)

任務(wù)航程損耗指數(shù)是指無人機完成任務(wù)時間長短，設(shè)無人機Vi號執(zhí)行任務(wù)Mj的航程損耗指數(shù)為：

(2)

式中：DisVij表示無人機Vi與任務(wù)Mj之間的距離；max{DisVij|1≤i≤m}表示所有無人機到任務(wù)Mj的最大距離。

1.3 任務(wù)完成潛力指數(shù)

任務(wù)完成潛力是指無人機完成指定任務(wù)的概率大小，應(yīng)優(yōu)先分配任務(wù)給完成概率大的無人機。設(shè)無人機Vi號完成任務(wù)Mj的潛力指數(shù)為:

(3)

式中：TiVi表示無人機Vi號在空中飛行的最大時間；max{TiVi|1≤i≤m}表示所有無人機在空中飛行的最大時間；Potij表示無人機Vi號執(zhí)行任務(wù)Mj時的任務(wù)完成概率。

1.4 執(zhí)行任務(wù)價值指數(shù)

執(zhí)行任務(wù)價值指數(shù)是指無人機在完成匹配任務(wù)后能夠創(chuàng)造的最大價值，設(shè)無人機Vi完成匹配任務(wù)Mj的執(zhí)行任務(wù)價值指數(shù)為:

(4)

式中：ValMj表示完成任務(wù)Mj的收益；max{ValMj|1≤i≤m}則表示所有任務(wù)中完成收益最大值。

1.5 戰(zhàn)場無人機禁飛區(qū)域

在現(xiàn)代戰(zhàn)爭中，雷達等偵測手段成為了無人機的頭號敵人，躲避雷達和監(jiān)控設(shè)備將會大大降低無人機墜毀概率，為了模擬敵人的雷達和監(jiān)控設(shè)備，無人機在完成任務(wù)過程中禁止在該區(qū)域內(nèi)飛行，即滿足：

(5)

式中：Vxi、Vyi分別表示無人機飛行狀態(tài)下的橫縱坐標；Oxi、Pyi則表示敵軍雷達和監(jiān)控設(shè)備的橫縱坐標。

考慮應(yīng)以最短時間執(zhí)行任務(wù)，無人機執(zhí)行任務(wù)路徑為直線往返，所以無人機與禁飛區(qū)中心位置最短距離大于等于其安全半徑可轉(zhuǎn)化為無人機與被執(zhí)行任務(wù)之間連線與禁飛區(qū)圓形區(qū)域相切或相離，過禁飛區(qū)圓心向無人機飛行路徑直線作垂線，無人機到禁飛區(qū)邊緣的最近距離：

(6)

式中：Aijx+Bijy+Cij=0為無人機Vi執(zhí)行任務(wù)Mj時無人機位置與任務(wù)點位置連線的直線方程；Ri(i=1，2，…,n)為禁飛區(qū)的安全半徑。

1.6 無人機分配優(yōu)化模型

任務(wù)風險指數(shù)以及航程損耗指數(shù)作為代價指標需要進行最小優(yōu)化，而任務(wù)完成潛力指數(shù)和任務(wù)收益指數(shù)作為最終收益要進行最大優(yōu)化。為了能夠?qū)?yōu)化目標統(tǒng)一，采用倒數(shù)方法表示系統(tǒng)任務(wù)收益。

(7)

式中：Get_Fin為完成任務(wù)潛力指數(shù)的倒數(shù)；Get_Inc為執(zhí)行任務(wù)價值指數(shù)的倒數(shù)。

將四個指標的線性組合作為無人機分配任務(wù)的綜合評價指標來評判分配方案的優(yōu)劣，由此得到最終的無人機分配優(yōu)化目標函數(shù)為：

(8)

式中：m和n分別表示無人機和任務(wù)的最大數(shù)量。m和n的約束條件為：

(9)

式中：kVi為每種類型無人機的最大任務(wù)負荷，無人機執(zhí)行任務(wù)數(shù)量不能超過其最大任務(wù)負荷；hij表示無人機Vi號是否去執(zhí)行了任務(wù)Mj，記錄無人機完成任務(wù)的狀態(tài)，若無人機Vi完成了任務(wù)Mj則將其各項指標代入計算，否則不列入數(shù)值。計算表達式為：

(10)

2 多無人機分配優(yōu)化算法

2.1 經(jīng)典螢火蟲算法

經(jīng)典螢火蟲算法是一種啟發(fā)式算法，靈感來源于螢火蟲閃爍行為。螢火蟲不分性別，任意個體將會吸引到所有其他的螢火蟲。吸引力與它們的亮度成正比，對于任意兩個螢火蟲，亮度低的螢火蟲被吸引，向更加明亮的移動，其亮度又隨著其距離的變化而變化。如果在某個螢火蟲鄰域范圍內(nèi)沒有亮度更高的螢火蟲，那么它會隨機移動，直到集中于全局最亮螢火蟲的周圍。

群體中每一個螢火蟲都對應(yīng)問題的一個可能解。假設(shè)Xi=(xi1,xi2,…,xid)是一只螢火蟲，其中：i表示螢火蟲的編號；d表示每一個螢火蟲解的緯度數(shù)。對于兩只不同的螢火蟲即不同解Xi、Xj,i≠j，二者之間的吸引度可以表示為：

(11)

式中：β0表示距離r=0處的吸引力；rij表示兩只螢火蟲之間的距離；γ表示兩者之間傳播媒介對光的吸收率，由介質(zhì)性質(zhì)決定。式(12)即為兩只不同螢火蟲之間的距離。

(12)

移動公式表示為：

xid(t+1)=xid(t)+β(rij)·(xjd(t)-xid(t))+αε

(13)

式中：α∈[0,1]表示螢火蟲每次移動的步長的系數(shù)；ε為常數(shù)，表示移動步長；t表示迭代的次數(shù)。所有螢火蟲按照式(13)向著更優(yōu)個體移動。

2.2 改進的混沌自適應(yīng)螢火蟲算法

螢火蟲算法容易陷入局部最優(yōu)解，而且還存在著最亮個體距離過遠而導致的螢火蟲無法集中收斂和收斂速度慢問題。對傳統(tǒng)螢火蟲算法進行改進，運用變尺度混沌方法將光吸收系數(shù)改進為跟隨迭代次數(shù)不斷更替的混沌數(shù)值，再將螢火蟲的位置公式中引入全局最優(yōu)以及自適應(yīng)步長因子與慣性權(quán)重來整體優(yōu)化螢火蟲算法的性能。

2.2.1步長因子優(yōu)化

理想情況下，螢火蟲最終會收斂于極少點或者單個點，由此可得到：

(14)

當?shù)螖?shù)達到一定數(shù)值時，式(14)就會收斂為一個數(shù)值，收斂后的解不再發(fā)生變化，此時可以根據(jù)式(11)-式(13)得到：

(15)

由式(15)可知，當最終結(jié)果收斂時，步長因子α=0。

根據(jù)此性質(zhì)，提出一種自適應(yīng)步長的改進方案：

(16)

式中：Tmax為迭代最大次數(shù)。

由式(16)可以看出，當?shù)螖?shù)增加時，步長因子在不斷減小，在t→∞時步長因子α→0，加快了收斂速度和精度。

2.2.2自適應(yīng)慣性權(quán)重

為了能夠使得螢火蟲移動時方向和搜索距離更加準確，在螢火蟲上一時刻位置xid(t)前引入μ(t)自適應(yīng)慣性權(quán)重：

(17)

式中：gbest(t)為螢火中歷史全局最優(yōu)值；E(f)為第t次迭代所有目標位置的平均值：

(18)

通過引入自適應(yīng)慣性權(quán)重，使得計算后期螢火蟲的收斂精度和速度進一步提高。

2.2.3引入歷史全局最優(yōu)值

在螢火蟲的位置更新中加入歷史全局最佳位置，讓螢火蟲有記憶地搜尋最優(yōu)解，在向更亮的個體移動的過程中同時向著歷史最佳位置靠攏，使得位置較遠的螢火蟲也能在迭代次數(shù)較高的情況下集中于全局最優(yōu)解附近，大大加快了收斂速度和收斂精度。改進后的位置公式為：

xid(t+1)=μ(t)xid(t)+β0(rij)·(xjd(t)-xid(t))+

ω(gbest(t)-xid(t))+α(t)ε

(19)

式中：gbest(t)是迭代次數(shù)為t時的歷史最佳位置。ω系數(shù)隨著t增大而減小：

(20)

2.2.4變尺度混沌光強度吸收系數(shù)

光吸收系數(shù)γ是影響螢火蟲搜索精度和速度非常重要的參數(shù)[13]，能夠很大程度影響到螢火蟲向最優(yōu)解集中。當γ→∞時，根據(jù)式(11)可知β(i,j)→0，螢火蟲的吸引力最小，有利于在小范圍內(nèi)細化搜索；當γ→0時，β(i,j)→∞，螢火蟲吸引力最大，可以進行大范圍移動，有利于在大范圍內(nèi)全局搜索最優(yōu)解。如果光吸收系數(shù)設(shè)定為常數(shù)則會影響到螢火蟲搜索的精度和速度，基于此提出一種變尺度混沌光強度吸收系數(shù)來強化螢火蟲的全局與局部搜索能力。

混沌是一種普遍存在的非線性現(xiàn)象，具有隨機性、初值敏感性、應(yīng)用便利性，利用這些特性改變螢火蟲的光吸收強度系數(shù)，讓算法能夠跳出局部最優(yōu)解，避免了迭代過程中光吸收強度保持不變的缺陷。

根據(jù)Gandomi等[14]對映射函數(shù)的分析，選擇混沌應(yīng)用效果較好的Sinusoidal映射，其公式為：

(21)

式中：a為一個幅值常數(shù)。

搜索空間對于混沌優(yōu)化方法有較大的影響，搜索空間較小時效果較為明顯，搜索空間過大會導致混沌優(yōu)化失效。隨著搜索空間的增大，搜索精度也會進一步降低，所以采用變尺度混沌方法限制其搜索空間大小。將式(21)改進為：

(22)

式中：

(23)

此時光強度吸收系數(shù)為：

(24)

螢火蟲的亮度公式改進為：

(25)

βrev(i,j)隨著迭代次數(shù)變化的曲線如圖1所示，迭代前期收斂速度較快，能夠提高收斂速度，迭代后期搜索范圍變小，收斂速度較慢，有利于群體在小范圍內(nèi)精確尋找最優(yōu)位置。

圖1 混沌變異γ變化曲線

根據(jù)上述提出的改進方案，變尺度混沌自適應(yīng)螢火蟲算法(CAFA)的流程如圖2所示。

圖2 混沌自適應(yīng)螢火蟲算法流程

3 實驗與結(jié)果分析

為了驗證提出的分配算法的合理性，本文設(shè)計了如下算例進行無人機協(xié)同作戰(zhàn)仿真實驗。假設(shè)任務(wù)開始前，我軍已經(jīng)獲取了敵軍所有目標部隊以及交戰(zhàn)區(qū)域敵軍防空陣地的坐標，敵我雙方交戰(zhàn)的地域S=[0，80]×[0，80] km2內(nèi)，有15個地點安排有不同類型任務(wù)，并且4架作戰(zhàn)無人機已被我方地面部隊送達適合起飛的4個位置執(zhí)行相關(guān)任務(wù)。作戰(zhàn)地域整體分布情況如圖3所示。

圖3 作戰(zhàn)區(qū)域整體位置分布

在交戰(zhàn)區(qū)域S內(nèi)設(shè)立三個禁飛區(qū)，無人機在完成任務(wù)過程中禁止在該區(qū)域內(nèi)飛行即滿足：

(26)

式中：Vxi、Vyi分別表示無人機飛行狀態(tài)下的橫縱坐標；三個雷達的偵測范圍分別為方圓12 km、11 km、10 km。

表1 無人機各項參數(shù)表

表2 任務(wù)各項參數(shù)表

續(xù)表2

根據(jù)表1和表2相關(guān)無人機和任務(wù)參數(shù)可知，毀傷任務(wù)1、7、11僅可以由3號和4號無人機完成即xi1、xi7、xi11取值為3、4，監(jiān)視任務(wù)2、10、15僅可由1號、2號、3號無人機完成即xi2、xi10、xi15的取值為1、2或3，其他任務(wù)取值以此類推。

對算例中任務(wù)按照1～n進行編號，無人機則按照1～m進行編號，無人機總數(shù)為4架，則螢火蟲個體的搜索范圍Ω?[1，5)，所得小數(shù)均向下取整，由任務(wù)數(shù)n=15可設(shè)定螢火蟲個體xi屬性為15維，第i個螢火蟲表示為xi=(xi1,xi2,…,xi15)。為保證算法收斂到最優(yōu)解，設(shè)置螢火蟲的初始種群個體數(shù)量N=20，迭代次數(shù)t=1 000，其步長因子α、光吸收系數(shù)γ、慣性系數(shù)ω都由函數(shù)定義，分別用粒子群算法、經(jīng)典螢火蟲算法、混沌自適應(yīng)螢火蟲算法對此問題進行求解得到其最優(yōu)分配序列如表3所示，運用PSO、FA、CAFA三種算法求解迭代對比如圖4所示。

表3 無人機任務(wù)分配表

圖4 三種不同算法對應(yīng)迭代對比

可以看出，三種算法的迭代速度有非常大的差別，其中以混沌自適應(yīng)螢火蟲算法的迭代速度最快，在74次左右就收斂到最優(yōu)值，比粒子群和傳統(tǒng)螢火蟲算法在迭代速度上有了很大提升。所以混沌自適應(yīng)螢火蟲算法對此問題有更好地適應(yīng)度。在無人機或任務(wù)狀態(tài)發(fā)生改變時，該算法可以更快地響應(yīng)計算出新的最優(yōu)分配方案。算法結(jié)果對比如表4所示，其飛行路線如圖5所示。

表4 三種算法結(jié)果對比表

圖5 無人機執(zhí)行任務(wù)飛行軌跡

表4給出了PSO、FA和混沌自適應(yīng)算法的數(shù)值結(jié)果對比，可以看出針對此問題的解PSO和FA的迭代時間、次數(shù)和最終結(jié)果相對于混沌自適應(yīng)算法適應(yīng)度都相對較差，混沌自適應(yīng)算法得到的結(jié)果相對于PSO和FA精度分別提高了16.07%、11.12%，迭代時間相對提高了31.99%，24.79%，收斂率也相對提高了33.33%、17.65%。實驗結(jié)果表明CAFA具有較強的全局搜索能力和處理復雜問題的能力，在面對復雜情況時能夠更快響應(yīng)，計算出當前狀態(tài)下的最佳方案，且能根據(jù)作戰(zhàn)任務(wù)和無人機狀態(tài)的改變實時更新方案。除此之外，該算法能夠很好地提升傳統(tǒng)螢火蟲算法在初期容易陷入局部最優(yōu)和隨機移動造成的收斂較慢的問題，使得在優(yōu)化分配任務(wù)初期能夠更準確、更快地優(yōu)化當前方案，節(jié)省大量時間成本，讓無人機群的作戰(zhàn)性能進一步提升。

4 結(jié) 語

本文針對多數(shù)量無人機協(xié)同作戰(zhàn)任務(wù)的分配問題提出一種基于變尺度混沌光吸收強度系數(shù)、自適應(yīng)步長、慣性系數(shù)、全局歷史最優(yōu)解的綜合螢火蟲優(yōu)化算法。算法能夠在搜索前期自適應(yīng)選擇最優(yōu)方向并加快搜索速度，在收斂后期又可以精確搜索局部最優(yōu)解，有效地解決由于步長不變而導致的容易在搜索后期跳過最優(yōu)解、收斂前期速度過慢的問題，具有非常好的收斂精度和速度；能夠在一定程度上提升無人機群的協(xié)同作戰(zhàn)的性能、反應(yīng)速度并提高處理復雜多變的情況下任務(wù)分配速度。考慮地形和環(huán)境等影響因素，將算法如何運用于更加復雜的異構(gòu)無人機協(xié)同作戰(zhàn)系統(tǒng)，是下一步研究的目標。