改進(jìn)的蝗蟲優(yōu)化算法在雙目標(biāo)應(yīng)急物資中心選址問(wèn)題中的應(yīng)用

彭大江, 葉春明, 趙靈瑋

(上海理工大學(xué) 管理學(xué)院,上海 200093)

0 引言

近年來(lái)，國(guó)內(nèi)外頻發(fā)地震、海嘯和瘟疫等緊急事件，它們不僅影響面積廣，而且無(wú)法做到全面預(yù)防，還會(huì)造成巨大的人員傷亡和經(jīng)濟(jì)損失[1,2]。當(dāng)此類緊急事件發(fā)生時(shí)，如何能在短時(shí)間內(nèi)迅速響應(yīng)，做到有條不紊地展開救援和收集發(fā)放物資是應(yīng)急管理領(lǐng)域中的研究重點(diǎn)[3,4]。以2020年初爆發(fā)的新型冠狀病毒為例，武漢市在這場(chǎng)戰(zhàn)役中做出巨大犧牲：臨時(shí)封城，關(guān)閉通往其他地區(qū)的通道，堅(jiān)決防止疫情向其他地區(qū)擴(kuò)散。在這種情況下，疫區(qū)人民的生活及醫(yī)療物資極度匱乏，急需臨時(shí)建立應(yīng)急物資倉(cāng)庫(kù)，收集國(guó)家政府為疫區(qū)輸送的物資和社會(huì)愛(ài)心人士自發(fā)捐贈(zèng)的物資，然后高效合理地分發(fā)給群眾[5]。合理的應(yīng)急設(shè)施布局不僅會(huì)穩(wěn)定民心，使得防控過(guò)程更加順利，并且在后續(xù)的物資運(yùn)輸分配過(guò)程中按需分配，更加公平。

目前國(guó)內(nèi)外研究的應(yīng)急選址問(wèn)題主要基于三類經(jīng)典模型：(1)選擇設(shè)施并適當(dāng)分配給需求點(diǎn)使得需求點(diǎn)與設(shè)施之間最大服務(wù)距離最短的p-中心問(wèn)題；Lu在此基礎(chǔ)上考慮點(diǎn)權(quán)重和不確定救援需求與配送時(shí)間，利用改進(jìn)的模擬退火算法求解[6]；Ye等在此基礎(chǔ)上考慮人口分布，經(jīng)濟(jì)條件等因素利用變鄰域搜索算法來(lái)求解應(yīng)急倉(cāng)庫(kù)的選址問(wèn)題[7]。(2)在覆蓋所有需求點(diǎn)的前提下，使選擇設(shè)施的數(shù)量最小化的集合覆蓋問(wèn)題，或是在給定設(shè)施數(shù)量的前提下，使選擇設(shè)施能覆蓋盡可能多的應(yīng)急點(diǎn)的最大覆蓋問(wèn)題；陳志宗等以此為基礎(chǔ)提出了一種災(zāi)害應(yīng)急反應(yīng)的樞紐集覆蓋模型，并運(yùn)用改進(jìn)的遺傳算法求解[8]。(3)選擇設(shè)施使需求點(diǎn)到對(duì)應(yīng)設(shè)施的加權(quán)平均距離最小化的p-中值問(wèn)題；Zhao等在此基礎(chǔ)上考慮地震時(shí)的撤退時(shí)間與總庇護(hù)區(qū)域進(jìn)行建模，并用改進(jìn)的粒子群算法求解[9]；陳剛等在傳統(tǒng)p-中值問(wèn)題上運(yùn)用多項(xiàng)logit模型刻畫居民的有限理性選擇行為，分別使用遺傳算法和模擬退火算法求解此情況下的應(yīng)急避難所選址問(wèn)題[10]。

