胡 軍，張振興，鄒 立

(1.湖南大學(xué) 信息科學(xué)與工程學(xué)院, 湖南 長沙 410082；2. 桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室,廣西 桂林 541004；3.南京大學(xué) 計(jì)算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室, 江蘇 南京 210093；4.湖南大學(xué) 嵌入式與網(wǎng)絡(luò)計(jì)算湖南省重點(diǎn)實(shí)驗(yàn)室，湖南 長沙 410082)

面向社交網(wǎng)絡(luò)基于協(xié)作度協(xié)商的聯(lián)盟形成機(jī)制

胡 軍1,4?，張振興1,2，鄒 立1,3

(1.湖南大學(xué) 信息科學(xué)與工程學(xué)院, 湖南 長沙 410082；2. 桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室,廣西 桂林 541004；3.南京大學(xué) 計(jì)算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室, 江蘇 南京 210093；4.湖南大學(xué) 嵌入式與網(wǎng)絡(luò)計(jì)算湖南省重點(diǎn)實(shí)驗(yàn)室，湖南 長沙 410082)

分布式多Agent構(gòu)成的社交網(wǎng)絡(luò)通常表現(xiàn)出不同的特征，針對不同的社交網(wǎng)絡(luò)和多Agent本身的異質(zhì)性，提出了一種面向社交網(wǎng)絡(luò)的基于協(xié)作度協(xié)商聯(lián)盟形成機(jī)制.該機(jī)制依托多Agent構(gòu)成的社交網(wǎng)絡(luò)環(huán)境，建立面向分布式環(huán)境的分布式協(xié)商協(xié)議，并設(shè)計(jì)一種考慮到社交網(wǎng)絡(luò)特征和Agent異質(zhì)性的基于協(xié)作度的協(xié)商策略，采用分布式自動協(xié)商方式形成聯(lián)盟.通過對全連通網(wǎng)絡(luò)、層次網(wǎng)路和小世界網(wǎng)絡(luò)的仿真實(shí)驗(yàn)結(jié)果表明，該機(jī)制能夠有效地實(shí)現(xiàn)分布式環(huán)境下的聯(lián)盟形成，并且在反應(yīng)大多數(shù)實(shí)際應(yīng)用環(huán)境的小世界社交網(wǎng)絡(luò)中表現(xiàn)出相對較好的性能.

多Agent系統(tǒng)；聯(lián)盟形成；分布式自動協(xié)商；社交網(wǎng)絡(luò)；協(xié)作度

形成聯(lián)盟是多Agents最常用的一種協(xié)作方式，高效的構(gòu)建聯(lián)盟是多Agent系統(tǒng)中的研究熱點(diǎn)之一.目前的聯(lián)盟形成方法存在著諸多的局限.一是，大多數(shù)方法針對多Agent全連通的情況，未考慮實(shí)際環(huán)境中Agents之間不同的連接結(jié)構(gòu)，適用面較窄；二是，現(xiàn)有研究中大多是針對集中式系統(tǒng)的，不適用于分布式的應(yīng)用情況，實(shí)用性不強(qiáng)；三是，忽略了不同Agent的異質(zhì)性，沒有考慮Agent的協(xié)作態(tài)度和協(xié)作資源的不同，實(shí)用性不強(qiáng).如文獻(xiàn)[1-4]中Agent之間都是全連通的，求解聯(lián)盟的方法是通過搜索聯(lián)盟結(jié)構(gòu)圖獲得最優(yōu)聯(lián)盟結(jié)構(gòu).這樣聯(lián)盟形成的過程是一個NP難問題，而實(shí)際應(yīng)用中全連通的Agent情況并不多見.文獻(xiàn)[5-6]引入了社交網(wǎng)絡(luò)和學(xué)習(xí)型協(xié)同圖的概念，使得問題的求解簡化，但是文中沒有考慮不同的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對聯(lián)盟形成的影響.集中式環(huán)境中，文獻(xiàn)[7-9]先通過協(xié)商形成候選聯(lián)盟集，然后通過發(fā)起聯(lián)盟的集中管理者Agent分配效用，確定最終聯(lián)盟.針對分布式應(yīng)用環(huán)境，文獻(xiàn)[10]中建立了一套基于協(xié)商的聯(lián)盟形成機(jī)制，Agent在分布式協(xié)商協(xié)議下形成聯(lián)盟和確定效用值的劃分并且對比了不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對聯(lián)盟形成的影響，但是該機(jī)制沒有考慮不同Agent的協(xié)作資源和協(xié)作態(tài)度的不同的異質(zhì)性，使得聯(lián)盟形成效率相對不高.為了解決現(xiàn)有研究中的局限性，本文試圖建立一套在分布式環(huán)境下、面向社交網(wǎng)路結(jié)構(gòu)的，異質(zhì)的多Agent聯(lián)盟形成機(jī)制.本文首先對比分析全連通的、隨機(jī)樹型的、小世界網(wǎng)絡(luò)社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特點(diǎn)；然后針對分布式應(yīng)用環(huán)境，構(gòu)建一個分布式的協(xié)商協(xié)議來保障聯(lián)盟形成；接下來考慮鄰居Agent的歷史信任度和資源擁有情況下引入了協(xié)作度的概念，來體現(xiàn)不同Agent的協(xié)作資源和協(xié)作態(tài)度的差異性，進(jìn)而表達(dá)不同社交網(wǎng)絡(luò)結(jié)構(gòu)的特點(diǎn)，建立一種基于Agent協(xié)作度的協(xié)商策略；最后，實(shí)現(xiàn)面向社交網(wǎng)絡(luò)的基于協(xié)作度協(xié)商聯(lián)盟形成機(jī)制SOCNCF(social networks oriented collaboration degree based negotiation coalition formation mechanism ).

