涌現(xiàn)計(jì)算綜述

李 勁， 肖人彬

(華中科技大學(xué)自動(dòng)化學(xué)院，武漢 430074)

涌現(xiàn)計(jì)算綜述

李 勁， 肖人彬

(華中科技大學(xué)自動(dòng)化學(xué)院，武漢 430074)

從涌現(xiàn)現(xiàn)象入手，介紹了涌現(xiàn)計(jì)算的基本原理和特點(diǎn)；接著介紹了一種重要的涌現(xiàn)計(jì)算模型—元胞自動(dòng)機(jī)，并闡明了涌現(xiàn)計(jì)算與群集智能的關(guān)系；然后探討了涌現(xiàn)計(jì)算中待求解問題的涌現(xiàn)計(jì)算模型映射、自組織現(xiàn)象和同步現(xiàn)象等涌現(xiàn)計(jì)算中的若干關(guān)鍵問題；最后從工程涌現(xiàn)計(jì)算和社會(huì)涌現(xiàn)計(jì)算兩個(gè)方面綜述了涌現(xiàn)計(jì)算在自動(dòng)設(shè)計(jì)，工程優(yōu)化，交通管理、智能控制、信息處理等工程領(lǐng)域及其在公共管理、市場(chǎng)、經(jīng)濟(jì)和軍事等社會(huì)領(lǐng)域的應(yīng)用。

涌現(xiàn)計(jì)算；群集智能；元胞自動(dòng)機(jī)

0 引言

在自然系統(tǒng)、社會(huì)系統(tǒng)以及許多人工系統(tǒng)中普遍存在著涌現(xiàn)現(xiàn)象。所謂涌現(xiàn)，是指由大量相對(duì)簡單的單元(agent)構(gòu)成的系統(tǒng)，在agent之間的局部相互作用下，會(huì)在整體上出現(xiàn)一些在局部觀察不到的新的屬性、規(guī)律或者模式。自然界中的很多物理現(xiàn)象，如大量氣體分子共同作用產(chǎn)生氣體壓力，大量光子作用形成干涉或衍射圖樣，受激幅射產(chǎn)生激光等都可以視為一種涌現(xiàn)現(xiàn)象；在人類和動(dòng)物社會(huì)系統(tǒng)中，螞蟻的覓食、筑巢等行為，蜂群的花蜜采集行為，鳥群覓食和飛行行為，人類的交往合作行為等都是涌現(xiàn)現(xiàn)象；而在互聯(lián)網(wǎng)、交通網(wǎng)、物流網(wǎng)絡(luò)、經(jīng)濟(jì)系統(tǒng)等人工系統(tǒng)中也存在各種涌現(xiàn)現(xiàn)象。

人們構(gòu)建了許多模型來模擬自然界中的涌現(xiàn)現(xiàn)象，如元胞自動(dòng)機(jī)[1]、人工神經(jīng)網(wǎng)絡(luò)、人工生命模型，遺傳算法、蟻群算法、蜂群算法、人工免疫算法等。此類模型具有一些共同的特征，那就是由多個(gè)相對(duì)簡單的主體(agent)構(gòu)成，每個(gè)agent遵守一些簡單的規(guī)則并相互作用，從而在整體上產(chǎn)生涌現(xiàn)現(xiàn)象，具有整體大于部分之和的特點(diǎn)。通過將一些待解決的問題映射到此類模型中，可以對(duì)一些傳統(tǒng)計(jì)算方法不易解決的問題進(jìn)行高效的求解。這種利用涌現(xiàn)現(xiàn)象進(jìn)行問題求解的方法稱為涌現(xiàn)計(jì)算。

與主要關(guān)注于線性行為的傳統(tǒng)計(jì)算方法不同，涌現(xiàn)計(jì)算是從非線性系統(tǒng)的涌現(xiàn)現(xiàn)象中獲得計(jì)算結(jié)果的。在大量相互作用的簡單單元構(gòu)成的非線性系統(tǒng)中，存在自組織、合作、同步等復(fù)雜現(xiàn)象，對(duì)這些現(xiàn)象的研究有利于我們理解涌現(xiàn)現(xiàn)象的產(chǎn)生規(guī)律，從而更好地利用涌現(xiàn)計(jì)算來解決實(shí)際問題。在許多情境下，涌現(xiàn)計(jì)算具有比傳統(tǒng)計(jì)算更高的效率，對(duì)于某些問題而言使用涌現(xiàn)計(jì)算方法是目前唯一有效的解決途徑[2]。

1 涌現(xiàn)現(xiàn)象

1.1 涌現(xiàn)現(xiàn)象的基本概念和性質(zhì)

涌現(xiàn)的一個(gè)簡單描述性定義是：復(fù)雜系統(tǒng)內(nèi)部個(gè)體之間通過局部相互作用，產(chǎn)生在系統(tǒng)層面上才能觀察到的一些新屬性和新現(xiàn)象[3]。在復(fù)雜系統(tǒng)中，隨著系統(tǒng)從局部到整體的過渡，少數(shù)規(guī)則可以產(chǎn)生復(fù)雜而神奇的系統(tǒng)現(xiàn)象，在這些復(fù)雜的系統(tǒng)現(xiàn)象中存在一些特定的模式，我們通常將這些可識(shí)別并且可以重復(fù)發(fā)生的特征和模式稱為涌現(xiàn)現(xiàn)象。因此可識(shí)別并且可以重復(fù)是涌現(xiàn)現(xiàn)象必不可少的特征之一，這意味著涌現(xiàn)現(xiàn)象反映著系統(tǒng)中某些規(guī)律性的部分。在孕育涌現(xiàn)現(xiàn)象的復(fù)雜系統(tǒng)中，通常不存在一個(gè)中心控制者，即涌現(xiàn)現(xiàn)象是在沒有中心控制的情況下發(fā)生的，它基于眾多主體的簡單相互作用而產(chǎn)生，但同時(shí)又遠(yuǎn)遠(yuǎn)超過了主體個(gè)體的能力范圍。由于無法從簡單的局部規(guī)則中預(yù)測(cè)到會(huì)發(fā)生什么樣的涌現(xiàn)現(xiàn)象，無法預(yù)料是涌現(xiàn)的另一重要特征，這一特性同時(shí)也帶來了搜索和尋求問題更優(yōu)解的可能性。

1.2 自然系統(tǒng)中的涌現(xiàn)現(xiàn)象

自然中存在許多涌現(xiàn)現(xiàn)象，這也是我們得以進(jìn)行涌現(xiàn)計(jì)算建模的基礎(chǔ)。一個(gè)典型的例子就是蟻群的覓食行為。每只單獨(dú)的螞蟻都是一個(gè)相對(duì)簡單的個(gè)體，能力有限，只能完成一些簡單的任務(wù)。然而，當(dāng)大量的螞蟻個(gè)體在一起形成蟻群時(shí)，整個(gè)蟻群就能表現(xiàn)出非常復(fù)雜和神奇的涌現(xiàn)現(xiàn)象，如社會(huì)分工、集體協(xié)作等等。例如在螞蟻覓食的過程中，就能表現(xiàn)出具有智能的涌現(xiàn)行為，能夠?qū)ふ业匠惭ǖ绞澄锏淖顑?yōu)路徑。這一行為已經(jīng)超出了單個(gè)螞蟻的能力范疇，是大量螞蟻通過傳遞信息相互作用共同協(xié)作的結(jié)果。在螞蟻覓食的過程中，不存在一個(gè)中心控制個(gè)體，蟻群是通過分布式的協(xié)作找到最快搬運(yùn)路徑的，這一行為完全是局部相互作用的結(jié)果，是蟻群中典型的涌現(xiàn)現(xiàn)象。除了覓食行為，蟻群中還存在勞動(dòng)分工[4]和墓地構(gòu)造[5]等涌現(xiàn)現(xiàn)象。與蟻群中類似的涌現(xiàn)現(xiàn)象在蜂群、鳥群和魚群中同樣存在。此外，人體中神經(jīng)系統(tǒng)的記憶、學(xué)習(xí)等智能行為和表現(xiàn)可以視為神經(jīng)元相互作用而產(chǎn)生的涌現(xiàn)現(xiàn)象[6]，大量細(xì)胞的相互作用中存在著豐富的涌現(xiàn)現(xiàn)象[7]。

1.3 社會(huì)系統(tǒng)中的涌現(xiàn)現(xiàn)象

涌現(xiàn)現(xiàn)象在人際交往，演員合作，科學(xué)家合作和經(jīng)濟(jì)系統(tǒng)等社會(huì)系統(tǒng)中非常普遍。

Tao Z等[8]提出了社區(qū)結(jié)構(gòu)涌現(xiàn)的判別方法，并對(duì)美國安然公司以電子郵件發(fā)送關(guān)系形成的社會(huì)網(wǎng)絡(luò)進(jìn)行了研究，得到了社區(qū)結(jié)構(gòu)的演化過程及其涌現(xiàn)現(xiàn)象的計(jì)算結(jié)果。

此外，經(jīng)濟(jì)系統(tǒng)也是一個(gè)很好的例子。隨著計(jì)算機(jī)技術(shù)的發(fā)展，研究者們?cè)絹碓蕉嗟厥褂枚郺gent涌現(xiàn)合作系統(tǒng)來對(duì)市場(chǎng)互動(dòng)行為進(jìn)行探索，以發(fā)現(xiàn)經(jīng)濟(jì)金融現(xiàn)象中更多的規(guī)律和知識(shí)，為價(jià)格預(yù)測(cè)，資產(chǎn)交易及市場(chǎng)應(yīng)用設(shè)計(jì)新的商業(yè)模式。經(jīng)濟(jì)學(xué)之父亞當(dāng)·斯密曾提出有“看不見的手”在引導(dǎo)著市場(chǎng)，今天我們可以認(rèn)為這個(gè)“看不見的手”其實(shí)是經(jīng)濟(jì)領(lǐng)域的涌現(xiàn)現(xiàn)象，可以由涌現(xiàn)計(jì)算模型和算法進(jìn)行預(yù)測(cè)。智能涌現(xiàn)計(jì)算與經(jīng)濟(jì)學(xué)的交叉將有利于更好地洞察人類市場(chǎng)互動(dòng)行為的本質(zhì)[9]。

1.4 人工系統(tǒng)中的涌現(xiàn)現(xiàn)象

通信網(wǎng)、交通網(wǎng)等許多人工構(gòu)建的系統(tǒng)中也存在著涌現(xiàn)現(xiàn)象[10-14]。比如計(jì)算機(jī)網(wǎng)絡(luò)中數(shù)據(jù)包傳輸?shù)膿砣F(xiàn)象，交通系統(tǒng)中的交通堵塞，人工多主體模型表現(xiàn)出來的與生物啟發(fā)原型相似的各種涌現(xiàn)行為等。

Christie P[15-16]等對(duì)人為建造的復(fù)雜系統(tǒng)—計(jì)算機(jī)網(wǎng)絡(luò)的涌現(xiàn)特性進(jìn)行了研究，他們用分?jǐn)?shù)維描述了計(jì)算機(jī)互聯(lián)網(wǎng)的涌現(xiàn)集群特性，對(duì)最短連線問題進(jìn)行了研究，定義維度的倒數(shù)為幾何溫度Ti，分析表明系統(tǒng)在Ti約為0.5時(shí)會(huì)發(fā)生相變。而以計(jì)算機(jī)網(wǎng)絡(luò)為平臺(tái)，還誕生了類似BitTorrent的分布式系統(tǒng)，雖不存在中心控制，看似處于“無政府狀態(tài)”，但系統(tǒng)運(yùn)作良好且具有很好的魯棒性，其工作過程中存在大量涌現(xiàn)現(xiàn)象值得研究和借鑒。