這幾類選址問(wèn)題均為離散選址問(wèn)題，考慮應(yīng)急點(diǎn)的需求，在待選設(shè)施中進(jìn)行選擇?，F(xiàn)已證明，三類選址問(wèn)題均為NP-Hard，除非P=NP，否則該類問(wèn)題不存在多項(xiàng)式時(shí)間精確算法。目前解決該問(wèn)題的算法主要集中在兩類：以割平面法和分支定界法為代表的精確算法[11,12]〗。此類算法的優(yōu)勢(shì)在于保證獲得全局最優(yōu)解，但由于其時(shí)間復(fù)雜度為指數(shù)級(jí)，無(wú)法應(yīng)用到大規(guī)模問(wèn)題中。另一類為群智能優(yōu)化的啟發(fā)式算法[7～9]。此類算法雖然無(wú)法保證獲得理論全局最優(yōu)，但可在合理計(jì)算時(shí)間內(nèi)獲得高效的滿意解，因此更適合用于實(shí)際應(yīng)用中較大規(guī)模的問(wèn)題。此外越來(lái)越多的學(xué)者考慮更貼合實(shí)際情況的多目標(biāo)應(yīng)急選址問(wèn)題[13～15]，而這類問(wèn)題的求解方式通常與智能優(yōu)化算法更加契合，因此許多研究采用此類算法求解以獲得更佳的解決方案。

本文在已有文獻(xiàn)的研究基礎(chǔ)上，在考慮后續(xù)運(yùn)輸成本和有概率發(fā)生緊急事件而導(dǎo)致無(wú)法正常運(yùn)送物資的情況，為應(yīng)急物資中心選址問(wèn)題建模；然后針對(duì)該問(wèn)題，引入并改進(jìn)蝗蟲優(yōu)化算法[16]，使其更適合于求解該應(yīng)急物資中心選址問(wèn)題；最后通過(guò)數(shù)值計(jì)算的對(duì)比實(shí)驗(yàn)，驗(yàn)證該算法的可行性和有效性。

1 問(wèn)題與模型

1.1 問(wèn)題描述

當(dāng)區(qū)域內(nèi)發(fā)生緊急事件后，物資和人手極度匱乏，若建立過(guò)多的應(yīng)急物資服務(wù)點(diǎn)不僅會(huì)導(dǎo)致資源浪費(fèi)，更重要的是很可能導(dǎo)致外部物資運(yùn)送到該區(qū)域時(shí)分配效率低，轉(zhuǎn)運(yùn)速度慢，難以高效保障生活醫(yī)療水平。在這種情形下，需要在區(qū)域內(nèi)選擇數(shù)個(gè)設(shè)施作為應(yīng)急物資中心，來(lái)提高外界物資分配至該區(qū)域內(nèi)各需求點(diǎn)的效率和僅存資源的利用率。因此問(wèn)題描述為區(qū)域內(nèi)存在m個(gè)應(yīng)急需求點(diǎn)，要求在n個(gè)給定的設(shè)施中，確定p個(gè)設(shè)施作為應(yīng)急物資中心點(diǎn)，使得一些指標(biāo)最大化或最小化。

對(duì)于應(yīng)急物資中心選址問(wèn)題，若完全考慮所有細(xì)節(jié)會(huì)使模型過(guò)于復(fù)雜，為突出研究的重點(diǎn)同時(shí)保證模型的擴(kuò)展性，我們做出如下假設(shè)：(1)應(yīng)急物資中心的儲(chǔ)備量由其服務(wù)的需求點(diǎn)確定，即應(yīng)急物資中心不會(huì)出現(xiàn)物資供給不足的情況；(2)每個(gè)應(yīng)急需求點(diǎn)接受且僅接受某一個(gè)應(yīng)急物資中心點(diǎn)的服務(wù)；(3)每個(gè)應(yīng)急需求點(diǎn)有出現(xiàn)緊急情況的概率。當(dāng)某個(gè)應(yīng)急點(diǎn)出現(xiàn)緊急情況時(shí)，其必須處于對(duì)應(yīng)應(yīng)急物資中心的最大正常服務(wù)半徑內(nèi)方可正常接受服務(wù)。

