基于加權(quán)聚合粒子群算法的礦井火災(zāi)救援研究

黃萍，李兵磊

(1.福州大學(xué)環(huán)境與資源學(xué)院，福建福州350116; 2.福州大學(xué)紫金礦業(yè)學(xué)院，福建福州350116)

基于加權(quán)聚合粒子群算法的礦井火災(zāi)救援研究

黃萍1，李兵磊2

(1.福州大學(xué)環(huán)境與資源學(xué)院，福建福州350116; 2.福州大學(xué)紫金礦業(yè)學(xué)院，福建福州350116)

提出一種基于加權(quán)聚合的最小中心粒子群算法，對粒子群優(yōu)化算法的搜索范圍與目標(biāo)權(quán)重進(jìn)行改進(jìn).仿真實(shí)驗(yàn)結(jié)果表明，采用此算法在典型的標(biāo)準(zhǔn)函數(shù)測試中訓(xùn)練速度快、精度高，對其在礦井火災(zāi)救援最佳救援路線優(yōu)化模型中的性能進(jìn)行測試和分析，可知該方法有利于避免早熟收斂，增強(qiáng)全局搜索能力，同時(shí)提高非劣最優(yōu)解的精度，可為礦井火災(zāi)事故救援的決策提供重要技術(shù)支持.

礦井;火災(zāi)救援;加權(quán)聚合;最小中心;粒子群算法

0 引言

在礦井發(fā)生火災(zāi)時(shí)，對人員的井下救援往往被礦井的特殊地質(zhì)環(huán)境和復(fù)雜惡劣的疏散路線制約，被困人員難以第一時(shí)間獲取火災(zāi)的信息，這樣拖延了救援的時(shí)間，給施救人員帶來了很大的困難.根據(jù)相關(guān)數(shù)據(jù)統(tǒng)計(jì)，我國國有煤礦約有56%存在自燃的危險(xiǎn)性［1］.由此可見，礦井火災(zāi)是煤礦主要災(zāi)害之一.此外，在礦井發(fā)生火災(zāi)時(shí)，瓦斯突出和爆炸有一定的相互作用，這樣更容易造成嚴(yán)重的二次災(zāi)害［2］.因此，對礦井救援路線優(yōu)化問題的研究具有重要的意義.

礦井救援最佳路線的影響因素比較復(fù)雜，應(yīng)急救援路線是指地面救援人員以出口節(jié)點(diǎn)(主井或風(fēng)井)為起點(diǎn)，所有井下受困人員所處的危險(xiǎn)巷道位置為終點(diǎn)，救出所有受困人員回到出口節(jié)點(diǎn)的救援路徑［3］.礦井發(fā)生火災(zāi)時(shí)煙氣流、高溫氣體、耗氧量很大程度上影響最佳救援線路的選擇，因此需要科學(xué)的算法，通過比較、分析來合理地確定救援的路線.目前，傳統(tǒng)的救援路徑優(yōu)化方案有Dijkstra算法、A*算法、蟻群算法等［4］，這些傳統(tǒng)的算法往往具有運(yùn)行時(shí)間長，缺乏一定的并行性的缺點(diǎn)，在處理復(fù)雜的情況時(shí)，難以達(dá)到理想的效果.

礦井火災(zāi)最佳救援路線中含有多個(gè)優(yōu)化目標(biāo)，這樣可以將實(shí)際問題轉(zhuǎn)化為運(yùn)籌學(xué)中多個(gè)目標(biāo)優(yōu)化問題.與傳統(tǒng)的多目標(biāo)優(yōu)化方法相比較，粒子群算法在處理多目標(biāo)優(yōu)化問題時(shí)具有較大優(yōu)勢［5］.首先，它可以代表整個(gè)解集種群，因此，可以按照并行的方式在同一時(shí)間搜索多個(gè)非劣解，這樣獲得的高速搜索能力能更高效地得到多目標(biāo)意義下的最優(yōu)解［6］.其次，粒子群優(yōu)化算法(particle swarm optimization，簡稱PSO)具有收斂速度快，計(jì)算簡單，易于實(shí)現(xiàn)等優(yōu)點(diǎn).最后，PSO算法的通用性也具有較大的優(yōu)勢，能夠有效處理多重類型的目標(biāo)函數(shù)和約束，并且能順利地與傳統(tǒng)優(yōu)化方法相結(jié)合，因此能使自身的局限性得到改進(jìn)，從而達(dá)到更高效解決問題的目的［7］.

