基于改進蟻群算法的消防路線規劃系統*

許向陽，吳澤華

（河北科技大學，河北 石家莊 050000）

0 引 言

隨著社會經濟的飛速發展，城市規模不斷擴大，車流量越來越大，帶來的交通問題越來越嚴重，給一些用于緊急工作的車輛帶來了極大不便，如急救車、警車和消防車等。在這些車輛執行任務時，時間就是生命。因此，在這些車輛執行任務時，為任務車規劃一條最優路徑，必將提高其工作效率，減少財產損失，保障人們的安全[1]。將科技融入到實際生活是科技發展的必經之路。隨著地理信息系統（GIS）的不斷發展，越來越多與地理相關的行業開始結合GIS來提升自己在本行業的影響力。地理信息系統是專門為地理數據和空間數據誕生的，在處理地理模擬、空間網絡分析等方面具有很大優勢。網絡分析是GIS的一個重要功能，而路徑規劃是網絡分析的一個重要應用[2]。將GIS的路徑規劃功能與消防行業相結合，可以提高消防作業的效率。

目前，對于消防與GIS結合的研究中，路線規劃仍是研究重點[3]。路線規劃研究的本質是研究最優路徑算法[4]，常用的經典最優路徑算法有Dijkstra算法、A*算法、蟻群算法和Floyd算法等。這些經典的最優路徑算法都有不足，如Dijkstra算法不能解決帶負權值的圖，如果處理的數據量較大，可能需要鄰接表；A*算法不能保證找到最優解；蟻群算法在數據量非常大時，容易陷入局部最優解，且算法執行時間長、復雜度高等。基于這些算法的局限性，本文提出在蟻群算法的基礎上優化，使其能夠更好地應用于現實生活。

1 系統設計

1.1 系統需求分析設計

為了加強對消防工作的管理，提高消防工作效率，實現智能消防模型，為了達到智能消防的目的，系統需要進行消防設施信息的存儲；為了提高消防出警效率，提高消防資源利用率，系統需要提供消防決策的功能；同時，系統應該提供可視化工具，來對智能消防的規劃結果進行展示。

1.2 系統整體架構

根據系統的需求分析，可設計系統包含以下模塊：用戶登錄模塊、數據管理模塊、出警決策輔助模塊、網絡分析模塊和結果展示模塊。系統總體架構如圖1所示。

圖1 系統總體架構

1.3 道路因素分析

結合實際生活中的道路影響因素，提出以下幾種關鍵影響道路通行概率的影響因素，包括路段總通行概率P、遇到交通管制的概率P1，發生交通事故的概率P2，由于人為因素產生的交通擁堵概率P3，由于天氣原因導致的交通擁堵概率P4。綜上所述，影響道路通行的總概率P為：

其中，在遇到交通管制情況下，P1為0＜P1＜1；發生交通事故時，P2為0＜P2＜1；由于人為原因產生的交通擁堵概率0＜P3＜1；由于天氣原因導致的交通擁堵概率為0＜P4＜1。如果沒有上述原因的干擾，則路段的總通行概率P=1。道路因素對路段通行概率情況如圖2所示。

圖2 道路因素對道路通行影響

1.4 系統關鍵技術

網絡數據集是進行交通網絡分析的數據基礎，由網絡元素組成。網絡元素的本質是要素集，要素集的幾何信息是用于建立網絡的連通性，且網絡元素的屬性可以約束網絡中被運輸網絡對象的運輸路徑。基本的網絡元素可以劃分為三種，分別是邊要素、節點要素和轉彎要素。邊要素與節點要素相連，是資源流動的紐帶；節點要素連接邊要素，引導目標從一條邊到另一條邊移動；轉彎要素用來記錄在兩條邊或多條邊之間運動的信息。其中，邊要素和節點要素是網絡的基本結構。網絡數據集的創建有兩種方式：一種是基于ShapeFile文件，利用該文件創建的網絡數據集僅支持單模式的網絡分析；另一種是基于地理數據庫GeoDatabase，利用地理數據庫創建的網絡數據集可以支持多模式網絡分析。單模式與多模式的區別在于出行方式的不同。多模式包括不同類型和級別的道路，可提供更多的出行手段。

2 蟻群算法

2.1 經典蟻群算法模型

蟻群算法是由螞蟻搜索食物的過程演變而來的。算法的基本思想如下：螞蟻在搜索食物的過程中，會在路過的道路上留下一種叫信息素的物質；因為螞蟻在找到食物的周圍和在家的周圍釋放的信息素濃度最多，所以螞蟻會根據信息素濃度的大小來確定自己的行進方向，因此螞蟻群體會表現出正反饋的特征。道路上信息素濃度越多，螞蟻選擇該道路的概率越大。隨著某條道路上信息素濃度的不斷增加，這條道路上通過的螞蟻也越來越多，最優路徑隨之產生[6]。

