涌現計算綜述

李 勁， 肖人彬

(華中科技大學自動化學院，武漢 430074)

涌現計算綜述

李 勁， 肖人彬

(華中科技大學自動化學院，武漢 430074)

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

涌現計算；群集智能；元胞自動機

0 引言

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

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

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

1 涌現現象

1.1 涌現現象的基本概念和性質

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

1.2 自然系統中的涌現現象

自然中存在許多涌現現象，這也是我們得以進行涌現計算建模的基礎。一個典型的例子就是蟻群的覓食行為。每只單獨的螞蟻都是一個相對簡單的個體，能力有限，只能完成一些簡單的任務。然而，當大量的螞蟻個體在一起形成蟻群時，整個蟻群就能表現出非常復雜和神奇的涌現現象，如社會分工、集體協作等等。例如在螞蟻覓食的過程中，就能表現出具有智能的涌現行為，能夠尋找到巢穴到食物的最優路徑。這一行為已經超出了單個螞蟻的能力范疇，是大量螞蟻通過傳遞信息相互作用共同協作的結果。在螞蟻覓食的過程中，不存在一個中心控制個體，蟻群是通過分布式的協作找到最快搬運路徑的，這一行為完全是局部相互作用的結果，是蟻群中典型的涌現現象。除了覓食行為，蟻群中還存在勞動分工[4]和墓地構造[5]等涌現現象。與蟻群中類似的涌現現象在蜂群、鳥群和魚群中同樣存在。此外，人體中神經系統的記憶、學習等智能行為和表現可以視為神經元相互作用而產生的涌現現象[6]，大量細胞的相互作用中存在著豐富的涌現現象[7]。

1.3 社會系統中的涌現現象

涌現現象在人際交往，演員合作，科學家合作和經濟系統等社會系統中非常普遍。

Tao Z等[8]提出了社區結構涌現的判別方法，并對美國安然公司以電子郵件發送關系形成的社會網絡進行了研究，得到了社區結構的演化過程及其涌現現象的計算結果。

此外，經濟系統也是一個很好的例子。隨著計算機技術的發展，研究者們越來越多地使用多agent涌現合作系統來對市場互動行為進行探索，以發現經濟金融現象中更多的規律和知識，為價格預測，資產交易及市場應用設計新的商業模式。經濟學之父亞當·斯密曾提出有“看不見的手”在引導著市場，今天我們可以認為這個“看不見的手”其實是經濟領域的涌現現象，可以由涌現計算模型和算法進行預測。智能涌現計算與經濟學的交叉將有利于更好地洞察人類市場互動行為的本質[9]。

1.4 人工系統中的涌現現象

通信網、交通網等許多人工構建的系統中也存在著涌現現象[10-14]。比如計算機網絡中數據包傳輸的擁塞現象，交通系統中的交通堵塞，人工多主體模型表現出來的與生物啟發原型相似的各種涌現行為等。

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

在圖象數據庫這樣的人工系統中亦存在涌現現象。Santini S等[17]發現在圖象數據庫中特定圖像的語義是一種涌現現象。他們認為圖像本身并不具有固有的內在含義，而是將它們置于由其他圖像構成的上下文環境中并在用戶互動中涌現產生的，并據此提出了一種圖像操作與配置接口模型，使得用戶不但可以對單個圖像進行操作也可以對圖像之間的關系進行操作和定義，從而讓圖像可以在互動中產生涌現語義。

人為構建的機器人系統中亦存在涌現現象，可以利用其進行機器人的智能化控制。Shimizu M等[18]對一種名為Slimebot的機器人系統進行了研究，這個系統由多個相同的模塊化的小機器人組成，根據環境的不同在分布式算法的控制下相互作用組成不同的形態。實驗表明，在基于涌現現象的算法作用下，可以在保證系統連貫性的情況下對機器人的形態進行實時控制。Lee S I等[19]開發了一種基于遺傳算法的模糊邏輯控制器用于控制移動機器人，并用內部模型的狀態轉換圖分析了控制器的行為。實驗結果表示通過進化可以獲得恰當的控制策略，并且在所獲得的模糊規則集的互相作用下，機器人會表現出涌現行為。

