嚴華健 ，張國富 ，蘇兆品 ，劉 揚

（1. 合肥工業(yè)大學計算機與信息學院，合肥230601；2. 工業(yè)安全與應急技術安徽省重點實驗室（合肥工業(yè)大學），合肥230601；3. 安全關鍵工業(yè)測控技術教育部工程研究中心（合肥工業(yè)大學），合肥230601；4. 安徽省經(jīng)濟信息中心網(wǎng)絡管理處，合肥230001）

0 引言

近年來，我國各類自然災害多發(fā)頻發(fā)，給國民經(jīng)濟與社會發(fā)展造成巨大的損失。當災害發(fā)生后，如何及時、有效、合理地把各個儲備點有限的救災物資分配到災區(qū)的各個物資發(fā)放點，成為應急管理部門非常關心的一個重要問題，也是國內(nèi)外學者研究的一個熱點［1］。時至今日，現(xiàn)有針對救災物資分配問題的研究大致可以粗略地分為單目標優(yōu)化和多目標優(yōu)化兩大類。

在單目標優(yōu)化方面，Arora 等［2］針對單種醫(yī)療救援物資的分配，建立了費用約束下的救助率最大化模型。Altay［3］根據(jù)各儲備點和發(fā)放點之間的供需關系，構建了基于應急能力的救災物資分配整數(shù)規(guī)劃模型，以最大化物資分配效用。Wex等［4］構建了一種以最小化所有事故救援總完成時間為目標的各種救援力量分配模型。李永義等［5］基于災區(qū)區(qū)域大小、受災程度、人口密度和災區(qū)群眾需求構建了基于區(qū)間數(shù)的地震應急物資分配多屬性決策模型。王旭坪等［6］在考慮受災地區(qū)災民非理性攀比心理的基礎上，依據(jù)應急物資分配數(shù)量和配送時間最小化應急物資分配的攀比函數(shù)值。劉長石等［7］考慮應急物資分配的公平性，以所有需求點的損失攀比效應總和最小為目標構建應急物資分配模型。于冬梅等［8］從需求區(qū)域和應急設施應急服務質(zhì)量的視角構建了一個基于障礙約束、容量及安全庫存約束的應急設施選址與資源分配優(yōu)化模型，追求障礙約束下的應急設施最大時間滿意度。胡忠君等［9］對受災區(qū)域進行無監(jiān)督聚類劃分來明確各受災點的緊急度，然后基于粒子群算法最小化救災物資分配方案帶來的相關運輸費用。

在多目標優(yōu)化方面，王旭坪等［10］利用前景理論建立了一個最大化感知救援時間滿意度、災區(qū)需求滿意度和物資分配效用滿意度的三目標非線性整數(shù)規(guī)劃模型，并利用分散搜索算法對模型進行求解。Chang 等［11］構建了一個最小化物資需求不滿足度、總消耗時間和總運輸成本的三目標優(yōu)化模型，并提出了一種基于貪心策略的多目標遺傳算法來搜索最佳分配方案和配送路徑。陳瑩珍等［12］考慮發(fā)放點之間物資分配的公平性，建立了一個最大化發(fā)放點的物資滿足量、最小化最大運送時間的兩目標優(yōu)化模型，并引入差異演化算法進行求解。蘇兆品等［13］針對多儲備點、多發(fā)放點和多種救援物資，同時考慮應急響應總時間和應急資源總成本這兩個優(yōu)化目標，并設計了一種基于非支配排序差異演化和編碼修正機制的求解算法。張國富等［14］構建了一個最小化救援物資的未滿足量、最小化最大通行時間和最大化最小通行可靠度的三目標救災物資分配和調(diào)度集成優(yōu)化模型，并設計了一種基于二維第二代非支配排序遺傳算法（Non-dominated Sorted Genetic Algorithm 2，NSGA2）與蟻群優(yōu)化的混合智能搜索算法進行求解。陳剛等［15］同時考慮物資分配的效率和公平，構建了一個最小化受災點的總加權嫉妒值和最小化總物流成本的兩目標優(yōu)化模型，并引入NSGA2算法進行求解。

