網(wǎng)絡(luò)多agent模型定性分析*

李 艷 會(huì)

(中山大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，廣州 510275)

1 基礎(chǔ)知識(shí)

K.Lerman和 O.Shehory[1-4]提出電子交易多agent模型，考慮系統(tǒng)的聚集行為.假定在一個(gè)系統(tǒng)中每個(gè)agent都給定一個(gè)任務(wù)，以最低價(jià)購(gòu)買貨物；假定所有的 agent都知道提供商品的供應(yīng)商的位置和商品的零售價(jià)，多個(gè) agent可以聚集在一起形成一個(gè)大的客戶來(lái)批發(fā)商品，商品的價(jià)格隨批發(fā)量的增多而降低，但有一個(gè)最低價(jià)格，也就是說(shuō)批發(fā)量有最大值.因此，各 agent到處游走，在各供應(yīng)商處集聚形成較大的批發(fā)商，稱之為隊(duì)列，單個(gè) agent可以自己選擇加入哪一個(gè)供應(yīng)商隊(duì)列，也可以從一個(gè)已經(jīng)形成的批發(fā)商處轉(zhuǎn)移到其他批發(fā)商處.分析系統(tǒng)中 agent的這些行為，xi是t時(shí)刻系統(tǒng)中有i個(gè)agent的隊(duì)列(批發(fā)商)的個(gè)數(shù)，dxi/dt是這種隊(duì)列的數(shù)量變化，xn是最大值隊(duì)列，ai是結(jié)合率，是一個(gè)agent加入到有i個(gè)agent的隊(duì)列中去的速率，bi是分解率，是有i個(gè)agent的隊(duì)列中的某個(gè)agent離開(kāi)的速率.建立的模型[1]為(式(1)(n>2))

(1)

其中ai，bi(i=1，2，…，n)為非負(fù)常數(shù).

K.Lerman和O.Shehory[1]對(duì)所有ai=a，bi=b(i=1，2，…，n)的特殊情形進(jìn)行了數(shù)值仿真，結(jié)果如圖1所示.從圖1 的數(shù)值模擬結(jié)果，可以發(fā)現(xiàn)幾個(gè)有趣的現(xiàn)象(圖1中的ri(t)(1≤i≤n)對(duì)應(yīng)于文中的xi(t)/N).

圖1 數(shù)值仿真的結(jié)果

(1) 當(dāng)B=0時(shí)，結(jié)果中x1(t)不存在；

(2) 當(dāng)B等于某個(gè)值時(shí)，所有ri(t)都相等；

(3) 從xn>xn-1>…xk>xk-1>…x2>x1變化到xn

另外存在的問(wèn)題是此系統(tǒng)是否有解.由于各agent是自由的，會(huì)不會(huì)隨處游蕩，也就是對(duì)應(yīng)的模型有沒(méi)有穩(wěn)定解.這些agent形成的隊(duì)列(批發(fā)商)的規(guī)模如何，模型的假設(shè)條件是否符合實(shí)際，為解決這些問(wèn)題，對(duì)系統(tǒng)進(jìn)行定性分析.

2 定性分析(一般情形)

對(duì)一般情形下的系統(tǒng)(1)，有定理1-3.

定理1 系統(tǒng)(1)的解xk(t)(k=1，2，…，n)滿足關(guān)系式

(2)

證明系統(tǒng)(1)的第2式可改寫為

(3)

同理系統(tǒng)(1)的第3式，可得

(4)

將式(3)(4)代入系統(tǒng)(1)可得

即

證明系統(tǒng)(1)的平衡點(diǎn)由方程組

(5)

式(5)中，所有2≤k≤n的方程相加可得

x2=(a1/b2)x12

依次代入，可得

代入式(2)，可得

定理3 系統(tǒng)(1)運(yùn)行過(guò)程中總有xi(t)≥0(i=1，2，…，n)，并且xi(t)不同時(shí)為 0，其中x1(t)不會(huì)停留在邊界上，即使在某時(shí)刻tm，x1(tm)=0，x1(t)也不會(huì)始終為 0.

