黃振東

【摘 要】工程系統(tǒng)中存在大量的優(yōu)化與控制問題，與智能算法求解不同，將工程系統(tǒng)看做是復(fù)雜自組織系統(tǒng)，從自組織計(jì)算的角度研究復(fù)雜工程系統(tǒng)問題是復(fù)雜性科學(xué)研究的新方向。本文介紹自組織系統(tǒng)概念特征，綜述了自組織計(jì)算模型及原理，對自組織計(jì)算在工程系統(tǒng)中的應(yīng)用優(yōu)勢及設(shè)計(jì)難點(diǎn)進(jìn)行了總結(jié)。

【關(guān)鍵詞】自組織；涌現(xiàn)；工程系統(tǒng)；多智能體系統(tǒng)

自組織技術(shù)作為研究復(fù)雜系統(tǒng)的一個(gè)有力工具，已經(jīng)引起許多科學(xué)家的關(guān)注。工程系統(tǒng)中的自組織涌現(xiàn)算法，是期望設(shè)計(jì)一種自組織系統(tǒng)，通過系統(tǒng)內(nèi)部智能體的局部相互作用，系統(tǒng)涌現(xiàn)出穩(wěn)定的結(jié)構(gòu)（即設(shè)計(jì)目標(biāo)）。

1 自組織的概念與特征

自組織系統(tǒng)在各個(gè)學(xué)科中定義不盡相同，普遍認(rèn)為自組織系統(tǒng)為一些個(gè)體集合，可無需通過外部控制，系統(tǒng)通過個(gè)體之間的局部相互作用的實(shí)現(xiàn)全局行為。

一般來說，自組織系統(tǒng)具有如下的一些特性[1]：

（1）分散控制。指的是系統(tǒng)主要利用個(gè)體的局部交互作用影響全局行為。

（2）涌現(xiàn)性。一般來說，涌現(xiàn)是一種來自系統(tǒng)各組元之間的相互作用的全局結(jié)果的現(xiàn)象。而系統(tǒng)全局結(jié)果相對于系統(tǒng)的組成部分是新穎的，或者說系統(tǒng)內(nèi)部組成部分的交互作用是無法預(yù)測系統(tǒng)的全局行為的。涌現(xiàn)的例子包括：螞蟻系統(tǒng)中螞蟻個(gè)體通過信息素交互產(chǎn)生的全局路徑、鳥群的遷徙、汽車之間的相互作用而產(chǎn)生的堵車等等。

（3）自適應(yīng)性。一個(gè)自組織系統(tǒng)會(huì)自動(dòng)調(diào)整系統(tǒng)狀態(tài)以適應(yīng)環(huán)境的變化，即其具有一定的抗擾動(dòng)能力和自適應(yīng)維持其結(jié)構(gòu)的能力。

（4）進(jìn)化：進(jìn)化是自組織系統(tǒng)涌現(xiàn)和自適應(yīng)性的結(jié)果。

2 自組織系統(tǒng)的求解模型

利用自組織系統(tǒng)研究工程問題，需要對自組織系統(tǒng)模型進(jìn)行研究，使得其可以在數(shù)學(xué)上進(jìn)行分析或通過計(jì)算機(jī)模擬研究。由于涌現(xiàn)行為不可預(yù)測性，合理的模型可以提供了一個(gè)虛擬實(shí)驗(yàn)平臺(tái)來探索涌現(xiàn)與局部規(guī)則之間的關(guān)系。目前，研究較多的模型有元胞自動(dòng)機(jī)（CA）[2]和多智能體系統(tǒng)（MAS）[3]。

2.1 元胞自動(dòng)機(jī)

元胞自動(dòng)機(jī)模型是一個(gè)研究自組織系統(tǒng)的模擬方法，其實(shí)質(zhì)上是定義在一個(gè)由有限離散狀態(tài)的元胞組成的元胞空間上，并按照一定的局部規(guī)則，在離散的時(shí)間維度上演化的動(dòng)力學(xué)系統(tǒng)。元胞自動(dòng)機(jī)是一類模型的總稱，或者說是一個(gè)方法框架。其特點(diǎn)是時(shí)間、空間、狀態(tài)都離散，每個(gè)元胞只取有限多個(gè)狀態(tài)，且其狀態(tài)改變的規(guī)則在時(shí)間和空間上都是局部的。元胞自動(dòng)機(jī)自產(chǎn)生以來，被廣泛地應(yīng)用到社會(huì)學(xué)、生態(tài)學(xué)、計(jì)算機(jī)科學(xué)、物理學(xué)、化學(xué)等領(lǐng)域。

