NSGA-II算法的改進及其在應急管理中的應用

汪文文，方 璽，何 朗，劉 揚，張 亮

WANG Wenwen,FANG Xi,HE Lang,LIU Yang,ZHANG Liang

武漢理工大學 理學院，武漢 430070

School of Science,Wuhan University of Technology,Wuhan 430070,China

1 引言

近年來，國內(nèi)各種突發(fā)事件頻發(fā)，造成了極大的人員傷亡和經(jīng)濟損失，如2008年“5·12”汶川特大地震，2015年天津大爆炸，2016年湖北、安徽、河北多地區(qū)暴雨等。在突發(fā)事件[1]頻出不窮的情況下，應急問題已經(jīng)成為十分緊迫的重大問題。在應急管理中，應急設施是救援過程中必不可少的組成部分，研究應急管理中的設施選址對于提高應急管理能力有重要的應用價值，吸引了國內(nèi)外眾多研究學者的目光。

應急選址優(yōu)化問題是城市應急系統(tǒng)中不可或缺的一部分，近年來無數(shù)學者對其進行研究，提出不同的模型。Salman等[2]基于突發(fā)事件下的應急選址，通過最大化需求覆蓋，提出0-1整數(shù)規(guī)劃求解；Wohlgemuth等[3]考慮最小化配送中心到需求點的距離、區(qū)域內(nèi)的需求點非覆蓋需求建立多目標模型；由于傳統(tǒng)靜態(tài)、確定型選址模型在應用上僅考慮單一時間，Ballou[4]首先提出了動態(tài)設施選址問題，研究了如何選擇一個倉庫使其在規(guī)劃期內(nèi)實現(xiàn)利潤最大；Gao等[5]將動態(tài)選址問題分為LAP與VRP兩部分，并在動態(tài)環(huán)境下考慮隨機與循環(huán)流量等因素，對模型進行求解；Marufuzzaman等[6]構(gòu)建一個基于容量的動態(tài)選址模型，以期在滿足需求點的需求條件下以最小的代價在決策時間內(nèi)給出選址方案；動態(tài)模型被運用到多個領域，如戰(zhàn)斗物流[7]、電商物流[8]、應急物流等。由于靜態(tài)模型考慮其選址因素均獨立于時間，而動態(tài)選址考慮了在實際應用中需求量、能源價格、市場增長等可變因素，其模型在實際應用中具有更強的適應性，且更加科學。

應急選址所需要考慮的因素極為復雜，通常需要考慮多個因素，其所研究的問題為多目標優(yōu)化問題，該優(yōu)化問題一般采用進化算法進行求解，例如SPEA、PSO、NSGA、MOEA/D。Dong等[9]提出一種基于MOEA/D的改進算法，通過多樣性檢測和混合種群操作增強解的全局搜索能力；MOEA/D算法效率較高，但其最優(yōu)解的分布隨機性較大；NSGA-II采用非支配排序機制降低算法的復雜度，且Pareto最優(yōu)解集具有良好的分布性，是一種綜合性能較好的算法。Badri等[10]構(gòu)建了一個有約束的多目標優(yōu)化問題，并通過NSGA-II、SPEA2以及PESA-II進行求解，實驗結(jié)果顯示NSGA-II可產(chǎn)生相對較優(yōu)的Pareto前沿。由于NSGA-II在收斂過程中易產(chǎn)生重復個體而陷入早熟，對于NSGA-II算法的改進逐步被提出，Zade等[11]提出一種基于交叉和變異算子改進的NSGA-II，增強了解集的多樣性以及精確性，但增加了算法的計算量；常輝等[12]提出基于遞歸的快速排序法，增強了算法的魯棒性，降低了算法的復雜性，但其僅適用于雙目標問題，而對于多目標問題其效率則具有一定的局限性。在實際應用中，單一的算法對于求解多目標優(yōu)化問題往往已不能滿足需求，混合優(yōu)化算法逐步被提出，Li等[13]提出了一種基于改進的NSGA-II的二階段變量值選擇去解決包含多個解的質(zhì)量特性，但在降低算法復雜度的同時造成優(yōu)秀解在迭代過程中逐步損失。因此對于NSGA-II算法的改進仍需持續(xù)深入研究。本文擬通過將禁忌搜索算法融入到NSGA-II的精英策略中，加強算法的局部搜索能力，同時保留其多樣性以及分布性，并通過數(shù)值算例驗證算法的收斂性及分布性。

