雙目標(biāo)消防救援站選址模型的元胞陰陽(yáng)平衡優(yōu)化算法

許秋艷, 馬 良, 劉 勇

(1.上海理工大學(xué) 管理學(xué)院,上海 200093; 2.鹽城工學(xué)院 信息工程學(xué)院,江蘇 鹽城 224051)

0 引言

消防救援站布局規(guī)劃是典型組合優(yōu)化問(wèn)題，屬于運(yùn)籌學(xué)中NP難問(wèn)題[1]。嚴(yán)珍珍等將消防救援站選址問(wèn)題表示為以成本最小為目標(biāo)的集合覆蓋問(wèn)題，并采用帶精英策略的蟻群算法進(jìn)行求解[2]。盧厚清等以覆蓋面積最大，利用連續(xù)網(wǎng)空間覆蓋模型處理消防救援站選址問(wèn)題，并設(shè)計(jì)改進(jìn)模擬退火算法進(jìn)行求解[3]。Wang等采用集合覆蓋模型構(gòu)建消防救援站選址模型，并采用ARON工具箱求解模型[4]。Chen等利用最大覆蓋模型構(gòu)建消防救援站選址模型，并采用地理信息系統(tǒng)軟件進(jìn)行站點(diǎn)布局的求解[5]?？紤]到問(wèn)題復(fù)雜性，越來(lái)越多研究人員將多目標(biāo)優(yōu)化引入到消防救援站選址布局中。Yang構(gòu)建成本最小和最遠(yuǎn)距離最短的雙目標(biāo)消防救援站選址模型，采用基于遺傳算法的求解方法[6]。Yao等將P-中值選址模型和最大覆蓋模型相結(jié)合，構(gòu)建多目標(biāo)消防救援站選址模型，并設(shè)計(jì)啟發(fā)式算法求解非劣解[7]。王寧等考慮消防救援站的平衡性與效益，建立消防站布局的多目標(biāo)覆蓋模型，并采用Pareto強(qiáng)度進(jìn)化算法求解模型[1]。

上述多目標(biāo)優(yōu)化研究為消防救援站布局規(guī)劃提供了更好解決方案，但是對(duì)時(shí)間這一重要指標(biāo)研究的較少。我國(guó)提出了15分鐘消防標(biāo)準(zhǔn)，如何將時(shí)間因素引入到多目標(biāo)消防救援站建模中是必須要解決的問(wèn)題。在選址時(shí)還要考慮需求點(diǎn)人口數(shù)量和潛在火災(zāi)風(fēng)險(xiǎn)等級(jí)。此外，根據(jù)最新發(fā)布的《城市消防站建設(shè)標(biāo)準(zhǔn)》，明確要求控制成本。因此，本文將構(gòu)建考慮時(shí)效性和經(jīng)濟(jì)性的雙目標(biāo)消防救援站布局規(guī)劃模型，并將上述其它因素納入到建模中。

采用多目標(biāo)優(yōu)化模型處理消防救援站選址問(wèn)題更加合理，但是加大了模型求解難度。許多研究是將多目標(biāo)消防救援站選址問(wèn)題轉(zhuǎn)化為單目標(biāo)問(wèn)題進(jìn)行求解，無(wú)法得到真正非劣解[8]。智能優(yōu)化算法是求解該類(lèi)問(wèn)題常用方法。典型算法有多目標(biāo)遺傳算法、多目標(biāo)微粒群優(yōu)化算法、多目標(biāo)蟻群優(yōu)化算法等[8]。但是這些算法求解非劣解的效率需要提升，另外這些算法也無(wú)法直接用于多目標(biāo)消防救援站選址模型的求解。該選址問(wèn)題屬于多目標(biāo)組合優(yōu)化問(wèn)題，而多目標(biāo)組合優(yōu)化問(wèn)題比多目標(biāo)連續(xù)優(yōu)化問(wèn)題的求解更加困難，缺少實(shí)用算法。

