多主體群體行為的信息論測(cè)量指標(biāo)

摘要多主體系統(tǒng)是目前人工智能研究的熱點(diǎn)之一，多個(gè)主體通過(guò)協(xié)調(diào)和通訊這些自組織過(guò)程完成單一主體很難完成的功能。但是，如何定量分析主體在自組織過(guò)程中的行為和它們的相互作用是一個(gè)比較困難的問(wèn)題。我們提出了一種基于信息論的定量分析多主體系統(tǒng)群體行為的方法，通過(guò)多主體系統(tǒng)中所有主體信息熵的均值分析多主體系統(tǒng)的整體行為，并通過(guò)主體對(duì)之間的互信息分析多主體系統(tǒng)中主體間的相互作用。通過(guò)粘液菌模型進(jìn)行的驗(yàn)證實(shí)驗(yàn)表明所提出的方法可以定量分析主體的行為模式。

關(guān)鍵詞群體行為 多主體系統(tǒng) 信息理論

中圖分類號(hào):TP3文獻(xiàn)標(biāo)識(shí)碼:A

0 引言

自上世紀(jì)九十年代以來(lái)，隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的發(fā)展，智能主體和多主體成為人工智能研究的一個(gè)熱點(diǎn)，它可望將人類從浩瀚無(wú)邊的信息海洋中解放出來(lái)，使用戶只關(guān)注自己感興趣的信息。目前，智能主體技術(shù)已在決策支持、①故障診斷、②商業(yè)市場(chǎng)建模③等很多領(lǐng)域得到成功應(yīng)用。在很多情況下，我們所使用的主體都不只一個(gè)，多主體系統(tǒng)研究一組自治主體之間智能行為的協(xié)調(diào)，讓很多智能主體協(xié)同在一起為完成一個(gè)共同的目標(biāo)服務(wù)，這些自主主體通過(guò)主體間以及主體與環(huán)境間的相互作用進(jìn)行合作。④

每個(gè)智能主體都有自己的獨(dú)立目標(biāo)，但從整體上看，多主體系統(tǒng)表現(xiàn)為一個(gè)整體。因此，研究單獨(dú)主體的局部行為與多主體系統(tǒng)總體行為的一致性對(duì)設(shè)計(jì)多主體系統(tǒng)是非常重要的。在衡量一個(gè)多主體系統(tǒng)時(shí)，人們常使用目標(biāo)完成比例和目標(biāo)完成代價(jià)作為衡量系統(tǒng)整體行為的測(cè)量指標(biāo)。這些測(cè)量指標(biāo)從主體們需要完成其任務(wù)的角度來(lái)看是非常重要的。但是，這些測(cè)量標(biāo)準(zhǔn)對(duì)弄清楚多主體系統(tǒng)中各個(gè)主體的行為是不夠的，因?yàn)楹茈y說(shuō)清楚一個(gè)主體為什么會(huì)得到高分以及它是如何得到高分的。而且這兩個(gè)測(cè)量指標(biāo)對(duì)不同的系統(tǒng)其標(biāo)度也不相同，不利于不同系統(tǒng)間進(jìn)行比較。

熱力學(xué)第二定律指出如沒(méi)有外部能量的作用系統(tǒng)總是趨向于無(wú)序，而多主體系統(tǒng)局部行為與總體行為的一致性表明系統(tǒng)在自組織狀態(tài)下是趨于有序的。使多主體系統(tǒng)有序化的原因是因?yàn)樾畔⒌募尤耄畔㈧厥且环N廣泛使用的量度信息的方法，因此有研究者提出可使用信息熵來(lái)分析多主體系統(tǒng)的動(dòng)態(tài)自組織行為。⑤⑥⑦我們?cè)诒疚闹刑岢隽艘环N新的基于信息論的定量分析多主體系統(tǒng)的方法，其在于分析系統(tǒng)的自組織行為及主體間的相互作用。我們所提出方法與其他方法的不同之處在于該方法不僅可定量分析系統(tǒng)的整體行為而且可以定量分析主體間相互作用的強(qiáng)度。

1 主體間相互作用

一般認(rèn)為主體間的相互作用等同于交換主體狀態(tài)的信息。由信息理論我們可以知道多主體系統(tǒng)中信息和熵之間的關(guān)系，信息增加將引起熵的減少，而信息減少將引起熵的增加。因此，可通過(guò)熵來(lái)度量主體的相互作用和自組織行為。

考慮一個(gè)多主體系統(tǒng)S，它具有N個(gè)主體s1，…sn，…sN，這些主體之間按概率規(guī)則互相聯(lián)系、互相制約。各個(gè)主體的出現(xiàn)概率分別是p1，…pn，…pN。可通過(guò)這些主體的概率函數(shù)――熵來(lái)描述S的不確定性:

H(S) = -pnlogpn

當(dāng)滿足條件pn = ，n=1，…，N時(shí)，H(S)取最大值，記為H0，即H0 = [H(S)]max = logN。它表示系統(tǒng)具有最大的不確定性，各個(gè)元素完全以隨機(jī)的方式，互相無(wú)關(guān)的實(shí)現(xiàn)。

