吳今培

?

規(guī)則計(jì)算——探索復(fù)雜性的有力模式

吳今培

（五邑大學(xué) 智能技術(shù)與系統(tǒng)研究所，廣東 江門 529020）

自然界中存在著許許多多的復(fù)雜系統(tǒng)，這些系統(tǒng)的每一部分的結(jié)構(gòu)可以非常簡單，但由于各部分之間存在一定的耦合，最終表現(xiàn)出系統(tǒng)的整體性態(tài)極其復(fù)雜. 基于規(guī)則計(jì)算的元胞自動機(jī)為模擬自然現(xiàn)象和生命現(xiàn)象提供了新的思路和方法，成為探索復(fù)雜系統(tǒng)的一種有力模式. 論文介紹了規(guī)則計(jì)算的產(chǎn)生和發(fā)展，著重闡述了規(guī)則計(jì)算的本質(zhì)，并對自下而上的基于規(guī)則的建模方法中存在的一些問題進(jìn)行了總結(jié)與展望.

規(guī)則計(jì)算；復(fù)雜性；元胞自動機(jī)

進(jìn)入21世紀(jì)，人類究竟以什么樣的世界觀和方法論觀察世界、認(rèn)識世界和改造世界呢？英國著名科學(xué)家霍金（S.Hahing）認(rèn)為：21世紀(jì)是復(fù)雜性的世紀(jì). 美國著名科學(xué)家、諾爾貝獎獲得者考溫（G.Cowan）把復(fù)雜性科學(xué)譽(yù)為“21世紀(jì)的科學(xué)”. 這是因?yàn)楫?dāng)代重大的自然問題和社會問題都具有很強(qiáng)的關(guān)聯(lián)性，且日益整體化和復(fù)雜化，人們不僅要認(rèn)識單個因素或單個事物，而且還要從系統(tǒng)整體出發(fā)認(rèn)識和解決復(fù)雜系統(tǒng)的問題. 可以說，如今人們在分析社會結(jié)構(gòu)、處理大工業(yè)生產(chǎn)、規(guī)劃國民經(jīng)濟(jì)、研究生物和生態(tài)的問題時(shí)，幾乎沒有一種復(fù)雜事物的研究不在復(fù)雜性科學(xué)的對象之內(nèi). 因此，復(fù)雜性探索的興起，標(biāo)志著人與社會、人與自然之間的一場新的對話已經(jīng)開始[1].

1 復(fù)雜性探索的兩種重要模式

1.1 計(jì)算復(fù)雜性

任何人的生活、學(xué)習(xí)和工作都離不開計(jì)算，我們遇到實(shí)際問題時(shí)常常會說需要“算一算”. 數(shù)學(xué)的誕生就是從實(shí)際問題的計(jì)算開始的，數(shù)學(xué)家則更是追求解決問題的一般算法. 從簡單的三角形面積算法到描述各種自然和社會現(xiàn)象的復(fù)雜的方程求解，定量化的方法已經(jīng)滲透到各行各業(yè). 在復(fù)雜性科學(xué)中，計(jì)算和算法有著特別的意義.

計(jì)算是一個物理的操作運(yùn)行過程，完成這一過程需要起碼的計(jì)算時(shí)間和計(jì)算空間. 所謂計(jì)算復(fù)雜性是指解決一個問題所耗費(fèi)的計(jì)算機(jī)資源的多少，是衡量算法效率的一種指標(biāo). 一般地說，計(jì)算機(jī)解決一個問題的程序需要多少步驟，叫做時(shí)間復(fù)雜性；需要多少記憶容量或存儲量，叫做空間復(fù)雜性. 時(shí)間復(fù)雜性與空間復(fù)雜性的存在告訴我們，時(shí)間和空間是計(jì)算最基本的物理限制因素，計(jì)算時(shí)間與空間都是有限的，且與人類活動的合理的時(shí)間與空間尺度密切相關(guān)，如果超出這一合理時(shí)空尺度，計(jì)算就是不現(xiàn)實(shí)的，也是不可能的.

計(jì)算復(fù)雜性是由算法的復(fù)雜性決定的. 判斷一個問題是否屬于難解的復(fù)雜性問題，就是考察問題是否具有算法，其運(yùn)行時(shí)間和所占空間是否超過了合理尺度. 即，計(jì)算復(fù)雜性把系統(tǒng)的復(fù)雜轉(zhuǎn)化為解決一個問題所需耗費(fèi)的時(shí)間或空間的問題：因此，我們可以看出，計(jì)算復(fù)雜性所研究的問題都是有關(guān)算法的問題. 同一個計(jì)算問題往往可以用多種不同的算法來求解，對于大量的數(shù)據(jù)，尋找出最優(yōu)的算法就可以大量節(jié)約計(jì)算所需要的時(shí)間與空間.

算法是解一類問題的計(jì)算方法，傳統(tǒng)科學(xué)認(rèn)為計(jì)算并不能發(fā)現(xiàn)什么新東西，因而計(jì)算方法只是一種輔助性的方法. 但是復(fù)雜性科學(xué)改變了人們的陳舊觀念，復(fù)雜性的許多現(xiàn)象和規(guī)律都是通過計(jì)算發(fā)現(xiàn)的，復(fù)雜性理論的許多分支，例如，元胞自動機(jī)、生命游戲、人工生命、復(fù)雜適應(yīng)系統(tǒng)等都是建立在計(jì)算或算法的基礎(chǔ)上，都是運(yùn)用計(jì)算方法的典型案例：因此，計(jì)算方法（或計(jì)算模式）是研究復(fù)雜性的重要方法.

1.2 復(fù)雜性研究的兩種計(jì)算模式

今天，人們所認(rèn)識到的復(fù)雜性具有兩種重要范式. 一種是20世紀(jì)科學(xué)發(fā)展所揭示的用迭代過程和微分方程所描述的簡單系統(tǒng)，它因非線性關(guān)系而展現(xiàn)出復(fù)雜行為，如蝴蝶效應(yīng)、混沌現(xiàn)象、分形結(jié)構(gòu)等，這是復(fù)雜性的一種重要范式. 另一種是世紀(jì)之交人們廣泛觀察到的，由某些簡單規(guī)則自組織演化而形成的大量復(fù)雜系統(tǒng)，例如，技術(shù)系統(tǒng)中的互聯(lián)網(wǎng)、社會系統(tǒng)中的人際關(guān)系網(wǎng)、生命系統(tǒng)中的細(xì)胞網(wǎng)等，它們受簡單規(guī)則的驅(qū)動而涌現(xiàn)出整體的復(fù)雜性. 這可能是復(fù)雜性更重要的一種范式. 相應(yīng)地，描述復(fù)雜系統(tǒng)行為的方法也有2種.