總的來說，基于單目標優(yōu)化的救災物資分配，雖然模型和算法簡單易行，但只能輸出一個最終解，很難在各個優(yōu)化指標上達到一個理想的平衡［16］；而對于救災物資多目標分配，最終可以輸出一個Pareto 解集，可以讓決策者根據(jù)實際的需求挑選合適的偏好解，但是，現(xiàn)有研究均局限于三個優(yōu)化目標之內(nèi)，且大都考慮時間、成本等因素。此外，在現(xiàn)有研究中，往往只考慮某種特定情況下的救災物資分配，例如所有種類的應急物資供應量都很充足，導致應急救援場景較為單一。眾所周知，災害應急響應是一個十分復雜的系統(tǒng)工程，需要考慮的因素牽涉到方方面面，甚至需要考慮社會心理學等，簡單的多目標優(yōu)化思路和單一的應急場景很難契合復雜的應急環(huán)境，難以滿足實際應急決策的需求。

基于上述背景，本文在總結已有工作的基礎上，引入社會心理學中的相關因素，從應急響應工程的系統(tǒng)性、社會性上進行設計，綜合考慮了應急響應總時間、災民恐慌度、救災物資未滿足度、物資分配公平性、災民損失、應急響應總成本等決策指標，構建了一個多儲備點、多發(fā)放點、多種救災物資的高維多目標（大于等于四個優(yōu)化目標）分配模型，從而為決策者提供更加全面、科學的思考。此外，本文引入了在高維多目標優(yōu)化方面性能優(yōu)越的移位密度估計（Shift-based Density Estimation，SDE）［17］和第二代強度帕累托進化算法（Strength Pareto Evolutionary Algorithm 2，SPEA2）［18］混合算法 SPEA2+SDE 來求解所提的模型，并針對SPEA2+SDE 無法處理約束的弊端，基于自適應個體修正（Adaptive Individual Repair，AIR）改進SPEA2+SDE，以提升它在解決本文的復雜高維多目標約束優(yōu)化問題上的性能。最后，通過和已有方法的對比實驗分析驗證了所提模型和算法的有效性。

1 問題描述

設某地區(qū)突發(fā)災害后，周邊有n 個救災物資儲備點A={a1，a2，…，an}，需要響應災區(qū)里 m 個物資發(fā)放點的應急需求G ={g1，g2，…，gm}。

定義1 ?gj∈ G(j ∈ {1，2，…，m})有一個相對的受災程度 λj∈ [0，1]，滿足越大，表示 gj受災情況越嚴重。

定義2 ?gj∈G 有一定的救災物資需求量Dj=其 中 ：r 表 示 救 災 物 資 的 種 類 ；表示發(fā)放點gj對第k 種救災物資的需求量，可由應急專家結合災情評估系統(tǒng)根據(jù)發(fā)放點gj的服務區(qū)域大小、受災程度、人口密度和災區(qū)群眾需求進行預估。注意，如果= 0，則gj不需要第k種救援物資。

定義3 ?ai∈ A(i ∈{1 ，2，…，n} )擁有一個救災物資儲備量其中表示儲備點 ai在第 k 種救災物資上的儲備量。注意，如果= 0，則ai沒有第k種救援物資。

定義4 考慮到各物資儲備點在經(jīng)濟和地域上的差異性，?ai∈A 有一個救災物資單位成本其中：表示儲備點ai在第k種救援物資上的單位成本。

定義5 ?ai∈A 對?gj∈G 有一個救災物資分配量Xij=表示儲備點 ai到發(fā)放點 gj在第 k 種救災物資上的分配量，滿足，即每個儲備點ai向所有發(fā)放點提供的第k 種救災物資的總量不可能超過第k種救災物資上的儲備量，且有，即所有儲備點向發(fā)放點gj提供的第k 種救災物資總量不會超過gj在第k 種救災物資上的需求量。

定義6 考慮到各儲備點之間物資種類和運輸工具的同 ，?ai∈ A 對 ?gj∈ G 有 一 個 單 位 廣 義 時 間 距 離 Tij=表示從儲備點ai到發(fā)放點gj在第k種救災物資上的單位運輸時間。

