元胞自動機的演化行為研究

摘要：基于元胞自動機演化行為研究與仿真系統，通過對元胞自動機的一、二、三維演化行為的研究，從統計和漸進的角度對元胞自動機進行了分類，將元胞自動機的演化行為動態統計圖與沃爾弗拉姆對于元胞自動機的分類對應起來研究。這些從不同視角得到的結果有助于對元胞自動機的演化行為進行深入研究；但從統計和漸進的角度對元胞自動機進行分類是否具有普適性，是需要進一步研究探討的問題。

關鍵詞：元胞自動機； 演化行為； 統計； 漸進； 復雜系統

中圖分類號：TP391.41文獻標志碼：A

文章編號：1001－3695(2007)08－0038－04

元胞自動機是21世紀科學研究中一個異常活躍的前沿領域，是復雜性科學的核心技術之一。元胞自動機是一種時間、空間、狀態均離散，具有時空計算特征的網格動力學模型，是一個集數學、物理學、計算機科學、生物學和系統科學等多學科交叉的邊緣領域，有廣泛應用前景的研究方法[1]。當前，其應用領域廣泛涉及到社會學、生物學、生態學、信息科學、計算機科學、數學、物理學、化學、地理、環境、軍事學等，并取得了豐碩成果，如用于腫瘤細胞的增長機理、人類大腦的機理探索、航天軍事作戰模擬以及地理信息系統的開發等。

但是，元胞自動機作為一種全新的方法，目前的研究仍然不完整。無論是對元胞自動機本身的演化行為及相關理論的研究，還是應用元胞自動機機理來研究其他學科，都成為研究的前沿與熱點[2]。近年來，國內也有一些相關的應用性研究，但要么停留在理論上，要么僅僅是某方面的應用仿真[3]。因此，對元胞自動機的演化行為進行研究與仿真，并設計一個元胞自動機的演化行為仿真與應用系統是非常有必要的。本文在此基礎上，開發出了元胞自動機演化行為研究與仿真系統軟件，對元胞自動機的演化行為機理進行了深刻刻畫。該軟件可廣泛地應用于社會學、生物學、信息科學、數學、物理、化學等領域，將為這些學科的科學研究提供一種全新的研究技術。

1元胞自動機的演化行為統計特征

1．1 一維元胞自動機的演化行為

元胞自動機是探討復雜系統中局部—整體互動關系最簡單的模式，可視為演化分析的基本計算模型。通常用兩種方法來了解元胞自動機的演化行為，即計算機仿真及數學推演。元胞自動機體現了整體辯證思想：用簡單的局域相互作用表現復雜系統的整體行為及其時間演化。它有三個顯著的特點，即大規模同步并行、局域相互作用和簡單結構。這些特點使其能高效地模擬許多復雜現象[5，6]。由于在元胞自動機中選擇不同的規則能產生各種不同的演化模式，通過對其演化規則和演化行為的研究來探索復雜系統的演化過程。

沃爾弗拉姆（S. Wolfram）在詳細分析研究了一維元胞自動機的演化行為，并在大量計算機仿真的基礎上，將所有元胞自動機的演化行為歸納為四類[1]：

a)Ⅰ 平穩型（homogeneous）。自任何初始狀態開始，經過一定時間演化和若干步運算后便停留在一個固定的狀態。

b)Ⅱ 周期型(periodic)。經過一定時間演化后，在幾種狀態之間周期循環。

c)Ⅲ 混沌型(chaos)。自任何初始狀態開始，經過一定時間演化后，處于一種完全無序隨機的狀態，幾乎找不到任何規律。

d)Ⅳ 復雜型(edge of chaos)。在演化過程中可能產生復雜的結構。這種結構既不是完全的隨機混亂，又沒有固定的周期和狀態。

在元胞自動機的演化行為研究與仿真系統中觀察分析元胞自動機的演化行為，如圖1（a)~（d)所示。

