黃萍，李兵磊

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

基于加權聚合粒子群算法的礦井火災救援研究

黃萍1，李兵磊2

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

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

礦井;火災救援;加權聚合;最小中心;粒子群算法

0 引言

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

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

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

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

1 粒子群算法的改進

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

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

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

具體的算法過程如下:

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

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

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

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

2 算法流程

2.1 初始化

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

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

2.2 域約束

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

2.3 設置粒子的位置和速度

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

2.4 主程序

1)對粒子群進行初始化，設種群大小為N，隨機賦予每個粒子初始值為xi，vi;

2)對各個子目標函數(shù)的值進行計算;

3)計算粒子適應度，采用加入懲罰函數(shù)的目標函數(shù)方法計算;

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

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

6)根據(jù)下式:

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

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

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

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

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

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

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

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

函數(shù)2:

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

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

4 實例應用

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

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

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

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

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

5 結語

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

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

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

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

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

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

［4］賈進章.礦井火災仿真與避災路線的數(shù)學模型［J］.自然災害學報，2008，17(1):163－168.

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

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

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

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

［9］吳正科，楊青真，施永強，等.帶粒子釋放和速度限制的粒子群算法［J］.計算機應用研究，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ōu)化算法［J］.計算機科學，2011，38(8):257－259.

［12］闞超豪.多向?qū)W習自適應的粒子群算法［J］.計算機工程與應用，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.

(責任編輯:蔣培玉)

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－)，講師，主要從事安全管理、安全工程技術等研究，pinghuang@fzu.edu.cn

國家自然科學基金資助項目(51604082)