為有效求解該問(wèn)題，本文在陰陽(yáng)平衡優(yōu)化算法[9](Yin-Yang pair optimization, YYPO)和元胞自動(dòng)機(jī)基礎(chǔ)上，設(shè)計(jì)元胞陰陽(yáng)平衡優(yōu)化算法(cellular Yin-Yang pair optimization，CYYPO)進(jìn)行求解。YYPO算法是Punnathanam等在2016年提出的一種新型智能優(yōu)化算法，其優(yōu)化原理來(lái)自中華傳統(tǒng)文化中的陰陽(yáng)學(xué)說(shuō)。算法期望在哲學(xué)原理上實(shí)現(xiàn)陰陽(yáng)平衡，進(jìn)而實(shí)現(xiàn)算法全局探索和局部開(kāi)發(fā)的均衡。但是基本陰陽(yáng)平衡優(yōu)化方法全局搜索性能強(qiáng)，而局部搜索性能弱[9]。為有效求解該問(wèn)題，本文將元胞自動(dòng)機(jī)引入到基本陰陽(yáng)平衡優(yōu)化算法中，提高算法局部?jī)?yōu)化能力。元胞自動(dòng)機(jī)由馮諾依曼提出，是在時(shí)間與空間都離散的一種動(dòng)力學(xué)模型。根據(jù)其原理，重復(fù)簡(jiǎn)單計(jì)算規(guī)則就能刻畫(huà)復(fù)雜系統(tǒng)行為，多次進(jìn)行鄰域的交互作用就能提高算法局部搜索能力[10]。個(gè)體在陰陽(yáng)平衡優(yōu)化算法搜索空間進(jìn)行全局尋優(yōu)，以搜索到盡可能多的包含非劣解的區(qū)域；同時(shí)也在元胞空間利用演化規(guī)則對(duì)這些區(qū)域進(jìn)行局部?jī)?yōu)化，以搜索到Pareto最優(yōu)解。此外，利用算法交流機(jī)制實(shí)現(xiàn)優(yōu)化信息在算法的搜索空間和元胞空間內(nèi)的共享，每個(gè)個(gè)體動(dòng)態(tài)調(diào)整搜索行為，引導(dǎo)整個(gè)群體不斷向Pareto最優(yōu)前端逼近。實(shí)驗(yàn)驗(yàn)證了所構(gòu)建選址模型和求解算法的可行性與有效性。

1 考慮時(shí)效性和經(jīng)濟(jì)性的雙目標(biāo)消防救援站選址模型

1.1 問(wèn)題描述

根據(jù)我國(guó)15分鐘的消防標(biāo)準(zhǔn)，在設(shè)施點(diǎn)布局規(guī)劃時(shí)要考慮時(shí)效性?；馂?zāi)危險(xiǎn)等級(jí)可分為四個(gè)等級(jí)，分別是輕微，中等，嚴(yán)重和極高。結(jié)合火災(zāi)風(fēng)險(xiǎn)等級(jí)，引入救援響應(yīng)時(shí)間的概念[11]。輕微，中等，嚴(yán)重和極高四種火災(zāi)風(fēng)險(xiǎn)等級(jí)的響應(yīng)時(shí)間分別為12～15分鐘；8～12分鐘；5～8分鐘和4～5分鐘。結(jié)合上述分析，給出時(shí)效性評(píng)價(jià)函數(shù)定義：

(1)

借鑒覆蓋水平函數(shù)概念[11]，函數(shù)f(tij)可以是線性或者非線性函數(shù)。本文采用Sigmoid函數(shù)，表達(dá)式如下:

(2)

1.2 模型構(gòu)建

構(gòu)建的消防救援站選址模型為:

max∑i∈I∑j∈Jwig(tij)xij

(3)

min∑j∈Jcjyj

(4)

s.t. ∑j∈Jyj=p

(5)

xij≤yj,?i∈I,j∈J

(6)

(7)

(8)

yj∈{0,1},?j∈J

(9)

xij∈{0,1},?i∈I,j∈J

(10)