要運(yùn)用PSO來優(yōu)化問題，需要解決的關(guān)鍵問題就是如何確定每個(gè)粒子的最優(yōu)位置(gbest)以及群體的最優(yōu)位置(pbest)［8］.解決方法與目標(biāo)數(shù)有關(guān)，對于單目標(biāo)優(yōu)化問題，根據(jù)每個(gè)粒子的歷史最優(yōu)位置獲取當(dāng)前的最優(yōu)位置，群體的最優(yōu)位置決定了全局的最優(yōu)位置，這種方法十分簡單直接.但是，與單目標(biāo)不同，多目標(biāo)由于并無單個(gè)最優(yōu)位置，所以無法直接確定gbest、pbest，因此，PSO算法無法直接在應(yīng)用上解決多目標(biāo)優(yōu)化問題，它在本質(zhì)上與單目標(biāo)優(yōu)化問題存在不同:連續(xù)解集合有一組或多組，單目標(biāo)連續(xù)解只有單個(gè)或一組［9］.根據(jù)上述情況，提出一種基于加權(quán)聚合的最小中心粒子群算法(簡稱WAPSMCO)，以提高PSO的運(yùn)算效率.

1 粒子群算法的改進(jìn)

在PSO的算法中，根據(jù)最好粒子得出信息，它的表現(xiàn)是其他個(gè)體會快速地向最好粒子收斂，因此，運(yùn)用PSO算法處理多目標(biāo)優(yōu)化問題，結(jié)果容易收斂在非劣最優(yōu)域的局部［10］.由于上述的缺點(diǎn)，為了避免早熟收斂，增強(qiáng)全局搜索能力，同時(shí)提高非劣最優(yōu)解的精度.本文對算法做了如下改進(jìn).

1)針對多目標(biāo)優(yōu)化問題的非劣最優(yōu)解集的搜索，提出一種最小中心粒子群算法(簡稱PSMCO)，這種方法在每次迭代選全局最優(yōu)位置的時(shí)候，針對當(dāng)前粒子的位置算出一個(gè)最小中心，在這個(gè)中心上每個(gè)函數(shù)取值最?。?1］.然后算出每個(gè)粒子離這個(gè)中心的距離，則離中心最近的點(diǎn)即為全局最優(yōu)位置，再根據(jù)粒子群算法的公式進(jìn)行迭代.

2)在解決多目標(biāo)優(yōu)化問題上，傳統(tǒng)的方法是通過加權(quán)求和，將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題來解決，這種方法稱為加權(quán)聚合粒子群算法(簡稱WAPSO).這種方法要求對問題本身有很強(qiáng)的先驗(yàn)認(rèn)識，本文將其與粒子群最小中心優(yōu)化算法進(jìn)行結(jié)合，形成WAPSMCO算法，即在求解過程中為每一個(gè)目標(biāo)函數(shù)賦予一定的動態(tài)權(quán)重，因此將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，接著再通過最小中心法對全局求優(yōu)［12］.

具體的算法過程如下:

1)在第t步迭代的時(shí)候，步驟如圖1所示.

