摘 要： 借鑒統(tǒng)計物理中對復(fù)雜系統(tǒng)自組織性的評估思想，基于協(xié)同進化的涌現(xiàn)方法，提出了一種通用的多主體系統(tǒng)中涌現(xiàn)行為的定量評估模型，并指出如何將該模型的評估值作為復(fù)雜系統(tǒng)進化的反饋。
關(guān)鍵詞： 定量評估模型 多主體系統(tǒng) 協(xié)同進化算法
多主體系統(tǒng)MAS(Multi-Agent System）是目前人工智能、自適應(yīng)控制等諸多領(lǐng)域的一個研究熱點。作為復(fù)雜系統(tǒng)的一種抽象描述模型，MAS的涌現(xiàn)能力已特別引起研究者的關(guān)注。一般認為，具有涌現(xiàn)性的系統(tǒng)能通過由多個自主體的局部行為的相互作用得到系統(tǒng)的全局行為與目標(biāo)，因而在理解各種復(fù)雜大規(guī)模問題的機理并加以求解方面具有十分重要的意義。
由于針對MAS涌現(xiàn)的研究目前主要集中在涌現(xiàn)方法上，對系統(tǒng)涌現(xiàn)行為的評估幾乎空白。因此怎樣進行MAS涌現(xiàn)行為的評估是一個亟待解決的問題。本文針對這一不足，提出一種通用的多主體系統(tǒng)中涌現(xiàn)行為的定量評估模型。該模型借鑒統(tǒng)計物理中對復(fù)雜系統(tǒng)自組織性的評估思想，基于協(xié)同進化的涌現(xiàn)方法，通過計算進化系統(tǒng)的復(fù)雜度來對系統(tǒng)整體進化行為進行評估。并且，對怎樣將該模型的評估值作為復(fù)雜系統(tǒng)進化的反饋及對該模型的定量性、合理性和通用性進行了分析。實驗結(jié)果證明，本文的方法可以對MAS涌現(xiàn)行為進行有效的評估。
1 系統(tǒng)的體系結(jié)構(gòu)
包含協(xié)同進化與定量評估模型的復(fù)雜問題求解系統(tǒng)的總體思想是：借鑒復(fù)雜性科學(xué)的研究思路，用生態(tài)種群協(xié)同進化實現(xiàn)系統(tǒng)行為的涌現(xiàn)，再用定量評估模型來指導(dǎo)系統(tǒng)的涌現(xiàn)過程，其體系結(jié)構(gòu)如圖1所示。
在涌現(xiàn)方法研究中，首先用MAS來對應(yīng)復(fù)雜問題，然后建立一個生態(tài)多種群協(xié)同進化環(huán)境來對應(yīng)MAS，再用生態(tài)種群協(xié)同進化來調(diào)控MAS的演化行為。在定量評估模型研究中，首先構(gòu)建MAS的涌現(xiàn)評估模型，然后進一步利用評估結(jié)果作為涌現(xiàn)中Agent層和系統(tǒng)層的反饋來指導(dǎo)系統(tǒng)涌現(xiàn)出適當(dāng)?shù)恼w行為。
2 多主體系統(tǒng)中涌現(xiàn)行為的定量評估模型
2.1 定量評估模型的構(gòu)建
借鑒統(tǒng)計物理中對復(fù)雜系統(tǒng)自組織性的評估思想，參考Smith[3][4]等人定量評估抽象物理系統(tǒng)自組織性（復(fù)雜性）的方法，本文的MAS涌現(xiàn)定量評估模型按如下步驟構(gòu)建。
(1)記錄子群進化軌跡的矩陣
矩陣Z記錄了系統(tǒng)中N個Agent經(jīng)過M代的進化軌跡。
gi表示進化到第i代時，彼此之間相互關(guān)聯(lián)的所有Agent的局部行為向量，即協(xié)同進化中第i代的所有子群個體特征向量；nij表示第j代中第i個Agent的個體特征值，這里可以用遺傳算法中個體基因編碼的函數(shù)表示。
該矩陣記錄了每個子群的整個進化歷程，提供了評估模型要分析的數(shù)據(jù)集合。
(2)計算矩陣的奇異值
奇異值的定義：設(shè)矩陣A∈Cm*n。A*A的特征值的非負平方根稱作A的奇異值；A的奇異值的全體記作?滓(A)。
奇異值的定理：矩陣的非零奇異值的個數(shù)就等于矩陣的秩rank(A)。
按照奇異值的定義計算出矩陣Z的奇異值向量，然后按如下公式計算出
′：
由奇異值的定義及定理可以看出：復(fù)雜程度小的系統(tǒng)產(chǎn)生的矩陣對應(yīng)的有意義的大于0的′值個數(shù)少，反之則多，這可以與復(fù)雜系統(tǒng)的熵相對應(yīng)。
(3)計算熵
要通過矩陣的奇異值向量得到單一量化的值還需要進一步的計算。在上面的計算結(jié)果得到的向量′的基礎(chǔ)上，用如下的公式計算出香農(nóng)熵（shannon entrophy）S：
(4)計算自由度
用如下的公式計算出自由度Ω：Ω=2S
計算的結(jié)果用于衡量系統(tǒng)復(fù)雜程度。
2.2 定量評估模型反饋指導(dǎo)演化涌現(xiàn)的方法
將評估模型與演化涌現(xiàn)結(jié)合，目的是用評估結(jié)果指導(dǎo)演化過程。
如圖1所示，這里的反饋分二層進行：①將評估值反饋作用在系統(tǒng)行為層，可基于評估值對多Agent的關(guān)聯(lián)特征參數(shù)作進一步優(yōu)化，即調(diào)整子群間協(xié)同進化合作與競爭參數(shù)，從而獲得滿足要求的系統(tǒng)行為。②將評估值反饋作用在單Agent進化層次，對單Agent的局部進化參數(shù)作進一步優(yōu)化，即調(diào)整單Agent選擇、交叉、變異參數(shù)，從而獲得滿足要求的單Agent進化行為。
2.3 定量評估模型的分析
(1)定量性
不同于一般的定性分析，本文的模型基于動態(tài)系統(tǒng)理論，給出一種基于系統(tǒng)熵的定量評估方法。此方法的優(yōu)點為：
①該定量評估模型依賴于多個Agent的局部進化行為、Agent之間的相互關(guān)聯(lián)特征及生存環(huán)境(資源)，可以分析評估值的變化與系統(tǒng)描述參數(shù)的對應(yīng)關(guān)系及與系統(tǒng)各種行為的對應(yīng)關(guān)系，從而可以定量評估系統(tǒng)涌現(xiàn)出的不同行為。
?、诳梢钥疾炷Ｐ椭袇?shù)取值與系統(tǒng)整體行為的相互影響，找出系統(tǒng)行為轉(zhuǎn)換的相變點或臨界區(qū)域，深入探討復(fù)雜系統(tǒng)的涌現(xiàn)機理。
(2)合理性
Smith等人提出的抽象物理系統(tǒng)中的定量評估模型[3][4]是以非線性的二維粒子的復(fù)雜運動為研究對象，構(gòu)建記錄系統(tǒng)粒子運動特性的矩陣。其中行向量記錄了每個粒子的速度、位置屬性；列向量記錄了某一粒子某一屬性隨時間的變化情況。例如xi j、yi j、xi j、yi j，分別表示粒子j在第i時刻時x、y方向的位置、速度值。然后采用與上述模型類似的計算過程計算出系統(tǒng)的自由度，從而與不同的系統(tǒng)涌現(xiàn)行為相對應(yīng)。實驗證明，這種方法在抽象物理系統(tǒng)中是一種可行的系統(tǒng)涌現(xiàn)評估方法。
本文模型與Smith提出的模型的區(qū)別主要在構(gòu)建記錄子群進化軌跡的矩陣。通過分析基于生態(tài)種群協(xié)同進化方法實現(xiàn)的多主體系統(tǒng)的涌現(xiàn)行為，將所有粒子的運動屬性對應(yīng)到本文的MAS系統(tǒng)的單個Agent的局部行為向量；粒子間復(fù)雜的非線性關(guān)系對應(yīng)到本文的單個Agent相互關(guān)聯(lián)特性，即協(xié)同進化的合作與競爭關(guān)系；粒子隨時間的位移對應(yīng)到本文的MAS系統(tǒng)每一代的進化軌跡。
通過上述的對應(yīng)關(guān)系，實現(xiàn)了抽象物理系統(tǒng)的定量評估方法與基于生態(tài)種群協(xié)同進化的MAS涌現(xiàn)方法的有效結(jié)合，從而充分體現(xiàn)了本文的MAS涌現(xiàn)行為的定量評估模型的合理性。
(3)通用性
從評估矩陣的構(gòu)建和系統(tǒng)自由度的計算過程可以看出，評估結(jié)果只依賴于個體的局部狀態(tài)變量，與具體進化算法無關(guān)。因此，只要個體的特性值選擇合理，本文的模型對采用任意進化算法的MAS系統(tǒng)都是適用的。
3 實驗結(jié)果分析
這里選取了二種不同的協(xié)同進化算法。一種算法使得每個Agent進化過程中采用的交叉、變異算子效果明顯，另一種則相反。而且選擇操作采用保留最佳個體的策略，然后按照上述評估模型求得系統(tǒng)自由度，即系統(tǒng)進化復(fù)雜程度分別為：系統(tǒng)1的Ω=1.3886e+105；系統(tǒng)2的Ω=1.8544e-040。
圖2～圖4給出了采用二種不同協(xié)同進化算法時，系統(tǒng)的求解效果、奇異值和子群進化曲線的比較。其中，圖2記錄了采用二種不同的協(xié)同進化算法，進化代數(shù)為100代時的進化結(jié)果圖；圖3記錄了二種不同的協(xié)同進化條件下計算出的系統(tǒng)奇異值，縱坐標(biāo)記錄了奇異值的對數(shù)，并將100個奇異值按照從大到小的順序排列；圖4記錄了采用二種不同的協(xié)同進化算法得到的所有Agent進化過程的特性值曲線，Agent數(shù)量為16，對應(yīng)了每個小圖的16條不同的曲線，曲線上的每一點對應(yīng)了該Agent進化到當(dāng)前代時的特性值。
從圖2中可以看出，這二種不同的協(xié)同進化系統(tǒng)求解的效果基本相同。但從圖4中可以看出系統(tǒng)復(fù)雜程度有著顯著的差別，系統(tǒng)1的復(fù)雜程度明顯高于系統(tǒng)2，相應(yīng)計算出的系統(tǒng)復(fù)雜性評估值Ω相差上百個數(shù)量級。從圖3中可以看出，系統(tǒng)1中對系統(tǒng)復(fù)雜性評估產(chǎn)生重要作用的奇異值的個數(shù)（即奇異值取對數(shù)后值大于0的個數(shù)）明顯多于系統(tǒng)2，其作用效果（即奇異值取對數(shù)后的值的大小）明顯大于系統(tǒng)2。
將系統(tǒng)的奇異值曲線圖、子群進化復(fù)雜程度曲線圖和計算所得的系統(tǒng)進化復(fù)雜性程度評估值?贅相對照，可以得出以下結(jié)論：子群的進化曲線變化幅度大的系統(tǒng)奇異值的作用效果顯著且有意義的奇異值個數(shù)較多，從而通過模型計算得到的系統(tǒng)復(fù)雜性評估值較大，反之則相反。因此本文的定量評估模型計算出的系統(tǒng)復(fù)雜性評估值有效地反映了實際系統(tǒng)的復(fù)雜程度。
4 結(jié)束語
目前國內(nèi)外針對MAS的涌現(xiàn)研究主要集中在涌現(xiàn)方法上，對系統(tǒng)整體涌現(xiàn)行為如何評估幾乎是空白。針對具體的復(fù)雜系統(tǒng)，系統(tǒng)的進化不僅要實現(xiàn)高效率，進化過程中系統(tǒng)的復(fù)雜程度也是衡量進化算法好壞的重要指標(biāo)。本文的模型提出了一種解決此類問題的通用的方法。當(dāng)然，目前的研究只是對這種將統(tǒng)計物理中有關(guān)復(fù)雜系統(tǒng)自組織性的評估應(yīng)用到多主體系統(tǒng)定量評估的思想方法的初步嘗試，提出的是一種通用的定量評估模型。
下一步的研究主要是針對特定的應(yīng)用背景，具體實現(xiàn)本文的進化算法及在具體條件下Agent的相互關(guān)聯(lián)特性和Agent的局部進化行為向量，構(gòu)建評估矩陣并實現(xiàn)反饋，引導(dǎo)系統(tǒng)涌現(xiàn)出符合要求的整體行為。
參考文獻
1 Yong C H，Miikkulainen R.Cooperative Coevolution of Multi-Agent Systems.Systems Technical，2001；Report AI01-287
2 Dagaeff T，Chantemargue F，Hirsbrunner B.Emergence-based Cooperation in a Multi-Agent System.In：Proceedings of the Second European Conference on Cognitive Science(ECCS′97).Manchester，U.K，1997
3 Wright W A，Smith R E，Danek M A et al.A Measure of Emergence in an Adapting，Multi-Agent Context.In：Proc. of 6th Int.Conf.of Simulation of Adaptive Behavior. Honolulu，USA，2000
4 Wright W A，Smith R E，Danek M.A Generalisable Measure of Self-Organization and emergence.In：Proceedings of Artificial Neural Networks.Springer Verlag，2001：857
5 Shimoyama N，Sugawara K，Mizuguchi T.Collective Motion in Systems of Mobile Elements.Physical Review Letters，1996；58：6480