在如上假設(shè)的前提下，我們以最大覆蓋選址模型為基礎(chǔ)，建立雙目標(biāo)覆蓋模型來(lái)抽象應(yīng)急物資中心的選址問(wèn)題，以達(dá)到如下目標(biāo)：(1)最小化應(yīng)急需求點(diǎn)到相應(yīng)應(yīng)急物資中心的運(yùn)輸成本；(2)最小化出現(xiàn)緊急情況時(shí)無(wú)法正常完成運(yùn)輸?shù)奈镔Y量?；谝陨戏治?，我們定義以下數(shù)學(xué)符號(hào)并建立該數(shù)學(xué)模型。

1.2 數(shù)學(xué)模型建立

雙目標(biāo)覆蓋模型可用一個(gè)二分圖G=(E,F)來(lái)描述，模型中涉及的數(shù)學(xué)符號(hào)及意義如下:

E={ei|i=1,2,…,m}：應(yīng)急需求點(diǎn)集合，共m個(gè)應(yīng)急需求點(diǎn)；

F={fj|j=1,2,…,n}：候選應(yīng)急物資設(shè)施點(diǎn)集合，共n個(gè)候選設(shè)施點(diǎn)；

ωi：需求點(diǎn)ei的物資需求量(ωi>0)；

p：開設(shè)的設(shè)施點(diǎn)數(shù)量(p

d：規(guī)定設(shè)施點(diǎn)可以正常服務(wù)的最大距離；

dij：需求點(diǎn)ei到設(shè)施點(diǎn)fj的歐氏距離；

A=[aij]m×n：若dij

xj∈{0,1}：若設(shè)施點(diǎn)fj開設(shè)，xj=1，否則xj=0；

yij∈{0,1}：若需求點(diǎn)ei接受設(shè)施點(diǎn)fj的服務(wù)，yi=1，否則yi=0；

δ：運(yùn)輸成本系數(shù)(δ>0)，即運(yùn)輸每單位距離的每單位物資將消耗δ單位的運(yùn)輸成本；

μ：發(fā)生緊急情況的概率(μ>0)。對(duì)于滿足yij=1的設(shè)施點(diǎn)fj和需求點(diǎn)ei，若dij>d則發(fā)生緊急情況時(shí)，設(shè)施點(diǎn)fj無(wú)法正常服務(wù)需求點(diǎn)ei。

根據(jù)上一節(jié)目標(biāo)函數(shù)與約束條件的分析，建立的雙目標(biāo)覆蓋模型的數(shù)學(xué)表達(dá)式如下：

(1)

(2)

(6)

目標(biāo)函數(shù)(1)表示需要最小化所有被覆蓋需求點(diǎn)到對(duì)應(yīng)設(shè)施之間的運(yùn)輸成本總和；目標(biāo)函數(shù)(2)表示需要最小化無(wú)法正常配送的物資量的期望值；約束(3)表示選擇的設(shè)施點(diǎn)數(shù)應(yīng)正好為p個(gè)；約束(4)表示需求點(diǎn)ei可接受fj服務(wù)的必要條件是設(shè)施點(diǎn)fj開設(shè)；約束(5)表示每個(gè)需求點(diǎn)接受且僅接受1個(gè)設(shè)施點(diǎn)的服務(wù)；約束(6)表示xj和yi均為0-1變量。

2 改進(jìn)的蝗蟲優(yōu)化算法

2.1 基本蝗蟲優(yōu)化算法

蝗蟲優(yōu)化算法(Grasshopper Optimization Algorithm, GOA)是Saremi等人[16]于2017年提出的一種新型群智能優(yōu)化啟發(fā)式算法，其源于對(duì)大自然中蝗蟲群的覓食行為模擬?；认x優(yōu)化算法有收斂速度快，原理簡(jiǎn)單易實(shí)現(xiàn)的優(yōu)點(diǎn)，但其全局搜索能力一般，不易搜索到最優(yōu)解。針對(duì)這些問(wèn)題，有學(xué)者對(duì)算法尋優(yōu)能力其進(jìn)行改進(jìn)[17,18]。同時(shí)GOA在優(yōu)化中的應(yīng)用也比較廣泛，目前有函數(shù)優(yōu)化[19,20]，作業(yè)車間調(diào)度[21]，特征提取[22]，背包問(wèn)題[23]等。

由于篇幅原因，此處不再贅述基本蝗蟲優(yōu)化算法的流程，具體請(qǐng)參見文獻(xiàn)[16]，個(gè)體位置更新公式如下所示：

(7)

(8)

2.2 二進(jìn)制蝗蟲優(yōu)化算法

為將蝗蟲優(yōu)化算法應(yīng)用到本文的應(yīng)急物資中心選址問(wèn)題，需要修改以下三個(gè)方面才能使其正常運(yùn)行：(1)初始化的操作；(2)修復(fù)不滿足約束條件的解；(3)修改更新公式。

2.2.1 初始化操作

算法中解的維度與待選設(shè)施點(diǎn)數(shù)n相同，一個(gè)滿足約束條件的解中有且僅有p個(gè)設(shè)施點(diǎn)開啟，為保證初始化效率和解的多樣性，我們采用隨機(jī)初始化的方式。構(gòu)造解x的主要操作步驟如下：

1)記當(dāng)前已開設(shè)設(shè)施點(diǎn)數(shù)為k=0，當(dāng)前處理的設(shè)施標(biāo)號(hào)i=1；

