涌現(xiàn)計算概述

張江

?

涌現(xiàn)計算概述

張江

（北京師范大學(xué) 管理學(xué)院系統(tǒng)科學(xué)系，北京 100875）

通過4個實例：蟻群最短路徑算法、粒子群優(yōu)化算法、一維元胞自動機(jī)和粘菌的涌現(xiàn)計算，闡述了涌現(xiàn)計算的基本思想和方法，并對涌現(xiàn)計算中的一些問題進(jìn)行了總結(jié)與展望.

涌現(xiàn)；涌現(xiàn)計算；復(fù)雜系統(tǒng)；多主體模擬

傳統(tǒng)的計算模式大多是一種串行的、中心控制式的，例如圖靈機(jī)僅有一個讀寫頭在工作，每一個時刻只能完成一步運算[1].計算機(jī)理論科學(xué)家們已經(jīng)證明這種串行機(jī)器在原則上能夠模擬一切計算，甚至包括大規(guī)模的并行運算裝置，前提是我們對效率沒有任何要求. 然而，在現(xiàn)實世界中，效率是一個非常重要的問題，利用大量的并行空間換取運算時間是更重要的問題. 隨著計算機(jī)網(wǎng)絡(luò)以及存儲設(shè)備的大量普及，到了20世紀(jì)末期，人們越來越重視這種去中心化的、并行的運算模式. 在復(fù)雜性科學(xué)研究中，人們甚至為這些新的運算模式取了一個好聽的名字：涌現(xiàn)計算.

涌現(xiàn)（Emergence），字面翻譯為突然出現(xiàn)，在系統(tǒng)科學(xué)中它意味著“整體大于部分之和”. 任何系統(tǒng)都是由大量微觀元素構(gòu)成的整體，這些微觀個體之間會發(fā)生局部的相互作用，然而當(dāng)我們把這些個體看作一個整體的時候，就會有一些全新的屬性或者規(guī)律或者模式自發(fā)地冒出來，那么這種現(xiàn)象就被稱為涌現(xiàn)[2]. 本文通過若干涌現(xiàn)計算的例子，讓讀者真正領(lǐng)會涌現(xiàn)是一種非常強(qiáng)大的資源，可以用來解決各式各樣的實際問題，同時也指出這種方法的一些不足之處.

1 以螞蟻覓食為例簡介涌現(xiàn)與涌現(xiàn)計算

一個涌現(xiàn)的實例來自螞蟻王國[3]. 我們都知道，每只小小的螞蟻都是一個非常簡單的個體，它們沒有聰明的頭腦，只會完成一些簡單的計算任務(wù). 然而，當(dāng)把成千上萬只小螞蟻組合到一起的時候，整個蟻群就能表現(xiàn)出非常復(fù)雜、龐大的涌現(xiàn)現(xiàn)象，如社會分工、集體協(xié)作等等.

例如在螞蟻覓食的活動中，它們就能表現(xiàn)出涌現(xiàn)的行為. 我們知道，單個的螞蟻體形弱小，它們的視力范圍非常有限，只能看到鄰近的景物. 然而，當(dāng)大量的螞蟻共同協(xié)作的時候，它們通過相互作用傳遞信息，就可以發(fā)現(xiàn)一條最快的搬運食物回巢的路線，這條最快的搬運路徑就是典型的螞蟻群體的涌現(xiàn)行為. 事實上，在這群螞蟻中，并沒有哪個蟻王或者蟻后對整隊螞蟻發(fā)號施令，所有的涌現(xiàn)行為全部是這群螞蟻局部相互作用的結(jié)果.

將涌現(xiàn)的思想借鑒到計算系統(tǒng)便構(gòu)成了涌現(xiàn)計算的想法. 從計算的觀點來看，一個涌現(xiàn)系統(tǒng)其實就是一個并行計算的系統(tǒng). 蟻群中的單個螞蟻是一個小型處理器，它們可以并行地、局部地完成計算任務(wù)，而蟻群則可以通過集合這些并行處理單元來完成復(fù)雜的運算任務(wù)，如尋找有效的搬運食物路徑或者形成復(fù)雜、好看的圖案. 我們完全可能設(shè)計一個人工計算系統(tǒng)，通過模擬簡單的并行計算單元實現(xiàn)對整體涌現(xiàn)系統(tǒng)的模擬，如我們可以把蟻群覓食的例子用計算機(jī)模擬出來，具體見圖1.

