張惠彬 黃順祥 劉峰 關(guān)彩虹

(1.中國(guó)人民解放軍北部戰(zhàn)區(qū)疾病預(yù)防控制中心 沈陽 110030； 2.中國(guó)人民解放軍防化學(xué)院 北京 102205)

0 引言

大氣污染化學(xué)事故一直威脅著人民生命財(cái)產(chǎn)安全，同時(shí)嚴(yán)重影響著生態(tài)環(huán)境。在2006—2010年間，我國(guó)共發(fā)生危險(xiǎn)化學(xué)品事故490起，共造成879人死亡，其中較大事故70起，死亡310人，重大事故5起，死亡96人。事故發(fā)生后，對(duì)人員及時(shí)疏散是控制事故損失的最重要的措施之一，只有及時(shí)有效的進(jìn)行人員疏散才能大量減少人員傷亡。NISHINARI等[1]運(yùn)用蟻群算法對(duì)人員疏散路徑的優(yōu)化問題進(jìn)行研究，并進(jìn)行了仿真實(shí)驗(yàn)。葉啟文[2]對(duì)城市軌道交通突發(fā)事件的人員疏散問題進(jìn)行研究，并運(yùn)用遺傳算法進(jìn)行目標(biāo)優(yōu)化。薛李生輝等[3]運(yùn)用粒子群算法研究公共場(chǎng)所突發(fā)事件人員疏散問題。靳寧[4]將蟻群算法與Agent理論相結(jié)合，將人員疏散過程中的物理因素與人員的社會(huì)行為進(jìn)行結(jié)合研究。

遺傳算法GA (Genetic Algorithm)是進(jìn)化算法EA (Evolutionary Algorithm)中最有代表性的一類，這種算法旨在通過模擬自然界生物的遺傳進(jìn)化過程，找到最優(yōu)解。20世紀(jì)70年代美國(guó)密歇根大學(xué)的HOLLAND[5]教授出版的著作以及JONG[6]發(fā)表的博士論文最早提出了遺傳算法的概念體系，80年代是遺傳算法發(fā)展最迅速的時(shí)期，不管是應(yīng)用研究還是理論研究都成了熱門課題，從1985年開始，每?jī)赡甓家匍_一次遺傳算法國(guó)際會(huì)議(ICGA)，并成立了國(guó)際遺傳算法協(xié)會(huì)(ISGA)。1989年，GOLDBERG[7]對(duì)遺傳算法進(jìn)行了全面剖析，撰寫《搜索、優(yōu)化和機(jī)器學(xué)習(xí)中的遺傳算法》一書，總結(jié)了遺傳算法的主要研究成果。2000年，HAN等[8]提出了量子遺傳算法( Quantum Genetic Algorithm)，該算法將量子的態(tài)矢量表達(dá)形式引入遺傳編碼中，用量子旋轉(zhuǎn)門來實(shí)現(xiàn)染色體基因的調(diào)整，這一調(diào)整為該算法在計(jì)算機(jī)上的執(zhí)行提供了扎實(shí)的理論基礎(chǔ)。2009年，章琳等[9]提出了基于遺傳算法的多小波自適應(yīng)去噪算法，該算法能通過遺傳算法自適應(yīng)地尋求圖像去噪后的最小均方差。

本文擬通過遺傳算法對(duì)優(yōu)化模型求解，并對(duì)算法進(jìn)行適當(dāng)調(diào)整，以期得到最理想的疏散路徑。

1 人員疏散路徑優(yōu)化模型的建立

1.1 建?；舅枷?/h3>