2.2 多智能體系統(tǒng)

多智能體系統(tǒng)（MAS）是通過多個(gè)智能體相互交互和作用而使得系統(tǒng)達(dá)到某種目標(biāo)的計(jì)算系統(tǒng)。MAS方法中包含組成系統(tǒng)的智能體和環(huán)境的定義以及智能體之間的相互作用。MAS系統(tǒng)中環(huán)境作為智能體生存活動(dòng)的空間，將MAS組織成一個(gè)整體，為智能體提供通信和協(xié)調(diào)平臺(tái)；智能體被認(rèn)為是具有智能性和自適應(yīng)性的個(gè)體，遵循一定的規(guī)則，根據(jù)自身的局部信息與環(huán)境和其他智能體的交互作用來調(diào)整自身的狀態(tài)和行為，使得系統(tǒng)逐漸進(jìn)化，從而在整體上顯現(xiàn)出更高層次的有序性。換句話說，系統(tǒng)是基于分散控制的思想，根據(jù)智能體的局部適應(yīng)度函數(shù)來評價(jià)組成整體解的智能體的狀態(tài)變量，每個(gè)智能體根據(jù)局部信息和局部適應(yīng)度函數(shù)在當(dāng)前解得鄰域內(nèi)作出相應(yīng)的決策行為，通過智能體之間的相互競爭與協(xié)作等局部相互作用，系統(tǒng)自組織涌現(xiàn)出宏觀的結(jié)構(gòu)。

元胞自動(dòng)機(jī)模型中各個(gè)元胞一般是同質(zhì)的并遵循相同的鄰域和局部規(guī)則，其元胞狀態(tài)更新也是同步的；而多智能體系統(tǒng)中的智能體可以是同質(zhì)的，也可以是異質(zhì)的，并且各個(gè)智能體具有獨(dú)立性和自主性，其鄰域設(shè)定和局部作用規(guī)則也不盡相同，智能體的狀態(tài)更新可以是同步的，也可以是異步的。因此，MAS對于復(fù)雜系統(tǒng)的具有更強(qiáng)的表達(dá)力。此外，若將元胞自動(dòng)機(jī)中的元胞看成智能體，元胞的鄰域結(jié)構(gòu)和局部規(guī)則對應(yīng)看成智能體鄰域結(jié)構(gòu)和局部規(guī)則，則元胞自動(dòng)機(jī)可以看成一類特殊的MAS系統(tǒng)。MAS方法已被證明是非常適合研究復(fù)雜系統(tǒng)涌現(xiàn)性質(zhì)的模擬系統(tǒng)。

3 自組織系統(tǒng)機(jī)制與應(yīng)用

3.1 直接相互作用機(jī)制

直接相互作用機(jī)制是直接設(shè)計(jì)個(gè)體的局部相互作用的自組織機(jī)制。其基于一些基本的原則如局部化和廣播，智能體通過直接的局部的耦合作用自組織涌現(xiàn)出全局狀態(tài)。與傳統(tǒng)的分布式算法不同，自組織算法具有在環(huán)境中存在一定擾動(dòng)的情況下，系統(tǒng)能最終收斂到并保持需要的全局穩(wěn)定狀態(tài)，也就是說系統(tǒng)具有較強(qiáng)的魯棒性。

這種機(jī)制的典型實(shí)例是那些應(yīng)用在自組裝和分布式自定位領(lǐng)域。例如，文獻(xiàn)[4]中，通過設(shè)計(jì)粒子的局部規(guī)則，使得粒子自組織形成不同的形狀。

3.2 Stigmergy機(jī)制

Stigmergy這個(gè)詞是生物學(xué)家Grasse 創(chuàng)造的，用來解釋白蟻的筑巢行為。它是一種間接相互作用的自組織機(jī)制：群體中的個(gè)體之間沒有直接的相互作用，個(gè)體通過改變環(huán)境的方式來發(fā)生作用。而環(huán)境的變化又會(huì)影響個(gè)體的行為，其結(jié)果導(dǎo)致了環(huán)境的更新。這是一個(gè)信息的正反饋機(jī)制。

Stigmergy機(jī)制被廣泛應(yīng)用于MAS的設(shè)計(jì)中以獲得需要的涌現(xiàn)特征。Brueckner等[5]將它作為Agent 協(xié)作機(jī)制，應(yīng)用于移動(dòng)自組網(wǎng)的管理中，使得管理具有良好的自組織特征。Karuna等[6]等將MAS 應(yīng)用于工業(yè)自動(dòng)控制，并把Stigmergy 作為其協(xié)調(diào)和控制機(jī)制，使得整個(gè)控制系統(tǒng)具有涌現(xiàn)特征的預(yù)測能力。