(a)132號規則平穩型演化行為(b）208號規則周期型演化行為

(c）203號規則混沌型演化行為(d)Chaotic gliders復雜型演化行為

在一維最簡元胞自動機的情況下（狀態數是2，半徑是1），從圖1(a）觀察132號元胞自動機變成了一條豎線，表明132號規則的元胞自動機被吸引到了一個固定的狀態。

圖1(b）中208號元胞自動機是若干條斜線。由于邊界是循環的，可以預言，經過若干個時間周期的運行后，元胞自動機將回復到原來的狀態，這樣的元胞自動機是循環的。兩個相同狀態之間經歷的時間步長為這種元胞自動機的周期。

圖1(c)中203號元胞自動機既沒有固定的周期也沒有被吸引到一個點，它們處于一種混亂的、無序的狀態，稱這種狀態為混沌狀態。通過反復運行最簡元胞自動機程序可見，所有的256種元胞自動機都能被歸為固定值、周期循環、混沌三類。

是不是所有元胞自動機的演化行為只有這三種類型呢？考慮稍微復雜一點的情況，狀態數為2，鄰居半徑為2的一維元胞自動機的情況。在這樣的元胞自動機中，除了上面敘述的三種類別依然存在外，還發現了另一種類型，如圖1(d)所示。其運行圖好像一棵倒掛的葡萄藤。這種葡萄藤是一種復雜的結構，它既不等同于完全的隨機，又沒有固定的循環跡象。這種復雜結構正是筆者感興趣的一種類型。因為它既沒有被吸引到固定的點或周期狀態而變得死板，又沒有因為隨機而過于活躍；它既保證了一定的流動活性，同時又能產生具有記憶性的結構。該運行情況顯然不同于前面敘述的三種類別，稱其為復雜型。幾乎所有的一維元胞自動機運行的演化行為都能歸到沃爾弗拉姆所劃分的四類之中。

經過沃爾弗拉姆研究，發現可用參數λ來劃分元胞自動機的類型。定義參數

根據參數λ的取值不同，分析元胞自動機的演化行為：

a)當λ=0~0.1，所有的元胞被吸引到一種固定的狀態，即為第一類元胞自動機。

b)λ=0.2附近，系統在一些固定狀態之間周期循環，這相當于第二類元胞自動機。λ=0．3的元胞自動機相比λ=0.2的在開始時具有更復雜的結構。

c)λ在0.3~0.6時，會出現相當復雜的結構。這些結構既不屬于固定周期或固定值，也不屬于完全的隨機。因此這些元胞自動機屬于第四類即復雜型。隨著λ的增長，復雜結構的維持時間會變得越來越大。

d)λ≥0.6時，復雜結構消失，系統將被吸引到一種完全隨機的混沌狀態。

綜上所述，隨著λ的增大，元胞自動機展現出來的結構將逐漸變得復雜。當λ介于一個中間值時，演化行為會達到最大的復雜性；隨著λ的進一步增大，復雜結構會逐漸被隨機結構所取代。

根據λ的連續變化，能夠得到四種元胞自動機之間的過渡轉換形態：

元胞自動機的第Ⅲ類型是完全隨機、無序，這類系統過于松散，不可能產生有價值的結構。第Ⅳ類元胞自動機剛好存在于從有序到無序之間一個狹小的空間中。在這里，復雜結構形成了神奇的王國，會不斷地看到若干局部結合成有趣的結構與秩序，但同時這些結構和秩序永遠不會被凍結，它們偶爾會被破壞，但新的結構馬上又會生成。這樣的狀態被人工生命之父郎頓稱為混沌與秩序的邊緣。科學家們已經對有序、隨機的性質有了清楚的研究，然而對于從有序到無序轉變的過程則仍然沒有足夠認識。原因在于這樣的狀態具有太多復雜的結構，很難預言它的具體性質。第Ⅳ類元胞自動機也是這樣，下一時刻元胞自動機會是怎樣的情況？除了按照其物理規律運行外別無他法，因為復雜的元胞自動機的行為不能預言。

