元胞自動機演化行為的統(tǒng)計與仿真研究

元胞自動機演化行為的統(tǒng)計與仿真研究

元細胞自動機是21世紀科學研究的一個異?；钴S的前沿領域。這是復雜科學的中心技術之一。元胞自動機是一種時間、空間、狀態(tài)均離散,具有時空計算特征的網(wǎng)格動力學模型,是一個集數(shù)學、物理學、計算機科學、生物學和系統(tǒng)科學等多學科交叉的邊緣領域,有廣泛應用前景的研究方法。當前,其應用領域廣泛涉及到社會學、生物學、生態(tài)學、信息科學、計算機科學、數(shù)學、物理學、化學、地理、環(huán)境、軍事學等,并取得了豐碩成果,如用于腫瘤細胞的增長機理、人類大腦的機理探索、航天軍事作戰(zhàn)模擬以及地理信息系統(tǒng)的開發(fā)等。但是,元胞自動機作為一種全新的方法,目前的研究仍然不完整。無論是對元胞自動機本身的演化行為及相關理論的研究,還是應用元胞自動機機理來研究其他學科,都成為研究的前沿與熱點。近年來,國內(nèi)也有一些相關的應用性研究,但要么停留在理論上,要么僅僅是某方面的應用仿真。因此,對元胞自動機的演化行為進行研究與仿真,并設計一個元胞自動機的演化行為仿真與應用系統(tǒng)是非常有必要的。本文在此基礎上,開發(fā)出了元胞自動機演化行為研究與仿真系統(tǒng)軟件,對元胞自動機的演化行為機理進行了深刻刻畫。該軟件可廣泛地應用于社會學、生物學、信息科學、數(shù)學、物理、化學等領域,將為這些學科的科學研究提供一種全新的研究技術。1元細胞自動機的發(fā)展行為統(tǒng)計特征1.1元胞自動機的演化行為元胞自動機是探討復雜系統(tǒng)中局部—整體互動關系最簡單的模式,可視為演化分析的基本計算模型。通常用兩種方法來了解元胞自動機的演化行為,即計算機仿真及數(shù)學推演。元胞自動機體現(xiàn)了整體辯證思想:用簡單的局域相互作用表現(xiàn)復雜系統(tǒng)的整體行為及其時間演化。它有三個顯著的特點,即大規(guī)模同步并行、局域相互作用和簡單結(jié)構(gòu)。這些特點使其能高效地模擬許多復雜現(xiàn)象。由于在元胞自動機中選擇不同的規(guī)則能產(chǎn)生各種不同的演化模式,通過對其演化規(guī)則和演化行為的研究來探索復雜系統(tǒng)的演化過程。沃爾弗拉姆(S.Wolfram)在詳細分析研究了一維元胞自動機的演化行為,并在大量計算機仿真的基礎上,將所有元胞自動機的演化行為歸納為四類:a)Ⅰ平穩(wěn)型(homogeneous)。自任何初始狀態(tài)開始,經(jīng)過一定時間演化和若干步運算后便停留在一個固定的狀態(tài)。b)Ⅱ周期型(periodic)。經(jīng)過一定時間演化后,在幾種狀態(tài)之間周期循環(huán)。c)Ⅲ混沌型(chaos)。自任何初始狀態(tài)開始,經(jīng)過一定時間演化后,處于一種完全無序隨機的狀態(tài),幾乎找不到任何規(guī)律。d)Ⅳ復雜型(edgeofchaos)。在演化過程中可能產(chǎn)生復雜的結(jié)構(gòu)。這種結(jié)構(gòu)既不是完全的隨機混亂,又沒有固定的周期和狀態(tài)。在元胞自動機的演化行為研究與仿真系統(tǒng)中觀察分析元胞自動機的演化行為,如圖1(a)～(d)所示。在一維最簡元胞自動機的情況下(狀態(tài)數(shù)是2,半徑是1),從圖1(a)觀察132號元胞自動機變成了一條豎線,表明132號規(guī)則的元胞自動機被吸引到了一個固定的狀態(tài)。圖1(b)中208號元胞自動機是若干條斜線。由于邊界是循環(huán)的,可以預言,經(jīng)過若干個時間周期的運行后,元胞自動機將回復到原來的狀態(tài),這樣的元胞自動機是循環(huán)的。兩個相同狀態(tài)之間經(jīng)歷的時間步長為這種元胞自動機的周期。圖1(c)中203號元胞自動機既沒有固定的周期也沒有被吸引到一個點,它們處于一種混亂的、無序的狀態(tài),稱這種狀態(tài)為混沌狀態(tài)。通過反復運行最簡元胞自動機程序可見,所有的256種元胞自動機都能被歸為固定值、周期循環(huán)、混沌三類。是不是所有元胞自動機的演化行為只有這三種類型呢?考慮稍微復雜一點的情況,狀態(tài)數(shù)為2,鄰居半徑為2的一維元胞自動機的情況。在這樣的元胞自動機中,除了上面敘述的三種類別依然存在外,還發(fā)現(xiàn)了另一種類型,如圖1(d)所示。其運行圖好像一棵倒掛的葡萄藤。這種葡萄藤是一種復雜的結(jié)構(gòu),它既不等同于完全的隨機,又沒有固定的循環(huán)跡象。這種復雜結(jié)構(gòu)正是筆者感興趣的一種類型。因為它既沒有被吸引到固定的點或周期狀態(tài)而變得死板,又沒有因為隨機而過于活躍;它既保證了一定的流動活性,同時又能產(chǎn)生具有記憶性的結(jié)構(gòu)。該運行情況顯然不同于前面敘述的三種類別,稱其為復雜型。幾乎所有的一維元胞自動機運行的演化行為都能歸到沃爾弗拉姆所劃分的四類之中。經(jīng)過沃爾弗拉姆研究,發(fā)現(xiàn)可用參數(shù)λ來劃分元胞自動機的類型。定義參數(shù)λ=(m2r+1-nq)/m2r+1。其中:m為狀態(tài)集S={s1,…,sm}中的狀態(tài)數(shù);r為鄰居半徑;nq是所有輸出項為0的個數(shù)。因此,λ參數(shù)反映了一組規(guī)則中轉(zhuǎn)換成非零狀態(tài)的比例。根據(jù)參數(shù)λ的取值不同,分析元胞自動機的演化行為:a)當λ=0～0.1,所有的元胞被吸引到一種固定的狀態(tài),即為第一類元胞自動機。b)λ=0.2附近,系統(tǒng)在一些固定狀態(tài)之間周期循環(huán),這相當于第二類元胞自動機。λ=0.3的元胞自動機相比λ=0.2的在開始時具有更復雜的結(jié)構(gòu)。c)λ在0.3～0.6時,會出現(xiàn)相當復雜的結(jié)構(gòu)。這些結(jié)構(gòu)既不屬于固定周期或固定值,也不屬于完全的隨機。因此這些元胞自動機屬于第四類即復雜型。隨著λ的增長,復雜結(jié)構(gòu)的維持時間會變得越來越大。d)λ≥0.6時,復雜結(jié)構(gòu)消失,系統(tǒng)將被吸引到一種完全隨機的混沌狀態(tài)。綜上所述,隨著λ的增大,元胞自動機展現(xiàn)出來的結(jié)構(gòu)將逐漸變得復雜。當λ介于一個中間值時,演化行為會達到最大的復雜性;隨著λ的進一步增大,復雜結(jié)構(gòu)會逐漸被隨機結(jié)構(gòu)所取代。根據(jù)λ的連續(xù)變化,能夠得到四種元胞自動機之間的過渡轉(zhuǎn)換形態(tài):Ⅰ->Ⅱ->Ⅳ->Ⅲ,即固定點->周期->復雜->混沌。元胞自動機的第Ⅲ類型是完全隨機、無序,這類系統(tǒng)過于松散,不可能產(chǎn)生有價值的結(jié)構(gòu)。第Ⅳ類元胞自動機剛好存在于從有序到無序之間一個狹小的空間中。在這里,復雜結(jié)構(gòu)形成了神奇的王國,會不斷地看到若干局部結(jié)合成有趣的結(jié)構(gòu)與秩序,但同時這些結(jié)構(gòu)和秩序永遠不會被凍結(jié),它們偶爾會被破壞,但新的結(jié)構(gòu)馬上又會生成。這樣的狀態(tài)被人工生命之父郎頓稱為混沌與秩序的邊緣。科學家們已經(jīng)對有序、隨機的性質(zhì)有了清楚的研究,然而對于從有序到無序轉(zhuǎn)變的過程則仍然沒有足夠認識。原因在于這樣的狀態(tài)具有太多復雜的結(jié)構(gòu),很難預言它的具體性質(zhì)。第Ⅳ類元胞自動機也是這樣,下一時刻元胞自動機會是怎樣的情況?除了按照其物理規(guī)律運行外別無他法,因為復雜的元胞自動機的行為不能預言。復雜的結(jié)構(gòu)誕生于混沌的邊緣。把混沌邊緣的概念推廣,也就是把秩序、周期這些動態(tài)情況看做是一種凝固的吸引力,它保證了系統(tǒng)能夠固定于某一種結(jié)構(gòu);另一方面,隨機、混沌形成了另一種張力,使得系統(tǒng)趨于不穩(wěn)定,但同時為系統(tǒng)提供了創(chuàng)新的動力。僅僅當這兩種力處于一種恰到好處的平衡態(tài)時,也就是系統(tǒng)處于混沌的邊緣條件下,該系統(tǒng)才會更加有活力,并且演變得越來越復雜。1.2初始元胞自動機的分類通過前面對一維元胞自動機機理的分析,可見元胞自動機是通過簡單的規(guī)則進行演化,產(chǎn)生復雜的行為,并在大量的計算機仿真基礎上,將所有元胞自動機的演化行為歸納為平穩(wěn)型、周期型、混沌型和復雜型四大類。對最簡單的初等元胞自動機的分類尚且如此困難,而二維以至三維的規(guī)則更多,演化行為更為復雜,對二維或三維元胞自動機進行系統(tǒng)分類就更是難以進行。目前,國內(nèi)外還沒有相關的較好的研究成果。下面將對二、三維元胞自動機的分類從統(tǒng)計和漸進的角度進行探索。1基于周期目標的分類方法在理論上,元胞自動機的演化空間通常在各維上是無限延展的,這有利于在理論上的推理和研究。在實際應用過程中,無法在計算機上實現(xiàn)這一理想條件,因此,需要定義不同的邊界條件。歸納起來,邊界條件主要有三種類型,即周期型、反射型和定值型。在應用中,這三種邊界條件為更加客觀、自然地模擬實際現(xiàn)象,還有可能采用隨機型,即在邊界實時產(chǎn)生隨機值。a)周期型(periodicboundary)是指相對邊界連接起來的元胞空間。對于一維空間,元胞空間表現(xiàn)為一個首尾相接的圈;對于二維空間,上下相接、左右相接,形成一個拓撲圓環(huán)面(torus)。周期型空間與無限空間最為接近,因而在理論探討時,常以此類空間型作為試驗。本文以周期型邊界為前提來進行討論。b)反射型(reflectiveboundary)是指在邊界外,鄰居的元胞狀態(tài)是以邊界為軸的鏡面反射。c)定值型(constantboundary)是指所有邊界外,元胞均取某一固定常量,如0、1等。d)隨機型(randomboundary)是指邊界元胞取實時產(chǎn)生的隨機值。在進行統(tǒng)計漸進分類時有三個前提:邊界條件是周期型;元胞狀態(tài)是兩狀態(tài)的,即生和死;初始條件是一個中心元胞狀態(tài)為生,其他元胞狀態(tài)為死。在上述前提下,某一規(guī)則的元胞自動機演化到一定步數(shù)后,若其生的元胞比例趨于穩(wěn)定,則為穩(wěn)定型;若出現(xiàn)周期性的變化,則為周期型;若無明顯規(guī)律,則為復雜型。可以看到,這種分類方法是根據(jù)元胞演化過程中的統(tǒng)計性質(zhì)來分類的,并且是一種漸進(極限)情況下的統(tǒng)計性質(zhì)。在具體判斷某一規(guī)則是否為穩(wěn)定型時,本文使用元胞自動機演化行為仿真系統(tǒng)。22二維進化行為的漸進性分析(1)元胞共生的狀態(tài)某一規(guī)則是穩(wěn)定型是指當其初始條件為一個中心元胞狀態(tài)是生時,在經(jīng)過有限步演化后,生的元胞比率趨于平穩(wěn)(或不變)。圖2是能夠生成自相似圖形的規(guī)則動態(tài)統(tǒng)計圖。其規(guī)則是Si={1Si+1=10f(4)=1或4時?Si+1=1；否則Si+1=0其中:Si表示元胞在i時刻的狀態(tài);Si+1表示元胞在i+1時刻即下一時刻的狀態(tài);f(4)中的4表示鄰居類型為4鄰胞,其取值表示鄰居狀態(tài)為生的元胞數(shù)目之和。圖3是演化到第26步時的行為,可以看到明顯的自相似現(xiàn)象。當演化到第64步時就已經(jīng)穩(wěn)定(不變)了,這時元胞為生的比例為λ=0.6352,在沃爾弗拉姆的分類中,表示復雜型演化行為。從演化行為的仿真例子可以看到穩(wěn)定型的兩種類型:a)演化到一定步數(shù)后生的元胞比例恒為某一個常數(shù)不變;b)演化到一定步數(shù)后趨于穩(wěn)定,但不是常數(shù),有一定的上下波動,但波動幅度非常小。(2)生成n、n-qp的si、nfb圖像某一規(guī)則是周期型是指當其初始條件為中心一個元胞狀態(tài)是生時,在經(jīng)過有限步演化后,生的元胞比率趨于某一周期性的變化。圖4是在第1步后就開始周期性變化。其規(guī)則是Si={1f(8)=0或8時?Si+1=1；否則Si+1=00f(8)=1或7時,Si+1=1;否則Si+1=0圖5是其演化到第10步和15步時的圖像,其周期為57,這個規(guī)則的圖像非常奇特有趣。對應地,在沃爾弗拉姆的分類中,表示穩(wěn)定型演化行為。從演化行為的仿真例子可以看到周期型的兩種類型:a)演化到一定步數(shù)后,生的元胞比例是一種簡單周期,即周期為幾類圖案交替出現(xiàn);b)演化到一定步數(shù)后也出現(xiàn)周期,但周期較長,且每一個周期內(nèi)部還存在小周期(部分周期)。(3)各步模擬的圖像不屬于以上兩種類型的統(tǒng)稱為復雜型,即其動態(tài)統(tǒng)計圖是無規(guī)則波動的曲線。圖6是復雜型規(guī)則的動態(tài)統(tǒng)計圖。其規(guī)則是Si={1f(8)=2、4、6、8時?Si+1=1；否則Si+1=00f(8)=1、3、5、7時?Si+1=1；否則Si+1=0圖7是演化到第154步和155步時的圖像。這類情形僅從統(tǒng)計圖上來看還不是太復雜,雖然波動幅度稍微有點大,但還算是比較穩(wěn)定。由于其演化圖非常復雜,沒有什么規(guī)律,歸為復雜類。對應的λ=0.468,在沃爾弗拉姆的分類中,表示復雜型演化行為。33三維行為的漸進統(tǒng)計分類(1)元胞自動機分類前提類似于二維元胞自動機統(tǒng)計漸進分類的原理,可以給出三維元胞自動機統(tǒng)計漸進分類的原理。三個前提是:邊界條件是定值型;元胞狀態(tài)是兩狀態(tài)的,即生和死;初始條件是各元胞狀態(tài)以0.5的概率為生。與二維元胞自動機統(tǒng)計漸進分類的前提相比:a)條件變成了定值型。這是因為周期型的三維邊界在計算機上實現(xiàn)比較困難(包括算法和運算速度兩個困難),但這個對分類來說并沒有太大影響。b)初始條件變成了隨機型的初始條件。這個對于對初始條件特別敏感的規(guī)則來說影響較大,但可以通過多次重復進行仿真實驗來消除影響。在上述前提下,某一規(guī)則的元胞自動機演化到一定步數(shù)后,若其生的元胞比例趨于穩(wěn)定,則為穩(wěn)定型;若出現(xiàn)周期性的變化,則為周期型;若無明顯規(guī)律,則為復雜型。(2)三維行為的漸進性分析模型1:三維漸進穩(wěn)定型Si={1f(26)=0、1、4、5、6、8、9、12、13、16、17、20、21、25、26時?Si+1=1；否則Si+1=00f(26)=1、5、9、13、17、21、25時?Si+1=1；否則Si+1=0動態(tài)統(tǒng)計圖如圖8所示,演化到第118步時的圖像如圖9所示。從動態(tài)統(tǒng)計圖可見,此演化規(guī)則對應于三維漸進穩(wěn)定型的演化行為。對應地,λ=0.259,在沃爾弗拉姆的分類中,表示周期型演化行為。《決定》是網(wǎng)型的演化規(guī)則Si={1f(26)=0、1、25、26時?Si+1=1；否則Si+1=00f(26)=5、8、20、23時?Si+1=1；否則Si+1=0動態(tài)統(tǒng)計圖如圖10所示,演化到第20步時的圖形如圖11所示。其演化行為呈漸進周期狀態(tài)。從圖10可見,此演化規(guī)則對應于三維漸進周期型的演化行為。對應地,λ=0.307,在沃爾弗拉姆的分類中,表示周期型演化行為。si+1:2Si={1f(26)=1、12、13、23時?Si+1=1；否則Si+1=00f(26)=0、4、24、26時?Si+1=1；否則Si+1=0動態(tài)統(tǒng)計圖如圖12所示,演化到第14步時的圖像如圖13所示。其演化行為呈無規(guī)則狀態(tài),為復雜型演化行為。從圖12可見,此演化規(guī)則對應于三維復雜型的演化行為。對應地,λ=0.16,在沃爾弗拉姆的分類中,表示周期型演化行為。2實際仿真情況下元胞自動機演化行為的仿真結(jié)果綜上所述,沃爾弗拉姆對于元胞自動機的分類以及混沌邊緣的概念,不僅僅適用于一維元胞自動