1.2.1 數(shù)學(xué)方程的解析求解方法

自然界的許多復(fù)雜現(xiàn)象，它們是完全不同的，但卻具有相同的數(shù)學(xué)形式，通?？梢杂梦⒎址匠瘫硎?，求解微分方程，分析解的性質(zhì)，就能夠研究復(fù)雜系統(tǒng)的行為. 例如，連續(xù)動力系統(tǒng)可采用常微分方程解決復(fù)雜問題，并認(rèn)為復(fù)雜性存在于所研究的系統(tǒng)中；混沌動力系統(tǒng)應(yīng)用非線性常微分方程來描述和解決復(fù)雜問題，并認(rèn)為復(fù)雜性存在于所研究的系統(tǒng)中，美國氣象學(xué)家洛倫茨（E.Lorenz）在天氣預(yù)報(bào)中所發(fā)現(xiàn)的混沌就是令人矚目的一例.

在20世紀(jì)五六十年代，人們普遍認(rèn)為氣象系統(tǒng)雖然非常復(fù)雜，但仍然是遵循牛頓定律的確定性對象，只要計(jì)算機(jī)功能強(qiáng)大，天氣狀況就可以精確預(yù)報(bào). 馮·諾伊曼（Von Neumann）所設(shè)計(jì)的第一代計(jì)算機(jī)就是以天氣模擬為理想任務(wù). 他設(shè)想通過使用計(jì)算機(jī)計(jì)算流體運(yùn)動的方程，人類就可以控制天氣. 天氣變化是一種特殊的流體運(yùn)動——對流. 洛倫茨建立了下面這個極其簡單的對流模型，一個只有3個方程的一階微分方程組：

洛倫茨把這個方程組作為大氣對流模型，用計(jì)算機(jī)進(jìn)行計(jì)算，觀察這個系統(tǒng)的演化行為. 終于有一天他看到了一個奇異的現(xiàn)象.

1963年冬季的一天，在一次實(shí)驗(yàn)中為了更細(xì)微地考察結(jié)果，他把一個中間解0.506取出，提高精度到0.506 127再輸回方程式. 當(dāng)他喝了杯咖啡以后回來再看，竟大吃一驚：本來很小的差異，結(jié)果卻偏離十萬八千里！再次實(shí)驗(yàn)表明計(jì)算機(jī)并沒有毛病. 洛倫茨發(fā)現(xiàn)，由于誤差會以指數(shù)形式增長，在這種情況下，一個微小的誤差隨著不斷推移造成了巨大的后果. 于是他認(rèn)定：無論系統(tǒng)初始條件有多么微小的改變，其后運(yùn)動就會因失之毫厘而謬以千里，變得面目全非. 該現(xiàn)象被稱為混沌現(xiàn)象，又形象地稱為“蝴蝶效應(yīng)”.

洛倫茨的模型是一個理想的模型，他把一組對流方程簡化到只剩下了骨架，除了非線性之外，幾乎什么都沒有剩下. 正是由于在系統(tǒng)中包含著非線性因素才產(chǎn)生了混沌，它是非線性系統(tǒng)的固有特性，如非周期性、對初值的敏感依賴性、長期行為的不可預(yù)測性等.

在實(shí)際應(yīng)用中，面對非結(jié)構(gòu)化、非線性和復(fù)雜性等問題，現(xiàn)實(shí)世界的許多復(fù)雜結(jié)構(gòu)不可能用數(shù)學(xué)方程來完美表達(dá)：要么因復(fù)雜系統(tǒng)變數(shù)太多無法得到合適的數(shù)學(xué)方程；要么方程極其復(fù)雜而難以求解；要么方程存在無窮多的解，不符合客觀實(shí)際的要求. 為了彌補(bǔ)解析方法之不足，我們需要尋找新的計(jì)算方法. 這就是用計(jì)算機(jī)去探索和模擬如何從簡單的運(yùn)算規(guī)則涌現(xiàn)出驚人復(fù)雜行為的方法.

1.2.2 簡單規(guī)則反復(fù)迭代的計(jì)算機(jī)模擬方法[2-3]

復(fù)雜性科學(xué)研究表明，最簡單的元素、最簡單的關(guān)系和最簡單的規(guī)則，在一定條件下反復(fù)迭代就可以模擬生命甚至可能窮盡地模擬宇宙已有的一切復(fù)雜性和多樣性. 也就是說，重復(fù)使用簡單規(guī)則，可能形成極為復(fù)雜的行為. 我們可以歸結(jié)為一個公式：復(fù)雜性=簡單性+迭代. 這不禁使我們想起中國的圍棋和易經(jīng). 圍棋的規(guī)則很簡單，變化卻很復(fù)雜；易經(jīng)的道理很樸素，但其陰、陽爻的排列組合卻無窮無盡、變幻莫測；同樣，在人類社會中，個人與個人之間簡單的對策，只要重復(fù)（迭代的）博弈就會產(chǎn)生各種復(fù)雜的社會合作和社會結(jié)構(gòu).

正如美國科學(xué)家史蒂芬（K.Steven）所說，“每當(dāng)你觀察物理和生物方面非常復(fù)雜的系統(tǒng)時(shí)，你會發(fā)現(xiàn)它們的基本組成因素和基本法則非常簡單. 復(fù)雜性的出現(xiàn)是因?yàn)檫@些簡單因素自動地不斷地在相互發(fā)生作用”[3].

