交通流理論元胞自動機模型

交通流理論元胞自動機模型第一頁，共七十四頁，2022年，8月28日主要內容2元胞自動機的定義和構成3184號規(guī)則4NS模型簡介5BML模型簡介元胞自動機交通流模型6雙車道模型簡介1緒論第二頁，共七十四頁，2022年，8月28日1緒論StephenWolfram.ANewKindofScience.WolframMedia,2002.第三頁，共七十四頁，2022年，8月28日1緒論“三個世紀以前，人們發(fā)現建立在數學方程基礎上的規(guī)律能夠用于對自然界的描述，伴隨著這種新觀念，科學發(fā)生了轉變。在此書中我的目的是將要用簡單的電腦程序來表達更為一般類型的規(guī)律，并在此種規(guī)律基礎上建立一種新的科學，從而啟動另一場科學變革。”著名的物理學家、數學家和計算機科學家S.Wolfram以這樣的驚世之言開始了他的宏篇巨著《一種新科學》。Wolfram認為傳統科學未能建立起解釋宇宙復雜性的理論，靠數學方程做不到這一點。所以他要發(fā)動一場新的科學革命，革命的內容就是要用簡單的電腦程序取代數學方程。Wolfram所鐘情的這種簡單電腦程序的核心基礎就是我們將要介紹的元胞自動機。第四頁，共七十四頁，2022年，8月28日

元胞自動機（CellularAutomata，簡稱CA）實質上是定義在一個由具有離散、有限狀態(tài)的元胞組成的元胞空間上，并按照一定的局部規(guī)則，在離散的時間維度上演化的動力學系統。1緒論第五頁，共七十四頁，2022年，8月28日在元胞自動機中，空間被一定形式的規(guī)則網格分割為許多單元。這些規(guī)則網格中的每一個單元都稱為元胞(cell)，并且它只能在有限的離散狀態(tài)集中取值。所有的元胞遵循同樣的作用規(guī)則，依據確定的局部規(guī)則進行更新。大量的元胞通過簡單的相互作用而構成動態(tài)系統的演化。1緒論第六頁，共七十四頁，2022年，8月28日1緒論元胞自動機發(fā)展歷程20世紀50年代，JohnvonNeumann最早提出；(vonNeumann,J.1963，collectedworks,editedbyA.H.Taub)1970年，JohnConway提出生命游戲(Conway,J.(1970).InM.Gardner,(Ed.),ScientificAmerican,223(4),pp.120-123.)1983年，StephenWolfram初等元胞自動機

(StephenWolfram.ReviewsofModernPhysics,1983,Vol.55.StephenWolfram.Nature,1984,Vol.311)1986年至今，理論及應用

第七頁，共七十四頁，2022年，8月28日1緒論元胞自動機自產生以來，被廣泛地應用到社會、經濟、軍事和科學研究的各個領域。到目前為止，其應用領域涉及生物學、生態(tài)學、物理學、化學、交通科學、計算機科學、信息科學、地理、環(huán)境、社會學、軍事學以及復雜性科學等。

