第四章元胞自動機元胞自動機ppt課件1元胞自動機起源于對自我復(fù)制的機器的研究馮·諾依曼（VonNeumann）S.Ulam一個由元胞組成的完全離散的構(gòu)架（現(xiàn)稱網(wǎng)格），其中元胞表示系統(tǒng)的個體，個體具有若干個離散狀態(tài)，個體狀態(tài)根據(jù)網(wǎng)格中的鄰元狀態(tài)按規(guī)則同步進行變化。廣為人知---生命游戲1970年劍橋大學(xué)的JohnH.Conway由《科學(xué)美國人》的數(shù)學(xué)游戲?qū)诮榻B到全世界20世紀80年代以來，CA得到了很大的發(fā)展并已經(jīng)廣泛地應(yīng)用于物理學(xué)、生物學(xué)、數(shù)學(xué)、計算機科學(xué)和社會科學(xué)等研究領(lǐng)域。4.1概述元胞自動機起源于對自我復(fù)制的機器的研究4.1概述24.2元胞自動機模型A.概述元胞自動機是一個空間、空間和狀態(tài)都是離散的模型。該模型可用一個四元組表示：

其中：S表示細胞狀態(tài)，是一個有限的、離散的狀態(tài)集合；La表示元胞空間，a是一個正整數(shù)，表示細胞空間的維數(shù)；N表示領(lǐng)域內(nèi)元胞的組合，n表示鄰居的個數(shù)f表示狀態(tài)轉(zhuǎn)移函數(shù)，即狀態(tài)轉(zhuǎn)移規(guī)則。4.2元胞自動機模型A.概述S表示細胞狀態(tài)，是一個有限的3

B.領(lǐng)域和鄰元對于一個元胞，在空間位置上與它相鄰的元胞稱為它的鄰元（有時也稱作鄰居）。所有由鄰元組成的區(qū)域稱為它的鄰域。圖d：一維CA網(wǎng)格的領(lǐng)域定義圖c：二維CA網(wǎng)格的鄰域定義馮·諾依曼鄰域不同大小的摩爾鄰域鄰域和鄰元的定義可以是多樣的，如圖所示B.領(lǐng)域和鄰元對于一個元胞，在空間位置上與4

C.狀態(tài)每個元胞有若干個狀態(tài)，如：物理系統(tǒng)：（分子）固態(tài)，液態(tài)生物系統(tǒng)：（細胞）活與死社會系統(tǒng)：（個人）相信與不相信謊言政治系統(tǒng)：（國家）戰(zhàn)爭與妥協(xié)……

C.狀態(tài)每個元胞有若干個狀態(tài)，如：5

D.網(wǎng)格圖a：一維的CA網(wǎng)格圖b：二維的CA網(wǎng)格一維的CA模型是將直線分成若干相同的等份；二維的CA模型是將一個平面分成許多正方形、六邊形或三角形的網(wǎng)格（最常見的是將其劃分成正方形）；三維的CA模型將空間劃分成許多立體網(wǎng)格。在各種CA模型中，每一個等份（單元格）代表一個元胞，CA的網(wǎng)格可以有不同的形式(維數(shù)，大小)。D.網(wǎng)格圖a：一維的CA網(wǎng)格圖b：二維的CA網(wǎng)格6

E.狀態(tài)更新規(guī)則（一）根據(jù)每個元胞及鄰元的不同狀態(tài)，由狀態(tài)更新規(guī)則決定這個元胞在下一個時刻的狀態(tài)。序號i個體在t=1,…,n時刻的狀態(tài)規(guī)則可以是確定型的，也可以是隨機型的。，其中為個體i的鄰元在t時刻的狀態(tài)。E.狀態(tài)更新規(guī)則（一）根據(jù)每個元胞及鄰元的7狀態(tài)更新規(guī)則（二）對于一個一維的CA，一個細胞具有兩種可能的狀態(tài)如生或死，相信或者不相信等等，表示為０或１。如規(guī)則一：我們使用前面圖c左邊的鄰元定義，且定義其狀態(tài)更新規(guī)則為：當(dāng)個體的兩個鄰元都活或者都死，該個體在下一時刻變?yōu)樗溃环粗臓顟B(tài)在下一時刻變?yōu)榛睢＜矗乱?guī)則如下表所示：t時刻鄰元的狀態(tài)111110101100011010001000t

+

