摘要：快速有效的應(yīng)急疏散是保障火災(zāi)現(xiàn)場被困人員逃生和救援人員撤離的重要環(huán)節(jié)，合理的火場路徑規(guī)劃能有效地幫助火場被困人員實現(xiàn)安全逃生。本文針對火災(zāi)現(xiàn)場的疏散路徑規(guī)劃問題，提出了基于聚類融合交叉粒子群算法的疏散路徑規(guī)劃分析模型?；诰垲惾诤辖徊媪Ｗ尤核惴?，在不同柵格大小和復(fù)雜地形條件下，聚類融合交叉粒子群算法通過增強(qiáng)粒子的探索能力增加了粒子多樣性，快速有效地規(guī)劃出相應(yīng)的最優(yōu)疏散路徑，使人員在火場緊急情況下安全快速地到達(dá)出口，提高疏散效率，減少人員傷亡。仿真結(jié)果驗證該算法的可行性和有效性。

關(guān)鍵詞：消防；粒子群算法； 路徑規(guī)劃； 適應(yīng)度

1引言

    近年來，隨著經(jīng)濟(jì)社會迅速發(fā)展,幼小活動場所或少兒教育機(jī)構(gòu)大量出現(xiàn)，這些地方聚集大量兒童，場所內(nèi)部部局復(fù)雜、功能多樣、空間大、可燃物多，一旦發(fā)生火災(zāi)造成的人員傷亡、經(jīng)濟(jì)損失和社會影響將極為嚴(yán)重。尤其在多障礙物的幼小活動場所，由于場所障礙物不規(guī)則，人員年齡小、消防安全常識欠缺，所以一旦發(fā)生火災(zāi)，逃生極為困難。粒子群算法（PSO）是模擬鳥類飛行的一種優(yōu)化算法，根據(jù)粒子群算法對建筑空間進(jìn)行網(wǎng)格模型劃分，定義和描述建筑空間各網(wǎng)格的靜態(tài)屬性，利用粒子群算法尋找最優(yōu)路徑是可行的一種方法。

    本文嘗試將聚類算法和遺傳算子加入到粒子群算法中，以此來實現(xiàn)在稀疏仿真地圖中的路徑尋優(yōu)。引入基于劃分的聚類方法中的Kmeans算法，根據(jù)粒子的適應(yīng)度進(jìn)行聚類，把粒子劃分為若干個粒子子群，便于粒子在保存群體極值時，更多數(shù)目的適應(yīng)度較好粒子信息傳遞到下一代粒子中，有效提高了算法的尋優(yōu)速度。對每個子群采用一定規(guī)則的交叉和變異算子，從而提高粒子群算法的種群多樣性。在每個子區(qū)內(nèi)更新粒子速度和位置時，隨著代數(shù)的增加改變慣性權(quán)重和加速系數(shù)，避免了早熟的現(xiàn)象。最后通過仿真驗證了該算法的有效性，實驗結(jié)果表明，算法加快了收斂速度，防止局部最優(yōu)的問題產(chǎn)生，使火場被困人員在復(fù)雜的環(huán)境中，能快速找到最滿意的路徑。

2聚類融合混合粒子群算法

2.1聚類分析

    為了加強(qiáng)粒子之間信息交流，使粒子群算法收斂性好，將初始種群中的粒子根據(jù)聚類方法中的Kmeans算法分為若干個子種群，由每個子種群的最優(yōu)粒子以及個體最優(yōu)粒子的速度和位置信息指導(dǎo)下一代粒子更新進(jìn)行速度和位置值。這樣處理方式加強(qiáng)粒子的信息交換，從之前只有兩個極值保留下來到現(xiàn)在有若干個極值保存下來，增加了粒子的多樣性和信息傳遞，進(jìn)而避免了局部最優(yōu)的情況發(fā)生，利用粒子之間在迭代過程中的信息更新，加快收斂速度。

 每個粒子至今為止搜索到的最優(yōu)位置P1(1)(i=1,2,...,N)每個聚類區(qū)C1(i=1,2,...,K)粒子至今為止搜索到的最優(yōu)位置q1(i=1,2,...,K)

 2.2 加入交叉變異控制算子

 將遺傳算子加入到粒子群優(yōu)化過程中，已有很多研究成果。李紅亞學(xué)者對研究成果進(jìn)行了細(xì)致的分類和研究，無論是哪一種融合，遺傳算子都能起到解決粒子群陷入局部最優(yōu)值出現(xiàn)早熟、種群多樣性差、搜索范圍小等缺點，使得兩種算法在性能上克服局限，再實現(xiàn)優(yōu)勢互補(bǔ)^[7]。本文將交叉算子和變異算子加入到粒子群算法路徑規(guī)劃過程中，在迭代過程中，對適應(yīng)度進(jìn)行排序，令前x%的粒子直接遺傳到下一代，后（100-X）%的粒子進(jìn)行交叉變異操作，通過變換X的值，調(diào)整算法的延展性。

 將粒子與父代中同一聚類的群體極值進(jìn)行交叉操作，使交叉后的粒子具有群體極值的優(yōu)勢；對適應(yīng)度相對不好的粒子進(jìn)行變異操作，使變異后的粒子能夠保持多樣性，跳出局部最優(yōu)。

