基于改進飛蛾撲火算法的應急資源調度研究*

黃彩霞，劉年平，謝曉君

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

0 引言

由于各類突發事件頻發,對人民群眾的生命財產安全造成巨大威脅，應急資源的及時安排和合理調度對減小災后損失極其重要，因此,研究應急資源調度模型意義重大。

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

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

因此，本文在不同運輸路況下，構建消耗成本最低、裝車時間最少的多目標應急資源調度模型即基于雙自適應因子的改進飛蛾撲火算法(DAMFO)，用以求解各災害點的應急資源配置方案，研究結果可為制定合理高效的應急資源調度方案提供依據。

1 問題描述與模型建立

1.1 問題描述

設某城市有n個應急資源儲備點(A1，A2，…，An)，有m個受災點(B1，B2，…，Bm)，儲備點提供p種物資(C1，C2，…，Cp)。設aqi表示第q種應急物資在第i個儲備點的儲存量，bqj表示第j個受災點對第q種應急物資的需求量(1≤i≤n,1≤j≤m,1≤q≤p)。設從第i個應急物資儲備點到第j個受災點的運輸道路上，存在道路毀壞的可能性，Xij表示道路毀壞的距離，T0表示單位距離下修復毀壞道路的時間，Tend表示修復毀壞道路的最晚修復時間。設0≤α<β表示道路正常通行；β≤α<δ表示道路毀壞，需要修復，若修復時間T0Xij

1.2 條件假設

假設儲備點應急物資總量、運輸車輛足夠，受災點對每種應急物資的需求度、每輛車運輸速速一致，最短運輸路線只有1條且運輸路況只能是道路正常、道路毀壞可修復或道路毀壞不可修復、道路毀壞不可通行中的1種。

1.3 模型建立

1)飛蛾撲火優化算法

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

2)基于Levy飛行的飛蛾撲火優化算法

基于Levy飛行的飛蛾撲火優化(LMFO)算法在MFO算法的基礎上增加了1個隨機擾動，該隨機擾動被稱為Levy飛行。Levy飛行的突出特點是大量小步移動，偶爾有較大步移動，這樣飛蛾就不會在1個地方一直重復搜索，進而改變1個系統的行為。對飛蛾群執行1次Levy飛行，如式(1)～(4)所示。

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

(1)

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

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

(2)

Levy(β)的隨機數如式(3)所示：

(3)

式中：u和v服從標準正態分布；?是正態分布的方差，如式(4)所示：

(4)

式中：Γ是1個標準的伽碼函數；β=1.5。

3)模型建立

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

(5)

(6)

s.t.

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

2 改進飛蛾撲火算法

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

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

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

(15)

(16)

式中：W0為自適應權值因子；li為當前迭代次數；lM為最大迭代次數。隨迭代進行，自適應權值逐漸變小，飛蛾擁有更強的跳出局部最優解的能力。

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

t=rand([W1,-1])

(17)

(18)

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

3)改進種群初始化方法，提高初始種群質量。

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

(19)

(20)

3 算例分析

3.1 算例描述

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

表1 儲備點提供的物資數量及受災點需要的物資數量

表2 儲備點各物資的單位運輸量成本

表3 各物資在儲備點裝車時間

表4 儲備點至受災點的道路損毀距離

表5 儲備點至受災點的道路損毀程度系數

設置時間成本系數θ為1，權重系數滿足w1+w2=1。根據專家評價法，分析運輸成本權重w1為1/4，時間成本權重w2為3/4，即對應急資源調度配置方案來說，應急物資裝車時間成本比運輸成本更重要。MFO算法、LMFO算法和DAMFO算法的參數設置如下：飛蛾群體數為500個，最大迭代次數為500，個體位置信息的維度根據算例中5個儲備點對2個受災點提供的3種應急物資確定為30，LMFO算法和采用Levy飛行的DAMFO算法中乘數因子設置為0.05。

3.2 仿真結果

為驗證算法的有效性，主要比對隨機種群初始化場景下和改進種群初始化場景下的MFO算法、LMFO算法和DAMFO算法在求解應急資源調度優化模型下的尋優性能。為了公平性，上述算法測試時均采用相同的飛蛾初始種群，即在迭代開始前擁有相同的適應度值。

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

圖1 收斂速度比較

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

圖2 收斂性能比較

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

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

表6 最終適應度值

4)MFO算法和DAMFO算法的最優調度方案見表7。由式(13)計算可得，當道路無損壞時，MFO算法和DAMFO算法的單目標函數值minf分別為309.3，308.75，后者在裝車時間及運載成本方面節約55%；當道路有損壞時，MFO算法和DAMFO算法的單目標函數值minf為328.55，328.252 5，后者在裝車時間及運載成本方面節約了29.75%。分析得出無論是否存在道路損壞情況，DAMFO算法的最優方案均優于MFO算法的最優方案，在合理調配應急資源和節約裝車時間、運載成本方面表現出更大優勢。

表7 MFO/DAMFO算法的最優調度方案

4 結論

1)針對災害事故發生后，為解決制定及時、有效的多災害點應急資源調度方案問題，將應急資源在不同運輸路況下運輸的最低消耗成本、最少裝車時間作為優化目標，引入變量歸一化和約束條件作為懲罰項，構建應急資源調度模型。

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

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