1 社交網(wǎng)絡(luò)

分布式環(huán)境中，多Agent之間的連通關(guān)系構(gòu)建的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖，可以看成是多Agent之間的社交網(wǎng)絡(luò)SN(Social Network).該網(wǎng)絡(luò)結(jié)構(gòu)構(gòu)成多Agent通過分布式協(xié)商形成聯(lián)盟的環(huán)境基礎(chǔ).

1.1 簡單的社交網(wǎng)絡(luò)

設(shè)AGENT={Agent1,Agent2,…,Agenti}，表示一個用于聯(lián)盟形成的Agents集合，Agents連通關(guān)系的網(wǎng)絡(luò)拓?fù)鋱DG=(A,E).A表示不同的Agent，E表示連接Agent的邊，把可以與Agenti直接通信的其他Agent定義為Agenti的直接鄰居，其形式化的定義如式(1):

I(i)={i'|(i',i)∈E,i'≠i}

(1)

例如，e=(1,2)∈E表示的意思是Agent1和Agent2之間是連通的，他們可以通過協(xié)商形成聯(lián)盟.

傳統(tǒng)的聯(lián)盟形成機(jī)制中很少考慮到成員Agent的SN差異性，大多考慮的都是全連通的情況.但是實(shí)際應(yīng)用中Agent是處于不同的SN中的，Agent之間的交互將受到SN的差異性限制.圖1是使用本文實(shí)驗(yàn)平臺產(chǎn)生的3種簡單的社交網(wǎng)絡(luò)，可見，圖1(a)中可能形成的聯(lián)盟是{Agent0}，{Agent1}，{Agent2}，{Agent0，Agent1}，{Agent0，Agent2}，和{Agent0，Agent1，Agent2}.可見聯(lián)盟{(lán)Agent1,Agent2}是不可能形成的，因?yàn)锳gent1和Agent2沒有之間相連，他們之間不能相互交互協(xié)商形成聯(lián)盟.在圖1(b)中由于Agent之間的連同關(guān)系變了，所以不能形成的聯(lián)盟是{Agent0，Agent2}，{Agent1，Agent3}.最后，在如圖1(c) 的全連通圖中，由于每一個Agent之間都是之間相連的，所有{Agent0，Agent1，Agent2，Agent3}的任意子集都可能形成聯(lián)盟.

1.2 幾類典型的社交網(wǎng)絡(luò)

1.2.1 全連通網(wǎng)絡(luò)

全連通網(wǎng)絡(luò)中Agents之間都是全連通的，其聯(lián)通關(guān)系如圖1(c)所示，此時I(i)={i'|i'∈AGENT,i'≠i}.在這種網(wǎng)絡(luò)中，每個Agent的直接鄰居數(shù)目是相同的，也就是說每個節(jié)點(diǎn)的度數(shù)是一樣的，各個節(jié)點(diǎn)之間就有對稱性.

1.2.2 樹型網(wǎng)絡(luò)

樹型社交網(wǎng)絡(luò)是具有層次結(jié)構(gòu)的社交網(wǎng)絡(luò)，是通過隨機(jī)選擇節(jié)點(diǎn)的生成方式構(gòu)建的樹形結(jié)構(gòu).在隨機(jī)樹型的社交網(wǎng)絡(luò)中，最典型的特點(diǎn)就是不同層次的Agent所具有的鄰居數(shù)目|I(i)|差異性大.如圖2所示，上層的Agent具有更高的連通性，而下層的Agent連通性比較差，葉子節(jié)點(diǎn)只有一個直接鄰居.

(a)

(b)

(c)

圖2 隨機(jī)樹社交網(wǎng)絡(luò)

1.2.3 小世界網(wǎng)絡(luò)

小世界網(wǎng)絡(luò)一類特殊的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)，在這種網(wǎng)絡(luò)中大部份的節(jié)點(diǎn)彼此并不相連，但絕大部份節(jié)點(diǎn)之間經(jīng)過少數(shù)幾步就可到達(dá).這反映的是現(xiàn)實(shí)世界中陌生人可以通過彼此共同認(rèn)識的人而連接的現(xiàn)象.