2)確定全局最優(yōu)位置gbest.加權(quán)聚合即對每個(gè)目標(biāo)函數(shù)給予一定的權(quán)重，是解決多目標(biāo)優(yōu)化問題最常用的方法.根據(jù)這一方法，所有的目標(biāo)都賦以加權(quán)組合F=其中wi(i=1，…，k)為非負(fù)權(quán)重.通常設(shè)定這些權(quán)重在優(yōu)化過程中可以是定值也可以動態(tài)調(diào)整.如果權(quán)重是固定的，就是傳統(tǒng)加權(quán)聚合方法(CWA).使用這個(gè)方法，每次優(yōu)化運(yùn)行只能得到一個(gè)非劣最優(yōu)解，并且需要搜索空間的先驗(yàn)知識，以便選擇適當(dāng)?shù)臋?quán)重.因此，為了得到所需數(shù)量的非劣最優(yōu)解，需要進(jìn)行重復(fù)多次的搜索.然而，由于時(shí)間的限制和繁重的計(jì)算成本，這個(gè)方法對于大多數(shù)問題都不太適用.因此，提出其他加權(quán)聚合方法來彌補(bǔ)CWA的局限性.對于多目標(biāo)優(yōu)化問題，在優(yōu)化過程中，可根據(jù)下式進(jìn)行權(quán)重修正:

式中:k為目標(biāo)函數(shù)的個(gè)數(shù);t為迭代指數(shù);F為權(quán)重的變化頻率.這就是“Bang－Bang”加權(quán)算法(BWA).據(jù)此，權(quán)重可以通過sign(－)功能突然改變.另外，權(quán)重也可以根據(jù)下式進(jìn)行逐步修正:

這就是所謂的動態(tài)加權(quán)聚合方法(DWA)［13］.本文主要采用DWA方法，同時(shí)也考慮了BWA方法，根據(jù)檢測函數(shù)的實(shí)驗(yàn)，發(fā)現(xiàn)這兩種方法得出的結(jié)果差別不大.

2 算法流程

2.1 初始化

在通常情況下粒子群算法初始化方式使用的是隨機(jī)初始化，選取c1和c2作為變量參數(shù)，分別調(diào)節(jié)向全局最好粒子和個(gè)體最好粒子方向飛行的最大步長，若太小則粒子可能遠(yuǎn)離目標(biāo)區(qū)域，若太大則會導(dǎo)致突然向目標(biāo)區(qū)域飛去，或飛過目標(biāo)區(qū)域.合適的c1、c2可以加快收斂且不易陷入局部最優(yōu)，考慮到參數(shù)有一定的波動范圍，應(yīng)該充分利用這種先驗(yàn)信息，在初始化時(shí)如果采取完全隨機(jī)初始化，就會在一些沒有意義的解上浪費(fèi)大量時(shí)間.所以，初始化時(shí)最好采用實(shí)際的參數(shù)值當(dāng)作參考值，例如:選取0.1%≤c1≤1.5%，0.5%≤c2≤2.5%，且c1＜c2，作為參數(shù)的取值范圍.將迭代次數(shù)設(shè)置為500，粒子數(shù)為100.

在程序里取不同的pro值(取值0～1之間)，就可以調(diào)整算法的側(cè)重點(diǎn)，從而對算法做出比較.當(dāng)程序里面的pro取1的時(shí)候，用的是加權(quán)聚合算法;當(dāng)程序里面的pro取0的時(shí)候，用的是最小中心算法;當(dāng)程序里面的pro取1/2的時(shí)候，是這兩種方法的結(jié)合.

2.2 域約束

在實(shí)際問題的求解上，通常解空間的要求不會是整個(gè)實(shí)數(shù)空間，而是在一個(gè)限定范圍內(nèi)求最優(yōu)解，稱為域約束，如下:

2.3 設(shè)置粒子的位置和速度

在粒子群算法中，parpos和parvel分別為粒子的位置和速度，而numiter為迭代次數(shù)(number of iteration)，numpar為粒子數(shù)(number of particles).程序源代碼如下:

2.4 主程序

1)對粒子群進(jìn)行初始化，設(shè)種群大小為N，隨機(jī)賦予每個(gè)粒子初始值為xi，vi;