該算法的基本流程如圖3所示。

圖3 蟻群算法流程

基本蟻群算法模型如下：每只螞蟻經過一條路徑后，會對該路徑上的信息素進行更新，假設整個蟻群的螞蟻總量為m，當前螞蟻的編號為k，t時刻邊(i, j)上的信息素濃度為Δτij(t)，螞蟻k每經過一次迭代信息素更新量為Δτkij(t)，其中信息素更新量按照式（2）進行更新：

Q為信息素總量，為一個常數；Lk為當前螞蟻本次迭代過程中經過的總距離。經過多次迭代后，t時刻道路(i, j)上的信息素總量為：

螞蟻更新信息素后，道路上信息素會以不同的速度揮發。信息素的揮發公式為：

τij( t + n )為經過n時刻后道路(i, j)上的信息素濃度，ρ為信息素衰減因子，范圍為(0,1)。

算法運行過程中，每只螞蟻選擇下一個城市不是隨機選擇的，而是按照式（5）的轉移概率公式進行下一個城市點的轉移：

為螞蟻的轉移概率，為在運行t個時間周期后道路上的信息素濃度，為啟發函數因子。啟發函數因子需要設定合適的值，若啟發函數因子過大，算法的收斂速度快，容易陷入局部最優解；若啟發函數因子過小，算法將找不到最優解[7]。

2.2 改進蟻群算法模型

經典的蟻群算法運行時間長、算法效率較低，算法運行到一定程度后易陷入局部最優的停滯狀態。為了避免算法陷入局部最優的停滯，提高算法的運行效率，本文提出修改算法中的幾個關鍵參數，保證在算法可運行狀態下提高算法運行效率，解決陷入局部最優解的狀態。

算法核心是信息素的更新策略。信息素更新分為局部信息素更新和全局信息素更新，本文將分別對其作出改進。

局部信息素更新改進為：

θ為信息素增加因子，取值范圍為(0,1)。當螞蟻k沿著某條道路(i, j)找到食物時，螞蟻k會按照式（6）的方式釋放信息素。采用該方式可以提高信息素的播撒效率，為第k+1只螞蟻提供更快的路徑選擇。

螞蟻在尋路過程中，道路上的信息素濃度會按照一定速率揮發。若某條道路上的信息素持續揮發至0，螞蟻將停止向此條路徑轉移。為了避免螞蟻陷入局部最優解，將每條道路上的信息素濃度設置在[min，max]之間，并且對信息素揮發引入輔助揮發因子，對全局信息素更新策略作出如下改進：

式（7）中添加參數ω∈(0,1)和γ∈(1,2)。其中，ω為信息素負揮發因子，在一定范圍內可以減緩信息素的揮發，為螞蟻的隨機轉移概率提供參考；γ為信息素正揮發因子，當螞蟻預測到自己走過的路程大于起點與目的點的歐幾里得距離時，便加快當前道路上的信息素濃度。同時，為了避免算法陷入局部最優，每條道路上的信息素濃度都會維持在一定范圍。如果當前道路信息素濃度小于道路信息素濃度下限時，系統會將當前道路信息素濃度置為道路信息素濃度最小值。

在信息素揮發策略中，為螞蟻提供智能功能。螞蟻在開始搜索路徑之間，先對起點到目的點的歐幾里得距離做一個估值D0。螞蟻尋路開始后，當螞蟻發現經過的距離D大于D0時，說明當前路徑并非最短路徑。為了減少算法迭代次數，智能螞蟻將適當提高當前道路的信息素揮發因子，加快算法運行速度。當螞蟻發現經過的距離D小于D0時，則降低當前道路信息素揮發因子，以保證算法能夠找到最短路徑。

改進后蟻群算法的流程，如圖4所示。

3 系統實現

3.1 系統開發環境

由于ArcGIS平臺對地理數據有很強大的處理能力，且ArcEngine針對C#語言提供了用于實現地理功能的各種接口，故本系統采用VS2010平臺結合ArcEngine提供的地理功能接口。地理數據的處理采用的是ArcCatalog，能夠實現網絡數據集的創建。可以設置網絡數據集中的屬性如道路連通性、轉彎特性等。系統基于C#的可視化應用程序，提供了友好的系統用戶界面，功能界面如圖5所示。系統主界面主要包括五個模塊：文件管理、構建網絡數據集、添加網絡元素、尋找最優路徑和結果分析。如圖5所示，左側導航欄中包括網絡節點信息和地理信息；左下角為鷹眼功能展示，可以通過拖動鷹眼的小地圖，實現對主地圖的查詢。

圖4 改進蟻群算法流程

圖5 系統主界面

利用ArcEngine開發解決最優路徑問題的基本步驟如下：

（1）讀取shp文件和網絡數據集數據；

（2）創建網絡分析上下文對象INAContext和網絡分析對象；

（3）加載位置停靠點圖層，創建網絡位置；