3)若k

2.2.2 修復(fù)解的操作

對(duì)于不滿足約束的解x，記其中已開設(shè)設(shè)施數(shù)為k，分以下三種情況處理：

1)若k=p，無(wú)需修復(fù)，結(jié)束操作；

2)若k

3)若k>p，在已開設(shè)設(shè)施中隨機(jī)選擇k-p個(gè)關(guān)閉，標(biāo)記對(duì)應(yīng)的xi=0。

2.2.3 修改更新公式

為在二進(jìn)制蝗蟲優(yōu)化算法中延續(xù)原算法中按全局最優(yōu)解更新位置的思想，我們改進(jìn)更新公式，替換為如下操作:

(9)

(10)

(11)

3 新型多目標(biāo)蝗蟲優(yōu)化算法

為將算法應(yīng)用于本文問(wèn)題，我們需要設(shè)計(jì)二進(jìn)制多目標(biāo)蝗蟲優(yōu)化算法(Binary Multi-objective Grasshopper Optimization, BMOGOA)，考慮首先引入Fuzzy集關(guān)聯(lián)熵系數(shù)[24]來(lái)建立目標(biāo)函數(shù)值評(píng)價(jià)體系，然后加入外部檔案來(lái)存儲(chǔ)非劣解，再提出根據(jù)關(guān)聯(lián)熵系數(shù)來(lái)動(dòng)態(tài)確定每輪迭代中最優(yōu)解的方法，使算法可以正常迭代，最后添加競(jìng)爭(zhēng)決策機(jī)制對(duì)算法尋優(yōu)能力進(jìn)行改進(jìn)。

3.1 Fuzzy集的關(guān)聯(lián)熵系數(shù)

關(guān)聯(lián)熵系數(shù)是評(píng)價(jià)兩個(gè)Fuzzy集之間相似性的重要工具，其計(jì)算的主要步驟如下:

1)對(duì)兩個(gè)Fuzzy集A和B，它們各自的熵計(jì)算方式如式(12)和(13)所示:

+(1-A(xi))ln(1-A(xi))

(12)

+(1-B(xi))ln(1-B(xi))

(13)

其中，n是Fuzzy集中元素的個(gè)數(shù)，A(xi)和B(xi)分別表示Fuzzy集A和B中的第i個(gè)元素對(duì)相應(yīng)Fuzzy集的隸屬度，本文中可簡(jiǎn)單理解其為成員值，滿足O

2)A關(guān)于B的偏熵記為EB(A)，對(duì)應(yīng)的，B關(guān)于A的偏熵記為EA(B)，計(jì)算方式如下:

+(1-B(xi))ln(1-A(xi))