小世界網(wǎng)絡(luò)的判定準(zhǔn)則有兩個，分別是特征路徑長度和高集聚系數(shù).網(wǎng)絡(luò)的特征路徑長度是指在它的圖表示中，兩個節(jié)點(diǎn)的路徑長度的平均值(這里路徑長度指兩節(jié)點(diǎn)間最短路徑的長度).許多復(fù)雜網(wǎng)絡(luò)盡管節(jié)點(diǎn)數(shù)目巨大，但節(jié)點(diǎn)之間的特征路徑長度則非常小[11].集聚系數(shù)則是用來描述“抱團(tuán)”現(xiàn)象的，也就是“你朋友之間相互認(rèn)識的程度”.從數(shù)學(xué)的角度上來說，一個節(jié)點(diǎn)的集聚系數(shù)等于與它相連的節(jié)點(diǎn)中相互連接的點(diǎn)對數(shù)與總點(diǎn)對數(shù)的比值.高集聚系數(shù)實(shí)際上保證了較小的特征路徑長度[12].圖3是由100個Agent形成的小世界網(wǎng)絡(luò)，其中最大度數(shù)為10，平均度數(shù)為5.8.由圖可以看出，小世界網(wǎng)絡(luò)有明顯的“抱團(tuán)”現(xiàn)象，并且有邊將這些“團(tuán)”連接起來.

圖3 小世界型社交網(wǎng)絡(luò)

2 分布式協(xié)商模型

本文是使用分布式協(xié)商的方法形成聯(lián)盟，所以首先介紹分布式協(xié)商的形式化模型基礎(chǔ)；接下來敘述分布式協(xié)商要素；最后給出分布式協(xié)商協(xié)議.

設(shè)Agenti擁有一個特定的資源ri，ri描述的是這個Agent執(zhí)行任務(wù)時可以利用的資源；把Agenti的直接鄰居所擁有的資源稱為Agenti的備用資源.當(dāng)Agenti無法單獨(dú)完成某些特定的任務(wù)時，Agenti可以使用自己的備用資源，通過與其直接鄰居形成聯(lián)盟來完成.Agent集合中的各個Agent可能形成的聯(lián)盟是C1,C2,…,Cn∈2I，Ci中每個成員Agenti擁有ri所描述的資源，這樣聯(lián)盟Ci擁有的資源描述為rC∈∏i∈Cri.形成聯(lián)盟Ci后可以得到一個整體的效用V(rC)∈Z+，這個效用代表的是聯(lián)盟在系統(tǒng)中產(chǎn)生的效用值；通過協(xié)商，每一個成員Agent可以在這個效用值中劃分到一份效用值vi∈Z+，易見∑i∈C=vi=V(rC).并且整體效用可用式(2)計(jì)算：

V(rC)=|C|∑i∈Cri

(2)

可見，形成的聯(lián)盟越大，獲得的聯(lián)盟效用越大.

2.1 協(xié)商要素

分布式協(xié)商中的協(xié)商要素包括協(xié)商提議、協(xié)商區(qū)間和協(xié)商決策函數(shù)，這些都是構(gòu)建分布式協(xié)商的前提.

2.1.1 協(xié)商提議

Agenti可以通過發(fā)送提議的方式向I(i)合適的Agentj發(fā)出聯(lián)盟邀請，協(xié)商提議定義為式(3)所示：

(3)

2.1.2 協(xié)商區(qū)間

所謂協(xié)商區(qū)間就是協(xié)商雙方的協(xié)商的效用分配的波動區(qū)間，即最小效用和最大效用.假如Agenti已經(jīng)收到了Agentk∈Ι(i)∪{i},k≠j的提議(rC,vi)，如式(4)所示的等式表示對是Agentj加入該聯(lián)盟后增加的效用：

δV(rC,rj)=V(rC,rj)-V(rC)

(4)

因此Agenti能夠得到的最大效用如式(5)所示，其中vi是Agentj加入聯(lián)盟之前Agenti所獲得的效用分配，δV(rC,rj) 由式(4)求得，即Agenti很自私的全部占有Agentj加入增加的效用.

(5)

要衡量Agenti的最小效用就要計(jì)算當(dāng)前Agenti的最好的效用值，Agenti將到目前為止可以加入的最優(yōu)聯(lián)盟的提議定義為o*=maxo∈commitsetiv(o)，其中，commitseti表示Agenti當(dāng)前可以加入的聯(lián)盟提議集合.因此Agenti的最小效用如式(6)所示，即協(xié)商區(qū)間的最小值不能小于Agenti到目前為止取得的最大效用：

vmin(rC,rj)=max (0,vi(o*))

(6)

2.1.3 協(xié)商決策函數(shù)

協(xié)商決策函數(shù)是Agent在收到協(xié)商提議后的按照最大化自身利益的原則決策自身行為的過程.

(7)

綜上，Agent的決策函數(shù)定義如式(8)所示，即：

(8)

可見一個Agent進(jìn)行協(xié)商決策的過程就是產(chǎn)生不同類型的提議，有：接收提議、反提議、新建提議等.

因此，Agenti可以執(zhí)行的決策有：

根據(jù)協(xié)商策略就當(dāng)前收到的提議產(chǎn)生反提議；