圖1 螞蟻覓食的計算機(jī)模擬

在一個二維的離散化的網(wǎng)格世界里，我們可以用一個計算機(jī)程序體（稱之為Agent）來模擬一只覓食的螞蟻. 這只螞蟻可以從自己的巢穴出發(fā)，在這個網(wǎng)格世界中隨機(jī)游走. 如果它找到了食物就開始往回折返，為了呼喚其他螞蟻過來，它會在經(jīng)過的格子中撒下信息素（圖1b）中的彩色方格）. 其他的螞蟻在隨機(jī)游走的過程中，如果碰到了彩色方格（聞到了信息素的味道）就會沿著信息素的濃度向前爬行，直到找到食物. 一旦它找到食物又會進(jìn)一步向環(huán)境播撒信息素. 這樣，一旦有一只螞蟻找到了食物，就會吸引更多的螞蟻過來. 同時，信息素還會在環(huán)境中慢慢地?fù)]發(fā)、褪色，這樣，沒有螞蟻經(jīng)過的那條路徑就會逐漸耗散它的信息素，漸漸地，只有那條最短的路徑聚集了最多的螞蟻，螞蟻群體們通過相互作用找到了通向食物最短的路. 所有這些現(xiàn)象完全可以在計算機(jī)模擬世界中計算得到，因此，我們說，涌現(xiàn)是可以通過多主體計算進(jìn)行模擬的.

由于涌現(xiàn)的系統(tǒng)有很多優(yōu)越特征，例如它的抗干擾能力、創(chuàng)新性等；所以，人們感興趣的是另外一種思路，也就是我們給系統(tǒng)預(yù)設(shè)一個具體的計算目標(biāo)，但是這個計算目標(biāo)不是通過傳統(tǒng)的編程直接告訴計算機(jī)如何實現(xiàn)，而是通過設(shè)計一種微觀個體的相互作用規(guī)則，從而讓最終的目標(biāo)自發(fā)地涌現(xiàn)出來. 也就是說，如果某系統(tǒng)的涌現(xiàn)行為或者屬性可以看作是某種計算的話，那么我們就稱這個系統(tǒng)正在執(zhí)行涌現(xiàn)計算[4].

涌現(xiàn)計算與涌現(xiàn)的模擬有很大的相似性，它們都是利用計算系統(tǒng)實現(xiàn)系統(tǒng)的涌現(xiàn)現(xiàn)象，但是二者又有很大的不同. 涌現(xiàn)的模擬旨在用計算機(jī)模擬一個真實的系統(tǒng)，使得這個模擬具備某種涌現(xiàn)的特征；而涌現(xiàn)計算則要求更高：該系統(tǒng)不僅需要具備涌現(xiàn)特征，這種涌現(xiàn)特征還要能完成某種特定的計算任務(wù). 也就是說，涌現(xiàn)模擬是利用個體的簡單計算而實現(xiàn)涌現(xiàn)，涌現(xiàn)計算則要求系統(tǒng)的涌現(xiàn)完成實際的計算.

讓我們再回到螞蟻的例子上來，雖然我們已經(jīng)可以把蟻群的行為和涌現(xiàn)屬性用計算機(jī)模擬出來，但這個模擬系統(tǒng)并不能幫我們執(zhí)行有意義的計算. 轉(zhuǎn)機(jī)出現(xiàn)了，1992年Marco Dorigo在他的博士論文中提出了蟻群優(yōu)化算法[5]（Ant Colony Optimization）：通過改造螞蟻的模擬程序的確找到了一條真實地圖上的最短路徑（具體參見文獻(xiàn)[6]）. 這是一種典型的涌現(xiàn)計算的例子，作為一種涌現(xiàn)的結(jié)果，這條最短路徑是被涌現(xiàn)計算出來的.

