基于改進(jìn)飛蛾撲火算法的應(yīng)急資源調(diào)度研究*

黃彩霞，劉年平，謝曉君

(西南科技大學(xué) 環(huán)境與資源學(xué)院,四川 綿陽 621000)

0 引言

由于各類突發(fā)事件頻發(fā),對(duì)人民群眾的生命財(cái)產(chǎn)安全造成巨大威脅，應(yīng)急資源的及時(shí)安排和合理調(diào)度對(duì)減小災(zāi)后損失極其重要，因此,研究應(yīng)急資源調(diào)度模型意義重大。

在研究應(yīng)急資源調(diào)度模型方面：Kemball-Cook等[1]提出針對(duì)性管理應(yīng)急資源的供應(yīng)和運(yùn)輸；List等[2]在放射性危險(xiǎn)物品運(yùn)輸優(yōu)化模型中引入應(yīng)急概念，為后續(xù)應(yīng)急資源調(diào)度研究奠定基礎(chǔ)；王妍妍等[3]提出實(shí)時(shí)更新應(yīng)急物資的大數(shù)據(jù)信息；鞏玲君等[4]考慮災(zāi)后應(yīng)急資源調(diào)度的優(yōu)先順序；盛虎宜等[5]基于災(zāi)后物資調(diào)度公平性建立多目標(biāo)優(yōu)化模型；Wang等[6]建立以最少時(shí)間、最低成本為多目標(biāo)的二維優(yōu)化模型；Jiang等[7]考慮運(yùn)輸時(shí)間、道路通行程度和物資調(diào)度需求，建立應(yīng)急物資車輛調(diào)度模型；薛星群等[8]考慮通行約束力和運(yùn)力限制的災(zāi)后應(yīng)急物資調(diào)度；田曉勇等[9]結(jié)合道路搶修情況考慮應(yīng)急調(diào)度優(yōu)化問題。

在求解應(yīng)急資源調(diào)度模型算法方面：孫欣欣等[10]基于遺傳算法，以運(yùn)輸時(shí)間最少、物資儲(chǔ)備庫(kù)最少建立多目標(biāo)應(yīng)急物資調(diào)度模型；張永領(lǐng)等[11]提出基于混沌粒子群算法的應(yīng)急資源調(diào)度模型；王付宇等[12]提出基于改進(jìn)天牛須算法的應(yīng)急資源調(diào)度模型；Mirjalil[13]提出飛蛾撲火優(yōu)化(MFO)算法求解應(yīng)急物資調(diào)度最優(yōu)化問題；賀體龍等[14]基于改進(jìn)飛蛾撲火群智能算法，研究道路損壞情境下多需求點(diǎn)的應(yīng)急資源調(diào)度問題；Trivedi等[15]提出Levy-MFO算法(LMFO)求解應(yīng)急物資調(diào)度方案。上述研究成果極大地推進(jìn)了應(yīng)急資源調(diào)度水平，但隨著災(zāi)害事故現(xiàn)場(chǎng)的復(fù)雜化、動(dòng)態(tài)化，單一的設(shè)計(jì)指標(biāo)不能很好地反映應(yīng)急資源調(diào)度的合理性、及時(shí)性。同時(shí)，伴隨應(yīng)急資源調(diào)度模型優(yōu)化，求解應(yīng)急資源調(diào)度模型的傳統(tǒng)遺傳算法、粒子群算法、MFO算法等存在陷入局部最優(yōu)和全局尋優(yōu)性能差的問題。

因此，本文在不同運(yùn)輸路況下，構(gòu)建消耗成本最低、裝車時(shí)間最少的多目標(biāo)應(yīng)急資源調(diào)度模型即基于雙自適應(yīng)因子的改進(jìn)飛蛾撲火算法(DAMFO)，用以求解各災(zāi)害點(diǎn)的應(yīng)急資源配置方案，研究結(jié)果可為制定合理高效的應(yīng)急資源調(diào)度方案提供依據(jù)。

1 問題描述與模型建立

1.1 問題描述