硬件技術的發展使構建大規模的無線傳感器網絡成為可能，單個傳感器體積大大減小，功耗降低，價格也越來越便宜。在大量智能微終端構成的智能微塵中多個傳感器之間的局部作用會產生通信與合作，節點失效與網絡的魯棒性等許多涌現現象值得進行深入的研究[20-22]。

對于人工系統中的涌現現象進行研究，一方面可以更加了解系統的運作方式和演化動力學過程；一方面可以運用涌現現象中存在的規律，對系統進行控制和優化，提升系統的性能。

2 涌現計算概述

2.1 涌現計算與涌現現象之間的關系，涌現計算的基本定義和特點

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

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

值得注意的是，雖然涌現計算是一種“自底向上”的算法，一定的局部規則會產生什么樣的涌現現象往往難以預測，而近年這一問題更具難度的逆問題——即給定一個期望產生的涌現現象，那么系統中的主體應該遵循什么樣的局部規則才會導致這一特定涌現現象的產生—也得到了注意和研究[29-31]。這將有利于增加我們對涌現現象的認識深度和控制能力，具有一定的實用價值。

綜上，我們可以認為涌現計算是由一系列獨立計算處理進程并行合作構成的計算過程的總體，由低等級計算進程之間依照特定規則集進行相互作用而構成高等級計算過程，實現可預計的總體功能，不受任何形式的全局控制，以局部作用產生的涌現現象作為計算結果，并能夠在演化過程中實現自身穩定和收斂。

圖靈機數學模型奠定了現代計算機科學的理論基礎，它使用一個讀寫頭進行工作，每個時刻只完成一步操作。以圖靈機為基本模型的傳統計算模式也多采用串行的工作模式，雖然在原則上能夠模擬一切運算，但是在遇到類似NP難問題這樣復雜度很高的問題時，由于求解時間隨問題規模快速增長，實際的計算求解變得不再可行。與大多數傳統計算模式的串行工作方式不同，涌現計算采用分布式的并行運算模式，且在涌現計算中不存在中心控制，而主要依賴個體之間的局部作用來在整體上涌現出計算結果，這些特點使得涌現計算模式能夠在可接受的時間內為一些無法使用傳統計算模式求解的問題提供可接受的解。因此，涌現計算是傳統計算模式很好的補充，為計算問題提供了一種新的求解方法和途徑。

2.2 一種涌現計算模型：元胞自動機

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

一個標準的元胞自動機(A)由元胞、元胞狀態、鄰域和狀態更新規則構成。可用式(1)來表示

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

(1)

其中，L為元胞空間；d為元胞自動機內元胞空間的維數；S為元胞有限的、離散的狀態集合；N為某個鄰域內所有元胞的集合；f為局部映射或局部規則。

圖1 傳統元胞自動機的鄰域定義方式

圖2 基于網絡的元胞鄰域定義

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

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

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

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

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

2.3 涌現計算與群集智能

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

3 涌現計算中的若干關鍵問題

涌現計算中存在涌現模型映射、自組織、同步等關鍵問題，這些問題之間互相交疊，相互關聯，共同影響著涌現計算的過程和結果。

3.1 向涌現計算模型的映射

目前常用的涌現計算模型有元胞自動機、螞蟻算法、蜂群算法、神經網絡、遺傳算法等。在進行具體問題的求解時，首先需要做的就是要完成從具體問題到涌現計算模型的映射。要將需求解的問題和條件在涌現計算模型中表達出來，并進行相關的定義以便對計算所得到的涌現結果進行解釋和翻譯，轉化為實際問題的解。

以元胞自動機為例，在求解工程設計中的連續結構拓撲優化問題時，便需要建立元胞自動機和結構有限元之間的映射關系，以利用元胞自動機完成連續結構涌現計算[38]。文獻[38]中所提到的連續結構拓撲優化是在設計空間、支撐與載荷條件和某些工藝設計等受限條件下，確定結構構件之間的相互連接方式，結構內有無孔洞、孔洞的數量、位置等拓撲形式，使結構能將外載荷傳遞到支座，同時使結構的某些性能指標達到最優。在使用元胞自動機模型進行涌現計算求解時，首先要用規則形狀的單元進行連續結構的網格劃分，然后用有限元方法計算在給定載荷和約束條件下的局部應變能密度，再將上述網格映射為元胞自動機的進化環境，然后要利用“比例—積分—微分”控制原理和滿應力設計準則重構基于應變能的元胞局部進化規則，通過元胞進化得到單元密度變化系數，從而得到新的設計域，重復上述過程直到進化出滿足收斂條件的連續結構的拓撲形式。

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

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

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

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

