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

關鍵詞：消防；粒子群算法； 路徑規劃； 適應度

1引言

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

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

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

2.1聚類分析

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

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

 2.2 加入交叉變異控制算子

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

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

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

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

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

2.4 適應度函數的選擇

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

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

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

2.5 具體步驟

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

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

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

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

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

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

3 結果分析

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

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

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

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

4 結論

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

參考文獻

[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混合算法時間優化的旅行商問題研究[J].計算機應用研究，2015，32（12）：3613-3617.

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

[6]高鷹, 謝勝利, 許若寧. 基于聚類的多子群粒子群優化算法[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］．微電子學與計算機，2005,22（6）：98－100.）