2)對各個(gè)子目標(biāo)函數(shù)的值進(jìn)行計(jì)算;

3)計(jì)算粒子適應(yīng)度，采用加入懲罰函數(shù)的目標(biāo)函數(shù)方法計(jì)算;

4)確定粒子個(gè)體及全局歷史最佳pi和pg;

5)使用充分大(小)適應(yīng)度函數(shù)值的方法，通過比較每個(gè)值，選擇新的最佳;

6)根據(jù)下式:

以此來對粒子速度和位置進(jìn)行更新，如果出現(xiàn)粒子的某一維超過邊界的情況，則需要重新隨機(jī)初始化此維數(shù)據(jù);

7)對上述目前粒子群中的非劣解進(jìn)行篩選，將其加入精英集中，并從中剔除精英合集中的劣解;

8)檢驗(yàn)得出的結(jié)果能否滿足終止的條件，滿足則退出，不滿足就得返回步驟2)重新進(jìn)行計(jì)算.

PSO算法解決多目標(biāo)約束優(yōu)化問題的時(shí)候，重點(diǎn)需要解決的問題是群體和自身最佳位置，最佳位置的選擇必須滿足:算法收斂速度好;所得解在Pareto邊界上要存在一定的分散性［14］.在對自身位置進(jìn)行選擇時(shí)，要求是能通過較少的比較次數(shù)就能得到非劣解的更新結(jié)果.PSO算法在處理約束問題時(shí)，正常使用懲罰函數(shù)法，利用這種方法來作為粒子適值，從而PSO能夠解決多目標(biāo)約束化的問題.約束化處理的是等式和不等式或單個(gè)約束構(gòu)成的優(yōu)化問題.這種問題的解要求要符合約束條件同時(shí)也要達(dá)到目標(biāo)函數(shù)的要求.

要說明的是，dominate.m是mo_pso.m調(diào)用的程序，用以判斷一個(gè)解是否優(yōu)于另一個(gè)，是否為非劣最優(yōu)的.最終所要達(dá)到的目標(biāo)是得到最終精英集，即為PSO算法所得非劣解集.

3 算法的優(yōu)化性能分析

算法的時(shí)間復(fù)雜度分析是衡量一個(gè)算法的重要指標(biāo)，通過分析算法的運(yùn)行時(shí)間來比較算法的優(yōu)劣性，選擇2個(gè)有代表性的多目標(biāo)檢測函數(shù)來衡量算法的性能.為檢驗(yàn)算法的性能，對標(biāo)準(zhǔn)測試函數(shù)進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)的結(jié)果得到用于解決這些多目標(biāo)問題的運(yùn)行結(jié)果，其非劣最優(yōu)解的前沿圖例.如下式:

在式(4)的PSO公式中，參數(shù)設(shè)置如下:慣性權(quán)重w從0.5線性遞減到0.4，加速度系數(shù)c1、c2均為0.5.函數(shù)1:

函數(shù)2:

本文用3種算法對函數(shù)1和函數(shù)2連續(xù)運(yùn)行10次所得函數(shù)全局最小值的平均值和運(yùn)行時(shí)間進(jìn)行比較.為了更好地評價(jià)算法的收斂性能，測試結(jié)果如圖2～3所示，從中可以看出算法收斂速度的快慢.

從圖2～3可明顯地看出，相對于WAPSO算法和PSMCO算法，WAPSMCO算法以更少的迭代次數(shù)得到精度更高的解，并且此算法的收斂速度是非?？斓?經(jīng)過上述兩個(gè)標(biāo)準(zhǔn)測試函數(shù)數(shù)值模擬實(shí)驗(yàn)，可以輕易看出WAPSMCO算法優(yōu)于其它兩種算法.

4 實(shí)例應(yīng)用