進(jìn)一步，蟻群優(yōu)化算法還可以用來解決包括旅行商問題、組合優(yōu)化問題等更一般的問題. 這也就體現(xiàn)了涌現(xiàn)計算的強(qiáng)大優(yōu)勢.

2 3種涌現(xiàn)計算實例

2.1 粒子群優(yōu)化算法

1986年，計算機(jī)科學(xué)家Craig Reynolds發(fā)明了一種被稱為Boid的計算機(jī)模擬程序. 通過給計算機(jī)中的智能體（Boid）設(shè)置3條簡單的規(guī)則：靠近、對齊、避免碰撞，Craig就能活靈活現(xiàn)地模擬出鳥類群體的飛行行為[7]. 然而，早期的Boid僅僅能夠逼真地模擬實際的鳥類飛行情況，如果我們在Boid所處的人工環(huán)境中加入食物會出現(xiàn)什么情況呢？在真實世界中，鳥類會爭先恐后地奔向食物. 假如我們在Boid飛行的環(huán)境撒上很多食物，顏色深的地方表示食物濃度大，淺的地方濃度小，那么Boid就應(yīng)該會自動聚集在食物濃度較大的地方.

能不能用鳥類飛行覓食的行為來解決實際的優(yōu)化問題呢？我們?nèi)匀徊捎帽扔鞯姆椒?，把人工Boid飛行的空間比喻成優(yōu)化問題的解空間，把優(yōu)化函數(shù)的函數(shù)值比喻成食物的濃度. 這樣，優(yōu)化函數(shù)值越大的地方對應(yīng)的食物越多，Boid飛向這個點的概率就會越大. 最后，很有可能所有的Boid都集中到了目標(biāo)函數(shù)值最大的點，從而利用Boid群體的涌現(xiàn)行為求解了函數(shù)優(yōu)化的問題.

這實際上就是粒子群優(yōu)化算法（Particle Swarm Optimization，簡稱PSO算法）的思路. 在PSO算法中，一群虛擬的粒子（就相當(dāng)于是Boid）在優(yōu)化空間中自由飛翔，它們會尋找食物并聚集到食物最多的點從而完成優(yōu)化任務(wù). 如果某個特殊的Boid在問題空間中發(fā)現(xiàn)了一個食物濃度更高的點，它就會召集其他的Boid過去. Boid在飛行的過程中會經(jīng)歷一些小的干擾，這樣就會使有些Boid在飛行的過程中發(fā)生與原軌道的較小偏移，從而使得Boid群體具有了一定的創(chuàng)新性.

圖2 PSO算法優(yōu)化函數(shù)的動態(tài)展示

2.2 一維元胞自動機(jī)的涌現(xiàn)計算

為了更好地理解涌現(xiàn)計算是怎樣在計算機(jī)中發(fā)生的，Jims Crutchfield[9]用一類最簡單的涌現(xiàn)系統(tǒng)：一維的元胞自動機(jī)來實現(xiàn)涌現(xiàn)計算. 由于一維的元胞自動機(jī)是一類典型的通過局部相互作用生成復(fù)雜的全局模式的系統(tǒng)，所以，細(xì)致分析這類系統(tǒng)往往能夠讓我們對系統(tǒng)的運作機(jī)理有更好的了解.

所謂的一維元胞自動機(jī)是一個一維的方格世界，如圖3所示. 其中每一個方格（元胞）是由黑白兩種顏色構(gòu)成的，并且每個元胞下一時刻的顏色僅僅由它左右兩側(cè)元胞的顏色決定. 我們知道，每個元胞的顏色只有黑白兩種，這樣，任意一個元胞加上它左右兩個元胞的顏色組合就一共有8種情況：黑黑黑、黑黑白，黑白黑、白黑黑、黑白白、白黑白、白白白. 只要我們?yōu)檫@8種情況下的每一種都指定當(dāng)前元胞在下一時刻的顏色，那么就完全定義了這個一維元胞自動機(jī)的規(guī)則.