第八頁，共七十四頁，2022年，8月28日1緒論元胞自動機應用生物學領域：因為元胞自動機的設計思想本身就來源于生物學自繁殖的現象，所以它在生物學上的應用更為自然而廣泛。例如元胞自動機用于腫瘤細胞的增長機理和過程模擬、人類大腦的機理探索、愛滋病病毒HIV的感染過程、自組織、自繁殖等生命現象的研究以及最新流行的克隆(clone)技術的研究等。另外，元胞自動機還可以用來模擬植物的生長過程以及貝殼上的色素沉積圖案。第九頁，共七十四頁，2022年，8月28日1緒論元胞自動機應用生態(tài)學領域：元胞自動機被用于兔子-草，鯊魚-小魚等生態(tài)系統動態(tài)變化過程的模擬，展示出令人滿意的動態(tài)效果;元胞自動機還成功地應用于螞蟻的行走路徑，大雁、魚類洄游等動物的群體行為的模擬；另外，基于元胞自動機模型的生物群落的擴散模擬也是當前的一個應用熱點。第十頁，共七十四頁，2022年，8月28日1緒論元胞自動機應用物理學領域：在元胞自動機基礎之上發(fā)展出來的格子氣自動機(LGA)和格子-波爾茲曼方法(LBM)在計算流體領域獲得了巨大的成功。不僅能夠解決傳統流體力學計算方法所能解決的絕大多數問題，并且在多孔介質、多相流、微小尺度方面具有其獨特的優(yōu)越性。格子-波爾茲曼方法還被成功地應用于磁場、電場、熱擴散和熱傳導的模擬。另外，元胞自動機還被用來模擬雪花等枝晶的形成、液態(tài)金屬材料的凝固結晶過程以及顆粒材料的垮塌現象等。第十一頁，共七十四頁，2022年，8月28日1緒論元胞自動機應用交通科學領域：1986年，M.Cremer和J.Ludwig初次將元胞自動機運用到車輛交通的研究中。隨后，元胞自動機在車輛交通中的應用主要沿著兩條主線展開：對城市道路交通流的研究，以Nagel-Schreckenberg模型為代表;對城市交通網絡的研究，以BML模型為代表。另外，80年代以來，計算機水平日新月異的發(fā)展為元胞自動機的應用提供了強有力的支持。因此，在進入上個世紀90年代后，元胞自動機在交通流理論研究領域中得到了廣泛的應用。第十二頁，共七十四頁，2022年，8月28日1緒論元胞自動機應用計算機科學與信息學領域：元胞自動機的邏輯思維方法為并行機的發(fā)展提供了另一個理論框架。20世紀80年代，T.Toffoli和N.H.Margolus制造出第一臺通用元胞自動機計算機CAM6，其性能可與當時的巨型計算機相比擬，并且其圖形顯示功能明顯優(yōu)于其他類型的計算機。元胞自動機還被用來研究信息的保存、傳遞、擴散的過程。除此之外，元胞自動機在圖像處理和模式識別中也體現出了其獨到的優(yōu)勢。第十三頁，共七十四頁，2022年，8月28日

元胞自動機（CellularAutomata，簡稱CA）實質上是定義在一個由具有離散、有限狀態(tài)的元胞組成的元胞空間上，并按照一定的局部規(guī)則，在離散的時間維度上演化的動力學系統。元胞自動機的定義：2元胞自動機的定義和構成第十四頁，共七十四頁，2022年，8月28日2元胞自動機的定義和構成元胞自動機的構成：元胞自動機最基本的組成：元胞、元胞空間、鄰居及規(guī)則四部分。另外，還應包含狀態(tài)和時間。

可以視為由一個元胞空間和定義于該空間的變換函數所組成。第十五頁，共七十四頁，2022年，8月28日元胞自動機的構成示意圖2元胞自動機的定義和構成第十六頁，共七十四頁，2022年，8月28日元胞

元胞又可稱為單元、細胞或基元，是元胞自動機的最基本的組成部分。元胞分布在離散的一維、二維或多維歐幾里德空間的晶格點上。2元胞自動機的定義和構成第十七頁，共七十四頁，2022年，8月28日元胞狀態(tài)元胞的狀態(tài)可以是二進制形式，如：（0，1），（生，死），（黑、白）等；也可以在一個有限整數集內S內取值：如交通領域的CA模型中，有時元胞狀態(tài)可在[-(Vmax+1)～Vmax+1)]之間取值。狀態(tài)參量：嚴格意義上的CA只能有一個狀態(tài)參量；但是，在實際應用中，可以具有多個狀態(tài)參量。2元胞自動機的定義和構成第十八頁，共七十四頁，2022年，8月28日元胞空間元胞在空間中分布的空間格點的集合就是元胞空間。元胞空間的幾何劃分元胞空間的邊界條件2元胞自動機的定義和構成第十九頁，共七十四頁，2022年，8月28日元胞空間的幾何劃分理論上，它可以是任意維數的歐幾里德空間規(guī)則劃分。常用的元胞自動機一般是一維和二維的。