影響人員疏散的因素主要有三方面，一是疏散路線的距離，二是道路的通行難易程度，三是化學(xué)毒劑的大氣擴(kuò)散情況。計(jì)算疏散路線的距離，可以把整個(gè)區(qū)域每一個(gè)路口設(shè)為一個(gè)節(jié)點(diǎn)，通過分段計(jì)算各節(jié)點(diǎn)間的距離，就能得到整條疏散路徑的距離。道路通行難易程度可以看成是路徑的通行修正系數(shù)，主要由日常車輛行駛速度決定?；瘜W(xué)毒劑的大氣擴(kuò)散因素是最重要的影響因素[10]，直接影響人員的傷亡，所以是最應(yīng)該避開的因素，如果避不開，也要選擇擴(kuò)散濃度低的路徑。進(jìn)行路徑優(yōu)化前首先就要進(jìn)行大氣擴(kuò)散模擬[11-12]，應(yīng)用擴(kuò)散模擬的濃度場(chǎng)數(shù)據(jù)，運(yùn)用毒負(fù)荷模型進(jìn)行毒性計(jì)算，選取傷亡概率最小的路段通行。通過以上三方面因素的影響，定義疏散當(dāng)量長(zhǎng)度，該當(dāng)量長(zhǎng)度最小的路徑就是最優(yōu)路徑。

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

1.2.1 節(jié)點(diǎn)矩陣

從事發(fā)點(diǎn)到疏散安置點(diǎn)的整個(gè)區(qū)域中，有n個(gè)節(jié)點(diǎn)，第i節(jié)點(diǎn)的坐標(biāo)為(xi,yi)，事發(fā)點(diǎn)坐標(biāo)為(x1,y1)，從第i個(gè)節(jié)點(diǎn)到第j個(gè)節(jié)點(diǎn)之間的距離為dij，通行難易程度為kij。

D=[dij]

D表示節(jié)點(diǎn)間的距離矩陣，用矩陣表示為：

(1)

從矩陣中可以看出，當(dāng)節(jié)點(diǎn)i等于節(jié)點(diǎn)j時(shí)，dij=0，另外，在實(shí)際通行時(shí)并不是所有的節(jié)點(diǎn)間都有路段連接，那么在計(jì)算時(shí)可以把這些節(jié)點(diǎn)間的距離值設(shè)成較大的值，比如，節(jié)點(diǎn)i和節(jié)點(diǎn)j之間不能相連，那么dij=Na，這樣就能確保最優(yōu)路徑不會(huì)出現(xiàn)無法連通的路段。

同理，設(shè)通行難易程度矩陣為：

K=[kij]

(2)

1.2.2 目標(biāo)函數(shù)

定義當(dāng)量長(zhǎng)度L，該當(dāng)量長(zhǎng)度主要受三方面因素影響，分別為路徑長(zhǎng)度，通行難易程度，以及大氣擴(kuò)散的影響，在三因素影響下，當(dāng)量長(zhǎng)度最小的路徑就是最優(yōu)路徑。

目標(biāo)函數(shù)表示為：

(3)

dij用節(jié)點(diǎn)間的坐標(biāo)來確定，即：

(4)

kij由兩節(jié)點(diǎn)間的距離和日常行車速度vij來確定，即：

(5)

λ表示用罰函數(shù)的形式把大氣擴(kuò)散的影響引入到模型參與計(jì)算，主要由節(jié)點(diǎn)的擴(kuò)散濃度來決定，這里引入輕度危害濃度閾值ca，中度危害濃度閾值cb，重度危害濃度閾值cc，致死危害濃度閾值cd，那么：

(6)

2 基于遺傳算法的優(yōu)化求解方法

對(duì)于人員疏散的路徑優(yōu)化問題，沒有現(xiàn)成的算法設(shè)計(jì)可用，需要有針對(duì)性地進(jìn)行算法設(shè)計(jì)，從而實(shí)現(xiàn)算法的有效運(yùn)行，找到最優(yōu)路徑。算法設(shè)計(jì)完成后，應(yīng)用Matlab軟件編寫源代碼，進(jìn)行計(jì)算求解。

2.1 染色體編碼設(shè)計(jì)以及初始化種群