其中，式(3)表示考慮時(shí)效性的綜合覆蓋水平最大；式(4)表示消防救援站總建設(shè)成本最小；式(5)表示消防救援站建設(shè)數(shù)量；式(6)表示在備選點(diǎn)j建立消防救援站時(shí)，才能為需求點(diǎn)i提供服務(wù)；式(7)和(8)要求每個(gè)需求點(diǎn)i被分配給一個(gè)消防救援站提供服務(wù)，當(dāng)需求點(diǎn)i時(shí)效性函數(shù)g(tij)為0時(shí)，將其分配到一個(gè)行車(chē)時(shí)間最短的消防救援站；式(9)和(10)表示決策變量取值范圍。

針對(duì)該模型NP難問(wèn)題特征，本文在陰陽(yáng)平衡優(yōu)化算法基礎(chǔ)上，設(shè)計(jì)元胞陰陽(yáng)平衡優(yōu)化算法來(lái)求解該問(wèn)題。

2 陰陽(yáng)平衡優(yōu)化算法

陰陽(yáng)平衡優(yōu)化算法YYPO在具體實(shí)現(xiàn)時(shí)，包含利用超球體和歸檔集的兩個(gè)解更新階段[9]。受太極圖的啟示，算法在1為半徑的超球體內(nèi)，分別以P1與P2兩個(gè)點(diǎn)作中心，δ1與δ2作步長(zhǎng)進(jìn)行解的更新。由于這兩個(gè)點(diǎn)采用同樣的解更新策略，為簡(jiǎn)單起見(jiàn)，令P代表P1或者P2，δ代表δ1或者δ2。在生成新解前，首先生成2D(D代表變量維數(shù))個(gè)同樣的點(diǎn)P。解的更新方法共分為1維更新和D維更新兩種，

方法如式(11)和(12)所示:

(11)

(12)

算法基于等概率原則選擇上述兩種方法中的一種進(jìn)行解的更新。此外，從P1產(chǎn)生的2D個(gè)點(diǎn)中，選擇適應(yīng)度值最優(yōu)點(diǎn)替換P1。算法對(duì)P2也進(jìn)行相同操作。

算法采用精英保留策略，在每次超球體內(nèi)的解更新之前，會(huì)將P1和P2儲(chǔ)存到名為archive的歸檔集內(nèi)。每間隔I次迭代，算法就進(jìn)入基于歸檔集的解更新階段，將采用archive中的2I個(gè)點(diǎn)對(duì)當(dāng)前的P1與P2進(jìn)行更新。首先，在archive中選擇最優(yōu)點(diǎn)，如果該點(diǎn)優(yōu)于點(diǎn)P1則將這兩點(diǎn)互換。然后，對(duì)點(diǎn)P2也采用同樣更新策略。此外，在該階段算法還要在Imin和Imax之間重新生成參數(shù)I，并且對(duì)搜索半徑δ1與δ2進(jìn)行更新，具體計(jì)算方法如下：

δ1=δ1-(δ1/α)

(13)

δ2=δ2+(δ2/α)

(14)

其中，α表示縮小/擴(kuò)大因子。

算法反復(fù)進(jìn)行上述兩種解更新方法，直到滿足停止條件。

3 元胞陰陽(yáng)平衡優(yōu)化算法

3.1 元胞自動(dòng)機(jī)

元胞自動(dòng)機(jī)是描述系統(tǒng)存在和演化的離散動(dòng)態(tài)系統(tǒng)。元胞、元胞空間、鄰居和演化規(guī)則是其四個(gè)基本組成部分。以下給出元胞自動(dòng)機(jī)在算法中的具體實(shí)現(xiàn)形式。

定義1元胞及元胞空間

令集合C=(c1,c2,…,cj,…,cN)，N表示備選消防救援站數(shù)量；cj∈{0,1}，若cj=1，表示在第j個(gè)備選點(diǎn)建消防救援站，若cj=0，表示未在第j個(gè)備選點(diǎn)建消防救援站。集合C中cj所有可能取值的組合構(gòu)成的集合定義為元胞空間，并用L={CellX=(c1,c2,…,cj,…,cN)|cj∈{0,1}}表示。一個(gè)組合CellX是一個(gè)元胞。