以山西某煤礦火災(zāi)救援項(xiàng)目為例，煤礦通風(fēng)系統(tǒng)節(jié)點(diǎn)編號示意圖見圖4.導(dǎo)入該井下巷道的地理信息數(shù)據(jù)之后，假定火災(zāi)發(fā)生在(14，15)之間的巷道上，節(jié)點(diǎn)14為源節(jié)點(diǎn)，救援人員出發(fā)地點(diǎn)為節(jié)點(diǎn)1，將源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)之間的巷道交通網(wǎng)定義為一張網(wǎng)絡(luò)圖，路段即為圖的邊，路段之間的交點(diǎn)為圖的節(jié)點(diǎn)，網(wǎng)絡(luò)圖節(jié)點(diǎn)的總數(shù)代表圖的規(guī)模.將巷道的當(dāng)量長度(L當(dāng))、呼吸耗氧量及風(fēng)險(xiǎn)作為邊的3個(gè)權(quán)重，為各個(gè)邊賦予相應(yīng)的權(quán)重值，分別采用經(jīng)典粒子群算法和本文的WAPSMCO算法尋找節(jié)點(diǎn)l至節(jié)點(diǎn)14之間的多目標(biāo)最佳救援路線，輸入?yún)?shù)及對比結(jié)果分別見表1、表2.

表1 初始輸入數(shù)據(jù)(部分)Tab.1Initial input data(part)

表2 不同算法優(yōu)化結(jié)果Tab.2Optimized results of different algorithms

從表2可以看出，利用本文的WAPSMCO優(yōu)化模型及算法求得的最優(yōu)路徑既能滿足耗氧量和風(fēng)險(xiǎn)的限制，還能在滿足限制條件的路線中找到當(dāng)量度最短的路徑.利用該路徑采取救援行動，既能最大限度地保障救援人員的安全，又能使其以較快速度到達(dá)受災(zāi)地點(diǎn)輔助井下人員撤離，從而達(dá)到最大限度地降低人員傷亡的目的.

值得指出的是，本文提出的WAPSMCO算法有利于事故發(fā)生后的應(yīng)急救援決策者進(jìn)行決策，選擇最佳救援路線.在主要優(yōu)化目標(biāo)和次要優(yōu)化目標(biāo)的限定值已知的情況下，決策者在建立模型和做出決策時(shí)可以運(yùn)用這個(gè)算法求出符合要求的最佳救援路線;與此同時(shí)，在多個(gè)目標(biāo)優(yōu)化的時(shí)候，當(dāng)其中有一個(gè)優(yōu)化目標(biāo)的限定值未知時(shí)，可以根據(jù)目標(biāo)函數(shù)的變化曲線，設(shè)定不同的限值，制定出不同的最優(yōu)救援路線.

5 結(jié)語

1)提出一種基于加權(quán)聚合的最小中心粒子群算法，改進(jìn)粒子群優(yōu)化算法的搜索范圍和目標(biāo)權(quán)重.

2)仿真實(shí)驗(yàn)結(jié)果表明采用此算法在典型的標(biāo)準(zhǔn)函數(shù)測試中訓(xùn)練速度快、精度高，對其優(yōu)化性能進(jìn)行測試和分析，可知該方法有利于避免早熟收斂，增強(qiáng)全局搜索能力，同時(shí)提高非劣最優(yōu)解的精度.

3)應(yīng)用基于加權(quán)聚合的最小中心粒子群算法建立礦井火災(zāi)救援路線模型，并與經(jīng)典的粒子群算法進(jìn)行對比，證明該算法具有較高的求解效率，而且能同時(shí)兼顧多個(gè)優(yōu)化目標(biāo).應(yīng)急救援多目標(biāo)優(yōu)化方案的確定對于礦井災(zāi)害救援預(yù)案的決策具有重要的意義.

［1］徐新華.煤礦自燃火災(zāi)防滅火技術(shù)分析［J］.山西焦煤科技，2016，34(7):16－17.

［2］武爽，季經(jīng)緯，趙平，等.基于數(shù)值模擬的礦井火災(zāi)救援路徑選取研究［J］.中國煤炭，2011(10):89－92.

