1、基于一維交通流元胞自動(dòng)機(jī)計(jì)算機(jī)編程模擬【摘要】主要介紹了元胞自動(dòng)機(jī)的特點(diǎn)及定義,元胞自動(dòng)機(jī)在道路交通流模擬中的應(yīng)用,設(shè)計(jì)了交通元胞自動(dòng)機(jī)的結(jié)構(gòu),建立了運(yùn)用元胞自動(dòng)機(jī)的交通流模擬模型, 運(yùn)用C語(yǔ)言編程實(shí)現(xiàn)模擬,并利用Matlab得到流率與交通密度的關(guān)系;探討了元胞自動(dòng)機(jī)在道路交通流模擬中應(yīng)用前景?！娟P(guān)鍵詞】一維交通流；元胞自動(dòng)機(jī); C語(yǔ)言編程;模擬一、引言1992年,Nagel-Schreckenberg采用元胞自動(dòng)機(jī)模擬公路交通流,從此以后,相繼有許多研究機(jī)構(gòu)開始了交通元胞自動(dòng)機(jī)的研究,并已有許多研究成果及相關(guān)模擬軟件產(chǎn)生。元胞自動(dòng)機(jī)(Cellular Automata,簡(jiǎn)稱CA)是一種時(shí)間和

2、空間都離散的動(dòng)力系統(tǒng)模型。散布在柵格(Lattice Grid)中的每一元胞(Cell)取有限的離散狀態(tài),遵循同樣的作用規(guī)則,依據(jù)確定的局部規(guī)則作同步更新,大量元胞通過(guò)簡(jiǎn)單的相互作用而構(gòu)成動(dòng)態(tài)系統(tǒng)的演化。不同于一般的動(dòng)力學(xué)模型,元胞自動(dòng)機(jī)不是由嚴(yán)格定義的物理方程或函數(shù)確定,而是用一系列模型構(gòu)造的規(guī)則構(gòu)成。凡是滿足這些規(guī)則的模型都可以算作是元胞自動(dòng)機(jī)。因此,元胞自動(dòng)機(jī)是一類模型的總稱,或者說(shuō)是一個(gè)方法框架。其特點(diǎn)是時(shí)間、空間、狀態(tài)都離散,每個(gè)變量只取有限多個(gè)狀態(tài),且其狀態(tài)改變的規(guī)則在時(shí)間和空間上都是局部的。二、元胞自動(dòng)機(jī)介紹、元胞自動(dòng)機(jī)在元胞自動(dòng)機(jī)的發(fā)展過(guò)程中,許多學(xué)者構(gòu)造了不同的模型。本文主要

3、介紹交通流模擬常用的初等元胞自動(dòng)機(jī),又稱Wolfram元胞自動(dòng)機(jī)。初等元胞自動(dòng)機(jī)(Elementary Cellular Automata,簡(jiǎn)稱E-CA)是狀態(tài)集S只有兩個(gè)元素s1,s2,即狀態(tài)個(gè)數(shù)k=2,鄰居半徑r=1的一維元胞自動(dòng)機(jī)。2、元胞自動(dòng)機(jī)的構(gòu)成元胞自動(dòng)機(jī)最基本的組成是元胞、元胞空間、鄰居及規(guī)則四部分。即元胞自動(dòng)機(jī)是由一個(gè)元胞空間和定義于該空間的變換函數(shù)所組成的。（）元胞元胞又可稱為單元或基元,是元胞自動(dòng)機(jī)的最基本的組成部分。元胞分布在離散的一維或二維歐幾里德空間的晶格點(diǎn)上。（）狀態(tài)狀態(tài)可以是0,1的二進(jìn)制形式。或是s0,s1,sk整數(shù)形式的離散集。對(duì)于一維元胞自動(dòng)機(jī),定義元胞的兩