定義2穆?tīng)栢従宇?lèi)型NMoore={CellY|diff(CellY-CellX)≤r,CellX,CellY∈L}。其中，diff(CellY-CellX)≤r是兩個(gè)元胞間的差異。

定義3演化規(guī)則

根據(jù)元胞鄰居的類(lèi)型計(jì)算元胞及其鄰居的每個(gè)目標(biāo)函數(shù)值，并根據(jù)偏序關(guān)系進(jìn)行比較，選擇最好的Pareto最優(yōu)解集。

定義4偏序關(guān)系

在處理多目標(biāo)優(yōu)化問(wèn)題時(shí)，采用偏序關(guān)系同時(shí)考慮Pareto解集的收斂性和分布性。首先采用非支配排序法分析Pareto解集的收斂性，將所有搜索個(gè)體分成不同層級(jí)。目前沒(méi)有被其它任何個(gè)體所支配的個(gè)體為非支配的(Pareto-占優(yōu)的)，定義該個(gè)體的rank為1，所有這些非支配的個(gè)體集合成為第一層Pareto-占優(yōu)集合；然后對(duì)剩下的個(gè)體繼續(xù)按照上述方法生成第二層Pareto-占優(yōu)集合。以此類(lèi)推，將每個(gè)尋優(yōu)個(gè)體都進(jìn)行排序[8]。

除考慮Pareto解集收斂性外，還需考慮其分布情況。采用擁擠距離分析個(gè)體之間聚集情況[8]。設(shè)P[n]distance為個(gè)體n的擁擠距離，P[n].k為個(gè)體n的第k個(gè)目標(biāo)函數(shù)值。當(dāng)有r個(gè)目標(biāo)函數(shù)時(shí)，第n個(gè)個(gè)體擁擠距離為

(15)

通過(guò)上述計(jì)算，每個(gè)搜索個(gè)體都有排序值和擁擠距離兩個(gè)特征值。在此基礎(chǔ)上，定義個(gè)體n和個(gè)體m的偏序關(guān)系：當(dāng)P[n]rankP[m]distance時(shí),n?m。其中，P[n]rank和P[m]rank分別表示個(gè)體n和個(gè)體m的rank值。

3.2 候選解的表示

本文采用V型轉(zhuǎn)換函數(shù)進(jìn)行處理：

(16)

(17)

在得到模型中的選址變量后，根據(jù)各個(gè)需求點(diǎn)到備選消防救援點(diǎn)的行車(chē)時(shí)間，將每個(gè)需求點(diǎn)分配到離其最近的消防救援點(diǎn)，就得到了模型中的分配變量。該方法突出了時(shí)效性相對(duì)于經(jīng)濟(jì)性的重要性。

需要指出的是，在生成選址變量時(shí)，可能會(huì)產(chǎn)生不可行解，需要對(duì)此進(jìn)行修復(fù)。當(dāng)消防救援站建設(shè)數(shù)量超過(guò)預(yù)設(shè)值時(shí)，根據(jù)偏序關(guān)系，每次選擇排名最后的個(gè)體對(duì)應(yīng)的已建備選點(diǎn)進(jìn)行關(guān)閉，直到備選設(shè)施數(shù)滿足規(guī)定數(shù)量要求。當(dāng)消防救援站建設(shè)數(shù)量低于預(yù)設(shè)值時(shí)，同樣根據(jù)偏序關(guān)系，每次選擇排名第一的個(gè)體對(duì)應(yīng)的未建備選點(diǎn)，直到備選設(shè)施數(shù)等于規(guī)定數(shù)量。

因此，利用上述候選解的表示方式，就可以直接生成該問(wèn)題的可行解。

3.3 算法流程

綜上所述，給出求解新模型的元胞陰陽(yáng)平衡優(yōu)化算法的主要計(jì)算步驟:

步驟1隨機(jī)產(chǎn)生兩個(gè)初始點(diǎn)P1和P2，初始化搜索步長(zhǎng)δ1和δ2以及更新頻率I；

