摘要：

元胞自動機能利用簡單的局部規則和離散方法描述復雜的全局的連續系統，已成為探索復雜系統的一種有效工具。

文章

闡述了元胞自動機的發展歷程、結構、特征及基本理論與方琺；

介紹了元胞自動機在寡頭壟斷行為、交通管理及工程運輸、城市發展、市場營銷、股票投資、企業戰略等管理領域中的應用；

指出元胞自動機理論的優勢與不足，

并提出進一步的研究展望。

1引言

復雜科學

20世紀80年代，以美國圣塔菲(SantaFe)學派為首提出了復雜科學，一經提出，在世界范圍內引起了廣泛的關注。目前，關于復雜性和復雜系統的科學研究占據著越來越重要的位置，以至于被有些科學家譽為“21世紀的科學”。

1985年，耗散結構理論的創始人，諾貝爾化學獎獲得者I.Prigogine提出了社會經濟復雜系統中的自組織問題。1988年，諾貝爾物理學獎獲得者P.Anderson和諾貝爾經濟學獎獲得者K.J.Arow通過組織專題討論會，提出了經濟管理可以看作是一個演化著的復雜系統。此后，隨著研究的不斷深入，復雜系統中所涉及的非線性、非平衡、突變、混沌、分形、自組織等理論在經濟管理領域有了越來越廣泛的應用。

元胞自動機

在復雜性和復雜系統的研究過程中，國內外學者提出了許多探索復雜性的方法及工具，其中，元胞自動機(cellularautomaton，CA)以其組成單元的簡單規則性，單元之間作用的局部性和信息處理的高度并行性，并表現出復雜的全局性等特點而備受關注，成為探索復雜系統的一種有效工具。

2元胞自動機的基本理論及方法

2.1元胞自動機的發展

20世紀50年代初，現代計算機的創始人馮·諾依曼(vonNeuman)為模擬生物發育中細胞的自我復制而提出了元胞自動機的雛形。但在當時這項工作并未引起廣泛的關注與重視。

1970年，劍橋大學的J.H.Conway設計了一種計算機游戲———“生命的游戲”。它是具有產生動態圖案和動態結構能力的元胞自動機模型，吸引了眾多科學家的興趣，推動了元胞自動機研究的迅速發展。

之后，S.Wolfram對初等元胞自動機的256種規則產生的所有模型進行了詳細而深入的研究。他還用熵來描述其演化行為，把元胞自動機分為：平穩型、周期型、混沌型、復雜型四類。

近年來隨著復雜性研究的進展，作為探索復雜系統的一種有效工具，元胞自動機獲得了深入的研究和廣泛的應用。

2.2元胞自動機的構成特征

2.2.1元胞自動機的構成

標準元胞自動機是一個由「元胞、元胞狀態、鄰域和狀態更新規則」構成的四元組，用數學符號可以表示為A=(L,d,S,N,f)

A代表一個元胞自動機系統

L表示元胞空間

d表示元胞自動機內元胞空間的維數，是一正整數

S是元胞有限的、離散的狀態集合

N表示某個鄰域內所有元胞的集合

f表示局部映射或局部規則。

具體描述：

元胞空間

元胞是構成元胞自動機的最基本單元，而元胞空間是元胞所分布的空間網點集合。

理論上，元胞空間是在各維向上無限延展的，但實際中無法在計算機上實現。因此，需要定義不同的邊界條件。

元胞空間的邊界條件主要有三種類型：周期型、反射型和定值型。

元胞狀態

通常在某一個時刻一個元胞只能有一種元胞狀態，而且該狀態取自一個有限集合，如{0,1}，{生,死}或{0,a1,a2,an}。

在社會科學領域中，元胞狀態可以用來代表個體所持的態度、個體特征或行為等。

鄰域

在空間位置上與元胞相鄰的細胞稱為它的鄰元，由所有鄰元組成的區域稱為它的鄰域。

在一維元胞自動機中，通常以半徑r來確定鄰域，距離某個元胞r內的所有元胞均被認為是該元胞的鄰域。

一維元胞自動機的鄰域：

在二維元胞自動機中，通常有以下幾種類型的鄰域：

馮·諾依曼型(vonNeumanNeighborhoods)

摩爾型(MooreNeighborhoods)

馬哥勒斯型(MargolusNeighborhoods)

它是每次將一個2×2的元胞塊做統一處理，而上述前兩類鄰域中，每個元胞是分別處理的

同樣，也可以定義二維以上的高維元胞自動機的鄰域

