元胞自動(dòng)機(jī)的基礎(chǔ)理論主講人：賈斌Email:bjia@第二章經(jīng)典的元胞自動(dòng)機(jī)2.1S.Wolfram和初等元胞自動(dòng)機(jī)初等元胞自動(dòng)機(jī)(ElementaryCellularAutomata)是狀態(tài)集S只有兩個(gè)元素{s1，s2}，即狀態(tài)個(gè)數(shù)k=2，鄰居半徑r=l的一維元胞自動(dòng)機(jī)。它幾乎是最簡(jiǎn)單的元胞自動(dòng)機(jī)模型。由于在S中具體采用什么符號(hào)并不重要，它可取{0，1}，{-l，1}，{靜止，運(yùn)動(dòng)}，{黑，白}，{生，死}等等，這里重要的是S所含的符號(hào)個(gè)數(shù)，通常我們將其記為{0，1}

Wolfram的初等元胞自動(dòng)機(jī)對(duì)初等元胞自動(dòng)機(jī)，鄰居個(gè)數(shù)N=2×r，這樣局部映射就可以寫成下面的形式映射函數(shù)中含有三個(gè)狀態(tài)變量，每個(gè)狀態(tài)變量有2種狀態(tài)，所以總共有如下8種組合方式：111110101100011010001000也可以寫為：Wolfram的初等元胞自動(dòng)機(jī)2.1.1Wolfram對(duì)一維元胞自動(dòng)機(jī)的標(biāo)號(hào)111110101100011010001000t21或021或021或021或021或021或021或021或0t+1可見(jiàn)，總共有28=256種情況，也就是說(shuō)有256種規(guī)則Wolfram的初等元胞自動(dòng)機(jī)2.1.1Wolfram對(duì)一維元胞自動(dòng)機(jī)的標(biāo)號(hào)假設(shè)一個(gè)元胞所具有的狀態(tài)數(shù)為k，所采用的鄰居半徑為r（即鄰域中含有2r+1個(gè)元胞），這樣可能的輸入條件就有：總的可能規(guī)則數(shù)為：可能規(guī)則數(shù)的計(jì)算方法：Wolfram的初等元胞自動(dòng)機(jī)2.1.1Wolfram對(duì)一維元胞自動(dòng)機(jī)的標(biāo)號(hào)11111010110001101000100000111011tt+1示例:Wolfram的初等元胞自動(dòng)機(jī)2.1.2幾種典型的規(guī)則11111010110001101000100000100111tt+1Rule30：Wolfram的初等元胞自動(dòng)機(jī)2.1.2幾種典型的規(guī)則Rule30演化結(jié)果t=50t=100Wolfram的初等元胞自動(dòng)機(jī)2.1.2幾種典型的規(guī)則Rule30演化結(jié)果t=250Wolfram的初等元胞自動(dòng)機(jī)t=1000Wolfram的初等元胞自動(dòng)機(jī)2.1.2幾種典型的規(guī)則11111010110001101000100000110110tt+1Rule90：Wolfram的初等元胞自動(dòng)機(jī)2.1.2幾種典型的規(guī)則Rule90演化結(jié)果t=30t=100Wolfram的初等元胞自動(dòng)機(jī)2.1.2幾種典型的規(guī)則Rule90演化結(jié)果t=250Wolfram的初等元胞自動(dòng)機(jī)t=1000Wolfram的初等元胞自動(dòng)機(jī)2.1.2幾種典型的規(guī)則Rule110演化結(jié)果t=25t=100t=250t=2500Wolfram的初等元胞自動(dòng)機(jī)2.1.2幾種典型的規(guī)則11111010110001101000100010100101tt+1Rule150：Wolfram的初等元胞自動(dòng)機(jī)2.1.2幾種典型的規(guī)則Rule150演化結(jié)果t=25t=100Wolfram的初等元胞自動(dòng)機(jī)2.1.2幾種典型的規(guī)則Rule150演化結(jié)果t=250t=2500Wolfram的初等元胞自動(dòng)機(jī)2.1.2幾種典型的規(guī)則Rule150演化結(jié)果:初始條件為隨機(jī)狀態(tài)t=250Wolfram的初等元胞自動(dòng)機(jī)2.1.2幾種典型的規(guī)則11111010110001101000100010001110tt+1Rule184：Wolfram的初等元胞自動(dòng)機(jī)2.1.2幾種典型的規(guī)則Rule184演化結(jié)果t=100t=100，p=0.2,周期性邊界條件Rule184演化結(jié)果t=100，p=0.3,周期性邊界條件Rule184演化結(jié)果第二章經(jīng)典的元胞自動(dòng)機(jī)2.2J.Conway和他的生命游戲（gameoflife）