復雜的結構誕生于混沌的邊緣。把混沌邊緣的概念推廣，也就是把秩序、周期這些動態情況看做是一種凝固的吸引力，它保證了系統能夠固定于某一種結構；另一方面，隨機、混沌形成了另一種張力，使得系統趨于不穩定，但同時為系統提供了創新的動力。僅僅當這兩種力處于一種恰到好處的平衡態時，也就是系統處于混沌的邊緣條件下，該系統才會更加有活力，并且演變得越來越復雜。

1．2 二維及多維元胞自動機的演化行為

通過前面對一維元胞自動機機理的分析，可見元胞自動機是通過簡單的規則進行演化，產生復雜的行為，并在大量的計算機仿真基礎上，將所有元胞自動機的演化行為歸納為平穩型、周期型、混沌型和復雜型四大類。

對最簡單的初等元胞自動機的分類尚且如此困難，而二維以至三維的規則更多，演化行為更為復雜，對二維或三維元胞自動機進行系統分類就更是難以進行。目前，國內外還沒有相關的較好的研究成果。下面將對二、三維元胞自動機的分類從統計和漸進的角度進行探索。

1）統計漸進分類的原理

在理論上，元胞自動機的演化空間通常在各維上是無限延展的，這有利于在理論上的推理和研究。在實際應用過程中，無法在計算機上實現這一理想條件，因此，需要定義不同的邊界條件。歸納起來，邊界條件主要有三種類型，即周期型、反射型和定值型。在應用中，這三種邊界條件為更加客觀、自然地模擬實際現象，還有可能采用隨機型，即在邊界實時產生隨機值。

a)周期型(periodic boundary)是指相對邊界連接起來的元胞空間。對于一維空間，元胞空間表現為一個首尾相接的圈；對于二維空間，上下相接、左右相接，形成一個拓撲圓環面(torus)。周期型空間與無限空間最為接近，因而在理論探討時，常以此類空間型作為試驗。本文以周期型邊界為前提來進行討論。

b)反射型(reflective boundary)是指在邊界外，鄰居的元胞狀態是以邊界為軸的鏡面反射。

c)定值型(constant boundary)是指所有邊界外，元胞均取某一固定常量，如0、1等。

d)隨機型（random boundary）是指邊界元胞取實時產生的隨機值。

在進行統計漸進分類時有三個前提：

邊界條件是周期型；

元胞狀態是兩狀態的，即生和死；

初始條件是一個中心元胞狀態為生，其他元胞狀態為死。

在上述前提下，某一規則的元胞自動機演化到一定步數后，若其生的元胞比例趨于穩定，則為穩定型；若出現周期性的變化，則為周期型；若無明顯規律，則為復雜型。

可以看到，這種分類方法是根據元胞演化過程中的統計性質來分類的，并且是一種漸進（極限）情況下的統計性質。在具體判斷某一規則是否為穩定型時，本文使用元胞自動機演化行為仿真系統。

2）二維演化行為的漸進統計分析

(1)穩定型

某一規則是穩定型是指當其初始條件為一個中心元胞狀態是生時，在經過有限步演化后，生的元胞比率趨于平穩（或不變）。

其中：Si表示元胞在i時刻的狀態；Si+1表示元胞在i+1時刻即下一時刻的狀態； f(4)中的4表示鄰居類型為4鄰胞，其取值表示鄰居狀態為生的元胞數目之和。圖3是演化到第26步時的行為，可以看到明顯的自相似現象。當演化到第64步時就已經穩定（不變）了，這時元胞為生的比例為λ=0．635 2，在沃爾弗拉姆的分類中，表示復雜型演化行為。

圖2自相似圖形的動態統計圖圖3演化的自相似圖形

從演化行為的仿真例子可以看到穩定型的兩種類型：a)演化到一定步數后生的元胞比例恒為某一個常數不變；b)演化到一定步數后趨于穩定，但不是常數，有一定的上下波動，但波動幅度非常小。

（2）周期型

某一規則是周期型是指當其初始條件為中心一個元胞狀態是生時，在經過有限步演化后，生的元胞比率趨于某一周期性的變化。

