粒子群蟻群融合算法的火災(zāi)救援路徑研究

李怡弘，裘 炅

(杭州電子科技大學(xué) 計算機學(xué)院，浙江 杭州 310018)

粒子群蟻群融合算法的火災(zāi)救援路徑研究

李怡弘，裘 炅

(杭州電子科技大學(xué) 計算機學(xué)院，浙江 杭州 310018)

為獲取最優(yōu)的救援路徑，以提高救援的有效性和實時性，文中提出了一種粒子群蟻群融合算法。該算法在分析影響路徑選擇因素的基礎(chǔ)上，運用模糊數(shù)學(xué)中的層次分析法評定了道路的權(quán)重，建立了消防滅火救援模型；使用粒子群算法快速獲取次優(yōu)解，將此次優(yōu)解作為蟻群算法的初始信息素增量，并將求解出各段路徑權(quán)重矩陣引入到優(yōu)化后的蟻群算法狀態(tài)轉(zhuǎn)移概率的求解模型中來，再利用這種改進后的狀態(tài)轉(zhuǎn)移規(guī)則，且考慮行車速度時變性的基礎(chǔ)上求解出模型的最優(yōu)解。實驗結(jié)果表明，該方法可以完成最佳救援路徑的規(guī)劃。

粒子群算法；蟻群算法；融合算法；優(yōu)化；救援路徑

火災(zāi)危害嚴(yán)重，且隨著社會經(jīng)濟的發(fā)展，火災(zāi)事故發(fā)生概率遞增，嚴(yán)重的威脅著公共安全和人們的生命財產(chǎn)安全[1]。當(dāng)火災(zāi)發(fā)生時，救援時間是影響火災(zāi)救援工作的關(guān)鍵因素[2]，而消防車輛到達(dá)現(xiàn)場所需時間與其所選擇的路徑是有緊密聯(lián)系的。因此，如何合理規(guī)劃救援路徑就顯得尤為重要。目前，常用的路徑規(guī)劃方法有：蟻群算法、遺傳算法、神經(jīng)網(wǎng)絡(luò)算法、粒子群算法等智能仿生法[3]。不同的路徑規(guī)劃方法有著各自的優(yōu)缺點：遺傳算法全局搜索能力強，但算法容易“早熟”，陷入局部最優(yōu)，且算法編程實現(xiàn)比較復(fù)雜，搜索時間較慢[4]；神經(jīng)網(wǎng)絡(luò)法具有高度的并行性，收斂速度快，但是其求解速度慢且在求解過程中需要非常詳盡的數(shù)據(jù)才能實現(xiàn)路徑規(guī)劃[5]；蟻群算法是一種全局啟發(fā)式的算法，具有良好的信息反饋機制，可以分布式并行計算，且啟發(fā)式搜索能力較強，但是由于初始信息素匱乏，使得初期運算速度慢[6]；粒子群算法概念簡單、易于實現(xiàn)，需調(diào)整參數(shù)較少，初期收斂速度快，具有較強的全局搜索能力，但后期局部搜索能力差，易陷入局部最優(yōu)[7]。

基于上述描述，本文提出將粒子群蟻群融合算法作為火災(zāi)救援路徑規(guī)劃的求解算法。融合算法結(jié)合粒子群算法初期易收斂、搜索速度快和蟻群算法搜索精度高的優(yōu)勢，從算法的效率和求解質(zhì)量上都有了很大的提高。針對實時的交通路況，本文引入道路權(quán)重的概念，根據(jù)路程距離長度、道路交通量、道路路面狀況和天氣狀況四個因素[8]采用層次分析法獲取各個路段的權(quán)重，將此作為融合算法中路徑選擇的依據(jù)。最終算法結(jié)合火災(zāi)發(fā)生時刻各段道路的實時行車速度，找到一條時效性最高的滅火救援路徑。本文充分考慮了在火災(zāi)發(fā)生時刻影響消防車輛調(diào)度的一些客觀因素，并在算法求解時結(jié)合調(diào)度高時效性的特性。因此，該方案具有一定的現(xiàn)實參考意義。

1 相關(guān)問題概述及模型建立

