第十一章 元胞自動機(jī)理論

1、12022-4-27第十一章第十一章元胞自動機(jī)理論元胞自動機(jī)理論及其應(yīng)用及其應(yīng)用22022-4-27參考文獻(xiàn)：nStephen Wolfram，A New Kind of Science，Wolfram Media, Inc., 2002 n高原等，細(xì)胞自動機(jī)的多重分形特征和動力學(xué)根源，西北地震學(xué)報(bào)，1995，4n何越磊，鐵路選線中的元胞自動機(jī)模型，蘭州交通大學(xué)學(xué)報(bào)，2004/0132022-4-27n1. .元胞自動機(jī)的定義元胞自動機(jī)的定義n2.2.初等元胞自動機(jī)初等元胞自動機(jī)n3.3.交通流的元胞自動機(jī)模型交通流的元胞自動機(jī)模型n4.4.火災(zāi)逃生的元胞自動機(jī)模型火災(zāi)逃生的元胞自動機(jī)模型42

2、022-4-27典型應(yīng)用：n交通流模擬n火災(zāi)逃生、人員疏散模型n森林火災(zāi)模型n城市、農(nóng)村土地利用演化模擬n社會學(xué)、生物學(xué)、生態(tài)學(xué)、信息科學(xué)、計(jì)算機(jī)科學(xué)、數(shù)理化 52022-4-27 1. 1. 元胞自動機(jī)模型元胞自動機(jī)模型n元胞自動機(jī)元胞自動機(jī)(Cellular Automata，簡稱，簡稱CA)是一個是一個時間時間和和空間空間都離散的動力系統(tǒng)。散布在規(guī)則格網(wǎng)都離散的動力系統(tǒng)。散布在規(guī)則格網(wǎng) 中的每一元胞中的每一元胞取有限的離散狀態(tài)，遵循同樣的規(guī)則作同步更新。取有限的離散狀態(tài)，遵循同樣的規(guī)則作同步更新。n大量元胞通過簡單的相互作用而構(gòu)成動態(tài)系統(tǒng)的大量元胞通過簡單的相互作用而構(gòu)成動態(tài)系統(tǒng)的演化演

3、化。不。不同于一般的動力學(xué)模型，元胞自動機(jī)不是由嚴(yán)格定義的方同于一般的動力學(xué)模型，元胞自動機(jī)不是由嚴(yán)格定義的方程或函數(shù)確定，而是用一系列的程或函數(shù)確定，而是用一系列的規(guī)則規(guī)則構(gòu)成。構(gòu)成。n凡是滿足這些規(guī)則的模型都可以算作是元胞自動機(jī)模型。凡是滿足這些規(guī)則的模型都可以算作是元胞自動機(jī)模型。因此，元胞自動機(jī)是一類模型的總稱，或者說是一個方法因此，元胞自動機(jī)是一類模型的總稱，或者說是一個方法框架。其特點(diǎn)是時間、空間、狀態(tài)都離散，每個變量只取框架。其特點(diǎn)是時間、空間、狀態(tài)都離散，每個變量只取有限多個狀態(tài)，且其狀態(tài)改變的規(guī)則在時間和空間上都是有限多個狀態(tài)，且其狀態(tài)改變的規(guī)則在時間和空間上都是局部的。局部

4、的。62022-4-272.2.初等元胞自動機(jī)n初等元胞自動機(jī)是狀態(tài)集S只有兩個元素s1，s2，即狀態(tài)個數(shù)k=2，鄰居半徑r=1的一維元胞自動機(jī)。它是最簡單的元胞自動機(jī)模型。由于在S中具體采用什么符號并不重要，它可取 0，1，-1，1，靜止，運(yùn)動 等等，重要的是S所含的符號個數(shù)，通常我們將其記為 0，1。此時，鄰居集N的個數(shù)2r=2，局部映射f：S3S可記為:111(,)ttttiiiiSf SS S72022-4-27n初等元胞自動機(jī)是狀態(tài)集S只有兩個元素s1，s2，即狀態(tài)個數(shù)k=2，鄰居半徑r=1的一維元胞自動機(jī)。它是最簡單的元胞自動機(jī)模型。由于在S中具體采用什么符號并不重要，它可取 0，

5、1，-1，1，靜止，運(yùn)動 等等，重要的是S所含的符號個數(shù)，通常我們將其記為 0，1。此時，鄰居集N的個數(shù)2r=2，局部映射f：S3S可記為:111(,)ttttiiiiSf SS S2.2.初等元胞自動機(jī)82022-4-27由于只有0、1兩種狀態(tài)，所以函數(shù)f共有28=256種狀態(tài)。t111110101100001010001 000t+101001 100S. Wolfram的初等元胞自動機(jī)的初等元胞自動機(jī) 92022-4-27nThree centuries ago science was transformed by the dramatic new idea that rules bas

6、ed on mathematical equations could be used to describe the natural world. My purpose in this book is to initiate another such transformation, and to introduce a new kind of science that is based on the much more general types of rules that can be embodied in simple computer programs. 詳見：詳見：Free onli

