蟻群元胞優(yōu)化算法在人群疏散路徑規(guī)劃中的應用*

王培良 張婷 肖英杰

1)(上海海事大學商船學院,上海 201306)

2)(山東交通職業(yè)學院航海學院,濰坊 261206)

3)(濰坊科技學院,濰坊 262700)

針對疏散路徑規(guī)劃問題,以柵格化地圖為背景的基礎上,提出了蟻群元胞優(yōu)化算法.首先為統(tǒng)一仿真時間步長,建立以六邊形元胞為基礎的柵格地圖;然后利用靜態(tài)勢場對啟發(fā)函數進行優(yōu)化,利用分段更新規(guī)則優(yōu)化信息素更新方式;最后,將模型參數作為粒子群優(yōu)化算法的粒子位置信息進行優(yōu)化,求解參數的最優(yōu)組合值.仿真結果表明: 采用蟻群元胞優(yōu)化模型進行疏散路徑規(guī)劃時,不僅加快了搜索速度,而且增大了解空間,提高了搜索能力,可以有效避免陷入局部最優(yōu)解.

1 引 言

隨著現代工業(yè)和科技的發(fā)展,大型建筑物結構變得越來越復雜,突發(fā)事件的發(fā)生,使得疏散人群的難度越來越高,易造成重大的人員傷亡和經濟損失.如何快速及時的預警、應對突發(fā)事件已經成為世界范圍內亟待解決的問題.疏散路徑規(guī)劃是提升疏散成功率的有效方式之一,大量學者正進行堅持不懈的研究,以期最大限度地降低發(fā)生突發(fā)事件所帶來的危害,因此疏散路徑規(guī)劃已成為當前學科研究的重點和熱點.

目前,在應急疏散路徑規(guī)劃中應用較為廣泛的算法有Dijkstra算法、Floyd算法、A*算法、蟻群算法(ant colony clgorithm,ACO)等.相比于時間損耗較大的Dijkstra算法、時間復雜度較高而不適應大量數據仿真的Floyd算法、以及易陷入局部最優(yōu)解的 A*算法,Dorigo和Gambardella[1]提出的帶有正反饋、啟發(fā)式的ACO算法,具有較強的魯棒性及全局搜索能力,在解決路徑規(guī)劃問題時效果良好.Babinec等[2]提出了跳點搜索策略,減少了遍歷節(jié)點的數目,提高了算法運算速度,但是在所規(guī)劃的路徑中仍存在轉折點.Cui等[3]通過改進啟發(fā)式因子對蟻群算法進行優(yōu)化,提升了尋徑效果.Imen等[4]提出了改進的禁忌搜索模型,用于求解網格地圖中的路徑規(guī)劃問題.Dorigo和Gambardella[5]通過研究提出了螞蟻系統(tǒng)模型(ant colony system,ACS),該算法能夠在保持螞蟻算法模型的基礎上,精簡了算法結構.Stützle和Hoos[6,7]提出了最大-最小螞蟻系統(tǒng)(max-min ant system,MMAS),該算法通過設置信息素的閾值提高了其全局搜索能力,避免出現停滯現象.張瑋等[8]將蟻群算法與煙花算法相結合,通過對信息素的初始值進行優(yōu)化提升算法性能.胡啟國等[9]通過優(yōu)化信息素更新和狀態(tài)轉移規(guī)則,解決了算法容易陷入局部最優(yōu)解的問題.Hsu等[10]通過改進信息素的更新規(guī)則對蟻群算法進行優(yōu)化,緩解了原算法易陷入局部最優(yōu)解的問題.李東妮等[11]將蟻群算與遺傳算法相結合,加入交叉和變異算子,增加了獲得全局最優(yōu)解的概率.王曉燕等[12]結合人工勢場法,通過優(yōu)化信息素初始值以及揮發(fā)系數,提升了算法搜索能力.總之,現有研究主要依據傳統(tǒng)四邊形柵格為背景的ACO算法,并進行優(yōu)化來進行路徑規(guī)劃[13,14],未能解決仿真時步長不統(tǒng)一問題,同時對算法參數的優(yōu)化也未能提出系統(tǒng)性方法[15?17].