1時刻中心格的狀態(tài)01011010表：一個一維CA的狀態(tài)更新規(guī)則狀態(tài)更新規(guī)則（二）對于一個一維的CA，一個細胞8狀態(tài)更新規(guī)則（三）再如規(guī)則二：我們?nèi)匀皇褂们懊鎴Dc左邊的鄰元定義，但重新定義其狀態(tài)更新規(guī)則為：當(dāng)個體的兩個鄰元都活或者都死，該個體在下一時刻改變狀態(tài)；反之，該個體的狀態(tài)在下一時刻保持不變。該規(guī)則下狀態(tài)更新可以如下表所示：t時刻鄰元的狀態(tài)111110101100011010001000t

+

1時刻中心格的狀態(tài)01101001表：一個一維CA的狀態(tài)更新規(guī)則狀態(tài)更新規(guī)則（三）再如規(guī)則二：我們?nèi)匀皇褂们懊?4.3元胞自動機仿真技術(shù)4.3.1模型的構(gòu)建考慮以下問題：確定系統(tǒng)中有那些個體，如何分類？個體有幾種狀態(tài)，分別是什么；個體所處的空間形式，是一維、二維還是多維；個體的鄰元形式及個數(shù)，這與網(wǎng)格形式及交互群體規(guī)模有關(guān)；根據(jù)個體狀態(tài)、網(wǎng)格形式及鄰元，確定個體狀態(tài)的演變規(guī)則。4.3元胞自動機仿真技術(shù)4.3.1模型的構(gòu)建10此外，還需確定：系統(tǒng)中的個體與單元格是否一致。 簡單的、經(jīng)典的CA模型中，單元格與個體不加區(qū)分，每個單位格就是一個個體，個體始終在單元格中，個體的狀態(tài)即為單元格的狀態(tài)。但在一些復(fù)雜系統(tǒng)中，尤其在個體可以移動的系統(tǒng)中，將個體與單元格區(qū)分更為方便。系統(tǒng)中有否有離散事件。 采用CA模型描述的系統(tǒng)，每個時刻都需根據(jù)規(guī)則確定每個元胞的狀態(tài)。除此之外，有的系統(tǒng)中某些個體會在特定時刻（有條件或無條件）發(fā)生狀態(tài)變化，此時可以采用離散事件仿真方法，將該時刻列于事件表，根據(jù)事件表處理該類事件。此外，還需確定：114.3.2仿真技術(shù)1.仿真鐘仿真鐘步進式推進，步長為1。在每一時刻都需改變個體以及網(wǎng)格狀態(tài)，還要收集統(tǒng)計數(shù)據(jù)。2.事件的處理 某些系統(tǒng)中有離散事件的發(fā)生。對這類事件也采用事件表，將特定時刻及事件類型登記在事件表中。在仿真鐘步進式推進的每個仿真時刻，除根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則對所有元胞進行狀態(tài)更新外，還要檢查一下是否有特殊事件發(fā)生，如果有就產(chǎn)生事件進行處理。3.隨機因素的處理 CA模型描述的復(fù)雜系統(tǒng)中往往帶有不確定性4.3.2仿真技術(shù)1.仿真鐘124.3.3仿真流程4.3.3仿真流程13

流言模型流言模型解釋了流言通過個體之間局部的交互進行傳播的過程：流言從一個人開始傳播給某些聽眾，每個人從自己的鄰居那里聽到流言，然后他會把流言傳給其他的鄰居，并且假定一旦某個人聽到這個流言，他會記住，不需要再次的傳播。4.4流言模型流言模型4.4流言模型14

4.4.1基本的流言模型A.概述流言模型刻畫了流言通過個體之間局部的交互進行傳播的過程：流言從一個人開始傳播給某些聽眾，每個人從自己的鄰居那里聽到流言，然后他會把流言傳給其他的鄰居，并且假定一旦某個人聽到這個流言，他會永遠記住。B.CA模型模型采用二維網(wǎng)格，鄰元數(shù)量8個（摩爾領(lǐng)域）。模型中的單元格有兩種狀態(tài)：不相信流言和相信流言。單元格的狀態(tài)更新規(guī)則如下：①如果單元格是白色的（不相信），并且它的鄰元中有黑色的（相信），則該單元格從白色變成黑色。②如果單元格是黑色的，則該單元格將永遠保持黑色不變。4.4.1基本的流言模型A.概述15C.仿真原理T=0T=1T=2C.仿真原理T=0T=1T=216傳播過程：曲線圖示——表示數(shù)量動態(tài)變化曲線：t=0,number=1t=1,number=9t=2,number=25t=3,number=49t=4,number=81個數(shù)＝(2n+1)2,n為步數(shù)傳播過程：曲線圖示——表示數(shù)量動態(tài)變化曲線：t=0,num17基本模型因為簡化了真實情況，流言傳播速度很快，與真實系統(tǒng)不符。