GameofLife生命游戲（gameoflife）是由劍橋大學(xué)的數(shù)學(xué)家JohnHortonConway在1970年提出來(lái)的。生命游戲（gameoflife）的構(gòu)成：元胞分布在規(guī)則劃分的二維網(wǎng)格上；元胞具有0，1兩種狀態(tài)，0代表“死”，1代表“生”；元胞以相鄰的8個(gè)元胞為鄰居。即Moore鄰居形式；一個(gè)元胞的生死由其在該時(shí)刻本身的生死狀態(tài)和周圍八個(gè)鄰居的狀態(tài)決定。GameofLifeSurvival(生存)：對(duì)一個(gè)活的元胞，如果它的鄰居中有兩個(gè)或三個(gè)元胞是活的，那么該元胞將繼續(xù)生存下去。Die(死亡):對(duì)一個(gè)活的元胞(a)如果它的鄰居中有四個(gè)或四個(gè)以上的元胞是活的，那么該元胞將死去；(b)如果它的鄰居中只有一個(gè)或沒(méi)有活的元胞，那么該元胞也將死去。Born(繁殖):對(duì)一個(gè)空的元胞，如果它的鄰居中有3個(gè)（不能多也不能少）活的，那么該元胞將成為一個(gè)活的元胞。生命游戲的規(guī)則：GameofLife生命游戲的規(guī)則(數(shù)學(xué)形式)：SNt表示t時(shí)刻，中心元胞i的鄰居的狀態(tài)。GameofLife生命游戲中的一些演化過(guò)程和形態(tài)：GameofLife生命游戲中的一些演化過(guò)程和形態(tài)：GameofLife生命游戲中的典型形態(tài)分類：TypeI:stilllives(固定不變類)——構(gòu)形的狀態(tài)不會(huì)隨著時(shí)間的演化而改變GameofLife生命游戲中的典型形態(tài)分類：TypeII:oscillators(振蕩型)——經(jīng)過(guò)一定時(shí)間的演化后，仍然會(huì)回歸到初始的形態(tài)，且位置不會(huì)發(fā)生變化blinkerGameofLife生命游戲中的典型形態(tài)分類：TypeIII:spaceship(宇宙飛船型)——和振蕩型的類似，宇宙飛船型的構(gòu)形在經(jīng)過(guò)一定步驟的演化后，會(huì)回歸到其初始構(gòu)形；但是，同振蕩型不同的是：構(gòu)形已經(jīng)不在原來(lái)的初始位置上，而是沿著一定的方向發(fā)生了位移，并且方向是一個(gè)固定的方向，中間的轉(zhuǎn)換步驟也是一個(gè)固定的過(guò)程。gliderGameofLife生命游戲中的典型形態(tài)分類：TypeIV:Patternsthatconstantlyincreaseinpopulationsize(生命數(shù)量以常數(shù)值增加)TypeIVa:(guns)Oscillatorsthatemitspaceshipsineachcycle.大炮：(在每個(gè)循環(huán)中向外發(fā)射宇宙飛船的振蕩型構(gòu)形)GameofLife生命游戲中的典型形態(tài)分類：TypeIVb:(breeders):Patternsthatincreasetheirpopulationsizequadratically（evenfast）生命數(shù)量呈二次方（或更快）的速度增長(zhǎng)的構(gòu)形GameofLife生命游戲中的典型形態(tài)分類：TypeV(unstable):Patternsthatevolvethroughasequenceofstates,whichneverreturntotheoriginalstate.經(jīng)過(guò)一系列的演化過(guò)程，再也不會(huì)恢復(fù)到初始狀態(tài)的那些構(gòu)形acorn其他一些構(gòu)形：GameofLife生命游戲的擴(kuò)展：三維生命游戲的一些構(gòu)形第二章經(jīng)典的元胞自動(dòng)機(jī)2.3Langton和“能自我復(fù)制的元胞自動(dòng)機(jī)”