圖3 一維元胞自動機(jī)

我們可以用一張二維圖形來展現(xiàn)一維元胞自動機(jī)的運行情況，如圖4所示. 圖4a）中，每一個橫行表示這個元胞自動機(jī)在某一時刻的狀態(tài)，從上往下則表示時間運行的狀態(tài)，每一個元胞都根據(jù)它左右兩個鄰居的顏色進(jìn)行自己顏色的更新. 元胞自動機(jī)的動態(tài)展現(xiàn)二維圖如圖4b）所示.

圖4 一維元胞自動機(jī)的運行

一維的元胞自動機(jī)完全是一個確定性的系統(tǒng)，由于規(guī)則是固定的，這樣，只要給定初始狀態(tài)（第1行的黑白排列情況），那么元胞自動機(jī)所畫出的圖像就是固定的.

我們完全可以把這個元胞自動機(jī)看作是一個計算系統(tǒng)，只要我們把該自動機(jī)的初始條件看作是這個元胞自動機(jī)的輸入數(shù)據(jù)，而把運行比如說100步之后的黑白元胞的分布情況看作它的計算結(jié)果，那么給定一組輸入條件之后，這個元胞自動機(jī)就會完成一系列局部的操作，最終在第100步的時候給出一個結(jié)果. 當(dāng)元胞自動機(jī)的規(guī)則確定之后，不同的輸入一般會對應(yīng)不同的輸出結(jié)果. 但問題是，一般情況下，這個元胞自動機(jī)不會進(jìn)行有意義的運算，因為它的規(guī)則太任意了.

能不能設(shè)計某種非常簡單的計算任務(wù)，從而在各種各樣的元胞自動機(jī)（規(guī)則不同）中找到一種合適的自動機(jī)來完成指定的計算任務(wù)呢？Crutchfield運用遺傳算法對所有可能的一維元胞自動機(jī)進(jìn)行搜索，通過不斷進(jìn)化，系統(tǒng)終于找到了一些能完成簡單運算的元胞自動機(jī). 比如，Crutchfield設(shè)計的一個簡單的運算任務(wù)就是對初始的黑白元胞的比例進(jìn)行分類. 如果初始條件下，黑色的元胞偏多一些，元胞自動機(jī)100步后的輸出就必須全部都是黑色元胞；反之，則要求元胞自動機(jī)在100步后全部輸出白色. 這樣，如果我們把初始的黑白元胞看作輸入，把100步后的結(jié)果看作輸出，那么這個一維元胞自動機(jī)就能夠完成密度分類這個簡單的任務(wù)[10]，如圖5所示.

圖5 一維元胞自動機(jī)完成密度分類任務(wù)

這個任務(wù)表面上看起來很簡單，然而對于元胞自動機(jī)來說卻非常難. 因為每個元胞只能跟它左右兩個鄰居通信而看不到輸入時候的整體情況. 在計算過程中，每一個元胞也只能根據(jù)左右鄰居的顏色機(jī)械地按照固定的規(guī)則變換顏色，不存在某個超級元胞能夠?qū)λ械脑l(fā)號施令以決定系統(tǒng)的運行. 也就是說，這群元胞必須學(xué)會相互協(xié)調(diào)合作才能完成對于它們來說非常復(fù)雜的任務(wù).

然而，通過遺傳算法，Crutchfield終于找到了這種能夠完成密度分類任務(wù)的一維元胞自動機(jī). 6a）圖的初始黑色元胞密度為0.48，該元胞自動機(jī)正確給出了全部是白色的答案；6b）圖的初始密度為0.51，該元胞自動機(jī)正確給出了全部黑色的答案.

圖6 用遺傳算法找到的可以成功分類初始元胞黑色密度的自動機(jī)