設(shè)某城市有n個(gè)應(yīng)急資源儲(chǔ)備點(diǎn)(A1，A2，…，An)，有m個(gè)受災(zāi)點(diǎn)(B1，B2，…，Bm)，儲(chǔ)備點(diǎn)提供p種物資(C1，C2，…，Cp)。設(shè)aqi表示第q種應(yīng)急物資在第i個(gè)儲(chǔ)備點(diǎn)的儲(chǔ)存量，bqj表示第j個(gè)受災(zāi)點(diǎn)對(duì)第q種應(yīng)急物資的需求量(1≤i≤n,1≤j≤m,1≤q≤p)。設(shè)從第i個(gè)應(yīng)急物資儲(chǔ)備點(diǎn)到第j個(gè)受災(zāi)點(diǎn)的運(yùn)輸?shù)缆飞希嬖诘缆窔牡目赡苄裕琗ij表示道路毀壞的距離，T0表示單位距離下修復(fù)毀壞道路的時(shí)間，Tend表示修復(fù)毀壞道路的最晚修復(fù)時(shí)間。設(shè)0≤α<β表示道路正常通行；β≤α<δ表示道路毀壞，需要修復(fù)，若修復(fù)時(shí)間T0Xij

1.2 條件假設(shè)

假設(shè)儲(chǔ)備點(diǎn)應(yīng)急物資總量、運(yùn)輸車輛足夠，受災(zāi)點(diǎn)對(duì)每種應(yīng)急物資的需求度、每輛車運(yùn)輸速速一致，最短運(yùn)輸路線只有1條且運(yùn)輸路況只能是道路正常、道路毀壞可修復(fù)或道路毀壞不可修復(fù)、道路毀壞不可通行中的1種。

1.3 模型建立

1)飛蛾撲火優(yōu)化算法

飛蛾撲火優(yōu)化(MFO)算法主要靈感來自飛蛾的定向水平飛行方式。MFO算法具有的特殊結(jié)構(gòu)，在低維時(shí)能夠更好地協(xié)調(diào)局部和全局的搜索能力，使其不容易陷入局部極值而找到最優(yōu)解，但在高維每次迭代中都會(huì)選取當(dāng)前最優(yōu)解，容易陷入局部最優(yōu)而導(dǎo)致過早收斂，由于種群多樣性低，使得全局尋優(yōu)性能不高。

2)基于Levy飛行的飛蛾撲火優(yōu)化算法

基于Levy飛行的飛蛾撲火優(yōu)化(LMFO)算法在MFO算法的基礎(chǔ)上增加了1個(gè)隨機(jī)擾動(dòng)，該隨機(jī)擾動(dòng)被稱為L(zhǎng)evy飛行。Levy飛行的突出特點(diǎn)是大量小步移動(dòng)，偶爾有較大步移動(dòng)，這樣飛蛾就不會(huì)在1個(gè)地方一直重復(fù)搜索，進(jìn)而改變1個(gè)系統(tǒng)的行為。對(duì)飛蛾群執(zhí)行1次Levy飛行，如式(1)～(4)所示。

飛蛾實(shí)時(shí)位置如式(1)所示：

(1)

Levy的分布如式(2)所示：

Levy(β)～u=t-β(1<β<3)

(2)

Levy(β)的隨機(jī)數(shù)如式(3)所示：

(3)

式中：u和v服從標(biāo)準(zhǔn)正態(tài)分布；?是正態(tài)分布的方差，如式(4)所示：

(4)

式中：Γ是1個(gè)標(biāo)準(zhǔn)的伽碼函數(shù)；β=1.5。

3)模型建立

經(jīng)典MFO算法需要給定飛蛾位置的上下邊界，邊界條件是飛蛾位置的線性組合，無法直接獲得。為解決此問題，以運(yùn)輸過程中消耗成本最低、物資裝車時(shí)間最少為優(yōu)化目標(biāo)，引入變量歸一化約束條件作為懲罰項(xiàng)，建立如下模型如式(5)～(14)所示：

(5)

(6)

s.t.

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

2 改進(jìn)飛蛾撲火算法

MFO算法和LMFO算法均使用對(duì)數(shù)螺旋函數(shù)更新飛蛾位置，使飛蛾容易陷入局部最優(yōu)，另外MFO算法中，無論是迭代初期還是迭代后期，飛蛾向火焰飛行的速度一致，無法獲得全局最優(yōu)解。因此，本文提出基于雙自適應(yīng)因子的改進(jìn)MFO算法DAMFO。該算法在MFO算法或LMFO算法的基礎(chǔ)上做了如下改進(jìn)：

1)增加自適應(yīng)權(quán)值因子，提升初期全局搜索能力。原飛蛾位置更新公式如式(15)～(16)所示：

S(Mi,Fj)=Diexp(bt)×cos(2πt)+W0Fj

(15)

(16)

式中：W0為自適應(yīng)權(quán)值因子；li為當(dāng)前迭代次數(shù)；lM為最大迭代次數(shù)。隨迭代進(jìn)行，自適應(yīng)權(quán)值逐漸變小，飛蛾擁有更強(qiáng)的跳出局部最優(yōu)解的能力。

