劉文寧，王家偉，湯雪芹

(重慶交通大學 信息科學與工程學院，重慶 400047)

元胞自動機模型(Cellular Automaton，CA)作為一種實現(xiàn)規(guī)則簡單，可以將復(fù)雜系統(tǒng)簡單化的模型，是目前應(yīng)用最廣泛的疏散模型之一[1].然而，其簡單的實現(xiàn)規(guī)則也導致了其在描述疏散個體行為上具有一定的局限性，而且當元胞的鄰域為擴展Moore 鄰域時，會花費較多的時間用于搜索可行領(lǐng)域元胞.

人工魚群算法(Artificial Fish Swarm Algorithm，AFSA)作為一種較為新型的群集智能算法，其利用群體之間信息交互來實現(xiàn)全局尋優(yōu)的思想，為微觀疏散模型的研究提供了一種新的思路.Lu DJ 等人[2，3]使用人工魚群算法來描述應(yīng)急疏散時個體在路網(wǎng)中尋找疏散出口的過程.

不同于應(yīng)急疏散，在綜合交通樞紐常規(guī)疏散的過程中，人員的行為表現(xiàn)更為豐富，具有排隊等待、逗留、從眾、跟隨、隨機探索、出(入)口選擇行為、導向行為等，使用單一的CA模型或者原始的AFSA 算法都是難以完全刻畫這些行為的.因此，本文改進原始AFSA 算法，結(jié)合CA模型，提出一種基于元胞魚群算法(CA-IAFSA)的人員疏散模型，在刻畫人員多樣行為的同時，降低模型的時間復(fù)雜度.

1 相關(guān)研究

CA模型是把空間和時間按照一定間距離散化，系統(tǒng)物理量只取有限個狀態(tài)的物理系統(tǒng)簡化模型[1].它具有四個基本組成部分:元胞、狀態(tài)、鄰域和轉(zhuǎn)換規(guī)則.基于CA的疏散模型側(cè)重于研究應(yīng)急情況下的人員疏散過程[4-6]，關(guān)注于人員特性或者環(huán)境對疏散效率造成的影響[7-10]，忽略個體在疏散過程中的行為表現(xiàn)和相互影響.

AFSA 算法最早是在2002年被提出的[11]，該算法使用人工魚的四種基本行為:聚群行為、追尾行為、覓食行為、隨機行為來實現(xiàn)變量在變量空間中尋優(yōu)的過程[12].該算法在解決配電網(wǎng)重構(gòu)等一系列連續(xù)性優(yōu)化問題取得了較好的效果，但在解決離散型優(yōu)化問題上仍具有一定的局限性[13].

目前，將AFSA 算法和CA 結(jié)合起來進行研究的文獻較少.柳毅[14]在研究帶時間窗可回程取貨車輛路徑問題數(shù)據(jù)模型的基礎(chǔ)上，將AFSA 算法和CA 結(jié)合設(shè)計了元胞魚群算法.將二者結(jié)合起來，一方面可以提高AFSA 算法對離散型優(yōu)化問題的處理能力，另一方面可以使用AFSA 算法中人工魚的搜索規(guī)則來替代CA模型中的元胞狀態(tài)轉(zhuǎn)換規(guī)則，從而降低模型的時間復(fù)雜度.

2 基于元胞魚群算法的疏散模型

將綜合交通樞紐內(nèi)需要換乘的人員看成是人工魚，按照乘車意向劃分為多個種群，上層采用改進的AFSA算法，底層采用CA 框架，將搜索空間離散化，在每輪迭代過后，利用CA模型的鄰域模型和狀態(tài)轉(zhuǎn)換規(guī)則，解決位置沖突.

2.1 模型假設(shè)

(1)人員在移動過程中，不考慮碰撞與擠壓；

(2)換乘客流全部來源于火車到站客流，其乘車意向假設(shè)已知.人員在移動過程中不會更改乘車意向.

2.2 個體抽象

考慮個體的速度差異、視野差異，個體表示為:

其中，X代表個體p的位置；O表示乘車意向；v0是初始速度；v(t)=v0×e-ω×(ρ(t)-1)，ρ(t)是t時刻周圍人群密度(單位:人/m2)；w為視野范圍；M是一張記憶表，M=(l1,l2,···,lk)，用于記錄個體p記憶中的引導指示，防止陷入局部最優(yōu)，l=(st,en)，l表示引導指示的方向矢量，st表示起始坐標，en表示終點坐標；Q=(exit,t1,t2)，保存?zhèn)€體p當前的排隊信息，exit表示p正在出口(乘車點)exit處排隊，t1表示到達exit的時刻，t2表示離開exit的時刻.