遺傳算法終于找到了可以正確分類的元胞自動機(jī)，那么究竟這些簡單的自動機(jī)是如何完成這種復(fù)雜的計算任務(wù)的呢？Crutchfield進(jìn)一步研究發(fā)現(xiàn)，這些成功分類的自動機(jī)的運行圖都具備一種明顯的特征：有很多橫框區(qū)域的大斜線，以及一些明顯的三角形塊狀區(qū)域. 我們知道，在元胞自動機(jī)的運行圖中，一條黑色的斜線就相當(dāng)于一個傳播的信號（黑色元胞的信息從一側(cè)傳遞到另一側(cè)）. 也就是說，這些元胞之間會建立一種相互通信的機(jī)制. 當(dāng)初始的某一個區(qū)域有更多的黑色元胞的時候，在這些元胞的邊界出就會產(chǎn)生某種“粒子”（有一些傳播的元胞組成），從而與白色元胞區(qū)域產(chǎn)生對消的現(xiàn)象. 這樣，通過不斷的“粒子對消”完成了黑色元胞數(shù)與白色元胞數(shù)的比較，最后輸出正確的運算結(jié)果.

為了看清楚這些簡單的元胞自動機(jī)的運行原理，Crutchfield甚至過濾掉了那些規(guī)則的三角塊區(qū)域，而把邊界的“粒子”凸現(xiàn)出來（圖7）. 我們看到，這些粒子（標(biāo)為希臘字母的線條）在時空中運動，把信息從世界的一端傳遞到另一端，并與其他的粒子相互碰撞、反應(yīng)，生成其他的粒子或者湮滅，從而完成對于這些元胞自動機(jī)來說非常復(fù)雜的計算任務(wù).

圖7 “粒子碰撞”圖

總結(jié)來看，Crutchfield所研究的演化元胞自動機(jī)屬于一類涌現(xiàn)計算模型，每個元胞都只能完成簡單的局部運算，但是這些元胞通過相互作用完成了全局的運算. Crutchfield的研究進(jìn)一步指出，這些簡單的并行相互作用的元胞之所以能夠完成全局運算，其中一個最重要的因素就是它們可以通過“粒子”進(jìn)行跨區(qū)域的通信，從而使不同區(qū)域的兩個或多個元胞之間能夠發(fā)生相互作用而實現(xiàn)整體的協(xié)調(diào)與合作.

Crutchfield的研究指出，涌現(xiàn)計算的一個重要的必要條件就是：信息的流動. 只有信息的流動才能完成不同區(qū)域的通信，從而真正讓本來相互分散的個體連接成一個整體.

2.3 粘菌的涌現(xiàn)計算

之前提到的各種涌現(xiàn)計算或者對涌現(xiàn)的模擬都是在計算機(jī)中完成的，下面看一個發(fā)生在現(xiàn)實世界中的涌現(xiàn)計算的例子.

2010年1月，著名科學(xué)雜志《Science》刊登了一篇題名為Rules for Biologically Inspired Adaptive Network Design的文章，作者是來自日本北海道大學(xué)的Tero等教授. 他們利用現(xiàn)實世界的一團(tuán)粘菌（俗稱鼻涕蟲，一種粘菌門的組織，生長在腐爛的植物或潮濕的地面上，英文名字為Slime mold）設(shè)計了一條連通東京及其附近城市的鐵路網(wǎng)[10]！這是一次別開生面的涌現(xiàn)計算！

粘菌是一群裸露的無細(xì)胞壁多核的原生質(zhì)團(tuán)，它們可以通過連續(xù)的形變而緩慢移動，當(dāng)這團(tuán)裸露的細(xì)胞在空間上遇到多個分散的食物源的時候，就會構(gòu)建起一些運輸營養(yǎng)的通道. Tero等教授正是利用了粘菌的這種天性，在實驗室中為粘菌們設(shè)計了一套人工食物源環(huán)境，讓這群簡單的原生質(zhì)團(tuán)形成了運輸營養(yǎng)的網(wǎng)絡(luò). 他們將一張東京以及附近城市的地圖作為粘菌生長的環(huán)境，在初始時刻，讓粘菌集中在地圖上的東京點，接著在地圖東京附近的城市放上粘菌喜歡吃的食物，然后讓這群粘菌在實驗地圖上緩慢變形、游走. 起初，這群簡單的細(xì)胞群體在地圖上擴(kuò)散，幾個小時后，當(dāng)它們遇到了食物之后就開始精煉這些模式而形成若干運輸食物的隧道；再經(jīng)過幾個小時后，一些較大的運輸隧道開始慢慢成長，而更多的小型隧道逐漸消失；最終，只有幾個主干隧道保留了下來. 經(jīng)過一天多的時間，它們最終演化出了一條條營養(yǎng)運輸網(wǎng)絡(luò) .

