基于改進煙花算法的資源分配

鄒適宇，李復名，謝愛平，周濤，劉鵬

中國電子科技集團公司第二十九研究所，成都 610000

資源分配是指針對某個目標，遵循一定的策略將規模為N的資源映射和劃分到P個個體上，是一個NP-Hard問題。作為一個典型的組合優化問題，進行合理的資源分配能夠達到提高效率、節約成本、合理配置資源或總體收益最佳等系統目標[1]。其求解途徑一般包括窮舉法、分支定界法等確定性算法[2-5]和遺傳算法、粒子群算法等智能優化算法[6-9]。

煙花算法(Firework Algorithm, FWA)作為智能優化算法的一種，由于其操作簡單、性能較優，具有較強的并行性與魯棒性，自北京大學的譚營教授于2010年提出以來便受到廣泛關注[10]。但傳統煙花算法在求解大規模資源分配問題時也存在計算效率偏低、易陷入局部最優等問題。

研究人員針對這些問題也做了改進工作，主要包括以下2個方面：第一，算法本身機制和算子的改進。文獻[11]僅保留FWA的爆炸操作，提出一種骨架煙花算法，該算法具有簡單易行、參數少等優點；文獻[12]針對FWA求解精度低的問題，提出具有灰色關聯算子的煙花算法；文獻[13]在分析高斯變異算子不足的基礎上，提出了一種基于差分變異算子的煙花算法，增強了算法的精度和收斂速度；文獻[14]引入爆炸半徑動態調整的策略，提出一種帶有動態爆炸半徑的增強型煙花算法，以增強算法跳出局部最優的能力。第二，同其他智能優化算法的融合。文獻[15]將生物地理學優化方法的遷移操作引入到FWA中，以增強種群之間的信息共享文獻，改善種群多樣性；文獻[16]在FWA的基礎上，引入混合蛙跳算法的分組策略，增強了算法跳出局部最優的能力；文獻[17]為了提高FWA的全局搜索能力，將模擬退火算法引入FWA中，提出了一種基于模擬退火與高斯擾動的煙花優化算法。

然而上述改進煙花算法在求解具有多約束條件多優化目標的資源分配問題時，求解效果相對不佳。本文為了改善傳統煙花算法性能，以多無人機協同作業任務分配[18]為研究背景，提出一種改進煙花算法，在傳統煙花算法的基礎上引入遺傳算法[19]的變異算子，增加模擬退火操作[20]，最后對算法性能進行了仿真驗證。

1 資源分配數學模型

資源分配問題作為一個共性的數學問題具有眾多應用場景，本文選取多無人機協同任務分配這一復雜、典型的資源分配問題進行研究。為了使數學模型更貼近實際應用場景，本文考慮了無人機的可偵查頻段等功能指標，以最小化飛行總航程、任務執行總時間和損耗代價為優化目標構建資源分配數學模型。

根據無人機實際應用場景的需求，將多無人機協同作業任務分配場景描述為一個三元組{U,T,C}，其中U表示無人機的集合，T表示目標任務的集合，C表示約束條件的集合。本文的約束條件包括：無人機任務約束、偵查頻段約束、最大航程約束和最大執行任務數量約束。

設某一無人機的偵查頻段范圍為[fmin,fmax]，最大執行任務數量為M，其執行任務序列為{Task1,Task2,…,Taskk}，按照任務序列執行完所有任務的航程為di，其中一目標任務Tj包含頻率為fk，xi,j=1表示任務j由無人機i執行，xi,j=0表示無人機i不執行任務j，則需滿足：

(1)

fmax≥fk≥fmin

(2)

di≤dmax

(3)

k≤M

(4)

為了降低無人機執行任務風險、減少資源浪費，本文設置以下3個優化目標：① 無人機飛行總航程最短；② 任務執行總時間最短；③ 無人機損耗最小。

優化目標①要求任務執行完成后，無人機飛行總航程最短，將無人機飛行總航程指標用F1表示，即

(5)

式中：di為無人機i完成任務序列飛行的總航程。

優化目標②要求無人機機群執行分配到的任務目標的總任務執行時間最短，將任務執行總時間指標用F2表示，即