4、個(gè)狀態(tài),即0,1。（）元胞空間元胞分布的空間網(wǎng)點(diǎn)集合就是所謂的元胞空間。元胞空間的幾何劃分:理論上,它可以是任意維數(shù)的歐幾里德空間規(guī)則劃分。目前研究多集中在一維和二維元胞自動(dòng)機(jī)上。對(duì)于一維元胞自動(dòng)機(jī),元胞空間的劃分只有一種。邊界條件:在理論上,元胞空間在各維上是無(wú)限的。但是在實(shí)際應(yīng)用過(guò)程中,無(wú)法在計(jì)算機(jī)上實(shí)現(xiàn)這一理想條件,因此,需要定義不同的邊界條件。構(gòu)形:構(gòu)形是指某個(gè)時(shí)刻,元胞空間上所有元胞狀態(tài)的空間分布組合。通常,在數(shù)學(xué)上,它可以表示為一個(gè)多維的整數(shù)矩陣。（）鄰居以上的元胞及元胞空間只表示了系統(tǒng)的靜態(tài)成分,為將動(dòng)態(tài)引入系統(tǒng),必須加入演化規(guī)則。在元胞自動(dòng)機(jī)中,這些規(guī)則是定義在局部空間范圍內(nèi)的

5、,即一個(gè)元胞下一時(shí)刻的狀態(tài)取決于其本身狀態(tài)和它的鄰居元胞的狀態(tài)。因而,在指定規(guī)則之前,必須定義一定的鄰居規(guī)則,明確哪些元胞屬于該元胞的鄰居。在一維元胞自動(dòng)機(jī)中,通常以半徑來(lái)確定鄰居,距離一個(gè)元胞內(nèi)的所有元胞均被認(rèn)為是該元胞的鄰居。3、規(guī)則根據(jù)元胞當(dāng)前狀態(tài)及其鄰居狀況確定下一時(shí)刻該元胞狀態(tài)的動(dòng)力學(xué)函數(shù),即一個(gè)狀態(tài)轉(zhuǎn)移函數(shù)。將一個(gè)元胞的所有可能狀態(tài)連同負(fù)責(zé)該元胞的狀態(tài)變換的規(guī)則一起稱為一個(gè)變換函數(shù)。這個(gè)函數(shù)構(gòu)造了一種簡(jiǎn)單的、離散的空間/時(shí)間的局部物理成分。、時(shí)間元胞自動(dòng)機(jī)是一個(gè)動(dòng)態(tài)系統(tǒng),它在時(shí)間維上的變化是離散的,即時(shí)間t是一個(gè)整數(shù)值,而且連續(xù)等間距。假設(shè)時(shí)間間距dt=1,若t=0為初始時(shí)刻,t=

6、1為其下一時(shí)刻。在上述轉(zhuǎn)換函數(shù)中,一個(gè)元胞在t+1時(shí)刻的狀態(tài)只決定于t時(shí)刻的該元胞及其鄰居元胞的狀態(tài)。三、一維交通元胞自動(dòng)機(jī)的設(shè)計(jì)、元胞空間的離散一維交通元胞自動(dòng)機(jī)適宜于單車道交通流的模擬,為此以車輛行駛時(shí)所占道路長(zhǎng)度(包括安全間距)l為單位,將長(zhǎng)度為L(zhǎng)的道路均勻劃分成連續(xù)的柵格,構(gòu)成元胞空間,形成一列元胞。、模擬時(shí)間的離散假定模擬總時(shí)間為T,在該時(shí)間空間上,以時(shí)間間距dt推進(jìn)模擬時(shí)間,當(dāng)dt=1時(shí),從t=0初始時(shí)間開始,依次順序加1,推進(jìn)模擬時(shí)間,直至模擬結(jié)束。3、狀態(tài)定義元胞狀態(tài)為0,1,其中1表示該元胞為有車狀態(tài),0表示該元胞為無(wú)車狀態(tài)。且車輛的運(yùn)行方向是相同的。4、鄰居對(duì)于單車道交通流