［3］樊雯婧.井下火災(zāi)多救護(hù)隊(duì)救援路徑優(yōu)化的群智能算法研究［D］.西安:西安建筑科技大學(xué)，2014.

［4］賈進(jìn)章.礦井火災(zāi)仿真與避災(zāi)路線的數(shù)學(xué)模型［J］.自然災(zāi)害學(xué)報(bào)，2008，17(1):163－168.

［5］蓋文妹，鄧云峰，李競，等.礦井火災(zāi)最佳救災(zāi)路線優(yōu)化模型及算法［C/OL］//International Symposium on Coal Mining＆Safety.2013:216－221.http://d.g.wanfangdata.com.cn/Conference_WFHYXW577295.aspx.

［6］陳仁文，朱霞，徐棟霞，等.基于改進(jìn)型粒子群算法的卡箍直徑檢測算法研究［J］.儀器儀表學(xué)報(bào)，2014(8):1 837－1 843.

［7］朱童，李小凡，魯明文.位置加權(quán)的改進(jìn)粒子群算法［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47(5):4－6.

［8］鄭波，樓旭陽，崔寶同.基于位置加權(quán)粒子群算法的WSNS能量優(yōu)化［J］.江南大學(xué)學(xué)報(bào)(自然科學(xué)版)，2014(5):568－571.

［9］吳正科，楊青真，施永強(qiáng)，等.帶粒子釋放和速度限制的粒子群算法［J］.計(jì)算機(jī)應(yīng)用研究，2013，30(3):682－685.

［10］ALFI A.Particle swarm optimization algorithm with dynamic inertia weight for online parameter identification applied to Lorenz chaotic system［J］.International Journal of Innovative Computing，Information and Control，2012，8(2):1 191－1 203.

［11］李朔楓，李太勇.一種基于距離的自適應(yīng)模糊粒子群優(yōu)化算法［J］.計(jì)算機(jī)科學(xué)，2011，38(8):257－259.

［12］闞超豪.多向?qū)W習(xí)自適應(yīng)的粒子群算法［J］.計(jì)算機(jī)工程與應(yīng)用，2013，49(6):23－28.

［13］GUTIERREZ A L，LANZA M，BARRIUSO I，et al.Comparison of different pso initialization techniques for high dimensional search space problems:a test with FSS and antenna arrays［C］//Proceedings of the 5th European Conference on Antennas and Propagation(EUCAP).Rome:IEEE，2011:965－969.

［14］ZHU Z L，LIN S，CUI K，et al.Network topology layout algorithm based on community detection of complex networks［J］.Journal of Computer－Aided Design and Computer Graphics，2011，23(11):1 808－1 815.

(責(zé)任編輯:蔣培玉)

Mine fire rescue based on weighted aggregation particle swarm optimization

HUANG Ping1，LI Binglei2
(1.College of Environment and Resources，F(xiàn)uzhou University，F(xiàn)uzhou，F(xiàn)ujian 350116，China; 2.College of Zijin Mining，F(xiàn)uzhou University，F(xiàn)uzhou，F(xiàn)ujian 350116，China)

This paper presents a minimum center particle swarm optimization based on the weighted aggregation，which improves the hunting zone and goal weight of particle swarm optimization algorithm.The simulation results show that this algorithm has fast speed and high precision in typical standard function test training.Its performance in the mine fire rescue optimization route model is tested and analyzed.It was found that the method helps to avoid premature convergence，and enhance the global search capability，while increasing the accuracy of Pareto optimal solution，which can provide important technical support for mine fire accident rescue decisions.

mine;fire rescue;weighted aggregation;minimum center;particle swarm optimization

X913.1

A

10.7631/issn.1000－2243.2016.06.0868

1000－2243(2016)06－0868－06

2016－06－06

黃萍(1986－)，講師，主要從事安全管理、安全工程技術(shù)等研究，pinghuang@fzu.edu.cn

國家自然科學(xué)基金資助項(xiàng)目(51604082)