2.3 行為抽象

(1)出(入)口選擇行為:

(2)導向行為:當在視野可見范圍內(nèi)，沒有目標出口，存在引導指示時，選擇距離最近的引導指示l.

若l?M:

若d(st,)＞η:

若d(st,)≤η:

其中，η是一個自定義參數(shù)，表示疏散引導指示的作用范圍.

若l∈M:

當pi視野可見范圍內(nèi)即無出口又無引導指示時，則選擇從眾行為、跟隨行為、探索行為中最優(yōu)的一種行為執(zhí)行.

(3)從眾行為:pi搜索視野可見范圍內(nèi)具有相同意向的伙伴，計算其中心位置Xc，若Y(Xc)優(yōu)于Y()，將作為pi下一個時間步的待選位置.

(4)跟隨行為:pi搜索視野可見范圍內(nèi)具有相同乘車意向的伙伴pj，若Y(Xj)優(yōu)于Y()，將作為pi下一個時間步的待選位置.

(5)探索行為:個體在視野范圍內(nèi)隨機而不重復(fù)的任選一個位置Xr，若Y(Xr)優(yōu)于Y(Xi)，則將作為pi下一個時間步的待選位置.

若pi在嘗試了try_num次后，仍沒找到較優(yōu)的位置，則停留在原地.

(6)隨機行為:當pi在嘗試了以上五種行為后，仍停留在原地，說明陷入了局部最優(yōu)，此時，隨意選擇一個可行的方向進行移動.

完成一輪迭代后，最終確定下一時間步的移動位置Xn.

2.4 排隊機制的實現(xiàn)

pi在t時刻確定相應(yīng)的出(入)口eO，且d(pi,eO)＜ξ (ξ 表示距離閥值)，pi進入到eO當前的排隊隊列中，pi停止移動，排隊結(jié)束后，則恢復(fù)運動.

2.5 位置沖突的解決

當個體確定了下一個時間步的移動位置Xn時，底層使用CA模型的并行更新策略來解決位置沖突.沖突解決規(guī)則如下:

(1)將Xn作為中心元胞，使用Moore 型鄰域，當Xn與之間既沒有障礙物，Xn也沒有被其他個體占據(jù)，優(yōu)先選擇Xn.

(2)當發(fā)生沖突時，遍歷Xn周圍滿足條件的鄰域元胞N(Xn)，分別計算未被其他個體占據(jù)且與Xn之間不存在障礙物的元胞與的歐式距離，隨機選擇一個元胞作為下一個時間步的目標移動位置.

(3)Xn周圍沒有滿足條件的鄰域元胞時，停留在原地.

圖1 CA模型解決位置沖突

3 實驗及結(jié)果分析

3.1 環(huán)境設(shè)置

在MATLAB 上搭建2D模擬環(huán)境，進行實驗.疏散環(huán)境設(shè)置如下:

(1)環(huán)境區(qū)域為100 m×100 m，元胞邊長為0.2 m，設(shè)置火車站的范圍為x∈[0 m,100 m]，y∈[0 m,20 m].各交通方式的出/入口參數(shù)設(shè)置如表1所示.

(2)這里參考文獻[15]，設(shè)置個體占地面積0.4 m×0.4 m，初始速度服從正態(tài)分布N(1.34,0.262)，(單位:m/s)時間變化步長為1s.

(3)ω=0.01，η=2，ξ=2v.

表1 各交通方式的出/入口參數(shù)設(shè)置

3.2 算法參數(shù)分析

采用控制變量法依次測試人工魚的探索嘗試次數(shù)try_num及視野范圍w對于疏散效果的影響.設(shè)置人數(shù)為500，換乘其他四種交通方式的人數(shù)各占25%.

(1)調(diào)試try_num參數(shù)值:設(shè)置w隨機分布在[20,30]范圍內(nèi).try_num變化步長為5，分析try_num=5，10，…，50時對于疏散效果的.實驗結(jié)果如圖2所示.

圖2 參數(shù)try_num 對疏散效果的影響

(2)調(diào)試w參數(shù)值:基于實驗(1)，設(shè)置try_num=20，設(shè)置w變化步長為5，分析w分布[5，10]，[10，15]，…，[45，50]范圍時對于疏散效果的影響.實驗結(jié)果如圖3所示.