2)增加自適應(yīng)速度因子，減緩迭代初期飛行速度，加快迭代后期收斂速度。原飛蛾位置更新公式中的t參數(shù)可由式(17)～(18)隨機(jī)產(chǎn)生：

t=rand([W1,-1])

(17)

(18)

式中：rand([a,b])函數(shù)表示在區(qū)間[a,b]間均勻產(chǎn)生1個(gè)隨機(jī)數(shù)；自適應(yīng)速度因子W1表示通過該方法，在迭代后期t生成較小值的概率更高，從而加速整個(gè)系統(tǒng)的收斂。

3)改進(jìn)種群初始化方法，提高初始種群質(zhì)量。

步驟2：針對(duì)每組q，j，計(jì)算差值如式(19)所示：

(19)

(20)

3 算例分析

3.1 算例描述

假設(shè)在某地區(qū)發(fā)生地震災(zāi)害，出現(xiàn)2個(gè)受災(zāi)點(diǎn)B1，B2，該地區(qū)應(yīng)急資源儲(chǔ)備點(diǎn)共有5個(gè)A1，A2，A3，A4，A5。受災(zāi)點(diǎn)需要儲(chǔ)備點(diǎn)提供的應(yīng)急物資共有3種，分別為急救藥品C1、食品C2，帳篷C3。儲(chǔ)備點(diǎn)可以提供的各種應(yīng)急物資數(shù)量和受災(zāi)點(diǎn)需要的各種應(yīng)急物資數(shù)量見表1。車輛在儲(chǔ)備點(diǎn)到受災(zāi)點(diǎn)的路途中運(yùn)輸單位物資量所產(chǎn)生的成本C，見表2。各物資在儲(chǔ)備點(diǎn)的單位裝車時(shí)間見表3。儲(chǔ)備點(diǎn)至受災(zāi)點(diǎn)的交通道路損毀距離Xij和相應(yīng)損毀程度系數(shù)α見表4～5。設(shè)當(dāng)0≤α≤0.2，表示交通道路可以通行，不需要工人對(duì)道路進(jìn)行施工修復(fù)；當(dāng)0.2<α<0.7，表示交通道路可以修復(fù)，設(shè)單位距離下修復(fù)毀壞道路的時(shí)間為0.5 h(即T0=0.5 h)，最長(zhǎng)修復(fù)時(shí)間不得超過3 h(即Tend=3 h)，當(dāng)修復(fù)時(shí)間T0Xij

表1 儲(chǔ)備點(diǎn)提供的物資數(shù)量及受災(zāi)點(diǎn)需要的物資數(shù)量

表2 儲(chǔ)備點(diǎn)各物資的單位運(yùn)輸量成本

表3 各物資在儲(chǔ)備點(diǎn)裝車時(shí)間

表4 儲(chǔ)備點(diǎn)至受災(zāi)點(diǎn)的道路損毀距離

表5 儲(chǔ)備點(diǎn)至受災(zāi)點(diǎn)的道路損毀程度系數(shù)

設(shè)置時(shí)間成本系數(shù)θ為1，權(quán)重系數(shù)滿足w1+w2=1。根據(jù)專家評(píng)價(jià)法，分析運(yùn)輸成本權(quán)重w1為1/4，時(shí)間成本權(quán)重w2為3/4，即對(duì)應(yīng)急資源調(diào)度配置方案來說，應(yīng)急物資裝車時(shí)間成本比運(yùn)輸成本更重要。MFO算法、LMFO算法和DAMFO算法的參數(shù)設(shè)置如下：飛蛾群體數(shù)為500個(gè)，最大迭代次數(shù)為500，個(gè)體位置信息的維度根據(jù)算例中5個(gè)儲(chǔ)備點(diǎn)對(duì)2個(gè)受災(zāi)點(diǎn)提供的3種應(yīng)急物資確定為30，LMFO算法和采用Levy飛行的DAMFO算法中乘數(shù)因子設(shè)置為0.05。

3.2 仿真結(jié)果

為驗(yàn)證算法的有效性，主要比對(duì)隨機(jī)種群初始化場(chǎng)景下和改進(jìn)種群初始化場(chǎng)景下的MFO算法、LMFO算法和DAMFO算法在求解應(yīng)急資源調(diào)度優(yōu)化模型下的尋優(yōu)性能。為了公平性，上述算法測(cè)試時(shí)均采用相同的飛蛾初始種群，即在迭代開始前擁有相同的適應(yīng)度值。