2 多目標動態(tài)選址模型

2.1 應急物資點選址決策目標評價體系

本文考慮以救援時間為評價的主要指標，用物資效用反映時效性，以災區(qū)滿意度反映公平性，以臨時物資配送中心的個數(shù)反映均衡性，建立多目標動態(tài)選址模型；在模型求解時，充分對3個目標進行分析，通過改進的NSGA-II算法進行求解，得到更為合適的選址方案，對于應急管理系統(tǒng)進行科學決策具有一定的指導意義。

2.2 基本參數(shù)與決策變量

假定平面上存在3個集合，即需求點集合、臨時物資候選點集合和固定物資點，已知任意兩個點之間的可行距離以及汽車運行速度，選取合適的臨時物資點，并得到最優(yōu)調(diào)度方案。本文考慮物資效用、臨時物資點個數(shù)以及災區(qū)滿意度作為目標函數(shù)，基本參數(shù)如下：在地震災害中人的存活率與時間的關系，I為固定物資點集合，J為需求點集合，S為臨時物資候選點集合，V為各種汽車運行速度的集合。候選點s被選擇，則hs=1，否則hs=0。

2.3 多目標動態(tài)選址模型

基于應急物資中心選址決策目標評價體系的分析，本文將物資儲備應急效用、災區(qū)滿意度、臨時物資點的數(shù)目作為目標決策函數(shù)。

由文獻[14]知某次地震災害后，受災人員的存活率與時間的關系為：

定義物資儲備應急效用為各個物資點的有效利用量：

定義受災區(qū)域的滿意度為各個物資點（包括固定物資點和臨時物資點）的儲備效用與各個災區(qū)所需要應急物資之比，且災區(qū)的滿意度值盡可能大，即：

式（5）保證了在固定物資點資源都用盡之后，才開始用臨時物資點；式（6）表明由臨時物資點運到各個災區(qū)的資源量應該小于其儲備量；式（7）表示運往災區(qū)的物資量應該小于其需求量，以減少不必要的經(jīng)濟損失；式（8）保證運輸量有意義。

本文所構(gòu)建的為多目標動態(tài)選址模型，與傳統(tǒng)靜態(tài)選址模型的主要區(qū)別在于隨著災害的持續(xù)發(fā)展，往往會導致災區(qū)對于應急物資的需求量逐步遞增，原有的物資點并不能向災區(qū)提供充足的物資，此時會造成供不應求的狀況。而本文所構(gòu)建的模型則將這一因素考慮進來，增加了模型的魯棒性。

針對自變量個數(shù)較多且最優(yōu)解較為復雜的多目標優(yōu)化問題，傳統(tǒng)的目標優(yōu)化算法MOEA/D、NSGA-II的收斂性以及所得解的精度均較差。同時MOEA/D進行加權(quán)存在一定的主觀因素，而本文所研究的背景為應急物資選址，對于目標函數(shù)的權(quán)重無法給出比較客觀的分析，而NSGA-II在迭代搜索過程中難以找到孤立點，且子代容易產(chǎn)生重復個體，因此本文擬在NSGA-II的基礎上加入禁忌搜索[15-16]算法設計一種混合優(yōu)化算法，以期算法能夠達到較強的收斂效果。

3NSGA-II及改進

本文研究的內(nèi)容為一個多目標優(yōu)化問題，對于多目標優(yōu)化問題，一般采用多目標進化算法（MOEAs）[17]和多目標轉(zhuǎn)換為單目標兩種方式來進行求解，然而多目標問題轉(zhuǎn)化為單目標問題則可能造成所求的解為非可行解，因此本文采用MOEAs進行求解。NSGA-II是一種較為常用的MOEAs算法，其優(yōu)點在于運行效率高，所得解集具有良好的分布性，其主要不足在于難以找到孤立點，且容易產(chǎn)生大量重復個體。為克服上述缺點，本文提出一種改進的NSGA-II算法，主要在以下兩方面進行改進：

