孫德山

?

元胞自動機研究進展

孫德山

（遼寧師范大學 數(shù)學學院，遼寧 大連 116029）

元胞自動機是一個具有簡單運算規(guī)則的動態(tài)模型，但卻能展現(xiàn)出復雜的行為. 元胞自動機引起了許多研究者的關注，相關研究工作已經(jīng)廣泛展開. 論文綜述了元胞自動機的研究進展及在不同領域的一些應用.

元胞自動機；元胞空間；復雜系統(tǒng)

1951年，Von Neumann給出了元胞自動機（Cellular Automata，CA）模型，又稱為細胞自動機. 元胞自動機在時間和空間上是一個離散的動力系統(tǒng)，目前已經(jīng)成為復雜系統(tǒng)建模的主要工具[1]. 元胞自動機可以看成是由許多網(wǎng)格組成的，網(wǎng)格中的每個單元為一個元胞，只取有限的離散狀態(tài)，它們都遵循同樣的局部變換規(guī)則，并進行同步更新；大量元胞通過簡單的相互作用形成系統(tǒng)的動態(tài)演化，并能形成復雜的演化狀態(tài)；元胞自動機不是由確定的函數(shù)定義，而是由簡單的規(guī)則決定. 即，元胞自動機模型是滿足一定規(guī)則的動力系統(tǒng)的總稱，每個變量的狀態(tài)只取有限多個，并且狀態(tài)改變的規(guī)則都是局部的. 本文介紹元胞自動機的構成原理、研究進展以及在不同領域中的應用.

1 元胞自動機的基本組成

元胞、元胞空間、鄰居及規(guī)則就構成一個元胞自動機. 元胞自動機最基本的組成單位是元胞，元胞位于離散的一維、二維或多維空間的網(wǎng)格點上. 元胞的狀態(tài)可以由{0,1}組成，也可以是整數(shù)形式的離散集. 元胞所分布的空間網(wǎng)點集合稱為元胞空間，其幾何劃分可以是任意維數(shù)的歐幾里得空間劃分. 一維和二維元胞自動機是目前研究的重點. 一維元胞自動機的元胞空間劃分只有一種形式，二維元胞空間的劃分很靈活，可按三角形、四方形或六邊形3種網(wǎng)格排列.

元胞空間可以在各維上無限延展，這有助于在理論上進行研究，但是這一理想條件無法在實際應用中實現(xiàn)，因此，定義不同的邊界條件顯得非常重要. 邊界條件一般有3種類型：反射型、定值型和周期型. 有時，可以采用隨機型來模擬實際的自然現(xiàn)象，即實時在邊界生成隨機數(shù).

以上的元胞及元胞空間只表示了系統(tǒng)的靜態(tài)成分，將演化規(guī)則加入后就形成了動態(tài)系統(tǒng). 元胞自動機中的這些規(guī)則是在局部空間范圍內(nèi)定義的，一個元胞將根據(jù)自身的狀態(tài)和它的鄰居元胞的狀態(tài)決定其下一時刻的狀態(tài)；因此，定義鄰居規(guī)則是元胞自動機運行的前提，必須明確一個元胞的鄰居有哪些. 一維元胞自動機根據(jù)半徑來確定鄰居. 二維元胞自動機定義鄰居比較復雜，一般采用如圖1所示的2種形式. 圖1中，中心元胞用黑色表示，其鄰居元胞用灰色表示，中心元胞在下一時刻的狀態(tài)是根據(jù)自身狀態(tài)和鄰居的狀態(tài)來計算.

圖1a）是馮·諾依曼型鄰居，此時元胞的鄰居由上、下、左、右相鄰的4個元胞組成，鄰居半徑為1. 圖1b）是摩爾型鄰居，此時元胞的鄰居由上、下、左、右、左上、右上、右下、左下8個元胞組成.

圖1 元胞自動機的鄰居模型

規(guī)則是元胞自動機演化的動力依據(jù)，是確定元胞下一時刻狀態(tài)的動力學函數(shù)，即

2 幾種典型元胞自動機及其Matlab實現(xiàn)

在元胞自動機的發(fā)展過程中，科學家們構造了各種各樣的元胞自動機模型. 以下幾個典型模型對元胞自動機的理論方法的研究起到了極大的推動作用，因此，它們又被認為是元胞自動機發(fā)展歷程中的幾個里程碑.

2.1 初等元胞自動機

1: 111 110 101 100 011 010 001 000

+1: 000 010 000 000 010 010 000 000

: 010111110101011100010

+1: 1010001010101010001