4.4.2概率規(guī)則的流言模型真實系統(tǒng)不是每個人都相信改變想法（逆轉(zhuǎn)）鄰元以一定概率相信流言多數(shù)模型規(guī)則改變基本模型因為簡化了真實情況，流言傳播速度很快，與真實系統(tǒng)不符181.模型引入概率規(guī)則，此類模型與最簡單的流言模型不同之處僅在于狀態(tài)的演變規(guī)則中包含了隨機因素狀態(tài)轉(zhuǎn)換規(guī)則①發(fā)生變化原始規(guī)則：“如果單元格是白色的（不相信），并且它的鄰元中有黑色的（相信），則該單元格從白色變成黑色。”改變?yōu)椋喝绻麊卧袷前咨模ú幌嘈牛⑶宜泥徳杏泻谏模ú幌嘈牛瑒t該單元格以一定概率從白色變成黑色1.模型引入概率規(guī)則，此類模型與最簡單的流言模型不同之處僅192.仿真實現(xiàn)當(dāng)單元格為相信狀態(tài)，在設(shè)置其鄰元時，對所有鄰元產(chǎn)生一個（0，1）均勻分布隨機抽樣。由于演變規(guī)則為“以50%的概率成為相信者”，則在8個鄰元中隨機數(shù)在（0，0.5）的不相信的單元格變?yōu)橄嘈牛渌牟蛔儭?.仿真實現(xiàn)當(dāng)單元格為相信狀態(tài)，在設(shè)置其鄰元時，對所有鄰元203.仿真結(jié)果相信人數(shù)的變化對比基本模型（p=1）和概率模型(p=0.5)結(jié)論與全部相信的情形相比流言擴散慢的多，也合理的多。但相信人數(shù)的變化規(guī)律定性上是一樣的，只是參數(shù)不同而已，說明概率不同沒有引起基本規(guī)律的變化，只是延緩了變化過程。3.仿真結(jié)果相信人數(shù)的變化214.4.3帶遺忘的流言模型1.模型上面模型假設(shè)一旦個體已經(jīng)相信流言就永遠不會忘記,但如果個體以某種概率忘記流言將會產(chǎn)生什么樣的結(jié)果呢？帶遺忘的流言模型就是描述這一現(xiàn)象的。規(guī)則②從原來的“如果一個單元格是黑色的，它將永遠保持黑色”變?yōu)椤叭绻粋€單元格是黑色的，它會以一個固定的小概率變成白色”。4.4.3帶遺忘的流言模型1.模型222.仿真實現(xiàn)有遺忘的CA模型中，當(dāng)個體從不相信變?yōu)橄嘈诺臓顟B(tài)，首先要用一個遺忘概率來確定該個體是否屬于遺忘個體。若是遺忘個體，則要根據(jù)遺忘時間的分布參數(shù)設(shè)置遺忘時刻，將遺忘事件（包括遺忘時刻與個體序號）登記到事件表中。2.仿真實現(xiàn)有遺忘的CA模型中，當(dāng)個體從不相信變?yōu)橄嘈诺臓?3遺忘事件作為一個原發(fā)事件，當(dāng)仿真時鐘到達此時刻，則將該個體從相信狀態(tài)變?yōu)椴幌嘈牛@樣就實現(xiàn)了遺忘，遺忘事件處理邏輯如圖所示。遺忘事件作為一個原發(fā)事件，當(dāng)仿真時鐘到達此時刻，則將該個體從243.仿真結(jié)果設(shè)定流言相信概率50%,遺忘個體的比例為10%,一次仿真結(jié)果如圖。黑色中的白色代表已經(jīng)忘記流言的單元格3.仿真結(jié)果設(shè)定流言相信概率50%,遺忘個體的比例為10%251.概述在有些情況下，個體的狀態(tài)是由其周圍大多數(shù)個體的狀態(tài)決定的。例如，人們只有在他的大多數(shù)朋友已接受一種時尚時，他才接受這一種時尚。用于研究這一類問題的CA模型，我們稱之為多數(shù)模型。多數(shù)模型的特點是：模型中單元格的狀態(tài)取決于其所有鄰元的集體狀態(tài)。