在圖象數(shù)據(jù)庫這樣的人工系統(tǒng)中亦存在涌現(xiàn)現(xiàn)象。Santini S等[17]發(fā)現(xiàn)在圖象數(shù)據(jù)庫中特定圖像的語義是一種涌現(xiàn)現(xiàn)象。他們認(rèn)為圖像本身并不具有固有的內(nèi)在含義，而是將它們置于由其他圖像構(gòu)成的上下文環(huán)境中并在用戶互動(dòng)中涌現(xiàn)產(chǎn)生的，并據(jù)此提出了一種圖像操作與配置接口模型，使得用戶不但可以對(duì)單個(gè)圖像進(jìn)行操作也可以對(duì)圖像之間的關(guān)系進(jìn)行操作和定義，從而讓圖像可以在互動(dòng)中產(chǎn)生涌現(xiàn)語義。

人為構(gòu)建的機(jī)器人系統(tǒng)中亦存在涌現(xiàn)現(xiàn)象，可以利用其進(jìn)行機(jī)器人的智能化控制。Shimizu M等[18]對(duì)一種名為Slimebot的機(jī)器人系統(tǒng)進(jìn)行了研究，這個(gè)系統(tǒng)由多個(gè)相同的模塊化的小機(jī)器人組成，根據(jù)環(huán)境的不同在分布式算法的控制下相互作用組成不同的形態(tài)。實(shí)驗(yàn)表明，在基于涌現(xiàn)現(xiàn)象的算法作用下，可以在保證系統(tǒng)連貫性的情況下對(duì)機(jī)器人的形態(tài)進(jìn)行實(shí)時(shí)控制。Lee S I等[19]開發(fā)了一種基于遺傳算法的模糊邏輯控制器用于控制移動(dòng)機(jī)器人，并用內(nèi)部模型的狀態(tài)轉(zhuǎn)換圖分析了控制器的行為。實(shí)驗(yàn)結(jié)果表示通過進(jìn)化可以獲得恰當(dāng)?shù)目刂撇呗?，并且在所獲得的模糊規(guī)則集的互相作用下，機(jī)器人會(huì)表現(xiàn)出涌現(xiàn)行為。

硬件技術(shù)的發(fā)展使構(gòu)建大規(guī)模的無線傳感器網(wǎng)絡(luò)成為可能，單個(gè)傳感器體積大大減小，功耗降低，價(jià)格也越來越便宜。在大量智能微終端構(gòu)成的智能微塵中多個(gè)傳感器之間的局部作用會(huì)產(chǎn)生通信與合作，節(jié)點(diǎn)失效與網(wǎng)絡(luò)的魯棒性等許多涌現(xiàn)現(xiàn)象值得進(jìn)行深入的研究[20-22]。

對(duì)于人工系統(tǒng)中的涌現(xiàn)現(xiàn)象進(jìn)行研究，一方面可以更加了解系統(tǒng)的運(yùn)作方式和演化動(dòng)力學(xué)過程；一方面可以運(yùn)用涌現(xiàn)現(xiàn)象中存在的規(guī)律，對(duì)系統(tǒng)進(jìn)行控制和優(yōu)化，提升系統(tǒng)的性能。

2 涌現(xiàn)計(jì)算概述

2.1 涌現(xiàn)計(jì)算與涌現(xiàn)現(xiàn)象之間的關(guān)系，涌現(xiàn)計(jì)算的基本定義和特點(diǎn)

在自然系統(tǒng)、社會(huì)系統(tǒng)和人工系統(tǒng)中，普遍存在著涌現(xiàn)現(xiàn)象[23]。可以通過多主體的方法來對(duì)這些系統(tǒng)及其中存在的涌現(xiàn)現(xiàn)象進(jìn)行摸擬。例如蟻群、蜂群、鳥群及菌落等生物系統(tǒng)中便存在聚集，遷移，合作覓食等眾多涌現(xiàn)行為和現(xiàn)象，可以使用計(jì)算機(jī)對(duì)其進(jìn)行模擬[24-26]。對(duì)蟻群的模擬導(dǎo)致了蟻群算法的產(chǎn)生，對(duì)蜂群的模擬則是構(gòu)建蜂群算法的基礎(chǔ)。具有類似的合作覓食行為的群體稱為社會(huì)覓食昆蟲，它們可抽象為一種多主體系統(tǒng)，要實(shí)現(xiàn)合作覓食，需要群體在具有內(nèi)部凝聚力的同時(shí)對(duì)環(huán)境刺激保持恰當(dāng)?shù)捻憫?yīng)。Liu Y F等[27]將凝聚力表征為一種穩(wěn)定屬性使得即使在系統(tǒng)中存在因檢測(cè)其他主體位置和速度以及食物源的位置時(shí)存在的不確定性而帶來的噪聲情況下，局部主體的行為依然可以在整體上涌現(xiàn)出合作覓食的行為。他們的實(shí)驗(yàn)結(jié)果定量證實(shí)了在某種意義上合作覓食優(yōu)于個(gè)體覓食，并明晰了局體主體的相互作用和群體涌現(xiàn)行為之間的聯(lián)系。仿真模型在實(shí)驗(yàn)中表現(xiàn)出了復(fù)雜而有序的群體行為，與真實(shí)的生物群體在噪聲環(huán)境中表現(xiàn)出的行為非常相似。

同時(shí)需要注意到的是，一方面，涌現(xiàn)出來的現(xiàn)象并不一定總是我們所期望的，比如在神經(jīng)系統(tǒng)中，癲癇癥狀也是一種大量神經(jīng)元相互作用下的涌現(xiàn)行為[28]，但并不是我們所期望的，反而是需要想辦法消除的；另一方面，所需要求解的問題并不一定總具有顯式的多主體結(jié)構(gòu)。因此，涌現(xiàn)現(xiàn)象或?qū)τ楷F(xiàn)現(xiàn)象的模擬并不完全等同于涌現(xiàn)計(jì)算。為了利用涌現(xiàn)現(xiàn)象對(duì)問題進(jìn)行求解，首先需要對(duì)自然中存在的某些復(fù)雜系統(tǒng)及涌現(xiàn)現(xiàn)象進(jìn)行抽象并建立相應(yīng)的多主體模型；接下來需要對(duì)模型的特性進(jìn)行研究并對(duì)其進(jìn)行修正和控制，以使其可以產(chǎn)生所需要的涌現(xiàn)現(xiàn)象與模式；最后，對(duì)于某個(gè)具體的待求解的問題，需要將它映射到某一種建立好的多主體模型中，這樣才可能利用多主體系統(tǒng)的涌現(xiàn)現(xiàn)象對(duì)問題進(jìn)行求解，這個(gè)過程便是涌現(xiàn)計(jì)算。涌現(xiàn)計(jì)算具有去中心化，并行運(yùn)算的特點(diǎn)，而且具有黑箱特性，往往不需要對(duì)所求解問題進(jìn)行精確的數(shù)學(xué)建模，在許多復(fù)雜問題的求解上具有一定優(yōu)勢(shì)。

值得注意的是，雖然涌現(xiàn)計(jì)算是一種“自底向上”的算法，一定的局部規(guī)則會(huì)產(chǎn)生什么樣的涌現(xiàn)現(xiàn)象往往難以預(yù)測(cè)，而近年這一問題更具難度的逆問題——即給定一個(gè)期望產(chǎn)生的涌現(xiàn)現(xiàn)象，那么系統(tǒng)中的主體應(yīng)該遵循什么樣的局部規(guī)則才會(huì)導(dǎo)致這一特定涌現(xiàn)現(xiàn)象的產(chǎn)生—也得到了注意和研究[29-31]。這將有利于增加我們對(duì)涌現(xiàn)現(xiàn)象的認(rèn)識(shí)深度和控制能力，具有一定的實(shí)用價(jià)值。

綜上，我們可以認(rèn)為涌現(xiàn)計(jì)算是由一系列獨(dú)立計(jì)算處理進(jìn)程并行合作構(gòu)成的計(jì)算過程的總體，由低等級(jí)計(jì)算進(jìn)程之間依照特定規(guī)則集進(jìn)行相互作用而構(gòu)成高等級(jí)計(jì)算過程，實(shí)現(xiàn)可預(yù)計(jì)的總體功能，不受任何形式的全局控制，以局部作用產(chǎn)生的涌現(xiàn)現(xiàn)象作為計(jì)算結(jié)果，并能夠在演化過程中實(shí)現(xiàn)自身穩(wěn)定和收斂。

圖靈機(jī)數(shù)學(xué)模型奠定了現(xiàn)代計(jì)算機(jī)科學(xué)的理論基礎(chǔ)，它使用一個(gè)讀寫頭進(jìn)行工作，每個(gè)時(shí)刻只完成一步操作。以圖靈機(jī)為基本模型的傳統(tǒng)計(jì)算模式也多采用串行的工作模式，雖然在原則上能夠模擬一切運(yùn)算，但是在遇到類似NP難問題這樣復(fù)雜度很高的問題時(shí)，由于求解時(shí)間隨問題規(guī)?？焖僭鲩L，實(shí)際的計(jì)算求解變得不再可行。與大多數(shù)傳統(tǒng)計(jì)算模式的串行工作方式不同，涌現(xiàn)計(jì)算采用分布式的并行運(yùn)算模式，且在涌現(xiàn)計(jì)算中不存在中心控制，而主要依賴個(gè)體之間的局部作用來在整體上涌現(xiàn)出計(jì)算結(jié)果，這些特點(diǎn)使得涌現(xiàn)計(jì)算模式能夠在可接受的時(shí)間內(nèi)為一些無法使用傳統(tǒng)計(jì)算模式求解的問題提供可接受的解。因此，涌現(xiàn)計(jì)算是傳統(tǒng)計(jì)算模式很好的補(bǔ)充，為計(jì)算問題提供了一種新的求解方法和途徑。

2.2 一種涌現(xiàn)計(jì)算模型：元胞自動(dòng)機(jī)

元胞自動(dòng)機(jī)(亦稱為細(xì)胞自動(dòng)機(jī))是一種離散模型，最早由馮·諾依曼在1950年為模擬生物細(xì)胞的自我復(fù)制而提出。此后，S.Wolfram對(duì)初等元胞機(jī)256種規(guī)則所產(chǎn)生的模型進(jìn)行了深入研究，并用熵來描述其演化行為，將元胞自動(dòng)機(jī)分為平穩(wěn)型、周期型、混沌型和復(fù)雜型。

一個(gè)標(biāo)準(zhǔn)的元胞自動(dòng)機(jī)(A)由元胞、元胞狀態(tài)、鄰域和狀態(tài)更新規(guī)則構(gòu)成。可用式(1)來表示

A=(L,d,S,N,f)

(1)

其中，L為元胞空間；d為元胞自動(dòng)機(jī)內(nèi)元胞空間的維數(shù)；S為元胞有限的、離散的狀態(tài)集合；N為某個(gè)鄰域內(nèi)所有元胞的集合；f為局部映射或局部規(guī)則。

圖1 傳統(tǒng)元胞自動(dòng)機(jī)的鄰域定義方式

圖2 基于網(wǎng)絡(luò)的元胞鄰域定義

元胞空間是元胞所分布的空間網(wǎng)點(diǎn)的集合。傳統(tǒng)元胞自動(dòng)機(jī)的鄰域定義方式有Von Neumann鄰近和Moore型鄰近兩種，如圖1所示。近來則發(fā)展出了類似于網(wǎng)絡(luò)連接的鄰居定義方式，如圖2所示，這樣元胞的鄰居將不被限定于其位置的附近，從而在很大程度上拓展了其結(jié)構(gòu)復(fù)雜性，可能產(chǎn)生更復(fù)雜多樣的涌現(xiàn)現(xiàn)象，具有更強(qiáng)的信息處理、問題表征和求解的能力。如宋玉蓉、蔣國平突破了元胞自動(dòng)機(jī)的傳統(tǒng)鄰域定義方式，采用網(wǎng)絡(luò)的鄰接矩陣A直接定義各元胞鄰居關(guān)系，從而可以使用元胞自動(dòng)機(jī)模型對(duì)諸如Internet,WWW, P2P 和E-mail 等信息技術(shù)網(wǎng)絡(luò)中節(jié)點(diǎn)交互具有全局特性的對(duì)象進(jìn)行仿真研究[32]。理論上元胞空間在各個(gè)維向上是無限延伸的，為能夠在計(jì)算機(jī)上實(shí)現(xiàn)定義了邊界條件，包括周期型、反射型和定值型。