步驟2根據(jù)偏序關(guān)系，若點(diǎn)P2優(yōu)于點(diǎn)P1，則互換這兩個(gè)點(diǎn)取值和步長(zhǎng)；

步驟3將點(diǎn)P1和P2保存到歸檔集；

步驟4在基于超球體的解更新階段，按相同概率原則分別利用P1與P2進(jìn)行優(yōu)化搜索；

步驟5根據(jù)演化規(guī)則，元胞在鄰居范圍內(nèi)進(jìn)行演化，并根據(jù)偏序關(guān)系，保存最好的Pareto最優(yōu)解；

步驟6若迭代間隔數(shù)和更新頻率I相等，則進(jìn)入基于歸檔集的解更新階段，轉(zhuǎn)步驟7；否則，轉(zhuǎn)步驟8；

步驟7根據(jù)偏序關(guān)系，利用歸檔集對(duì)當(dāng)前P1和P2進(jìn)行更新，調(diào)整兩個(gè)步長(zhǎng)δ1和δ2，重新生成更新頻率I；

步驟8若迭代次數(shù)達(dá)到預(yù)設(shè)最大值，算法停止，輸出最終的Pareto解集；否則，轉(zhuǎn)到步驟2。

4 數(shù)值實(shí)驗(yàn)

通過(guò)實(shí)驗(yàn)測(cè)試新模型和新算法的可行性和有效性。首先給出算例及其計(jì)算結(jié)果；然后比較新模型和最大覆蓋模型的選址方案；最后將新算法和5種智能優(yōu)化方法的計(jì)算性能進(jìn)行比較。

4.1 算例和計(jì)算結(jié)果

現(xiàn)有60個(gè)區(qū)域(分別用1～60進(jìn)行標(biāo)號(hào))，政府計(jì)劃在50個(gè)備選點(diǎn)(分別用1～50進(jìn)行標(biāo)號(hào))中選擇3個(gè)點(diǎn)建造消防救援站。火災(zāi)風(fēng)險(xiǎn)等級(jí)極高的需求點(diǎn)有1、9、13、14、22、23、29、31、34、35、42、52，對(duì)應(yīng)人口數(shù)各為15.36、15.22、14.83、12.81、13.09、16.25、12.02、18.78、19.86、18.98、18.75、18.62(人口單位：萬(wàn))；火災(zāi)風(fēng)險(xiǎn)等級(jí)嚴(yán)重的需求點(diǎn)有3、27、32、33、36、43、46、53、54、56、57、59、60，對(duì)應(yīng)人口數(shù)各為11.46、14.56、11.73、17.71、10.09、16.67、18.34、14.57、16.81、19.30、17.02、18.79、14.08；火災(zāi)風(fēng)險(xiǎn)等級(jí)中等的需求點(diǎn)有2、7、8、11、17、39、40、41、47、48、49、50、55，對(duì)應(yīng)人口數(shù)各為7.95、7.00、9.03、9.48、6.86、8.35、11.61、8.53、11.15、9.58、6.43、10.83、10.43；火災(zāi)風(fēng)險(xiǎn)等級(jí)輕微的需求點(diǎn)有4、5、6、10、12、15、16、18、19、20、21、24、25、26、28、30、37、38、44、45、51、58，對(duì)應(yīng)人口數(shù)各為5.21、5.86、4.97、7.71、1.64、3.39、5.09、1.59、4.83、2.28、2.01、8.49、5.99、6.39、4.69、5.70、3.37、2.22、4.49、8.47、4.45、3.16。(限于篇幅，需求點(diǎn)到救援站備選點(diǎn)行車(chē)時(shí)間和備選點(diǎn)建設(shè)成本數(shù)據(jù)請(qǐng)和第一作者聯(lián)系)。

采用CYYPO算法求解上述算例。

算法參數(shù)設(shè)置為Imin=1，Imax=5，α=25。此外，兩個(gè)搜索步長(zhǎng)δ1和δ2初值設(shè)為0.5，為預(yù)防δ2無(wú)限制增加，越過(guò)算法搜索空間，設(shè)其上限為0.75。穆?tīng)栢従訁?shù)r取1。最大函數(shù)評(píng)價(jià)次數(shù)為40000次。實(shí)驗(yàn)在IntelCorei53.00GHz、8G內(nèi)存的計(jì)算機(jī)上進(jìn)行，軟件為Windows10和MatlabR2019a。