4.5多數(shù)模型1.概述4.5多數(shù)模型26仍然假定單元格有白與黑兩種狀態(tài)。最簡單的模型只有一條規(guī)則：單元格下一時刻的狀態(tài)變?yōu)樗拇蠖鄶?shù)Moore鄰元的狀態(tài)決定，或者該單元格保持目前的狀態(tài)不變。Moore型鄰元有8個，因此，這一規(guī)則是說：當(dāng)有5個或更多白色單元格圍繞時，單元格將變成白的；如果有5個或更多黑色單元格圍繞時，它將變成黑的；當(dāng)有4個白色4個黑色時，它保持原來狀態(tài)不變。

2.最簡單的多數(shù)模型仍然假定單元格有白與黑兩種狀態(tài)。2.最簡單的多273.仿真結(jié)果仿真的初始狀態(tài)是黑白單元格隨機分布在網(wǎng)格中，按上述規(guī)則的運行結(jié)果是形成了一個白色塊與黑色塊相間的圖案3.仿真結(jié)果仿真的初始狀態(tài)是黑白單元格隨機分布在網(wǎng)格中，按284.多數(shù)模型的擴展如對這個規(guī)則作些修正，假定人們對流行時尚的態(tài)度是不同的，一些人較容易受時尚的影響，而另一些人則可能不太容易受到時尚的影響。模型的狀態(tài)更新規(guī)則將變?yōu)椋阂恍┌咨珕卧裨趦H有4個黑色相鄰單元格時也會變黑色，而一些則必須至少有6個黑色相鄰的單元格時才變色；對每個黑色單元格也是相似的。對于流行時尚易受影響或有抗拒傾向的個體在模型中是隨機分布的。每個仿真時鐘內(nèi)，那些需要6個其他顏色的鄰居才改變自身顏色的單元格和那些只要4個就會變顏色的單元格數(shù)目是相同的。在這一修正模型中，單元格不再是同質(zhì)的，取而代之的是一些具有個體差異的單元格。482個時間步之后，黑白區(qū)塊已形成了大的簇。4.多數(shù)模型的擴展如對這個規(guī)則作些修正，假定人們對流行時尚29(a)(b)(c)(a)(b)(c)304.6艾滋病傳播模型艾滋病的傳播特性 艾滋病傳播的主要特點是與個體行為密切相關(guān)，病例中家族聚集和特殊行為人群聚集現(xiàn)象十分明顯。所以對艾滋病傳播相關(guān)行為的人群分類，有效的描述不同行為人群的傳播特征是研究的前提。艾滋病毒感染者在感染后有幾年或十幾年的存活期，但各個時期傳播強度不一樣。在艾滋病傳播的仿真中，不僅要模擬傳播過程也要模擬個體感染直至死亡的全過程。4.6艾滋病傳播模型艾滋病的傳播特性31艾滋病病程

結(jié)合臨床表現(xiàn)，根據(jù)其傳播特性可以分成這樣幾個階段：第一階段為感染階段，即從健康人到感染者。第二階段是感染之后到死亡的患病階段，在這期間感染者的行為特征與傳播他人強度密切相關(guān)。其中在感染期由于病癥不明顯，傳播強度大，在發(fā)病期傳播強度減弱，如死亡則不再傳播。