(14)

+(1-A(xi))ln(1-B(xi))

(15)

3)A與B之間的關(guān)聯(lián)熵定義如式(16)所示，為它們的偏熵之和:

E(A;B)=EB(A)+EA(B)

(16)

4)A與B之間的關(guān)聯(lián)熵系數(shù)定義為式(17)所示:

(17)

3.2 解的關(guān)聯(lián)熵系數(shù)

記兩個(gè)單目標(biāo)函數(shù)最小值構(gòu)成的向量為Zmin={z1,min,z2,min}，單目標(biāo)函數(shù)最大值構(gòu)成的向量Zmax={z1,max,z2,max}，算法中種群X的第i個(gè)個(gè)體xi，其實(shí)際函數(shù)值序列為Zi={z1(xi),z2(xi)}，我們采用以下方式構(gòu)造解的關(guān)聯(lián)熵系數(shù):

(18)

個(gè)體xi的第j個(gè)目標(biāo)函數(shù)值映射到Fuzzy集后成員值為fj(xi)，其滿足01。通過(guò)式(18)可映射出理想Fuzzy集Fmin={f1(x1,min),f2(x2,min)}和真實(shí)Fuzzy集Fi={f1(xi),f2(xi)}。此時(shí)，個(gè)體xi的適應(yīng)度即可用γ(Fi;Fmin)來(lái)度量。

3.3 多目標(biāo)更新策略

為盡可能獲取帕累托前沿，我們?yōu)樗惴ㄌ砑油獠繖n案[25]，存儲(chǔ)每一代新產(chǎn)生的非劣解。

3.3.1 外部檔案初始化

記初始種群為X，外部檔案為EA。由帕累托支配的定義可知，與理解函數(shù)值序列Zmin={z1,min,z2,min}對(duì)應(yīng)的解x1,min和x2,min大概率不被當(dāng)前種群中的解支配，因此我們將其添加至外部檔案。外部檔案初始化過(guò)程的偽代碼如算法1所示。

3.3.2 外部檔案更新

算法執(zhí)行過(guò)程中，種群每次完成迭代，都需要對(duì)外部檔案進(jìn)行更新，更新過(guò)程偽代碼如算法2所示。

算法2.外部檔案更新的偽代碼輸入:種群X,外部檔案EA,1.初始化臨時(shí)種群tX=X2.while tX≠{}3.令x*=tX,執(zhí)行tX=tX{x*}4.記is_dominated=False5.for each a in EA6.if x*?a then7.執(zhí)行EA=EA{a}8.continue9.else if x*p x then10.is_dominated=True11.end if12.end for13.if not is_dominated=then14. EA=EA U{x*}15.end if16.end while

3.4 最優(yōu)解選擇策略

二進(jìn)制蝗蟲優(yōu)化算法的更新過(guò)程需要當(dāng)前最優(yōu)解，若在多目標(biāo)的情況下，直接將解的關(guān)聯(lián)熵系數(shù)最大的作為最優(yōu)解，則導(dǎo)致最終的解將大概率聚集于一點(diǎn)，不可能逼近帕累托最優(yōu)解。因此，本文提出基于輪盤賭算法的最優(yōu)解選擇策略，其主要步驟如下：

1)對(duì)外部檔案EA中的每個(gè)非支配解計(jì)算解ai的關(guān)聯(lián)熵系數(shù)fi；

3)產(chǎn)生一個(gè)[0,1]內(nèi)均勻分布的隨機(jī)數(shù)r，若r

上述操作完成后，可按與關(guān)聯(lián)熵系數(shù)成正比的概率從外部檔案EA中獲得一個(gè)非支配解，從而在迭代過(guò)程中動(dòng)態(tài)引導(dǎo)種群向帕累托前沿靠近。

3.5 競(jìng)爭(zhēng)決策機(jī)制