CYYPO算法共求出14組Pareto最優(yōu)解。這里，僅給出第2個(gè)Pareto最優(yōu)解對(duì)應(yīng)的分配方案。選擇的消防設(shè)施點(diǎn)為20、24和32。分配給20號(hào)消防設(shè)施點(diǎn)的需求點(diǎn)有4、7、13、15、25、26、31、33、34、41、44、48、52、56、57和59；分配給24號(hào)消防設(shè)施點(diǎn)的需求點(diǎn)有1、6、8、9、10、12、14、17、19、20、21、22、23、27、28、29、32、35、36、40、42、43、45、46、54、55和60；分配給32號(hào)消防設(shè)施點(diǎn)的需求點(diǎn)有2、3、5、11、16、18、24、30、37、38、39、47、49、50、51、53和58。時(shí)效性函數(shù)值為1的需求點(diǎn)包括1、3、5、6、7、8、9、10、11、12、13、14、15、16、18、22、23、25、26、28、29、30、31、32、33、34、35、37、38、39、41、42、43、46、48、49、50、51、52、54、55、56、57和60；其它需求點(diǎn)(按標(biāo)號(hào)順序)的時(shí)效性函數(shù)值分別為0.7540、0.5572、0.4551、0.7089、0.7271、0.2176、0.5150、0.7790、0.7958、0.8100、0.7990、0.3015、0.8038、0.7958、0.7958、0.6637和0.7685。

從上述結(jié)果可以發(fā)現(xiàn)，所有需求點(diǎn)的時(shí)效性函數(shù)值均大于0，說(shuō)明消防站可以在規(guī)定時(shí)間內(nèi)到達(dá)救援現(xiàn)場(chǎng)。所有需求點(diǎn)時(shí)效性函數(shù)平均值為0.9009，時(shí)效性函數(shù)值為1的需求點(diǎn)比例為72%?；馂?zāi)風(fēng)險(xiǎn)等級(jí)為極高、嚴(yán)重、中等和輕微的四種需求點(diǎn)時(shí)效性函數(shù)值平均值分別為1、0.9362、0.8856和0.8349，時(shí)效性函數(shù)值為1的比例分別為100%、69%、62%和63%。在建模時(shí)引入時(shí)效性函數(shù)，能夠從整體考慮各種類(lèi)型需求點(diǎn)救援時(shí)間要求，盡量實(shí)現(xiàn)消防站規(guī)劃的系統(tǒng)最優(yōu)。下文將所建模型和最大覆蓋模型的計(jì)算結(jié)果做比較，說(shuō)明新模型的有效性。

4.2 模型對(duì)比

本文構(gòu)建的雙目標(biāo)消防救援站選址模型是最大覆蓋模型的一種擴(kuò)展形式，將從綜合覆蓋水平、建設(shè)總成本和時(shí)效性函數(shù)值三方面對(duì)這兩種模型進(jìn)行比較。最大覆蓋模型采用Matlab優(yōu)化工具箱進(jìn)行求解。雙目標(biāo)消防救援站選址模型仍采用CYYPO算法進(jìn)行求解，參數(shù)設(shè)置保持不變。考慮從50個(gè)備選點(diǎn)選擇3個(gè)、4個(gè)和5個(gè)待建點(diǎn)三種情況。

在第一種選址問(wèn)題中，最大覆蓋模型和雙目標(biāo)選址模型的選址方案各為(28,40,50)和(20,24,32)；綜合覆蓋水平各為409.4058和575.1102；總成本各為548和469。在第二種選址問(wèn)題中，這兩種模型的選址方案各為(8,26,40,48)和(13,34,38,41)；綜合覆蓋水平各為422.9375和579.9749；總成本各為769和622。在第三種選址問(wèn)題中，這兩種模型的選址方案各為(5,34,45,49,50)和(8,15,33,35,46)；綜合覆蓋水平各為405.7096和584.4218；總成本各為1076和962。從上述結(jié)果可以發(fā)現(xiàn)，和最大覆蓋模型相比，雙目標(biāo)選址模型不僅可以提高總救援服務(wù)質(zhì)量，而且可以降低總建設(shè)成本。