狀態更新規則

是指根據元胞當前狀態及其鄰域中元胞的狀態決定下一時刻該元胞狀態的狀態轉移函數。

狀態更新規則可以寫為，為t時刻的鄰域狀態組合，稱為元胞自動機的局部映射或局部規則。

2.2.2標準元胞自動機的特征

離散性：元胞自動機的空間、時間及狀態都是離散的。

同質性：元胞空間中每個單元格可能具有的狀態集合相同，并且決定各個元胞狀態變化的規則也是相同的。

并行性：元胞空間中各個元胞按狀態更新規則變化是同步進行的，特別適合于并行計算，且各個元胞的狀態變化是獨立行為，互相沒有任何影響。

局部性：一個元胞在t+1時刻的狀態由其周圍半徑為r的鄰域中的元胞的當前時刻t的狀態決定，因此，在時間、空間上都存在著局部性。

維數高：元胞自動機是一類無窮維動力系統。

3元胞自動機在管理系統中的應用

元胞自動機已被廣泛地應用于社會、經濟、軍事以及自然科學的各個領域

在社會學中，元胞自動機用于研究政治組織的突現、個人行為的社會性、流言的傳播等。

在生物學中，用于腫瘤細胞的增長機理和過程模擬、人類大腦的機理探索、艾滋病病毒HIV的感染過程、自組織、自繁殖等生命現象的研究以及克隆技術的研究。

在計算機科學中，元胞自動機被視為并行計算機而用于并行計算的研究。

在物理學中，除了格子氣元胞自動機在流體力學上的成功應用，元胞自動機還應用于磁場、電場等場的模擬，以及熱擴散、熱傳導和機械波的模擬。

在軍事科學中，元胞自動機用于模擬軍事作戰，理解戰爭過程。

在管理領域，國內外學者開始應用元胞自動機來解釋分析各種管理現象，對各種管理現象進行演化模擬。

元胞自動機在管理系統中的應用：

4標準元胞自動機的優勢與不足

從復雜系統的研究不難看出，應用元胞自動機方法對復雜系統進行描述具有很多優勢：

元胞自動機方法是立足于復雜系統的特征去模擬和描述復雜性的，因而更具有針對性、典型性和準確性。元胞自動機方法的基本出發點有三個方面：

復雜系統是由許多基本單元組成的

每個基本單元的狀態為有限的幾種

每一基本單元的狀態隨時間的演化只取決于相鄰單元的狀態

元胞自動機采用典型的“自下而上”的建模方法，符合復雜系統的形成規律，也是大多數復雜系統研究采用的思維方式，是復雜科學所倡導的復雜性研究方法。

元胞自動機的離散性使許多復雜問題得以簡化，其統計測度也很容易計算，易于完成從概念模型到計算機物理模型的轉變。

元胞自動機方法是用元胞作為基本單元描述復雜系統的整體行為，演化的規則可以預設，許多過程可以通過計算機來完成，所以具有直觀性及可控性。

元胞自動機方法可以使微觀層面上決策和機制如何產生一定的動態宏觀效果的過程更加明晰和易于掌握。

元胞自動機方法以新的設定表征了復雜系統“確定性中的內在隨機性”，即應用元胞的設定和確定的規則最終使系統產生隨機結果。在加一定的隨機項之后又使系統產生確定性結果，體現了隨機性與確定性兩者結合的非線性系統的基本特征。

元胞自動機中的狀態更新規則不依賴于數學函數，甚至可用語言簡單描述亦可達到相同目的，因此元胞自動機模型的表達更為直觀、簡單。

元胞自動機具有應用的廣泛性、靈活性和開放性。元胞自動機不是一種數理方程，而是一種方法框架。

一方面，各領域的學者通過擴展元胞自動機的組成構件，提出和建立適合專題現象的擴展模式；

另一方面，元胞自動機允許建模者在模型框架下，用各領域的專業規律構建狀態更新規則，靈活地結合已有的相關專業模型，使得元胞自動機具有應用的廣泛性、靈活性和開放性。

標準元胞自動機模型也存在一些缺陷和不足：

元胞形態

在標準元胞自動機中，元胞具備規則一致的形狀，有規律地在元胞空間中排列。但是在現實世界中很少有如此規則的狀態。

元胞空間的幾何形狀

在標準元胞自動機中，二維元胞空間可按照三角形、四邊形、六邊形等幾種網格排列。

三角形網格的缺點是在計算機顯示與表達時困難，須轉變成四方網格。