7、ne access:http:/ t111110 101100011010001000 t+100001110000011000011100001110000111000101101100111010001rule 1rule 2rule 3rule 4rule 184rule 255rule 256112022-4-273. 交通流的元胞自動機(jī)模型交通流的元胞自動機(jī)模型特別注意：特別注意：第第184號規(guī)則號規(guī)則車輛行駛規(guī)則為：黑色元胞表示被一輛車占據(jù)，白色表示無車，若前方格子有車，則停止。若前方為空，則前進(jìn)一格。t111110101100011010001000t+1101110001992

8、年，德國學(xué)者Nagel和Schreckenberg在第184號規(guī)則提出了一維交通流CA模型，即，NS 模型（或NaSch模型）122022-4-27nNS 模型是一個隨機(jī)CA交通流模型，每輛車的狀態(tài)都由它的速度和位置所表示，其狀態(tài)按照以下演化規(guī)則并行更新 ： na) 加速過程 nb）安全剎車過程 nc）隨機(jī)慢化過程 （以隨機(jī)慢化概率p） nd）位置更新nnnxxvm a x (1, 0 )nnvvmin(,1)nnnvvdmaxmin(1,)nnvvv其中：L-車輛長度7.5m1nnndxxL132022-4-27a）加速過程 b）安全剎車過程 c）隨機(jī)慢化過程（以隨機(jī)慢化概率p）d）位置更新

9、142022-4-27n在NS 模型的基礎(chǔ)上，又陸續(xù)地提出了一系列一維CA交通模型，如TT、BJH、VDR、FI等模型；n雙車道CA交通模型：STNS模型n機(jī)非混合CA模型： CCA模型n城市路網(wǎng)CA模型： BML、CTM模型Los Alamos National Laboratory： TRANSIMS (TRansportation ANalysis SIMulation System) 詳見：賈斌，高自友，基于元胞自詳見：賈斌，高自友，基于元胞自動機(jī)的交通系統(tǒng)建模與模擬，科學(xué)動機(jī)的交通系統(tǒng)建模與模擬，科學(xué)出版社，出版社，2007-10 152022-4-27高速公路自發(fā)形成的堵塞航拍圖，

10、1975年162022-4-27隨機(jī)慢化概率p=0.2；密度=13.3veh/km/lan（0.1）； 172022-4-27隨機(jī)慢化概率p=0.2；密度=20veh/km/lan（0.15）； 182022-4-27隨機(jī)慢化概率p=0.2；密度=27veh/km/lan（0.2）； 192022-4-27隨機(jī)慢化概率p=0.2；密度=33veh/km/lan（0.25）； 202022-4-274.4.火災(zāi)逃生的元胞自動機(jī)模型火災(zāi)逃生的元胞自動機(jī)模型n（1）元胞的劃分n（2）鄰域空間n（3）元胞狀態(tài)n（4）元胞狀態(tài)變化的規(guī)則212022-4-27（1）元胞的劃分n火災(zāi)的發(fā)生均是在一定區(qū)域中，

11、因此火災(zāi)逃生區(qū)域是一個二維的空間。在模型中，將所研究的二維空間按矩形方式進(jìn)行均勻的網(wǎng)格劃分，每個格點(diǎn)即為元胞，所有元胞共同構(gòu)成了元胞空間。n在模型中，將每個元胞的大小劃分為只能容納一個人的大小，如0.4m 0.4m。這是密集人流中的典型的人員空間分配。222022-4-27（2）鄰域空間n在一個給定的元胞點(diǎn)陣中，規(guī)定每個元胞在計(jì)算自己的下一個狀態(tài)時所考察的鄰域。n模擬火災(zāi)逃生的正方形網(wǎng)格空間下, 選擇兩種鄰域形式。n（a）由Von. Neumann限定每個元胞只注意它四個最臨近的元胞,即上、下、左、右四個鄰居。n（b）由Moore鄰域除了包含元胞的四個鄰居外,還包含另外四個對角的次臨近元胞。2

12、32022-4-27n這兩種鄰域的形式實(shí)際上是火災(zāi)逃生中人員的視野概念。隨著人員視野的擴(kuò)大,其對當(dāng)前時間步運(yùn)動方向的確定就可以按照下一時間步的最優(yōu)選擇來進(jìn)行。此外,視野還可以用來模擬人員在火災(zāi)中由于煙氣存在而導(dǎo)致的視力范圍縮小等問題。242022-4-27（3）元胞狀態(tài)n在元胞空間中, 每個元胞有兩種狀態(tài)：一是被人占據(jù)，另一種空，沒有人員。在數(shù)學(xué)公式里，元胞的狀態(tài)數(shù)就是Si 可能的取值數(shù)，或叫做它的域。n所有元胞的狀態(tài)是同時發(fā)生變化的，在時刻t+1的第i個元胞的狀態(tài)是由時刻 t 的第 i個元胞以及相鄰的距離不超過r的 2r個元胞的狀態(tài)決定的。252022-4-27n(4) 元胞狀態(tài)變化的規(guī)則n元胞下一時間的狀態(tài)主要有兩個并行的變更階段。第一個階段是目標(biāo)格點(diǎn)的選擇,每個人員在本身所在格點(diǎn)及