摘 要： 借鑒統(tǒng)計(jì)物理中對(duì)復(fù)雜系統(tǒng)自組織性的評(píng)估思想，基于協(xié)同進(jìn)化的涌現(xiàn)方法，提出了一種通用的多主體系統(tǒng)中涌現(xiàn)行為的定量評(píng)估模型，并指出如何將該模型的評(píng)估值作為復(fù)雜系統(tǒng)進(jìn)化的反饋。
關(guān)鍵詞： 定量評(píng)估模型 多主體系統(tǒng) 協(xié)同進(jìn)化算法
多主體系統(tǒng)MAS(Multi-Agent System）是目前人工智能、自適應(yīng)控制等諸多領(lǐng)域的一個(gè)研究熱點(diǎn)。作為復(fù)雜系統(tǒng)的一種抽象描述模型，MAS的涌現(xiàn)能力已特別引起研究者的關(guān)注。一般認(rèn)為，具有涌現(xiàn)性的系統(tǒng)能通過(guò)由多個(gè)自主體的局部行為的相互作用得到系統(tǒng)的全局行為與目標(biāo)，因而在理解各種復(fù)雜大規(guī)模問(wèn)題的機(jī)理并加以求解方面具有十分重要的意義。
由于針對(duì)MAS涌現(xiàn)的研究目前主要集中在涌現(xiàn)方法上，對(duì)系統(tǒng)涌現(xiàn)行為的評(píng)估幾乎空白。因此怎樣進(jìn)行MAS涌現(xiàn)行為的評(píng)估是一個(gè)亟待解決的問(wèn)題。本文針對(duì)這一不足，提出一種通用的多主體系統(tǒng)中涌現(xiàn)行為的定量評(píng)估模型。該模型借鑒統(tǒng)計(jì)物理中對(duì)復(fù)雜系統(tǒng)自組織性的評(píng)估思想，基于協(xié)同進(jìn)化的涌現(xiàn)方法，通過(guò)計(jì)算進(jìn)化系統(tǒng)的復(fù)雜度來(lái)對(duì)系統(tǒng)整體進(jìn)化行為進(jìn)行評(píng)估。并且，對(duì)怎樣將該模型的評(píng)估值作為復(fù)雜系統(tǒng)進(jìn)化的反饋及對(duì)該模型的定量性、合理性和通用性進(jìn)行了分析。實(shí)驗(yàn)結(jié)果證明，本文的方法可以對(duì)MAS涌現(xiàn)行為進(jìn)行有效的評(píng)估。
1 系統(tǒng)的體系結(jié)構(gòu)
包含協(xié)同進(jìn)化與定量評(píng)估模型的復(fù)雜問(wèn)題求解系統(tǒng)的總體思想是：借鑒復(fù)雜性科學(xué)的研究思路，用生態(tài)種群協(xié)同進(jìn)化實(shí)現(xiàn)系統(tǒng)行為的涌現(xiàn)，再用定量評(píng)估模型來(lái)指導(dǎo)系統(tǒng)的涌現(xiàn)過(guò)程，其體系結(jié)構(gòu)如圖1所示。
在涌現(xiàn)方法研究中，首先用MAS來(lái)對(duì)應(yīng)復(fù)雜問(wèn)題，然后建立一個(gè)生態(tài)多種群協(xié)同進(jìn)化環(huán)境來(lái)對(duì)應(yīng)MAS，再用生態(tài)種群協(xié)同進(jìn)化來(lái)調(diào)控MAS的演化行為。在定量評(píng)估模型研究中，首先構(gòu)建MAS的涌現(xiàn)評(píng)估模型，然后進(jìn)一步利用評(píng)估結(jié)果作為涌現(xiàn)中Agent層和系統(tǒng)層的反饋來(lái)指導(dǎo)系統(tǒng)涌現(xiàn)出適當(dāng)?shù)恼w行為。
2 多主體系統(tǒng)中涌現(xiàn)行為的定量評(píng)估模型
2.1 定量評(píng)估模型的構(gòu)建
借鑒統(tǒng)計(jì)物理中對(duì)復(fù)雜系統(tǒng)自組織性的評(píng)估思想，參考Smith[3][4]等人定量評(píng)估抽象物理系統(tǒng)自組織性（復(fù)雜性）的方法，本文的MAS涌現(xiàn)定量評(píng)估模型按如下步驟構(gòu)建。
(1)記錄子群進(jìn)化軌跡的矩陣
矩陣Z記錄了系統(tǒng)中N個(gè)Agent經(jīng)過(guò)M代的進(jìn)化軌跡。
gi表示進(jìn)化到第i代時(shí)，彼此之間相互關(guān)聯(lián)的所有Agent的局部行為向量，即協(xié)同進(jìn)化中第i代的所有子群個(gè)體特征向量；nij表示第j代中第i個(gè)Agent的個(gè)體特征值，這里可以用遺傳算法中個(gè)體基因編碼的函數(shù)表示。
該矩陣記錄了每個(gè)子群的整個(gè)進(jìn)化歷程，提供了評(píng)估模型要分析的數(shù)據(jù)集合。
(2)計(jì)算矩陣的奇異值
奇異值的定義：設(shè)矩陣A∈Cm*n。A*A的特征值的非負(fù)平方根稱作A的奇異值；A的奇異值的全體記作?滓(A)。
奇異值的定理：矩陣的非零奇異值的個(gè)數(shù)就等于矩陣的秩rank(A)。
按照奇異值的定義計(jì)算出矩陣Z的奇異值向量，然后按如下公式計(jì)算出
′：
由奇異值的定義及定理可以看出：復(fù)雜程度小的系統(tǒng)產(chǎn)生的矩陣對(duì)應(yīng)的有意義的大于0的′值個(gè)數(shù)少，反之則多，這可以與復(fù)雜系統(tǒng)的熵相對(duì)應(yīng)。
(3)計(jì)算熵
要通過(guò)矩陣的奇異值向量得到單一量化的值還需要進(jìn)一步的計(jì)算。在上面的計(jì)算結(jié)果得到的向量′的基礎(chǔ)上，用如下的公式計(jì)算出香農(nóng)熵（shannon entrophy）S：
(4)計(jì)算自由度
用如下的公式計(jì)算出自由度Ω：Ω=2S
計(jì)算的結(jié)果用于衡量系統(tǒng)復(fù)雜程度。
2.2 定量評(píng)估模型反饋指導(dǎo)演化涌現(xiàn)的方法
將評(píng)估模型與演化涌現(xiàn)結(jié)合，目的是用評(píng)估結(jié)果指導(dǎo)演化過(guò)程。
如圖1所示，這里的反饋分二層進(jìn)行：①將評(píng)估值反饋?zhàn)饔迷谙到y(tǒng)行為層，可基于評(píng)估值對(duì)多Agent的關(guān)聯(lián)特征參數(shù)作進(jìn)一步優(yōu)化，即調(diào)整子群間協(xié)同進(jìn)化合作與競(jìng)爭(zhēng)參數(shù)，從而獲得滿足要求的系統(tǒng)行為。②將評(píng)估值反饋?zhàn)饔迷趩蜛gent進(jìn)化層次，對(duì)單Agent的局部進(jìn)化參數(shù)作進(jìn)一步優(yōu)化，即調(diào)整單Agent選擇、交叉、變異參數(shù)，從而獲得滿足要求的單Agent進(jìn)化行為。
2.3 定量評(píng)估模型的分析
(1)定量性
不同于一般的定性分析，本文的模型基于動(dòng)態(tài)系統(tǒng)理論，給出一種基于系統(tǒng)熵的定量評(píng)估方法。此方法的優(yōu)點(diǎn)為：
①該定量評(píng)估模型依賴于多個(gè)Agent的局部進(jìn)化行為、Agent之間的相互關(guān)聯(lián)特征及生存環(huán)境(資源)，可以分析評(píng)估值的變化與系統(tǒng)描述參數(shù)的對(duì)應(yīng)關(guān)系及與系統(tǒng)各種行為的對(duì)應(yīng)關(guān)系，從而可以定量評(píng)估系統(tǒng)涌現(xiàn)出的不同行為。
②可以考察模型中參數(shù)取值與系統(tǒng)整體行為的相互影響，找出系統(tǒng)行為轉(zhuǎn)換的相變點(diǎn)或臨界區(qū)域，深入探討復(fù)雜系統(tǒng)的涌現(xiàn)機(jī)理。
(2)合理性
Smith等人提出的抽象物理系統(tǒng)中的定量評(píng)估模型[3][4]是以非線性的二維粒子的復(fù)雜運(yùn)動(dòng)為研究對(duì)象，構(gòu)建記錄系統(tǒng)粒子運(yùn)動(dòng)特性的矩陣。其中行向量記錄了每個(gè)粒子的速度、位置屬性；列向量記錄了某一粒子某一屬性隨時(shí)間的變化情況。例如xi j、yi j、xi j、yi j，分別表示粒子j在第i時(shí)刻時(shí)x、y方向的位置、速度值。然后采用與上述模型類(lèi)似的計(jì)算過(guò)程計(jì)算出系統(tǒng)的自由度，從而與不同的系統(tǒng)涌現(xiàn)行為相對(duì)應(yīng)。實(shí)驗(yàn)證明，這種方法在抽象物理系統(tǒng)中是一種可行的系統(tǒng)涌現(xiàn)評(píng)估方法。
本文模型與Smith提出的模型的區(qū)別主要在構(gòu)建記錄子群進(jìn)化軌跡的矩陣。通過(guò)分析基于生態(tài)種群協(xié)同進(jìn)化方法實(shí)現(xiàn)的多主體系統(tǒng)的涌現(xiàn)行為，將所有粒子的運(yùn)動(dòng)屬性對(duì)應(yīng)到本文的MAS系統(tǒng)的單個(gè)Agent的局部行為向量；粒子間復(fù)雜的非線性關(guān)系對(duì)應(yīng)到本文的單個(gè)Agent相互關(guān)聯(lián)特性，即協(xié)同進(jìn)化的合作與競(jìng)爭(zhēng)關(guān)系；粒子隨時(shí)間的位移對(duì)應(yīng)到本文的MAS系統(tǒng)每一代的進(jìn)化軌跡。
通過(guò)上述的對(duì)應(yīng)關(guān)系，實(shí)現(xiàn)了抽象物理系統(tǒng)的定量評(píng)估方法與基于生態(tài)種群協(xié)同進(jìn)化的MAS涌現(xiàn)方法的有效結(jié)合，從而充分體現(xiàn)了本文的MAS涌現(xiàn)行為的定量評(píng)估模型的合理性。
(3)通用性
從評(píng)估矩陣的構(gòu)建和系統(tǒng)自由度的計(jì)算過(guò)程可以看出，評(píng)估結(jié)果只依賴于個(gè)體的局部狀態(tài)變量，與具體進(jìn)化算法無(wú)關(guān)。因此，只要個(gè)體的特性值選擇合理，本文的模型對(duì)采用任意進(jìn)化算法的MAS系統(tǒng)都是適用的。
3 實(shí)驗(yàn)結(jié)果分析
這里選取了二種不同的協(xié)同進(jìn)化算法。一種算法使得每個(gè)Agent進(jìn)化過(guò)程中采用的交叉、變異算子效果明顯，另一種則相反。而且選擇操作采用保留最佳個(gè)體的策略，然后按照上述評(píng)估模型求得系統(tǒng)自由度，即系統(tǒng)進(jìn)化復(fù)雜程度分別為：系統(tǒng)1的Ω=1.3886e+105；系統(tǒng)2的Ω=1.8544e-040。
圖2～圖4給出了采用二種不同協(xié)同進(jìn)化算法時(shí)，系統(tǒng)的求解效果、奇異值和子群進(jìn)化曲線的比較。其中，圖2記錄了采用二種不同的協(xié)同進(jìn)化算法，進(jìn)化代數(shù)為100代時(shí)的進(jìn)化結(jié)果圖；圖3記錄了二種不同的協(xié)同進(jìn)化條件下計(jì)算出的系統(tǒng)奇異值，縱坐標(biāo)記錄了奇異值的對(duì)數(shù)，并將100個(gè)奇異值按照從大到小的順序排列；圖4記錄了采用二種不同的協(xié)同進(jìn)化算法得到的所有Agent進(jìn)化過(guò)程的特性值曲線，Agent數(shù)量為16，對(duì)應(yīng)了每個(gè)小圖的16條不同的曲線，曲線上的每一點(diǎn)對(duì)應(yīng)了該Agent進(jìn)化到當(dāng)前代時(shí)的特性值。
從圖2中可以看出，這二種不同的協(xié)同進(jìn)化系統(tǒng)求解的效果基本相同。但從圖4中可以看出系統(tǒng)復(fù)雜程度有著顯著的差別，系統(tǒng)1的復(fù)雜程度明顯高于系統(tǒng)2，相應(yīng)計(jì)算出的系統(tǒng)復(fù)雜性評(píng)估值Ω相差上百個(gè)數(shù)量級(jí)。從圖3中可以看出，系統(tǒng)1中對(duì)系統(tǒng)復(fù)雜性評(píng)估產(chǎn)生重要作用的奇異值的個(gè)數(shù)（即奇異值取對(duì)數(shù)后值大于0的個(gè)數(shù)）明顯多于系統(tǒng)2，其作用效果（即奇異值取對(duì)數(shù)后的值的大?。┟黠@大于系統(tǒng)2。
將系統(tǒng)的奇異值曲線圖、子群進(jìn)化復(fù)雜程度曲線圖和計(jì)算所得的系統(tǒng)進(jìn)化復(fù)雜性程度評(píng)估值?贅相對(duì)照，可以得出以下結(jié)論：子群的進(jìn)化曲線變化幅度大的系統(tǒng)奇異值的作用效果顯著且有意義的奇異值個(gè)數(shù)較多，從而通過(guò)模型計(jì)算得到的系統(tǒng)復(fù)雜性評(píng)估值較大，反之則相反。因此本文的定量評(píng)估模型計(jì)算出的系統(tǒng)復(fù)雜性評(píng)估值有效地反映了實(shí)際系統(tǒng)的復(fù)雜程度。
4 結(jié)束語(yǔ)
目前國(guó)內(nèi)外針對(duì)MAS的涌現(xiàn)研究主要集中在涌現(xiàn)方法上，對(duì)系統(tǒng)整體涌現(xiàn)行為如何評(píng)估幾乎是空白。針對(duì)具體的復(fù)雜系統(tǒng)，系統(tǒng)的進(jìn)化不僅要實(shí)現(xiàn)高效率，進(jìn)化過(guò)程中系統(tǒng)的復(fù)雜程度也是衡量進(jìn)化算法好壞的重要指標(biāo)。本文的模型提出了一種解決此類(lèi)問(wèn)題的通用的方法。當(dāng)然，目前的研究只是對(duì)這種將統(tǒng)計(jì)物理中有關(guān)復(fù)雜系統(tǒng)自組織性的評(píng)估應(yīng)用到多主體系統(tǒng)定量評(píng)估的思想方法的初步嘗試，提出的是一種通用的定量評(píng)估模型。
下一步的研究主要是針對(duì)特定的應(yīng)用背景，具體實(shí)現(xiàn)本文的進(jìn)化算法及在具體條件下Agent的相互關(guān)聯(lián)特性和Agent的局部進(jìn)化行為向量，構(gòu)建評(píng)估矩陣并實(shí)現(xiàn)反饋，引導(dǎo)系統(tǒng)涌現(xiàn)出符合要求的整體行為。
參考文獻(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