工程系統中的自組織技術研究

黃振東

【摘 要】工程系統中存在大量的優化與控制問題，與智能算法求解不同，將工程系統看做是復雜自組織系統，從自組織計算的角度研究復雜工程系統問題是復雜性科學研究的新方向。本文介紹自組織系統概念特征，綜述了自組織計算模型及原理，對自組織計算在工程系統中的應用優勢及設計難點進行了總結。

【關鍵詞】自組織；涌現；工程系統；多智能體系統

自組織技術作為研究復雜系統的一個有力工具，已經引起許多科學家的關注。工程系統中的自組織涌現算法，是期望設計一種自組織系統，通過系統內部智能體的局部相互作用，系統涌現出穩定的結構（即設計目標）。

1 自組織的概念與特征

自組織系統在各個學科中定義不盡相同，普遍認為自組織系統為一些個體集合，可無需通過外部控制，系統通過個體之間的局部相互作用的實現全局行為。

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

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

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

（3）自適應性。一個自組織系統會自動調整系統狀態以適應環境的變化，即其具有一定的抗擾動能力和自適應維持其結構的能力。

（4）進化：進化是自組織系統涌現和自適應性的結果。

2 自組織系統的求解模型

利用自組織系統研究工程問題，需要對自組織系統模型進行研究，使得其可以在數學上進行分析或通過計算機模擬研究。由于涌現行為不可預測性，合理的模型可以提供了一個虛擬實驗平臺來探索涌現與局部規則之間的關系。目前，研究較多的模型有元胞自動機（CA）[2]和多智能體系統（MAS）[3]。

2.1 元胞自動機

元胞自動機模型是一個研究自組織系統的模擬方法，其實質上是定義在一個由有限離散狀態的元胞組成的元胞空間上，并按照一定的局部規則，在離散的時間維度上演化的動力學系統。元胞自動機是一類模型的總稱，或者說是一個方法框架。其特點是時間、空間、狀態都離散，每個元胞只取有限多個狀態，且其狀態改變的規則在時間和空間上都是局部的。元胞自動機自產生以來，被廣泛地應用到社會學、生態學、計算機科學、物理學、化學等領域。

2.2 多智能體系統

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

元胞自動機模型中各個元胞一般是同質的并遵循相同的鄰域和局部規則，其元胞狀態更新也是同步的；而多智能體系統中的智能體可以是同質的，也可以是異質的，并且各個智能體具有獨立性和自主性，其鄰域設定和局部作用規則也不盡相同，智能體的狀態更新可以是同步的，也可以是異步的。因此，MAS對于復雜系統的具有更強的表達力。此外，若將元胞自動機中的元胞看成智能體，元胞的鄰域結構和局部規則對應看成智能體鄰域結構和局部規則，則元胞自動機可以看成一類特殊的MAS系統。MAS方法已被證明是非常適合研究復雜系統涌現性質的模擬系統。

3 自組織系統機制與應用

3.1 直接相互作用機制

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

這種機制的典型實例是那些應用在自組裝和分布式自定位領域。例如，文獻[4]中，通過設計粒子的局部規則，使得粒子自組織形成不同的形狀。

3.2 Stigmergy機制

Stigmergy這個詞是生物學家Grasse 創造的，用來解釋白蟻的筑巢行為。它是一種間接相互作用的自組織機制：群體中的個體之間沒有直接的相互作用，個體通過改變環境的方式來發生作用。而環境的變化又會影響個體的行為，其結果導致了環境的更新。這是一個信息的正反饋機制。

Stigmergy機制被廣泛應用于MAS的設計中以獲得需要的涌現特征。Brueckner等[5]將它作為Agent 協作機制，應用于移動自組網的管理中，使得管理具有良好的自組織特征。Karuna等[6]等將MAS 應用于工業自動控制，并把Stigmergy 作為其協調和控制機制，使得整個控制系統具有涌現特征的預測能力。

3.3 強化機制

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

3.4 競爭與合作機制

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

4 自組織系統在工程優化設計中的特點、優勢，存在的問題及難點

基于MAS的自組織系統設計對于復雜工程系統具有無可比擬的表達力，可以成為研究復雜工程系統涌現行為的通用的模型和求解框架，其基于分散控制的思想，能充分挖掘智能體的局部信息指導智能體的進化，同時，在系統進化過程中，可以結合多種求解策略，特別是結合具體問題的特征，根據環境的變化有針對性的設計智能體相應的規則，具有靈活性，適應性與魯棒性的優點，大大提高求解問題的能力。

自組織技術在工程中的應用中，大多數是利用自組織系統進行系統模擬與預測。而在工程優化領域應用的較少。對于設計自組織涌現系統應用于工程優化問題，其關鍵問題在于如何設計個體局部相互作用，使得智能體的微觀行為能涌現所要求的宏觀性能[7]。然而，由于自組織涌現的具有新穎性以及難以預測性，使得自組織系統的應用于工程優化設計很難實現。因為我們很難根據想要的系統優化設計目標來推斷出局部作用規則。

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

5 總結與展望

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

相比于自上而下設計的智能算法，自組織涌現的方法求解復雜工程優化問題更有優勢，但也存在一些問題和困難，今后的工作可以從自組織系統構建、鄰域結構設計、交互機制設計等方面做深入研究，使自組織求解成為復雜工程優化的高效的求解框架。

【參考文獻】

[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]黃紅兵.基于涌現視角的多 Agent 系統分析研究[D].長沙：國防科技大學，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.

[責任編輯：曹明明]