1.1 基于層次分析法的道路權(quán)重評定

本文采用定性與定量相結(jié)合的層次分析法AHP(Analytic Hierarchy Process)來確定各個影響因子的權(quán)重。首先將交通流量、路徑距離、道路等級、天氣狀況作為路段權(quán)值的4個影響因子，結(jié)合AHP原理構(gòu)造一個2層結(jié)構(gòu)：目標(biāo)層Z和準(zhǔn)則層A。如圖1所示，Z層的權(quán)重用W表示，A層的權(quán)重分別用w1,w2,w3,w4表示。

圖1 路段權(quán)重因子模型

然后根據(jù)文獻(xiàn)[9]以及AHP計算步驟可計算得出各個影響因子的權(quán)重即w1,w2,w3,w4的值為W=(0.5848 0.1320 0.1320 0.1513)。

1.2 數(shù)學(xué)模型建立

1.2.1 基本假設(shè)

(1)已知消防站點(消防車輛出發(fā)點)和火災(zāi)現(xiàn)場的具體位置；

(2)對于消防車輛，在消防站(車輛起始點)出發(fā)時無停頓時間，即消防車輛充足，接到調(diào)度指令立即出發(fā)；

(3)本文討論的火災(zāi)救援只討論從單一起點(消防站點)到單一目的地(火災(zāi)現(xiàn)場)問題；

(4)消防車輛在行駛過程中，整個區(qū)域內(nèi)的設(shè)施固定，即建筑物位置、大小，道路位置等保持不變；

(5)本文不考慮從接到火災(zāi)報警到調(diào)動消防人員的過程；

(6)行駛速度不考慮車輛行駛的方向，即正向和反向是一致的；

(7)在已經(jīng)劃分好的時間段內(nèi)，消防車輛的在設(shè)定的路段內(nèi)速度不變。

1.2.2 建立數(shù)學(xué)模型

本文研究的目標(biāo)是：如何在火災(zāi)發(fā)生后以時間為優(yōu)化目標(biāo)找到一條從消防站點到達(dá)火災(zāi)現(xiàn)場的最優(yōu)路徑。假設(shè)有向圖G(V,E)，V代表有向圖G中路徑上的節(jié)點集，即V={v1,v2,…,vn}，v1,v2,…,vn代表了G中的建筑物，本文規(guī)定，v1代表消防站點，vn代表火災(zāi)現(xiàn)場；E代表有向圖G中節(jié)點之間的路徑集，E?V×V表示可行路徑總和，設(shè)置R為v1到vn的所有可行路徑總和，R∈E；P為其中的某一條路徑，P∈R；(vi,vj)∈E代表從節(jié)點i到節(jié)點j之間的路程，e(vi,vj)=ωij代表節(jié)點i到節(jié)點j之間的權(quán)值。ωij的計算可結(jié)合上一節(jié)AHP中各個影響因子權(quán)值的評定，得到

ωij=tij+sij/(vij×ω1)(ω2×rij+ω3×fij+ω4×wij)

(1)

其中，w1,w2,w3,w4為AHP中獲得的各因素的權(quán)重系數(shù)；sij代表vi到vj之間的距離；vij代表v1到vn之間的平均速度；r、f、w分別代表道路等級、交通流量和天氣因子。tij表示從vi到vj之間所需的時間。由于不同時間內(nèi)通過某一路段的速度不一樣，為了更加準(zhǔn)確貼近實際情況，增加算法可靠性，本文以天為劃分的粒度，將一天24 h分為幾個時間段來分別表示當(dāng)前時段內(nèi)的速度情況：T0

其中，lij代表v1到vn距離的長度。

設(shè)ω(P)為v1到vn所有路段的權(quán)值總和，即有

ω(P)=∑ωiji,j∈(1,…,n)

(2)

因此，要求找到一條從消防站v1到火災(zāi)現(xiàn)場vn的路徑使得式(3)成立

(3)

道路的權(quán)值越小，救援時間就越短，圖2為救援路徑規(guī)劃模型。

圖2 救援路徑規(guī)劃模型圖

2 相關(guān)算法概述

2.1 粒子群優(yōu)化算法基本原理

