一維細胞自動機探索

一維細胞自動機探索（1）最簡一維細胞自動機

最簡單的一維細胞自動機的狀態(tài)集合為兩個元素{0,1}。鄰居是一個半徑為1的區(qū)域，也就是每一個方格的左、右兩個方格是它的鄰居，這樣每一個方格單元和它的鄰居可以表示如下：

黑色的方格是當前細胞，兩邊的灰色方格是它的鄰居。由于狀態(tài)集只有{0，1}兩個狀態(tài)，也就是說方格只能有黑、白兩種顏色，那么任意的一個方格加上它的兩個鄰居，這3個方格的狀態(tài)組合一共就有8種。這8種情況為下圖示：

他們表示的狀態(tài)分別是：111，110，101，100，011，010，001，000。也就是說對于狀態(tài)數(shù)為2，鄰居半徑為1的所有一維細胞自動機的鄰居和其自身的狀態(tài)組合就這8種。（2）規(guī)則與編號

下面考慮規(guī)則。假設當前考慮的細胞為ci，他在t時刻的狀態(tài)為si,t，而它的兩個鄰居狀態(tài)為si-1,t，si+1,t，則ci在下一時刻的狀態(tài)為si,t+1，則轉換規(guī)則用函數(shù)表示為：si,t+1=f(si-1,t,si,t,si+1,t)其中，si,t∈{0,1}，對于任意的i和t

由于在我們這個最簡單的細胞自動機中每個細胞和它的鄰居狀態(tài)的所有可能組合就上面列出來的8種，所以它的輸入就是上面列出的8種組合之一，輸出表示的是每個細胞下一時刻的狀態(tài)，而狀態(tài)只可能有0、1兩種，則規(guī)則的輸出要么是0，要么是1。這樣，任何一個規(guī)則就是一個或者一組轉換，比如下圖表示的就是一個規(guī)則：

↓↓↓↓

↓↓↓↓

這個規(guī)則也可以列為下面的表：輸入111110101100011010001000輸出10100011

那么這組規(guī)則就對應著編碼：10100011，也就是把八個位置上的方格進行一個排列。我們可以把輸出部分的二進制編碼轉換成十進制數(shù)的形式：163，這就是該細胞自動機的編碼。當狀態(tài)數(shù)增多，半徑增大的時候，這種編碼方式就不實用了，我們需要用另一種方式來編碼。考慮下面這樣的規(guī)則若有一個規(guī)則是：“如果輸入的三個方格中黑色方格只有1個，那么下一時刻當前方格就是黑色；如果有兩個黑色方格，則下時刻是白色，如果有三個方格，則下時刻是黑色，如果有4個方格，那么下一時刻是白色”可以表示成下面的函數(shù)表：si,t+1=1，如果si-1,t+si,t+si+1,t=1

si,t+1=0，如果si-1,t+si,t+si+1,t=2

si,t+1=1，如果si-1,t+si,t+si+1,t=3

si,t+1=0，如果si-1,t+si,t+si+1,t=0其中，si,t∈{0,1}，對于任意的i和t

這種情況下，輸入就僅僅有4種情況，因此可以得到下面的表：輸入0123輸出0101

同樣的道理，我們可以對它進行編碼為：0101，表示為十進制就是5。顯然，這種編碼方式比前一種短，但是這種編碼方法不能反映所有的細胞自動機。（4）最簡一維細胞自動機的動態(tài)行為

對于一維的情況，我們假設所有的方格都分布在一條直線上，并且直線的長度為我們動畫區(qū)域的寬度，比如說是400，也就是說有400個方格在這條直線上。我們用黑色的格表示直線上1狀態(tài)的方格，用白色的格表示0狀態(tài)的方格。那么一條斷續(xù)的橫線就是當前所有細胞狀態(tài)的一種分布。這些方格隨著時間變化，就形成了不同的橫線。我們把這些隨著時間變化的線縱向拼在一起形成了一個網(wǎng)格區(qū)域。其中縱軸表示時間的流逝（往下為正），橫軸為細胞自動機在對應時刻的狀態(tài)，就能得到一幅圖像。這就是上面的示例程序所表演的，變換不同的編碼參數(shù)，你會看到，觀察它們的動態(tài)行為。