定義7 ?ai∈A 對?gj∈G 有一個單位運輸成本Cij=表示從儲備點 ai到發(fā)放點 gj在第 k 種救災物資上的單位運輸成本。

依據(jù)上述定義，對于n 個儲備點和m 個發(fā)放點，總共有n × m 個 Xij，構成一個可能的救災物資分配方案 Xn×m。在災害發(fā)生后，受災群眾心理相對比較脆弱，從災民心理風險感知的角度考慮，如果Xn×m分配不公平或配送不均衡，則容易消解災民對安置措施的安全感受，從而導致群體性恐慌事件等嚴重后果。因此，在災害應急響應過程中，尤其在資源短缺的時期，救災物資的分配應充分考慮災民對救災物資的到達時間和數(shù)量的敏感度。

首先，從救災物資的到達時間上來看，災民對救災物資分配的時效性最為敏感［19］，因此，決策者總是期望 Xn×m對應的應急響應總時間要盡可能地短，即

除此之外，各個發(fā)放點之間對救災物資的獲取時間存在著普遍的攀比心理，如果各發(fā)放點獲得救災物資的時間與其心理預期時間相差過大，則會給災民帶來額外的心理恐慌，從而極易誘導群體性事件的爆發(fā)。因此，根據(jù)前景理論的價值函數(shù)模型，可用

來表示發(fā)放點gj獲得救援物資的時間，用

來表示各個發(fā)放點獲得救援物資的平均時間，用δ*（一個較大的常數(shù)）來表示τ*對應的災民的心理恐慌度，則發(fā)放點gj區(qū)域中災民的心理恐慌度［19］為：

其中：α，β ∈ (0，1)為敏感性遞減系數(shù)，γ ∈ [1.5，2.5]為損失厭惡系數(shù)。據(jù)此，決策者總是期望分配方案Xn×m對應的災民心理恐慌度應該越小越好，即

在另一方面，從救災物資的數(shù)量上來看，決策者總是期望各發(fā)放點的救災物資未滿足度要盡可能地小，即

從社會心理學角度進一步考慮，當發(fā)放點gj的救災物資未滿足量

大于某個發(fā)放點gj*的未滿足量

時，gj區(qū)域的災民就會產(chǎn)生嫉妒心理，相反則沒有嫉妒反應?？捎?/p>

來表示gj區(qū)域的災民對gj*產(chǎn)生的嫉妒值。另外，出于對群體效應的考慮，受災情況越嚴重的地方越容易引發(fā)群體事件，其嫉妒值的權重應該越大。根據(jù)最小妒忌公平原則［15］，所有發(fā)放點的加權嫉妒值越小，災民的心理效用就會越均等，物資分配的公平性就越高，即

不僅如此，災民的損失也與救災物資未滿足量和受災程度具有典型的凸函數(shù)關系［20］，受災情況越嚴重，災民的損失會隨著救災物資未滿足量的增加而急劇增加。因此，可用

來最小化各發(fā)放點所負責災區(qū)內(nèi)災民的損失。

需要注意的是，救災物資分配還應該考慮經(jīng)濟因素，尤其在應急響應的中、后期，決策者需要謹慎考慮投入的成本（包括物資成本和運輸成本），總是期望應急響應總成本要盡可能地小，即

基于上述考慮，面向多個發(fā)放點的應急需求，對多個儲備點的多種救災物資同時進行分配，構建如式（7）所示的高維多目標優(yōu)化模型。該模型總共包含了6 個目標函數(shù)，基本囊括了應急響應工程的系統(tǒng)性、社會性等諸方面因素。需要指出的是，這樣設計的目的是為了盡可能地為決策者提供更加科學、全面的決策參考。在實際的應急決策中，決策者可以在決策支持系統(tǒng)中根據(jù)災情信息靈活選擇需要考慮的目標函數(shù)，從而提高系統(tǒng)的人機交互性。此外，第一個約束條件是為了保證任意一個儲備點在任意一種救災物資上的供給不存在資源沖突；第二個約束條件是為了確保任意一個發(fā)放點在任意一種救災物資上的需求不存在過度供應，從而避免資源浪費；第三個等式約束條件是為了讓每個儲備點竭盡全力地貢獻資源，從而盡可能地利用現(xiàn)有資源實現(xiàn)最佳的救援效果。