Langton的自我復(fù)制環(huán)Langton螞蟻第二章經(jīng)典的元胞自動(dòng)機(jī)2.3Langton和“能自我復(fù)制的元胞自動(dòng)機(jī)”自我復(fù)制環(huán)（SelfreproducingLoop）的構(gòu)成：元胞分布在規(guī)則劃分的二維網(wǎng)格上；元胞具有(0~7)8種狀態(tài)；元胞以相鄰的4個(gè)元胞為鄰居。即VonNewmann鄰居形式；一個(gè)元胞的生死由其在該時(shí)刻本身的生死狀態(tài)和周圍4個(gè)鄰居的狀態(tài)決定。2.3Langton和他的元胞自動(dòng)機(jī)”自我復(fù)制環(huán)的初始構(gòu)形及狀態(tài)解析：Langton環(huán)由一個(gè)方形環(huán)和一個(gè)向外伸展的生長(zhǎng)臂組成，形似字母Q。環(huán)的內(nèi)側(cè)和外側(cè)由狀態(tài)為2的殼元胞組成，內(nèi)殼和外殼構(gòu)成了一個(gè)管道。在管道中，0為背景元胞，1為核心元胞，4,7為基因元胞，3,5,6是信息元胞。2.3Langton和他的元胞自動(dòng)機(jī)”自我復(fù)制環(huán)圖示：2.3Langton和他的元胞自動(dòng)機(jī)”自我復(fù)制環(huán)圖示：2.3Langton和他的元胞自動(dòng)機(jī)”自我復(fù)制環(huán)圖示：2.3Langton和他的元胞自動(dòng)機(jī)”Langton螞蟻：從任意一點(diǎn)往一個(gè)方向（上、下、左、右選其一）出發(fā)，螞蟻進(jìn)行游走，它的規(guī)則有兩條：1、如果走到的格子為空，則占領(lǐng)這個(gè)格子并且螞蟻?lái)槙r(shí)針旋轉(zhuǎn)90度；2、如果走到的格子已經(jīng)被占領(lǐng)，則把這個(gè)格子的狀態(tài)變?yōu)榭眨⑶夷鏁r(shí)針旋轉(zhuǎn)90度。2.3Langton和他的元胞自動(dòng)機(jī)”Langton螞蟻模擬結(jié)果：2.3Langton和他的元胞自動(dòng)機(jī)”Langton螞蟻模擬結(jié)果：2.4LatticeGasandLatticeBoltzmannMethod第二章經(jīng)典元胞自動(dòng)機(jī)LGAandLBM(orL-BGK)格子氣自動(dòng)機(jī)

，它是以元胞自動(dòng)機(jī)為基礎(chǔ)發(fā)展出的一種新的流體計(jì)算方法，是元胞自動(dòng)機(jī)在流體力學(xué)與統(tǒng)計(jì)物理中的具體化，也是元胞自動(dòng)機(jī)在科學(xué)研究領(lǐng)域成功應(yīng)用的范例

2.4.1格子氣自動(dòng)機(jī)(LatticeGasAutomata,簡(jiǎn)稱LGA)LGAandLBM(orL-BGK)2.4.1LGA流體的宏觀行為不依賴于具體的微觀行為：即任何一個(gè)系統(tǒng)，只要它能夠滿足連續(xù)方程和Navier-Stokes方程（動(dòng)量方程），那么就可以用來(lái)模擬流體。具體的微觀行為并不重要。

假設(shè)條件：LGAandLBM(orL-BGK)2.4.1LGA元胞空間采用正方形網(wǎng)格；（1）HPPModel

