王培良 張婷 肖英杰

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

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

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

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

1 引 言

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

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

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

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

2.1 柵格地圖建立

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

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

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

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

2.2 基本模型描述

使用ACCO算法對疏散路徑進行規(guī)劃時,采用六邊形柵格將仿真環(huán)境劃分為均勻的離散網(wǎng)格圖,然后計算出從起始節(jié)點到目的節(jié)點的可行網(wǎng)格鏈集合,最后在集合中選擇最優(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為網(wǎng)格地圖的信息矩陣;Pm×n為信息素矩陣;m和n表示矩陣的行列數(shù),m一般與單次迭代螞蟻數(shù)量相同;CS為元胞狀態(tài),取值為{0,1},表征此元胞是否被占用,1表示被占用;Cw為元胞空間,w表示空間維數(shù),從G中獲取,這里w取2維;CN為元胞鄰域,使用2.1節(jié)中所述Moore型;CR為元胞規(guī)則,是蟻群移動的基本約束,主要取決于三點,即1)所選元胞為非障礙物或邊界;2)所選元胞更加有利于到達目的元胞;3)概率轉(zhuǎn)移公式?jīng)Q定鄰域元胞被選中的概率,如

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

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

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

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

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

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

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

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

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

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

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

3.3 參數(shù)優(yōu)化

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

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

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

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

3.4 路徑規(guī)劃流程

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

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

4 仿真分析

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

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

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

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

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

4.2 仿真結(jié)果分析

4.2.1 參數(shù)優(yōu)化結(jié)果

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

根據(jù)仿真要求進行兩組運算,其求解結(jié)果如表2所列.

表1 PSO 算法參數(shù)取值Table 1.The parameters of PSO algorithm.

表2 參數(shù)求解結(jié)果Table 2.Parameter solution results.

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

4.2.2 路徑規(guī)劃結(jié)果

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

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

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

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

4.2.3 路徑長度及分析

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

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

4.2.4 迭代對比分析

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

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

圖7 路徑長度對比(a)傳統(tǒng)算法路徑統(tǒng)計;(b)基于經(jīng)驗參數(shù)的 ACCO 算法路徑統(tǒng)計;(c)啟發(fā)函數(shù)優(yōu)化后的路徑統(tǒng)計;(d)信息素更新優(yōu)化的路徑統(tǒng)計;(e)基于參數(shù)組1的路徑統(tǒng)計;(f)基于參數(shù)組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)勢,現(xiàn)對算法其他方面性能進行分析,主要包括:

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

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

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

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

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

5 結(jié) 論

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

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