證明首先證明在任意時(shí)刻t，系統(tǒng)中xi(t)(i=1，2，…，n)不全為0，這由定理1很容易得證.假定某一時(shí)刻xi(t)=0(1≤i≤n)，下面根據(jù)不同i進(jìn)行分析.

(1) 當(dāng)i=1時(shí)，即假定在某時(shí)刻t，x1(t)=0，根據(jù)系統(tǒng)(1)有

(2) 當(dāng)i=k(2≤k

因此，在t+Δt時(shí)刻就有xk(t+Δt)≥0(Δt→0)，不會(huì)出現(xiàn)xk(t)<0的情況.

(3) 當(dāng)i=n，即在某時(shí)刻t，xn(t)=0，根據(jù)系統(tǒng)(1)有

因此，xn(t)≥0，不會(huì)出現(xiàn)xn(t)<0的情況.

定理4 整個(gè)系統(tǒng)運(yùn)行過(guò)程中，xi一直在第一卦限內(nèi)部或邊緣，當(dāng)xi(t)=0(2≤i≤n)，并且保持dxi/dt=0.

3個(gè)定理證明了僅在第一卦限研究系統(tǒng)(1)即可，并且結(jié)合式(2)可知，系統(tǒng)(1)的解在第一卦限的一個(gè)有界閉區(qū)域內(nèi).由于此區(qū)域內(nèi)僅有一個(gè)奇點(diǎn)，因此，系統(tǒng)的解趨于此奇點(diǎn)或某極限環(huán).

3 定性分析(特殊情形ai=a，bi=b)

K.Lerman和 O.Shehory[1]對(duì)系統(tǒng)(1)中ai=a，bi=b時(shí)進(jìn)行了數(shù)值仿真，為了簡(jiǎn)化分析，令B=b/a，τ=at，則系統(tǒng)(1)變?yōu)?/p>

(6)

下面解釋數(shù)值仿真結(jié)果中的某些現(xiàn)象.

由此說(shuō)明了數(shù)值仿真結(jié)果中為什么會(huì)出現(xiàn)隨著B的增長(zhǎng)，系統(tǒng)從xn>xn-1>…>xk>xk-1>…>x2>x1變化到xn

這樣，從一般性分析的基礎(chǔ)上便可對(duì)原系統(tǒng)的數(shù)值仿真結(jié)果進(jìn)行說(shuō)明.圖2是定性分析結(jié)果，圖1是原文的數(shù)值仿真.圖1中ri含義同圖2的xi，橫坐標(biāo)軸是B/N，縱坐標(biāo)軸是ri/N，也即文中的xi/N.曲線形狀是相同的，只是相當(dāng)于縮小一個(gè)比例.

圖2 定性分析結(jié)果

從上面的分析可以看出，數(shù)值仿真的結(jié)果可以從原模型中通過(guò)定性分析得出，從分析結(jié)果驗(yàn)證了模型滿足系統(tǒng)假設(shè)條件.另外，定性分析嚴(yán)格證明了數(shù)值分析中的結(jié)論并且分析出一些數(shù)值仿真所不能得到的一些特性.

參考文獻(xiàn)：

[1] LERMAN K，GALSTYAN A. A General Methodology for Mathematical Analysis of Multi-Agent Systems[R]. USC Information Sciences Technical Report IsI-TR-529，2001

[2] LERMAN K，SHEHORY O. Coalition Formation for Large-Scale Electronic Markets[A]. ICMAS-2000[C]. Boston or IBM Research Lab in Haifa，2000

[3] LERMAN K. Design and Mathematical analysis of agent-based system[M]. Berlin：Springer-Verlag，2001

[4] LERMAN K，GALSTYAN A. Mathematical Model of Foraging in a Group of Robots Effect of Interference[J]. Autonomous Robots，2002(13)：127-141