孫德山

?

元胞自動機(jī)研究進(jìn)展

孫德山

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

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

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

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

1 元胞自動機(jī)的基本組成

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

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

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

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

圖1 元胞自動機(jī)的鄰居模型

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

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

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

2.1 初等元胞自動機(jī)

1: 111 110 101 100 011 010 001 000

+1: 000 010 000 000 010 010 000 000

: 010111110101011100010

+1: 1010001010101010001

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

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

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

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

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

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

2.2 生命游戲

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

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

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

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

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

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

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

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

取一個初始狀態(tài)，如圖4所示，其中白色表示1（生），黑色表示0（死），根據(jù)演化規(guī)則，經(jīng)過若干步達(dá)到一個穩(wěn)定的狀態(tài)，結(jié)果如圖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ī)的應(yīng)用

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[27] 劉源遠(yuǎn)，董宏光，高建喜，等. 基于元胞自動機(jī)的投資者心理與股價波動分析[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)計學(xué)習(xí)理論、機(jī)器學(xué)習(xí)方法.