鑒于上述問題,本文提出蟻群元胞優(yōu)化模型(ant colony cellular optimization,ACCO),以六邊形柵格為仿真地圖劃分依據,重新設計并優(yōu)化啟發(fā)函數和信息素更新方式,以期提升ACCO算法的搜索能力、收斂速度等.同時系統(tǒng)性地提出利用粒子群優(yōu)化(partical swarm optimization,PSO)算法對ACCO算法參數進行優(yōu)化的方法[18].最后通過仿真對比分析,驗證ACCO算法的可行性和有效性.

2 蟻群元胞優(yōu)化模型構建

2.1 柵格地圖建立

在進行傳統(tǒng)的路徑規(guī)劃仿真求解時,均使用的四邊形柵格地圖[19,20],且一般采用moore型鄰域,即 N={s1,s2,···si},i∈ [1,8],si∈ [0,1],i和si均取整數,i表示鄰域元胞編號,si表示元胞是否被選中,取1時表示被選中,灰色為中心元胞即螞蟻當前所在元胞,黑色元胞表示障礙物或者邊界,(2 1)分別表示柵格的行列號(行號以中心點所在位置為基準,列號同理),如圖1(a)所示.

使用上述四邊形柵格在進行系統(tǒng)仿真時,假定柵格的邊長為e,則選擇下一步的目標元胞時,極軸和斜向方向的移動距離分別為e和如圖1(b)所示,因此當元胞的移動速度v不變時,元胞的移動時間為產生時間步長不統(tǒng)一問題,影響模型的真實性.為有效避免“斜向穿墻”現象,提出使用六邊形柵格,當柵格邊長仍為e時,元胞每次仿真移動的距離為移動時間為如圖 1(c).

因此,建立六邊形柵格地圖,并以地圖左下角為原點建立笛卡爾坐標系,水平方向為X軸.設每個六邊形的內切圓圓心為其中心坐標點,則坐標值(x,y)為

其中 i為當前柵格行號,i ∈ [1,2,···,Ni];j為當前柵格列號,分別為柵格的行列總數;分別為x,y方向上的單位增量.

2.2 基本模型描述

使用ACCO算法對疏散路徑進行規(guī)劃時,采用六邊形柵格將仿真環(huán)境劃分為均勻的離散網格圖,然后計算出從起始節(jié)點到目的節(jié)點的可行網格鏈集合,最后在集合中選擇最優(yōu)解[21].

圖1 柵格示意圖(a)Moore 型鄰域;(b)傳統(tǒng)四邊形柵格;(c)改進六邊形柵格Fig.1.Grid schematic:(a)Mooretype neighborhood;(b)traditional quadrilateral grid;(c)improved hexagon grid.

蟻群元胞優(yōu)化算法可表示為:

其中Gm×n為網格地圖的信息矩陣;Pm×n為信息素矩陣;m和n表示矩陣的行列數,m一般與單次迭代螞蟻數量相同;CS為元胞狀態(tài),取值為{0,1},表征此元胞是否被占用,1表示被占用;Cw為元胞空間,w表示空間維數,從G中獲取,這里w取2維;CN為元胞鄰域,使用2.1節(jié)中所述Moore型;CR為元胞規(guī)則,是蟻群移動的基本約束,主要取決于三點,即1)所選元胞為非障礙物或邊界;2)所選元胞更加有利于到達目的元胞;3)概率轉移公式決定鄰域元胞被選中的概率,如

其中pij為由元胞i轉移到元胞j的概率值,τij為元胞i與j之間的信息素濃度,hij為元胞i與j之間的啟發(fā)函數,α與β為信息素啟發(fā)因子和期望啟發(fā)因子,tabu為當前螞蟻的禁忌表;O為優(yōu)化策略,主要針對傳統(tǒng)模型存在的問題進行優(yōu)化,詳見第3節(jié).

3 優(yōu)化策略描述