(6)

優化目標③要求無人機機群在完成所有任務后，所有無人機的損耗代價最小，將損耗代價指標用F3表示，即

(7)

式中：price(Xi)和damage(Xi)分別表示無人機i的價格和損傷概率。

基于以上優化目標，設由N架無人機執行M個目標任務，無人機i的任務集為Xi，執行任務的效能為F(Xi)，得到多無人機協同任務分配模型：

(8)

式中：效能函數F(Xi)=R(Xi)-C(Xi)，R(Xi)和C(Xi)分別代表無人機i執行任務獲得的收益以及付出的代價。具體定義為

R(Xi)=nT(Xi)S(Xi)

(9)

C(Xi)=a1b1F1+a2b2F2+a3b3F3

(10)

式中：n為一個常數，T(Xi)∈[0,1]為目標任務威脅等級，S(Xi)∈[0,1]為目標任務執行成功概率。a1、a2和a3分別為航程代價函數F1、時間代價函數F2和損耗代價函數F3的權重系數，a1+a2+a3=1，b1、b2和b3為F1、F2和F3的歸一化系數。

2 傳統煙花算法

煙花算法啟發于煙花爆炸的過程，主要由爆炸算子、變異算子、映射規則和選擇策略4個部分組成[21]。其基本原則是：若一個煙花的適應度值比較好，則該煙花爆炸幅度比較小且產生的火星數比較多，目的是加快當前最優值附近局部搜索能力；相反，若某個煙花適應度值比較差，則該煙花爆炸幅度大且產生火星數較少，目的主要是為了增強種群多樣性。

基于此，煙花算法偽代碼如算法1所示：

算法1 傳統煙花算法輸入:煙花數目n,爆炸火花數nE,爆炸半徑rE,爆炸數目限制因子a、b,變異火花數M輸出:種群中最優個體p初始化煙花種群 for 每一個迭代周期:計算種群內各火花粒子的適應度f(xi)。將適應度排序,保留適應度最高的個體p到下一代。按照爆炸公式生成nE個爆炸火花。按高斯變異公式,隨機選取M個火花進行高斯變異。對可行域范圍外的火花按照映射規則映射到可行域內按照概率p(xi)=∑Nj=1xi-xj∑Nk=1∑Nj=1xk-xj選取n-1個煙花粒子進入下一代。end forreturn p

3 改進煙花算法

由于在傳統煙花算法中，爆炸和變異操作均是對粒子進行的整體變換，因此，在迭代過程中會丟失很多煙花粒子內部所包含的可行解信息，進而導致陷入局部最優、收斂速度慢等問題。

針對本文的多無人機協同任務分配這一數學模型，傳統煙花算法由于爆點范圍大、爆炸以及變異產生的新一代煙花粒子發生聚集而產生不相關搜索等問題。

為了改善這種情況，提升算法效率，增強算法精度，本文提出一種改進煙花算法(SAGAFWA)，在傳統煙花算法的基礎上舍棄高斯變異操作，對每次迭代的最優個體引入遺傳算法的變異算子，加強最優個體粒子內部的信息交流，增強算法的局部尋優能力，提高算法尋找最優解的效率。此外，增加模擬退火操作，增強算法的全局搜索能力，以跳出局部最優。

算法流程如圖1所示?？梢钥闯觯倪M后的煙花算法具體包括如下步驟：

圖1 改進煙花算法流程圖

步驟1初始化解空間并進行符號編碼?；诒疚牡亩酂o人機協同任務分配問題，首先根據無人機任務約束條件，采用符號編碼的方式對問題進行編碼，設置染色體P的長度為M以保證每個任務都有無人機分配并不會多次分配；然后確定種群內部煙花粒子的數目以及維數，初始化解空間，并計算所有解空間內煙花粒子的適應度函數值。

如圖2所示，該煙花粒子表示有3架無人機執行5項任務。0號無人機執行1、4號任務，1號無人機執行2號任務，2號無人機執行3、5號任務。

圖2 編碼方式

(11)

步驟3爆炸。根據爆炸公式，得到初始種群中每一個個體爆炸產生的火花位置，并進行越界檢查，對于越界的火花粒子，根據映射規則映射到可行域內。