7、的模擬,可假設(shè)元胞t+1的狀態(tài)僅受到其最近的鄰居元胞的狀態(tài)及該元胞t時(shí)刻狀態(tài)的影響。因此其鄰居半徑取為r=1。5、動(dòng)態(tài)進(jìn)化規(guī)則一維交通元胞自動(dòng)機(jī)狀態(tài)更新規(guī)則實(shí)際上是Wolfram規(guī)則的擴(kuò)展,統(tǒng)稱為規(guī)則184。(1)Wolfram規(guī)則根據(jù)實(shí)際的交通流變化,對(duì)于實(shí)際的單車道交通流模擬而言,可設(shè)計(jì)初等元胞自動(dòng)機(jī)的一個(gè)規(guī)則如右表所示 (黑色方塊代表1,白色方塊代表0)。這樣,對(duì)于任何一個(gè)一維的0,1序列,應(yīng)用以上規(guī)則,可以產(chǎn)生下一時(shí)刻的相應(yīng)的序列。以下序列就是應(yīng)用以上規(guī)則產(chǎn)生的:t:t+1:選擇鄰居半徑r=1,由此確定狀態(tài)轉(zhuǎn)移函數(shù)f為:0,0,00;0,0,10;0,1,01;1,0,00;0,1,1

8、1;1,0,10;1,1,00;1,1,10。顯然規(guī)則表達(dá)了車輛運(yùn)動(dòng)狀態(tài)的變化, 稱為運(yùn)動(dòng)規(guī)則。由于交通模擬不僅要考慮車輛的運(yùn)動(dòng)狀態(tài)的變化,而且需考慮其速度狀態(tài)的轉(zhuǎn)化,由此以上的運(yùn)動(dòng)規(guī)則可以表達(dá)為半徑為1的速度規(guī)則:110,101符號(hào)表示元胞處于有車或無(wú)車狀態(tài)。(2)一維交通元胞自動(dòng)機(jī)狀態(tài)更新規(guī)則在規(guī)則184的基礎(chǔ)上,假定車輛有幾種可能的速度,u=0,1,2,umax,設(shè)ui為車i的速度,di為車i與車i+1間的間距。按速度規(guī)則,系統(tǒng)更新步驟為:步驟1可能的加速:如果uidi,則uidi-1;步驟3隨機(jī)變速:如果ui0,服從于概率pi,使uiui=ui-1;步驟4車輛向前移動(dòng)ui個(gè)元胞。對(duì)于一

9、維交通元胞自動(dòng)機(jī)umax可取1,從而通過(guò)模擬確定交通量、速度、密度三者之間的關(guān)系。上述的交通元胞自動(dòng)機(jī)可以應(yīng)用到交通系統(tǒng)的研究中。如采用交通元胞自動(dòng)機(jī),更直觀地考察不同交通密度的交通流特性,便于分析和理解。四、單車道交通流元胞自動(dòng)機(jī)模擬模型建立交通模型的根本目的就是要以足夠的精確度來(lái)再現(xiàn)客觀的交通現(xiàn)象,在進(jìn)行交通微觀模擬的過(guò)程中,以元胞自動(dòng)機(jī)理論為主要的理論基礎(chǔ),全面構(gòu)造車輛的到達(dá),在路段上的自由行駛、跟駛和緊急減速等各種運(yùn)行狀態(tài)的運(yùn)行規(guī)則。這里的交通模型主要包括兩個(gè)部分:一是車輛產(chǎn)生模型;二是車輛行駛模型。車輛產(chǎn)生模型實(shí)際上就是將交通流的輸入部分,作用于被模擬路段的起始斷面,它依靠隨機(jī)數(shù)技術(shù)

10、產(chǎn)生符合已給定概率分布的車輛的狀態(tài)屬性以及交通流參數(shù)以此向系統(tǒng)提供初值。車輛行駛模型即是反映車輛在路段上行駛時(shí)狀態(tài)變化過(guò)程的模型,即元胞自動(dòng)機(jī)模型。、模擬基本參數(shù)道路長(zhǎng)度:L=7500m;元胞長(zhǎng)度:l=7.5m;元胞數(shù)目:n=1000個(gè);最大車速:Vmax=5元胞長(zhǎng)度/s=57.5 m/s=135 km/h;模擬總時(shí)間:T=10000 s(總運(yùn)行步長(zhǎng));時(shí)間步長(zhǎng):dt=1s;定義隨機(jī)減速概率:p=0.5。、車輛的隨機(jī)產(chǎn)生本文的隨機(jī)車輛產(chǎn)生是依據(jù)泊松分布原理的斷面發(fā)車模型。通過(guò)對(duì)相關(guān)資料提供的車流數(shù)據(jù)的分析與實(shí)地觀察數(shù)據(jù),在城區(qū)、市郊、高速公路等車輛通行較為頻繁的地方,車流到達(dá)情況接近均勻的波峰