二維元胞自動機通常有三種劃分方式三角形正方形正六邊形

一維元胞自動機的元胞空間只有一種劃分2元胞自動機的定義和構成第二十頁，共七十四頁，2022年，8月28日二維元胞自動機的三種網格劃分2元胞自動機的定義和構成第二十一頁，共七十四頁，2022年，8月28日網格類型優(yōu)點缺點三角形擁有相對較少的鄰居數目，易于處理復雜邊界在計算機的表達與顯示不方便，需要轉換為四方網格。正方形直觀而簡單，而且特別適合于在現有計算機環(huán)境下進行表達顯示不能較好地模擬各向同性的現象正六邊形能較好地模擬各向同性的現象，因此，模型能更加自然而真實在表達顯示上較為困難、復雜三類網格劃分的優(yōu)缺點對比2元胞自動機的定義和構成第二十二頁，共七十四頁，2022年，8月28日元胞空間邊界條件理論上，元胞空間是無限的；實際應用中無法達到這一理想條件。常用的邊界條件如下：周期型定值型絕熱型反射型2元胞自動機的定義和構成第二十三頁，共七十四頁，2022年，8月28日元胞空間邊界條件周期型邊界條件（periodicboundary）定義：周期型是指相對邊界連接起來的元胞空間

對一維空間，首尾相接形成一個圓環(huán)對二維空間，上下相接，左右相接，而形成一個拓撲圓環(huán)面，形似車胎或甜點圈周期型空間與無限空間最為接近，因而在理論探討時，常以此類空間作為試驗。2元胞自動機的定義和構成第二十四頁，共七十四頁，2022年，8月28日元胞空間邊界條件定值型邊界條件(ConstantBoundary)定義：所有邊界外元胞均取某一固定常量絕熱型邊界條件(AdiabaticBoundary)定義：在指邊界外鄰居元胞的狀態(tài)始終和邊界元胞的狀態(tài)保持一致，即具有狀態(tài)的零梯度。2元胞自動機的定義和構成第二十五頁，共七十四頁，2022年，8月28日定義：在邊界外鄰居的元胞狀態(tài)是以邊界元胞為軸的鏡面反射。元胞空間邊界條件反射型邊界條件(ConstantBoundary)2元胞自動機的定義和構成第二十六頁，共七十四頁，2022年，8月28日構形(Configuration)定義：構形是在某個時刻，在元胞空間上所有元胞狀態(tài)的空間分布組合。在數學上，它通常可以表示為一個多維的整數矩陣。2元胞自動機的定義和構成第二十七頁，共七十四頁，2022年，8月28日鄰居(Neighbor)馮-諾依曼(Von.Neumann)型定義如下：分別表示鄰居元胞的行坐標和列坐標：分別表示中心元胞的行坐標和列坐標：鄰居的數目＝2元胞自動機的定義和構成第二十八頁，共七十四頁，2022年，8月28日鄰居(Neighbor)摩爾(Moore)型定義如下：鄰居的數目＝2元胞自動機的定義和構成第二十九頁，共七十四頁，2022年，8月28日鄰居(Neighbor)擴展的摩爾(Moore)型定義如下：鄰居的數目＝2元胞自動機的定義和構成第三十頁，共七十四頁，2022年，8月28日鄰居(Neighbor)馬哥勒斯(Margolus)型與前幾種鄰居的本質區(qū)別：以2×2的元胞塊為單元進行處理，而不是向前面幾種，對每個元胞分別處理。主要應用領域：格子氣流體，顆粒流等Margolus鄰居的表現形式和幾個演化規(guī)則2元胞自動機的定義和構成第三十一頁，共七十四頁，2022年，8月28日規(guī)則(Rule)根據元胞當前狀態(tài)及其鄰居狀況確定下一時刻該元胞狀態(tài)的動力學函數，簡單講，就是一個狀態(tài)轉移函數。稱f為元胞自動機的局部映射或局部規(guī)則2元胞自動機的定義和構成第三十二頁，共七十四頁，2022年，8月28日時間元胞自動機中的時間是離散的，是一系列的整數值，是一個無量綱的整數。若時間步長為dt=1,t=0為初始時刻，則t+1就為下一個時刻。2元胞自動機的定義和構成第三十三頁，共七十四頁，2022年，8月28日根據上面對元胞自動機的組成分析，我們可以更加深入地理解元胞自動機的概念?？梢詫⒃詣訖C概括為一個用數學符號來表示的四元組。A:代表一個元胞自動機系統；Ld：代表元胞空間；d：為空間維數；S：是元胞有限的離散的狀態(tài)集合；N：表示鄰域內所有元胞的組合（包括中心元胞在內）；f：是局部轉換函數，也就是規(guī)則。2元胞自動機的定義和構成第三十四頁，共七十四頁，2022年，8月28日1986年，Cremer和Ludwig初次將元胞自動機運用到車輛交通的研究中。交通流的元胞自動機模型大致可分為兩大類：研究高速公路交通的模型（以NS模型為代表）；研究城市網絡交通的模型（以BML模型為代表）這兩類模型是以Wolfram命名的184號模型為基礎發(fā)展而來的。3184號規(guī)則第三十五頁，共七十四頁，2022年，8月28日184號模型道路被劃分為等距格子，每個格點表示一個元胞；某個時刻，元胞或者是空的，或者被一輛車占據；所有車輛的行進方向都是一致的（如向右）；在每一個時間步內：若第n輛車的前方元胞是空的，則該車可以向前行駛一步；若前面的元胞被另一輛車n+1所占據，即使第n+1輛車在本時間步內離開此元胞，第n輛車也停在原地不動；整個系統采用周期性邊界條件以確保車輛數守恒。3184號規(guī)則第三十六頁，共七十四頁，2022年，8月28日10001110111110101100011010001000tt+1Rule184：3184號規(guī)則第三十七頁，共七十四頁，2022年，8月28日tt+1t+223+24+25+27=1843184號規(guī)則第三十八頁，共七十四頁，2022年，8月28日