2 救災物資高維多目標分配算法

近年來，多目標進化算法在解決目標個數(shù)不多于三個的多目標優(yōu)化問題上展現(xiàn)了卓越的性能，例如主流的NSGA2［14］、SPEA2［19］等。然而，上述方法在求解高維多目標優(yōu)化問題時卻遇到極大的困難，這是因為隨著目標函數(shù)個數(shù)的增加，傳統(tǒng)的Pareto 占優(yōu)關系很難有效區(qū)分進化個體，而且使得逼近問題真實Pareto 前沿所需的候選解個數(shù)猛增，嚴重影響了算法的探索能力［21-22］。Li 等［17］從維護種群多樣性的角度出發(fā)，同時兼顧個體的分布和收斂信息，提出了一種移位密度估計策略。SDE通過遷移稀疏個體（即收斂性差的個體）在目標空間的位置，使其具有較大的密度值，從而讓其更容易被淘汰。Li 等［17］將 SDE 與 SPEA2 相結合應用于多個基準高維多目標優(yōu)化問題，取得了很好的效果。因此，本文引入簡單易行且效果突出的SPEA2+SDE 算法來求解如式（7）所示的救災物資高維多目標分配問題。

不過，需要特別指出的是，式（7）是一個典型的約束優(yōu)化問題，特別是還包含一個等式約束條件，而SPEA2+SDE 算法只見長于無約束優(yōu)化問題，因此，需要結合問題本身，對傳統(tǒng)的SPEA2+SDE 算法進行改進，以提高算法對這個特殊的高維多目標約束優(yōu)化問題的求解能力。

為了更清晰地表達，本章首先給出基本的SPEA2+SDE 算法，然后給出本文提出的個體編碼方案和個體修正（Individual Repair，IR）策略，最后介紹本文的改進型混合優(yōu)化算法。

2.1 基本的SPEA2+SDE算法

SPEA2+SDE 算法［17］包含進化種群（包含N 個個體）和外部種群（包含N′個體）兩部分，其大致流程如下：

步驟1 在初始化時，設置初始迭代次數(shù)t = 0。根據(jù)待求解的問題隨機生成初始進化種群Qt和外部種群Q′t。根據(jù)Q′t中N′個個體的編碼和多目標函數(shù)計算每個個體在每個目標函數(shù)上的值。

步驟2 如果t 已達最大迭代次數(shù)，則算法終止迭代，輸出Q′t中的所有非支配個體作為最終的最優(yōu)解集，否則算法繼續(xù)迭代。

步驟3 根據(jù)Qt中N 個個體的編碼和多目標函數(shù)計算每個個體在每個目標函數(shù)上的值。

步驟 4 將 Qt和 Q′t合并成一個組合種群 Vt= Qt+ Q′t，并對Vt中的每個個體的每個目標函數(shù)值進行min-max標準化。

步驟5 對Vt進行適應度分配。對于Vt中的每一個個體x，對應一個支配強度值S(x)，為x能夠支配的點的數(shù)目，即

據(jù)此，基于小生境法可得x 的原始適應度，即x 的支配者的強度值之和：

此外，每一個個體x還有一個擁擠度值：

步驟6 對Vt進行環(huán)境選擇。在Vt中，所有的F(x)＜1的個體（即非支配個體）被全部復制到新的外部種群Q′t+1。如果|Q′t+1|= N′，則此時環(huán)境選擇結束。如果|Q′t+1|＜ N′，則外部種群沒有填滿，那么對于在Vt中剩下的所有支配個體（即F(x)≥1），按照適應度值F(x)進行升序排序，選擇前面適應度值最小的 N′-|Q′t+1|個個體進入 Q′t+1。如果|Q′t+1|＞ N′，則外部種群過大，進行截尾操作，依次從Q′t+1中刪除一個與鄰近個體距離最?。ㄊ諗啃宰畈睿┑膫€體，直到滿足|Q′t+1|=N′。

步驟7 對新的外部種群Q′t+1進行min-max 標準化和適應度值分配。