發(fā)送一個提議給當(dāng)前可加入的最優(yōu)聯(lián)盟的邀請者Agent，加入該聯(lián)盟；

2.2 分布式協(xié)商協(xié)議

協(xié)商協(xié)議通過對分布式協(xié)商通信過程的規(guī)定和Agent協(xié)商狀態(tài)的定義，來實(shí)現(xiàn)協(xié)商過程的收斂性和避免死鎖.

協(xié)商中的Agentj的狀態(tài)定義為：sj={DONE,WAIT(i),SLEEP}.其中，DONE狀態(tài)表示Agentj已接受某個協(xié)商提議，該Agent的協(xié)商已完成.WAIT(i)狀態(tài)表示Agentj已向Agenti發(fā)送了協(xié)商提議，等待i的回復(fù).SLEEP狀態(tài)表示Agentj的初始狀態(tài)，等待其他Agent發(fā)送提議過來.

具體協(xié)議流程如圖4所示，開始形成聯(lián)盟前，所有的Agent都處于SLEEP狀態(tài)，當(dāng)Agentj發(fā)送提議給Agenti∈I(j)后，邀請者Agentj將sj設(shè)置為WAIT(i)狀態(tài)，此時I(j)/{i}中所有的Agent不能再發(fā)送新的提議給Agentj，避免死鎖發(fā)生.此時唯一能和Agentj通信的只有Agenti，Agenti將發(fā)送給Agentj反提議、接受Agenti或者拒絕提議.如果Agenti接受了Agentj，Agenti將si設(shè)置為DONE.此時，Agenti將其自身的狀態(tài)通知給正在等待它回應(yīng)的主體.如果該提議包含該鄰居，它發(fā)送接受提議消息給該鄰居，如Agentj，對其他主體發(fā)送拒絕消息，之后Agenti將不能再收到任何提議.同時Agentj將Agenti加入保證可以加入的聯(lián)盟集commitsetj中，Agentj將sj設(shè)置為SLEEP，表示現(xiàn)在Agentj可以接收新的提議；如果Agenti發(fā)送反提議給Agentj，Agentj將sj設(shè)置為SLEEP，Agenti自己將si設(shè)置為WAIT(i)；如果Agenti發(fā)送拒絕提議給Agentj，則Agentj將sj設(shè)置為SLEEP.本協(xié)議是通過避免產(chǎn)生提議環(huán)和避免提議沖突，來實(shí)現(xiàn)協(xié)商過程的不死鎖性的.具體來說，通過下列通信的規(guī)則來實(shí)現(xiàn)：

圖4 分布式協(xié)商協(xié)議中Agent狀態(tài)遷移圖

3 基于協(xié)作度的協(xié)商策略

3.1 協(xié)商策略函數(shù)

本文提出基于協(xié)作度的協(xié)商策略CBNT(CooperationDegree-BasedNegotiationTactic)，協(xié)商策略函數(shù)如式(9)所示指數(shù)函數(shù)族來逐步產(chǎn)生讓步后的新提議.

(9)

3.2 協(xié)作度

本文引入了協(xié)作度的概念，來描述Agent的協(xié)作資源和歷史協(xié)作狀況的不同，從而體現(xiàn)在不同社交網(wǎng)絡(luò)結(jié)構(gòu)的差異性，進(jìn)而通過協(xié)作度對協(xié)商態(tài)度值產(chǎn)生影響，來實(shí)現(xiàn)不同策略的協(xié)商過程.

定義1Agentj相對Agenti的歷史協(xié)作度：

(10)

其中，分母是Agenti和Agentj所有歷史交互提議的次數(shù)，分子是Agenti和Agentj所有歷史交互協(xié)商成功的次數(shù).反應(yīng)歷史協(xié)商過程中Agentj接受Agenti提議的幾率，稱為Agentj相對Agenti的歷史協(xié)作度，反應(yīng)的是Agent的協(xié)作態(tài)度.

定義2 Agentj相對Agenti的現(xiàn)在協(xié)作度：

(11)

分子是Agenti的鄰居Agentj擁有的備用資源數(shù)量，分母是Agenti所有的鄰居擁有的備用資源總和，當(dāng)Agentj相對Agenti的其他鄰居而言擁有更多的備用資源時，我們認(rèn)為Agentj相對Agenti的現(xiàn)在協(xié)作度較高，反應(yīng)的是Agent的協(xié)作資源.

定義3 Agentj相對Agenti的協(xié)作度：

cij=a×cij-past+b×cij-now∈[0,1]

(12)

Agentj相對Agenti的協(xié)作度是綜合考慮定義1和定義2中的歷史協(xié)作度和現(xiàn)在協(xié)作度的，式中a+b=1恒成立.a和b的選擇反應(yīng)的是聯(lián)盟形成中更注重歷史表現(xiàn)還是現(xiàn)在的資源占有情況.

基于上述協(xié)作度的定義，Agenti對Agentj的協(xié)商態(tài)度值采用式(13)計(jì)算：

(13)