在最簡細胞自動機的情況下（狀態(tài)數(shù)是2，半徑是1），這些細胞自動機分成3類。觀察224號（長編碼）細胞自動機，從上而下出現(xiàn)了一些細胞，之后就逐漸變成了全白色，也就是說經(jīng)過幾個時間步的運行后，細胞自動機全部變?yōu)榱斯潭顟B(tài)0（也就是白色的方格），并再也不變化了。而132號和203號細胞自動機都是變成了幾個豎線。不要忘了每一行就是某一時刻細胞自動機的一個狀態(tài)，因此在豎向上能夠形成一條豎線就說明這個細胞的狀態(tài)在時間軸上沒有變化。所以132號、203號與224號它們被吸引到了一個固定的狀態(tài)。

再看208號細胞自動機，它是若干條斜的線。由于我們的邊界是循環(huán)的，因此可以預言，經(jīng)過若干個時間周期的運行以后，細胞自動機又回復到了原來的狀態(tài)，因而這樣的細胞自動機是循環(huán)的。兩個相同狀態(tài)之間經(jīng)歷的時間步長為這種細胞自動機的周期。再看150號和151號細胞自動機，他們顯然既沒有固定的周期也沒有被吸引到一個點，它們是出于一種混亂的、無序的狀態(tài)，我們稱這種狀態(tài)為混沌狀態(tài)。通過反復的運行最簡細胞自動機程序我們不難發(fā)現(xiàn)，所有的256種細胞自動機都能被歸為這三類：固定值、周期循環(huán)、混沌之一。

我們可以猜想，是不是所有的細胞自動機的動態(tài)行為就這三種類型呢？讓我們把探索的疆域擴大到稍微復雜一點的情況，我們考慮狀態(tài)數(shù)為2，鄰居半徑為2（也就是說每個細胞都有4個鄰居，左右兩邊各兩個），仍然是一維的情況。在這樣的細胞自動機中除了上面敘述的三種類別依然存在外，我們還發(fā)現(xiàn)了另一種類型，請看20號（按照短編碼方案）和52號（按照短編碼方案）這兩個細胞自動機的動態(tài)運行圖竟然如此怪異，就好像一棵倒掛的葡萄藤。這種葡萄藤是一種復雜的結構，它既不等同于完全的隨機，又沒有固定的循環(huán)的跡象。這種復雜結構正是我們感興趣的一種類型，因為它既沒有被吸引到固定的點或周期狀態(tài)而變得死板，又沒有因為隨機而過于活躍；它既保證了一定的流動活性，同時又能產(chǎn)生具有“記憶性”的結構。該運行情況顯然不同于前面敘述的三種類別，所以我們稱其為復雜型。繼續(xù)運行各種參數(shù)的一維細胞自動機，我們發(fā)現(xiàn)幾乎所有的一維細胞自動機運行的動態(tài)行為都能被劃分為這四類情況。

綜合上面的討論，我們把細胞自動機歸為四種類別，它們分別是：I、固定值型：細胞自動機經(jīng)過若干步運算便停留在一個固定的狀態(tài)；

II、周期型：細胞自動機在幾種狀態(tài)之間周期循環(huán)；

III、混沌型：細胞自動機處于一種完全無序隨機的狀態(tài)，幾乎找不到任何規(guī)律；

IV、復雜型：細胞自動機在運行的過程中可能產(chǎn)生復雜的結構，這種結構既不是完全的隨機混亂，又沒有固定的周期和狀態(tài)。

上面我們僅僅就一維細胞自動機的情況作了介紹，二維細胞自動機也無非就是這4種情況之一。其實我們想一下，前面介紹的“生命游戲”屬于哪種類型呢？當然應該是第IV種。只有復雜的類型才會給我們帶來永恒的新奇。

下面我們自然會思考一個問題，為什么細胞自動機會有這幾種類型？它們之間有沒有什么聯(lián)系呢？混沌的邊緣