從系統(tǒng)科學(xué)的觀點(diǎn)看，迭代是什么意思？它說的是，對于某一個事物或一個系統(tǒng)，反復(fù)地運(yùn)用同樣的規(guī)律來支配它. 而迭代研究的結(jié)果表明：這個事物或這個系統(tǒng)即使受一些十分簡單的規(guī)則支配和決定，也會產(chǎn)生出十分復(fù)雜的甚至是混沌而不可預(yù)測的結(jié)果. 迭代在生命世界中，對應(yīng)著繁殖；在復(fù)雜系統(tǒng)中，擴(kuò)展到包含經(jīng)濟(jì)系統(tǒng)的增長、免疫系統(tǒng)抗體的增加、人腦中某些神經(jīng)突觸的加強(qiáng)以及系統(tǒng)中某種相互聯(lián)結(jié)形式的持續(xù)性等等：所以有學(xué)者將系統(tǒng)迭代看作與多樣性和適應(yīng)性并列的復(fù)雜系統(tǒng)行為相互作用的三大特征之一.

復(fù)雜適應(yīng)系統(tǒng)理論的創(chuàng)始人霍蘭德（J. Holland）正是抓住了這一點(diǎn)，他認(rèn)為：涌現(xiàn)生成過程的關(guān)鍵就是由少數(shù)幾條簡單的規(guī)則支配的個體在其大量的相互作用和反復(fù)迭代中產(chǎn)生出巨大的復(fù)雜性和涌現(xiàn)性、不可預(yù)測的新穎性和不可還原的整體性的過程. 據(jù)此，霍蘭德提出了復(fù)雜系統(tǒng)涌現(xiàn)的受約束生成過程的精確描述.

首先，將系統(tǒng)中的適應(yīng)性個體的功能表達(dá)為簡單的行為規(guī)則，即轉(zhuǎn)換函數(shù)：

其次，將個體之間的相互作用表達(dá)為界面函數(shù)：

以上分析思路是通過建立簡單規(guī)則，再借助計(jì)算機(jī)的反復(fù)迭代實(shí)現(xiàn)對系統(tǒng)演化過程的分析，而不是通過建立系統(tǒng)的精確數(shù)學(xué)方程式進(jìn)行解析分析.

2 基于規(guī)則計(jì)算的離散動態(tài)系統(tǒng)分析

2.1 規(guī)則計(jì)算的內(nèi)涵

何謂規(guī)則計(jì)算？

規(guī)則計(jì)算不是用嚴(yán)格定義的數(shù)學(xué)方程或函數(shù)建立的模型，而是用一系列規(guī)則構(gòu)成的模型. 通過計(jì)算機(jī)反復(fù)地計(jì)算極其簡單的規(guī)則，就可以使之發(fā)展成為復(fù)雜的模型，并可以解釋自然界中的絕大多數(shù)現(xiàn)象.

規(guī)則計(jì)算的基本觀點(diǎn)：自然界和人類社會許多復(fù)雜結(jié)構(gòu)、復(fù)雜現(xiàn)象和復(fù)雜過程，歸根結(jié)底只是由大量基本組成元素的簡單相互作用所引起，我們可能僅僅用一些簡單模型（或單純的程序代碼）就可以模擬.

大家都觀察過一群大雁在空中展翅飛舞，它們會時(shí)聚時(shí)散，一會兒排成個“一”字，一會兒排成個“人”字. 大雁的飛行顯然是一種有序行為，然而這種秩序是從哪里來的呢？一種解釋是，秩序來源于某只領(lǐng)頭大雁的命令和協(xié)調(diào)，領(lǐng)導(dǎo)者可以通過直接對其他大雁發(fā)號施令讓整個群體具有優(yōu)美的秩序排列；也有人認(rèn)為，自然進(jìn)化使得每只大雁的頭腦中都預(yù)存了整個大雁飛行隊(duì)列的姿態(tài). 事實(shí)上，非線性科學(xué)的研究結(jié)果告訴我們，原因在于每只飛行的大雁都遵循3條簡單的行動規(guī)則：1）分隔，盡量避免與鄰近伙伴碰撞；2）匹配，盡量與鄰近伙伴的平均方向一致；3）吸引，盡量朝鄰近伙伴的中心移動. 正是在這種簡單規(guī)則的共同制約下，大雁之間的相互作用導(dǎo)致了群體秩序和諧的自然出現(xiàn). 這一過程在復(fù)雜性科學(xué)中叫涌現(xiàn)（Emergence）.

自然界中，這樣的例子比比皆是：魚群能快速地進(jìn)行有序的大規(guī)模遷徙，螞蟻?zhàn)裱恍┓浅：唵蔚囊?guī)則就能發(fā)現(xiàn)最優(yōu)的通向食物的路徑，一群螢火蟲能夠節(jié)奏一致地進(jìn)行閃爍. 這類系統(tǒng)一般都由大量數(shù)目的個體組成，但是個體本身卻非常簡單，它們沒有中央控制器，沒有監(jiān)督者，只具有檢測局部信息的能力，信息的獲取和交換也只是在部分個體之間進(jìn)行，而且可能是動態(tài)變化的；但是就是基于這些局部信息的簡單作用或控制卻能產(chǎn)生一些人們所期望的宏觀行為. 這怎么可能呢？這就是自然界中自組織的力量.

由簡單性而導(dǎo)致的復(fù)雜性涌現(xiàn)的奇異現(xiàn)象，似乎暗示著自然界的一種內(nèi)在運(yùn)行過程，即使是最復(fù)雜的事物，它也是從最簡單的單元、最簡單的規(guī)則中演化出來的. 復(fù)雜性正是通過大量簡單元素在簡單的行為規(guī)則支配下反復(fù)迭代而形成的.

2.2 規(guī)則計(jì)算模型[4-5]

復(fù)雜系統(tǒng)通常是由許多同類型的并且相對簡單的部分或元素組成的. 部分和元素的行為通常易于理解，而整體或系統(tǒng)的行為則難于做簡單的解釋，而且從部分行為的理解中不可預(yù)測整體的系統(tǒng)行為. 這意味著，對于整體的復(fù)雜行為沒有一個明確的總體算法，更難建立一個整體的數(shù)學(xué)方程. 為什么會是這樣的呢？復(fù)雜性是怎樣形成的呢？過去我們對于這個問題沒有很好的解釋. 直到20世紀(jì)50年代，計(jì)算機(jī)之父馮·諾依曼提出一個沒有固定的數(shù)學(xué)公式的模型，即元胞自動機(jī)（Cellular Automata，CA），并給出了最簡單和最標(biāo)準(zhǔn)的案例，才清楚地說明復(fù)雜性和復(fù)雜性行為是怎樣從元素的簡單性中產(chǎn)生出來和發(fā)展起來的.