為增強(qiáng)多目標(biāo)蝗蟲優(yōu)化算法在離散空間的搜索能力，我們?yōu)樗惴ㄌ砑痈?jìng)爭(zhēng)決策機(jī)制[26]。該機(jī)制在迭代次數(shù)l>λLmax(0<λ<1)時(shí)被執(zhí)行。競(jìng)爭(zhēng)決策機(jī)制的偽代碼如算法3所示。

3.6 多目標(biāo)蝗蟲優(yōu)化算法執(zhí)行流程

如圖1所示是算法的執(zhí)行過(guò)程圖，算法開始后，首先建立兩個(gè)較小的種群，并分別調(diào)用單目標(biāo)的二進(jìn)制蝗蟲優(yōu)化算法并行計(jì)算，記錄好函數(shù)上下界后才開始正式計(jì)算。

圖1 多目標(biāo)蝗蟲優(yōu)化算法流程圖

4 數(shù)值實(shí)驗(yàn)及結(jié)果分析

為驗(yàn)證多目標(biāo)蝗蟲優(yōu)化算法在應(yīng)急物資中心選址問(wèn)題上應(yīng)用的可行性和有效性，本節(jié)開展數(shù)值實(shí)驗(yàn)，并通過(guò)一些指標(biāo)來(lái)評(píng)估算法的性能。作為對(duì)照，本文選用多目標(biāo)離散選址問(wèn)題中使用頻率最高的NSGA-II算法，該算法是目前公認(rèn)最有效的多目標(biāo)進(jìn)化算法之一，通過(guò)對(duì)比實(shí)驗(yàn)評(píng)測(cè)本文算法性能。

4.1 實(shí)驗(yàn)數(shù)據(jù)

本文的測(cè)試數(shù)據(jù)選擇OR-Lib中最大覆蓋問(wèn)題的3個(gè)SJC數(shù)據(jù)集，其中僅給出應(yīng)急需求點(diǎn)的坐標(biāo)和對(duì)應(yīng)的需求量，急物資中心可選址在任意需求點(diǎn)。由于給定的開設(shè)數(shù)p和最大正常服務(wù)距離d的取值不同將產(chǎn)生完全不同的問(wèn)題，我們最終選擇的數(shù)據(jù)集為SJC324，SJC500和SJC818，其應(yīng)急點(diǎn)數(shù)分別為324，500和818。該數(shù)據(jù)集中沒(méi)有運(yùn)輸成本系數(shù)δ和發(fā)生緊急情況的概率μ的信息，為模擬實(shí)際情況，我們?nèi)ˇ?0.01，μ=0.1。

4.2 評(píng)價(jià)指標(biāo)

由于無(wú)法獲取該問(wèn)題的真實(shí)帕累托前沿，為評(píng)測(cè)算法的解集質(zhì)量，計(jì)算效率和魯棒性，我們主要通過(guò)以下指標(biāo)來(lái)評(píng)價(jià)算法的性能。

(1)非支配解的數(shù)量(Number of Pareto Solution, NPS)是算法獲取的非支配解數(shù)量，一般認(rèn)為非支配解數(shù)量越多，算法性能越好。

(2)空間評(píng)價(jià)指標(biāo)(Spacing Metric, SM)衡量帕累托近似解集中每個(gè)解到其他解的最小距離的標(biāo)準(zhǔn)差，反映解集中解分布的均勻性，其計(jì)算公式如式(19)所示:

(19)

(3)C指標(biāo)(C-Metric)可衡量非支配解集A和B中占優(yōu)支配的情況，計(jì)算方式如式(20)所示，其表示B中個(gè)體被A中個(gè)體支配的占比。

(20)

C(A,B)的取值范圍是[0,1]，特別地，如果C(A,B)=1表示B中所有個(gè)體均被A中某些個(gè)體支配；如果C(A,B)=0表示B中所有個(gè)體都不被A中任何個(gè)體支配。

4.3 參數(shù)設(shè)置

