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

劉文寧，王家偉，湯雪芹

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

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

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

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

1 相關(guān)研究

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

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

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

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

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

2.1 模型假設(shè)

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

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

2.2 個(gè)體抽象

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

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

2.3 行為抽象

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

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

若l?M:

若d(st,)＞η:

若d(st,)≤η:

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

若l∈M:

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

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

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

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

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

(6)隨機(jī)行為:當(dāng)pi在嘗試了以上五種行為后，仍停留在原地，說(shuō)明陷入了局部最優(yōu)，此時(shí)，隨意選擇一個(gè)可行的方向進(jìn)行移動(dòng).

完成一輪迭代后，最終確定下一時(shí)間步的移動(dòng)位置Xn.

2.4 排隊(duì)機(jī)制的實(shí)現(xiàn)

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

2.5 位置沖突的解決

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

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

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

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

圖1 CA模型解決位置沖突

3 實(shí)驗(yàn)及結(jié)果分析

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

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

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

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

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

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

3.2 算法參數(shù)分析

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

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

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

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

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

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

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

3.3 實(shí)驗(yàn)及對(duì)比分析

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

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

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

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

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

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

圖4 三種模型的模擬效果

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

表2 兩種模型的疏散效果對(duì)比

4 結(jié)論與展望

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