我們假定系統(tǒng)的組成元素是完全簡單的，用規(guī)則模型來表述這種簡單性并用計(jì)算機(jī)模擬這種簡單性，看復(fù)雜性怎樣由此而形成. 現(xiàn)在我們有了一抽象的計(jì)算系統(tǒng)，它在時(shí)間上和空間上都是離散的，其元素的狀態(tài)及支配這些狀態(tài)的規(guī)則在計(jì)算上是極為簡單的，但由此組成的總體模式和構(gòu)型卻可以模擬現(xiàn)實(shí)世界的全部復(fù)雜性. 這樣，我們就可以借助這種工具對復(fù)雜性的形成及其行為進(jìn)行離散動力學(xué)的分析.

我們主要在一維元胞自動機(jī)上進(jìn)行分析，討論下面幾個問題.

2.2.1 CA的基本組成

可見，CA是一個由大量的簡單元件、簡單鏈接、簡單規(guī)則、有限狀態(tài)和局域作用所組成的信息處理系統(tǒng). 但是，它可以模擬世界的絕大多數(shù)復(fù)雜現(xiàn)象，所以在理論上和實(shí)用上的潛力都是非常巨大的.

圖1 元胞自動機(jī)構(gòu)成

圖2 一維元胞自動機(jī)工作原理

2.2.2 CA的工作原理

圖3 初等元胞自動機(jī)可能的8種輸入狀態(tài)組合

圖4 初等元胞自動機(jī)可能的輸出狀態(tài)

圖5 沃爾夫勒姆110號規(guī)則

沃爾夫勒姆認(rèn)為規(guī)則110號元胞自動機(jī)是普適的，等價(jià)于一臺普適圖靈機(jī)（Universal Turing Machine）. 通過110號元胞機(jī)可以實(shí)現(xiàn)從簡單的規(guī)則和簡單的初始條件產(chǎn)生出復(fù)雜的圖形模式. 圖6給出了該元胞自動機(jī)經(jīng)過150個時(shí)間步和700個時(shí)間步的演化情況. 可以看到，得到的演化圖案中規(guī)律性與隨機(jī)性相互融合在一起：既不是完全規(guī)則的，也不是完全隨機(jī)的.

圖6 110號規(guī)則在多個時(shí)間步內(nèi)的演化情況

沃爾夫勒姆利用計(jì)算機(jī)對初等元胞自動機(jī)的256種規(guī)則做了非常詳盡的研究，在大量數(shù)值模擬實(shí)驗(yàn)的基礎(chǔ)上，他將所有元胞自動機(jī)的動力學(xué)行為歸納為如下4類.

1）平穩(wěn)型：只生成簡單重復(fù)的圖案，比如全黑、全反或黑白相間的圖形等. 它相當(dāng)于在系統(tǒng)動力學(xué)中，向著一個固定點(diǎn)吸引子演化.

2）周期型：產(chǎn)生一系列周期圖案，元胞自動機(jī)演化至持續(xù)循環(huán)狀態(tài). 它相當(dāng)于在系統(tǒng)動力學(xué)中，向著極限環(huán)演化.

①實(shí)施生態(tài)工程建設(shè)與管理離不開聯(lián)邦政府的大力支持。針對生態(tài)問題范圍廣、難度大、所需經(jīng)費(fèi)多的現(xiàn)實(shí)，雖然佛羅里達(dá)州政府全力支持水資源管理局為環(huán)境修復(fù)所做的各項(xiàng)努力，但兩者的力量仍遠(yuǎn)遠(yuǎn)不夠，聯(lián)邦政府的支持成了解決問題的關(guān)鍵。

3）混沌型：產(chǎn)生非周期圖案，或自相似的分形圖案，具有明顯的隨機(jī)性，就像不正常的電視頻道不斷發(fā)出干擾的雪花那樣，元胞自動機(jī)演化到混沌狀態(tài). 它相當(dāng)于在系統(tǒng)動力學(xué)中，向著奇異吸引子演化.

4）復(fù)雜型：產(chǎn)生復(fù)雜圖案，元胞自動機(jī)會演化成一種有序與隨機(jī)相結(jié)合的結(jié)構(gòu)，可以與生命系統(tǒng)等復(fù)雜系統(tǒng)中的自組織現(xiàn)象相比擬，如110規(guī)則. 它相當(dāng)于在系統(tǒng)動力學(xué)中，向著“混沌邊緣”演化. 系統(tǒng)的行為既不是完全隨機(jī)的，也不是完全有序的，這是復(fù)雜性的基本特性.

沃爾夫勒姆認(rèn)為，幾乎所有的元胞自動機(jī)的動力學(xué)行為都可歸結(jié)成數(shù)量如此之少的四類. 這是一個重大的發(fā)現(xiàn)，它反映出這種分類可能具有某種普適性：即使系統(tǒng)的內(nèi)在規(guī)則非常簡單，初始狀態(tài)也非常簡單，系統(tǒng)也可能展現(xiàn)出非常復(fù)雜的行為. 據(jù)此，沃爾夫勒姆認(rèn)為：這一基本現(xiàn)象最終和我們在自然界中看到的絕大多數(shù)復(fù)雜現(xiàn)象是密切相關(guān)的.

沃爾夫勒姆對元胞自動機(jī)的研究，始終貫穿著一條主線，那就是：宇宙的一切過程都僅僅遵循非常簡單的運(yùn)算，而且這個運(yùn)算很可能就是規(guī)則110號元胞自動機(jī). 他認(rèn)為，自然界的現(xiàn)象雖然千奇百怪，但大多數(shù)復(fù)雜現(xiàn)象都是由一些內(nèi)在的簡單規(guī)則決定的；如果讓計(jì)算機(jī)反復(fù)迭代極其簡單的規(guī)則，那么就可以使之發(fā)展成為異常復(fù)雜的模型，并可以解釋自然界中的絕大多數(shù)的復(fù)雜現(xiàn)象.

2.2.3 CA的特征