以第i個煙花粒子xi為例進行說明：基于適應度函數公式，則可根據以下公式得到第i個煙花粒子爆炸生成的火花數量Ni和爆炸半徑Ri，即

(12)

(13)

式中：fmax和fmin分別表示所有煙花粒子中適應度的最大值和最小值；ε為一個很小的常數，用來避免分子分母為0。

為了限制煙花爆炸產生火花的數量過多或過少，為每個煙花設定了產生火花數量的限制公式，即

(14)

爆炸產生的火花將在爆炸半徑范圍內隨機產生位移，即

(15)

式中：xi,j表示煙花粒子xi爆炸生成的第j(1≤j≤Ni)個火花，k表示煙花粒子的第k維。

步驟4變異。由于傳統煙花算法中的變異算子爆點范圍大且是對粒子整體進行的變換，會導致新產生的變異粒子丟失原本煙花粒子內部包含的可行解信息，從而導致算法搜索效率低、搜索精度低等問題。因此，引入遺傳算法的思想，生成變異火花，增強算法的局部尋優能力。以概率pm選取所有煙花粒子中的最優個體，然后進行隨機位置的基因段變異生成新個體p′，如圖3所示。

圖3 變異操作

步驟5映射。為避免模擬退火、爆炸或變異產生火花的第k維度的值超出可行域，需要構建映射規則將其映射到可行域內。采用模運算的映射規則，其公式為

(16)

步驟6選擇。將修正后的火花粒子，作為下一代的備選個體。根據選擇策略公式計算出每個個體被選擇的概率，采用輪盤賭的方式，優先選擇被選概率高的個體作為下一代。為了保證下一代種群的多樣性，選用歐氏距離來度量任意2個個體之間的距離，利用基于距離的選擇算子選擇剩下的n-1個個體，每個體被選中的概率為

(17)

基于上述步驟，改進煙花算法的偽代碼如算法2所示。

算法2 改進煙花算法輸入:煙花數目n,爆炸火花數nE,爆炸半徑rE,爆炸數目限制因子a、b,模擬退火常數α,初始溫度T,遺傳變異概率pm。輸出:種群中最優個體p。初始化煙花種群for每一個迭代周期: 計算種群內各火花粒子的適應度f(xi)。將適應度排序,保留適應度最高的個體p到下一代。do while T>Tmin: for 每一個溫度迭代周期: 對最優個體p引入高斯擾動算子g,p′=pg,根據映射規則映射到可行域內 Δf=f(p′)-f(p)。 if Δf >0: 最優個體p=p′。 else: 按照Metropolis準則以一定概率接受新的最優解p′。 T=Tα end do按照爆炸式(12)生成nE個爆炸火花。按變異概率pm選取最優個體進行隨機位置的基因段變異。對爆炸和變異產生的可行域范圍外的火花按照映射式(16)映射到可行域內。按照概率式(17)選取n-1個煙花粒子進入下一代。end forreturn p

4 實驗仿真

4.1 仿真環境

基于本文第1節構建的多無人機協同作業任務分配數學模型，繪制出400 km×400 km的區域仿真地圖，如圖4所示。

圖4 仿真環境圖

由仿真環境圖可以看出，地圖中有{a,b,c,d,e}共5架無人機，10個目標任務散布于400 km×400 km的仿真環境中，需要將圖中的5架無人機分配給區域內的10個目標任務。其中，無人機和目標任務的具體屬性如表1和表2所示。

表1 無人機屬性信息

表2 目標任務屬性信息

4.2 仿真結果與分析

設置初始煙花數目為100，爆炸火花數目nE=10，爆炸半徑rE=2，爆炸數目限制因子a=0.5，b=0.6，模擬退火常數α=0.98，遺傳變異概率pm=0.5。將迭代次數設置為N=100，并在N= 25，50，75，100時對分配結果進行采樣，取其中一次實驗結果，如圖5和圖6所示。

圖5 改進煙花算法收斂曲線

圖6 改進煙花算法分配方案