粒子群優(yōu)化算法[10](Particle Swarm Optimization，PSO)首先初始化一群隨機粒子，然后通過多次循環(huán)迭代搜索到最優(yōu)粒子。在每次迭代過程中，粒子先獲取個體極值pbesti(到目前為止粒子自身搜索到的最優(yōu)位置)和全局極值gbesti(到目前為止粒子群中搜索到的最優(yōu)位置)，然后利用式(4)和式(5)更新每個粒子的速度和位置，從而引導(dǎo)粒子向最優(yōu)解方向移動

(4)

(5)

2.2 蟻群算法基本原理及優(yōu)化

蟻群優(yōu)化算法ACO[11](Ant Colony Optimization)是由意大利學(xué)者Dorigo M提出的一種模仿螞蟻覓食的新興群智能算法。一群螞蟻在尋找食物的過程中，沿途中會釋放一種叫做信息素的化學(xué)物質(zhì)。一條路徑上經(jīng)過的螞蟻越多，該路徑上留下的信息素也越多，其他螞蟻能感知這種信息素并朝信息素較濃的位置移動。信息素越濃的路徑，螞蟻選擇的概率越大，最終螞蟻找到到達(dá)食物的最短路徑。ACO算法用于求解組合優(yōu)化問題時有兩大步驟：路徑構(gòu)建和信息素更新。本文就這兩大步驟分別對算法進行優(yōu)化。

2.2.1 概率選擇機制優(yōu)化策略

在構(gòu)建路徑時，螞蟻利用狀態(tài)轉(zhuǎn)移規(guī)則來選擇下一個節(jié)點[12]?；鞠伻核惴ㄖ形浵佭x擇下一個節(jié)點是依據(jù)四周路徑上信息素的濃度[13]，失去了探索新路徑的可能，因此，本文在原有的概率選擇機制基礎(chǔ)上，新增一種“隨機”方式，這樣不僅能有效避免算法陷入局部最優(yōu)，而且也更加符合螞蟻個體的行為。并且，在此基礎(chǔ)上引入本文中所述的道路權(quán)重概念，得到新的概率選擇機制優(yōu)化策略如式(6)所示

(6)

其中，[ωij]代表路徑i和j之間的權(quán)重；q是在0～1區(qū)間內(nèi)隨機獲取的值；q0和q1都是設(shè)定好的在區(qū)間0～1之間的固定值。文中設(shè)置q0=0.6，q1=0.8。

概率選擇機制優(yōu)化策略的設(shè)計在一定程度上增加了解空間的多樣性，從而提高了螞蟻找到最優(yōu)路徑的概率，而且引入道路權(quán)重后的概率選擇機制將實時道路情況作為路徑選擇的參考指標(biāo)，對算法在合理性和效率上都有一定的優(yōu)化作用。

2.2.2 信息素更新機制

本文提出的信息素更新機制包括兩個方面：動態(tài)局部更新和帶調(diào)節(jié)因子的全局更新。

動態(tài)局部更新：由于ACO算法全局更新信息素機制在螞蟻尋徑過程中具有一定的時延性[14]，因此，本文提出一種新的動態(tài)局部更新機制，該機制打破ACO算法中一次迭代結(jié)束后再更新所有路徑上的信息素的方式，而采用“走一步，更新一次”的策略，更新為式(7)～式(9)。

τij(t+1)=(1-ξ)τij(t)+ξΔτij

(7)

(8)

(9)

在上述公式中：螞蟻數(shù)量為m，Q為常數(shù)；ξ為局部信息素?fù)]發(fā)因子，螞蟻k在迭代中已走過節(jié)點數(shù)為x；螞蟻k在迭代中已走過節(jié)點間距離為dl；Lz為m只螞蟻在迭代中走過的總距離。

動態(tài)局部更新機制保證了若螞蟻經(jīng)過某路徑時信息素時實時更新，為后期螞蟻的搜索提供了一定的指導(dǎo)性，減少了螞蟻的搜索時間，提高了算法性能。