多目標(biāo)蝗蟲優(yōu)化算法的關(guān)鍵參數(shù)設(shè)置：作用力函數(shù)s(r)中l(wèi)=1.5，f=0.5、保留最優(yōu)解概率的邊界值rmin=0.45，rmax=0.95、目標(biāo)函數(shù)值的邊界系數(shù)α=0.8，β=1.2以及調(diào)用競(jìng)爭(zhēng)決策機(jī)制的迭代數(shù)比率λ=0.8；NSGA-II的交叉概率為0.9，變異概率為0.1。兩種算法的種群數(shù)量均為為300，在BMOGOA開始時(shí)分別分配50個(gè)個(gè)體作為2個(gè)單目標(biāo)函數(shù)優(yōu)化過(guò)程的種群，多目標(biāo)優(yōu)化過(guò)程僅使用200個(gè)個(gè)體。由于問(wèn)題規(guī)模相對(duì)較大，兩種算法的最大迭代次數(shù)均設(shè)置為300次。本文的實(shí)驗(yàn)環(huán)境為Intel Core i5 2.3Ghz，16GB內(nèi)存，Windows 7操作系統(tǒng)。為保證公平性，多目標(biāo)蝗蟲優(yōu)化算法和NSGA-II算法均使用C++編寫。

4.4 計(jì)算結(jié)果與分析

我們記BMOGOA為算法A，NSGA-II為算法B，各算法獨(dú)立求解每個(gè)問(wèn)題10次以后，各自合并非支配解集，得到的算法的性能指標(biāo)如表1所示。

表1 算法性能指標(biāo)統(tǒng)計(jì)表

從表1可以看到，BMOGOA在測(cè)試問(wèn)題中指標(biāo)幾乎全面優(yōu)于NSGA-II。對(duì)比圖2和圖3可發(fā)現(xiàn)，保持?jǐn)?shù)據(jù)集和正常服務(wù)距離不變，當(dāng)待選應(yīng)急物資中心數(shù)增加時(shí)，BMOGOA較NSGA-II表現(xiàn)更佳：求得的解有良好的分布，并且計(jì)算時(shí)間較NSGA-II平均降低24%，在大規(guī)模問(wèn)題中的求解過(guò)程中響應(yīng)更加迅速?？v觀所有測(cè)試數(shù)據(jù)，BMOGOA獲得的解都不劣于NSGA-II獲得的解，因此說(shuō)明本文算法的在較大規(guī)模問(wèn)題上的可行性和有效性。

圖2 問(wèn)題8的非支配解集分布

5 結(jié)論

本文對(duì)應(yīng)急物資中心選址問(wèn)題進(jìn)行研究，提出了一種考慮后續(xù)運(yùn)輸成本以及緊急情況下不能正常配送物資的離散選址模型，針對(duì)該模型提出了一種二進(jìn)制多目標(biāo)蝗蟲優(yōu)化算法(BMOGOA)。該算法以模糊關(guān)聯(lián)熵為核心，融合競(jìng)爭(zhēng)決策機(jī)制和最優(yōu)解選擇機(jī)制，引導(dǎo)算法不斷向理想解迭代更新，同時(shí)存儲(chǔ)當(dāng)前非劣解到外部檔案。通過(guò)多次數(shù)值實(shí)驗(yàn)，BMOGOA表現(xiàn)出較強(qiáng)的可行性和有效性，并在測(cè)試問(wèn)題上幾乎全面優(yōu)于目前多目標(biāo)離散選址問(wèn)題中使用頻率最高的NSGA-II，展現(xiàn)出更高的求解效率，同時(shí)能求得更優(yōu)質(zhì)的解，因此其可作為求解多目標(biāo)離散選址問(wèn)題的一種有效算法。在實(shí)際生活中不乏中大規(guī)模的離散應(yīng)急選址問(wèn)題，通過(guò)對(duì)本文模型的擴(kuò)展和算法的優(yōu)化，能在可接受時(shí)間范圍內(nèi)提供數(shù)個(gè)較優(yōu)質(zhì)的解以供決策人選擇，在此基礎(chǔ)上結(jié)合定性分析，可在應(yīng)急物中心資選址問(wèn)題中做出更科學(xué)的決策，最大化僅有資源的利用率。