實驗人員將粘菌構(gòu)建的食物運輸網(wǎng)絡(luò)與現(xiàn)實的東京附近的地鐵網(wǎng)絡(luò)進(jìn)行比較，發(fā)現(xiàn)這兩種網(wǎng)絡(luò)非常相似，如圖8所示.

圖8 粘菌計算出的運輸網(wǎng)絡(luò)與東京附近城市的鐵路網(wǎng)絡(luò)對比①

圖8向我們展示，兩個網(wǎng)絡(luò)無論在結(jié)構(gòu)還是形狀上都非常相似. 也就是說，這群看起來笨拙無比、沒有任何智力可言的粘菌的確完成了可觀的計算任務(wù)：修筑軌道網(wǎng)絡(luò). 更有趣的是，為了修建這樣一套有效率的網(wǎng)絡(luò)運輸系統(tǒng)，被稱為靈長類動物之首，號稱具有超凡智力的人類設(shè)計師也要花費數(shù)十年的時間.

就這樣，這些簡單得不能再簡單、低級得不能再低級的粘菌通過簡單的相互作用就在整體上實現(xiàn)了一次可觀的涌現(xiàn)計算.

3 討論

在領(lǐng)略了各式各樣的涌現(xiàn)計算的實例之后，我們一定會感嘆大自然的鬼斧神工，原來簡單的計算機(jī)程序或者是粘菌竟能完成如此復(fù)雜的運算任務(wù). 然而，涌現(xiàn)與計算這個課題才剛剛開始，我們對于涌現(xiàn)和計算還知之甚少，由涌現(xiàn)計算引發(fā)的一些問題需要思考.

3.1 永恒的新奇與開放式結(jié)局

我們曾指出，涌現(xiàn)是指一種不能夠還原成底層的高層屬性或者現(xiàn)象，尤其是對于計算系統(tǒng)來說，人們更希望系統(tǒng)能夠自發(fā)冒出來一些設(shè)計者意想不到的新奇屬性. 著名的系統(tǒng)科學(xué)家John Holland（遺傳算法之父）曾用“永恒的新奇性”（Perpetual Innovation）一詞來描述人們希望實現(xiàn)的真正的涌現(xiàn)計算系統(tǒng).

我們都知道，自然界的進(jìn)化現(xiàn)象是生生不息、永無休止的. 一個物種滅絕了，總會伴隨著新的物種出現(xiàn)，更有趣的是，進(jìn)化還會產(chǎn)生于多個層面上. 宇宙的演化用了大約150億年的時間，而地球上的生命演化則僅僅用了40多億年的時間；人類出現(xiàn)之后，文明的進(jìn)化卻僅用了將近5 000年時間. 在每個層面上，復(fù)雜性和新奇性不斷產(chǎn)生，進(jìn)化永無休止.

在涌現(xiàn)計算中，程序員希望他們設(shè)計的系統(tǒng)能實現(xiàn)一種所謂的開放式結(jié)局進(jìn)化（Open Ended Evolution）. 即進(jìn)化能夠永無休止地運行下去，一些新的屬性和現(xiàn)象能從系統(tǒng)中冒出來. 開放式結(jié)局一直是程序設(shè)計者追求的目標(biāo)之一，但多年來一直沒有實現(xiàn). 這是為什么呢？有沒有理論上的解答呢？

3.2 涌現(xiàn)計算與尺度