圖4 一種涌現計算模型

3.2 自組織

自組織是指某一系統中自發形成的時空有序結構或狀態。它是一種在沒有中心控制(沒有組織者或其他系統之外的設計)、沒有完全信息的條件下，僅僅通過微觀個體的局部相互作用導致的系統全局結構的涌現。自下而上、自發性、涌現性是自組織必備的和重要的特征。自組織有3個主要特性：涌現、自適應、進化。涌現是一種由系統各組元之間的相互作用而形成的全局現象。適應性自組織系統通過自下而上的涌現行為處理干擾的存在和對環境變化作出自動的適應性改變以維護系統的穩定。進化是自組織系統涌現和適應性綜合作用的結果。自組織現象在自然與人工系統中普遍存在。

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

那么自組織會在什么樣的條件下發生，又是如何發生的呢？Nicolis G 等[43]認為自組織發生在由非線性相互作用的元素組成的遠離平衡態開放系統中，這意味著為涌現計算而構建的人工系統是由互相之間具有非線性作用的多個元素構成并且處于遠離平衡態的混沌的邊緣。Nicolis G 等給出的為必要條件，相對寬泛，因為并不是所有非線性作用都能產生自組織現象。Haken[44]則進一步指出自組織中非線性作用的具體形式為競爭性協同，即涌現計算系統中的多個主體之間同時存在競爭與合作的關系。我們認為系統開放并遠離平衡態是自組織的必要條件，涌現計算系統開放于求解環境中進行輸入物質、能量和信息的交換，系統中各主體在競爭性協同中實現正反饋機制，使系統中蘊含的有序性得到增強與表達，進而自組織形成某種特定的功能性結構，從而涌現出所求解問題的解。

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

3.3 同步

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

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

對于涌現、自組織和同步等復雜系統中關鍵主題的研究，將能夠幫助我們更好地認識涌現現象發生的機理，從而控制涌現現象的產生和發展的方向，有利于在涌現計算中避免不需要或不希望的涌現現象的產生，獲得所需要的涌現現象，使涌現計算的過程更具可控性，提高涌現計算求解問題的能力。

4 涌現計算的典型應用

4.1 工程系統中的涌現計算

許多涉及到眾多影響因素的復雜工程問題往往可以使用涌現計算得到很好的解決。

肖人彬等[38]采用基于元胞自動機的連續結構涌現模型計算了在不同溫度邊界條件和熱源分布情況下方形平板散熱的最優拓撲結構，實現了基于涌現計算的自動結構設計，實驗證明這是一種有效而高效的設計方法。汪鐳等[60-62]將涌現計算中的一種重要算法模型——人工神經網絡應用于自動控制及傳動系統領域，取得了良好的效果，此外他們還以反饋式神經網絡和群體智能算法為基礎給出了自然計算理念統一的框架描述, 自然計算領域內的相關群體智能算法表現出一種相對統一的智能計算模式，即涌現計算模式。

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

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

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

圖5 帶有傳感反饋的機器人系統框圖

圖6 機器人的結構及其自動涌現生成的運動路徑

Floreano D等[70]使用一個時間離散的迭代神經網絡進化算法控制一個實體的移動機器人，通過在實驗初期設置的一組約束條件，在無需預先進行設定的情況下，機器人自動涌現出了對電池充電器進行定位并周期性回到充電器所在處進行充電的行為。

Yong Li等[71]提出了一種正反饋HOPFIELD神經網絡結構，具有類似于標準HOPFIELD方法的涌現特性，用于交叉開關切換控制，相比于包括標準HOPFIELD方法在內的以前的方法，在計算時間和解的質量上均具有優勢。

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