11、分布。在此選用常用、簡(jiǎn)單的概率分布泊松分布來(lái)表示交通流的分布情況。由于泊松分布的變異系數(shù)為D(x)/E(x)=I,則根據(jù)變異系數(shù)定義,該分布的概率曲線集中度比較均勻,能體現(xiàn)均勻分布。如公式:Pt*(n)=2/n!e- (1)其中:n為車輛數(shù);為參數(shù)根據(jù)實(shí)驗(yàn)采集數(shù)據(jù)方式得:式(1)中的參數(shù)有相應(yīng)的物理意義,表示在采樣時(shí)間t*內(nèi)的車輛數(shù)。令=at*,則a表示車輛平均到達(dá)率(veh/s),則泊松分布公式(1)轉(zhuǎn)化為:Pn(t*)=(at*)n/n!e-at* (2)式(2)表示的物理意義是:在時(shí)間區(qū)段t*內(nèi)有n輛車進(jìn)入模擬路段的可能性為Pn(t*)。通過(guò)在實(shí)際的車道上找一斷面,然后固定采樣時(shí)間測(cè)量通

12、過(guò)此斷面的車輛數(shù)。由實(shí)際測(cè)量的數(shù)據(jù)分析得出車輛產(chǎn)生率的期望。在本文中隨機(jī)取一個(gè)經(jīng)驗(yàn)值：a=0.5。在基于泊松分布原理而建立斷面發(fā)車模型時(shí),重要的是利用概率統(tǒng)計(jì)原理,確定出發(fā)車模型的相關(guān)參數(shù),從而建立具體的發(fā)車模型。如圖1所示。圖1服從泊松分布的車輛產(chǎn)生3、車速的隨機(jī)分布產(chǎn)生入口發(fā)車時(shí)不僅要產(chǎn)生發(fā)車時(shí)刻,也要對(duì)發(fā)車的速度賦初值,理論研究證明車速一般服從正態(tài)分布或?qū)?shù)正態(tài)分布。這里主要介紹了服從正態(tài)分布的隨機(jī)車速的產(chǎn)生。正態(tài)分布的分布函數(shù)F(x)為: Fx=PXx=-12exp-12t-u2dt (3)由于上式無(wú)法積分得到顯式,故不能進(jìn)行逆變,而采用函數(shù)變換法。當(dāng)XN(0,1)時(shí),Y=X+N(,

13、2)因此先考慮生成標(biāo)準(zhǔn)正態(tài)分布N(0,1)的隨機(jī)變量。采用Box-Muller的函數(shù)變換法,只要產(chǎn)生兩個(gè)均勻分布的隨機(jī)數(shù)u1和u2即可產(chǎn)生兩個(gè)服從標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)變量w1和w2,即: w1=-2ln(u2)sin(2u1) (4) W2=-2lnu2cos2u1 (5)其產(chǎn)生正態(tài)分布隨機(jī)變量的程序流程圖見圖2。 、模型基本規(guī)則產(chǎn)生階段:以按發(fā)車概率在起始空格點(diǎn)產(chǎn)生不同速度的車輛,相當(dāng)于不同速度的車輛進(jìn)入車道占圖2 服從正態(tài)分布變量的程序流程圖據(jù)不同的空格子; 加速規(guī)則:如果當(dāng)前車輛速度V(t)Vmax,則車輛加速:V(t+1)=min(Vmax,V+1);減速規(guī)則:如果一輛車到它前面最近鄰的