在編碼設(shè)計(jì)時(shí)，主要考慮了兩種編碼設(shè)計(jì)，一種是[0-1]之間的隨機(jī)數(shù)編碼，一種是[1-n]之間的自然數(shù)隨機(jī)編碼，都屬于浮點(diǎn)數(shù)編碼。自然數(shù)隨機(jī)編碼簡(jiǎn)單直觀，便于理解，就是將染色體的自然數(shù)順序確定為路徑經(jīng)過節(jié)點(diǎn)的順序，起點(diǎn)1和終點(diǎn)n保持不變。隨機(jī)數(shù)編碼就是在[0-1]之間隨機(jī)產(chǎn)生n個(gè)隨機(jī)數(shù)，但是第一個(gè)基因?yàn)?，第n個(gè)基因?yàn)?，以保證起點(diǎn)和終點(diǎn)不參與遺傳，這些隨機(jī)數(shù)按數(shù)值大小升序確定節(jié)點(diǎn)，比如：

對(duì)于染色體V=[0 0.012 0.176 0.765 0.489 0.243 0.315 1]

對(duì)應(yīng)的路徑就是L=[1 2 3 7 6 4 5 8]

應(yīng)用隨機(jī)數(shù)編碼進(jìn)行數(shù)值實(shí)驗(yàn)時(shí)，實(shí)驗(yàn)結(jié)果出現(xiàn)了走回頭路的現(xiàn)象，因?yàn)檫@些隨機(jī)數(shù)每個(gè)都不一樣，所以染色體基因都不同，即使經(jīng)過最大遺傳代數(shù)迭代，依然如此。所以，隨機(jī)數(shù)編碼不適用人員疏散的路徑優(yōu)化。

自然數(shù)編碼簡(jiǎn)單直觀，中間節(jié)點(diǎn)隨機(jī)產(chǎn)生，本文采用自然數(shù)編碼進(jìn)行路徑優(yōu)化。并隨機(jī)產(chǎn)生100個(gè)個(gè)體作為初始種群。

2.2 適應(yīng)度函數(shù)的建立

適應(yīng)度函數(shù)一般都建立在目標(biāo)函數(shù)的基礎(chǔ)上，本文建立的適應(yīng)度函數(shù)同樣以目標(biāo)函數(shù)為基礎(chǔ)。通過分析目標(biāo)函數(shù)可知，每個(gè)個(gè)體的目標(biāo)值均為正值，因此，考慮到適應(yīng)度函數(shù)的簡(jiǎn)單適用原則，建立適應(yīng)度函數(shù)為：

(7)

其中，L(i)表示種群中第i個(gè)個(gè)體的目標(biāo)函數(shù)取值。

2.3 選擇算子

計(jì)算出種群中個(gè)體的適應(yīng)度之后，就要進(jìn)行選擇，目的是選擇適應(yīng)度高的個(gè)體進(jìn)行下一步的遺傳操作。常用的選擇算子有輪盤賭選擇、隨機(jī)競(jìng)爭(zhēng)選擇、最佳保留選擇、無回放隨機(jī)選擇等，本文采用輪盤賭選擇算子進(jìn)行計(jì)算。其計(jì)算過程如下：

首先，計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度總和Fz：

(8)

其次，計(jì)算種群中每個(gè)個(gè)體的選擇概率pi，計(jì)算公式如下：

(9)

2.4 交叉算子

交叉算子通過模擬生物個(gè)體之間的交配，產(chǎn)生新的個(gè)體。常用的方法有單點(diǎn)交叉、兩點(diǎn)交叉與多點(diǎn)交叉、均勻交叉以及算數(shù)交叉等。本文選用單點(diǎn)交叉產(chǎn)生新的個(gè)體，不選用多點(diǎn)交叉以及其他交叉方法是由人員疏散路徑優(yōu)化問題本身決定的，因?yàn)槎帱c(diǎn)交叉等方法對(duì)個(gè)體結(jié)構(gòu)的破壞性較大，不能很好的延續(xù)母體的優(yōu)點(diǎn)，對(duì)于路徑問題，一段好的路徑選擇不宜設(shè)置多個(gè)交叉點(diǎn)，所以本文選擇單點(diǎn)交叉算子，交叉方法如下：