有人說，之所以我們沒有看到永恒的新奇和開放式結(jié)局，是因為我們沒有給人工涌現(xiàn)系統(tǒng)提供足夠大的演化空間和足夠長的演化時間. 大自然進(jìn)化出生命都用了數(shù)十億年的時間，憑什么要計算機(jī)僅僅用幾個小時或者幾天就演化出堪與自然界相比的復(fù)雜性呢？正如J.Gonway指出的，“只要給我足夠大的方格空間，并等待足夠長的時間，從原則上講，‘生命’（一種特殊的二維元胞自動機(jī)模型）游戲中可以創(chuàng)造任何你想要的東西，包括宇宙天體、進(jìn)化的生物，甚至是可以撰寫Ph.D論文的智慧生命”. 但關(guān)鍵問題是，我們到底需要多大的空間和多長的時間呢？

有人曾作過粗略計算：如果每個方格占用一個屏幕像素大小的空間，那么要在“生命游戲”中實現(xiàn)一個能夠完成自我復(fù)制的原始生命，就至少需要整個紐約市那么大的屏幕！可問題是，人類愿意設(shè)計這么大規(guī)模尺度的計算系統(tǒng)嗎？這樣的計算模擬系統(tǒng)有意義嗎？這也為我們提出了一個非常重要的理論問題：涌現(xiàn)計算和系統(tǒng)的尺度（空間上、時間上）到底有什么關(guān)系？分形的研究告訴我們，很多復(fù)雜系統(tǒng)都會展現(xiàn)出一種無標(biāo)度的特征. 也就是說，無論你從哪一個尺度去觀察一個復(fù)雜分形系統(tǒng)，都會發(fā)現(xiàn)它們是相似的. 如著名科學(xué)家Manderbrolt就曾指出，用不同單位的尺子去測量英國的海岸線，會得到完全不同的總長度. 這是因為海岸線是一個分形，隨著觀測尺度越來越精細(xì)，海岸線本身也會展現(xiàn)得越來越復(fù)雜，你完全找不到一種特征尺度能夠最好地刻畫復(fù)雜的分形.

因此，在計算系統(tǒng)中，我們也可能根本找不到一種所謂的特征尺度（空間或者時間），來最好地模擬大自然的永恒新奇和開放式結(jié)局進(jìn)化現(xiàn)象. 這是因為，大自然系統(tǒng)總是會隨著我們描述、模擬它的精度變大而不斷冒出各種復(fù)雜性. 但是無論計算系統(tǒng)多大，它總歸是有限的，是具備特征尺度的. 所以，這類系統(tǒng)永遠(yuǎn)也不會實現(xiàn)而只能無限逼近永恒的新奇與開放式結(jié)局. 這也僅僅是筆者的猜測之一，諸如尺度、分形、涌現(xiàn)等問題還需要更細(xì)致的分析研究.

3.3 涌現(xiàn)計算的語義與觀察者

雖然涌現(xiàn)計算在很多不同領(lǐng)域如人工模擬的螞蟻、真實的粘菌獲得了成功，但是，回想這些成功的案例，它們幾乎是一個例子一種設(shè)計，沒有什么共同性可言. 當(dāng)面臨一個嶄新的任務(wù)時，除了進(jìn)行反復(fù)的實驗，我們?nèi)匀徊荒茏裱恍┮?guī)律直接設(shè)計出一種涌現(xiàn)計算系統(tǒng). 這其中的一個關(guān)鍵問題就在于：計算系統(tǒng)需要在高層次與設(shè)計者進(jìn)行語義上的溝通，從而按照設(shè)計的模式去演化.

通常來講，我們給定計算機(jī)一組局部作用規(guī)則，讓它們在計算機(jī)中相互作用、演化是很容易的，這種系統(tǒng)必然會演化出一種整體的模式（例如元胞自動機(jī)）. 但問題的難點在于，這種整體模式對于我們觀察者來說往往是沒有任何意義的. 所以，涌現(xiàn)計算要解決的一個關(guān)鍵性問題就是如何在雜亂無章的整體模式與觀察者可理解的意義之間建立起一種聯(lián)系.