CA的特點(diǎn)是空間、時(shí)間、狀態(tài)都是離散的，每個元胞只取有限多個狀態(tài)，狀態(tài)更新的規(guī)則是局部且同步進(jìn)行的.

1）空間離散：各元胞分散在按一定規(guī)則劃分的離散的網(wǎng)格點(diǎn)上，元胞的狀態(tài)變化都由確定性規(guī)則表示，元胞的分布方式相合，大小形狀相合，空間分布規(guī)則整齊.

4）并行性：若將元胞自動機(jī)的狀態(tài)變化看成是數(shù)據(jù)處理，則元胞自動機(jī)的處理是同步進(jìn)行的，特別適合于并行運(yùn)算.

2.2.4 CA的優(yōu)點(diǎn)

1）CA適合于非結(jié)構(gòu)化問題的信息處理和系統(tǒng)建模.

2）CA在模擬仿真中沒有誤差積累.

3）CA不需要預(yù)先離散化.

4）CA是并行操作.

5）元胞相互作用的局域性.

總之，CA在科學(xué)方法論上提供了一種新范式：利用簡單的、局部規(guī)則的、離散的方法，去描述復(fù)雜的、全局的、連續(xù)的系統(tǒng). 所以，CA在信息系統(tǒng)科學(xué)及許多相關(guān)領(lǐng)域產(chǎn)生了巨大影響，得到了極其廣泛的應(yīng)用，幾乎涉及自然科學(xué)和社會科學(xué)的各個領(lǐng)域.

但是，在實(shí)際應(yīng)用中，用好元胞自動機(jī)的關(guān)鍵是元胞規(guī)則的確定，可以認(rèn)為，元胞的演化規(guī)則是元胞自動機(jī)的靈魂，一個元胞自動機(jī)模型是否成功，關(guān)鍵在于規(guī)則設(shè)計(jì)的是否合理，能否客觀地反映真實(shí)系統(tǒng)內(nèi)在的本質(zhì)特征. 如果遇到規(guī)則難以確定的情形，可以試驗(yàn)幾種規(guī)則，以觀察系統(tǒng)的宏觀演化結(jié)果是否與真實(shí)過程一致.

讓我們來看一個通俗的例子，教師為了提高教學(xué)質(zhì)量，對課堂教學(xué)可以確定規(guī)則. 有一位特級教師定下了“三不教”原則：1）凡學(xué)生自己看書能懂，不教；2）凡看書不懂但自己想想能夠弄懂，也不教；3）自己想想也不懂但經(jīng)過學(xué)生之間討論能夠弄懂，也不教. 這實(shí)際上是為教與學(xué)的關(guān)系定下了三條規(guī)則，最終能導(dǎo)致學(xué)生自學(xué)成才能力的顯著增強(qiáng). 長期的教學(xué)實(shí)踐實(shí)際上傳下了許多成文或不成文的規(guī)則，我們不妨從新的視角反思這些規(guī)則，并嘗試調(diào)整修改既定規(guī)則或者打破常規(guī)另立規(guī)則.

在涌現(xiàn)中應(yīng)強(qiáng)調(diào)激發(fā)自組織方法的重要性，涌現(xiàn)帶給管理者的啟示是：可以確定規(guī)則，期待涌現(xiàn)；也可以修改甚至重建規(guī)則，促成“涌現(xiàn)”.

2.3 規(guī)則計(jì)算（或迭代）蘊(yùn)含的科學(xué)思想

2.3.1 重復(fù)使用簡單規(guī)則，可能形成極為復(fù)雜的行為或圖形

一維非線性函數(shù)的迭代導(dǎo)致混沌是一個熟知的例子. 一個一維迭代：

2.3.2 采用由底向上的建模方法，可能得到一個逼真的復(fù)雜系統(tǒng)仿真模型⑤

對于簡單系統(tǒng)，人們認(rèn)為其組成元素是靜止的、被動的、沒有演化的，這樣的系統(tǒng)不會涌現(xiàn)出新的質(zhì)并形成新的有序結(jié)構(gòu). 但復(fù)雜系統(tǒng)具有涌現(xiàn)性、動態(tài)性、自適應(yīng)性、不可預(yù)測性等特征，面對這樣的系統(tǒng)，人們應(yīng)該如何進(jìn)行分析與研究呢？首先，我們應(yīng)該把系統(tǒng)的組成元素理解為“活”的個體，只有具有適應(yīng)能力的個體才是宏觀系統(tǒng)發(fā)展、演化的原動力. 例如，生物組織中的細(xì)胞、股市中的股民、城市交通系統(tǒng)中的司機(jī)、生態(tài)系統(tǒng)中的動植物……，這些個體都可以根據(jù)自身所處的環(huán)境和接收的信息，通過自己的規(guī)則進(jìn)行自適應(yīng)的判斷或決策. 我們利用計(jì)算機(jī)仿真的方法模擬復(fù)雜系統(tǒng)中個體的行為，讓一群這樣的個體在計(jì)算所營造的虛擬環(huán)境中進(jìn)行相互作用并演化，從而讓整體系統(tǒng)的復(fù)雜性行為自下而上地涌現(xiàn)出來.

2.3.3 規(guī)則計(jì)算擴(kuò)展了計(jì)算的概念和方法，成為復(fù)雜系統(tǒng)研究的重要工具