圖5是其演化到第10步和15步時的圖像，其周期為57，這個規則的圖像非常奇特有趣。對應地，在沃爾弗拉姆的分類中，表示穩定型演化行為。

從演化行為的仿真例子可以看到周期型的兩種類型：a)演化到一定步數后，生的元胞比例是一種簡單周期，即周期為幾類圖案交替出現；b)演化到一定步數后也出現周期，但周期較長，且每一個周期內部還存在小周期（部分周期）。

（3）復雜型

不屬于以上兩種類型的統稱為復雜型，即其動態統計圖是無規則波動的曲線。

圖7是演化到第154步和155步時的圖像。這類情形僅從統計圖上來看還不是太復雜，雖然波動幅度稍微有點大，但還算是比較穩定。由于其演化圖非常復雜，沒有什么規律，歸為復雜類。對應的λ=0.468，在沃爾弗拉姆的分類中，表示復雜型演化行為。

3）三維演化行為的漸進統計分類探索

（1）三維元胞自動機統計漸進分類的原理

類似于二維元胞自動機統計漸進分類的原理，可以給出三維元胞自動機統計漸進分類的原理。三個前提是：

邊界條件是定值型；

元胞狀態是兩狀態的，即生和死；

初始條件是各元胞狀態以0.5的概率為生。

與二維元胞自動機統計漸進分類的前提相比：a）條件變成了定值型。這是因為周期型的三維邊界在計算機上實現比較困難（包括算法和運算速度兩個困難），但這個對分類來說并沒有太大影響。b）初始條件變成了隨機型的初始條件。這個對于對初始條件特別敏感的規則來說影響較大，但可以通過多次重復進行仿真實驗來消除影響。

在上述前提下，某一規則的元胞自動機演化到一定步數后，若其生的元胞比例趨于穩定，則為穩定型；若出現周期性的變化，則為周期型；若無明顯規律，則為復雜型。

（2）三維演化行為的漸進統計分析

①穩定型演化規則

2結束語

綜上所述，沃爾弗拉姆對于元胞自動機的分類以及混沌邊緣的概念，不僅僅適用于一維元胞自動機，對于二維甚至多維元胞自動機仍然適用。本文從統計和漸進的角度對元胞自動機進行了分類，從實際仿真情況來看，大多數屬于穩定型和周期型，復雜型比較少。在實際仿真時發現，在統計上有規律的在其演化行為上可能表現得非常凌亂和無規律；而有些在演化圖形上非常有規律的，在統計上局部卻看不到什么規律，但從長期來看，卻是周期的或是穩定的。可以認為這些是局部復雜的，但全局服從一定的統計規律。

本文對于二維和三維元胞自動機分類的探討只是初步的。本文最有意義的工作是開發出了一個完整的元胞自動機演化行為研究與仿真系統。元胞自動機演化行為的仿真是進行元胞自動機演化行為研究及應用的必要手段，本系統可以提供一個很好的平臺。

參考文獻：

［1］WOLFRAM S. A new kind of science[M]. [S.l.]: Wolfram Media， Inc.，2002:231－249.

[2］WOLFRAM S. Theory and applications of cellular automata[M]. [S.l.]:World Scientific Publishing Co. PTE Ltd， 1986:203－220.

[3］周成虎，孫戰利，謝一春.地理元胞自動機研究[M].北京：科學出版社，1999：26－50.

[4］WEISBUCH G. Complex system dynamics: an introduction to auto￣mata networks[M]. [S.l.]:AddisonWesley Publishing Company，1991:113140.

[5］PLATEAU B，ATIF K. Stochastic automata network for modeling para￣llel systems[J].IEEE Trans on Software，Engineering，1991，17（10），10831108.

[6］PALADIN E.變異和演化——演化理論簡述[EB/OL].http://www2.hkedcity.net/citizen_files/aa/bs/fy1379/public_html/evolve.htm.

[7］鄧黎，王仲君.擴展奇偶規則的元胞自動機模型和分析[J].武漢理工大學學報：交通科學與工程版，2004，28（6）：936－938.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”