帶調(diào)節(jié)因子的全局更新：傳統(tǒng)ACO算法的全局更新機制無法加快收斂速度從而提高搜索效率[15]。因此，本文提出一種帶調(diào)節(jié)因子的信息素更新機制。首先，螞蟻在完成一次迭代后，對迭代過程中找到的所有路徑根據(jù)路徑長度進行排序，然后將排序得到的中間值作為標(biāo)準(zhǔn)，判斷該路徑是否需要更新信息素。更新信息素公式為

(10)

(11)

(12)

在式(10)～式(12)中，θk為調(diào)節(jié)因子；Lk為所有螞蟻在迭代中走過的總距離；Lmid所有螞蟻在迭代中走過的距離的中間數(shù)值；Lbest為所有螞蟻在迭代中的最優(yōu)路徑長度。

新的全局更新策略的思想是使“優(yōu)的路徑更優(yōu)，差的路徑更差”，迅速將螞蟻集中在較優(yōu)路徑上，加快了算法的收斂速度，減少搜索時間。

3 改進的粒子群蟻群融合算法實現(xiàn)

本文先使用PSO快速找到一條次優(yōu)路徑，并將此次優(yōu)解作為ACO的初始信息素增量，然后根據(jù)式(15)得到ACO的信息素初始分布量，最后采用優(yōu)化后ACO對路徑尋優(yōu)，以此得到最優(yōu)路徑

τs=τc+τp

(13)

在式(15)中，τp為PSO初次尋優(yōu)后得到的解轉(zhuǎn)化為的信息素增加值；τc為融合前的蟻群算法的初始值常量；τs為蟻群算法搜索前的信息素初始值。

圖3 融合算法流程圖

算法實現(xiàn)步驟：

步驟1PSO和 ACO參數(shù)初始化。設(shè)置算法中參數(shù)的初始值，其中令時間t=0；循環(huán)次數(shù)Nc=0；最大循環(huán)次數(shù)設(shè)為NCmax；初始化信息量τij(0)=τ0；

步驟2獲取粒子適應(yīng)度值。根據(jù)適應(yīng)度函數(shù)計算出每個粒子的適應(yīng)度值，并以此為依據(jù)來判斷該粒子是否為當(dāng)前最優(yōu)粒子；

步驟3更新pbest個體極值。將pbest值與每個粒子在步驟2中獲得的個體適應(yīng)度值比較，若粒子的適應(yīng)度值>pbest值，則將該適應(yīng)度值作為最新的pbest值保存，否則，則pbest值保持不變；

步驟4更新gbest全局極值。將gbest值與步驟2中獲得的全局適應(yīng)度值比較，若粒子的適應(yīng)度值大于gbest值，則將該適應(yīng)度值作為最新的gbest值保存，否則，gbest值保持不變；

步驟5更新速度V與位置x。根據(jù)式(4)～式(6)更新每個粒子的速度與位置；

步驟6返回步驟2，繼續(xù)執(zhí)行，直到算法達(dá)到最大迭代次數(shù)或輸出最優(yōu)解，此時執(zhí)行步驟7；

步驟7利用PSO得到的最優(yōu)路徑，根據(jù)式(13)進行ACO的信息素初始化；

步驟8首先設(shè)螞蟻的數(shù)量m，并放置在起始點。然后將這個起始點位加入到最新禁忌表tabu(s)中，其中tabu(s)里存放著螞蟻已經(jīng)過的點位，表示不可行節(jié)點；

步驟9判斷螞蟻的數(shù)量，如果>0，則執(zhí)行步驟10；否則，跳轉(zhuǎn)至步驟15；

步驟10增加螞蟻數(shù)目k=k+1；

步驟11首先獲取下一步可行節(jié)點集，然后根據(jù)公式(8)的狀態(tài)轉(zhuǎn)移規(guī)則來計算每一個可行節(jié)點的概率值，選擇概率最大的節(jié)點，并將此節(jié)點加入到tabu(s)中；

步驟12更新螞蟻數(shù)目；

步驟13判斷螞蟻的狀態(tài)。如果k

步驟14局部更新。只要螞蟻移動一步，即根據(jù)式(7)～式(9)進行局部范圍內(nèi)的信息素更新，并執(zhí)行步驟9；