演化的元胞自動機(jī)模型部分地回答了這個問題. 我們需要一種從觀察者到系統(tǒng)整體，再從系統(tǒng)整體到系統(tǒng)局部的反饋機(jī)制. 也就是說，由觀察者來判斷系統(tǒng)整體行為的語義（例如元胞自動機(jī)能不能對初始方格進(jìn)行密度分類），之后系統(tǒng)按照觀察者賦予的意義進(jìn)行演化（遺傳算法）. Crutchfield的研究指出，這種高層次的行為又會反饋給具體的元胞，并在它們之間產(chǎn)生一種信號傳遞機(jī)制，從而完成我們要求的涌現(xiàn)計算.

另外一種解決途徑來源于粘菌的涌現(xiàn)計算例子. 在這里，我們?nèi)匀恍枰c涌現(xiàn)系統(tǒng)建立某種高層次的語義聯(lián)系，但是改變的不再是系統(tǒng)，而是觀察者本身. 對于粘菌來說，它們自身的規(guī)則始終沒有改變過，它們只知道在低層次尋找食物. 然而，我們觀察者理解了粘菌的習(xí)性，于是通過設(shè)計食物的擺放位置（觀察者的行為），從而誘導(dǎo)出了粘菌涌現(xiàn)計算的整體意義.

[1] LEWIS H R, PAPADIMITRIOU C H. Elements of the theory of computation[M]. New Jersey: Prentice-Hall Inc,1998.

[2] 約翰·霍蘭. 涌現(xiàn)：從混沌到有序[M]. 上海：上?？茖W(xué)技術(shù)出版公司，2006.

[3] 李建會，張江. 數(shù)字創(chuàng)世紀(jì)：人工生命的新科學(xué)[M]. 北京：科學(xué)出版社，2006.

[4] FORREST S, HOFMEXR S A, SOMAYAJI A. Emergent computation[M]. Herausgeber: MIT Press, 1991.

[5] DORIGO M. Optimization, learning and natural algorithms[D]. Milano: Politecnico di Milan, 1992.

[6] 王旭，張江，崔平遠(yuǎn). 一種基于蟻群算法求解路徑規(guī)劃問題的新方法[C]//2003年中國智能自動化會議論文集：下冊，2003: 996-999.

[7] REYNOLDS C W. Flocks, herds and schools: a distributed behavioral model[J]. Computer Graphics, 1987, 21(4): 25-34.

[8] KENNEDY J, EBERTHART R. Particle swarm optimization[C]//IEEE Transations, 1995: 1942-1948.

[9] CRUTCHFIELD J P, MITCHELL M, DAS R. The evolutionary design of collective computation in cellular automata[M]//Evolutionary dynamics exploring the interplay of selection, neutrality, accident, and function. New York: Oxford University Press, 2002.

[10] TERO A, TAKAGI S, SAIGUSA T, et al. Rules for biologically inspired adaptive network design[J]. Science, 2010, 327: 439-442.

[11] 米歇爾·沃爾德洛普. 復(fù)雜：誕生于混沌與秩序邊緣的科學(xué)[M]. 北京：生活、讀書、新知三聯(lián)書店，1997.

①圖片參見http://www.wired.com/wiredscience/2010/01/slime-mold-grows-network-just-like-tokyo-rail- system/

Introduction to Emergent Computation

ZHANGJiang

(Department of Systems Science, School of Management, Beijing Normal University, Beijing 100875, China)

This paper introduces a new paradigm of computation emergent computation, which takes advantage of parallel computing of a large number of interacting individuals to process some complicated computational tasks. It presents the basic ideas and methods of emergent computation by four instances: ant colony shortest path finding, particle optimization algorithm, one-dimensional evolutionary cellular automata and the natural computing of the real slime molds. Finally, it summarizes some questions and the prospects of the emergent computation.

emergence; emergent computation; complex systems; multi-agent simulation

1006-7302（2011）04-0029-09

N941.1

A

2011-07-20

張江（1978—），男，北京市人，博士，中科院數(shù)學(xué)與系統(tǒng)科學(xué)所博士后，研究方向為系統(tǒng)理論與復(fù)雜性研究.