（1）改進遺傳算子的變異操作，變異個體從當前個體的領域產(chǎn)生，而非隨機生成，從而減少了重復個體產(chǎn)生的概率，同時提高了搜索效率。

（2）提出一種混合的精英策略，在進行合并的時候，將父代個體、遺傳算子所得的子代個體，以及禁忌搜索[18]所得子代進行合并，增強了子代群體的多樣性。

具體操作如下：

（1）變異算子的設計

變異算子影響著遺傳操作的效果，其可跳出局部最優(yōu)解，從而達到全局最優(yōu)解，而變異概率則影響著變異算子的效果。傳統(tǒng)的變異具有一定的隨機性，在搜索過程中易產(chǎn)生重復個體且具有一定的隨機性。本文采用變異個體從當前解的鄰域中產(chǎn)生而非隨機產(chǎn)生，加強解的局部搜索效率，且變異概率Pm隨著所產(chǎn)生的鄰域解的效果而動態(tài)變化，當鄰域最優(yōu)解滿足藐視準則，則Pm=1，否則Pm=0。當Pm=1時，則將當前個體作為變異個體加入到子代種群中。通過這種改進，減少了重復個體產(chǎn)生的概率，同時提高了搜索效率。可以通過增加搜索到孤立點的概率，從而增加個體的多樣性。

（2）混合精英策略

本文通過將禁忌搜索算法引入到精英策略中，以期增加解集的多樣性以及均勻性。令合并之后的解集為Rt=Pt?Gt?Tt，其中Pt為父代個體，Gt為遺傳算子所得個體，Tt為禁忌搜索算子所得個體。其次由非支配排序及擁擠度距離從Rt中選取前N個個體作為下一代父代個體Rt+1，通過這種操作可以保留NSGA-II避免父代優(yōu)良個體流失的優(yōu)點，同時增強局部搜索能力，進而減少子代中重復個體的個數(shù)，增強解集的多樣性。

禁忌搜索的策略如下：

（1）初始解

禁忌搜索算法對初始解的依賴性較高，因此初始解從父代個體非支配排序為1的個體中隨機選取。

（2）鄰域解

初始迭代，為增加搜索到最優(yōu)解的概率，擴大搜索范圍，隨著迭代的逐步進行，所得解趨近于最優(yōu)解，因此應該縮小搜索的范圍，避免重復搜索。鄰域生成以及搜索范圍分別按以下公式更新：

邊界處理：

若Xj＞UX,Xj=Xj+LX-UX，否則Xj=Xj-(LXUX)。

（3）候選解

對于給定個體X，計算其所有鄰域解的計算量較大，因此需要一定的策略選取候選解。本文采用非支配排序和擁擠度算子從所給候選解里面選取一定數(shù)量的解作為候選解N(x)。

（4）藐視準則

X∈opt{N(x)}，若存在X?Xbest，則X被選為下一個當前解。

（5）禁忌表

當前解X已被禁忌，當且僅當?Xj∈Tabulist，滿足

算法主要步驟如下：

步驟1產(chǎn)生初始種群Pop。

步驟2快速非支配排序，在進行選擇運算之間，根據(jù)個體非劣解的水平先對種群進行分層得到父代個體Pt。

步驟3遺傳算子操作（選擇、交叉和變異），變異算子采取本文所提方式進行，產(chǎn)生新的個體Gt。

步驟4禁忌搜索策略：按照本文所提的禁忌搜索算法的流程執(zhí)行，產(chǎn)生新的個體Tt。

步驟5精英策略，首先將父代Pt、遺傳算子Gt和禁忌搜索算子Tt合并成一個種群Rt=Pt?Gt?Tt，種群Rt的個體數(shù)目變?yōu)?N；其次，對種群Rt進行非支配排序，并計算相應的擁擠度距離；最后，根據(jù)等級的高低逐一選取個體，直至個體總數(shù)達到N，令其為新一輪進化過程的父代種群Pt+1。

步驟6重復步驟3～步驟5直至滿足迭代終止條件。

根據(jù)步驟1～步驟6可得NSGA-II-TS算法設計流程圖如圖1所示。

圖1 NSGA-II-TS流程圖