4 SOCNCF機(jī)制

SOCNCF機(jī)制在分布式協(xié)商模型的基礎(chǔ)上使用基于協(xié)作度的協(xié)商策略進(jìn)行聯(lián)盟形成，分布式協(xié)商模型保證算法的收斂性，基于協(xié)作度的協(xié)商策略保證算法的高效性.SOCNCF機(jī)制實(shí)現(xiàn)算法如算法1所示.算法開始階段會產(chǎn)生模擬分布式環(huán)境的不同類型的社交網(wǎng)絡(luò)，同時對Agent的協(xié)作度初始化；每一次聯(lián)盟形成過程開始前會利用前一次聯(lián)盟形成計(jì)算出的協(xié)作度cooperationTemp作為本輪的初始協(xié)作度；然后開始多輪協(xié)商進(jìn)行聯(lián)盟形成，在遵循社交網(wǎng)絡(luò)和分布式協(xié)商協(xié)議的前提下得到協(xié)商決策函數(shù)Decision；根據(jù)得到的不同Decision對用來計(jì)算Agent之間協(xié)作度的相關(guān)參數(shù)進(jìn)行計(jì)算和對Agent的狀態(tài)進(jìn)行更新，一遍聯(lián)盟形成后根據(jù)Agent之間協(xié)作度的相關(guān)參數(shù)計(jì)算協(xié)作度并保存至cooperationTemp.然后開始下一次聯(lián)盟形成過程，直至MAXHISTORYTIMES次后算法結(jié)束.

算法1 SOCNCFAlgorithm()

SOCNCFAlgorithm(){

graph = graphGen.getGg();

//產(chǎn)生Agents的社交網(wǎng)絡(luò)，初始化當(dāng)前協(xié)作度

cooperation=cooperationInit();

//Agent歷史協(xié)作的初始化

cooperationTemp;//用來保存歷史協(xié)作度記錄

for times:1→MAXHISTORYTIMES

//利用協(xié)作度的動態(tài)更新進(jìn)行

MAXHISTORY-TIMES次聯(lián)盟形成

allAgents=initialiser.createAgents();

//Agent集初始化

cooperation=cooperationTemp;

//將上一輪的協(xié)作度記錄賦給本Agent

for clock:1→MAX_TIME

//進(jìn)行最大輪數(shù)不超過MAX_TIME的協(xié)商

for agent:allAgents

//遍歷Agent集中所有的agent

if(agent.issleep&&!nonwaiting.isEmpty)

//判斷Agent自身和鄰居的狀態(tài)

Decision=agent.getDecision();

//根據(jù)決策函數(shù)進(jìn)行該Agent協(xié)商、決策

updateCooperationParameter(Decision，Parameter)//更新用來計(jì)算協(xié)作度的參數(shù)

updateState(Decision)

//根據(jù)得到的決策更新Agent的狀態(tài)

sortNeiberhour(cooperation)

//根據(jù)Agent不同鄰居的協(xié)作度的大小對鄰居進(jìn)行排序，下輪協(xié)商時將優(yōu)先選擇協(xié)作度高的Agent

endif

endfor //遍歷完所有的Agent

endfor //本輪協(xié)商結(jié)束

CalculateCooperation(cooperationTemp, Parameter)//根據(jù)本次聯(lián)盟形成的協(xié)作度

endfor//基于協(xié)作度的多次聯(lián)盟形成過程結(jié)束

}

5 實(shí)驗(yàn)分析

5.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)使用Eclipse平臺仿真多Agent聯(lián)盟形成過程，試驗(yàn)中模擬的機(jī)制有本文的SOCNCF和文獻(xiàn)[10]社交網(wǎng)絡(luò)中的聯(lián)盟形成機(jī)制CFMSN(Coalition Formation Mechanism In Social Network)，文獻(xiàn)[10]中所述的聯(lián)盟形成機(jī)制是單純的考慮Agent之間的連通關(guān)系—協(xié)作資源，忽略了Agent之間在協(xié)作態(tài)度上的異質(zhì)性.實(shí)驗(yàn)內(nèi)容包括兩部分，第1部分將對比使用不同的社交網(wǎng)絡(luò)時SOCNCF機(jī)制和CFMSN在總共使用的協(xié)商輪數(shù)上的差異性，由于SOCNCF機(jī)制需要?dú)v史信息的累計(jì)，故進(jìn)行了10次聯(lián)盟形成的過程，分別是CFMSN，SOCNCF-2，SOCNCF-3，…，SOCNCF-10，可見第1次聯(lián)盟形成實(shí)際上就是沒有使用協(xié)作度信息的CFMSN機(jī)制；實(shí)驗(yàn)的第2部分將在平均協(xié)商輪數(shù)、協(xié)商成功率、平均聯(lián)盟大小、平均個體效用等4個方面對比分析以上兩種方法在不同的社交網(wǎng)絡(luò)下形成聯(lián)盟時的性能，由于我們的實(shí)際應(yīng)用中大多的多Agent聯(lián)盟形成環(huán)境都是小世界網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，所以我們期望SOCNCF機(jī)制相比CFMSN機(jī)制來說在小世界網(wǎng)絡(luò)中有更好的性能.

