電話(huà):029-86167617 029-86167591 傳真:029-86167617 郵編:710018 郵箱:sxsxfxh@163.com
摘要:快速有效的應急疏散是保障火災現場(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.)