3.3 強(qiáng)化機(jī)制

強(qiáng)化是導(dǎo)致生物系統(tǒng)中分化出“專家”和“一般勞動(dòng)力”的機(jī)制。這主要通過兩種方式實(shí)現(xiàn)：①Agent的工作效率隨著經(jīng)驗(yàn)的增長而提高； ②Agent對相關(guān)刺激的閾值隨著工作經(jīng)驗(yàn)增加而降低。強(qiáng)化機(jī)制可以導(dǎo)致勞動(dòng)分工和產(chǎn)生組織結(jié)構(gòu)，這是MAS 中非常重要的一種涌現(xiàn)現(xiàn)象。強(qiáng)化機(jī)制是一種天然的學(xué)習(xí)方法，學(xué)習(xí)和工作效率的提高往往被認(rèn)為是產(chǎn)生勞動(dòng)分工的主要原因。在強(qiáng)化學(xué)習(xí)過程中，Agent嘗試在其環(huán)境中產(chǎn)生一些作用（輸出），然后收到一個(gè)關(guān)于該作用的評價(jià)（報(bào)酬），學(xué)習(xí)算法選擇性地保留那些最大化自身報(bào)酬的輸出。強(qiáng)化學(xué)習(xí)一般通過獎(jiǎng)懲函數(shù)來調(diào)整Agent的行為，這樣的交互學(xué)習(xí)作用使得系統(tǒng)具有較強(qiáng)的適應(yīng)性和涌現(xiàn)特征。例如，Mazurowski等[7]將強(qiáng)化學(xué)習(xí)用于MAS 通信，以產(chǎn)生通信涌現(xiàn)。

3.4 競爭與合作機(jī)制

在自然界中，各種生物與物種共同生存在一定的生活環(huán)境中，這種生存環(huán)境中的資源是有限的，它們必須通過競爭與合作才能獲得自己生存所需的資源共同生存下去。通過這些競爭與合作的交互，物種們不斷進(jìn)化和改變，并相互影響彼此的進(jìn)化過程，因而自然界中的生物與物種之間實(shí)際上構(gòu)成了一種協(xié)進(jìn)化的關(guān)系，生態(tài)系統(tǒng)逐步完善，以適應(yīng)環(huán)境。受生物系統(tǒng)協(xié)進(jìn)化機(jī)制的啟發(fā)，工程系統(tǒng)所期望的集體行為可通過智能體協(xié)進(jìn)化作用涌現(xiàn)出來[8]。換句話說，系統(tǒng)的功能是在智能體的局部相互競爭與合作的作用中涌現(xiàn)出來的。每個(gè)智能體具有一定的自組織的能力，能根據(jù)其知識(shí)和任務(wù)改變其與其它智能體和環(huán)境交互，以適應(yīng)環(huán)境的改變。

4 自組織系統(tǒng)在工程優(yōu)化設(shè)計(jì)中的特點(diǎn)、優(yōu)勢，存在的問題及難點(diǎn)

基于MAS的自組織系統(tǒng)設(shè)計(jì)對于復(fù)雜工程系統(tǒng)具有無可比擬的表達(dá)力，可以成為研究復(fù)雜工程系統(tǒng)涌現(xiàn)行為的通用的模型和求解框架，其基于分散控制的思想，能充分挖掘智能體的局部信息指導(dǎo)智能體的進(jìn)化，同時(shí)，在系統(tǒng)進(jìn)化過程中，可以結(jié)合多種求解策略，特別是結(jié)合具體問題的特征，根據(jù)環(huán)境的變化有針對性的設(shè)計(jì)智能體相應(yīng)的規(guī)則，具有靈活性，適應(yīng)性與魯棒性的優(yōu)點(diǎn)，大大提高求解問題的能力。

