基于改進(jìn)煙花算法的資源分配

鄒適宇，李復(fù)名，謝愛平，周濤，劉鵬

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

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

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

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

然而上述改進(jìn)煙花算法在求解具有多約束條件多優(yōu)化目標(biāo)的資源分配問題時(shí)，求解效果相對不佳。本文為了改善傳統(tǒng)煙花算法性能，以多無人機(jī)協(xié)同作業(yè)任務(wù)分配[18]為研究背景，提出一種改進(jìn)煙花算法，在傳統(tǒng)煙花算法的基礎(chǔ)上引入遺傳算法[19]的變異算子，增加模擬退火操作[20]，最后對算法性能進(jìn)行了仿真驗(yàn)證。

1 資源分配數(shù)學(xué)模型

資源分配問題作為一個共性的數(shù)學(xué)問題具有眾多應(yīng)用場景，本文選取多無人機(jī)協(xié)同任務(wù)分配這一復(fù)雜、典型的資源分配問題進(jìn)行研究。為了使數(shù)學(xué)模型更貼近實(shí)際應(yīng)用場景，本文考慮了無人機(jī)的可偵查頻段等功能指標(biāo)，以最小化飛行總航程、任務(wù)執(zhí)行總時(shí)間和損耗代價(jià)為優(yōu)化目標(biāo)構(gòu)建資源分配數(shù)學(xué)模型。

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

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

(1)

fmax≥fk≥fmin

(2)

di≤dmax

(3)

k≤M

(4)

為了降低無人機(jī)執(zhí)行任務(wù)風(fēng)險(xiǎn)、減少資源浪費(fèi)，本文設(shè)置以下3個優(yōu)化目標(biāo)：① 無人機(jī)飛行總航程最短；② 任務(wù)執(zhí)行總時(shí)間最短；③ 無人機(jī)損耗最小。

優(yōu)化目標(biāo)①要求任務(wù)執(zhí)行完成后，無人機(jī)飛行總航程最短，將無人機(jī)飛行總航程指標(biāo)用F1表示，即

(5)

式中：di為無人機(jī)i完成任務(wù)序列飛行的總航程。

優(yōu)化目標(biāo)②要求無人機(jī)機(jī)群執(zhí)行分配到的任務(wù)目標(biāo)的總?cè)蝿?wù)執(zhí)行時(shí)間最短，將任務(wù)執(zhí)行總時(shí)間指標(biāo)用F2表示，即

(6)

優(yōu)化目標(biāo)③要求無人機(jī)機(jī)群在完成所有任務(wù)后，所有無人機(jī)的損耗代價(jià)最小，將損耗代價(jià)指標(biāo)用F3表示，即

(7)

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

基于以上優(yōu)化目標(biāo)，設(shè)由N架無人機(jī)執(zhí)行M個目標(biāo)任務(wù)，無人機(jī)i的任務(wù)集為Xi，執(zhí)行任務(wù)的效能為F(Xi)，得到多無人機(jī)協(xié)同任務(wù)分配模型：

(8)

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

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

(9)

C(Xi)=a1b1F1+a2b2F2+a3b3F3

(10)

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

2 傳統(tǒng)煙花算法

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

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

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

3 改進(jìn)煙花算法

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

針對本文的多無人機(jī)協(xié)同任務(wù)分配這一數(shù)學(xué)模型，傳統(tǒng)煙花算法由于爆點(diǎn)范圍大、爆炸以及變異產(chǎn)生的新一代煙花粒子發(fā)生聚集而產(chǎn)生不相關(guān)搜索等問題。

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

算法流程如圖1所示?？梢钥闯?，改進(jìn)后的煙花算法具體包括如下步驟：

圖1 改進(jìn)煙花算法流程圖

步驟1初始化解空間并進(jìn)行符號編碼。基于本文的多無人機(jī)協(xié)同任務(wù)分配問題，首先根據(jù)無人機(jī)任務(wù)約束條件，采用符號編碼的方式對問題進(jìn)行編碼，設(shè)置染色體P的長度為M以保證每個任務(wù)都有無人機(jī)分配并不會多次分配；然后確定種群內(nèi)部煙花粒子的數(shù)目以及維數(shù)，初始化解空間，并計(jì)算所有解空間內(nèi)煙花粒子的適應(yīng)度函數(shù)值。