禁忌搜索算法在搜索過程中所產(chǎn)生的候選解在其當前解的鄰域產(chǎn)生，而非隨機生成，且其可以接受次優(yōu)解，具有較強的爬山能力，因此其搜索到最優(yōu)解的概率增大，同時保留了NSGA-II的遺傳算子操作，從而保留了NSGA-II所產(chǎn)生個體多樣且均勻的優(yōu)點。基于應急選址對于實時性和優(yōu)化性同等重要，本文通過在NSGA-II精英策略中加入禁忌搜索算法，設計一種混合的進化優(yōu)化算法，一方面加強解的局部尋優(yōu)能力，另一方面保留NSGA-II較優(yōu)的全局搜索能力，從而使得收斂到局部最優(yōu)解的速度加快且所得解的精度提高。

4 數(shù)值算例及結(jié)果分析

仿真實驗分為兩部分：首先對有界閉域上連續(xù)函數(shù)全局優(yōu)化進行算法的有效性分析；其次將其應用到離散應急選址問題上進行算法分析。本文所有的仿真實驗平臺為Intel?CoreTMi5-4200H，4.0 GB RAM，實驗環(huán)境為MATLAB R2012b（8.0.0.783）。

4.1 連續(xù)函數(shù)的應用

本文選擇經(jīng)典二維測試函數(shù)ZDT1、ZDT2、ZDT3[19]對算法進行實證分析，函數(shù)表達式如表1所示，選取經(jīng)典NSGA-II、MOEA/D與NSGA-II-TS進行對比分析，通過Pareto前沿對算法的收斂性以及分布性進行分析。

ZDT1、ZDT2、ZDT3分別在變量個數(shù)為30、100時進行測試，設置算法的種群大小為500，迭代次數(shù)為100，分別獨立運行20次，3種算法得到的Pareto前沿對比圖如圖2所示。從圖2的Pareto前沿對比圖中可以看出，通過NSGA-II-TS得到的Pareto收斂性以及多樣性明顯優(yōu)于NSGA-II和MOEA/D、NSGA-II-TS所得的Pareto光滑、均勻，且基本上和真實的Pareto重合，而MOEA/D所得Pareto存在較多間斷點，NSGA-II算法雖然得到的曲線形狀與真實的Pareto基本一致，但其收斂性遠遠不如NSGA-II-TS；同時隨著決策變量增加至100時，MOEA/D算法的效率明顯下降，逼近效果尤為差，且需要至少300次迭代才可較好地逼近，NSGA-II算法可在100次迭代中逼近真實Pareto，但其效果遠遠不如NSGA-II-TS。由此說明，無論是較少的決策變量還是較多的決策變量，NSGA-II-TS均可以較好地逼近最優(yōu)Pareto。

表1 測試函數(shù)

圖2 ZDT系列函數(shù)Pareto對比圖

表2 世代距離

表3 spacing指標值

本文為進一步說明3種算法的收斂性以及解集的均勻性，分別采用Deb[20]提出的世代距離和Schott[21]提出的spacing，對算法進行定量分析。表2和表3分別為對ZDT系列函數(shù)在不同變量下測試20次所獲得的spacing以及世代距離的均值、標準差和中值。由表1和表2可以看出，在20次實驗中，NSGA-II-TS獲得的spacing值和世代距離值均小于NSGA-II、MOEA/D，且NSGA-II-TS的波動性比較小，這種優(yōu)勢在決策變量增加至100時更為明顯，說明本文算法在解決連續(xù)多目標優(yōu)化問題上具有更好的收斂性。

4.2 應用分析

設置候選臨時應急物資點為100個，固定點為3個，需求點為10個，設定種群為100，迭代次數(shù)100，實驗20次，得到最優(yōu)Pareto解集。由于在實際應急救援中需給出最優(yōu)行動方案，本文采用理想點法[11]對組合解的優(yōu)劣程度進行評判，得出在該標準下的最優(yōu)應急方案。

首先，利用公式進行標準化：

其次，選擇理想點：

最后，使用歐式距離評測解的好壞，d(h)越小越好：