步驟15全局更新。當(dāng)螞蟻完成一次迭代后，計算本次所有路徑中最優(yōu)解的路徑長度，并根據(jù)式(10)～式(12)更新所有路徑上信息素濃度。與此同時，根據(jù)迭代次數(shù)判斷是否要結(jié)束算法，當(dāng)NC

步驟16得到算法的最優(yōu)解，輸出對應(yīng)路徑，至此，算法結(jié)束。

4 仿真結(jié)果

為了驗證優(yōu)化后粒子群蟻群融合算法的效果，進行了仿真實驗。蟻群參數(shù)分別為m=100，Nmax=50，α=1，β=2，Q=100，揮發(fā)率ρ= 0.1，信息素初始值為10。粒子群的參數(shù)分別為: 粒子數(shù)目30。 最大迭代次數(shù)為50，c1=c2= 2，w=0.9，Vmax=10。

本文使用圖5中的路網(wǎng)圖進行描述。其中，A～R節(jié)點代表建筑物，1～28代表兩節(jié)點之間的可行路徑。假定該區(qū)域只有一個已知位置的消防站點A，當(dāng)?shù)貓D中Q位置發(fā)生火災(zāi)時(假定有且只有該位置發(fā)生火災(zāi))，A點接到火警后，立刻出發(fā)前往火災(zāi)現(xiàn)場。因此，此時的目標(biāo)為：在滿足行車速度時變性的情況下，找到一條用時最少的救援路徑。

圖4 路網(wǎng)圖

為證明不同救援時刻(即路段權(quán)重不同)情況下對救援路徑選取是有一定影響的，假定選擇兩個不同時刻從消防站點出發(fā)。首先，獲取各段道路的權(quán)重，根據(jù)AHP中獲取的路徑距離、交通流量、道路等級、天氣狀況的權(quán)重向量與有關(guān)數(shù)據(jù)(假定該交通網(wǎng)中的所有路徑均為寬柏油路，天氣為晴天)根據(jù)式(1)計算得到每一段路徑的權(quán)重值，圖5為A時刻獲得的權(quán)重值，圖6為B時刻獲得的權(quán)重值。

圖5 路段各個道路權(quán)重值

圖6 路段各個道路權(quán)重值

然后，采用融合算法求解最優(yōu)路徑。將上一步計算得到的上述各個路段的權(quán)重量引入優(yōu)化后粒子群蟻群融合算法作為算法中的螞蟻路徑選擇時的狀態(tài)轉(zhuǎn)移概率，得到實時路況下的最優(yōu)路徑。圖5情況下得到的最優(yōu)路徑為：A-C-H-L-O-Q；用時9.8 min；權(quán)值為47。圖6情況下得到的最優(yōu)路徑為：A-C-H-K-Q；用時11.4 min；權(quán)值為52。以上結(jié)果證明：在不同時刻，由于不同路段的權(quán)重不同而導(dǎo)致所選擇的救援路徑不同，符合實際情況。

5 結(jié)束語

本文研究的重點是解決火災(zāi)救援時如何在行駛速度時變和各種交通實況下，以時間為優(yōu)化目標(biāo)找到一條從消防站點到達(dá)火災(zāi)現(xiàn)場的最優(yōu)路徑，為此提出了行車速度時變條件下消防滅火救援模型，在融合算法基礎(chǔ)上實現(xiàn)了交通實況下火災(zāi)救援路徑規(guī)劃，從而保

證了救援路徑的時效性。主要研究成果如下：(1)改進了蟻群算法。引入實時動態(tài)更新局部信息素與路徑優(yōu)劣排序為依據(jù)更新全局信息素相結(jié)合的方式替代原有的信息素更新機制；在路徑概率選擇機制中引入“隨機”概率以增加算法的全局搜索能力，并且引入AHP中獲得的路徑權(quán)重結(jié)合實時交通速度計算得到的權(quán)值作為概率選擇的依據(jù)；(2)將粒子群算法與優(yōu)化后的蟻群算法融合。融合算法將PSO得到的次優(yōu)解作為ACO的初始信息素分布增量，提高了算法的效率和求解精度。