為了探索自然與社會的復(fù)雜性，科學(xué)家們從不同的角度、用不同的方法建立了各種復(fù)雜系統(tǒng)模型. 用數(shù)學(xué)解析方法所建立的微分方程模型，其時(shí)間和狀態(tài)都是連續(xù)的，這是建立在時(shí)空連續(xù)的哲學(xué)認(rèn)識基礎(chǔ)上的，一大批重要的科學(xué)規(guī)律就是利用微分方程來推理和表達(dá)的. 由于現(xiàn)代計(jì)算機(jī)建立在離散的基礎(chǔ)上，微分方程在計(jì)算時(shí)不得不對自身進(jìn)行時(shí)空離散化，建立差分方程；或者展開成冪系列方程，截取部分展開式；或者采用某種轉(zhuǎn)換用離散結(jié)構(gòu)來表示連續(xù)變量. 這個改造過程不僅是繁雜的，而且失去了微分方程最重要的特性——精確性和連續(xù)性. 從實(shí)際系統(tǒng)抽取規(guī)則所建立的模型，其時(shí)間、狀態(tài)都是離散的，不需要預(yù)先離散化，很適合于計(jì)算機(jī)建模與模擬. 霍蘭德在評價(jià)計(jì)算機(jī)模型時(shí)說：“計(jì)算機(jī)模型同時(shí)具有抽象和具體兩個特性. 這些模型的定義是抽象的，同數(shù)學(xué)模型一樣，是用一些數(shù)字、數(shù)字之間的聯(lián)系以及數(shù)字隨時(shí)間的變化來定義的. 同時(shí)，這些數(shù)字被確切地‘寫進(jìn)’計(jì)算機(jī)的寄存器中，而不只是象征性地表現(xiàn)出來. ……我們能夠得到這些具體的記錄，這些記錄非常接近在實(shí)驗(yàn)室中認(rèn)真執(zhí)行操作所得到的實(shí)驗(yàn)記錄. 這樣以來，計(jì)算機(jī)模型同時(shí)具備了理論和實(shí)驗(yàn)的特征.”正因?yàn)橛?jì)算機(jī)模型具有這樣的特點(diǎn)，所以他認(rèn)為，計(jì)算機(jī)模型是“一種對涌現(xiàn)進(jìn)行科學(xué)研究的主要工具”. 復(fù)雜性科學(xué)中的許多模型，例如霍蘭德的涌現(xiàn)模型、康威（J. H. Gonway）的“生命游戲”模型，蘭頓（C. Langton）的“人工生命”模型等都是規(guī)則計(jì)算模型，都需要在計(jì)算機(jī)中模擬實(shí)現(xiàn)，都是超越解析方法而建立的一些新模型. 在現(xiàn)代計(jì)算機(jī)的計(jì)算環(huán)境下，基于規(guī)則迭代的離散計(jì)算方式在求解方面，尤其是復(fù)雜的動態(tài)系統(tǒng)模擬方面有更大的優(yōu)勢.

3 對兩種計(jì)算模式的述評

3.1 歷史見解[2-3]

大家知道，數(shù)學(xué)是研究現(xiàn)實(shí)世界的數(shù)量關(guān)系和空間形式的科學(xué). 相應(yīng)地，數(shù)學(xué)最基本的問題大體上有兩類，一類是求解，一類是求證. 求解就是算法構(gòu)造與計(jì)算，求證就是邏輯推理與演繹證明. 二者對人類精密思維的發(fā)展不可或缺. 對“計(jì)算”大家更容易感受，因?yàn)樗侨藗儚氖驴茖W(xué)研究和工程設(shè)計(jì)時(shí)的基本活動，可以說，在人類的生活和工作中無處不在.

人類文明的進(jìn)步充分印證了，數(shù)學(xué)能以其不可比擬的、無法替代的語言（概念、公式、定理、算法、模型等）對科學(xué)的現(xiàn)象和規(guī)律進(jìn)行精確而簡潔的描述. 正如大科學(xué)伽利略的一句名言：大自然這本書是用數(shù)學(xué)語言寫成的.

但是，科學(xué)進(jìn)步是那么迅速，到了20世紀(jì)中葉，幾乎所有簡單的問題都有了答案. 廣義相對論和量子力學(xué)解釋了宇宙在大尺度與小尺度中的運(yùn)行機(jī)制；對核酸分子DNA的結(jié)構(gòu)以及它們在遺傳復(fù)制機(jī)制中的了解，使得生命現(xiàn)象可以在分子層次（比細(xì)胞更微觀的層次）上簡單地被解釋. 當(dāng)簡單的問題被解答了，很自然地，科學(xué)家就會試圖挑戰(zhàn)更復(fù)雜的問題. 數(shù)學(xué)作為人類探索未知自然規(guī)律的重要研究方法同樣面臨復(fù)雜性的挑戰(zhàn). 我們知道，自然演化遵循著一種奇妙的規(guī)律，這一規(guī)律截然不同于人類自己發(fā)明的數(shù)學(xué)解析方法. 例如，人體36.8 ℃的恒定體溫是至關(guān)重要的，0.5 ℃的偏差足以使人產(chǎn)生病態(tài)，那么在0～100 ℃這樣大的范圍內(nèi)，人體是如何求出如此精確的最佳體溫的呢？這絕對不是梯度下降等解析方法能算出的，而我們也相信目前的解析方法遠(yuǎn)遠(yuǎn)無法完整描述體溫、人體結(jié)構(gòu)與環(huán)境間錯綜復(fù)雜的關(guān)系.

為了彌補(bǔ)解析方法的不足，科學(xué)家們需要擴(kuò)充計(jì)算的概念，關(guān)鍵是建立一種新的計(jì)算模式來擴(kuò)展但不是取代以數(shù)學(xué)方程式為主的解析方法.

3.2 現(xiàn)代見解[4]