(Hardy,PomeauanddePazzis)流體是由無(wú)數(shù)的粒子所構(gòu)成的。這些粒子既比分子的級(jí)別大，其質(zhì)量又比有限容積法中控制容積的質(zhì)量要小得多。粒子可以沿著格點(diǎn)之間的連線（link）運(yùn)動(dòng)每個(gè)粒子有四個(gè)速度狀態(tài)排他規(guī)則（包利不相容原理）LGAandLBM(orL-BGK)2.4.1LGA（1）HPPModelLGAandLBM(orL-BGK)2.4.1LGA（1）HPPModel：碰撞規(guī)則LGAandLBM(orL-BGK)2.4.1LGA（1）HPPModel：缺陷由于采用方形網(wǎng)格，這就決定了粒子只能在兩個(gè)方向上運(yùn)動(dòng)：水平方向和豎直方向，這就造成了粘性耗散的各向異性。LGAandLBM(orL-BGK)2.4.1LGA（2）FHPModel(FrischHasslacherandPomeau)采用了正六邊形網(wǎng)格劃分方式；有六個(gè)連接方向可供粒子運(yùn)動(dòng)在結(jié)點(diǎn)上允許靜止粒子的存在仍采用排他規(guī)則（包利不相容原理）LGAandLBM(orL-BGK)

2.4.1LGA（2）FHPModel(FrischHasslacherandPomeau)FHP模型中正六邊形格點(diǎn)示意圖粒子的速度集合LGAandLBM(orL-BGK)

2.4.1LGA（2）FHPModel：碰撞規(guī)則LGAandLBM(orL-BGK)

2.4.1LGA（2）FHPModel：碰撞規(guī)則LGAandLBM(orL-BGK)

2.4.1LGA（2）FHPModel：碰撞規(guī)則LGAandLBM(orL-BGK)

2.4.1LGA（2）FHPModel：碰撞規(guī)則LGAandLBM(orL-BGK)

2.4.1LGA（2）FHPModel：邊界無(wú)滑移邊界條件LGAandLBM(orL-BGK)

2.4.1LGA（2）FHPModel：狀態(tài)的更新?tīng)顟B(tài)的更新過(guò)程分為兩個(gè)子步：碰撞步：根據(jù)特定的碰撞規(guī)則，各粒子之間發(fā)生碰撞，并由此確定出出射狀態(tài)；流動(dòng)步（Streaming）：出射后的粒子沿著格點(diǎn)之間的連線流向下一個(gè)相鄰結(jié)點(diǎn)，然后準(zhǔn)備進(jìn)行下一次碰撞。LGAandLBM(orL-BGK)

2.4.1LGA

狀態(tài)的更新（以HPP模型為例）狀態(tài)更新示意圖LGAandLBM(orL-BGK)

2.4.1LGAEquationsofLGAModelt時(shí)刻，r處元胞的第i條格線上的粒子數(shù)宏觀密度和速度：LGAandLBM(orL-BGK)

2.4.1LGA宏觀量的計(jì)算：宏觀量平均值的示意圖LGAandLBM(orL-BGK)

2.4.1LGA宏觀量的計(jì)算：宏觀量平均值計(jì)算表LGAandLBM(orL-BGK)

2.4.1LGAEquationsofLGAModel碰撞函數(shù)LGAandLBM(orL-BGK)

2.4.1LGAEquationsofLGAModel連續(xù)方程：動(dòng)量方程：LGAandLBM(orL-BGK)

2.4.2L-BGKLGA的缺陷：缺少Galilean不變性結(jié)果有數(shù)值噪音，即有一定的波動(dòng)大的碰撞矩陣，求解計(jì)算量大對(duì)于二維的FHP，碰撞表的輸入條件有27條，而對(duì)應(yīng)三維FHP需要的輸入條件為224條LGAandLBM(orL-BGK)

2.4.2L-BGKBoltzmann方程表示在t時(shí)刻，在空間位置r處的dxdydz體積之內(nèi)，速度在v+dv范圍內(nèi)的平均分子數(shù)。表示由于分子之間的碰撞所造成的分布函數(shù)的變化率，稱為碰撞函數(shù)，它是一個(gè)非常復(fù)雜的積分式。LGAandLBM(orL-BGK)