每種組合分別對應0或1，共有組合28=256種，即初等元胞自動機只有256種不同規(guī)則. 根據(jù)上述8種組合產(chǎn)生的8個結果形成一個二進制（按照高低位順序），如上述規(guī)則01001100，將其轉化為十進制值：

的取值范圍為[0,255]，S.Wolfram定義該數(shù)值為初等元胞自動機的編號，于是前面的模型就是76號初等元胞自動機.

取長度為100的格子，每個格子代表一個元胞，初值取第50個格子為1，其余為0，用黑色表示0，白色表示1. 按照規(guī)則18和規(guī)則30演化100步，結果如圖2和圖3所示，Matlab實現(xiàn)見程序1和2.

圖2 規(guī)則18的演化結果

圖3 規(guī)則30 的演化結果

程序1

m=100;n=100;

s=zeros（m，n）;

s（1，n/2）=1;

for i=1：m-1

for j=2：n-1

if （s（i，j-1）==1&s（i，j）==0&s（i，j+1）==0）|（s（i，j-1）==0&s（i，j）==0&s（i，j+1）==1）

s（i+1，j）=1;

end

end

end

imagesc（s）;

colormap（gray）;

程序2

m=100;n=100;

s=zeros（m，n）;

s（1，n/2）=1;

for i=1：m-1

for j=2：n-1

if （s（i，j-1）==1&s（i，j）==0&s（i，j+1）==0）|（s（i，j-1）==0&s（i，j）==1&s（i，j+1）==1）|（s（i，j-1）==0&s（i，j）==1&s（i，j+1）==0）|（s（i，j-1）==0&s（i，j）==0&s（i，j+1）==1）

s（i+1，j）=1;

end

end

end

imagesc（s）

colormap（gray）

S.Wolfram對這256種不同規(guī)則的元胞自動機模型進行了深入而細致的研究[2]. 研究中發(fā)現(xiàn)，雖然初等元胞自動機的演化規(guī)則簡單，但有些元胞自動機卻能表現(xiàn)出非常復雜的空間形態(tài). 有些元胞自動機經(jīng)過一段時間的演化后，能形成一種穩(wěn)定的狀態(tài)，比如靜止狀態(tài)或周期性結構狀態(tài). S.Wolfram對初等元胞自動機的深入研究奠定了元胞自動機理論的基石，對后來興起的人工生命研究和復雜性科學研究作出了巨大的貢獻.

2.2 生命游戲

生命游戲是一種單人玩的計算機游戲，是J. H. Conway在20世紀60年代末設計的，它也是一種元胞自動機模型. 生命游戲中的元胞有{ “生”,“死” }兩個狀態(tài)，元胞類似國際象棋分布在網(wǎng)格內(nèi)，根據(jù)元胞的局部空間形態(tài)來決定元胞下一時刻的生死. 生命游戲的構成及運算規(guī)則如下：

1）元胞位于規(guī)則劃分的網(wǎng)格上；

2）元胞具有“生”和“死”兩種狀態(tài)，“死”用0代表，“生”用1代表；

3）元胞的鄰居采用Moore型，即以相鄰的8個元胞為鄰居.

4）一個元胞下一時刻的狀態(tài)由其在該時刻自身的生死狀態(tài)和8個鄰居的狀態(tài)決定. 當前時刻，如果一個元胞狀態(tài)為“生”，并且其8個鄰居元胞中有2個或3個的狀態(tài)為“生”，則在下一時刻該元胞為“生”，否則狀態(tài)為“死”；當前時刻，如果一個元胞狀態(tài)為“死”，并且其8個鄰居元胞中恰好有3個元胞為“生”，則該元胞在下一時刻的狀態(tài)為“生”，否則狀態(tài)為“死”.

盡管這些規(guī)則看上去簡單，但生命游戲經(jīng)過一定時間的演化卻能產(chǎn)生豐富有趣的圖案. 生命游戲的演化與元胞的初始狀態(tài)值有關. 任意給定初始狀態(tài)，經(jīng)過一定時間的演化，有的圖案會消失，有的圖案會穩(wěn)定不變，也有的圖案會重復多次出現(xiàn).

生命游戲模型雖然簡單，但卻在許多方面得到應用，其演化規(guī)則接近生物群體的生存繁殖規(guī)律：在生命密度很小，即為“生”的鄰居元胞數(shù)小于2時，因為孤獨并缺乏互助、缺乏配種繁殖機會等，往往會出現(xiàn)生命危機，元胞的狀態(tài)由生變?yōu)樗?；在生命密度很大，即為“生”的鄰居元胞?shù)大于3時，因為資源短缺、環(huán)境惡劣以及互相競爭而導致出現(xiàn)生存危機，元胞狀態(tài)值由生變?yōu)樗?；只有處于個體數(shù)量適中，即為“生”的鄰居元胞數(shù)為2或3時，生物才能保持良好的生存環(huán)境，才能保持元胞的狀態(tài)值繼續(xù)為生，并且繁衍后代，即元胞的狀態(tài)值由死變?yōu)樯? 因為該模型能夠模擬生命活動中的生存、競爭、滅絕等復雜生物現(xiàn)象，因而得名為“生命游戲”.