圖3 參數(shù)w 對疏散效果的影響

從圖2 可知，當設(shè)定人工魚的視野范圍w∈[20,30]時，try_num=20時，平均疏散時間與平均實驗時間最短，而當try_num大于35時，平均疏散時間基本變化不大，平均實驗時間卻在上下波動變化.因此，這里設(shè)置try_num=20.

從圖3中可知，當設(shè)定人工魚的探索嘗試次數(shù)try_num=20時，w∈[20,25]時，平均疏散時間和平均實驗時間最少，w的分布范圍大于30時，其對應(yīng)的平均疏散時間和平均實驗時間基本上變化不大.因此這里設(shè)置w的分布范圍為[20,25].

3.3 實驗及對比分析

設(shè)置人數(shù)為500，換乘其他4 種交通方式的人數(shù)各占25%.對比三種模型:①ICA模型:在CA模型中，加入導向行為、排隊行為和出口選擇機制；②CAAFSA:將CA模型和原始AFSA模型結(jié)合，加入排隊行為和出口選擇機制，不加導向行為；③本文提出的CA-IAFSA模型.(注:由于完整截取的圖片較大，圖4中的(c)和(d)只截取了部分效果圖.)

對比圖4中的(a)和(b)可以發(fā)現(xiàn)，模型①中，位于火車站內(nèi)的絕大數(shù)個體“絕對理性地”選擇了距離出口最近的位置，緊貼靠近出口的障礙物進行移動，且趨向于在出口處形成“拱形”.而在模型③的模擬效果圖中，人群是從遠離出口的初始位置以聚集的趨勢逐漸向三個出口靠近，有效地避免了“緊貼墻壁行走”.模型③相比模型①更好地體現(xiàn)了“從眾”和“避障”行為.

對比圖4中的(c)和(d)，相比模型②，加入“導向行為”的模型③克服了根據(jù)“最短路徑原則”移動而陷入局部最優(yōu)，原地徘徊而無法繼續(xù)疏散的缺陷，實現(xiàn)了人群自發(fā)有序地向著目的換乘點移動，很好地體現(xiàn)了人員疏散的“導向”行為.

對比圖5中的(a)，(b)，對于距離較近的三個火車出口，模型③相比模型①，實現(xiàn)了資源的均衡利用，比較符合實際情況下人員的“出口選擇”行為.

為了進一步驗證CA-IAFSA模型的在疏散模擬時間性能上的提升，分別將人數(shù)設(shè)置為300 人，500 人，1000 人，在同等條件下，使用ICA模型和CA-IAFSA模型進行10 次模擬實驗取均值，結(jié)果如表2所示.

由表2 可以看出，在同一實驗條件下，模型③與模型①相比，平均疏散時間在一定程度上有所降低，在實驗時間花費上至少降低了59%.原因是:前者采用擴展型摩爾型鄰域，遍歷鄰域元胞獲得下一個移動位置時花費了大量的時間.后者采用AFSA 算法中人工魚的搜索規(guī)則來替代CA模型中的元胞狀態(tài)轉(zhuǎn)換規(guī)則，避免了盲目搜索，同時，在一定程度上避免了“快即是慢”現(xiàn)象的發(fā)生，防止人群由于“最短路徑原則”產(chǎn)生過度擁擠，從而提升疏散性能.

圖4 三種模型的模擬效果

圖5 兩種模型的火車出口排隊人數(shù)變化趨勢

表2 兩種模型的疏散效果對比

4 結(jié)論與展望

本文提出的CA-IAFSA模型，針對綜合交通樞紐的常規(guī)疏散，考慮個體之間的速度差異、視野差異，將導向行為和排隊機制加入原始AFSA 算法中，融合CA模型構(gòu)建人員常規(guī)疏散模型.實驗結(jié)果證明，CA-IAFSA模型，可真實的反映人員在綜合交通樞紐內(nèi)進行換乘時的疏散過程.克服了原始AFSA 在存在障礙物的疏散環(huán)境中，易陷入局部最優(yōu)的缺陷，在刻畫人員的導向行為、避障行為、排隊行為、出(入)口選擇行為上具有較好的模擬效果，相比ICA模型，CAIAFSA模型在一定程度上減少了疏散時間，在時間復(fù)雜度上至少降低了59%.在今后的研究中，會根據(jù)實際情況，進一步對模型參數(shù)進行調(diào)整，為特定綜合交通樞紐場景中的人員常規(guī)疏散提供決策輔助.