一個(gè)元胞通常在一個(gè)時(shí)刻只有取自一個(gè)有限集合的一種狀態(tài)，例如{0,1}。元胞狀態(tài)可以代表個(gè)體的態(tài)度，特征，行為等。在空間上與元胞相鄰的細(xì)胞稱為鄰元，所有鄰元組成鄰域。

元胞自動(dòng)機(jī)是一種涌現(xiàn)計(jì)算的統(tǒng)一框架，它是一種由在局部轉(zhuǎn)化規(guī)則控制下逐代進(jìn)化的細(xì)胞陣列構(gòu)成的離散系統(tǒng)。很多涌現(xiàn)計(jì)算的仿真研究都借助了元胞自動(dòng)機(jī)方法，因?yàn)樵詣?dòng)機(jī)是一個(gè)具有簡單構(gòu)造但產(chǎn)生復(fù)雜自組織行為的離散動(dòng)力學(xué)系統(tǒng)，它能夠有效地克服平均場(chǎng)方法建立的微分方程模型因只能反映同步行為的平均趨勢(shì)而只適合對(duì)同步行為作整體預(yù)測(cè)的局限性，也能克服基于馬氏鏈建立的隨機(jī)模型缺乏空間概念、模型復(fù)雜、不適合描述同步行為動(dòng)態(tài)演化的特征。由于這種通用性，元胞自動(dòng)機(jī)模型在涌現(xiàn)計(jì)算的諸多不同領(lǐng)域得到了廣泛應(yīng)用。Simons N R S等[33]利用元胞自動(dòng)機(jī)來描述二維電磁場(chǎng)問題，并對(duì)一維平面波在理想矩形波導(dǎo)柱中的傳播與反射進(jìn)行了求解。Mamei M, Roli A等[34]對(duì)受擾動(dòng)的細(xì)胞自動(dòng)機(jī)進(jìn)行了研究，發(fā)現(xiàn)在系統(tǒng)不受擾動(dòng)時(shí)某些特定行為并不會(huì)涌現(xiàn)出來，此類宏觀行為常在普適計(jì)算中涌現(xiàn)，值得進(jìn)一步研究、控制和利用。

作為一種計(jì)算模型，元胞自動(dòng)機(jī)可以在普通計(jì)算機(jī)上實(shí)現(xiàn)，也可以使用專用的電路實(shí)現(xiàn)。它已被證明是一高效的VLSI(超大規(guī)模集成電路)體系結(jié)構(gòu)。量子元胞自動(dòng)機(jī)是一種具有很好前景的涌現(xiàn)技術(shù)的納米電路實(shí)現(xiàn)，它具有很高的集成度、切換頻率和很低的功耗。元胞自動(dòng)機(jī)的量子元胞自動(dòng)機(jī)實(shí)現(xiàn)，不僅推動(dòng)已開發(fā)出來的元胞自動(dòng)機(jī)系統(tǒng)向納米時(shí)代升級(jí)，同時(shí)也大大提高了其性能[35]。這為涌現(xiàn)計(jì)算的實(shí)現(xiàn)提供了更強(qiáng)有力的計(jì)算平臺(tái)。

涌現(xiàn)計(jì)算的確定和元胞自動(dòng)機(jī)的通用性問題在過去三十年里得到了很好的解決，而在計(jì)算機(jī)科學(xué)和非線性科學(xué)的邊界上，神奇的涌現(xiàn)現(xiàn)象會(huì)在哪里出現(xiàn)這一問題至今還有待進(jìn)一步探索。Sapin E等[36]提出未來的工作可以對(duì)所有已發(fā)現(xiàn)的元胞自動(dòng)機(jī)進(jìn)行評(píng)估，計(jì)算出Langtons lamda等規(guī)則參數(shù)。以所有實(shí)現(xiàn)“與門”功能的元胞自動(dòng)機(jī)為例，它們可能有相似的參數(shù)值，這也許可以回答計(jì)算通用性的邊界在哪里，有助于更好地理解局部規(guī)則作用下復(fù)雜系統(tǒng)中的涌現(xiàn)計(jì)算。

2.3 涌現(xiàn)計(jì)算與群集智能

群集智能是指眾多行為簡單的個(gè)體相互作用過程中涌現(xiàn)產(chǎn)生的整體智能行為。群集智能模型使用一組相互之間可以進(jìn)行直接通信或者間接通信的主體合作進(jìn)行分布式的問題求解。蟻群算法便是群集智能的典型代表之一。此外，根據(jù)蟻群的勞動(dòng)分工和墓地構(gòu)造等現(xiàn)象提出的一系列模型和算法，以及Kennedy 等[36]通過觀察鳥群的協(xié)作覓食活動(dòng)開發(fā)的粒子群優(yōu)化方法(Particle Swarm Optimization, PSO) 也都屬于群集智能的范疇。目前群集智能包括蟻群優(yōu)化方法ACO和粒子群優(yōu)化方法PSO兩個(gè)大類，主要用于復(fù)雜問題求解。智能行為可以認(rèn)為是多個(gè)主體互動(dòng)而產(chǎn)生的一種涌現(xiàn)現(xiàn)象。群集智能正是簡單的主體通過交互作用所表現(xiàn)出的不可預(yù)見的宏觀智能行為的特性，這種群體層面表現(xiàn)出的智能行為是一種涌現(xiàn)現(xiàn)象，因此群集智能屬于涌現(xiàn)計(jì)算范疇，是涌現(xiàn)計(jì)算中重要的組成部分?？梢哉J(rèn)為涌現(xiàn)計(jì)算是一種產(chǎn)生群集智能的重要途徑和方法。目前，群集智能的建模工具包括動(dòng)力學(xué)建模、元胞自動(dòng)機(jī)、人工神經(jīng)網(wǎng)絡(luò)、遺傳算法、蟻群算法和粒子群算法等[37]。它們亦都屬于涌現(xiàn)計(jì)算的具體實(shí)現(xiàn)算法。

3 涌現(xiàn)計(jì)算中的若干關(guān)鍵問題

涌現(xiàn)計(jì)算中存在涌現(xiàn)模型映射、自組織、同步等關(guān)鍵問題，這些問題之間互相交疊，相互關(guān)聯(lián)，共同影響著涌現(xiàn)計(jì)算的過程和結(jié)果。

3.1 向涌現(xiàn)計(jì)算模型的映射

目前常用的涌現(xiàn)計(jì)算模型有元胞自動(dòng)機(jī)、螞蟻算法、蜂群算法、神經(jīng)網(wǎng)絡(luò)、遺傳算法等。在進(jìn)行具體問題的求解時(shí)，首先需要做的就是要完成從具體問題到涌現(xiàn)計(jì)算模型的映射。要將需求解的問題和條件在涌現(xiàn)計(jì)算模型中表達(dá)出來，并進(jìn)行相關(guān)的定義以便對(duì)計(jì)算所得到的涌現(xiàn)結(jié)果進(jìn)行解釋和翻譯，轉(zhuǎn)化為實(shí)際問題的解。

以元胞自動(dòng)機(jī)為例，在求解工程設(shè)計(jì)中的連續(xù)結(jié)構(gòu)拓?fù)鋬?yōu)化問題時(shí)，便需要建立元胞自動(dòng)機(jī)和結(jié)構(gòu)有限元之間的映射關(guān)系，以利用元胞自動(dòng)機(jī)完成連續(xù)結(jié)構(gòu)涌現(xiàn)計(jì)算[38]。文獻(xiàn)[38]中所提到的連續(xù)結(jié)構(gòu)拓?fù)鋬?yōu)化是在設(shè)計(jì)空間、支撐與載荷條件和某些工藝設(shè)計(jì)等受限條件下，確定結(jié)構(gòu)構(gòu)件之間的相互連接方式，結(jié)構(gòu)內(nèi)有無孔洞、孔洞的數(shù)量、位置等拓?fù)湫问剑菇Y(jié)構(gòu)能將外載荷傳遞到支座，同時(shí)使結(jié)構(gòu)的某些性能指標(biāo)達(dá)到最優(yōu)。在使用元胞自動(dòng)機(jī)模型進(jìn)行涌現(xiàn)計(jì)算求解時(shí)，首先要用規(guī)則形狀的單元進(jìn)行連續(xù)結(jié)構(gòu)的網(wǎng)格劃分，然后用有限元方法計(jì)算在給定載荷和約束條件下的局部應(yīng)變能密度，再將上述網(wǎng)格映射為元胞自動(dòng)機(jī)的進(jìn)化環(huán)境，然后要利用“比例—積分—微分”控制原理和滿應(yīng)力設(shè)計(jì)準(zhǔn)則重構(gòu)基于應(yīng)變能的元胞局部進(jìn)化規(guī)則，通過元胞進(jìn)化得到單元密度變化系數(shù)，從而得到新的設(shè)計(jì)域，重復(fù)上述過程直到進(jìn)化出滿足收斂條件的連續(xù)結(jié)構(gòu)的拓?fù)湫问健?/p>

圖3 利用螞蟻算法模型進(jìn)行路徑求解的原理示意圖

又例如，當(dāng)使用螞蟻算法求解旅行商問題(Traveling Salesman Problem, TSP)時(shí)，首先需要將城鎮(zhèn)映射為螞蟻算法中的圖的結(jié)點(diǎn)，將城鎮(zhèn)之間的路程映射為結(jié)點(diǎn)之間的連接權(quán)。假設(shè)在初始狀態(tài)，所有螞蟻被放在不同的節(jié)點(diǎn)上，每只螞蟻路由表的第一項(xiàng)是其起始節(jié)點(diǎn)。每只螞蟻按某種算法根據(jù)信息素和距離信息以一定概率選擇一個(gè)目的結(jié)節(jié)并向其移動(dòng)，當(dāng)?shù)M(jìn)行到一定程度時(shí)，所有螞蟻都完成了旅行，他們的路由表會(huì)被裝滿，這時(shí)對(duì)每只螞蟻的路由信息以某種方式進(jìn)行評(píng)估可以得到一條生成的最短路徑。這個(gè)過程可反復(fù)執(zhí)行直到達(dá)到最大次數(shù)限制或所有螞蟻都使用同一路徑的時(shí)候。其求解最短路徑的示意圖如圖3所示。這樣便利用螞蟻算法模型涌現(xiàn)計(jì)算得到了TSP問題的解[39]。

對(duì)所求解問題進(jìn)行涌現(xiàn)計(jì)算模型的映射，要求設(shè)計(jì)者熟悉所求解問題的結(jié)構(gòu)，同時(shí)了解涌現(xiàn)計(jì)算模型的結(jié)構(gòu)和計(jì)算特點(diǎn)，在計(jì)算前需要對(duì)問題進(jìn)行表征，并在獲得涌現(xiàn)計(jì)算的結(jié)果后對(duì)其進(jìn)行解釋和轉(zhuǎn)化。涌現(xiàn)計(jì)算模型中各個(gè)構(gòu)建的屬性、它們所處的環(huán)境及它們之間作用規(guī)則所代表的意義都是人工指定的，這需要人工參與涌現(xiàn)計(jì)算的過程，并且對(duì)于每一個(gè)具體的問題都需要設(shè)計(jì)一個(gè)獨(dú)特的涌現(xiàn)計(jì)算模型。而我們知道，生物神經(jīng)系統(tǒng)在進(jìn)行信息處理時(shí)具有某種通用性，類似于一個(gè)“黑箱”系統(tǒng)，構(gòu)成涌現(xiàn)計(jì)算系統(tǒng)的神經(jīng)元和它們之間的作用規(guī)則是相對(duì)獨(dú)立的，并不受外部環(huán)境的直接影響，這樣一個(gè)系統(tǒng)僅通過傳感系統(tǒng)和執(zhí)行系統(tǒng)與外界進(jìn)行交互，從某種程度上來說人類的神經(jīng)系統(tǒng)是一個(gè)具有通用性的涌現(xiàn)計(jì)算系統(tǒng)。借鑒腦科學(xué)的研究成果，也發(fā)展出了類似的涌現(xiàn)計(jì)算模型。