運行上面的程序，觀察λ的不同，細胞自動機產(chǎn)生的動態(tài)行為如何變化。拖動中間的滑塊可以更改λ的數(shù)值。右邊New按鈕可以在當前的λ下隨機產(chǎn)生新的規(guī)則，底下的幾個選擇框分別更改狀態(tài)個數(shù)、鄰居模板個數(shù)（注意這個數(shù)字包括該細胞自己，比如N=5，那么左邊兩個細胞，右邊兩個細胞，再加上中間的細胞，所以鄰居半徑是2），Isotropic表示規(guī)則是不區(qū)分左右對稱的方格狀態(tài)的，Anisotropic則是區(qū)分的，因此Anisotropic產(chǎn)生的編碼比較長，下面的RandomStart表示從一個隨機的狀態(tài)開始，RandomClump表示從一個隨機的小塊開始演化。OneDotStart表示從一個點的初始狀態(tài)開始演化。下面的文本框里面顯示的是當前規(guī)則的編碼。下面將具體說明其中的原理。

為了更好的看清楚細胞自動機的動態(tài)行為，我們選用4個狀態(tài){0,1,2,3}，鄰居半徑為2（一共4個鄰居）的一維細胞自動機來討論，因為這種細胞自動機包含了所有的四種類別。

我們知道，在給定了狀態(tài)集{0,1,2,3}，鄰居半徑2的一維情況下，細胞自動機的規(guī)則集決定了它們的不同。每一個細胞自動機的規(guī)則集都可以看成是一張大的轉換表，形如：輸入012030312012231……輸出012……

其中每個輸入的5位數(shù)字串中，中間的一個表示當前細胞的t時刻的狀態(tài)，兩邊的數(shù)字都是它的鄰居狀態(tài)，而輸出則對應當前細胞在t+1時刻的狀態(tài)。表中一共有45=1024項，這其中有些輸出項為0狀態(tài)，有些不為0，我們把所有輸出項為0的個數(shù)記為nq。那么我們可以定義參數(shù)：λ=(45-nq)/45

這個參數(shù)反映了一組規(guī)則中轉換成非0狀態(tài)的比例。顯然，根據(jù)給定的λ我們可以得到很多的規(guī)則表，因此我們可以隨機的在這些規(guī)則表中選擇一個。比如令λ=0.5，那么我們可以隨機的生成一個規(guī)則組轉換表，表的輸出部分0狀態(tài)占據(jù)了一半的比例，其他的位置由1,2,3這幾個數(shù)隨機的填充。

下面看看根據(jù)參數(shù)λ的取值不同，細胞自動機的動態(tài)行為如何變化。請運行上面的程序，讓λ在0到1之間變化。當λ=0~0.1，所有的細胞被吸引到一種固定的狀態(tài)，這相當于我們上一節(jié)敘述的第一類細胞自動機；λ=0.2附近，系統(tǒng)在一些固定的狀態(tài)之間周期的循環(huán)，這相當于第二類細胞自動機，λ=0.3的細胞自動機比λ=0.2的在開始的時候具有更復雜的結構；λ介于大約0.3到0.6之間的時候，會出現(xiàn)相當復雜的結構。這些結構既不屬于固定的周期或者固定值，也不屬于完全的隨機，因此這些細胞自動機屬于第四類即“復雜型”。并且，隨著λ的增長，復雜結構的維持時間也會變得越來越大；λ>=0.6的時候，復雜的結構消失，系統(tǒng)將被吸引于一種完全隨機的混沌狀態(tài)。

由于在實驗中，規(guī)則是根據(jù)λ隨機產(chǎn)生的，因此我們在這里說明的動態(tài)行為隨λ的變化性質(zhì)僅僅是一種大致的分類。

根據(jù)這些試驗，我們不難得出，隨著λ的增大，細胞自動機展現(xiàn)出來的結構將逐漸變得復雜，當λ介于一個中間值的時候動態(tài)行為會達到最大的復雜性，然后隨著λ的進一步增大復雜結構就逐漸被隨機結構所取代。

根據(jù)λ的連續(xù)變化能夠得到四種細胞自動機之間的過渡轉化圖景：I->II->IV->III，即：固定點->周期->復雜->混沌

因此我們說，復雜的結構誕生于混沌的邊緣?；煦绲倪吘壥鞘裁礀|西？它是一種處于凝固的周期狀態(tài)與活躍的混沌之間的一種過渡過程，或者我們稱其為“相變過程”。所謂的“相變”就是指系統(tǒng)從量變到質(zhì)變的飛躍。就像煮開水，當溫度達到100度左右的時候，水會突然沸騰，這種狀態(tài)就是相變，因為從此水由液態(tài)變成了氣態(tài)。