自組織技術(shù)在工程中的應(yīng)用中，大多數(shù)是利用自組織系統(tǒng)進(jìn)行系統(tǒng)模擬與預(yù)測。而在工程優(yōu)化領(lǐng)域應(yīng)用的較少。對于設(shè)計(jì)自組織涌現(xiàn)系統(tǒng)應(yīng)用于工程優(yōu)化問題，其關(guān)鍵問題在于如何設(shè)計(jì)個(gè)體局部相互作用，使得智能體的微觀行為能涌現(xiàn)所要求的宏觀性能[7]。然而，由于自組織涌現(xiàn)的具有新穎性以及難以預(yù)測性，使得自組織系統(tǒng)的應(yīng)用于工程優(yōu)化設(shè)計(jì)很難實(shí)現(xiàn)。因?yàn)槲覀兒茈y根據(jù)想要的系統(tǒng)優(yōu)化設(shè)計(jì)目標(biāo)來推斷出局部作用規(guī)則。

目前，存在著三種方法尋找局部作用規(guī)則，即解析方法，仿生設(shè)計(jì)，試錯(cuò)方法。解析方法主要用于所研究的問題模型相對簡單，所需局部規(guī)則可以通過對全局屬性的解析得到，但這種方法局限性比較大。仿生設(shè)計(jì)方法主要通過生物系統(tǒng)的啟發(fā)來設(shè)計(jì)局部規(guī)則，仿生設(shè)計(jì)可以希望得到較好的設(shè)計(jì)結(jié)果，但它需要找出生物系統(tǒng)與所解決問題之間存在相似關(guān)系。試錯(cuò)方法是三類方法里面最一般的方法。然而，可能出現(xiàn)的巨大的參數(shù)空間和經(jīng)常反直覺的涌現(xiàn)性質(zhì)都給這類方法帶來很大的麻煩[7]。

5 總結(jié)與展望

工程系統(tǒng)中自組織涌現(xiàn)算法具有分散控制、自適應(yīng)性、魯棒性、靈活性以及擴(kuò)充性強(qiáng)等優(yōu)點(diǎn)。但其研究與應(yīng)用仍存在以下幾方面問題：①它們均是基于概率搜索的方法，從數(shù)學(xué)上對它們的正確性與可靠性的證明非常困難，仿真成為一種不可或缺的測試與驗(yàn)證方法。②系統(tǒng)的高層次的結(jié)構(gòu)是通過的個(gè)體之間的簡單交互作用涌現(xiàn)出來的，但由于涌現(xiàn)行為不可預(yù)測性質(zhì)，如何設(shè)計(jì)智能體之間的局部交互行為使得系統(tǒng)能夠涌現(xiàn)出所希望看到的高層次的行為結(jié)構(gòu)是一個(gè)極為困難的問題。

相比于自上而下設(shè)計(jì)的智能算法，自組織涌現(xiàn)的方法求解復(fù)雜工程優(yōu)化問題更有優(yōu)勢，但也存在一些問題和困難，今后的工作可以從自組織系統(tǒng)構(gòu)建、鄰域結(jié)構(gòu)設(shè)計(jì)、交互機(jī)制設(shè)計(jì)等方面做深入研究，使自組織求解成為復(fù)雜工程優(yōu)化的高效的求解框架。

【參考文獻(xiàn)】

[1]Heylighen F.The science of self-organization and adaptivity[J].The encyclopedia of life support systems， 2001，5（3）：253-280.

[2]Fredkin E. An informational process based on reversible universal cellular automata[J]. Physica D： Nonlinear Phenomena， 1990， 45（1）： 254-270.

[3]黃紅兵.基于涌現(xiàn)視角的多 Agent 系統(tǒng)分析研究[D].長沙：國防科技大學(xué)，2009.

[4]Mamei M， Zambonelli V F. Self-Organizing Spatial Shapes in Mobile Particles： The TOTA Approach[C]//Engineering Self-Organising Systems. Springer Berlin Heidelberg， 2005：138-153.

[5]Brueckner S A， Parunak H V D. Self-Organizing MANET Management[M]// Engineering Self-Organising Systems. Springer Berlin Heidelberg， 2004：20-35.

[6]Karuna H， Valckenaers P， Saint-Germain B， et al. Emergent Forecasting Using A Stigmergy Approach In Manufacturing Coordination And Control[J]. Lecture Notes in Computer Science， 2005， 3464：210-226.

[7]Mazurowski M A， Zurada J M. Emergence Of Communication In Multi-Agent Systems Using Reinforcement Learning[C]//Computational Cybernetics， 2006. ICCC 2006. IEEE International Conference on. 2006：1 - 6.

[8]Olaru A， Gratie C， Florea A M. A.M.： Emergent properties for data distribution in a cognitive mas[C]// Proc. of the 3rd International Symposium on Intelligent Distributed Computing - IDC 2009， October 13-14， Ayia. 2009.

[責(zé)任編輯：曹明明]