如Juyang Weng等[40]就構(gòu)建了這樣一種模型，它由感知器、啟發(fā)式代理和執(zhí)行器構(gòu)成，其結(jié)構(gòu)如圖4所示。啟發(fā)式代理由一些相互之間在啟發(fā)式算法下相互作用的單元構(gòu)成，與使用符號(hào)表征時(shí)處理單元內(nèi)部環(huán)境對(duì)外部環(huán)境是開放的不同，它們被限定在一個(gè)相對(duì)獨(dú)立的內(nèi)部環(huán)境的結(jié)構(gòu)中，與外界環(huán)境之間由一個(gè)被稱為“頭蓋骨”的結(jié)構(gòu)相互隔離，僅通過感知器和執(zhí)行器與外部環(huán)境進(jìn)行交互進(jìn)行涌現(xiàn)表征和計(jì)算。啟發(fā)式代理在“出生”后能不需要人工直接對(duì)其進(jìn)行定義和修改，通過交互式的學(xué)習(xí)來獲得針對(duì)各種不同任務(wù)的技能，所以不必針對(duì)每一個(gè)具體任務(wù)進(jìn)行映射，具有一定通用性。

圖4 一種涌現(xiàn)計(jì)算模型

3.2 自組織

自組織是指某一系統(tǒng)中自發(fā)形成的時(shí)空有序結(jié)構(gòu)或狀態(tài)。它是一種在沒有中心控制(沒有組織者或其他系統(tǒng)之外的設(shè)計(jì))、沒有完全信息的條件下，僅僅通過微觀個(gè)體的局部相互作用導(dǎo)致的系統(tǒng)全局結(jié)構(gòu)的涌現(xiàn)。自下而上、自發(fā)性、涌現(xiàn)性是自組織必備的和重要的特征。自組織有3個(gè)主要特性：涌現(xiàn)、自適應(yīng)、進(jìn)化。涌現(xiàn)是一種由系統(tǒng)各組元之間的相互作用而形成的全局現(xiàn)象。適應(yīng)性自組織系統(tǒng)通過自下而上的涌現(xiàn)行為處理干擾的存在和對(duì)環(huán)境變化作出自動(dòng)的適應(yīng)性改變以維護(hù)系統(tǒng)的穩(wěn)定。進(jìn)化是自組織系統(tǒng)涌現(xiàn)和適應(yīng)性綜合作用的結(jié)果。自組織現(xiàn)象在自然與人工系統(tǒng)中普遍存在。

自組織是一個(gè)自發(fā)產(chǎn)生的從無組織(或欠組織)到有組織的過程，對(duì)應(yīng)著系統(tǒng)的有序度的增加[41]，這使得系統(tǒng)能夠獲得時(shí)間、空間或功能上的結(jié)構(gòu)以適應(yīng)環(huán)境，所獲得的這種適應(yīng)性結(jié)構(gòu)便可視為涌現(xiàn)計(jì)算得到的解。涌現(xiàn)計(jì)算利用了自組織的適應(yīng)性，但有序度的過度增加則意味著系統(tǒng)的僵化和環(huán)境適應(yīng)性的下降[42]，因此在涌現(xiàn)計(jì)算中系統(tǒng)的有序度應(yīng)該維持在一定范圍。有序度過低則無法表現(xiàn)出適應(yīng)性，對(duì)應(yīng)著計(jì)算無法收斂得到有效的解；而過高則表現(xiàn)出僵化特性無法再對(duì)新的輸入作出反應(yīng)，涌現(xiàn)計(jì)算中的“早熟”現(xiàn)象便是有序度過高的表現(xiàn)。因此涌現(xiàn)計(jì)算中的自組織應(yīng)在有軼序與混沌之間取得平衡，即處于混沌的邊緣。這時(shí)系統(tǒng)將同時(shí)具有有效結(jié)構(gòu)和環(huán)境適應(yīng)性。

那么自組織會(huì)在什么樣的條件下發(fā)生，又是如何發(fā)生的呢？Nicolis G 等[43]認(rèn)為自組織發(fā)生在由非線性相互作用的元素組成的遠(yuǎn)離平衡態(tài)開放系統(tǒng)中，這意味著為涌現(xiàn)計(jì)算而構(gòu)建的人工系統(tǒng)是由互相之間具有非線性作用的多個(gè)元素構(gòu)成并且處于遠(yuǎn)離平衡態(tài)的混沌的邊緣。Nicolis G 等給出的為必要條件，相對(duì)寬泛，因?yàn)椴⒉皇撬蟹蔷€性作用都能產(chǎn)生自組織現(xiàn)象。Haken[44]則進(jìn)一步指出自組織中非線性作用的具體形式為競(jìng)爭性協(xié)同，即涌現(xiàn)計(jì)算系統(tǒng)中的多個(gè)主體之間同時(shí)存在競(jìng)爭與合作的關(guān)系。我們認(rèn)為系統(tǒng)開放并遠(yuǎn)離平衡態(tài)是自組織的必要條件，涌現(xiàn)計(jì)算系統(tǒng)開放于求解環(huán)境中進(jìn)行輸入物質(zhì)、能量和信息的交換，系統(tǒng)中各主體在競(jìng)爭性協(xié)同中實(shí)現(xiàn)正反饋機(jī)制，使系統(tǒng)中蘊(yùn)含的有序性得到增強(qiáng)與表達(dá)，進(jìn)而自組織形成某種特定的功能性結(jié)構(gòu)，從而涌現(xiàn)出所求解問題的解。

涌現(xiàn)計(jì)算的計(jì)算結(jié)果作為一種涌現(xiàn)現(xiàn)象，本身也是自組織的產(chǎn)物，計(jì)算結(jié)果的合理性和可用性表現(xiàn)出自組織過程對(duì)于外界環(huán)境的適應(yīng)性，而得到這一結(jié)果的過程即是系統(tǒng)自組織進(jìn)化的過程。因此作為復(fù)雜系統(tǒng)中的重要基本特征，自組織也是涌現(xiàn)計(jì)算中的關(guān)鍵問題之一，涌現(xiàn)計(jì)算中的自組織得到了很多研究和關(guān)注。Liu J M等[45]提出“面向自治的計(jì)算”，側(cè)重對(duì)復(fù)雜系統(tǒng)中實(shí)體中的自治行為建模及它們?cè)谶_(dá)成某一個(gè)特定目標(biāo)過程中的自組織現(xiàn)象進(jìn)行研究。社會(huì)系統(tǒng)的子系統(tǒng)之一——供應(yīng)鏈系統(tǒng)中，多企業(yè)主體在開放結(jié)構(gòu)下會(huì)在非線性互動(dòng)中自組織涌現(xiàn)出供應(yīng)鏈協(xié)作結(jié)構(gòu)和模式。李健，李剛等[46]采用多代理技術(shù)仿真對(duì)分散化供應(yīng)鏈中的自組織演化機(jī)制進(jìn)行了研究，研究表明演化對(duì)初始條件高度敏感，受外部環(huán)境和企業(yè)內(nèi)部機(jī)制因素控制，并存在著鎖定、路徑依賴和混沌等自組織系統(tǒng)特性。顧珊珊等[47]將車輛和信號(hào)燈視為主體，用元胞自動(dòng)機(jī)模擬動(dòng)態(tài)交通流，在激勵(lì)學(xué)習(xí)方法和遺傳算法的作用下，交通系統(tǒng)可以涌現(xiàn)出一定的動(dòng)態(tài)特征和規(guī)律，實(shí)現(xiàn)自組織控制。張嗣瀛[48]對(duì)自組織和自聚集現(xiàn)象進(jìn)行了研究，并給出了一個(gè)表達(dá)式對(duì)相關(guān)的規(guī)律性現(xiàn)象進(jìn)行概括與解釋，指出此式的多次重復(fù)對(duì)應(yīng)著重復(fù)的聚集和組織過程，是形成一類復(fù)雜系統(tǒng)結(jié)構(gòu)的基本規(guī)則。

3.3 同步

羅吉貴等[49]認(rèn)為，構(gòu)成復(fù)雜系統(tǒng)的基本單元都按照某種動(dòng)力學(xué)規(guī)律隨時(shí)間演化。由于基本單元之間存在相互作用，所以它們的演化并不是孤立的，而是在任何一個(gè)固定時(shí)刻的動(dòng)力學(xué)性質(zhì)表現(xiàn)出某種依賴關(guān)系，這種依賴關(guān)系即是同步。涌現(xiàn)計(jì)算的結(jié)果是復(fù)雜系統(tǒng)涌現(xiàn)出來的一種特征模式，可以視為復(fù)雜系統(tǒng)的斑圖，其反映了系統(tǒng)經(jīng)自組織過程而形成的某種有序性的結(jié)構(gòu)。在計(jì)算過程中，構(gòu)成計(jì)算模型的基本單元按照某種動(dòng)力學(xué)規(guī)律演化，它們之間按局部規(guī)則進(jìn)行相互作用，這使得它們的演化不是孤立的，動(dòng)力學(xué)性質(zhì)表現(xiàn)出某種依賴關(guān)系，即為同步關(guān)系。而斑圖正是同步關(guān)系在宏觀尺度上的表現(xiàn)，多樣化的同步導(dǎo)致了涌現(xiàn)現(xiàn)象即涌現(xiàn)計(jì)算結(jié)果的產(chǎn)生。因此涌現(xiàn)計(jì)算的基礎(chǔ)——涌現(xiàn)現(xiàn)象正是由同步種類的多樣性，尤其是廣義同步的存在而產(chǎn)生的，同步現(xiàn)象的研究對(duì)于涌現(xiàn)計(jì)算有著重要的意義。