由SAGAFWA的收斂曲線以及分配方案的變化可以看出，SAGAFWA在迭代25次時的分配方案為{[a:10,6,5],[c:7,1],[d:3,2],[e:4,8,9]}，即無人機a依次執行任務10、6、5，無人機c執行任務7和1，無人機d執行任務3和2，無人機e依次執行任務4、8、9。算法迭代至50次期間一直陷入局部最優，分配結果保持不變，直到迭代75次后，因其算法性能的優勢，成功跳出局部最優，分配方案變成{[a:6,5],[b:7,1],[c:4,10],[d:2,3],[e:8,9]}，迭代100次后，分配方案最終收斂為{[a:6,5],[b:7,1],[c:10],[d:2,3],[e:4,8,9]}。

4.3 算法對比

為了評估SAGAFWA在求解資源分配問題上的性能，以求解第1節構建的資源分配模型為例，即將5臺無人機分配給10個任務目標，對遺傳算法(Genetic Algorithm, GA)、FWA、和SAGAFWA進行對比實驗，參數設置如表3所示。

表3 算法參數設置

基于上述參數設置，在上述3種智能優化算法的基礎上，增加2組消融實驗，即遺傳煙花算法(GAFWA)和模擬退火煙花算法(SAFWA)，將迭代次數均設置為100，各執行10次，把最后輸出最優解集中的3個優化目標飛行總航程F1、任務執行總時間F2、損耗代價F3以及目標函數值F的最優值和平均值進行比較，實驗結果如表4所示。

表4 算法優化結果對比

可以看出，就優化目標無人機飛行總航程F1而言，2種傳統智能優化算法均無法獲得最優解；在對任務執行總時間F2的優化求解中，5種算法都可以得到最優值；以無人機損耗最小F3為優化目標時，FWA、GAFWA、SAFWA和SAGAFWA都具有尋得最優解的能力；而SAGAFWA對各優化指標都能尋得最優，且平均求解精度均優于其他4種算法。

為了對比5種算法的收斂速度，增加迭代次數至N=300后，其迭代收斂情況如圖7所示。

如圖7所示，GA收斂速度最快，但是最終在迭代20次后收斂于局部最優；FWA在迭代過程中不斷跳出局部最優，迭代240次后逐漸收斂，可見FWA擁有比GA更強的全局搜索能力；相較于FWA，GAFWA和SAFWA在算法性能上有一定提升；而本文提出的改進煙花算法則綜合了GA和SA的優勢，擁有比FWA、GAFWA和SAFWA更快的收斂速度，5種算法中最高的求解精度，在迭代100次后收斂于最優解。

圖7 算法收斂情況對比

由表5可以看出，GA存在的問題為：隨著種群間個體的信息交互，受到最優個體的影響，每個個體會朝著最優個體的方向變化，導致算法收斂速度變快，但是失去了算法的多樣性，容易陷入局部最優；FWA存在的問題是：傳統煙花算法對每一代的煙花粒子做了爆炸、高斯變異等大量的個體變化操作，雖然增強了算法的全局搜索能力，但是算法花費大量時間，導致收斂速度變慢，搜索效率變低；SAGAFWA則借鑒了GA的優點，增強了算法的局部搜索能力并提高了收斂速度，此外，增加的模擬退火操作也增強了算法跳出局部最優的能力，從而獲得了3種算法中最優的求解精度。

表5 算法性能對比

最后，選取3種公開測試函數(Rastrigin、Ackley、Beale)對算法性能進行測試驗證。設置每類算法迭代次數為20，初始種群數為50，實驗結果如表6所示。

表6 算法準確度對比

可以看出，GA在所有算法中性能最差，SAGAFWA在上述3類測試函數中均得到了5種算法中的最高求解精度，驗證了算法的魯棒性。

5 結 論

本文對資源分配問題的最優化求解進行了研究，提出了一種改進煙花算法，用遺傳算法的變異算子替換傳統煙花算法的高斯變異操作，增強算法局部尋優能力，并增加模擬退火步驟，提高算法跳出局部最優的能力。最后在對多無人機協同任務分配數學模型以及3種測試函數的求解上進行了仿真實驗，結果表明改進煙花算法在收斂速度和求解精度上均優于其他3種煙花算法，并且具有較強魯棒性。