細胞自動機系統(tǒng)的連續(xù)變化過程就好像水的固、液以及固態(tài)到液態(tài)之間的的變化過程。如下：I&II->IV->III

固體->相變->液體

I和II兩種狀態(tài)可以被看作是固態(tài)，就像冰一樣凝固在一起非常有秩序但同時也沒有活性。細胞自動機的第III類型就象是液態(tài)的水：完全的流動、隨機，沒有一個時刻能停留下來，然而由于這類系統(tǒng)過于松散，它也不可能產(chǎn)生有價值的結構。第IV類細胞自動機就剛好存在于從固態(tài)的冰到液態(tài)的水轉變的瞬息之間這么一個狹小的空間里。在這里，復雜的結構形成了神奇的王國，你會不斷地看到若干水分子結合成有趣的結構與秩序，但同時這些結構和秩序永遠不會被凍結，它們會偶爾被破壞，但新的結構馬上又會生成。這樣的狀態(tài)被“人工生命”之父郎頓稱為混沌與秩序的邊緣?？茖W家們已經(jīng)對固體、液體的性質(zhì)研究的比較清楚了，然而對于固體到液體轉變這樣一種相變的過程則仍然沒有認識足夠清楚，原因就在于這樣的狀態(tài)具有太多復雜的結構，我們很難預言它的具體性質(zhì)。第IV類細胞自動機也是這樣，下一時刻細胞自動機會是怎樣的情況？我們除了按照它的“物理規(guī)律”運行它外別無它法，因為復雜的細胞自動機的行為不能預言。

我們可以把混沌邊緣的概念推廣，也就是把秩序、周期這些動態(tài)的情況看作是一種凝固的吸引力，它保證了系統(tǒng)能夠固定于某一種結構；而另一方面，隨機、混沌則形成了另一種張力，它使得系統(tǒng)趨于不穩(wěn)定，但同時為系統(tǒng)提供了創(chuàng)新的動力。那么僅僅當這兩種力處于一種恰到好處的平衡態(tài)的時候，也就是系統(tǒng)處于混沌的邊緣條件下，該系統(tǒng)才會更加有活力，并且演變得越來越復雜。

生命從何處來？智能如何產(chǎn)生？人們?yōu)槭裁磿?chuàng)造有組織的同時又具有創(chuàng)新性的社會結構？答案是這些復雜的系統(tǒng)、復雜的結構來自于混沌的邊緣。只有當生命所處的環(huán)境既不太“熱”，即沒有太大的動蕩產(chǎn)生完全隨機的混沌狀態(tài)，同時又不能太“冷”，以至于所有活動都過于死板，這樣才能孕育真正的生命。因此地球上的生命正是誕生于混沌的邊緣這條狹窄的夾縫中。再考慮一個人的發(fā)展。如果一個人每天都在做同樣的事情，從不嘗試新鮮的生活，那么這個人所處的環(huán)境就過于死板最后將陷于一種機械循環(huán)的狀態(tài)（第I、II類細胞自動機）。反過來，如果這個人過于渙散，總在嘗試不同的新鮮事情，從來不會停下來靜靜的思考和沉淀，那么這個人就會過于靈活而也會一事無成。一個人只有處在“混沌邊緣”的狀態(tài)才能既產(chǎn)生學習、進化的動力，又會靜下心來讓所學的東西凝固成有價值的知識，從而創(chuàng)造輝煌的成果。再考慮一個國家，閉關鎖國肯定不能發(fā)展，系統(tǒng)將會變成一潭死水，反過來過于開放則根本不會形成這個國家這個民族的凝聚力也就失去了它們的個性，所以社會也要不停地把自己推向混沌邊緣的狀態(tài)才能不斷的發(fā)展下去。

系統(tǒng)為什么總要處于“混沌邊緣”的狀態(tài)呢？比如生命吧，靜止于某種固定的狀態(tài)不是挺好的么？為了適應多變的環(huán)境，生命必須不斷的進化而變得復雜，而要想變得復雜就必須讓自己處于混沌邊緣的狀