同步現(xiàn)象是復(fù)雜系統(tǒng)中最早得到研究的問題之一。Winfree和Kuramoto分別提出了Winfree 模型和Kuramoto 模型，假定系統(tǒng)中每個(gè)個(gè)體具有相同的振動(dòng)周期，將同步問題轉(zhuǎn)化為相同步問題進(jìn)行研究[50-51]。2000年，Néda 等[52]研究了人群中的掌聲同步現(xiàn)象，通過對(duì)音樂廳里錄制的真實(shí)掌聲進(jìn)行分析，得出掌聲同步時(shí)周期加倍的結(jié)論，并借助Kuramoto模型進(jìn)行了理論解釋[53]。李德毅等[54]選取“掌聲響起來”作為初始狀態(tài)，以心理學(xué)中的“從眾心理”為基礎(chǔ)，利用認(rèn)知物理學(xué)中的云模型和數(shù)據(jù)場(chǎng)理論構(gòu)造了一個(gè)描述集體行為的非線性涌現(xiàn)模型，開發(fā)了涌現(xiàn)計(jì)算實(shí)驗(yàn)平臺(tái)，對(duì)音樂廳里掌聲的自發(fā)涌現(xiàn)機(jī)理進(jìn)行了分析并模擬了多樣化的掌聲同步的虛擬現(xiàn)實(shí)；進(jìn)一步，他們將聽眾群體視為一個(gè)復(fù)雜多代理網(wǎng)絡(luò)，分析了掌聲涌現(xiàn)同步的內(nèi)在關(guān)鍵因素，探討了領(lǐng)掌者如何影響涌現(xiàn)掌聲同步，領(lǐng)掌者分布的影響等問題，指出掌聲的涌現(xiàn)同步有路徑多樣化，不確定性和適應(yīng)性，掌聲同步研究所用的模型和方法也可為其他局部信息和局部控制下的復(fù)雜多主體網(wǎng)絡(luò)的集體行為研究提供借鑒[55]。同步現(xiàn)象在自然界的復(fù)雜系統(tǒng)中廣泛存在，比如在視覺皮層中便發(fā)現(xiàn)了長程同步現(xiàn)象，受此啟發(fā)，DeLiang Wang[56]提出了一種局部耦合神經(jīng)振蕩器模型，它可以涌現(xiàn)出與視皮層類似的全局同步現(xiàn)象，在知覺編組和模式劃分上具有全局連接神經(jīng)網(wǎng)絡(luò)模型所不具有的一些優(yōu)勢(shì)。Zhang Q J 等[57]考察帶有延遲結(jié)點(diǎn)的復(fù)雜動(dòng)態(tài)網(wǎng)絡(luò)，對(duì)適應(yīng)性反饋同步進(jìn)行了研究發(fā)現(xiàn)了全局指數(shù)同步的一些新條件，并進(jìn)行了仿真驗(yàn)證。對(duì)復(fù)雜網(wǎng)絡(luò)中的混沌同步進(jìn)行了研究，由理論分析通過數(shù)值仿真提出和驗(yàn)證了同步產(chǎn)生的條件，并指出當(dāng)耦合配置和內(nèi)部耦合矩陣滿足特定條件時(shí)，混沌同步是不可能實(shí)現(xiàn)的[58]。能夠正確獲知復(fù)雜系統(tǒng)中同步行為的發(fā)生對(duì)于自然及人工涌現(xiàn)現(xiàn)象的建模和研究具有深遠(yuǎn)的意義，Boulden S 等[59]在各種復(fù)雜網(wǎng)絡(luò)拓?fù)渖线\(yùn)行空間迭代囚徒困境并采用遺傳算法進(jìn)行了涌現(xiàn)行為的獲知，結(jié)果顯示僅有策略代價(jià)信息是不夠的，需要更多的信息來對(duì)同步行為進(jìn)行感知。

對(duì)于涌現(xiàn)、自組織和同步等復(fù)雜系統(tǒng)中關(guān)鍵主題的研究，將能夠幫助我們更好地認(rèn)識(shí)涌現(xiàn)現(xiàn)象發(fā)生的機(jī)理，從而控制涌現(xiàn)現(xiàn)象的產(chǎn)生和發(fā)展的方向，有利于在涌現(xiàn)計(jì)算中避免不需要或不希望的涌現(xiàn)現(xiàn)象的產(chǎn)生，獲得所需要的涌現(xiàn)現(xiàn)象，使涌現(xiàn)計(jì)算的過程更具可控性，提高涌現(xiàn)計(jì)算求解問題的能力。

4 涌現(xiàn)計(jì)算的典型應(yīng)用

4.1 工程系統(tǒng)中的涌現(xiàn)計(jì)算

許多涉及到眾多影響因素的復(fù)雜工程問題往往可以使用涌現(xiàn)計(jì)算得到很好的解決。

肖人彬等[38]采用基于元胞自動(dòng)機(jī)的連續(xù)結(jié)構(gòu)涌現(xiàn)模型計(jì)算了在不同溫度邊界條件和熱源分布情況下方形平板散熱的最優(yōu)拓?fù)浣Y(jié)構(gòu)，實(shí)現(xiàn)了基于涌現(xiàn)計(jì)算的自動(dòng)結(jié)構(gòu)設(shè)計(jì)，實(shí)驗(yàn)證明這是一種有效而高效的設(shè)計(jì)方法。汪鐳等[60-62]將涌現(xiàn)計(jì)算中的一種重要算法模型——人工神經(jīng)網(wǎng)絡(luò)應(yīng)用于自動(dòng)控制及傳動(dòng)系統(tǒng)領(lǐng)域，取得了良好的效果，此外他們還以反饋式神經(jīng)網(wǎng)絡(luò)和群體智能算法為基礎(chǔ)給出了自然計(jì)算理念統(tǒng)一的框架描述, 自然計(jì)算領(lǐng)域內(nèi)的相關(guān)群體智能算法表現(xiàn)出一種相對(duì)統(tǒng)一的智能計(jì)算模式，即涌現(xiàn)計(jì)算模式。

Dong J 等[63]報(bào)道了一種基于局部信息的交通分配(dynamic traffic assignment, DTA)模型，僅使用由地下傳感器收集的局部信息而非全局信息來做出通行和限制通行的決策。與其他DTA算法的仿真比較實(shí)驗(yàn)證明，這種算法具有魯棒性和高效性。在智能交通中亦使用到了涌現(xiàn)合作技術(shù)[64]。

涌現(xiàn)計(jì)算在智能控制系統(tǒng)中扮演著重要的角色。在復(fù)雜動(dòng)態(tài)系統(tǒng)的控制中，出現(xiàn)了越來越多的傳統(tǒng)控制理論所不能滿足的需求。這主要是由于問題的復(fù)雜性和環(huán)境的不確定性常常需要使用啟發(fā)式推理對(duì)以往的經(jīng)驗(yàn)進(jìn)行學(xué)習(xí)從而進(jìn)行與人類相似的決策。這時(shí)系統(tǒng)要通過學(xué)習(xí)積累關(guān)于問題的信息動(dòng)態(tài)地產(chǎn)生可接受的解。使用神經(jīng)網(wǎng)絡(luò)、模糊邏輯、遺傳算法等涌現(xiàn)計(jì)算方法可實(shí)現(xiàn)這樣的功能，它們經(jīng)常與傳統(tǒng)控制理論一起被用于構(gòu)建高性能的智能控制器[65]。在生產(chǎn)控制領(lǐng)域，傳統(tǒng)的中心控制連續(xù)信息處理方法也逐漸不能滿足快速變化的生產(chǎn)環(huán)境的需要，對(duì)于計(jì)算復(fù)雜、非線性和不確定的環(huán)境，亦需要使用基于涌現(xiàn)的多主體分布式智能控制方法[66]。

Arena P 等[67]將涌現(xiàn)計(jì)算用于有腿機(jī)器人的運(yùn)動(dòng)控制，通過使用模擬細(xì)胞神經(jīng)網(wǎng)絡(luò)的自組織涌現(xiàn)結(jié)果生成運(yùn)動(dòng)步法，并使用VLSI實(shí)現(xiàn)了基于模擬細(xì)胞神經(jīng)網(wǎng)絡(luò)的中樞模式發(fā)生器，實(shí)驗(yàn)結(jié)果證明了這種方法的適用性。在過去幾十年里，有腿機(jī)器人的高速動(dòng)態(tài)步伐得到了許多研究，但目前發(fā)表的研究從生物力學(xué)和工程角度上來說都未能充分地描述高速奔跑的動(dòng)力學(xué)特征并實(shí)現(xiàn)它。Krasny D P等[68]使用一種稱為基于集的隨機(jī)優(yōu)化的高效進(jìn)化算法來產(chǎn)生高速的步態(tài)。這個(gè)算法可以找到用來生成周期性軌跡的開環(huán)控制參數(shù)。測(cè)試了多種方法用來生成腿的周期軌跡，結(jié)合進(jìn)化搜索找到的聯(lián)合方案，實(shí)現(xiàn)了絞鏈連接的四足機(jī)器人在非均勻負(fù)重情況下的節(jié)能、自然和非受限的快速奔跑，出于比較目的，同時(shí)也實(shí)現(xiàn)了跳躍和慢跑。實(shí)驗(yàn)表明在最高可達(dá)10m/s的速度范圍內(nèi)實(shí)現(xiàn)了基礎(chǔ)步態(tài)顯示出來的涌現(xiàn)特性。這個(gè)模型可以實(shí)現(xiàn)在動(dòng)物身上觀察到的主要?jiǎng)恿W(xué)特征。在結(jié)構(gòu)簡單的機(jī)器人系統(tǒng)上也可以實(shí)現(xiàn)自然高效的移動(dòng)。涌現(xiàn)計(jì)算在認(rèn)知機(jī)器人中的應(yīng)用尤為引人注目。Paolo Arena等[69]基于生物啟發(fā)計(jì)算算法的時(shí)空非線性神經(jīng)陣列，使用簡單的距離、接觸和視覺傳感器作為輸入，讓機(jī)器人基于用例進(jìn)行認(rèn)知學(xué)習(xí)并產(chǎn)生能針對(duì)特定目標(biāo)的涌現(xiàn)行為，其系統(tǒng)結(jié)構(gòu)如圖5所示。機(jī)器人可以自行通過認(rèn)知過程涌現(xiàn)出完成某一目標(biāo)的解決方案，并在簡單傳感器所獲取的外部信息誘導(dǎo)下對(duì)外部環(huán)境產(chǎn)生響應(yīng)完成特定任務(wù)，圖6展示了機(jī)器人的結(jié)構(gòu)及其自動(dòng)生成的運(yùn)動(dòng)路徑。這種方法讓機(jī)器人可以處理事先不可預(yù)知的動(dòng)態(tài)變化的環(huán)境，而這在太空任務(wù)或我們的日常生活中都是非常常見的。

圖5 帶有傳感反饋的機(jī)器人系統(tǒng)框圖

圖6 機(jī)器人的結(jié)構(gòu)及其自動(dòng)涌現(xiàn)生成的運(yùn)動(dòng)路徑

Floreano D等[70]使用一個(gè)時(shí)間離散的迭代神經(jīng)網(wǎng)絡(luò)進(jìn)化算法控制一個(gè)實(shí)體的移動(dòng)機(jī)器人，通過在實(shí)驗(yàn)初期設(shè)置的一組約束條件，在無需預(yù)先進(jìn)行設(shè)定的情況下，機(jī)器人自動(dòng)涌現(xiàn)出了對(duì)電池充電器進(jìn)行定位并周期性回到充電器所在處進(jìn)行充電的行為。

Yong Li等[71]提出了一種正反饋HOPFIELD神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，具有類似于標(biāo)準(zhǔn)HOPFIELD方法的涌現(xiàn)特性，用于交叉開關(guān)切換控制，相比于包括標(biāo)準(zhǔn)HOPFIELD方法在內(nèi)的以前的方法，在計(jì)算時(shí)間和解的質(zhì)量上均具有優(yōu)勢(shì)。

除用于智能控制外，涌現(xiàn)計(jì)算還可應(yīng)用于語音和圖像信息處理[72]。楊淑瑩等[73]使用免疫貓群優(yōu)化算法實(shí)現(xiàn)了不依賴于初始碼書選取，魯棒性強(qiáng)且低語音識(shí)別誤差率的矢量量化碼書設(shè)計(jì)?；谟楷F(xiàn)計(jì)算的多核和結(jié)構(gòu)可重構(gòu)平臺(tái)不斷發(fā)展，視覺處理系統(tǒng)變得越來越復(fù)雜，性能也更加強(qiáng)大[74]。模仿人腦工作模式的涌現(xiàn)時(shí)域處理技術(shù)可用類似人腦的方式進(jìn)行視頻識(shí)別和文本處理。Weng J Y 等[40]的模型借鑒腦生理的研究成果，由感知器、啟發(fā)式代理和執(zhí)行器構(gòu)成，其結(jié)構(gòu)如圖7所示。有別于面向任務(wù)的內(nèi)部符號(hào)表征方法，它采用啟發(fā)式網(wǎng)絡(luò),通過感知器和執(zhí)行器與外部環(huán)境的交互自動(dòng)進(jìn)行涌現(xiàn)表征。啟發(fā)式代理被認(rèn)為限定在一個(gè)類似“頭蓋骨”的結(jié)構(gòu)中不受外界環(huán)境的直接影響，形成一個(gè)相對(duì)獨(dú)立的內(nèi)部環(huán)境，僅通過感知器和執(zhí)行器與外部環(huán)境進(jìn)行交互。啟發(fā)式代理在“出生”后能在不需要人來重新進(jìn)行啟發(fā)式程序的編程或直接對(duì)其進(jìn)行修改的情況下通過增量學(xué)習(xí)獲得針對(duì)各種不同任務(wù)的技能。