生命游戲模型將平面劃分成類似圍棋的方格棋盤，每個方格稱為一個元胞. 元胞的狀態(tài)有2種：0代表死亡，1代表生存. 領域半徑為1，鄰居類型為Moore型，演化規(guī)則：

取一個初始狀態(tài)，如圖4所示，其中白色表示1（生），黑色表示0（死），根據(jù)演化規(guī)則，經(jīng)過若干步達到一個穩(wěn)定的狀態(tài)，結果如圖5所示，Matlab實現(xiàn)見程序3.

圖4 初始狀態(tài)

圖5 演化后的穩(wěn)定狀態(tài)

程序3

n=50;

z = zeros（n，n）;

sum=z;

cells = z;

cells（n/2，.25*n：.75*n） = 1;

cells（.25*n：.75*n，n/2） = 1;

cells = （rand（n，n））<.5 ;

x = 2：n-1;

y = 2：n-1;

imagesc（cells）;

colormap（gray）

figure;

for i=1：500

sum（x，y） = cells（x，y-1） + cells（x，y+1） + ...

cells（x-1，y） + cells（x+1，y） + ...

cells（x-1，y-1） + cells（x-1，y+1） + ...

cells（x+1，y-1） + cells（x+1，y+1）;

cells = （sum==3） | （sum==2 & cells）;

imagesc（cells）

colormap（gray）

drawnow

end

3 元胞自動機的應用

元胞自動機已廣泛應用于社會、經(jīng)濟、金融研究等各個領域. 元胞自動機在流體力學與統(tǒng)計物理中的應用代表是格子氣自動機[3]，也稱為格氣機，它利用元胞自動機的動態(tài)特征來模擬流體粒子的運動. 在物理學中，除了格氣機在流體力學上的成功應用，元胞自動機還應用于熱擴散、熱傳導和機械波的模擬等. 另外，元胞自動機可以用來模擬二元規(guī)則共晶生長[4-5]，共晶生長是凝聚態(tài)物理和材料科學領域的重要研究課題.

元胞自動機在交通系統(tǒng)建模[6-8]中，主要研究類型和駕駛行為相同的車輛所構成的交通流問題，為解決城市交通問題提供一定的理論支持. 元胞自動機也是模擬復雜地理系統(tǒng)的有效工具[9-16]，廣泛用于城市擴展和土地、森林資源利用變化的模擬.

在醫(yī)學中，元胞自動機可以模擬病毒的傳播和感染過程[17-18]，為疾病的控制和預防提供一定的幫助. 在化學中，元胞自動機可用來模擬原子、分子等各種微觀粒子在化學反應中的相互作用，從而研究化學反應的過程[19]. 元胞自動機也可用于模擬人員疏散過程[20-23].

在金融投資分析中，元胞自動機可以模擬股票市場的行為. 文獻[24-27]將元胞自動機的思想應用于金融市場的波動分析，元胞代表股票投資者，元胞的狀態(tài)空間有3種：股票買入（-1）、股票持有（0）、股票買出（1），元胞下一時刻的狀態(tài)受到鄰居元胞的投資行為影響，這樣可以根據(jù)自身元胞的從眾心理定義元胞狀態(tài)的形成規(guī)則，從而揭示金融市場中的從眾效應和信息傳遞的動力學特征.

元胞自動機作為一種動態(tài)模型，其應用幾乎涉及社會科學和自然科學的各個領域. 但目前大多數(shù)應用還僅局限在模擬仿真上，要達到真正的實用階段還需深入研究.

[1] 吳今培，李學偉. 系統(tǒng)科學發(fā)展概論[M]. 北京：清華大學出版社，2010.

[2] WOLFRAM S. A new kind of science[M]. Champaign Illinois: Wolfram Media, 2002.

[3] 李元香，康立山，陳硫屏. 格子氣自動機[M]. 北京：清華大學出版社，1994.

[4] 吳孟武，熊守美. 采用元胞自動機法模擬二元規(guī)則共晶生長[J]. 物理學報，2011, 60(5): 1-9.

[5] 武磊，劉雅政，程曉杰，等. 元胞自動機模擬晶粒長大的步長設定對模擬結果的影響[J]. 北京科技大學學報，2010, 32(6): 739-743.