但四方網格缺點是不能較好地模擬各向同性現象。

六邊形網格的能較好地模擬各向同性現象，模型更加自然而真實，但是表達和顯示上較困難、復雜。

元胞鄰域的定義

在標準元胞自動機中，鄰域的定義也較嚴格：

在一維元胞自動機中通常以半徑r來確定鄰域，在距離某個元胞r內的所有元胞被認為是該元胞的鄰域。

二維元胞自動機通常以規則的空間單元劃分，按照vonNeuman型、Moore型和Margolus型等方法進行處理。

這直接導致元胞狀態更新規則不能應用于更遠的單元。

元胞狀態更新規則的確定，在標準元胞自動機的狀態更新規則中：

規則中的因素過于單一

元胞狀態變化僅取決于鄰域的狀態組合，因此狀態變量既是自變量又是因變量。

而實際上，一個系統元素的行為不僅取決于一個層面的變量，其受制因素是大量的。

沒有考慮宏觀作用因素

但系統要素的行為不僅僅取決于自身及鄰域的局部小環境，而且還受到系統大環境的影響

狀態更新規則往往是確定的，但在實際復雜系統中，系統元素的行為往往是隨機的，表現出某種傾向性和可能性

狀態更新規則的定義較難，合理的更新規則是自動機模型效果的關鍵。

規則是針對抽象空間劃分的單元，發生在單元間的局部相互作用。

這個局部規則與宏觀規律既有聯系又有差別，其定義又是靠直覺和經驗，因而找到與實際規律相符的映射函數難度相當大

設計不當的狀態更新規則會產生一些人為制造的錯誤后果。

值得注意的是，以上標準元胞自動機的不足目前已經逐步得到改進，因此元胞自動機應用模型大多數已不再是標準元胞自動機模型。但對于標準元胞自動機的改進還有待于進一步提高，以提高元胞自動機對現實世界的模擬和應用能力。

5研究展望

元胞自動機具有利用簡單的局部的規則和離散的方法描述復雜的全局的連續系統的能力，因此，元胞自動機不僅在自己的領域而且在科學研究的方法學上對許多相關領域產生巨大影響。
元胞自動機研究與應用的主要發展趨勢將有如下幾個方面：

應用范圍將進一步擴大。

從元胞自動機在自然科學領域及社會科學領域的應用，尤其是在管理系統中的應用，可以預見元胞自動機具有廣闊的應用前景。如在交通運輸工程、環境工程等各管理系統中的應用將會不斷擴大。

研究深度將不斷加強。

目前，元胞自動機的理論與方法研究在我國還處于介紹國外研究成果、進行初步研究的時期，國內許多學者正在各自的領域推進元胞自動機及其應用的研究。在管理系統的元胞自動機的研究中，一方面需要對已有的模型進行更深入的探討；另一方面，需要以元胞自動機理論為基礎建立新的模型，同時也要注意吸收國外的最新研究成果，借鑒其他學科元胞自動機研究的主要成果。總之，元胞自動機的研究深度有待不斷加強。

標準模型將不斷擴展。

由于標準元胞自動機的缺陷及局限性，國內外學者從不同方面對標準元胞自動機進行了擴展，如連續型的元胞自動機，多維狀態空間元胞自動機，多層級元胞自動機，多元隨機的元胞自動機以在本文所提到的管理系統應用中對標準元胞自動機各構成要素的擴展等等。隨著元胞自動機研究的不斷深入和應用范圍的不斷擴大，標準元胞自動機必將被不斷擴展，使得元胞自動機對真實世界的模擬和應用能力不斷加強。

其他方法將不斷被引入元胞自動機模型中。

隨著研究的深入，其他領域的一些方法將不斷地被引入元胞自動機模型。如將遺傳算法和元胞自動機集成，使狀態更新規則具有遺傳性，形成遺傳自動機；將狀態更新規則模糊化，則可以有模糊規則，形成模糊元胞自動機；元胞的狀態可以根據神經網絡的閾值函數來更新，形成神經元胞自動機等。因此，元胞自動機與其他方法的不斷結合將使元胞自動機的功能越來越強大，成為一種研究復雜系統的越來越有效的方法與工具。

---

參考文獻

本文修改自：《中國工程科學》第9卷第一期《元胞自動機：一種探索管理系統復雜性的有效工具》，福州大學管理學院陳國宏

本文地址：http://www.cnblogs.com/bellkosmos/p/introduction_of_cellular_automata.html

總結

以上是生活随笔為你收集整理的元胞自动机简介的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。