為了對比不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和不同規(guī)模Agent集下SOCNCF機(jī)制的性能，Agent社交網(wǎng)絡(luò)環(huán)境設(shè)置有兩種，為了保證不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的可比性，第1種社交網(wǎng)絡(luò)環(huán)境中將網(wǎng)絡(luò)的最大度數(shù)都設(shè)定為20；第2種社交網(wǎng)絡(luò)環(huán)境中將網(wǎng)絡(luò)的最大度數(shù)都設(shè)定為40.實(shí)驗(yàn)中具體相關(guān)參數(shù)設(shè)置如下：

第1種社交網(wǎng)絡(luò)環(huán)境中，全連通網(wǎng)絡(luò)Agent集為21個，度數(shù)為20；小世界網(wǎng)絡(luò)Agent集為100個，模擬真實(shí)的社交環(huán)境，最大度數(shù)限制為20，平均度數(shù)為8.8；隨機(jī)樹網(wǎng)絡(luò)的Agent集為100個，模擬具有明顯層次結(jié)構(gòu)的環(huán)境，最大度數(shù)為20，平均度數(shù)為1.98.第2種社交網(wǎng)絡(luò)環(huán)境中把全連通網(wǎng)絡(luò)Agent集擴(kuò)展到41，小世界網(wǎng)絡(luò)和隨機(jī)樹網(wǎng)絡(luò)的Agent集擴(kuò)展為200，并限制最大度數(shù)為40.

單個Agent開銷是0到1的隨機(jī)分布；單個Agent的效用是開銷的1.5倍到3倍；為了去除試驗(yàn)中隨機(jī)過程的影響，每一次聯(lián)通形成過程都將重復(fù)100次取置信度為95%的置信區(qū)間作為實(shí)驗(yàn)結(jié)果；為了得到SOCNCF機(jī)制那個的協(xié)作度信息，將進(jìn)行10次聯(lián)盟形成過程；初始協(xié)作度可以為15(激進(jìn)型)、0.001(線性型)、-5(被動型)隨機(jī)選擇；為了既反映出Agent的協(xié)作態(tài)度，又反映出Agent的協(xié)作資源，協(xié)作度中取a,b都為0.5；同時為了使協(xié)作度對協(xié)商策略起到最為恰當(dāng)?shù)挠绊懖⑶覍︵従覣gent協(xié)作度有較好的判斷，β0設(shè)置為5，協(xié)商策略閥值Δcth為0.5.

5.2 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)的第1部分是對比使用不同的社交網(wǎng)絡(luò)時，SOCNCF機(jī)制和CFMSN機(jī)制在協(xié)商輪數(shù)上變化的差異性.實(shí)驗(yàn)的設(shè)置如5.1節(jié)描述所示，其中Agent網(wǎng)絡(luò)環(huán)境設(shè)置為第1種，初始協(xié)作度是5.1節(jié)中所示的3種隨機(jī)選擇的.為了驗(yàn)證SOCNCF的有效性，將進(jìn)行10聯(lián)盟形成的過程，為了去除試驗(yàn)中隨機(jī)因素的影響，每次聯(lián)盟形成過程重復(fù)了100次取平均值.最終實(shí)驗(yàn)結(jié)果如圖5所示.

方法

可以看出，全連通社交網(wǎng)絡(luò)的協(xié)商次數(shù)在CFMSN機(jī)制中最少，但是它隨著協(xié)作信息的累積沒有很明顯的減少聯(lián)盟形成的協(xié)商次數(shù)；相反，小世界社交網(wǎng)絡(luò)在CFMSN機(jī)制中聯(lián)盟形成的協(xié)商次 數(shù)最大，但是由于SOCNCF機(jī)制中的協(xié)作度很好地反應(yīng)了小世界社交網(wǎng)絡(luò)的特性，使得它隨著協(xié)作度信息的累集有很明顯的協(xié)商次數(shù)改進(jìn)，以至于到了SOCNCF-10時，它的協(xié)商次數(shù)最少.這反映了的SOCNCF機(jī)制更適合應(yīng)用于小世界社交網(wǎng)絡(luò)中，在不同的社交網(wǎng)絡(luò)中具體的各項(xiàng)性能對比將在實(shí)驗(yàn)的第2部分進(jìn)行.實(shí)驗(yàn)的第2部分是為了對比CFMSN機(jī)制和SOCNCF在不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的性能，從而驗(yàn)證SOCNCF機(jī)制的有效性.實(shí)驗(yàn)中Agent社交網(wǎng)絡(luò)環(huán)境分別取5.1節(jié)中所示的兩種；Agent的初始協(xié)作度是實(shí)驗(yàn)1中3種協(xié)商策略隨機(jī)選擇的，SOCNCF機(jī)制的數(shù)據(jù)取的是第10次形成聯(lián)盟時(SOCNCF-10)的數(shù)據(jù)；每次形成聯(lián)盟時重復(fù)試驗(yàn)100次，取置信度為95%的置信區(qū)間作為結(jié)果.Agent網(wǎng)絡(luò)環(huán)境為第1種時，實(shí)驗(yàn)結(jié)果如表1所示；Agent網(wǎng)絡(luò)環(huán)境為第2種時，實(shí)驗(yàn)結(jié)果如表2所示.其中協(xié)商輪數(shù)是聯(lián)盟形成中協(xié)商交互提議最多的次數(shù)；協(xié)商成功率是聯(lián)盟形成后，Agent集中收斂的Agent占的比分比，聯(lián)盟大小是形成的所有聯(lián)盟的平均值；而平均個體效用是所有收斂的Agent獲得的效用的平均值.