步驟8 對Q′t+1進行交配選擇。運用錦標賽選擇方式依次從Q′t+1中選擇兩個父代個體進行模擬二進制交叉，生成兩個子代個體放入新的進化種群Qt+1中，直到|Qt+1|= N。

步驟9 對新的進化種群Qt+1進行多項式變異。

步驟10 t = t + 1，轉(zhuǎn)步驟2。

2.2 個體編碼方案

如前所述，對于n 個儲備點和m 個發(fā)放點，對應一個救災物資分配方案，這恰似一個二維組合優(yōu)化問題。而原始的SPEA2+SDE 算法采用一維實數(shù)編碼，很難描述Xn×m的二維特性。因此，本文設計了一種二維整數(shù)向量編碼來表示算法中的每個個體，如式（11）所示。這種編碼方式簡單直觀、容易理解，而且從根本上與本文救災物資分配問題的二維本質(zhì)相適應，且極大方便了后續(xù)AIR 策略的設計，從而為問題的求解和高效算法的設計奠定了良好的基礎。

式（11）中，個體編碼的每一行表示一個儲備點（共有n行），每一列表示一個發(fā)放點（共有m 列），編碼中的任意一個元素Xn×m即是儲備點ai向發(fā)放點gj提供的救災物資分配量。注意，式（7）是一個約束優(yōu)化問題，因此，任意一個如式（11）所示的編碼可能存在如下情況：