作為對184號規(guī)則的推廣，Nagel和Schreckberg在1992年提出了一個模擬車輛交通的元胞自動機模型，即NS模型（也有人稱它為NaSch模型）。時間、空間和車輛速度都被整數離散化道路被劃分為等距離的離散的格子，即元胞每個元胞或者是空的，或者被一輛車所占據車輛的速度可以在（0～Vmax）之間取值4NS模型第三十九頁，共七十四頁，2022年，8月28日在時刻t到時刻t+1的過程中按照下面的規(guī)則進行更新：4NS模型第四十頁，共七十四頁，2022年，8月28日在時刻t到時刻t+1的過程中按照下面的規(guī)則進行更新：4NS模型第四十一頁，共七十四頁，2022年，8月28日更新過程圖示：4NS模型第四十二頁，共七十四頁，2022年，8月28日更新過程圖示：4NS模型第四十三頁，共七十四頁，2022年，8月28日更新過程圖示：4NS模型第四十四頁，共七十四頁，2022年，8月28日更新過程圖示：4NS模型第四十五頁，共七十四頁，2022年，8月28日邊界條件周期性邊界條件在每次更新結束后，我們要監(jiān)測道路上頭車的位置X_lead，如果X_lead>L_road，那么這兩車將從道路的另一端進入系統，變?yōu)榈缆飞系奈曹?，并且X_lead=X_lead-L_road,V_last=V_lead。開口邊界條件假設道路最左邊的元胞對應于X=1，并且道路的入口端包含V_max個元胞，也就是說，車輛可以從元胞(1,2,…,V_max)進入到道路中。在tt+1時刻，當道路上的車輛更新完成后，監(jiān)測道路上的頭車和尾車的位置X_lead和X_last。如果X_last>V_max，則一輛速度為V_max的車將以概率a進入元胞min[X_last-V_max,V_max]。在道路的出口處，如果X_lead>L_road，那么道路上的頭車以概率b駛出路段，而緊跟其后的第二輛車成為新的頭車。4NS模型第四十六頁，共七十四頁，2022年，8月28日與184號模型相比，NS模型的主要改進之處是引入了慢化概率和最大車速不再是1。NS模型雖然具有十分簡單的形式，但卻可以描述一些實際交通現象。比如NS模型可以模擬出自發(fā)產生的堵塞現象以及擁擠交通情況下的時走時停波等。4NS模型第四十七頁，共七十四頁，2022年，8月28日堵塞的形成4NS模型第四十八頁，共七十四頁，2022年，8月28日時走時停波4NS模型第四十九頁，共七十四頁，2022年，8月28日模擬結果：d=0.05,p=0.34NS模型第五十頁，共七十四頁，2022年，8月28日模擬結果：d=0.1,p=0.34NS模型第五十一頁，共七十四頁，2022年，8月28日模擬結果：d=0.2,p=0.34NS模型第五十二頁，共七十四頁，2022年，8月28日模擬結果：d=0.4,p=0.34NS模型第五十三頁，共七十四頁，2022年，8月28日模擬結果：d=0.8,p=0.34NS模型第五十四頁，共七十四頁，2022年，8月28日模擬結果：d=0.2，p=04NS模型第五十五頁，共七十四頁，2022年，8月28日NS模型的衍生和發(fā)展以NS模型為基礎，研究者主要做了以下三個方面的工作理論方面為了能夠模擬出交通實測中的各種現象，他們提出了各種各樣的改進模型。如通過改進慢化規(guī)則，提出慢啟動模型，巡航控制極限(CruiseControlLimit)模型，密度相關的慢啟動概率模型；通過改進加速規(guī)則，提出Fukui-Ishibashi(FI)模型；以及考慮前車速度效應的模型，三相交通狀態(tài)模型，舒適駕駛模型等等。4NS模型第五十六頁，共七十四頁，2022年，8月28日NS模型的衍生和發(fā)展理論方面他們對元胞自動機模型(主要是NS模型及FI模型)做了相關的解析分析(主要是平均場分析)，加深了人們對元胞自動機模型的理解。引入換道規(guī)則用來模擬多車道可以超車的情況，考察了雙向交通情況.4NS模型第五十七頁，共七十四頁，2022年，8月28日NS模型的衍生和發(fā)展應用方面利用NS模型對大型交通系統的模擬近年來取得了可喜的進展。到目前，NS模型已經應用于美國城市智能交通項目TRANSIMS，杜伊斯堡的內城交通，達拉斯/福斯-華斯地區(qū)的交通規(guī)劃，以及北萊茵-魏斯特伐利亞地區(qū)的交通公路網中。4NS模型第五十八頁，共七十四頁，2022年，8月28日NS模型及其衍生和發(fā)展介于理論和應用之間利用NS模型操作靈活簡單易行的特點，考察了各種交通瓶頸對交通的影響。一方面發(fā)現了一些新的物理現象，另一方面又為交通工程建設及交通管理規(guī)則的制定提供了合理建議和科學依據。4NS模型第五十九頁，共七十四頁，2022年，8月28日/applets/RoadApplet/RoadApplet.html/~mm/traffic/ca.htmlhttp://bolay.de/kai/RoadApplet/4NS模型第六十頁，共七十四頁，2022年，8月28日BML模型1992年，Biham,Middleton,Levine提出了第一個