14、另一輛車的距離gapV,則車輛減速為V(t+1)=gap;隨機(jī)慢化規(guī)則:在概率p下,在加速和減速規(guī)則下得到的速度減1,即:V(t+1)=max(V(t+1)-1,0)運(yùn)動(dòng)階段:各車輛以自己的速度向前運(yùn)動(dòng):X(t+1)=X(t)+V(t+1)轉(zhuǎn)出階段:如果車輛運(yùn)動(dòng)到終點(diǎn)格子處時(shí),它代表車輛的轉(zhuǎn)出。加速規(guī)則反映了司機(jī)有追求最大速度的愿望,減速規(guī)則即避免碰撞是為了避免與前車發(fā)生碰撞,隨機(jī)慢化規(guī)則考慮了不同駕駛者的個(gè)體行為,隨機(jī)化參數(shù)p同駕駛行為的三種特性有關(guān):最大速度時(shí)的速度波動(dòng);制動(dòng)時(shí)減速的過(guò)度反應(yīng);加速時(shí)的延遲。以上演化步驟作為一個(gè)周期反復(fù)進(jìn)行下去,它實(shí)際上描述了較為接近實(shí)際的高速公路上車輛的運(yùn)

15、動(dòng)狀況。五、計(jì)算機(jī)編程模擬、單車道交通流模擬模型流程圖基于上述的一維單車道交通元胞自動(dòng)機(jī),按照元胞自動(dòng)機(jī)規(guī)則確定的路段上的所有車輛運(yùn)動(dòng)狀態(tài)的程序如圖3所示。圖3單車道交通流元胞自動(dòng)機(jī)模擬模型流程圖、程序設(shè)計(jì)）隨機(jī)數(shù)發(fā)生器double schrage(int a,int m,int b)/隨機(jī)數(shù)發(fā)生器,直接返回隨機(jī)數(shù)0,1int q,r;double z;q=m/a;r=m%a;I=a*(I%q)-r*(I/q);if(I0)I=I+m;z=(double)I/m;return z;2)隨機(jī)車輛產(chǎn)生子程序int car()int flag;if(schrage(16807,0)0.5)flag=

16、1;else flag=0;return(flag);3)速度更新規(guī)則for(i=0;in;i+)if(vigapi&vi=gapi)vi=gapi;/隨機(jī)減速for(i=0;in;i+)if(schrage(16807,0)0.5)/隨機(jī)慢化概率:p=0.5vi=vi-1;/車速隨機(jī)慢化規(guī)則4)車輛位置更新for(i=0;in;i+)ai=ai+vi;3、模擬結(jié)果和討論根據(jù)以上模型模擬,運(yùn)用C語(yǔ)言編程實(shí)現(xiàn)模擬,并利用matlab,可以得到流量與交通密度之間的關(guān)系如圖4。分析圖中的曲線陡變?cè)?主要是因?yàn)殡S著車輛數(shù)的增加,在道路上車輛的密度增大,車輛之間的間距變小,車輛之間的相互影響加劇,模型

17、中的規(guī)則全部產(chǎn)生作用。在車輛密度較小時(shí),車輛是自由運(yùn)動(dòng),隨時(shí)間的增加,車輛向前行駛位置與時(shí)間是線性關(guān)系,即車輛勻速行駛。當(dāng)車輛密度增大時(shí),車輛自由運(yùn)動(dòng)的程度減小,隨時(shí)間的增加,出現(xiàn)了車輛聚集的阻塞相,位置與時(shí)間變?yōu)榱朔蔷€性關(guān)系,車輛位置分布是非均勻的,有的區(qū)域車輛密集,有的區(qū)域沒有車輛,車流的運(yùn)動(dòng)相與阻塞相交替出現(xiàn),非常類似于波的波峰和波谷的傳播。圖4交通密度的關(guān)系六、交通元胞自動(dòng)機(jī)的發(fā)展計(jì)算機(jī)技術(shù)的不斷發(fā)展,使得元胞自動(dòng)機(jī)在交通宏觀及微觀模擬方面的研究和應(yīng)用會(huì)越來(lái)越廣泛,前景十分廣闊。交通系統(tǒng)即是一個(gè)時(shí)間、空間離散的、復(fù)雜的大系統(tǒng),系統(tǒng)的特性受到人車路等多方面因素的影響,有時(shí)傳統(tǒng)的研究方法難以研究和解析某些交通現(xiàn)象,難以揭示其中的規(guī)律,顯然可以利用元胞自動(dòng)機(jī)研究交通流特性。結(jié)合道路交通的特點(diǎn),研究元胞自動(dòng)機(jī)在交通模擬仿真方面的應(yīng)用,有助于交通系統(tǒng)