此外，還比較了這兩種模型有關(guān)四種風(fēng)險(xiǎn)等級(jí)需求點(diǎn)的時(shí)效性指標(biāo)。在第一種選址問(wèn)題中，對(duì)最大覆蓋模型而言，風(fēng)險(xiǎn)等級(jí)為極高、嚴(yán)重、中等和輕微的需求點(diǎn)時(shí)效性平均值各為0.7491、0.6742、0.5122和0.5869；時(shí)效性值為1的比例各為50%、38%、8%和14%。對(duì)雙目標(biāo)選址模型而言，這四種需求點(diǎn)時(shí)效性平均值各為1、0.9362、0.8856和0.8349；時(shí)效性值為1的比例各為100%、69%、62%和63%。

在第二種選址問(wèn)題中，對(duì)最大覆蓋模型而言，四種風(fēng)險(xiǎn)等級(jí)需求點(diǎn)時(shí)效性平均值各為0.8815、0.6382、0.5349和0.6408；時(shí)效性值為1的比例各為75%、15%、15%和32%。對(duì)雙目標(biāo)選址模型而言，這四種需求點(diǎn)時(shí)效性平均值各為1、0.9510、0.8642和0.8721；時(shí)效性值為1的比例各為100%、77%、69%和64%。

在第三種選址問(wèn)題中，對(duì)最大覆蓋模型而言，四種風(fēng)險(xiǎn)等級(jí)需求點(diǎn)時(shí)效性平均值各為0.6893、0.6283、0.5251和0.8223；時(shí)效性值為1的比例各為42%、31%、23%和59%。對(duì)雙目標(biāo)選址模型而言，這四種需求點(diǎn)時(shí)效性平均值各為1、1、0.8840和0.8303；時(shí)效性值為1的比例各為100%、100%、54%和50%。

從上述結(jié)果可以知道，在這三種選址問(wèn)題中，在絕大多數(shù)時(shí)效性評(píng)價(jià)指標(biāo)方面，雙目標(biāo)選址模型均明顯優(yōu)于最大覆蓋模型。究其原因，所建模型在考慮消防救援水平總體最優(yōu)情況下，也可以提高大多數(shù)類(lèi)型需求點(diǎn)的平均救援水平。需要指出的是，采用其它非劣解和最大覆蓋模型的計(jì)算結(jié)果進(jìn)行比較時(shí)，也會(huì)得到類(lèi)似結(jié)論。因此，本文為消防救援站布局規(guī)劃提供了一種可行有效的選址模型。

表1 六種多目標(biāo)智能優(yōu)化算法計(jì)算結(jié)果比較

4.3 不同算法的求解性能比較

為進(jìn)一步測(cè)試CYYPO算法的計(jì)算性能，選擇蝙蝠算法BA、蜂群算法BCA、和聲搜索算法HS、NGSA-Ⅱ和元胞蟻群優(yōu)化算法CACO進(jìn)行對(duì)比測(cè)試。為公平起見(jiàn)，這6種算法設(shè)置相同最大函數(shù)評(píng)價(jià)次數(shù)，均為40000次。CYYPO算法參數(shù)設(shè)置保持不變，其它算法參數(shù)根據(jù)文獻(xiàn)[8]和[10]進(jìn)行設(shè)置。

采用常用的Hypervolume指標(biāo)[8,12]、Spread指標(biāo)[8,12]以及Ω支配性指標(biāo)[8,12]進(jìn)行算法優(yōu)化性能比較。第一個(gè)指標(biāo)用于評(píng)估算法非劣解集收斂性。該指標(biāo)值越小，說(shuō)明算法非劣解集收斂性越好。第二個(gè)指標(biāo)用于評(píng)估非劣解集的多樣性與分布均勻性。該指標(biāo)值越小，算法非劣解集的多樣性越好，分布更加均勻。第三個(gè)指標(biāo)用于評(píng)估算法獲得優(yōu)秀結(jié)果比例。該指標(biāo)越大，說(shuō)明算法得到非劣解數(shù)量越多。