因?yàn)橹黧w出現(xiàn)的概率我們很難得到，以上的計(jì)算公式雖容易理解但不方便計(jì)算。我們使用各個(gè)主體熵的平均值來(lái)分析多主體系統(tǒng)的整體行為，例如:穩(wěn)定性、約束或復(fù)雜性;由信息論我們知道，互信息意味著兩個(gè)隨機(jī)變量間信息交流的強(qiáng)度，如果兩個(gè)隨機(jī)變量是完全獨(dú)立的，那么他們之間的互信息為零。因此，我們使用每個(gè)主體對(duì)的互信息來(lái)分析兩個(gè)主體相互作用的強(qiáng)度。

當(dāng)計(jì)算這兩個(gè)指標(biāo)時(shí)，需要知道主體的狀態(tài)。一個(gè)主體是一個(gè)獨(dú)立的自治體，它通過(guò)傳感器從環(huán)境中得到輸入并通過(guò)一個(gè)決策過(guò)程輸出結(jié)果，但主體的決策過(guò)程依賴于它的內(nèi)部行為模式，不同的系統(tǒng)其內(nèi)部行為模式可完全不同。為了在分析主體的行為時(shí)不局限于特定的系統(tǒng)，使用主體的內(nèi)部行為模式參數(shù)是不合適的，為此我們使用主體的輸入和輸出作為主體的狀態(tài)。

為計(jì)算熵和互信息我們需要:

(1)主體X的狀態(tài)集x∈{x1，…，xn}(也就是輸入和輸出);

(2)主體X處于某一個(gè)狀態(tài)的概率p(x)。

一個(gè)主體X的熵以及X主體Y和間的互信息可定義如下:

H(X) = -p(x)logp(x)

I(X:Y) = p(x，y)log

2 信息學(xué)測(cè)量指標(biāo)

為校驗(yàn)以上方法的可行性，我們通過(guò)一個(gè)簡(jiǎn)單的自組織模型―粘液菌模型(Slime Mold Model)對(duì)以上概念進(jìn)行實(shí)驗(yàn)。

2.1 粘液菌模型

粘液菌細(xì)胞的群體行為在自組織系統(tǒng)中研究很多。⑧通常，它們作為獨(dú)立的變形蟲利用它們的偽足四處移動(dòng)，其行動(dòng)符合隨機(jī)規(guī)律。但當(dāng)環(huán)境條件惡化時(shí)，這些變形蟲突然改變了它們的行為并聚合為一個(gè)單一的多細(xì)胞體。在這個(gè)聚合過(guò)程中，它們發(fā)出一種稱為cAMP的化學(xué)信號(hào)來(lái)引導(dǎo)群體運(yùn)動(dòng)。當(dāng)它們移動(dòng)時(shí)，它們隨著環(huán)境中cAMP的變化而移動(dòng)。整個(gè)聚合過(guò)程是一個(gè)自組織過(guò)程，盡管所有的變形蟲根據(jù)其自身的局部信息行動(dòng)，但它們最終會(huì)自動(dòng)聚合到一起。

在粘液菌模型中，變形蟲主體被置于圖1所示的網(wǎng)格中。主體及其環(huán)境模型描述如下:

圖1粘液菌模型環(huán)境

2.1.1 主體模型

每個(gè)主體按照以下的步驟工作:(1)cAMP放在當(dāng)前格中;(2)在8個(gè)鄰域中嗅探前向三個(gè)網(wǎng)格的cAMP濃度;(3)動(dòng)到具有最強(qiáng)cAMP濃度的網(wǎng)格。

2.1.2 環(huán)境模型

在周圍環(huán)境中，cAMP被表示為T(x，y)和P(x，y)，其中T(x，y)表示網(wǎng)格(x，y)上cAMP的數(shù)量，而P(x，y)表示網(wǎng)格(x，y)上cAMP的濃度。主體可以在網(wǎng)格上嗅探cAMP的濃度。

隨著時(shí)間的推移，cAMP會(huì)揮發(fā)和擴(kuò)散，每一步完成后，T(x，y)和P(x，y)變成T*(x，y)和P*(x，y)

T*(x，y) = (1-γeva)T(x，y)+△T

如果有一個(gè)代理在網(wǎng)格(x，y)上，其他情況

P*(x，y) = P(x，y) + γdif{P(x-1，y)+P(x+1，y)

+P(x，y-1)+P(x，y+1)-5P(x，y)}+γevaT(x，y)

其中Q表示主體在第一步釋放的cAMP數(shù)量，而γeva和γdif表示cAMP的揮發(fā)率和擴(kuò)散率。

2.2 粘液菌模型參數(shù)

在粘液菌模型中，由揮發(fā)率和擴(kuò)散率定義的cAMP屬性會(huì)影響主體的自組織過(guò)程模式。在我們的實(shí)驗(yàn)中，我們比較了不同的模式以及熵和互信息分布的關(guān)系。