長期以來，算法和計(jì)算等概念一直與人類認(rèn)識客觀世界的活動相聯(lián)系. 今天，計(jì)算搭上了計(jì)算機(jī)這條順風(fēng)船，將其概念和方法泛化到自然界，廣泛滲透到宇宙學(xué)、物理學(xué)、生物學(xué)乃至經(jīng)濟(jì)學(xué)和社會學(xué)等諸多領(lǐng)域. 計(jì)算不僅成為人們認(rèn)識自然、生命、思維和社會的一種普適的觀念和方法，而且成為一種新的世界觀. 整個世界都是由算法控制并按算法所規(guī)定的規(guī)則演化的，宇宙是一部巨型的計(jì)算裝置，任何自然事件都是在自然規(guī)律作用下的計(jì)算過程，現(xiàn)實(shí)世界事物的多樣性只不過是算法的復(fù)雜程度的不同的外部表現(xiàn). 整個世界的演化：從虛無到存在，從非生命到生命，從感覺到思維，實(shí)際上都是一個計(jì)算復(fù)雜性不斷增加的過程. 生命的本質(zhì)是計(jì)算，自然事件的本質(zhì)也是計(jì)算，這就是20世紀(jì)80年代以來國際學(xué)術(shù)界逐步形成的關(guān)于計(jì)算的現(xiàn)代觀點(diǎn)或見解. 歷史進(jìn)入21世紀(jì)，美國物理學(xué)家、數(shù)學(xué)家和計(jì)算機(jī)專家沃爾夫勒姆花費(fèi)10年心血于2002年出版了一部1280頁的宏篇巨著《一種新科學(xué)》（），提出了復(fù)雜行為和現(xiàn)象源于簡單規(guī)則的觀點(diǎn). 在這部著作中，他以驚人之語開始：“三個世紀(jì)以前，人們發(fā)現(xiàn)建立在數(shù)學(xué)方程基礎(chǔ)上的規(guī)律能夠用于對自然界的描述，伴隨著這種新觀念，科學(xué)發(fā)生了轉(zhuǎn)變. 在此書中我的目的是將要用簡單的電腦程序來表達(dá)更為一般類型的規(guī)律，并在此規(guī)律基礎(chǔ)上建立一種新的科學(xué)，從而啟動另一場科學(xué)變革”. 作者在這里所指的三個世紀(jì)前那場發(fā)生在科學(xué)上的轉(zhuǎn)變就是我們常說的“科學(xué)革命”，那場革命從哥白尼發(fā)表《天體運(yùn)行論》為開端，到牛頓出版《自然哲學(xué)的數(shù)學(xué)原理》達(dá)到高潮. 沃爾夫勒姆認(rèn)為“傳統(tǒng)科學(xué)”未能建立解釋宇宙復(fù)雜性的理論，靠數(shù)學(xué)方程做不到這一點(diǎn)，所以他要發(fā)動一場新的“科學(xué)革命”，革命的內(nèi)容就是要用簡單的電腦程序取代數(shù)學(xué)方程. 沃爾夫勒姆所鐘情的這種簡單的電腦程序的核心就是元胞自動機(jī). 沃爾夫勒姆認(rèn)為，所有過程無論是由人力產(chǎn)生的還是自然界中自發(fā)的，都可以視作一種計(jì)算過程. 在他看來，從山頂滾下的巖石是一種計(jì)算過程，在角落里靜靜地生銹的一桶鐵釘也是一種計(jì)算過程，……. 時(shí)間和空間由離散的最小單元構(gòu)成，就如元胞自動機(jī)的元胞，宇宙間的一切變化只是元胞之間的信號傳遞. 按照他的“計(jì)算等價(jià)原理”，宇宙就是一臺普適元胞自動機(jī). 顯然，沃爾夫勒姆對元胞自動機(jī)所開展的一系列研究，更加強(qiáng)有力地支持了關(guān)于現(xiàn)代計(jì)算的觀點(diǎn)或見解.

3.3 辯證見解[2]

沃爾夫勒姆在大量的數(shù)值模擬和理論分析基礎(chǔ)上，把元胞自動機(jī)與周圍的真實(shí)世界聯(lián)系起來，例如：彈子球、紙牌游戲、布朗運(yùn)動、三體問題等等當(dāng)中的隨機(jī)性都可以用元胞自動機(jī)來解釋；流體的湍流、晶體生長的規(guī)律、華爾街股票的漲落也都可以用元胞自動機(jī)來模擬；還有自然界中的樹木、樹葉、貝殼、雪花以及幾乎所有東西的形狀，元胞自動機(jī)都能生成與它們一模一樣的圖案和形態(tài)，并能解釋這些東西的形狀為什么會是那個樣子. 沃爾夫勒姆甚至認(rèn)為凡解析計(jì)算能做的事情，規(guī)則計(jì)算也都能做. 于是他大膽預(yù)言：50年內(nèi)，更多的技術(shù)，將基于我的科學(xué)而不是傳統(tǒng)科學(xué)被創(chuàng)造出來. 人們在學(xué)習(xí)代數(shù)之前將先學(xué)元胞自動機(jī)理論. 沃爾夫勒姆的觀點(diǎn)引起了國際學(xué)術(shù)界的激烈爭論與質(zhì)疑.

其實(shí)，對于復(fù)雜系統(tǒng)模型的描述存在兩種方法：一種是建立精確的數(shù)學(xué)方程的演繹方法；一種是通過計(jì)算機(jī)反復(fù)迭代簡單規(guī)則的歸納方法. 元胞自動機(jī)是通過反復(fù)計(jì)算單純的程序代碼，可以說是歸納方法得到的結(jié)果. 演繹與歸納，是人類認(rèn)識世界的兩種基本方法，它們相互支持，相互補(bǔ)充，不存在誰取代誰的問題.

人的認(rèn)識一般是從研究個別對象開始的，從大量事實(shí)出發(fā)總結(jié)出一般規(guī)律. 例如，我們看到銅受熱體積會增大、鋁受熱體積會增大、鐵受熱體積也會增大，……，便形成一種看法：所有金屬受熱之后，體積都會膨脹. 這就是歸納推理的方法. 歸納法廣泛應(yīng)用于自然科學(xué)的研究，特別是物理學(xué)的研究. 科學(xué)家總是從有限次實(shí)驗(yàn)與觀察中作出關(guān)于無窮多對象的判斷，即由個別到一般（或普遍），結(jié)果卻常常是對的. 沃爾夫勒姆把元胞自動機(jī)應(yīng)用于樹葉、雪花、貝殼、湍流、彈子球等的模擬，其結(jié)果也都是對的，于是得出結(jié)論：從大尺度到小尺度幾乎所有東西的形態(tài)和圖案都可以用元胞自動機(jī)來模擬；幾乎所有達(dá)到一定復(fù)雜程度的系統(tǒng)都等價(jià)于規(guī)則110號元胞自動機(jī)，也即等價(jià)于一臺普適圖靈機(jī). 沃爾夫勒姆在元胞自動機(jī)理論研究中所采用的方法似乎是基于個案得來的，也就是通過歸納推理得到的.

不過，我們不禁要問歸納法得出的結(jié)論可靠嗎？猶如前面所舉金屬受熱體積會增大的例子，我們并沒有對所有種類的金屬無一遺漏地進(jìn)行加熱試驗(yàn)，你僅僅試驗(yàn)了全體金屬中極小極小的一部分，怎能從這一小部分的性質(zhì)推出全體金屬的性質(zhì)呢？怎么辦呢？這就必須用演繹推理的方法作指導(dǎo)才能作出正確的判斷.