在智能房屋領域，涌現計算被用來進行電力規劃與決策。帶有發電儲存和交易功能的智能房屋不再只是電網中一個無源的負載，而是有雙向的能量流入與流出。將智能房屋視為主體，可使用基于多主體的方法，結合當前和預期的用電量、發電量和貯電量來自動決定買入、存儲或是賣出電力資源，從而最小化其電費賬單[75]。

圖7 感知器、啟發式代理和執行器結構模型

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

4.2 社會系統中的涌現計算

在市場與經濟系統[77-78]，社會技術系統[79]，科學與教育[80]、演藝圈、人際關系社團[81-82]等社會系統中存在著大量的涌現現象，亦可以使用涌現計算來解決其中的很多問題。

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

圖8 粘菌涌現計算結果與東京周邊鐵路網絡的對比圖

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

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

針對更一般性的社會學命題，王飛躍等[93]采用人工社會模型，基于代理的建模、模擬和分析來進行研究，指出通過涌現的方式，人工社會模型中可以方便地涌現出合作、調節、反饋、競爭、沖突等復雜系統現象及它們之間的交互和轉換，展示了涌現計算在社會問題研究中的應用潛力。

5 結語

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

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

對于涌現現象的深入研究將進一步推動涌現計算的發展，同時反過來為我們理解和掌控身邊世界的運行提供更有效的工具。

[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]宋玉蓉, 蔣國平.基于一維元胞自動機的復雜網絡惡意軟件傳播研究[J]. 物理學報, 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]. 管理科學學報, 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]肖人彬. 面向復雜系統的群集智能 [M]. 北京: 科學出版社, 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]顏澤賢, 范冬萍, 張華夏. 系統科學導論—復雜性探索 [M]. 北京: 人民出版社, 2006.

[42]金士堯, 黃紅兵, 任傳俊. 基于復雜性科學基本概念的MAS涌現性量化研究 [J]. 計算機學報, 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. 非平衡系統中的自組織 [M]. 徐錫申,譯. 北京: 科學出版社, 1986

[44]哈肯 H. 協同學導論 [M]. 張紀岳,郭治安,譯. 西安: 西北大學科研處, 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]李健, 李剛, 孫林巖. 分散化供應鏈的自組織演化機制建模與仿真 [J]. 數學的實踐與認識, 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]顧珊珊, 陳禹. 復雜適應性系統的仿真與研究——基于CAS理論的交通模擬 [J]. 復雜系統與復雜性科學, 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]張嗣瀛. 復雜性科學, 整體規律與定性研究 [J]. 復雜系統與復雜性科學, 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]羅吉貴, 劉曾榮. 從同步到涌現 [J]. 復雜系統與復雜性科學, 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]李德毅, 劉坤, 孫巖, 等. 涌現計算: 從無序掌聲到有序掌聲的虛擬現實 [J]. 中國科學 E輯: 信息科學, 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]. 模式識別與人工智能， 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]. 電子學報, 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]. 系統工程理論與實踐, 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]楊淑瑩, 劉旭鵬, 陶沖, 等. 基于免疫貓群優化算法的矢量量化的碼書設計及語音識別 [J]. 模式識別與人工智能, 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方法的航空物流市場演化模型設計 [J]. 復雜系統與復雜性科學, 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]龔小慶, 范文濤, 丁義明. 建立系統科學基礎理論框架的一種可能途徑與若干具體思路( 之八) —— 固定環境中的穩態涌現 [J]. 系統工程理論與實踐, 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]龔小慶, 王展. 關于Zipf律的一點注記 [J]. 復雜系統與復雜性科學, 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]. 財經論叢, 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]趙劍冬, 黃戰. 基于Agent的經濟社會系統建模與仿真研究 [J]. 復雜系統與復雜性科學, 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]王飛躍, 史帝夫·蘭森. 從人工生命到人工社會—復雜社會系統研究的現狀和展望 [J]. 復雜系統與復雜性科學, 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.

(責任編輯 耿金花)

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

教育部高等學校博士學科點專項科研基金(20130142110051)

李勁(1980-)，男，河北雄縣人，博士，主要研究方向為涌現計算，群集智能。

肖人彬(1965-)，男，湖北武漢人，博士，教授，主要研究方向為復雜系統，復雜社會管理。

TP18

A