2.3自適應(yīng)調(diào)整加速系數(shù)和慣性權(quán)重

粒子群迭代過程中，早期希望粒子有較強(qiáng)的自我學(xué)習(xí)能力，較低的社會學(xué)習(xí)能力，這樣保持粒子的多樣性，在晚期希望粒子有較低的自我學(xué)習(xí)能力，較強(qiáng)的社會學(xué)習(xí)能力，這樣使粒子能收斂于全局最優(yōu)。為此，對傳統(tǒng)的粒子群加速系數(shù)進(jìn)行改進(jìn)，具體為：

    其中，C1max和C1min為加速系數(shù)C1的上下限。C2max和C2min為加速系數(shù)C2的上下限。tmax是迭代的最大次數(shù)。t是當(dāng)前迭代次數(shù)。

2.4 適應(yīng)度函數(shù)的選擇

在設(shè)計路徑時，要綜合考慮路徑的長短和是否成功避開障礙物，所以本文選擇的適應(yīng)度函數(shù)如下：

   其中N表示路徑段數(shù)，n記錄了與障礙物相交的路徑段數(shù)目，D表示路徑的長度。

   （xs，ys），（xf，yf）分別代表路徑起始點與終點坐標(biāo)。此設(shè)計將兩個因素綜合在一個函數(shù)中，實現(xiàn)了量化的統(tǒng)一。路徑長度越小，與障礙相交次數(shù)越少，則適應(yīng)度函數(shù)值越大。

2.5 具體步驟

1) 初始化參數(shù)。設(shè)置所需規(guī)劃地圖信息、起始點、終止、改進(jìn)算法的各種參數(shù)、粒子群的規(guī)模（N）、初始速度、聚類數(shù)目(k），交叉及變異概率。

2) 計算適應(yīng)度值。根據(jù)公式（4）及（5）更新每個粒子的適應(yīng)度值。

3) Kmeans算法對粒子分區(qū)。對N只粒子的適應(yīng)度值進(jìn)行排序，根據(jù)適應(yīng)度排序結(jié)果運用Kmeans算法分析把粒子分為k個聚類區(qū)，即W1(i=1,2,...,K)。