[6] 賈斌. 基于元胞自動機的交通系統(tǒng)建模與模擬[M]. 北京：科學出版社，2007.

[7] 杜小丹，趙仕波，鄢濤，等. 基于自主代理和元胞自動機的交通流模型[J]. 計算機科學，2010, 37(5): 231-239.

[8] 雷麗，薛郁，戴世強. 交通流的一維元胞自動機敏感駕駛模型[J]. 物理學報，2003, 52(9): 2121-2126.

[9] 馮永玖，童小華，劉妙龍，等. 基于GIS的地理元胞自動機模擬框架及其應用[J]. 地理與地理信息科學，2010, 26(1): 41-43.

[10] 喬紀綱，何晉強. 基于分區(qū)域的元胞自動機及城市擴張模擬[J]. 地理與地理信息科學，2009, 25(3): 67-70.

[11] 王璐，岑豫皖，李銳，等. 基于區(qū)塊特征的元胞自動機土地利用演化模型研究[J]. 地理與地理信息科學，2009, 25(3): 74-76.

[12] 尹長林，張鴻輝，劉勤志. 城市規(guī)劃CA模型及其應用[J]. 地理與地理信息科學，2008, 24(3): 71-74.

[13] 全泉，田光進，沙默泉. 基于多智能體與元胞自動機的上海城市擴展動態(tài)模擬[J]. 生態(tài)學報，2011, 31(10): 2875-2887.

[14] 何春陽，史培軍，陳晉，等. 基于系統(tǒng)動力學模型和元胞自動機模型的土地利用情景模型研究[J]. 中國科學：D輯，地球科學，2005, 35(5): 464-473.

[15] 王曉學，李敘勇，莫菲，等. 基于元胞自動機的森林水源涵養(yǎng)量模型新方法：概念與理論框架[J]. 生態(tài)學報，2010, 30(20): 5491-5500.

[16] 楊青生. 基于元胞自動機的土地資源節(jié)約利用模擬[J]. 自然資源學報，2009, 24(5): 753-761.

[17] 賀明峰，鄧成瑞. 基于元胞自動機的SARS傳播模型[J]. 數(shù)學的實踐與認識，2008, 38(3): 41-46.

[18] 李璐，宣慧玉，高寶俊. 基于元胞自動機的異質(zhì)個體HIV/AIDS傳播模型[J]. 系統(tǒng)管理學報，2008, 17(6)：704-710.

[19] 李才偉. 元胞自動機及復雜系統(tǒng)的時空演化模擬[D]．武漢：華中科技大學，1997.

[20] 孟俊仙，周淑秋，饒敏. 基于元胞自動機的人員疏散仿真研究[J]. 計算機工程與設計，2009, 30(1): 241-246.

[21] 宋衛(wèi)國，于彥飛，范維澄，等. 一種考慮摩擦與排斥的人員疏散元胞自動機模型[J]. 中國科學：E輯，2005, 35(7): 725-736.

[22] 翁文國，袁宏永，范維澄. 一種基于移動機器人行為的人員疏散的元胞自動機模型[J]. 科學通報，2006, 51(23): 2818-2822.

[23] 楊立中，方偉峰，黃銳，等. 基于元胞自動機的火災中人員逃生的模型[J]. 科學通報，2002, 47(12): 896-901.

[24] 高建喜，劉源遠，崔珊珊，等. 基于元胞自動機的股市模擬及分析：投資者心理和股票交易量[J]. 數(shù)學的實踐與認識，2009, 39(4): 6-12.

[25] 應尚軍，范英，魏一鳴. 單支股票市場的元胞自動機模型及其動力學研究[J]. 系統(tǒng)工程，2006, 24(7): 31-36.

[26] 應尚軍，魏一鳴，范英，等. 基于元胞自動機的股票市場投資行為模擬[J]. 系統(tǒng)工程學報，2001, 16(5): 382-388.

[27] 劉源遠，董宏光，高建喜，等. 基于元胞自動機的投資者心理與股價波動分析[J]. 科技通報，2008, 24(3): 427-432.

Developments of the Study of the Cellular Automata

SUNDe-shan

(Department of Math, Liaoning Normal University, Liaoning 116029, China)

Cellular automata are simple models of computation which exhibit complex behavior. They have captured the attention of many researchers, leading to an extensive research. The present paper deals with the advances of cellular automata and some of their applications in different fields.

cellular automata; cellular spaces; complex systems

1006-7302（2011）04-0022-07

N941.1

A

2011-07-20

孫德山（1970—），男，遼寧沈陽人，副教授，博士，研究方向為統(tǒng)計學習理論、機器學習方法.