元胞自動機研究的相關理論方法
元胞自動機與相關理論和方法的發(fā)展有著千絲萬縷的聯系，一方面，元胞自動機的發(fā)展得益于相關理論的研究，如邏輯數學、離散數學、計算機中的自動機理論，圖靈機思想;另一方面，元胞自動機的發(fā)展也促進了一些相關學科和理論(如人工智能、非線性科學、復雜性科學)的發(fā)展，甚至還直接導致了人工生命科學的產生。另外，在表現上，元胞自動機模型還與一些理論方法存在著較大的相似性，或者相對性。下面，我們對元胞自動機的一些相關理論方法，以及它們與元胞自動機模型的關系進行簡要討論。
1.元胞自動機與人工生命研究
人工生命是90年代才剛剛誕生的新生科學，是復雜性科學研究的支柱學科之一。人工生命是研究能夠展示自然界生命系統行為特征的人工系統的一間科學，它試圖在計算機、機器人等人工媒體上仿真、合成和生物有機體相關聯的一些基本現象，如自我復制、寄生、競爭、進化、協作等，并研究和觀察"可能的生命現象"(Life-as-it-could-be)，從而使人們能夠加深理解"已知的生命現象"(Life-as-we-know-it)(Longton，C·G·，1987;吳建兵，1998)。
元胞自動機是人工生命的重要研究工具和理論方法分支，蘭頓(Christopher Langton)等人正是基于對元胞自動機的深入研究提出和發(fā)展了人工生命。同時，人工生命的發(fā)展又為元胞自動機賦予了新的涵義，元胞自動機模型得到科學家們的重新認識和認可，并在90年代又一次成為科學研究的前沿課題，其理論和方法得到進一步的提高。另外，元胞自動機與其他的人工生命研究方法有著很大的相似性。元胞自動機模型與神經網絡、遺傳算法等其他人工生命方法一樣，都是基于局部的相互作用，來研究系統的整體行為。另外，元胞自動機、神經網絡、L—系統都可以歸為非線性動力學中的網絡動力學模型，它們相互聯系，關系密切。目前，一種被稱為元胞神經網絡(Cellular Neural Network，簡稱CNN)的模型就是元胞自動機與神經網絡結合的產物。
2.元胞自動機與"混沌的邊緣"
"混沌的邊緣 (On the Edge of Chaos)(Langton C. G.，1992;M. Waldrop，1997)"是當前復雜性科學研究的一個重要成果和標志性口號，為圣塔菲(Santa Fee)學派的旗幟。所謂的"混沌"并非科學意義上的"混沌"，而是Chaos本身的原有涵義，即與有序相對的"混亂"、"無序"的概念。因此，"混沌的邊緣"應當被理解為"混亂的邊緣"。或"無序的邊緣"，而與混沌動力學的"混沌"沒有直接聯系。其實，"混沌的邊緣"完整的含義是指:生命等復雜現象和復雜系統存在和產生于"混沌的邊緣"。有序不是復雜，無序同樣也不是復雜，復雜存在于無序的邊緣。
"混沌的邊緣"這個概念是Norman Packard和Chhstopher Langton在對元胞自動機深入研究的基礎上提出的，在此我們予以簡要介紹。
Langton在對S. Wolfram動力學行為分類的分析和研究基礎上，提出"混沌的邊緣"這個響亮的名詞，認為元胞自動機，尤其是第四類元胞自動機是最具創(chuàng)造性動態(tài)系統--復雜狀態(tài)，它恰恰界于秩序和混沌之間，在大多數的非線性系統中，往往存在一個相應于從系統由秩序到混沌變化的轉換參數。例如，我們日常生活中的水龍頭的滴水現象，隨著水流速度的變化而呈現不同的穩(wěn)定的一點周期、兩點或多點周期乃至混沌、極度紊亂的復雜動態(tài)行為，顯然，這里的水流速度。或者說水壓就是這個非線性系統的狀態(tài)參數。Langton則相應地定義了一個關于轉換函數的參數，從而將元胞自動機的函數空間參數比。該參數變化時，元胞自動機可展現不同的動態(tài)行為，得到與連續(xù)動力學系統中相圖相類似的參數空間，Langton的方法加下 (譚躍進，1996):
首先定義元胞的靜態(tài)(Quiescent State)。元胞的靜態(tài)具有這樣的特征，如果元胞所有領域都處于靜態(tài)。則該元胞在下一時刻將仍處于這種靜態(tài)(類似于映射中的不動點)?，F考慮一元胞自動機，每個元胞具有k種狀態(tài)(狀態(tài)集為Σ)，每個元胞與n個相鄰元胞相連。則共存在kn種鄰域狀態(tài)。選擇k種狀態(tài)中任意一種s∈Σ并稱之為靜態(tài)sq。假設對轉換函數而言，共有nq種變換將鄰域映射為該靜態(tài)，剩下的kn-nq種狀態(tài)被隨機地、均勻地映射為Σ-{sq} 中的每一個狀態(tài)。則可定義:
3.元胞自動機與微分方程
微分方程有著三百多年的發(fā)展歷史。一批偉大的科學家，如Euler、Caus。Langrange、Laplace、Poisson都作出了卓越的貢獻。而且，后來發(fā)展的偏微分萬程對量子力學等現代物理學的產生相發(fā)展有著重要的意義，一大批的物理規(guī)律就是利用偏微分方程來惟理和表達的，如麥克斯維方程等。恩格斯還指出“自然界的統一性，顯示在關于各種現象領域的微分方程的 ‘驚人類似‘之中"?？傊?，微分方程是現代科學的語言，也是科學研究中最為重要的研究工具之一。
微分方程的主要特點是時間、空間均連續(xù)(如果方程中有空間因子的話），這是建立在時空連續(xù)的哲學認識基礎上的。而元胞自動機則是完全的空間離散、時間離散，在這個意義上，微分方程和元胞自動機一對相對的計算方法 (Toffoli.T.，1987)。
在人工計算的情況下。由符號組成的(偏)微分方程可以靈活地進行約簡等符號運算，而得到精確的定量解。這是其優(yōu)勢。但在現代計算機日益發(fā)展，已成為我們科學研究的重要工具時，微分方程卻遇到了一個尷尬的問題。即計算機是建立在離散的基礎上的，微分方程在計算時不得不對自身進行時空離散化，建立差分方程等;或者展開成冪系列方程，截取部分展開式;或者采用某種轉換用離散結構來表示連續(xù)變量。這個改造過程不僅是繁雜的，甚至是不可能解決的，但最重要的是在這個過程中，微分方程也失去了它的自身最重
要的特性----精確性、連續(xù)性。
而對于元胞自動機來講，脫離計算機環(huán)境來進行運算幾乎是不可能的，但是借助計算機進行計算，則非常自然而合理，甚至它還是下一代并行計算機的原型。因此，在現代計算機的計算環(huán)境下，以元胞自動機為代表的離散計算方式在求解方面，尤其是動態(tài)系統模擬方面有著更大的優(yōu)勢。元胞自動機雖然在理論上具備計算的完備性，但滿足特定目的構模尚無完備的理論支持，其構造往往是一個直覺過程。用元胞自動機得到一個定量的結果非常困難，即便是可能的話，元胞自動機也將陷入一個尷尬，元胞自動機的狀態(tài)、規(guī)則等
構成必然會復雜化，從而不可避免地失去其簡單、生動的特性。
然而，證如物理學家玻爾所說，"相對的并不一定是矛盾的，有可能是相互補充和相互完善的"。二者互有優(yōu)缺點，相互補充，都有其存在的理由。但在現代計算機環(huán)境下，對于元胞自動機這一類相對來講還處于幼年階段的離散計算方式，需要予以更多的關注和支持。在地理學中，Lowry、Wilson、張新生(張新生，1997)等人的空間動力學模型都是基于微分方程的模型，由于這些模型大多是復雜的非線性微分方程，無法求得其解析解，需要按Euler方法或Runge-Kutta方法對微分方程進行一步或多步差分，完成相應的計算機模型或在GIS支持下的空間分析模型。對于這些模型，我們都可以構建相應的元胞自動機模型。
4.元胞自動機與分形分維
元胞自動機與分形分維理論有著密切的聯系。元胞自動機的自復制、混沌等特征，往往導致元胞自動機模型在空間構形上表現出自相似的分形特征，即元胞自動機的模擬結果通?？梢杂梅中卫碚搧磉M行定量的描述。同時，在分形分維的經典范例中，有些模型本身就是，或者很接近元胞自動機模型，例如下面我們提到的凝聚擴散模型，因此，某些元胞自動機模型本身就是分形動力學模型。但是，究其本質，元胞自動機與分形理論有著巨大的差別。
元胞自動機重在對想象機理的模擬與分析;分形分維重在對現象的表現形式的表達研究。元胞自動機建模時，從現象的規(guī)律入手，構建具有特定涵義的元胞自動機模型;而分形分維多是從物理或數學規(guī)律、規(guī)則構建模型，而后應用于某種特定復雜現象，其應用方式多為描述現象的自相似性和分形分維特征。然而，這些分數維究竟能夠給我們提供多少更有價值的信息?分形理論的進一步應用問題尚末得到解決 (儀垂祥，1995)。
此外，兩者都強調一個從局部到整體的過程，但在這個過程的實質上，二者卻存在巨大的差異。分形論的精髓是自相似性。這種自相似性不局限于幾何形態(tài)而具有更廣泛更深刻的含義;它是局部 (部分)與整體在形態(tài)、功能、信息和結構特性等方面而具有統計意義上的相似性。因此，分形理論提供給我們分析問題的方法論就是從局部結構推斷整體特征(陳述彭，1998)。相反，元胞自動機的精華在于局部的簡單結構在一定的局部規(guī)則作用下，所產生的整體上的"突現"性復雜行為;即系統 (整體)在宏觀層次上，其部分或部分的加和所不具有的性質(譚躍進等，1996)。因此，分形理論強調局部與整體的相似性和相關性，但元胞自動機重在表現"突現"特征，即局部行為結構與整體行為的不確定性、非線性關系。
5.元胞自動機與馬爾科夫(鏈)過程
馬爾科夫過程(MarKov Process)是一個典型的隨機過程。設X(t)是一隨機過程，當過程在時刻t0所處的狀態(tài)為已知時，時刻t(t>t0)所處的狀態(tài)與過程在t0時刻之前的狀態(tài)無關，這個特性成為無后效性。無后效的隨機過程稱為馬爾科夫過程。馬爾科夫過程中的時同和狀態(tài)既可以是連續(xù)的，又可以是離散的。我們稱時間離散、狀態(tài)離散的馬爾科夫過程為馬爾科夫鏈。馬爾科夫鏈中，各個時刻的狀態(tài)的轉變由一個狀態(tài)轉移的概率矩陣控制。
馬爾科夫鏈與元胞自動機都是時間離散、狀態(tài)離散的動力學模型，二者在概念上有一定的相通性。尤其是對于隨機型的元胞自動機來講，每個元胞的行為可以視為一個不僅時間上無后效，而且在空間上無外效的馬爾科夫鏈。
但是，即使是隨機型的元胞自動機也與馬爾科夫鏈存在相當大的差別。首先,馬爾科夫鏈沒有空間概念，只有一個狀態(tài)變量;而元胞自動機的狀態(tài)量則是與空間位置概念緊密相關的;其次，馬爾科夫鏈中的狀態(tài)轉移概率往往是預先設定好的，而隨機型元胞自動機中的元胞狀態(tài)轉移概率則是由當前元胞的鄰居構型所決定的。
6.元胞自動機、隨機行走模型和凝聚擴散模型
隨機行走模型(Random Walk Model)模擬的是統計數學中提供"最可能狀態(tài)"常用的數學模型。它的基本思想為:給定空間中的一個粒子:它在空間中的移動矢量 (包括方向和距離)是由躍遷概率的隨機量所控制，由此可以模擬諸如自然界中的分子布朗運動、電子在金屬中的隨機運動等復雜過程。其理論研究主要集中在對單個粒子的運動規(guī)律的研究。但是，隨機行走模型中粒子可以是很多個，但是它們遵循的規(guī)則都是一個統一的隨機規(guī)程，而且它們之間的運動是相互獨立的，互不影響。如果考慮它們之間的相互作用，就可能構
造出其他基于隨機行走的模型，例如凝聚擴散模型。
凝聚擴散(Diffusion-Limited Aggregation)模型，簡稱DLA，可以看作是一個多粒子的隨機行走模型，而且它的計算空間也往往是一個離散的格網。它是由A·Written和Sander于1981年首先提出的。其基本思想如下:給定初始點作為凝聚點，以它作為圓心做一個大圓，在圓周上的一個隨機點釋放一個粒子，為簡單起見，它的運動通常規(guī)定為一個隨機行走過程，直到它運動至與已有的凝聚點相鄰，改變它的狀態(tài)為凝聚點，不再運動;再隨機釋放一個粒子;直至凝聚。重復上述過程，就可以得到一個凝聚點的連通集，形似冬日里玻璃上的冰花。凝聚擴散模型還可以有不同的形式，如釋放點可以在一個四邊形中的頂部，從而在下面省長出形似荊棘的灌叢。而1984年，R·F·Voss提出的多粒子凝聚擴散(Multi-Particle Diffusion Aggregation)模型是對凝聚擴散模型的改進和發(fā)展。其基本思想是:在給定的離散空間中，依照一定的密度隨機散布自由粒子，在中心設置一個凝聚點作為種子點，也可以隨機布設若干個凝聚點作為種子，然后各自由粒子隨機行走，一旦與凝聚點相鄰，則變?yōu)樾碌哪埸c，直至所有的自由粒子"凝聚"。
7.元胞自動機與多主體系統
多主體系統(Multi-Agent System，簡稱MAS)是分布式人工智能的熱點課題 (史忠植.1998)，主要研究為了共同的、或各自的不同目標，自主的智能主體之間智能行為的協作、競爭等相互作用?；谥黧w的模型(Agent Based Model，簡記為ABM)，簡稱主體模型，又稱基于實體的模型(Entity Based Model，簡記為EBM)，或基于個體的模型(lndividual Based Model，簡記為IBM)，是多主體系統的一個子集，其主要特征是每個主體代表了現實世界中一個智能性、自治的實體或個體，如人群中的個人，生態(tài)系統中的植物個體、動物個體，交通流中的汽車，計算網絡中的計算機，經濟系統中的經營者等。而在多主體系
統中，組成系統的個體可以是任何系統部件，如組成專家系統的是一條條意見。
8.元胞自動機與系統動態(tài)學模型
系統動力學 (SystemDynamics，簡稱SD)是一間分析研究反饋系統的學科，也是一門認識系統問題和解決系統問題交叉的綜合性學科。它最初由美國麻省理工學院的Jay W·Forrestr教授于1956年開發(fā)提出，其特點是引入了系統分析的概念，強調信息反饋控制，是系統論、信息論、控制論和決策論的綜合產物，非常適于研究復雜系統的結構、功能與動態(tài)行為之間的關系。通過分析系統結構，選取適當因素，建立它們之間的反饋關系，并在此基礎上建立一系列微分方程，構建系統動態(tài)學方程，進一步考察系統在不同參數和不同
策略因素輸入時的系統動態(tài)變化行為和趨勢，為決策者提供決策支持。由于它能夠對實際系統進行動態(tài)仿真，因而系統動力學模型可作為實際系統，特別是社會、經濟、生態(tài)復雜大系統的"實驗室"(Forrester。J·W·，1969;裴相斌，1999;李一智等，1987)。
系統動態(tài)學模型在地球科學研究中具有比較廣泛的實用性。因為它著眼于系統的整體最佳目標，不是單純追求個別子系統的最佳目標，有助于實現人口、資源、環(huán)境與社會、經濟各子系統之間的協調，采用無量綱的綜合研究。同時，該模型仍采用的一階微分方程組，帶有延遲函數和表函數，又能引入投入一產出反饋回路的概念，能比較直觀、形象地處理某些比較復雜的非線性問題 (陳述彭，1991)。但是，系統動態(tài)學也有"先天不足"，而限制了它在地球科學中的應用。
(1)首先，SD對系統的描述帶有主觀性。建模者對系統結構的認識，主要包括因素的選取及其相關關系的描述，就直接反映在模型中。而復雜系統的不確定性、非線性等復雜性特征決定了它的系統結構具有混沌性，不同人對它的描述可能有很大的差別，因而，系統動態(tài)學在地學建模中，難免會受到個人主觀性的干擾，而影響模型的模擬結果。
(2)其次，SD缺乏全面的協調指標體系。復雜系統中有許多因素是定性的，需要一個量化的過程。那么，多個相關因子的分類、分級定量標準就需要從系統的高度進行協調，這往往是系統動態(tài)學模型的一個難題。
(3)最后，缺乏空間因素的處理功能，難以刻畫空間系統中各要素在空間上的相互作用和相互反饋關系(張新生，1997;裴相斌，1999)。這對其應用于空間復雜系統研究是個致命的限制。
系統動態(tài)學模型與元胞自動機都是采用 "自下而上"的研究思路，利用系統要素間的反饋等相互作用，來模擬和預測系統的整體的動態(tài)行為，它們都是研究復雜系統動態(tài)變化約有力工具。但是，二者又有所不同:首先，在模型機制上，CA模型基于系統要素間的空間相互作用，而SD則更多的考慮要素間指標屬性的關聯關系;其次，在模型表現形式上，CA是時間、空間、狀態(tài)全離散的，轉換規(guī)則也往往表現為參照表形式，而SD則表現為系列的微分方程組，時間、屬性及要素間反饋關系的表達都是連續(xù)性質的i第三，在結果表
現上，CA模型表現為系統空間結構的時空動態(tài)演化，而SD模型的結果是系統某個社會經濟指標的動態(tài)變化;最后，在應用上，CA模型多用于復雜系統的時空演化模擬，而SD模型缺乏空間概念，更適于社會經濟系統的模擬預測。