表4為各個算法通過理想點法所確定的最優(yōu)解。由表4可知，NSGA-II-TS效果比NSGA-II和MOEA/D算法好。首先，對于應急物資點個數(shù)NSGA-II比NSGAII-TS少兩個，但其物資效用度卻比NSGA-II-TS小了833 m3，并且災區(qū)的滿意度也比NSGA-II-TS小了4.6%，保證災區(qū)人民的滿意度較大，且物資效用達到最大，同比增加兩個物資點是值得考慮的；其次，對于MOEA/D算法，其物資效用度平均值基本在47000以上，達到比較好的效果，與NSGA-II-TS差別較小，然而其物資點則增加了NSGA-II-TS的一倍，代價較大，因此NSGA-II-TS在災區(qū)滿意度相當?shù)那闆r下，表現(xiàn)效果更優(yōu)。

表4 各算法所得的平均值

圖3為NSGA-II、MOEA/D以及NSGA-II-TS基于理想點法所得最優(yōu)解的對比分析圖。由圖3可知，在物資效用和滿意度下NSGA-II-TS所得的最優(yōu)方案均高于NSGA-II和MOEA/D所得的最優(yōu)方案，且NSGA-II-TS的波動性非常小，說明每次實驗基本上可得到最優(yōu)方案。結(jié)合表3，可以得出NSGA-II-TS優(yōu)于傳統(tǒng)的多目標求解算法MOEA/D及NSGA-II。

表5為NSGA-II、MOEA/D以及NSGA-II-TS基于秩和檢驗的差異度分析，結(jié)果顯示3種算法在物資效用、臨時物資點個數(shù)、滿意度上的顯著水平分別為0.01、0、0.02。拒絕原假設：物資效用、臨時物資點個數(shù)、滿意度在NSGA-II、MOEA/D以及NSGA-II-TS算法上是相關的，即3種算法所得的結(jié)果在統(tǒng)計學上具有顯著性差異，從而說明基于表3的分析是可靠的，再次驗證了NSGA-II-TS較傳統(tǒng)的NSGA-II、MOEA/D算法更優(yōu)。

由上述對比分析，可以明顯地發(fā)現(xiàn)NSGA-II-TS在處理大規(guī)模應急選址問題上效果更優(yōu)，可見本文算法的改進是有效的，隨著應急選址規(guī)模的增大，算法的優(yōu)越性更是明顯。

5 結(jié)論

泥石流等突發(fā)自然災害造成的人員傷亡和經(jīng)濟損失十分巨大，因此應急中心選址問題是應急救援方案中的核心環(huán)節(jié)。根據(jù)突發(fā)性事件具有動態(tài)性和時效性，考慮將救濟物資效用、受災區(qū)域滿意度以及臨時物資點個數(shù)作為目標函數(shù)，建立多目標動態(tài)選址模型，提出了一種改進的NSGA-II算法。該算法在精英策略上引入禁忌搜索的思想，從而實現(xiàn)了局部和全局搜索能力同時達到較優(yōu)的結(jié)果，同時保留解集的多樣性和均勻性，其理論與數(shù)值分析結(jié)果優(yōu)良。

圖3 對比分析圖

表5 假設檢驗匯總

（1）通過經(jīng)典函數(shù)ZDT1、ZDT2和ZDT3分別進行測試，從Pareto前沿、世代距離以及spacing指標值驗證了算法的收斂性和分布性。實驗結(jié)果顯示NSGA-II-TS的收斂性以及Pareto解集的分布性相比NSGA-II、MOEA/D均有顯著的提升。

（2）實證分析中NSGA-II-TS比NSGA-II所得的物資效用高出818 m3，滿意度同比增長4.6%，而臨時物資點個數(shù)僅僅增加兩個；與MOEA/D算法相比較，在物資效用及滿意度略優(yōu)的情況下，其臨時物資點的個數(shù)少了一倍，體現(xiàn)了NSGA-II-TS算法在解決應急物資處理中更為高效。

（3）通過秩和檢驗驗證NSGA-II、MOEA/D及NSGAII-TS所得最優(yōu)解之間的差異性，結(jié)果顯示3種算法在物資效用、臨時物資點個數(shù)、滿意度在統(tǒng)計學上具有顯著性差異，再次驗證了NSGA-II-TS較傳統(tǒng)的NSGA-II、MOEA/D算法在處理大規(guī)模應急選址優(yōu)化問題上表現(xiàn)更優(yōu)。

本文提出的算法在突發(fā)性災害危機的應急管理以及其他保障體系建設問題中具有較高的應用價值。