ACCO算法的優(yōu)化策略主要是對啟發(fā)函數、信息素更新方式以及參數組合設定等方面優(yōu)化,以解決傳統(tǒng)蟻群算法在進行路徑規(guī)劃問題時存在的收斂速度慢、搜索空間小、易陷入局部最優(yōu)解等問題.

3.1 啟發(fā)函數的設計優(yōu)化

啟發(fā)函數表征各鄰域元胞被選擇的期望程度,傳統(tǒng)四邊形柵格地圖常選用兩元胞之間的距離值為參考標準,而六邊形柵格地圖兩元胞之間的距離值為常數,導致啟發(fā)函數為常數而失去價值.將靜態(tài)勢場引入啟發(fā)函數的設計優(yōu)化中.靜態(tài)勢場值反映鄰域元胞與目的元胞之間的距離程度,距離越近,靜態(tài)勢場值越大,因此符合模型對啟發(fā)函數的要求.同時靜態(tài)場值的引入在提高模型收斂速度的基礎上,降低了迂回現象的發(fā)生概率.

優(yōu)化后的啟發(fā)函數為

同時,為增加解空間的范圍,提升最優(yōu)解的效果,當ACCO算法迭代到一定次數后,對最優(yōu)路徑中的節(jié)點與目的節(jié)點之間的啟發(fā)函數使用(3)式進行更新:

其中Did為節(jié)點i與目的節(jié)點d之間的距離值,S為最優(yōu)路徑長度,i -1 為最優(yōu)路徑中節(jié)點i的前一節(jié)點.

3.2 信息素更新規(guī)則優(yōu)化

當前常用的信息素更新方式主要分為三類: 蟻密模型,蟻量模型,以及蟻周模型.以蟻周模型為基礎,將全局信息素濃度的值限定在閾值[τmin,τmax]范圍內,設計分段更新規(guī)則進行信息素的更新,公式如下:

其中 k 為當前螞蟻;信息素濃度 τmin,τmax分別為1/Lb,τmax/20;ρ ∈[0,1] 為信息素揮發(fā)系數;Q 為信息素濃度總量;Lb為本次迭代的最優(yōu)路徑長度值;Lk為螞蟻k完成本次搜索所經過的路徑長度.

3.3 參數優(yōu)化

在 ACCO 算法中,參數 α,β,ρ 對算法的收斂速度以及解空間的大小等性能影響顯著: 參數α值越小,算法搜索的隨機性增強,但算法的收斂速度變慢;參數β值越小,算法越易陷入局部最優(yōu)解;參數ρ直接影響模型的全局搜索能力和收斂速度.因此,為提升模型性能,將利用粒子群優(yōu)化算法對參數進行優(yōu)化求解.

粒子群優(yōu)化算法是由Eberhart與Kennedy[22]在20世紀90年代提出的一種基于種群的全局隨機優(yōu)化算法.該算法中的每個粒子根據自身及其他粒子的位置信息不斷調整移動速度,同時調整移動的方向和距離,從而實現粒子在解空間內的全局尋優(yōu).在算法求解的迭代過程中,粒子通過個體極值和全局極值調整自身的速度與位置,其公式如下:

使用粒子群優(yōu)化算法進行參數優(yōu)化的思路是:將ACCO算法的參數α,β,ρ作為粒子群優(yōu)化算法的粒子位置信息進行求解,通過適應度評價函數不斷調整粒子位置,從而求得參數的最優(yōu)值和組合值.因此針對解路徑規(guī)劃問題,綜合考慮尋優(yōu)能力、運行時間、收斂速度和穩(wěn)定性等影響因素,設計出如下適應度評價函數:

其中Fi(x)為第i個粒子代表的參數所對應的適應度函數值;λ1,λ2,λ3,λ4為權重系數,且滿足λ1+λ2+λ3+λ4=1;Li(x)是使用粒子i運算所得的參數,表示ACCO算法搜索最優(yōu)路徑的能力;Lbest表示每次PSO迭代所得到的最優(yōu)路徑的元胞數量;Si(x)是使用粒子i運算所得的參數,表征ACCO算法的收斂速度;Nbest為ACCO算法搜索到當前最優(yōu)路徑時自身的迭代次數;Nmax為元胞螞蟻的最大迭代次數;Qi(x)是使用粒子i運算所得的參數,表示ACCO算法的穩(wěn)定性;Lstd為每次PSO迭代過程中,表征ACCO算法搜索到的路徑的方差;Ti(x)表示使用粒子i運算所得的參數,表征ACCO算法的運行時間;Dis表示元每次PSO迭代過程中ACCO算法搜索路徑總和.