1）對每一行而言，如果 ?i ∈{1，2，…，n}，?k ∈ {1，2，…，則儲備點ai分配出去的第k 種救災物資總量超過了其本身所的擁有量，造成應急資源沖突。

2）對每一列而言，如果 ?j ∈ {1，2，…，m}，?k ∈ {1，2，…，則發(fā)放點gj分配得到的第k 種救災物資總量超過了其本身的需求量，造成應急資源浪費。

上述的兩種約束違背情況將會導致在算法進化過程中產(chǎn)生大量的不可行個體，從而影響算法的求解效率。而在應急響應這個特殊的場景中，時效性是一個首要衡量指標。因此，在2.3 節(jié)中，本文將在基本的SPEA2+SDE 算法中嵌入AIR 策略，旨在將各種環(huán)境中的不可行個體修正為一個可行個體，讓算法始終在近似可行域中進行探索，從而提升算法的整體性能。

2.3 自適應個體修正策略

IR 的目的是解決算法進化過程中可能出現(xiàn)的應急資源沖突和浪費現(xiàn)象。為此，在個體編碼中必須動態(tài)跟蹤每一個儲備點和發(fā)放點的物資供給情況：一旦某儲備點ai當前某種救災物資的可用量為0，則ai將不再響應任何其他發(fā)放點在這種救災物資上的需求；此外，一旦某發(fā)放點gj的救災物資未滿足度為0，則gj將不再向其他任何儲備點發(fā)送請求。

在實際應急救援過程中，對于儲備點而言，少數(shù)幾種救災物資量能夠滿足發(fā)放點的救災物資需求，而多數(shù)種類的救災物資量無法滿足發(fā)放點的救災物資需求是比較合理的，但是在現(xiàn)有研究中總是假設所有種類的救援物資全部充足或者全部不充足，將所有種類的救援物資使用同一種修正策略進行統(tǒng)一考慮，這顯然是不符合實際的，因此本文的IR 策略除了要滿足2.2 節(jié)的約束，還應該對物資量充足的救援物資以及物資量不充足的救援物資采用不同的修正策略分開考慮。在應急這個特殊的應用場景，當某種救災物資的儲備量不充分時，應該從儲備點出發(fā)，要求所有的儲備點盡可能貢獻完它們該種資源的全部物資，這樣才能最大化響應效率；而對于儲備量充足的某種救災物資，應該從發(fā)放點的角度出發(fā)，這時本文的IR 策略要求所有發(fā)放點對該種救災物資的應急需求都得到滿足，這樣才能最大化響應效果?；谏鲜鏊枷?，本文提出了AIR策略來應對不同情景下的決策需求。

首先，隨機選擇一種救援物資k ∈ {1，2，…，r}，若則執(zhí)行策略一，否則執(zhí)行策略二。

AIR策略一：

步驟1 從編碼中隨機選擇一個未檢查的行i（對應儲備點 ai）。

步驟2 檢查ai對第k種救災物資的供給情況，執(zhí)行：

來更新ai對gj*的供應量。重復此步驟，直到

來更新ai對gj*的供給量。重復此步驟，直到

步驟2.4 更新每個發(fā)放點在第k種救災物資上的剩余需求，對?j ∈ {1，2，…，m}，如果

步驟3 如果所有行檢查完畢（即所有儲備點分配完畢），修正結束，否則轉(zhuǎn)步驟1。

AIR策略二：

步驟1 從編碼中隨機選擇一個未檢查的列j（對應發(fā)放點 gj）。

步驟2 檢查gj在第k種救災物資上的響應情況，執(zhí)行：

步驟3 如果所有列檢查完畢（即所有發(fā)放點響應完畢）修正結束，否則轉(zhuǎn)步驟1。

遍歷所有k后，修正結束，否則返回重新操作。

需要注意的是，在AIR 策略一中，由于該種資源緊缺，本文從儲備點的視角出發(fā)，依次檢查每個儲備點的供給情況，讓每個儲備點盡可能地貢獻該種資源，一旦資源貢獻完則不再響應其他發(fā)放點的請求，而且對后續(xù)儲備點的修正均是基于發(fā)放點的剩余需求量進行操作，從而有效保證修正后的個體編碼滿足式（7）中的約束條件。同理，在AIR 策略二中，由于該種資源非常充分，本文從發(fā)放點的視角出發(fā)，依次檢查每個發(fā)放點的響應情況，讓每個發(fā)放點盡可能地得到滿足，一旦需求得到滿足則不再向其他儲備點發(fā)送請求，而且對后續(xù)發(fā)放點的修正均是基于儲備點的剩余資源量進行操作，從而也確保了修正后的個體編碼滿足約束條件。由此，可以清楚地看到，個體編碼在經(jīng)過修正之后，發(fā)放點的需求能夠根據(jù)儲備點的現(xiàn)有資源狀況盡可能地得到滿足（盡可能的向最優(yōu)解靠近），而且可以有效解決可能出現(xiàn)的應急資源沖突和浪費現(xiàn)象。

2.4 SPEA2+SDE+AIR算法描述

本文將上述的個體編碼方案和修正策略嵌入到基本的SPEA2+SDE 算法中，提出一種改進型混合搜索算法，稱為SPEA2+SDE+AIR，如圖 1 所示。SPEA2+SDE+AIR 算法的基本流程如下：首先根據(jù)二維整數(shù)向量編碼在約束空間內(nèi)隨機生成初始的進化種群和外部種群；然后基于AIR 策略對組合種群進行修正，確保每個個體都是可行個體；根據(jù)式（7）計算每個可行個體的目標函數(shù)值，并進行適應度分配；對組合種群進行環(huán)境選擇生成新的外部種群；對新外部種群進行交配選擇和多項式變異生成新的進化種群；如果滿足終止條件，輸出外部種群中的所有非支配個體，否則對新進化種群進行個體修正使其成為可行種群，并繼續(xù)算法的進化。

從圖1 可以看出，與基本的SPEA2+SDE 算法相比，本文提出的SPEA2+SDE+AIR 算法能夠基于構造的二維整數(shù)向量編碼，充分考慮數(shù)學模型中的相關約束關系以及實際應急救援環(huán)境的復雜情況，利用AIR 策略將種群始終限制在可行域中進化，從而能夠為算法的適應度分配、環(huán)境選擇、交配選擇等提供更加準確可靠的啟發(fā)式信息，增強算法的收斂性能。

圖1 SPEA2+SDE+AIR算法的流程Fig. 1 Flowchart of SPEA2+SDE+AIR algorithm

3 實驗結果與分析

為了驗證本文SPEA2+SDE+AIR 算法在處理相關問題時的有效性，本章首先介紹算法的基本參數(shù)設置以及性能評價指標，然后考慮與兩種最新的針對于應急救援物資分配問題的算法：帶有編碼修正機制的非支配排序差異演化（Encoding Repair and Non-dominated Sorting based Differential Evolution，ERNS-DE）算法［13］，以及基于貪心搜索的多目標遺傳算法（Greedy-Search-based Multi-Objective Genetic Algorithm，GSMOGA）［11］分別進行模型及算法對比。ERNS-DE 采用面向發(fā)放點的編碼修正機制使種群中的每一個個體都是可行的；GSMOGA 則包含一種貪婪搜索方法，其中最接近發(fā)放點的儲備點在物資分配時優(yōu)先考慮，從而避免了不可行個體的產(chǎn)生。

3.1 參數(shù)設置與評價指標

為了模擬應急環(huán)境以充分評估算法性能，本文考慮20 個物資儲備點、10 個物資發(fā)放點以及50 種救援物資，對應10 000 個決策變量，并分別在兩種應急環(huán)境中進行測試。在應急環(huán)境1（標記為EN1），隨機設置5 種物資是充分的，即可以滿足所有需求點的要求，剩余45 種救災物資均是短缺的，不能滿足所有需求點的應急要求；在應急環(huán)境2（標記為EN2），隨機設置10 種物資可以滿足需求，剩下的40 種救災物資極其緊缺。依據(jù)上面的設定，每個測試實例均根據(jù)輸入的問題規(guī)模和約束條件隨機生成，且根據(jù)不同的隨機種子，在Intel Core i7 3.60 GHz CPU、內(nèi)存8.0 GB、操作系統(tǒng)Windows 10 的個人計算機上獨立運行30 次。為了對比的公平性，ERNS-DE 和GSMOGA 采用各自的推薦參數(shù)設置。對于本文的SPEA2+SDE+AIR，本文采用實驗法，即結合已有工作與通過大量測試獲得結果相對較好的一組參數(shù)組合，這也是目前最常用的確定參數(shù)的方法，其中較小的變異概率和較大的交叉概率有利于維護種群進化過程中的多樣性和收斂性。三種算法的具體參數(shù)如表1所示。

表1 三種算法的基本參數(shù)Tab. 1 Basic parameters of three algorithms

為了比較測試算法的整體性能，本文使用流行的超體積（HyperVolume，HV）［23］指標來進行衡量。超體積定義為被所求解集支配、但不被參考點支配的空間體積大小。超體積值可以提供有關于整個解決方案的收斂性和多樣性的一般信息，通常，較大的超體積值意味著解決方案的質(zhì)量更高。需要注意的是，參考點的選擇對于超體積的計算至關重要。由于在所提的高維多目標應急救援物資分配問題中不知道Pareto前沿的范圍，因此，對于每一組測試實例，需要將所有獲得的解集放在一起，去除其中的重復解以及支配解，然后，選擇的參考點略大于合并解集每個目標的最大值。這種方法已經(jīng)被證明是有效的，因為它能夠很好地平衡解集的收斂性與多樣性［24］。

在所提的高維多目標應急救援物資分配問題中，決策者通常更關心所采用的算法獲得的結果是否優(yōu)于其他對比算法。因此，本文采用經(jīng)典的覆蓋值（Coverage Value，CV）［25］來評估所得結果的收斂性。覆蓋值提供了一種直接的方法來比較通過所采用的算法獲得的解集中有多少個解支配了由對比算法所獲得的結果中的解。假設E 和F 分別是兩種不同的算法所獲得的解集，假如E 中的一個解的所有目標值與F 中的另一個解的所有目標值相比，都不比它們差，則認為前者覆蓋了后者。Cv（E，F(xiàn)）表示 F 被E 中解集所覆蓋的百分比，若Cv(E，F(xiàn)) ＞ Cv(F，E)，則意味著E 中的解相比 F 更優(yōu)。在本文的實驗中，對于每個測試實例，將在30 次獨立運行中所獲得的所有解放在一起，去除其中的重復解后再進行覆蓋值計算。

3.2 模型對比

首先，對于ERNS-DE 和GSMOGA，本文在進行實驗時，僅考慮其原有的目標函數(shù)（ERNS-DE 考慮f1和f6，GSMOGA 考慮f1、f3以及f6），剩余的目標函數(shù)由分配方案計算得出；而SPEA2+SDE+AIR 考慮所有的目標。由于三種算法所要優(yōu)化的目標數(shù)不同，所以此處本文不采用超體積和覆蓋值，而是選取了各個目標值的范圍，如表2 所示，其中較優(yōu)的目標值加粗表示。

由表2可以看出，就所選取的三個目標f1、f3以及f6而言，SPEA2+SDE+AIR 在7 個實例上獲得的結果優(yōu)于ERNS-DE 和GSMOGA所獲得的結果，而ERNS-DE和GSMOGA在所有實例中都沒有發(fā)現(xiàn)比SPEA2+SDE+AIR 更好的解。此外，SPEA2+SDE+AIR 在所有實例中占優(yōu)的目標個數(shù)都遠要高于ERNSDE 和GSMOGA。以上結果表明，盡管SPEA2+SDE+AIR 在處理6 個目標時具有更大的優(yōu)化負擔，但它仍舊可以在考慮的目標之間尋找到比ERNS-DE和GSMOGA更好的平衡。

表2 兩種環(huán)境下部分測試實例的目標值范圍Tab. 2 Objective value ranges of some test instances in two environments

3.3 算法對比

為了更加全面地比較SPEA2+SDE+AIR、ERNS-DE 和GSMOGA 三種算法之間的性能，在本節(jié)讓三種算法都考慮6個目標，在兩種環(huán)境下分別測試30個實例。

表3 顯示了三種算法測試結果的超體積值，在EN1 中，與ERNS-DE 以及 GSMOGA 相比，SPEA2+SDE+AIR 的超體積分別增大了約55 000 000%和14 000 000%，而在EN2 中，則分別增大了30 000 000% 和29 000 000%，尤其需要注意的是ERNS-DE 和GSMOGA 都出現(xiàn)了超體積值為0 的情形，尤其是GSMOGA 絕大部分的超體積為0。以上結果表明，SPEA2+SDE+AIR 的整體性能要比ERNS-DE 和GSMOGA 更好，所得解集具有更好的收斂性和多樣性。

表4 給出了在高維多目標應急救援物資分配問題上三種算法的覆蓋值結果，其中較優(yōu)的覆蓋值加粗表示。K、L、M 分別表示由SPEA2+SDE+AIR、ERNS-DE 以及GSMOGA 各自獲得的最終解集。在EN1和EN2中，SPEA2+SDE+AIR 與ERNSDE 相比，平均覆蓋值分別提高了34.87%和23.59%，而與GSMOGA相比，在所有測試實例中覆蓋值都提高了100%。以上結果表明，SPEA2+SDE+AIR 可以獲得比ERNS-DE 和GSMOGA更高質(zhì)量的解。

總體而言，SPEA2+SDE+AIR 在所有60 個測試實例中均表現(xiàn)優(yōu)異，而且可以在各種情況下獲得多樣化的解決方案。

表3 三種算法在兩種環(huán)境下的超體積（均值和標準差）結果Tab. 3 Hypervolume（mean and standard deviation）results of three algorithms in two environments

表4 三種算法在兩種環(huán)境下的覆蓋值結果 單位：%Tab. 4 Coverage values of three algorithms in two environments unit：%

續(xù)表

4 結語

本文針對災害應急響應中的應急資源分配這一熱點問題展開研究，首先構建了一個多儲備點、多發(fā)放點、多種救援物資的并發(fā)分配模型，然后通過引入相關心理學知識來量化受災群眾的恐慌心理和公平心理，在此基礎上提出了包括應急響應總時間、受災群眾的恐慌心理、發(fā)放點物資不滿足度、物資分配的公平性、受災群眾損失、應急響應總成本在內(nèi)的優(yōu)化目標，并提出了一種基于移位密度估計和自適應編碼修正的多目標優(yōu)化算法SPEA2+SDE+AIR。對比實驗說明，本文所提出的多目標優(yōu)化算法在種群進化過程中能夠很好地維持種群的多樣性和收斂性，從而提高算法的整體性能。在未來的工作中，多階段的動態(tài)優(yōu)化，以及救援物資分配與調(diào)度的集成優(yōu)化問題將是研究和改進的重要方向。