表1 第1種Agent社交網(wǎng)絡(luò)環(huán)境下聯(lián)盟形成效果對比

表2 第2種Agent社交網(wǎng)絡(luò)環(huán)境下聯(lián)盟形成效果對比

由表1可以看出，當(dāng)使用第1種Agent網(wǎng)絡(luò)環(huán)境時，由于SOCNCF機(jī)制使用了基于協(xié)作度的協(xié)商策略，能夠動態(tài)改變給對手的協(xié)商態(tài)度值，使得該機(jī)制與單純的基于網(wǎng)絡(luò)的CFMSN機(jī)制相比具有更好的性能；同時雖然使用CFMS機(jī)制時小世界社交網(wǎng)絡(luò)中的效果不是最好，但是由于SOCNCF機(jī)制中的協(xié)作度是Agent的協(xié)作資源和Agent的協(xié)作態(tài)度的綜合反映，而小世界網(wǎng)絡(luò)的高聚集性正好使得不同Agent之間的協(xié)作資源差異性較大，小世界網(wǎng)絡(luò)的低平均路徑使得Agent之間的協(xié)商成功率高，從而協(xié)商態(tài)度較好，所以SOCNCF機(jī)制在小世界社交網(wǎng)絡(luò)中具有比其他兩種社交網(wǎng)絡(luò)更好的性能.

表2中采取的是第2種Agent社交網(wǎng)絡(luò)環(huán)境，這時Agent的規(guī)模擴(kuò)大，節(jié)點(diǎn)最大的度數(shù)也增加了.實(shí)驗(yàn)結(jié)果表明，本文機(jī)制對網(wǎng)絡(luò)環(huán)境做出了變換時總體的趨勢和表1是相同的，即SOCNCF機(jī)制性能比CFMSN機(jī)制好，同時采取SOCNCF機(jī)制形成聯(lián)盟時小世界社交網(wǎng)絡(luò)中的性能最好.這說明SOCNCF機(jī)制的性能不會因?yàn)锳gent社交網(wǎng)絡(luò)環(huán)境的變化而失效，適應(yīng)于不同Agent大小、不同平均度數(shù)的Agent社交網(wǎng)絡(luò).

綜合上面兩部分實(shí)驗(yàn)可知，在CFMSN機(jī)制中，小世界社交網(wǎng)絡(luò)與其他兩種社交網(wǎng)絡(luò)相比在聯(lián)盟形成效率上不是最好的.但是SOCNCF機(jī)制通過引入?yún)f(xié)作度的概念，充分反映了小世界網(wǎng)絡(luò)高聚集、低平均路徑的特性，通過對協(xié)作度信息的累計(jì)后的SOCNCF在小世界網(wǎng)絡(luò)中具有最好的聯(lián)盟形成性能.而恰恰我們現(xiàn)實(shí)應(yīng)用中的多Agent系統(tǒng)大多都是小世界社交網(wǎng)絡(luò)，也就是說我們的SOCNCF機(jī)制具有很好的實(shí)用性.

6 總 結(jié)

本文提出的SOCNCF機(jī)制通過社交網(wǎng)絡(luò)模擬實(shí)際應(yīng)用中的多Agent環(huán)境，制約潛在的提議數(shù)；然后結(jié)合一系列的協(xié)商要素建立分布式協(xié)商協(xié)議，保證了該機(jī)制的收斂性；最后使用基于協(xié)作度的協(xié)商策略，既能提高聯(lián)盟形成的效率又能反應(yīng)不同的社交網(wǎng)絡(luò)的差異性；最后通過實(shí)驗(yàn)分析驗(yàn)證了該機(jī)制的可行性和有效性，并且驗(yàn)證SOCNCF機(jī)制在小世界網(wǎng)絡(luò)中的性能更突出，從而驗(yàn)證了SOCNCF的實(shí)用性.

[1] RAHWAN T, MICHALAK T, WOOLDRIDGE M,etal. Anytime coalition structure generation in multi-agent systems with positive or negative externalities[J]. Artificial Intelligence, 2012, 186: 95-122.

[2] 李少芳, 胡山立, 石純一. 一種基于勢結(jié)構(gòu)分組思想的任一時間聯(lián)盟結(jié)構(gòu)生成[J]. 計(jì)算機(jī)研究與發(fā)展, 2012, 48(11): 2047-2054.