演繹方法是從一般到個別的推理，演繹推理是一種必然性推理. 因?yàn)橥评淼那疤崾且话?，推出的結(jié)論是個別. 一般中概括個別，凡是一類事物所共同的屬性，其中的每一個別事物必然具有，所以從一般中必然能夠推出個別. 由此，我們可以這樣推理：自然界中，金屬受熱之后分子之間的凝聚力減弱，分子間距離增大，所以金屬體積會膨脹. 這就是演繹推理得出的結(jié)論. 又如，自然界中，一切物質(zhì)都是可分的，基本粒子是自然界中的一種物質(zhì)，因此，基本粒子是可分的. 在幾何學(xué)里，只有從公理或公設(shè)出發(fā)經(jīng)過演繹推理而證明的命題才被認(rèn)為是真理. 公理或公設(shè)（如：“一條有限直線可以不斷延長”、“等量加等量和相等”等）都是人們根據(jù)長期實(shí)踐經(jīng)驗(yàn)而認(rèn)為無需證明的基本事實(shí). 從幾條不言自明的公理出發(fā)，通過邏輯的鏈條，推導(dǎo)出成百上千條定理，這就是演繹推理的邏輯思維模式. 在數(shù)學(xué)王國里只承認(rèn)演繹推理，認(rèn)為由觀察得到的知識還不是真理，個別例子再多也沒有用，必須依靠演繹得出的結(jié)論才是必然的、普遍的.

為了獲得知識，認(rèn)識真理，究竟應(yīng)該用什么方法？歸納，還是演繹？這是西方哲學(xué)史上有過激烈爭論的課題. 兩種觀點(diǎn)展開了長期的反復(fù)的爭論，其結(jié)果是雙方觀點(diǎn)相互補(bǔ)充，逐漸接近：歸納與演繹是對立的統(tǒng)一. 歸納法重視感性認(rèn)識，以科學(xué)實(shí)驗(yàn)、經(jīng)驗(yàn)事實(shí)為基礎(chǔ)，是切實(shí)可靠的獲得知識的方法；演繹法重視理性認(rèn)識，能揭示出事物的內(nèi)在聯(lián)系，使我們看到現(xiàn)象背后的本質(zhì)，增加了認(rèn)識的深度. 歸納與演繹是獲得真理的兩種方法，它們既有區(qū)別又聯(lián)系密切，相互依賴，相互補(bǔ)充，使我們的認(rèn)識越來越接近真理.

傳統(tǒng)數(shù)學(xué)方程（如微分方程）是演繹推導(dǎo)出來的，其優(yōu)勢是：理論完備、嚴(yán)密、精確. 元胞自動機(jī)是一種時(shí)空離散的數(shù)學(xué)模型，借助計(jì)算機(jī)進(jìn)行計(jì)算，非常自然而合理，但是，滿足特定目的的構(gòu)型尚無完備的理論支持，其構(gòu)造往往是一個直覺過程. 微分方程和元胞自動機(jī)所對應(yīng)的計(jì)算模式：解析求解與規(guī)則迭代是一對相對的計(jì)算方法. 相對的并不一定是矛盾的，有可能是相互補(bǔ)充和相互完善的. 二者互有優(yōu)缺點(diǎn)，都有其存在的理由. 面對自然和社會的復(fù)雜性問題，人們建立的兩種科學(xué)描述體系和計(jì)算模式，它們的基礎(chǔ)不同、內(nèi)容不同、方法和形式不同，但它們是平等的伴侶，同樣重要，同樣有用，都是復(fù)雜系統(tǒng)研究的有力工具. 不過，在現(xiàn)代計(jì)算機(jī)環(huán)境下，對于元胞自動機(jī)這一類相對處于年幼階段的離散計(jì)算方式，它在理論上和實(shí)用上的潛力都是非常巨大的，需要給予更多的關(guān)注和支持.

4 結(jié)語

規(guī)則計(jì)算模型是一個眾多元素在簡單規(guī)則作用下，形成的各種各樣復(fù)雜系統(tǒng)的模型. 其中，元胞自動機(jī)從根本上開辟了一種不同于傳統(tǒng)信息系統(tǒng)的處理思想和方法，為解決現(xiàn)實(shí)世界中具有非線性、不確定性和非結(jié)構(gòu)化的復(fù)雜性問題提供了一條嶄新的途徑；所以，元胞自動機(jī)思想在許多領(lǐng)域的應(yīng)用中有著傳統(tǒng)算法思想所無法比擬的優(yōu)勢.

[1] 戴汝為. 社會智能科學(xué)[M]. 上海：上海交通大學(xué)出版社，2007.

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

[3] 顏澤賢，范冬萍，張華夏. 系統(tǒng)科學(xué)導(dǎo)論：復(fù)雜性探索[M]. 北京：人民出版社，2006.

[4] 甘濤. 元胞自動機(jī)與現(xiàn)代科學(xué)中的計(jì)算主義[M]. 北京：中國人民大學(xué)出版社，2005.

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

①參見http://www.wolfram.com/.

②John Horton Gonway. http://ibiblio.org/lifepatterns.

③ Christopher Langtom. http://zooland.alife.org.

④Complexity Digest.http://www.csu.edu.au/ci/.

⑤Journal of Complexity. http://www.academicpress.com/jcomp/.

Rule Calculation—Powerful Patterns in Complexity Exploration

WUJin-pei

(Institute of Intelligence Technology and Systems, Wuyi University, Jiangmen 529020, China)

There are many complex systems in nature. The structure of their components may be quite simple; however, they can display very rich and complex global behaviors since there are local interactions between the components. The cellular automata based on rule calculation provide a new perspective to simulating various natural and life phenomena. It is a powerful pattern in studying complex systems. This article introduces its generation and development, expounds the essence of the calculation of rules, and summarizes some questions in the modeling method based on rules and predicts its prospects.

rule calculation; complexity; cellular automata

1006-7302（2011）04-0001-13

N941.4

A

2011-07-20

吳今培（1937—），男，江西吉安人，教授，中南大學(xué)、北京航空航天大學(xué)博士生導(dǎo)師，研究方向?yàn)橄到y(tǒng)理論與復(fù)雜性研究等.