在智能房屋領(lǐng)域，涌現(xiàn)計(jì)算被用來進(jìn)行電力規(guī)劃與決策。帶有發(fā)電儲(chǔ)存和交易功能的智能房屋不再只是電網(wǎng)中一個(gè)無源的負(fù)載，而是有雙向的能量流入與流出。將智能房屋視為主體，可使用基于多主體的方法，結(jié)合當(dāng)前和預(yù)期的用電量、發(fā)電量和貯電量來自動(dòng)決定買入、存儲(chǔ)或是賣出電力資源，從而最小化其電費(fèi)賬單[75]。

圖7 感知器、啟發(fā)式代理和執(zhí)行器結(jié)構(gòu)模型

當(dāng)然，涌現(xiàn)計(jì)算并不一定都是在計(jì)算機(jī)上完成的。日本北海道大學(xué)的Tero 教授等[76]利用粘菌進(jìn)行涌現(xiàn)計(jì)算設(shè)計(jì)了一張連通東京及其附近城市的鐵路網(wǎng)。粘菌是一群裸露的無細(xì)胞壁多核的原生質(zhì)團(tuán)，它們可以通過連續(xù)的形變而緩慢移動(dòng)，當(dāng)這團(tuán)裸露的細(xì)胞在空間上遇到多個(gè)分散的食物源時(shí)，就會(huì)構(gòu)建起一些運(yùn)輸營養(yǎng)的通道。Tero教授等將一張東京以及附近城市的地圖作為粘菌生長的環(huán)境，在初始時(shí)刻，讓粘菌集中在地圖上的東京點(diǎn)，接著在地圖東京附近的城市放上粘菌喜歡吃的食物，然后讓這群粘菌在實(shí)驗(yàn)地圖上緩慢變形、游走。經(jīng)過一天多的時(shí)間，它們演化出了一張與現(xiàn)實(shí)的東京附近的地鐵網(wǎng)絡(luò)在結(jié)構(gòu)與形狀上均非常相似的營養(yǎng)運(yùn)輸網(wǎng)絡(luò)，如圖8所示。也就是說，使用粘菌進(jìn)行涌現(xiàn)計(jì)算完成了復(fù)雜而高效的軌道網(wǎng)絡(luò)運(yùn)輸系統(tǒng)的優(yōu)化設(shè)計(jì)工作。

4.2 社會(huì)系統(tǒng)中的涌現(xiàn)計(jì)算

在市場(chǎng)與經(jīng)濟(jì)系統(tǒng)[77-78]，社會(huì)技術(shù)系統(tǒng)[79]，科學(xué)與教育[80]、演藝圈、人際關(guān)系社團(tuán)[81-82]等社會(huì)系統(tǒng)中存在著大量的涌現(xiàn)現(xiàn)象，亦可以使用涌現(xiàn)計(jì)算來解決其中的很多問題。

Izumi K等[83]提出了一種人工市場(chǎng)方法，用基于主體的方法來進(jìn)行外匯市場(chǎng)的研究。用這種方法可以解釋市場(chǎng)中的峰值和重尾等涌現(xiàn)現(xiàn)象。通過采訪和問卷的方式來收集行業(yè)數(shù)據(jù)。調(diào)查顯示經(jīng)銷商在學(xué)習(xí)中的互動(dòng)與生物中的基因操作比較類似。使用基因算法建立了一個(gè)人工市場(chǎng)模型。這是一個(gè)由具有市場(chǎng)狀態(tài)內(nèi)部表征的agent組成的多agent系統(tǒng)。然后結(jié)合基本經(jīng)濟(jì)因素和政治新聞的真實(shí)數(shù)據(jù)集進(jìn)行了仿真。識(shí)別到了市場(chǎng)中的3個(gè)涌現(xiàn)現(xiàn)象，并推論這些涌現(xiàn)現(xiàn)象可以由因代理個(gè)體預(yù)測(cè)互動(dòng)和市場(chǎng)供需平衡形成的預(yù)測(cè)多樣性的相變來解釋。實(shí)際領(lǐng)域數(shù)據(jù)支持了仿真的結(jié)果。這種方法整合了實(shí)際工作與多代理模型，提供了市場(chǎng)中微觀與宏觀聯(lián)系的定量解釋。欒笑天等[84]使用元胞自動(dòng)機(jī)設(shè)計(jì)航空物流市場(chǎng)的演化模型，得到了航空物流市場(chǎng)的演化階段與細(xì)分市場(chǎng)特征的模擬結(jié)果，其模型能夠有效模擬各物流細(xì)分市場(chǎng)受不同階段影響因素的敏感度。Koritarov V S[85]使用計(jì)算社會(huì)學(xué)中基于主體的建模與仿真方法(Agent-Based Modeling and Simulation, ABMS)將電力市場(chǎng)作為一個(gè)復(fù)雜自適應(yīng)系統(tǒng)進(jìn)行了模擬與分析。這個(gè)仿真模型由代表電力市場(chǎng)中參與者的主體、代表主體存在和相互作用環(huán)境的互動(dòng)層以及代表時(shí)間層的計(jì)劃周期構(gòu)成。通過此模型可以有效地研究物理基礎(chǔ)設(shè)施(如發(fā)電站，電力傳輸系統(tǒng)等)和市場(chǎng)參與者的經(jīng)濟(jì)行為之間的復(fù)雜互動(dòng)行為。此外，涌現(xiàn)計(jì)算方法還被用來對(duì)電力客戶進(jìn)行分類[86]。龔小慶等[87-89]探討了固定環(huán)境中的穩(wěn)態(tài)涌現(xiàn)；對(duì)復(fù)雜系統(tǒng)在演化過程中所涌現(xiàn)出來的一種統(tǒng)計(jì)規(guī)律—Zipf律進(jìn)行了研究，證實(shí)了Zipf律與冪律分布的統(tǒng)計(jì)等價(jià)性；他們還從復(fù)雜系統(tǒng)的角度對(duì)經(jīng)濟(jì)系統(tǒng)進(jìn)行了研究，指出經(jīng)濟(jì)系統(tǒng)是一個(gè)具有分形特征的多層次的規(guī)則耦合關(guān)系網(wǎng)，其演化具有斷續(xù)平衡和路徑依賴的特征，經(jīng)濟(jì)系統(tǒng)中生態(tài)位的重疊導(dǎo)致外部性的產(chǎn)生，而制度的涌現(xiàn)和演化過程就是外部性的產(chǎn)生、轉(zhuǎn)換和平衡過程，這些關(guān)于經(jīng)濟(jì)系統(tǒng)中涌現(xiàn)現(xiàn)象的研究為涌現(xiàn)計(jì)算在經(jīng)濟(jì)領(lǐng)域中的應(yīng)用提供了理論支持。趙劍冬等[90]基于Agent的經(jīng)濟(jì)社會(huì)系統(tǒng)建模與仿真研究進(jìn)行了一種使用涌現(xiàn)計(jì)算方法ABMS研究經(jīng)濟(jì)系統(tǒng)的新嘗試，其建立的計(jì)算機(jī)仿真模型可以幫助分析影響產(chǎn)業(yè)集群發(fā)展的多個(gè)因素。

圖8 粘菌涌現(xiàn)計(jì)算結(jié)果與東京周邊鐵路網(wǎng)絡(luò)的對(duì)比圖

除經(jīng)濟(jì)系統(tǒng)外，涌現(xiàn)計(jì)算亦可用于軍事決策支持。計(jì)算紅軍(CRT)是一種基于仿真的優(yōu)化應(yīng)用，用以發(fā)現(xiàn)軍事策略(或工作計(jì)劃)中的不足之處。CRT的目的在于識(shí)別出那些表現(xiàn)出感興趣涌現(xiàn)現(xiàn)象的仿真模型。在CRT中使用的是海量多主體進(jìn)化算法。由于傳統(tǒng)CRT所使用的基于帕累托的算法會(huì)收斂于帕累托最優(yōu)，次優(yōu)的替代策略會(huì)被遺漏，從決策者的立場(chǎng)這限制了CRT的應(yīng)用，Zeng F C等[91]通過在海量多主體進(jìn)化算法中使用多樣化強(qiáng)化策略，有效提高解決多樣化問題的能力，增強(qiáng)了CRT用于輔助決策的能力。

對(duì)于大學(xué)課程時(shí)間表這樣人們所熟知的復(fù)雜規(guī)劃問題，亦可以使用涌現(xiàn)計(jì)算對(duì)其進(jìn)行求解。Lewis R等[92]提出了一種衡量種群多樣性和個(gè)體距離的方法，通過引入大量不同的適應(yīng)度函數(shù)，使用附加的局部搜索操作符對(duì)使用群基因算法進(jìn)行了改進(jìn)，用以求解上述問題取得了較好的效果。

針對(duì)更一般性的社會(huì)學(xué)命題，王飛躍等[93]采用人工社會(huì)模型，基于代理的建模、模擬和分析來進(jìn)行研究，指出通過涌現(xiàn)的方式，人工社會(huì)模型中可以方便地涌現(xiàn)出合作、調(diào)節(jié)、反饋、競(jìng)爭、沖突等復(fù)雜系統(tǒng)現(xiàn)象及它們之間的交互和轉(zhuǎn)換，展示了涌現(xiàn)計(jì)算在社會(huì)問題研究中的應(yīng)用潛力。

5 結(jié)語

計(jì)算能力的持續(xù)提高和對(duì)于復(fù)雜系統(tǒng)中涌現(xiàn)現(xiàn)象研究的不斷深入使得我們可以在計(jì)算機(jī)上使用多主體建模的方式對(duì)涌現(xiàn)現(xiàn)象進(jìn)行仿真和研究，并進(jìn)一步利用系統(tǒng)的涌現(xiàn)現(xiàn)象來高效求解一些使用傳統(tǒng)算法難以解決的問題。作為涌現(xiàn)計(jì)算的重要組成部分，群集智能方法已經(jīng)在多目標(biāo)優(yōu)化、數(shù)據(jù)分類、數(shù)據(jù)聚類、模式識(shí)別、電信QoS 管理、生物系統(tǒng)建模、流程規(guī)劃、信號(hào)處理、機(jī)器人控制、決策支持以及仿真和系統(tǒng)辯識(shí)等方面得到了廣泛的應(yīng)用。