如圖2所示，該煙花粒子表示有3架無人機(jī)執(zhí)行5項(xiàng)任務(wù)。0號無人機(jī)執(zhí)行1、4號任務(wù)，1號無人機(jī)執(zhí)行2號任務(wù)，2號無人機(jī)執(zhí)行3、5號任務(wù)。

圖2 編碼方式

(11)

步驟3爆炸。根據(jù)爆炸公式，得到初始種群中每一個個體爆炸產(chǎn)生的火花位置，并進(jìn)行越界檢查，對于越界的火花粒子，根據(jù)映射規(guī)則映射到可行域內(nèi)。

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

(12)

(13)

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

為了限制煙花爆炸產(chǎn)生火花的數(shù)量過多或過少，為每個煙花設(shè)定了產(chǎn)生火花數(shù)量的限制公式，即

(14)

爆炸產(chǎn)生的火花將在爆炸半徑范圍內(nèi)隨機(jī)產(chǎn)生位移，即

(15)

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

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

圖3 變異操作

步驟5映射。為避免模擬退火、爆炸或變異產(chǎn)生火花的第k維度的值超出可行域，需要構(gòu)建映射規(guī)則將其映射到可行域內(nèi)。采用模運(yùn)算的映射規(guī)則，其公式為

(16)

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

(17)

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

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

4 實(shí)驗(yàn)仿真

4.1 仿真環(huán)境

基于本文第1節(jié)構(gòu)建的多無人機(jī)協(xié)同作業(yè)任務(wù)分配數(shù)學(xué)模型，繪制出400 km×400 km的區(qū)域仿真地圖，如圖4所示。

圖4 仿真環(huán)境圖

由仿真環(huán)境圖可以看出，地圖中有{a,b,c,d,e}共5架無人機(jī)，10個目標(biāo)任務(wù)散布于400 km×400 km的仿真環(huán)境中，需要將圖中的5架無人機(jī)分配給區(qū)域內(nèi)的10個目標(biāo)任務(wù)。其中，無人機(jī)和目標(biāo)任務(wù)的具體屬性如表1和表2所示。

表1 無人機(jī)屬性信息

表2 目標(biāo)任務(wù)屬性信息

4.2 仿真結(jié)果與分析

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

圖5 改進(jìn)煙花算法收斂曲線

圖6 改進(jìn)煙花算法分配方案

由SAGAFWA的收斂曲線以及分配方案的變化可以看出，SAGAFWA在迭代25次時(shí)的分配方案為{[a:10,6,5],[c:7,1],[d:3,2],[e:4,8,9]}，即無人機(jī)a依次執(zhí)行任務(wù)10、6、5，無人機(jī)c執(zhí)行任務(wù)7和1，無人機(jī)d執(zhí)行任務(wù)3和2，無人機(jī)e依次執(zhí)行任務(wù)4、8、9。算法迭代至50次期間一直陷入局部最優(yōu)，分配結(jié)果保持不變，直到迭代75次后，因其算法性能的優(yōu)勢，成功跳出局部最優(yōu)，分配方案變成{[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節(jié)構(gòu)建的資源分配模型為例，即將5臺無人機(jī)分配給10個任務(wù)目標(biāo)，對遺傳算法(Genetic Algorithm, GA)、FWA、和SAGAFWA進(jìn)行對比實(shí)驗(yàn)，參數(shù)設(shè)置如表3所示。

表3 算法參數(shù)設(shè)置

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

表4 算法優(yōu)化結(jié)果對比

可以看出，就優(yōu)化目標(biāo)無人機(jī)飛行總航程F1而言，2種傳統(tǒng)智能優(yōu)化算法均無法獲得最優(yōu)解；在對任務(wù)執(zhí)行總時(shí)間F2的優(yōu)化求解中，5種算法都可以得到最優(yōu)值；以無人機(jī)損耗最小F3為優(yōu)化目標(biāo)時(shí)，F(xiàn)WA、GAFWA、SAFWA和SAGAFWA都具有尋得最優(yōu)解的能力；而SAGAFWA對各優(yōu)化指標(biāo)都能尋得最優(yōu)，且平均求解精度均優(yōu)于其他4種算法。

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

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

圖7 算法收斂情況對比

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

表5 算法性能對比

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

表6 算法準(zhǔn)確度對比

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

5 結(jié) 論

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