艾滋病病程32不同行為群體的傳播特性零傳播人群P0：如兒童，出生時沒被感染的健康兒童不可能被感染，因母嬰傳播已感染的兒童一般也不會傳播他人。一般人群PL：行為正常者，除正常的性行為外，無其它艾滋病病毒感染機會。這類個體易感度及傳播他人的強度均小。高危人群PH：具有高危行為，如共用針管吸毒者、性工作者、同性戀者、賣血者。他們由于特殊行為有較大的概率通過血液、性途徑感染艾滋病毒，感染后快速的傳播他人。報復(fù)者PH+：這些人感染了艾滋病病毒后，敵視報復(fù)社會，大量惡意傳播他人。這些人極少但破壞性卻不小。不同行為群體的傳播特性332.艾滋病傳播的CA模型a.個體狀態(tài)健康S1危險S2感染S3發(fā)病S4死亡S5患病階段感染階段狀態(tài)含義特點演變條件逆向演變S1健康未感染且不可能感染成為感染者的鄰元→S2無S2危險有可能感染根據(jù)一定的概率→S3當(dāng)不再是感染者的鄰元→S1S3感染已感染，癥狀不明顯，會傳播他人一定時間之后→S4無S4發(fā)病有明顯癥狀，傳播強度減弱一定時間之后→S5無S5死亡無傳染，鄰元的危險解除無2.艾滋病傳播的CA模型a.個體狀態(tài)健康危險感染發(fā)病死亡患34b.網(wǎng)格和鄰元鄰元的個數(shù)多少則表示已感染個體對他人的傳播強度。由于不同行為個體對他人的傳播強度差異很大，所以用不同的鄰域來表示不同類型個體不同病程的傳播強度。不同類型個體的易感度也有差異，模型中采用被感染概率來表示易感度，概率大的則易感度高。個體類型行為特性鄰元個數(shù)被感染概率P0無傳播，無感染00PL正常行為1－3低PH高危行為8－16高PH+報復(fù)行為>64低b.網(wǎng)格和鄰元鄰元的個數(shù)多少則表示已感染個體對他人的傳播強35C.狀態(tài)變化規(guī)則第一條規(guī)則是從健康狀態(tài)到危險狀態(tài)的演變。健康狀態(tài)的個體成為感染者的鄰元后，該個體從健康狀態(tài)轉(zhuǎn)換到危險狀態(tài)。實現(xiàn)方式是一旦個體感染后，根據(jù)感染者的行為類型設(shè)置其鄰元，使他的鄰元均為危險狀態(tài)。在設(shè)置鄰元的同時，應(yīng)根據(jù)各類人群的比例隨機設(shè)置每個鄰元的行為類型。第二條規(guī)則是從危險狀態(tài)到感染狀態(tài)的演變規(guī)則。處于危險狀態(tài)的個體均有一個不同的概率從危險狀態(tài)變?yōu)楦腥緺顟B(tài)。個體從感染到發(fā)病再到死亡不是一個傳播過程，而是病人的病變過程，其中狀態(tài)演變的主要決定因素是時間。從感染到發(fā)病以及從發(fā)病到死亡的時間間隔均是隨機變量C.狀態(tài)變化規(guī)則第一條規(guī)則是從健康狀態(tài)到危險狀態(tài)的演變。健363.仿真仿真鐘仿真時間單位為周狀態(tài)更新

一個是根據(jù)概率規(guī)則確定哪些個體從S2→S3，第二是為S3的個體根據(jù)其行為屬性設(shè)置鄰元，使其鄰元從S1→S2，對每個S2個體給一個行為屬性，并產(chǎn)生一個發(fā)病時間，登記到事件表。

事件處理事件類型名稱處理內(nèi)容登記時間1發(fā)病減少鄰元，產(chǎn)生并登記死亡事件感染時刻2死亡清除鄰元，未感染鄰元恢復(fù)健康狀態(tài)發(fā)病時刻3.仿真仿真鐘事件類型名稱處理內(nèi)容登記時間1發(fā)病減少鄰元，374.結(jié)果假設(shè)網(wǎng)格由個100*100個單元格構(gòu)成,人群的規(guī)模為＝2000。初始時刻所有個體隨機均勻的分布在網(wǎng)格上，P0、PL、PH、PH+的比例分別為0.1,0.7,0.12,0.08。某次仿真試驗中某時刻各類個體的空間分布情況。4.結(jié)果假設(shè)網(wǎng)格由個100*100個單元格構(gòu)成,人群的規(guī)模38各類行為人群5組不同比例下的感染曲線,保持P0和PL比例不變，變動PH和PH+的比例，為0.14(0.06)，0.16(0.04)，0.18(0.02)，0.20(0.0)。各類行為人群5組不同比例下的感染曲線,保持P0和PL比例不變391.模型美國社會中不同種族，尤其以黑人，白人為典型，無論白人、黑人都愿意周圍有較多的同族，否則將遷移。采用CA模型描述這一動態(tài)過程，此時網(wǎng)格代表一個地理區(qū)域，網(wǎng)格上格點代表居住點，可以有人居住也可以無人居住。該模型中個體可以移動。個體：家庭屬性：黑，白網(wǎng)格：二維（網(wǎng)格上的節(jié)點有個體或沒個體）鄰元：摩爾鄰元，8個網(wǎng)格狀態(tài)：白，黑，空個體狀態(tài)：不動，遷移規(guī)則：如個體的同族鄰元≥閥值則不動，否則遷移遷移規(guī)則：尋找滿足不動條件的空格

4.7遷移模型1.模型4.7遷移模型402.仿真在遷移模型的仿真中，仿真流程與CA仿真基本流程相同，也采用步進式推進。但是在每一仿真時刻執(zhí)行的內(nèi)容有些不同2.仿真在遷移模型的仿真中，仿真流程與CA仿真基本流程相同413.結(jié)果“容忍閾值”為37.5%（Moore鄰域中至少