3.4 路徑規(guī)劃流程

使用ACCO算法進行路徑規(guī)劃的流程如圖2所示.

圖2 算法流程圖Fig.2.Simulation flow chart.

4 仿真分析

4.1 仿真環(huán)境設定

為驗證所構建模型的性能,以某大型郵輪的B甲板上的展廳為工程背景進行仿真,模型的信息素濃度取14,螞蟻數量為30,計算對比ACCO算法與傳統(tǒng)算法的優(yōu)劣,郵輪B甲板構造詳情如圖3所示.

甲板中間位置展廳面積為 20 m × 20 m 的封閉空間,其構造詳情見圖 4(a),仿真環(huán)境為 20 × 20的柵格地圖,如圖4(b)所示.

圖3 某郵輪 B 甲板構造圖Fig.3.B-deck structure diagram of a cruise ship.

圖4 展廳構造與仿真圖(a)展廳構造圖;(b)仿真環(huán)境圖Fig.4.Exhibition hall construction and simulation:(a)Exhibition hall structure;(b)simulation environment diagram.

4.2 仿真結果分析

4.2.1 參數優(yōu)化結果

根據專家經驗法[23],對PSO算法的其他參數值分別按照表1進行賦值.

根據仿真要求進行兩組運算,其求解結果如表2所列.

表1 PSO 算法參數取值Table 1.The parameters of PSO algorithm.

表2 參數求解結果Table 2.Parameter solution results.

同時為觀察適應度評價函數性能,對比分析兩組參數的適應度值曲線,如圖5所示.

4.2.2 路徑規(guī)劃結果

根據上述模型構建描述及參數設定,分別使用傳統(tǒng)算法與ACCO算法進行仿真,其最終路徑效果如圖6所示.

圖6中S表示起始節(jié)點,E表示目的節(jié)點.從圖6可知,傳統(tǒng)模型與ACCO算法均可進行有效路徑規(guī)劃.

圖5 粒子適應度值曲線(a)參數組 1;(b)參數組 2Fig.5.The fitness value curves:(a)Parameter group 1;(b)parameter group 2.

圖6 仿真效果圖Fig.6.Simulation effect chart.

4.2.3 路徑長度及分析

當最大迭代次數一定時,由于傳統(tǒng)算法與ACCO算法在路徑選擇概率上的差異,導致每次迭代所有螞蟻搜尋的總路徑長度和搜索速度也不同,其結果如圖7所示.

由圖7分析可知,兩類算法在搜索路徑時,所經過的元胞總數隨著迭代次數的增加而逐漸減少;在算法迭代次數相同的情況下,ACCO算法經過的元胞總數明顯小于傳統(tǒng)算法,表明ACCO算法的搜索速度較快;隨著迭代的不斷進行,傳統(tǒng)算法的搜索已基本停滯,而ACCO算法仍在進行;橫向對比圖 7(a),(b),(c),(d)可知,當只是優(yōu)化啟發(fā)函數或者信息素更新方式時,優(yōu)化算法所經過的元胞總數高于ACCO算法,并且在收斂性方面也相對較弱,但是優(yōu)化算法的規(guī)劃效果明顯高于傳統(tǒng)算法;同時從圖7(b)中曲線走勢可明顯看出,優(yōu)化后的啟發(fā)函數對算法搜索能力和收斂速度的提升;對比分析圖 7(b),(e),(f)可知,基于經驗值的 ACCO算法的收斂速度和搜索速度明顯弱于參數組1,參數組2,但是收斂性比參數組1強,而參數組2在收斂速度、搜索能力以及收斂性方面均表現出明顯優(yōu)勢.此外,由于存在部分斷頭路徑問題,傳統(tǒng)算法在前期的搜索中波動性比較明顯.因此在算法搜索能力上,ACCO算法表現出更佳的性能.