實(shí)驗(yàn)環(huán)境是一個(gè)50×50的網(wǎng)格世界，共包含了50個(gè)主體。我們根據(jù)時(shí)間長(zhǎng)度和精度改變cAMP的屬性。揮發(fā)和擴(kuò)散率的值被設(shè)為以下四個(gè)不同的值:

a. γeva = 0.1，γdif = 0.1

b. γeva = 0.1，γdif = 0.3

c. γeva = 0.5，γdif = 0.1

d. γeva = 0.5，γdif = 0.3

我們使用這些參數(shù)進(jìn)行了1000步實(shí)驗(yàn)。

2.3 熵和互信息的計(jì)算

主體的輸入是主體前向方向上三個(gè)網(wǎng)格的cAMP的濃度，而輸出是主體的移動(dòng)方向，測(cè)量這些狀態(tài)需要觀察主體的每一步行動(dòng)。為了觀測(cè)這些概率，我們使用了蒙特卡洛方法，通過(guò)統(tǒng)計(jì)這些狀態(tài)在一個(gè)實(shí)驗(yàn)中各個(gè)步驟上的值來(lái)估計(jì)這些概率。

3 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)結(jié)果如表1所示:

表1粘液菌模型中主體的熵和互信息的分布情況

表1顯示了每一種參數(shù)(a~d)所對(duì)應(yīng)的熵和互信息。和V(I)表示隨機(jī)選擇的10對(duì)主體間互信息的均值和偏差，和V(H)表示所有主體的熵的均值和偏差。rId表示主體間歐式距離與互信息的相關(guān)系數(shù)。實(shí)驗(yàn)結(jié)果表明，當(dāng)選擇參數(shù)a和c時(shí)，互信息的均值要大于選擇參數(shù)b和d時(shí)。因此，選擇參數(shù)a和c時(shí)，主體之間的相互作用要強(qiáng)于選擇參數(shù)b和d時(shí)。當(dāng)選擇b和d時(shí)，熵的均值較小，表示主體的狀態(tài)是穩(wěn)定的。

通過(guò)運(yùn)行startLogo仿真程序，⑨我們可以觀察到:當(dāng)選擇參數(shù)a和c時(shí)，很多主體自組織為群體;而當(dāng)選擇參數(shù)b和d時(shí)，很多主體是獨(dú)立行動(dòng)的。這些主體的行為模式可以通過(guò)熵和互信息反映出來(lái)。同時(shí)，rId的值顯示當(dāng)兩個(gè)主體越近時(shí)，它們間的相互作用越強(qiáng)烈。

我們?cè)趯?shí)驗(yàn)過(guò)程中同時(shí)可以觀察到:當(dāng)選擇參數(shù)a和c時(shí)，因?yàn)橄嗷プ饔玫膹?qiáng)度，主體再構(gòu)成一個(gè)群體后隨即解體，構(gòu)成一個(gè)新的群體。而在選擇參數(shù)b和d時(shí)，當(dāng)主體構(gòu)成一個(gè)群體后，該群體很少被重構(gòu)。該行為模式與熵的分析結(jié)果一致，即主體的狀態(tài)在選擇參數(shù)b和d時(shí)比選擇a和c時(shí)穩(wěn)定。

4 結(jié)束語(yǔ)

研究主體的自組織行及主體間的相互作用對(duì)理解群體智能的作用機(jī)理具有重要作用。我們從信息論入手，提出了一種使用熵和互信息來(lái)定量分析主體間相互作用的方法。在粘液菌模型上進(jìn)行的實(shí)驗(yàn)結(jié)果驗(yàn)證了我們所提出的方法能夠定量表示主體的群體行為及它們之間的關(guān)系，表明我們所提出的方法是可行的。

★基金項(xiàng)目: 國(guó)家863計(jì)劃項(xiàng)目(2005AA12150)

注釋

①陳宏偉，袁國(guó)斌.基于多智能代理的分布式?jīng)Q策系統(tǒng)實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用研究，2002.18(8):46-50.

②李衛(wèi)寧.基于MAS的智能診斷技術(shù)集成方法研究[J].運(yùn)籌與管理，2005.14(5):13-17.

③周曉俊，張申生，周根春.基于約束的智能主體及其在自動(dòng)協(xié)商中的應(yīng)用[J].上海交通大學(xué)學(xué)報(bào)，2005.39(4):574-577.

④Wooldridge M，Introduction to MultiAgent Systems[M]， Chichester， UK， John Wiley Sons， 2002:46-58.

⑤Guerin S， Kunkle D， Emergence of Constraint in Self-Organizing Systems[J]. J. of Nonlinear Dynamics， Psychology， Life Sciences，2004.8(2):131-146.

⑥Parunak H V D， Brueckner S， Entropy and Self-organization in Multi-Agent Systems [C].Proceedings of the International Conference on Autonomous Agents. 2001:124-130.

⑦⑨Balch T， Hierarchic Social Entropy: An Information Theoretic Measure of Robot Team Diversity [J]，J. Autonomous Robots. 2000.8(3):209-237.

⑧Resnick M ， Turtles， Termits， and Traffic James: Explorations in Massively Parallel Microworlds [M]， Cambridge， US， MIT Press，1997:59-68.