（4）設置Solver參數（輸出、容差值等）；

（5）進行最優路徑分析；

（6）繪制分析結果路線，輸出結果信息。

3.2 系統功能介紹

系統整體界面風格，如圖5所示，系統各部分功能如下。

文件管理。此模塊用于打開工作空間，包括幾何網絡數據集和邏輯網絡數據集。

添加網絡元素。此模塊用于對所選圖層進行網絡停靠點的添加，提供網絡分析的基礎。

最短路徑分析。此模塊用于解決最優路徑問題。清除分析。此模塊用于清除網絡分析結果。

分析結果顯示。此模塊用于顯示網絡分析結果，可以選擇采用圖表顯示和折線顯示分析結果。

幫助。此模塊提供該系統的幫助文檔。

4 試驗結果對比

添加信息素更新因子后，t時刻螞蟻k的信息素更新情況如表1所示。

表1 信息素增加因子對信息素更新的影響

說明：Q為信息素總量，Lk為螞蟻一次循環經過的路徑，θ為信息素增加因子，τijk(t)為t時刻螞蟻k的信息素更新量，τijk'(t)為增加θ后信息素的更新量。

折線圖表示如圖6所示。

圖6 局部信息素因子對信息素更新影響

實驗分析結果表明：添加信息素更新因子θ后，對于信息素更新速率有很大的提高，但是考慮到信息素更新太快，可能會導致算法早熟，以至于未能找到最優路徑，因此選取適當的信息素更新因子才可以在保證最優路徑的基礎上，提高算法效率，通過多次試驗發現，當信息素更新因子θ在0.3～0.5范圍內時，算法可以在保證最優路徑的基礎上，提高信息素更新速度。

對于全局信息素更新策略，根據螞蟻所經過路程不同，采用的不同的信息素更新策略，本實驗取信息素揮發因子為0.5，信息素更新量為3.0，根據螞蟻所經過路程與初始估測值的關系，不同的信息素更新策略如表2所示。

說明：D0為螞蟻k估測起點與目的點的距離，D為螞蟻k尋路過程中實際走過的路程，ω為信息素的正揮發因子，γ為信息素的負揮發因子，折線圖分別如圖7、圖8所示。

表2 信息素揮發因子對信息素更新的影響

圖7 ω對信息素影響

圖8 γ對信息素影響

實驗表明：當D＜D0時，信息素更新速度很快，呈指數形式增長，隨著螞蟻走過的路程增加，信息素的更新速度趨于平緩；當D=D0時，信息素的更新速度是原來的2倍；當D＞D0時，信息素開始出現負增長（信息素開始衰減）。為了保證螞蟻的隨機搜索能力，規定每條道路上的信息素濃度有下限。當該道路上的信息素濃度衰減越過該下限時，系統強制將本道路上的信息素濃度置為最小值。通過多次試驗分析發現，在螞蟻尋路過程中，信息素揮發正因子ω=0.5，信息素揮發負因子γ=1.5時，系統的穩定性最好。

5 結 語

本文通過提出智能螞蟻信息素更新策略，使螞蟻根據不同距離采用不同的信息素更新策略。仿真結果表明，改進蟻群算法具有優越性。下一步嘗試將路徑之間的角度參數加入蟻群算法。

[1] Wang Z.A Preliminary Report on the Great Wencluan Earthquake[J].Earthquake Engineering Vibration,2014,7(02):225-255.

[2] Toro-Diaz H,Mayorga M E,Chanta.Joint Location and Dispatching Decisions for Emergency Medical Services[J].Computers & Industrial Engineeri ng,2015,165(05):1917-1928.

[3] Ozdamar L,Demir O.A Hierachical Chistreing and Routing Procedure for Large Scale Disaster Relief Logistics Planning[J].Transportation Research Part E,2012,48(03):591-602.

[4] 高炳楠.基于GIS的應急預案管理系統研究[D].北京:北京交通大學,2011.GAO Bing-nan.Research on Emergency Plan Management System Based on GIS[D].Beijing:Beijing Jiaotong University,2011.

[5] 魏錸,李含倫,劉琦,等.基于GIS和AHP的消防站點規劃[J].消防科學與技術,2010,29(09):827-833.WEI Lai,LI Han-lun,LIU Qi,et al.Fire Station Planning Based on GIS and AHP[J].Fire Science and Technology,2010,29(09):827-833.

[6] 陳艷.基于蟻群算法的最優路徑選擇研究[D].北京:北京交通大學,2007.CHEN Yan.Research on Optimal Path Selection Based on Ant Colony Algorithm[D].Beijing:Beijing Jiaotong University,2007.

[7] 陸鋒.最短路徑算法:分類體系與研究進展[J].測繪學報,2010,30(03):269-299.LU Feng.Shortest Path Algorithm: Classification System and Research Progress[J].Journal of Surveying and Mapping,2010,30(03):269-299.