[1] 傅智敏.我國火災(zāi)統(tǒng)計數(shù)據(jù)分析[J].安全與環(huán)境學(xué)報,2014(6):341-345.

[2] 王江波,茍愛萍.火災(zāi)中高層住宅小區(qū)疏散及救援風(fēng)險分析[J].消防科學(xué)與技術(shù),2015,(01):117-119.

[3] 夏勁松. 基于蟻群粒子群算法融合的移動機器人路徑規(guī)劃研究[D].廣東:廣東工業(yè)大學(xué),2012.

[4] 雷玉梅.基于改進遺傳算法的大規(guī)模TSP問題求解方案[J].計算機與現(xiàn)代化,2015(2):34-37.

[5] 唐禹.一種路徑規(guī)劃問題的蟻群算法研究[D].哈爾濱:哈爾濱工程大學(xué),2013.

[6] Jose B Escario,Juan F Jimenez,Jose M Giron-Sierra.Ant colony extended:experiments on the traveling salesman problem[J].Expert Systems with Applications,2015,42(7):390-410.

[7] 李擎,張超,陳鵬.一種基于粒子群參數(shù)優(yōu)化的改進蟻群算法[J].控制與決策,2013(6):873-878,883.

[8] 談曉勇,林鷹.基于混沌蟻群算法的應(yīng)急救援車輛調(diào)度優(yōu)化[J].計算機應(yīng)用研究,2014(9):2640-2643.

[9] 周東健,張興國,馬海波,等.基于柵格地圖-蟻群算法的機器人最優(yōu)路徑規(guī)劃[J].制造業(yè)自動化,2014(5):1-3,10.

[10] 張萬緒,張向蘭,李瑩.基于改進粒子群算法的智能機器人路徑規(guī)劃[J].計算機應(yīng)用,2014(2):510-513.

[11] Santos L,Coutinho-Rodrigues J,Current J R.An improved ant colony optimization based algorithm for the capacitated arc routing problem[J].Transportation Research Part B:Methodological,2010,44(2):246-266.

[12] 張晨,游曉明.基于柵格模型機器人路徑規(guī)劃的量子蟻群算法[J].電子科技,2016,29(7):1-3,7.

[13] 張興國,周東健,李成浩.基于粒子群-蟻群融合算法的移動機器人路徑優(yōu)化規(guī)劃[J].江西師范大學(xué)學(xué)報:自然科學(xué)版,2014(3):274-277.

[14] 杜博,夏春蕾,戴曙光.融合改進蟻群和粒子群算法的路徑搜索應(yīng)用[J].電子科技,2016,29(9):4-6,135.

[15] 葉仕通,萬智萍.一種基于改進全局信息素更新效率的蟻群算法及仿真[J].計算機應(yīng)用與軟件,2014(1):176-179.

The Particle Swarm Optimization Algorithm Merged with Ant Colony Optimization Algorithm of Fire Rescue Way Research

LI Yihong，QIU Jiong

(School of Computer Science,Hangzhou Dianzi University,Hangzhou 310018,China)

To obtain the optimal relief path, improve the effectiveness of the rescue and the real time,so a particle swarm ant colony fusion algorithm is put forward. The major thinking of the optimization is that on the basis of analyzing the factors influencing the path choice, using the analytic hierarchy process of fuzzy mathematics to evaluate the weight of the road, establish the fire fighting rescue model; Then use the particle swarm algorithm quickly get optimal solution,and take the solution as the initial pheromone increment of ant colony algorithm,put the solved each path weight matrix is introduced into the particle swarm ant colony algorithm to solve the model of state transition probability, then use this improved state transition rules, and consider the traffic speed to obtaine the optimal path of the model.Finally, the experimental results show that this method can accomplish the best relief path planning.

particle swarm optimization; ant colony optimization; fusion algorithm; optimize ;the relief path

2017- 03- 01

浙江省科技計劃項目(GK090910001)

李怡弘(1991-)，女，碩士研究生。研究方向：消防物聯(lián)。裘炅(1973-)，男，博士，副教授。研究方向：消防物聯(lián)。

TP311.5

A

1007-7820(2018)01-058-05