基于元胞魚群算法的人員疏散模型①

劉文寧，王家偉，湯雪芹

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

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

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

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

1 相關研究

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

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

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

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

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

2.1 模型假設

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

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

2.2 個體抽象

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

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

2.3 行為抽象

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

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

若l?M:

若d(st,)＞η:

若d(st,)≤η:

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

若l∈M:

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

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

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

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

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

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

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

2.4 排隊機制的實現

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

2.5 位置沖突的解決

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

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

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

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

圖1 CA模型解決位置沖突

3 實驗及結果分析

3.1 環境設置

在MATLAB 上搭建2D模擬環境，進行實驗.疏散環境設置如下:

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

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

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

表1 各交通方式的出/入口參數設置

3.2 算法參數分析

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

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

圖2 參數try_num 對疏散效果的影響

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

圖3 參數w 對疏散效果的影響

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

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

3.3 實驗及對比分析

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

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

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

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

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

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

圖4 三種模型的模擬效果

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

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

4 結論與展望

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