4) 對個體極值和群體極值進(jìn)行更新。對分區(qū)后的粒子更新適應(yīng)度值，個體極值為當(dāng)前粒子迄今為止搜索到的最優(yōu)位置P1(1)(i=1,2,...,K)，即適應(yīng)度最大時候粒子所在位置，個體極值對于每個粒子是唯一的，一共有N個。群體極值為每個聚類區(qū)W1(i=1,2,...,K）中的所有粒子迄今為止歷史搜索到的適應(yīng)度值最大的位置q1W1(i=1,2,...,K）群體極值一共有K個。

5) 速度和位置的更新。使用公式（3）更新自適應(yīng)學(xué)習(xí)因子C1(j=1,2,...,K）。

6) 若迭代次數(shù)達(dá)到設(shè)定值則停止程序運行，輸出全局最優(yōu)解，否則循環(huán)(4) (5)。

3 結(jié)果分析

 在Inte(R) Core(TM) i5-4200U CPU，1.60GHz，4GB內(nèi)存，MATLAB R2014a環(huán)境下對算法進(jìn)行仿真實驗。為了驗證本文采用的對適應(yīng)度Kmeans聚類分析方法和交叉、變異算子的有效性，在相同運行環(huán)境下分別用傳統(tǒng)粒子群算法、具有交叉、變異算子的粒子群算法和聚類融合交叉粒子群算法進(jìn)行了對比模擬仿真實驗。

 圖3至圖8分別給出了采用傳統(tǒng)粒子群算法、帶有交叉、變異算子的粒子群算法和本文聚類融合交叉粒子群算法的最優(yōu)路徑圖。從圖中容易看出，傳統(tǒng)粒子群優(yōu)化算法在相同迭代次數(shù)下走出的路徑效果最差，雖然找出一條不和障礙物重疊的路線，但是粒子路線跳躍起伏較大，帶來的耗能隨之增大，明顯是一條局部最優(yōu)路徑。圖4和圖7是在傳統(tǒng)粒子群中加入交叉、變異算子后的結(jié)果，可以看出減少了一些冗余路線，效果雖然有所改進(jìn)，但是耗費時間長，一些區(qū)域還存在可以優(yōu)化的可能性。而在交叉粒子群基礎(chǔ)上加入Kmeans聚類分析的本文改進(jìn)算法（圖5，圖8）得到的最優(yōu)路徑精度相對較高，在相同運行代數(shù)下，路徑長度明顯最短，路線較為順滑，相對而言降低了拐點數(shù)和無效路徑段，實際過程中可以達(dá)到節(jié)省被困人員體能消耗、縮短疏散時間的效果。

 為了更直觀看出加入聚類算法的優(yōu)勢，本文對交叉粒子群算法和聚類融合交叉粒子群算法收斂情況進(jìn)行比較，結(jié)果如圖9所示（粒子數(shù)為3000，迭代次數(shù)為10000，聚類數(shù)為10）。

 對比結(jié)果可以看出，粒子群算法加入交叉、變異算子可以改變傳統(tǒng)粒子群的最大的缺陷，即容易陷入早熟現(xiàn)象，增加種群多樣性，但是計算量會隨之加大，收斂代數(shù)也會成指數(shù)上升，針對這個缺陷，加入Kmeans聚類分析算法，能夠使收斂代數(shù)穩(wěn)定下降，加快收斂速度，使得總計算時間也大大縮短，對于智能路徑尋優(yōu)有很好的效果。

4 結(jié)論

本文提出基于聚類融合交叉粒子群算法的路徑規(guī)劃方案，通過引入聚類分析的思想和遺傳算法中的交叉、變異算子到傳統(tǒng)粒子群算法中，避免了粒子群算法在復(fù)雜環(huán)境下容易出現(xiàn)停滯現(xiàn)象。通過對比仿真實驗可以看出，選擇適合復(fù)雜地圖模型的聚類數(shù)目，在增加粒子多樣性的同時，可以加快收斂速度，搜索出的路徑明顯優(yōu)于傳統(tǒng)粒子群算法和交叉粒子群算法。通過模擬在幼兒活動場所內(nèi)發(fā)生火災(zāi)后，利用基于聚類融合交叉粒子群算法規(guī)劃火場逃生路徑是安全可行的，該算法既能保證避開障礙物，也可以實時動態(tài)避開危險區(qū)域，并且在此前提下迅速規(guī)劃出最短的逃生路線。

參考文獻(xiàn)

[1]Kubota K , Inoue K , Hashimoto R , et al. Development and Investigation of Efficient GA/PSO-Hybrid Algorithm Applicable to Real-World Design Optimization. Eleventh Conference on Congress on Evolutionary Computation. IEEE Press, 2009.

[2] A. Mohammadi, and M. Jazaeri. A Hybrid Particle Swarm Optimization-Genetic Algorithm for Optimal Location of SVC Devices in Power System Planning. In Proceedings of the 42nd International Universities Power Engineering Conference, pp. 1175 – 1181, 2007.

[3] A. A. A. Esmin, G. Lambert-Torres, and G. B. Alvarenga. Hybrid Evolutionary Algorithm Based on PSO and GA mutation. In Proceedings of the 6th International Conference on Hybrid Intelligent Systems, 2006.

[4] 張勇，陳玲，徐小龍，等.基于PSO-GA混合算法時間優(yōu)化的旅行商問題研究[J].計算機(jī)應(yīng)用研究，2015，32（12）：3613-3617.

[5]馮輝, 劉夢佳, 徐海祥. 基于AHPSO算法的無人艇多目標(biāo)路徑規(guī)劃[J]. 華中科技大學(xué)學(xué)報(自然科學(xué)版), 2018(6).

[6]高鷹, 謝勝利, 許若寧. 基于聚類的多子群粒子群優(yōu)化算法[J]. 計算機(jī)應(yīng)用研究, 2006, 23(4):40-41.

[7]李紅亞, 彭昱忠, 鄧楚燕. GA與PSO的混合研究綜述[J]. 計算機(jī)工程與應(yīng)用, 2018(2):20-28.

[8] YU H, LI X. Fast path planning of robot based on grid method [J]. Microelectronics and Computer，2005，22（6）：98－100．（于紅斌 李孝安．基于柵格法的機(jī)器人快速路徑規(guī)劃［J］．微電子學(xué)與計算機(jī)，2005,22（6）：98－100.）