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

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

1引言

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

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

2聚類(lèi)融合混合粒子群算法

2.1聚類(lèi)分析

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

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

 2.2 加入交叉變異控制算子

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

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

2.3自適應調整加速系數和慣性權重

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

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

2.4 適應度函數的選擇

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

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

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

2.5 具體步驟

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

2) 計算適應度值。根據公式（4）及（5）更新每個(gè)粒子的適應度值。

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

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

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

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

3 結果分析

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

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

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

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

4 結論

本文提出基于聚類(lèi)融合交叉粒子群算法的路徑規劃方案，通過(guò)引入聚類(lèi)分析的思想和遺傳算法中的交叉、變異算子到傳統粒子群算法中，避免了粒子群算法在復雜環(huán)境下容易出現停滯現象。通過(guò)對比仿真實(shí)驗可以看出，選擇適合復雜地圖模型的聚類(lèi)數目，在增加粒子多樣性的同時(shí)，可以加快收斂速度，搜索出的路徑明顯優(yōu)于傳統粒子群算法和交叉粒子群算法。通過(guò)模擬在幼兒活動(dòng)場(chǎng)所內發(fā)生火災后，利用基于聚類(lèi)融合交叉粒子群算法規劃火場(chǎng)逃生路徑是安全可行的，該算法既能保證避開(kāi)障礙物，也可以實(shí)時(shí)動(dòng)態(tài)避開(kāi)危險區域，并且在此前提下迅速規劃出最短的逃生路線(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混合算法時(shí)間優(yōu)化的旅行商問(wèn)題研究[J].計算機應用研究，2015，32（12）：3613-3617.

[5]馮輝, 劉夢(mèng)佳, 徐海祥. 基于A(yíng)HPSO算法的無(wú)人艇多目標路徑規劃[J]. 華中科技大學(xué)學(xué)報(自然科學(xué)版), 2018(6).

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

[7]李紅亞, 彭昱忠, 鄧楚燕. GA與PSO的混合研究綜述[J]. 計算機工程與應用, 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］．微電子學(xué)與計算機，2005,22（6）：98－100.）