1)隨機(jī)種群初始化場(chǎng)景下，xqij在[0,1]范圍內(nèi)均勻分布，MFO算法、LMFO算法、DAMFO算法的收斂速度、適應(yīng)度如圖1～2所示。

圖1 收斂速度比較

由圖1可知，在迭代初期，DAMFO算法的收斂速度相對(duì)最快，MFO算法次之，LMFO算法最慢。這是由于LMFO算法增加了Levy飛行，以期在尋優(yōu)初期跳出局部最優(yōu)點(diǎn)而找到全局最優(yōu)值，但也明顯拖累整個(gè)算法的收斂速度。由圖2可知，在迭代后期，DAMFO算法獲得更好的性能，具有相對(duì)最低的適應(yīng)度值；MFO算法直接陷入局部最優(yōu)點(diǎn)；而LMFO算法在迭代375次之后跳出局部最優(yōu)點(diǎn)，適應(yīng)度值大幅下降，但性能仍低于DAMFO算法。

圖2 收斂性能比較

2)改進(jìn)種群初始化場(chǎng)景下，飛蛾初始種群出現(xiàn)在全局最優(yōu)點(diǎn)附近的比例得到有效提升，在迭代尋優(yōu)過程中能更快地找到全局最優(yōu)點(diǎn)。在迭代尋優(yōu)初期，未采用Levy飛行的MFO算法和DAMFO算法適應(yīng)度值快速下降，DAMFO算法雖然在前期增加全局搜索能力，但其收斂性能與MFO算法旗鼓相當(dāng)。在迭代后期，未采用Levy飛行的DAMFO算法逐漸收斂，而其他算法仍需更多迭代次數(shù)才能收斂至全局最優(yōu)點(diǎn)。另外，由于采用快速收斂機(jī)制，即使采用Levy飛行的DAMFO算法也獲得和MFO算法相似的性能，遠(yuǎn)遠(yuǎn)優(yōu)于LMFO算法性能，這也說明LMFO算法在該場(chǎng)景中并不一定提升全局最優(yōu)搜索能力。

3)使用不同算法求解得到的最終適應(yīng)度值見表6，在隨機(jī)均勻種群初始化場(chǎng)景下適應(yīng)度值為851.01，改進(jìn)種群初始化場(chǎng)景下適應(yīng)度值為360.92。由表6可知，當(dāng)采用特殊初始化種群方法后，MFO算法、LMFO算法和DAMFO算法均有效提升最終收斂性能。

表6 最終適應(yīng)度值

4)MFO算法和DAMFO算法的最優(yōu)調(diào)度方案見表7。由式(13)計(jì)算可得，當(dāng)?shù)缆窡o損壞時(shí)，MFO算法和DAMFO算法的單目標(biāo)函數(shù)值minf分別為309.3，308.75，后者在裝車時(shí)間及運(yùn)載成本方面節(jié)約55%；當(dāng)?shù)缆酚袚p壞時(shí)，MFO算法和DAMFO算法的單目標(biāo)函數(shù)值minf為328.55，328.252 5，后者在裝車時(shí)間及運(yùn)載成本方面節(jié)約了29.75%。分析得出無論是否存在道路損壞情況，DAMFO算法的最優(yōu)方案均優(yōu)于MFO算法的最優(yōu)方案，在合理調(diào)配應(yīng)急資源和節(jié)約裝車時(shí)間、運(yùn)載成本方面表現(xiàn)出更大優(yōu)勢(shì)。

表7 MFO/DAMFO算法的最優(yōu)調(diào)度方案

4 結(jié)論

1)針對(duì)災(zāi)害事故發(fā)生后，為解決制定及時(shí)、有效的多災(zāi)害點(diǎn)應(yīng)急資源調(diào)度方案問題，將應(yīng)急資源在不同運(yùn)輸路況下運(yùn)輸?shù)淖畹拖某杀尽⒆钌傺b車時(shí)間作為優(yōu)化目標(biāo)，引入變量歸一化和約束條件作為懲罰項(xiàng)，構(gòu)建應(yīng)急資源調(diào)度模型。

2)提出基于雙自適應(yīng)因子的改進(jìn)MFO算法DAMFO，增加自適應(yīng)權(quán)值因子，提升初期全局搜索能力；增加自適應(yīng)速度因子，加快迭代后期收斂速度。

3)仿真結(jié)果顯示，DAMFO算法有效改善MFO算法和LMFO算法的尋優(yōu)性能等問題，在求解模型時(shí)能夠提供精確度、滿意度更高的應(yīng)急資源調(diào)度方案，具有較高的應(yīng)用價(jià)值。