初期使用較多的符號(hào)表征方法是面向任務(wù)的，需要理解此任務(wù)的人類設(shè)計(jì)者構(gòu)建用于表達(dá)此任務(wù)的特定外部環(huán)境，再通過涌現(xiàn)計(jì)算的方法得到特定結(jié)果。今后涌現(xiàn)計(jì)算將越來越多地借鑒神經(jīng)生物學(xué)的研究成果，由面向特定問題的人工符號(hào)表征轉(zhuǎn)為面向非特定問題的涌現(xiàn)表征。使用更復(fù)雜的更接近于生物神經(jīng)系統(tǒng)的模型，在內(nèi)部系統(tǒng)與外部環(huán)境的交互中進(jìn)行自動(dòng)的涌現(xiàn)表征實(shí)現(xiàn)啟發(fā)式涌現(xiàn)計(jì)算是未來的重要發(fā)展方向。系統(tǒng)在運(yùn)行中將在不需要人工重新進(jìn)行啟發(fā)式程序的編程或直接對(duì)其進(jìn)行修改的情況下通過增量學(xué)習(xí)獲得針對(duì)各種不同任務(wù)的技能。在新的更有效的計(jì)算范式得到發(fā)展的同時(shí)，以量子元胞自動(dòng)機(jī)為代表的針對(duì)特定涌現(xiàn)計(jì)算模式的專用硬件電路也將得到進(jìn)一步研究，從而為新的計(jì)算范式提供專用、更高效和具有更強(qiáng)計(jì)算能力的運(yùn)行支撐平臺(tái)。作為涌現(xiàn)計(jì)算重要通用模型的元胞自動(dòng)機(jī)也正向著更高維度、結(jié)構(gòu)更復(fù)雜的方向發(fā)展，以提供更強(qiáng)的表達(dá)和求解能力。隨著計(jì)算范式的完善和計(jì)算平臺(tái)的升級(jí)，涌現(xiàn)計(jì)算的應(yīng)用也將廣泛延伸至自然物理系統(tǒng)、生物系統(tǒng)和社會(huì)系統(tǒng)等各個(gè)領(lǐng)域，為規(guī)律發(fā)現(xiàn)和問題求解提供強(qiáng)有力的手段。新的涌現(xiàn)計(jì)算研究范式可能帶來傳統(tǒng)研究方法難以得到的新發(fā)現(xiàn)和解決問題的新方法。

對(duì)于涌現(xiàn)現(xiàn)象的深入研究將進(jìn)一步推動(dòng)涌現(xiàn)計(jì)算的發(fā)展，同時(shí)反過來為我們理解和掌控身邊世界的運(yùn)行提供更有效的工具。

[1]Wolfram S. Universality and complexity in cellular automata [J]. Physica D: Nonlinear Phenomena, 1984, 10(1): 1-35.

[2]Forrest S. Emergent computation: self-organizing, collective, and cooperative phenomena in natural and artificial computing networks: introduction to the proceedings of the ninth annual CNLS conference [J]. Physica D: Nonlinear Phenomena, 1990, 42(1): 1-11.

[3]Holland J H. Emergence: From Chaos to Order [M]. Redwood City: Oxford University Press, 2000.

[4]Kube C R, Bonabeau E. Cooperative transport by ants and robots [J]. Robotics and autonomous systems, 2000, 30(1): 85-101.

[5]Martin M, Chopard B, Albuquerque P. Formation of an ant cemetery: swarm intelligence or statistical accident? [J]. Future Generation Computer Systems, 2002, 18(7): 951-959.

[6]Chung J R, Choe Y. Emergence of memory in reactive agents equipped with environmental markers [J]. Autonomous Mental Development, IEEE Transactions on, 2011, 3(3): 257-271.

[7]Damiani C, Serra R, Villani M, et al. Cell-cell interaction and diversity of emergent behaviours [J]. Systems Biology, IET, 2011, 5(2): 137-144.[8]Tao Z, Xiao R, Wang L. Structure emergence in the evolution of social networks and its case study [J]. Procedia Computer Science, 2013, 17: 981-988.

[9]Seiffertt J, Wunsch D. Intelligence in markets: asset pricing, mechanism design, and natural computation [technology review] [J]. IEEE Computational Intelligence Magazine, 2008, 3(4): 27-30.

[10]Ha S Y, Ha T, Kim J H. Emergent behavior of a Cucker-Smale type particle model with nonlinear velocity couplings [J]. IEEE Transactions on Automatic Control, 2010, 55(7): 1679-1683.

[11]Park J, Kim H J, Ha S Y. Cucker-Smale flocking with inter-particle bonding forces [J]. IEEE Transactions on Automatic Control, 2010,55(11): 2617-2623.

[12]Finke J, Passino K M. Local agent requirements for stable emergent group distributions [J].IEEE Transactions on Automatic Control, 2011, 56(6): 1426-1431.

[13]Niazi M A, Hussain A. Sensing emergence in complex systems [J]. IEEE Sensors Journal, 2011, 11(10): 2479-2480.

[14]Tsilipanos K, Neokosmidis I, Varoutas D. A system of systems framework for the reliability assessment of telecommunications networks [J]. IEEE Systems Journal, 2013, 7(1): 114-124.

[15]Christie P. A fractal analysis of interconnection complexity [J]. Proceedings of the IEEE, 1993, 81(10): 1492-1499.

[16]Hales D, Patarin S. Computational sociology for systems" in the wild": the case of BitTorrent [J]. IEEE Distributed Systems Online, 2005, 6(7): 1-6.

[17]Santini S, Gupta A, Jain R. Emergent semantics through interaction in image databases [J]. IEEE Transactions on Knowledge and Data Engineering, 2001, 13(3): 337-351.

[18]Shimizu M, Ishiguro A, Kawakatsu T. Slimebot: a modular robot that exploits emergent phenomena[C]// Proceedings of the 2005 IEEE International Conference on Robotics & Automation, 2005: 2982-2987.