2.5 變異算子

在遺傳算法中，變異算子雖然是生成新個(gè)體的輔助算子，但作用卻十分關(guān)鍵，因?yàn)樽儺愃阕幽苡行Х乐顾惴ㄟM(jìn)入局部最優(yōu)陷阱。本文選擇互換變異算子，即在一定概率的情況下，在部分個(gè)體中隨機(jī)指定兩個(gè)有效基因互換位置，達(dá)到產(chǎn)生新個(gè)體的目的，變異方法如下：

A=(1 3 5 4 6 7 5 3 7 9)

隨機(jī)互換位置為2和5，得到新個(gè)體B：

B=(1 6 5 4 3 7 5 3 7 9)

2.6 新個(gè)體的邏輯處理

初始種群中的個(gè)體經(jīng)過交叉和變異后生成新的個(gè)體，由于這些個(gè)體都是自然數(shù)編碼，所以這些生成的新個(gè)體中難免會(huì)有重復(fù)的數(shù)字，每一個(gè)新個(gè)體代表著一條新的路徑，如果路徑中出現(xiàn)重復(fù)的節(jié)點(diǎn)就代表著走回頭路，這明顯是錯(cuò)誤的，如果這一問題不能解決就會(huì)導(dǎo)致計(jì)算無法收斂。這一問題的解決方法如下：

初始種群中的個(gè)體有n個(gè)基因，為了便于說明假設(shè)n=9，A0，B0為其中兩個(gè)個(gè)體：

A0=(1 3 5 4 7 2 6 8 9)

B0=(1 2 5 8 6 3 7 4 9)

單點(diǎn)交叉后，產(chǎn)生新個(gè)體A1，B1：

A1=(1 3 5 4 7 3 7 4 9)

B1=(1 2 5 8 6 2 6 8 9)

互換變異后，產(chǎn)生新個(gè)體A2，B2：

A2=(1 4 5 4 7 3 7 3 9)

B2=(1 8 5 8 6 2 6 2 9)

這時(shí)可以看出A2，B2中均有重復(fù)的數(shù)字出現(xiàn)，這時(shí)采取的方法是，對(duì)于這些重復(fù)的數(shù)字，前面的數(shù)字保留，后面出現(xiàn)的數(shù)字變成9并且移到個(gè)體序列最后的位置。對(duì)于有n個(gè)基因的個(gè)體來說，就是把后面出現(xiàn)的重復(fù)數(shù)字變成n，并移到個(gè)體序列最后的位置。A2，B2經(jīng)過如上操作，變成新個(gè)體A3，B3：

A3=(1 4 5 7 3 9 9 9 9)

B3=(1 8 5 6 2 9 9 9 9)

個(gè)體邏輯處理的Matlab程序如下：

%%種群中有90個(gè)個(gè)體，每個(gè)個(gè)體有13個(gè)基因，該種群變異后的邏輯重整%%

p3=ones(90,13)*13;

for i=1∶90

p2=unique(p1(i,:),'stable');

w=length(p2);

p3(i,1∶w)=p2;%重整后的新種群

end

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

為了驗(yàn)證算法的可行性，在這里設(shè)計(jì)一個(gè)案例進(jìn)行數(shù)值實(shí)驗(yàn)，該案例通過分析就可得知最優(yōu)路徑的大致范圍，再通過算法計(jì)算最優(yōu)路徑，看算法能否找到該路徑，從而驗(yàn)證算法的可行性。

3.1 實(shí)驗(yàn)案例設(shè)計(jì)