在實(shí)驗(yàn)中，仍然考慮上述三種選址問(wèn)題。針對(duì)每一種問(wèn)題，這6種算法各自運(yùn)行30次，分別統(tǒng)計(jì)上述三種指標(biāo)的平均值和標(biāo)準(zhǔn)差。實(shí)驗(yàn)結(jié)果如表1所示。此外，由于所求解問(wèn)題真實(shí)Pareto最優(yōu)解集未知，本文先求出所有算法得到的非劣解集的并集，再取其中的非支配解集作為近似Pareto最優(yōu)解集。

從表1可以發(fā)現(xiàn)，對(duì)于Hypervolume指標(biāo)、Spread指標(biāo)和Ω支配性指標(biāo)而言， CYYPO算法在絕大多數(shù)選址測(cè)試問(wèn)題上優(yōu)勢(shì)顯著。在迭代過(guò)程中，CYYPO算法充分利用陰陽(yáng)平衡優(yōu)化算法全局探索能力強(qiáng)的特點(diǎn)，即利用P2在超球體內(nèi)進(jìn)行全局搜索，以搜索到盡可能多的含有Pareto最優(yōu)解區(qū)域；在算法搜索空間尋優(yōu)的個(gè)體同時(shí)也分布在元胞空間，利用演化規(guī)則在鄰居范圍內(nèi)對(duì)這些區(qū)域進(jìn)行精細(xì)化搜索。此外，通過(guò)P1和P2的互換策略實(shí)現(xiàn)優(yōu)化信息在算法搜索空間和元胞空間共享，尋優(yōu)個(gè)體可以動(dòng)態(tài)調(diào)整搜索行為。隨著優(yōu)化搜索的深入，CYYPO算法能夠向分布在不同區(qū)域的多個(gè)Pareto最優(yōu)解逼近。因此，新算法的非劣解集的收斂性、分布的多樣性和均勻性更好。

此外，還測(cè)試了這6種算法優(yōu)化速度，比較這些算法獲得指定非劣解個(gè)數(shù)(分別為4、6和8)的平均計(jì)算時(shí)間。在第一組問(wèn)題中，這6種算法平均計(jì)算時(shí)間各為7.2、9.8、12.3、6.1、5.6和2.5。在第二組問(wèn)題中，這6種算法平均計(jì)算時(shí)間各為19.6、18.7、27.6、11.3、13.4和3.4。在第三種問(wèn)題中，除HS沒(méi)有在30分鐘內(nèi)獲得指定數(shù)量的非劣解外，其它5種算法平均計(jì)算時(shí)間各為28.5、27.1、22.3、24.9和6.7(單位：分鐘)。在所有測(cè)試問(wèn)題上，CYYPO算法所需要的平均計(jì)算時(shí)間都是最少的。因此，本文為雙目標(biāo)消防救援站選址問(wèn)題的求解提供了一種有競(jìng)爭(zhēng)力方法。

5 結(jié)束語(yǔ)

消防救援站選址是應(yīng)急管理中一類(lèi)重要研究問(wèn)題。本文引入時(shí)效性評(píng)價(jià)函數(shù)衡量救援服務(wù)質(zhì)量，構(gòu)建考慮時(shí)效性的綜合覆蓋水平以及總建設(shè)成本的雙目標(biāo)選址模型，并設(shè)計(jì)元胞陰陽(yáng)平衡優(yōu)化算法進(jìn)行求解。實(shí)驗(yàn)表明，所建立的模型可以有效求解消防救援站布局規(guī)劃問(wèn)題。和5種智能優(yōu)化算法相比較，所設(shè)計(jì)算法具有更好優(yōu)化性能。在選址基礎(chǔ)上，考慮消防車(chē)輛調(diào)度問(wèn)題是下一步研究方向。