4.2.4 迭代對比分析

由于ACCO算法對部分參數進行優(yōu)化,導致其與傳統(tǒng)算法在搜索能力上存在差距,因此當增加迭代次數時,解空間也表現出差異,如圖8所示.

分析圖8可知,當迭代進行到第70次時,傳統(tǒng)算法的搜索路徑已基本停滯,從而解空間已經固定,陷入局部最優(yōu)解的可能性增大;而ACCO算法在迭代進行到近200次時,搜索路徑的元胞總數依舊在減小,解空間在不斷增加,表明仍然在搜尋全局最優(yōu)解.因此傳統(tǒng)算法相比ACCO算法而言,更易陷入局部最優(yōu)解.

圖7 路徑長度對比(a)傳統(tǒng)算法路徑統(tǒng)計;(b)基于經驗參數的 ACCO 算法路徑統(tǒng)計;(c)啟發(fā)函數優(yōu)化后的路徑統(tǒng)計;(d)信息素更新優(yōu)化的路徑統(tǒng)計;(e)基于參數組1的路徑統(tǒng)計;(f)基于參數組2的路徑統(tǒng)計Fig.7.Path length comparison:(a)The path statistics for traditional algorithm;(b)the path statistics for ACCO algorithm with experience;(c)the path statistics for only optimizing heuristic function;(d)the path statistics for only optimizing pheromone update methods;(e)the path statistics for parameter group 1;(f)the path statistics for parameter group 2.

圖8 路徑長度迭代對比(a)傳統(tǒng)算法;(b)ACCO 算法Fig.8.Iteration comparison of path length:(a)Traditional algorithm;(b)ACCO algorithm.

4.2.5 其他性能對比分析

在對算法的搜索能力以及收斂性等性能進行了上述分析后,為了進一步凸顯本文所提算法的優(yōu)勢,現對算法其他方面性能進行分析,主要包括:

運行時間是指在相同的運行環(huán)境中,算法運行所消耗的平均時間;

可重復性是指對真實環(huán)境進行仿真時,對于相同輸入數據,經過多次重復實驗,實驗過程中出現完全相同的局部最優(yōu)路徑的概率;

收斂速率是指算法運行過程中,相鄰迭代過程中最優(yōu)路徑的元胞數之差的平均值;最優(yōu)性是指經過相同的迭代次數,算法搜索到的最優(yōu)路徑的元胞數量,以第100次迭代為例.詳見表3.

通過分析可知,ACCO算法與基本蟻群算法時間復雜度的區(qū)別主要在啟發(fā)函數和信息素的更新方式上,但是改進算法只增加了時間復雜度的常數項和低冪次項,可以忽略,因此時間復雜度并未改變,但由于增加了鄰域元胞的選擇性從而導致運行時間有所加長.同時改進算法在收斂速率、最優(yōu)性和可重復性方面均展現出明顯優(yōu)勢.

表3 算法性能對比表Table 3.Performances comparison of algorithms.

5 結 論

在進行路徑規(guī)劃算法時,傳統(tǒng)算法使用四邊形柵格地圖進行求解,容易導致時間步長不一致、搜索速度慢、易陷入局部最優(yōu)解等問題.

針對以上問題,提出以六邊形柵格替代傳統(tǒng)四邊形柵格作為背景地圖柵格化方法,從而解決四邊形柵格地圖的時間步長不統(tǒng)一的問題,為對比算法性能奠定基礎.同時,分別對啟發(fā)函數以及信息素更新方式進行了優(yōu)化設計.最后將ACCO算法的參數作為PSO算法的位置信息進行迭代求解,利用適應度函數值對求解性能做出評價,從而得到ACCO的最優(yōu)參數組合.仿真實驗結果表明,提出的ACCO算法相比于傳統(tǒng)算法,在算法收斂速度、算法搜索速度、最優(yōu)解的搜尋能力等各方面上均有明顯優(yōu)勢,因此可以為智能疏散系統(tǒng)的開發(fā)設計提供有益參考.