LI Shao-fang, HU Shan-li, SHI Chun-yi. An anytime coalition structure generation based on the grouping idea of cardinality structure[J]. Journal of Computer Research and Development, 2012, 48(11): 2047-2054. (In Chinese)

[3] 劉驚雷, 張偉, 童向榮, 等. 一種O(2.983n)時間復(fù)雜度的最優(yōu)聯(lián)盟結(jié)構(gòu)生成算法[J]. 軟件學(xué)報, 2011, 22(5): 938-950.

LIU Jing-lei, ZHANG Wei, TONG Xiang-rong,etal. O(2.983n) time complexity algorithm for optimal coalition structure generation [J]. Journal of Software, 2011, 22(5): 938-950.(In Chinese)

[4] SANDHOLM T. Agents in electronic commerce: Component technologies for automated negotiation and coalition formation[J]. Autonomous Agents and Multi-Agent Systems, 2000, 3(1): 73-96.

[5] VOICE T, RAMCHURN S D, JENNINGS N R. On coalition formation with sparse synergies[C]//Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 1. International Foundation for Autonomous Agents and Multiagent Systems．New York:ACM,2012: 223-230.

[6] LIEMHETCHARAT S, VELOSO M. Modeling and learning synergy for team formation with heterogeneous agents[C]//Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 1. International Foundation for Autonomous Agents and Multiagent Systems．New York:ACM, 2012: 365-374.

[7] SOH L，TSATSOULIS C. Allocation algorithms in dynamic negotiation-based coalition formation[C]//Proc of the 1st Int Conf on Autonomous Agents and Multiagent Systems. New York:ACM, 2002：16-23.

[8] SOH L K.Negotiation-based coalition formation model for agents with incomplete information and time constraints[R]. Lincoln, USA:Department of Computer Science and Engineering, University of Nebraska-Lincoln, 2002.

[9] 胡軍, 鄧?yán)? 宋穎輝. 面向議題關(guān)聯(lián)的雙邊多議題協(xié)商模型研究[J]. 湖南大學(xué)學(xué)報:自然科學(xué)版, 2011, 38(12)：66-71.

HU Jun, DENG Lei, SONG Ying-hui. Research on interdependence-oriented bilateral multi-issue negotiation model[J]. Journal of Hunan University :Natural Sciences, 2011, 38(12)：66-71. (In Chinese)

[10]RAMCHURN Sarvapali D,GERDING Enrico,JENNINGS N R,etal.Practical distributed coalition formation via heuristic negotiation in social networks[C]//Fifth International Workshop on Optimisation in Multi-agent Systems(OPTMAS).Valencia ES,2012:205.

[11]汪小帆, 李翔, 陳關(guān)榮. 復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M]. 北京:清華大學(xué)出版社, 2006:5-22.

WANG Xiao-fan, LI Xiang, CHEN Guan-rong. Theory and application of the complex network[M]. Beijing:Tsinghua Unversity Press, 2006:5-22.(In Chinese)

[12]ABRAHAM A, HASSANIEN A E, SNASEL V. Computational social network analysis: trends, tools and research advances[M].Berlin:Springer Press, 2009:205.

Social Networks Oriented Collaboration Degree Based Negotiation Coalition Formation Mechanism

HU Jun1,4?, ZHANG Zhen-xing1,2, ZOU Li1,3

(1.College of Computer Science and Electronic Engineering, Hunan Univ, Changsha, Hunan 410082,China；2. Guangxi Key Laboratory of Trusted Software, Guilin Univ of Electronic Technology, Guilin, Guangxi 541004,China；3.State Key Laboratory for Novel Software Technology, Nanjing Univ, Nanjing, Jiangsu 210093,China；4. Key Laboratory for Embedded and Network Computing of Hunan Province,Huna Univ, Changsha, Hunan 410082,China)

The social networks formed by distributed multi-Agent always show different characteristics. This paper proposed a social networks oriented collaboration degree based negotiation coalition formation mechanism aiming at the heterogeneity of different social networks and multi-Agent. This mechanism established a distributed negotiation protocol and designed a collaboration degree based negotiation tactic, which considered the characteristics of the social networks and the heterogeneity of the Agent. The experiment results in fully-connected network, hierarchical network and small world network have shown that this mechanism can form coalition in distributed environment effectively and show a better performance than other social networks in responding to small world networks in practical environment.

multi Agent systems; coalition formation; distributed auto-negotiation; social networking; collaboration degree

1674-2974(2015)02-0100-09

2014-01-16

國家自然科學(xué)基金資助項(xiàng)目(60773208),National Natural Science Foundation of China(60773208); 湖南省自然科學(xué)基金資助項(xiàng)目(11JJ3065); 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室研究資助項(xiàng)目(kx201333);計(jì)算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室研究資助項(xiàng)目( KFKT2013B14)

胡 軍(1971-)，男，湖南長沙人，湖南大學(xué)副教授，博士?通訊聯(lián)系人，E-mail:hujun_111@hnu.edu.cn

TP311

A