2.4.2L-BGK碰撞項(xiàng)的BGK簡(jiǎn)化（Bhatragar,GrossandKrook）：松弛或馳豫（relaxation）:在統(tǒng)計(jì)物理中指的是一個(gè)偏離平衡態(tài)的系統(tǒng)向平衡態(tài)逼近的過(guò)程。LGAandLBM(orL-BGK)

2.4.2L-BGK1991-1992期間，陳十一及錢躍宏等人幾乎同時(shí)提出了基于單一時(shí)間的松弛過(guò)程使得格子-Boltzmann方法中的碰撞項(xiàng)得到簡(jiǎn)化的方法，即格子-BGK方法。演化方程:LGAandLBM(orL-BGK)

2.4.2L-BGK：d2q9速度集合：平衡分布函數(shù)：LGAandLBM(orL-BGK)

2.4.2L-BGK：d2q9Navier-StokesEquation:運(yùn)動(dòng)粘度同松弛時(shí)間的關(guān)系：LGAandLBM(orL-BGK)

2.4.2L-BGK：計(jì)算步驟對(duì)所計(jì)算的系統(tǒng)選擇一個(gè)特征速度，然后據(jù)給定的Reynolds數(shù)計(jì)算出分子運(yùn)動(dòng)粘度；利用分子運(yùn)動(dòng)粘度同松弛時(shí)間的關(guān)系，計(jì)算出松弛時(shí)間設(shè)定初始的密度與速度分布；設(shè)定各格點(diǎn)的分布函數(shù)值；計(jì)算平衡態(tài)分布函數(shù)；演化更新：分為碰撞和流動(dòng)兩個(gè)子步來(lái)完成；計(jì)算出宏觀密度和速度，并更新他們的值；重復(fù)4～6，直到滿足一定的收斂條件。LGAandLBM(orL-BGK)

2.4LGA和L-BGK：應(yīng)用等溫流動(dòng)；多項(xiàng)流；相界面和相變；多孔介質(zhì)中的流動(dòng)；自然對(duì)流換熱；流動(dòng)的分歧；有化學(xué)反應(yīng)的界面問(wèn)題，等等。相分離相分離相分離多孔介質(zhì)多孔介質(zhì)利用重構(gòu)函數(shù)得到的多孔介質(zhì)結(jié)構(gòu)利用工業(yè)CT得到的實(shí)體砂巖的結(jié)構(gòu)2.5Nagel-Schreckenberg(NaSch)模型2.5NaSch模型作為對(duì)184號(hào)規(guī)則的推廣，Nagel和Schreckberg在1992年提出了一個(gè)模擬車輛交通的元胞自動(dòng)機(jī)模型，即NS模型（也有人稱它為NaSch模型）。時(shí)間、空間和車輛速度都被整數(shù)離散化道路被劃分為等距離的離散的格子，即元胞每個(gè)元胞或者是空的，或者被一輛車所占據(jù)車輛的速度可以在（0～Vmax）之間取值2.5NaSch模型在時(shí)刻t到時(shí)刻t+1的過(guò)程中按照下面的規(guī)則進(jìn)行更新：2.5NaSch模型在時(shí)刻t到時(shí)刻t+1的過(guò)程中按照下面的規(guī)則進(jìn)行更新：2.5NaSch模型更新過(guò)程圖示：2.5NaSch模型更新過(guò)程圖示：2.5NaSch模型更新過(guò)程圖示：2.5NaSch模型更新過(guò)程圖示：2.5NaSch模型邊界條件周期性邊界條件在每次更新結(jié)束后，我們要監(jiān)測(cè)道路上頭車的位置X_lead，如果X_lead>L_road，那么這兩車將從道路的另一端進(jìn)入系統(tǒng)，變?yōu)榈缆飞系奈曹嚕⑶襒_lead=X_lead-L_road,V_last=V_lead。開(kāi)口邊界條件假設(shè)道路最左邊的元胞對(duì)應(yīng)于X=1，并且道路的入口端包含V_max個(gè)元胞，也就是說(shuō)，車輛可以從元胞

(1,2,…,V_max)進(jìn)入到道路中。在t

t+1時(shí)刻，當(dāng)?shù)缆飞系能囕v更新完成后，監(jiān)測(cè)道路上的