[19]Lee S I, Cho S B. Emergent behaviors of a fuzzy sensory-motor controller evolved by genetic algorithm [J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B Cybernetics, 2001, 31(6): 919-929.

[20]Kahn J M, Katz R H, Pister K S J. Emerging challenges: mobile networking for “smart dust” [J]. Journal of Communications and Networks, 2000, 2(3): 188-196.

[21]Kunniyur S S, Venkatesh S S. Threshold functions, node isolation, and emergent lacunae in sensor networks [J]. IEEE Transactions on Information Theory, 2006, 52(12): 5352-5372.

[22]Olascuaga-Cabrera J G, Lopez-Mellado E, Mendez-Vazquez A, et al. A self-organization algorithm for robust networking of wireless devices [J]. IEEE Sensors Journal, 2011, 11(3): 771-780.

[23]Charles P. Emergent collectives [J]. IEEE Internet Computing, 2011, 15(5): 99-102.

[24]Gravagne I A, Marks R J. Emergent behaviors of protector, refugee, and aggressor swarms [J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B Cybernetics, 2007, 37(2): 471-476.

[25]Cucker F, Smale S. Emergent behavior in flocks [J].IEEE Transactions on Automatic Control, 2007, 52(5): 852-862.

[26]Dressler F, Suda T, Carreras I, et al. Guest editorial bio-inspired networking [J].IEEE Journal on Selected Areas in Communications, 2010, 28(4): 521-523.

[27]Liu Y, Passino K M. Stable social foraging swarms in a noisy environment [J]. IEEE Transactions on Automatic Control, 2004, 49(1): 30-44.

[28]Van Drongelen W, Lee H C, Hereld M, et al. Emergent epileptiform activity in neural networks with weak excitatory synapses [J]. IEEE Transactions on Neural Systems and Rehabilitation Engineering, 2005, 13(2): 236-241.

[29]Yu A R, Thompson B B, Marks R J. Competitive evolution of tactical multiswarm dynamics [J]. IEEE Transactions on Systems, Man, and Cybernetics Systems, 2013, 43(3): 563-569.

[30]Ewert W, Marks R J, Thompson B B, et al. Evolutionary inversion of swarm emergence using disjunctive combs control [J]. IEEE Transactions on Systems, Man, and Cybernetics Systems, 2013, 43(5): 1063-1076.

[31]Li N, Marden J R. Designing games for distributed optimization [J]. IEEE Journal of Selected Topics in Signal Processing, 2013, 7(2): 230-242.

[32]宋玉蓉, 蔣國平.基于一維元胞自動(dòng)機(jī)的復(fù)雜網(wǎng)絡(luò)惡意軟件傳播研究[J]. 物理學(xué)報(bào), 2009, 58(9): 5911-5918. Song Yurong, Jiang Guoping. Research of malware propagation in complex networks based on 1-D cellular automata [J]. Acta Physica Sinica. 2009, 58(9): 5911-5918.

[33]Simons N R S, Bridges G E, Podaima B W, et al. Cellular automata as an environment for simulating electromagnetic phenomena [J]. Microwave and Guided Wave Letters, 1994, 4(7): 247-249.

[34]Mamei M, Roli A, Zambonelli F. Emergence and control of macro-spatial structures in perturbed cellular automata, and implications for pervasive computing systems [J]. Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on, 2005, 35(3): 337-348.

[35]Mardiris V A, Karafyllidis I G. Universal cellular automaton cell using quantum cellular automata [J]. Electronics letters, 2009, 45(12): 607-609.

[36]Sapin E, Bull L, Adamatzky A. Genetic approaches to search for computing patterns in cellular automata [J]. Computational Intelligence Magazine, 2009, 4(3): 20-28.

[37]肖人彬, 陶振武. 群集智能研究進(jìn)展 [J]. 管理科學(xué)學(xué)報(bào), 2007, 10(3): 80-96. Xiao Renbin, Tao Zhenwu. Development in swarm intelligence [J]. Journal of Management Sciences in China, 2007, 10(3): 80-96.

[38]肖人彬. 面向復(fù)雜系統(tǒng)的群集智能 [M]. 北京: 科學(xué)出版社, 2013.

[39]Dorigo M, Maniezzo V, Colorni A. The ant system: optimization by a colony of cooperating agents [J]. IEEE Transactions on Systems, Man and Cybernetics-Part B, 1996, 26(1) : 29-41.

[40]Weng J, Luciw M D, Zhang Q. Brain-like emergent temporal processing: emergent open states [J]. IEEE Transactions on Autonomous Mental Development, 2013, 5(2): 89-116.

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

[42]金士堯, 黃紅兵, 任傳俊. 基于復(fù)雜性科學(xué)基本概念的MAS涌現(xiàn)性量化研究 [J]. 計(jì)算機(jī)學(xué)報(bào), 2009, 32(1): 17-29. Jin Shiyao,Huang Hongbing,Ren Chuanjun. Emergence oriented research on MAS with quantifications based on the notions in science of complexity [J]. Chinese Journal of Computers, 2009, 32(1): 17-29.

[43]尼科利斯 G, 普里戈金 I. 非平衡系統(tǒng)中的自組織 [M]. 徐錫申,譯. 北京: 科學(xué)出版社, 1986

[44]哈肯 H. 協(xié)同學(xué)導(dǎo)論 [M]. 張紀(jì)岳,郭治安,譯. 西安: 西北大學(xué)科研處, 1981.

[45]Liu J, Jin X, Tsui K C. Autonomy-oriented computing (AOC): formulating computational systems with autonomous components [J]. IEEE Transactions on Systems, Man and Cybernetics, Part A Systems and Humans, 2005, 35(6): 879-902.

[46]李健, 李剛, 孫林巖. 分散化供應(yīng)鏈的自組織演化機(jī)制建模與仿真 [J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí), 2008, 38(6): 26-34. Li Jian, Li Gang, Sun Linyan. Modeling and simulation of distributed supply-chain self-organizing evolution mechanism [J]. Mathematics in Practice and Theory, 2008, 38(6): 26-34.

[47]顧珊珊, 陳禹. 復(fù)雜適應(yīng)性系統(tǒng)的仿真與研究——基于CAS理論的交通模擬 [J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 2004, 1(1): 82-88. Gu Shanshan, Chen Yu. Modeling & simulation of complex adaptive system-a traffic simulation system [J]. Complex Systems and Complexity Science, 2004, 1(1): 82-88.

[48]張嗣瀛. 復(fù)雜性科學(xué), 整體規(guī)律與定性研究 [J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 2005, 2(1): 71-83. Zhang Siying. Complexity science, rules of the whole systems and the qualitative researches [J]. Complex Systems and Complexity Science, 2005, 2(1): 71-83.

[49]羅吉貴, 劉曾榮. 從同步到涌現(xiàn) [J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 2005, 2(1): 29-32. Luo Jigui, Liu Zengrong. From synchronization to emergence [J]. Complex Systems and Complexity Science, 2005, 2(1): 29-32.

[50]Winfree A T. Biological rhythms and the behavior of populations of coupled oscillators [J]. Journal of Theoretical Biology, 1967, 16(1):15-42.

[51]Araki H. International symposium on mathematical problems in theoretical physics [J]. Lecture Notes in Physics, 1975, 39.

[52]Néda Z, Ravasz E, Brechet Y, et al. Self-organizing processes: The sound of many hands clapping [J]. Nature, 2000, 403(6772): 849-850.

[53]Strogatz S H. Fromkuramoto to crawford: exploring the onset of synchronization in populations of coupled oscillators [J]. Physica D: Nonlinear Phenomena, 2000, 143(1): 1-20.

[54]李德毅, 劉坤, 孫巖, 等. 涌現(xiàn)計(jì)算: 從無序掌聲到有序掌聲的虛擬現(xiàn)實(shí) [J]. 中國科學(xué) E輯: 信息科學(xué), 2007, 37(10): 1248-1257. Li Deyi, Liu Kun, Sun Yan, et al. Emergent computation: the virtual reality of applause from disorder to ordered [J]. Science in China(Series E: Information Sciences), 2007, 37(10): 1248-1257.

[55]Li D, Liu K, Sun Y, et al. Emerging clapping synchronization from a complex multiagent network with local information via local control [J]. IEEE Transactions on Circuits and Systems II: Express Briefs, 2009, 56(6): 504-508.

[56]Wang D L. Emergent synchrony in locally coupled neural oscillators [J]. IEEE Transactions on Neural Networks, 1995, 6(4): 941-948.

[57]Zhang Q, Lu J, Lu J, et al. Adaptive feedback synchronization of a general complex dynamical network with delayed nodes [J]. IEEE Transactions on Circuits and Systems II: Express Briefs, 2008, 55(2): 183-187.

[58]Chen M. Chaos synchronization in complex networks [J]. IEEE Transactions on Circuits and Systems I: Regular Papers, 2008, 55(5): 1335-1346.

[59]Boulden S, Iorio A W, Abbass H A. Learning synchronization in networked complex systems using genetic algorithms[C]// IEEE Congress on Evolutionary Computation, 2010: 1-8.

[60]汪鐳, 周國興. 用Hopfield神經(jīng)網(wǎng)絡(luò)進(jìn)行交流傳動(dòng)系統(tǒng)參數(shù)辨識(shí) [J]. 模式識(shí)別與人工智能， 1996, 9(3): 291-296. Wang Lei, Zhou Guoxing. Hopfield neural network based AC drive system parameters identification [J]. Pattern Recognitien and Artificial Intelligence, 1996, 9(3): 291-296.

[61]康琦, 安靜, 汪鐳, 等. 自然計(jì)算的研究綜述 [J]. 電子學(xué)報(bào), 2012, 40(3): 548-558. Kang Qi, An Jing, Wang Lei, et al. nature-inspired computation: a survey [J]. Aacta Electronica Sinica, 2012, 40(3): 548-558.

[62]汪鐳, 康琦, 吳啟迪. 自然計(jì)算——人工智能的有效實(shí)施模式 [J]. 系統(tǒng)工程理論與實(shí)踐, 2007, 5: 126-134. Wang Lei, Kang Qi, Wu Qidi. Nature-inspired computation-effective realization of artificial intelligence [J]. Systems Engineering-Theory & Practice, 2007, 5: 126-134.

[63]Dong J, Zhang Z, Ma D. Emergent phenomenon and the local information based DTA model [C]// IEEE Intelligent Transportation Systems, 2003, 2: 1273-1277.

[64]Sotelo M A, Van Lint J W C, Nunes U, et al. Introduction to the special issue on emergent cooperative technologies in intelligent transportation systems [J]. IEEE Transactions on Intelligent Transportation Systems, 2012, 13(1): 1-5.

[65]Linkens D A, Nyongesa H O. Learning systems in intelligent control: an appraisal of fuzzy, neural and genetic algorithm control applications [J]. IEEE Proceedings Control Theory and Applications, 1996, 143(4): 367-386.

[66]Maturana F P, Staron R J, Hall K H. Methodologies and tools for intelligent agents in distributed control [J]. IEEE Intelligent Systems, 2005, 20(1): 42-49.

[67]Arena P, Fortuna L, Frasca M, et al. A CNN-based chip for robot locomotion control [J]. IEEE Transactions on Circuits and Systems I: Re-gular Papers, 2005, 52(9): 1862-1871.

[68]Krasny D P, Orin D E. Generating high-speed dynamic running gaits in a quadruped robot using an evolutionary search [J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2004, 34(4): 1685-1696.

[69]Arena P, Patanè L. Simple sensors provide inputs for cognitive robots [J]. IEEE Instrumentation & Measurement Magazine, 2009, 12(3): 13-20.

[70]Floreano D, Mondada F. Evolution of homing navigation in a real mobile robot [J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 1996, 26(3): 396-407.

[71]Li Y, Tang Z, Xia G P, et al. A positively self-feedbacked Hopfield neural network architecture for crossbar switching [J]. IEEE Transactions on Circuits and Systems I: Regular Papers, 2005, 52(1): 200-206.

[72]Dogaru R. Applications of Emergent Computation in Reaction-Diffusion CNNs for Image Processing[C]// 19th IEEE International Conference on Control Systems and Computer Science, 2013: 370-377.

[73]楊淑瑩, 劉旭鵬, 陶沖, 等. 基于免疫貓群優(yōu)化算法的矢量量化的碼書設(shè)計(jì)及語音識(shí)別 [J]. 模式識(shí)別與人工智能, 27(7): 577-583. Yang Shuying, Liu Xupeng, Tao Chong, et al. Vector quantization codebook design and speech recognition based on immune cat swarm optimization algorithm [J]. Pattern Recognition and Artificial Intelligence, 27(7): 577-583.

[74]Ha S Y, Ha T, Kim J H. Emergent behavior of a Cucker-Smale type particle model with nonlinear velocity couplings [J]. IEEE Transactions on Automatic Control, 2010, 55(7): 1679-1683.

[75]Kahrobaee S, Rajabzadeh R A, Soh L K, et al. A multiagent modeling and investigation of smart homes with power generation, storage, and trading features [J]. IEEE Transactions on Smart Grid, 2013, 4(2): 659-668.

[76]Tero A, Takagi S, Saigusa T, et al. Rules for biologically inspired adaptive network design [J]. Science, 2010, 327(5964): 439-442.

[77]Seiffertt J, Wunsch D. Intelligence in markets: asset pricing, mechanism design, and natural computation technology review [J]. IEEE Computational Intelligence Magazine, 2008, 3(4): 27-30.

[78]Chung J R, Choe Y. Emergence of memory in reactive agents equipped with environmental markers [J]. IEEE Transactions on Autonomous Mental Development, 2011, 3(3): 257-271.

[79]Lee S M, Pritchett A R. Predicting interactions between agents in agent-based modeling and simulation of sociotechnical systems [J]. IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans, 2008, 38(6): 1210-1220.

[80]Hurlburt G, Voas J, Miller K, et al. A nonlinear perspective on higher education [J]. Computer, 2010 (12): 90-92.

[81]Kong Z, Mettler B. Modeling human guidance behavior based on patterns in agent-environment interactions [J]. IEEE Transactions on Human-Machine Systems, 2013, 43(4): 371-384.

[82]Sanchez-Cortes D, Aran O, Mast M S, et al. A nonverbal behavior approach to identify emergent leaders in small groups [J]. IEEE Transactions on Multimedia, 2012, 14(3): 816-832.

[83]Izumi K, Ueda K. Phase transition in a foreign exchange market-analysis based on an artificial market approach [J]. IEEE Transactions on Evolutionary Computation, 2001, 5(5): 456-470.

[84]欒笑天, 吳桐水, 寇勇剛. 基于CA方法的航空物流市場(chǎng)演化模型設(shè)計(jì) [J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 2013, 10(4): 31-40. Luan Xiaotian, Wu Tongshui, Kou Yonggang. Designing the evolution model of aviation logistics market with cellular automata [J]. Complex Systems and Complexity Science, 2013, 10(4): 31-40.

[85]Koritarov V S. Real-world market representation with agents [J]. IEEE Power and Energy Magazine, 2004, 2(4): 39-46.

[86]Chicco G, Napoli R, Piglione F, et al. Emergent electricity customer classification [J]. IEE Proceedings-Generation, Transmission and Distribution, 2005, 152(2): 164-172.

[87]龔小慶, 范文濤, 丁義明. 建立系統(tǒng)科學(xué)基礎(chǔ)理論框架的一種可能途徑與若干具體思路( 之八) —— 固定環(huán)境中的穩(wěn)態(tài)涌現(xiàn) [J]. 系統(tǒng)工程理論與實(shí)踐, 2003, 8: 1-7. Gong Xiaoqing, Fan Wentao, Ding Yiming. A possible approach to the framework of the fundamental theory of system science: part eight [J]. Systems Engineering-theory & Practice, 2003, 8: 1-7.

[88]龔小慶, 王展. 關(guān)于Zipf律的一點(diǎn)注記 [J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 2008, 5(3): 73-78. Gong Xiaoqing, Wang Zhan. A note on the zipf′s law [J]. Complex Systems and Complexity Science, 2008, 5(3): 73-78.

[89]龔小慶. 經(jīng)濟(jì)系統(tǒng)涌現(xiàn)和演化——復(fù)雜性科學(xué)的觀點(diǎn) [J]. 財(cái)經(jīng)論叢, 2004, 5(111): 12-18. Gong Xiaoqing. Researches on emergence and evolution of economy——in the view of complexity sciences [J]. Collected Essays on Finance and Economics, 2004, 5(111): 12-18.

[90]趙劍冬, 黃戰(zhàn). 基于Agent的經(jīng)濟(jì)社會(huì)系統(tǒng)建模與仿真研究 [J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 2011, 8(4): 59-67. Zhao Jiandong, Huang Zhan. A study on agent based social-economic system modeling and simulation [J]. Complex Systems and Complexity Science, 2011, 8(4): 59-67.

[91]Zeng F, Decraene J, Low M Y H, et al. Evolving optimal and diversified military operational plans for computational red Teaming [J]. IEEE Systems Journal, 2012, 6(3): 499-509.

[92]Lewis R, Paechter B. Finding feasible timetables using group-based operators [J]. IEEE Transactions on Evolutionary Computation, 2007, 11(3): 397-413.

[93]王飛躍, 史帝夫·蘭森. 從人工生命到人工社會(huì)—復(fù)雜社會(huì)系統(tǒng)研究的現(xiàn)狀和展望 [J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 2004, 1(1): 33-41. Wang Feiyue, Lansing J S. From artificial life to artificial societies—new methods for studies of complex social systems [J]. Complex Systems and Complexity Science, 2004, 1(1): 33-41.

(責(zé)任編輯 耿金花)

Emergent Computation: an Overview

LI Jin，XIAO Renbin

(School of Automation, Huazhong University of Science and Technology, Wuhan 430074, China)

Firstly we introduce emergent phenomenon in complex systems and the basic principle of emergent computation. Secondly an important emergent computation model — cellular automata (CA) is demonstrated, and the relationship between emergent computation and swarm intelligence is illustrated. Then we discuss some key themes such as the mapping from source problems to emergent computation models, self-organization and synchronization. At last we review the application of emergent computation in aspects of engineering computation and social computation.

emergent computation；swarm intelligence；cellular automata

1672-3813(2015)04-0001-13;

10.13306/j.1672-3813.2015.04.001

2014-02-25 ；

2014-10-23

教育部高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金(20130142110051)

李勁(1980-)，男，河北雄縣人，博士，主要研究方向?yàn)橛楷F(xiàn)計(jì)算，群集智能。

肖人彬(1965-)，男，湖北武漢人，博士，教授，主要研究方向?yàn)閺?fù)雜系統(tǒng)，復(fù)雜社會(huì)管理。

TP18

A