如圖1所示，在節(jié)點(diǎn)1處的化工廠發(fā)生爆炸事故，大量硫化氫氣體發(fā)生泄漏，在廠區(qū)內(nèi)的監(jiān)測(cè)設(shè)備監(jiān)測(cè)到硫化氫氣體濃度已經(jīng)超過安全濃度閾值，且濃度迅速上升，此時(shí)主導(dǎo)風(fēng)向?yàn)槲髂巷L(fēng)，在節(jié)點(diǎn)1附近的群眾需要立即撤離。假設(shè)經(jīng)過大氣擴(kuò)散模擬，得到擴(kuò)散區(qū)域內(nèi)的濃度場(chǎng)分布，在各節(jié)點(diǎn)處的模擬擴(kuò)散濃度如表1所示，可以看出2，5節(jié)點(diǎn)處的擴(kuò)散濃度超過了重度危害濃度閾值，節(jié)點(diǎn)3處的擴(kuò)散濃度超過了中度危害濃度閾值，6，4節(jié)點(diǎn)處的擴(kuò)散濃度超過了輕度危害濃度閾值，人員疏散路徑經(jīng)過這些節(jié)點(diǎn)時(shí)懲罰系數(shù)λ迅速變大，導(dǎo)致當(dāng)量長(zhǎng)度L變大，從而被算法舍棄。

表1 節(jié)點(diǎn)擴(kuò)散濃度

圖1 疏散區(qū)域路徑分布

3.2 算法求解

運(yùn)用MATLAB2014a軟件編寫源代碼，進(jìn)行算法計(jì)算，其中初始種群規(guī)模100，最大遺傳代數(shù)500，代差0.9，交叉概率0.7，變異概率0.05。經(jīng)過500次迭代，輸出結(jié)果固定，最小當(dāng)量長(zhǎng)度為97，最優(yōu)路線為：1-8-9-10-12-13。圖2表示500次迭代過程中解的變化以及種群均值的變化，由圖中可以看出，迭代開始后解和種群均值迅速變小，且在100次迭代后保持了穩(wěn)定，體現(xiàn)了算法的穩(wěn)定性以及收斂速度較快的特點(diǎn)。算法選擇的最優(yōu)路線為：1-8-9-10-12-13。盡管疏散區(qū)域南部道路通行難度較大，但是受毒氣擴(kuò)散的影響較小，由于懲罰系數(shù)的限制，使選擇中部或北部區(qū)域道路的路徑當(dāng)量長(zhǎng)度增大，驅(qū)動(dòng)算法選擇南部區(qū)域的道路，體現(xiàn)了算法的準(zhǔn)確性以及可行性。

圖2 500次迭代后種群均值變化和解的變化

4 結(jié)論

本文對(duì)大氣污染化學(xué)事故中的人員應(yīng)急疏散問題進(jìn)行了研究，建立了人員疏散路徑優(yōu)化模型，設(shè)計(jì)了關(guān)于人員疏散路徑優(yōu)化問題的遺傳算法，并通過數(shù)值實(shí)驗(yàn)，驗(yàn)證了算法的可行性。主要結(jié)論如下：

(1)影響人員疏散的因素主要有三方面原因，一是疏散路線的距離，二是道路的通行難易程度，三是化學(xué)毒劑的大氣擴(kuò)散情況。本文依據(jù)這三方面影響因素，建立了人員疏散路徑優(yōu)化模型。

(2)建立了適用于計(jì)算人員疏散路徑優(yōu)化問題的遺傳算法方案。其中新個(gè)體的邏輯重整方法，成功解決了算法無法收斂的問題。根據(jù)遺傳算法方案，編寫了MATLAB程序。

(3)通過數(shù)值實(shí)驗(yàn)，模擬疏散現(xiàn)場(chǎng)，發(fā)現(xiàn)算法能很快得到計(jì)算結(jié)果，并且迅速收斂，驗(yàn)證了算法的可行性和適行性。