胡軍等

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

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

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A

形成聯(lián)盟是多Agents最常用的一種協(xié)作方式，高效的構(gòu)建聯(lián)盟是多Agent系統(tǒng)中的研究熱點之一.目前的聯(lián)盟形成方法存在著諸多的局限.一是，大多數(shù)方法針對多Agent全連通的情況，未考慮實際環(huán)境中Agents之間不同的連接結(jié)構(gòu)，適用面較窄；二是，現(xiàn)有研究中大多是針對集中式系統(tǒng)的，不適用于分布式的應(yīng)用情況，實用性不強；三是，忽略了不同Agent的異質(zhì)性，沒有考慮Agent的協(xié)作態(tài)度和協(xié)作資源的不同，實用性不強.如文獻(xiàn)[1-4]中Agent之間都是全連通的，求解聯(lián)盟的方法是通過搜索聯(lián)盟結(jié)構(gòu)圖獲得最優(yōu)聯(lián)盟結(jié)構(gòu).這樣聯(lián)盟形成的過程是一個NP難問題，而實際應(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)盟形成機制，Agent在分布式協(xié)商協(xié)議下形成聯(lián)盟和確定效用值的劃分并且對比了不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對聯(lián)盟形成的影響，但是該機制沒有考慮不同Agent的協(xié)作資源和協(xié)作態(tài)度的不同的異質(zhì)性，使得聯(lián)盟形成效率相對不高.為了解決現(xiàn)有研究中的局限性，本文試圖建立一套在分布式環(huán)境下、面向社交網(wǎng)路結(jié)構(gòu)的，異質(zhì)的多Agent聯(lián)盟形成機制.本文首先對比分析全連通的、隨機樹型的、小世界網(wǎng)絡(luò)社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特點；然后針對分布式應(yīng)用環(huán)境，構(gòu)建一個分布式的協(xié)商協(xié)議來保障聯(lián)盟形成；接下來考慮鄰居Agent的歷史信任度和資源擁有情況下引入了協(xié)作度的概念，來體現(xiàn)不同Agent的協(xié)作資源和協(xié)作態(tài)度的差異性，進而表達(dá)不同社交網(wǎng)絡(luò)結(jié)構(gòu)的特點，建立一種基于Agent協(xié)作度的協(xié)商策略；最后，實現(xiàn)面向社交網(wǎng)絡(luò)的基于協(xié)作度協(xié)商聯(lián)盟形成機制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)盟形成機制中很少考慮到成員Agent的SN差異性，大多考慮的都是全連通的情況.但是實際應(yīng)用中Agent是處于不同的SN中的， Agent之間的交互將受到SN的差異性限制.圖1是使用本文實驗平臺產(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}是不可能形成的，因為Agent1和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é)點的度數(shù)是一樣的，各個節(jié)點之間就有對稱性.

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

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

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

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

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

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

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

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

2.1協(xié)商要素

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

2.1.1協(xié)商提議

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

所謂協(xié)商區(qū)間就是協(xié)商雙方的協(xié)商的效用分配的波動區(qū)間，即最小效用和最大效用

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

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

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

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

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

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

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

3.2協(xié)作度

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

表示的是協(xié)商態(tài)度值的最小值，協(xié)商過程中Agent的協(xié)商態(tài)度值不能小于這個值.

通過協(xié)作度實現(xiàn)對協(xié)商態(tài)度值的影響，在形成聯(lián)盟時總是會參考鄰居的協(xié)商態(tài)度值，針對性的降低協(xié)作度高的鄰居協(xié)商態(tài)度值和提高協(xié)作度低的鄰居的協(xié)商態(tài)度值；并且優(yōu)先選擇讓步策略更好的鄰居協(xié)商，使得讓步更加迅速，并將協(xié)作度低的鄰居Agent逐漸被淘汰，使得協(xié)商策略將更加智能高效.

4SOCNCF機制

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

算法1SOCNCFAlgorithm（）

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)更新進行

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

allAgents=initialiser.createAgents（）；

//Agent集初始化

cooperation=cooperationTemp；

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

for clock：1→MAX_TIME

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

for agent：allAgents

//遍歷Agent集中所有的agent

if（agent.issleep&&！nonwaiting.isEmpty）

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

Decision=agent.getDecision（）；

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

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

updateState（Decision）

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

sortNeiberhour（cooperation）

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

endif

endfor //遍歷完所有的Agent

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

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

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

}

5實驗分析

5.1實驗設(shè)置

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

為了對比不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和不同規(guī)模Agent集下SOCNCF機制的性能，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.實驗中具體相關(guān)參數(shù)設(shè)置如下：

第1種社交網(wǎng)絡(luò)環(huán)境中，全連通網(wǎng)絡(luò)Agent集為21個，度數(shù)為20；小世界網(wǎng)絡(luò)Agent集為100個，模擬真實的社交環(huán)境，最大度數(shù)限制為20，平均度數(shù)為8.8；隨機樹網(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集擴展到41，小世界網(wǎng)絡(luò)和隨機樹網(wǎng)絡(luò)的Agent集擴展為200，并限制最大度數(shù)為40.

單個Agent開銷是0到1的隨機分布；單個Agent的效用是開銷的1.5倍到3倍；為了去除試驗中隨機過程的影響，每一次聯(lián)通形成過程都將重復(fù)100次取置信度為95%的置信區(qū)間作為實驗結(jié)果；為了得到SOCNCF機制那個的協(xié)作度信息，將進行10次聯(lián)盟形成過程；初始協(xié)作度可以為15（激進型）、0.001（線性型）、-5（被動型）隨機選擇；為了既反映出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實驗結(jié)果分析

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

可以看出，全連通社交網(wǎng)絡(luò)的協(xié)商次數(shù)在CFMSN機制中最少，但是它隨著協(xié)作信息的累積沒有很明顯的減少聯(lián)盟形成的協(xié)商次數(shù)；相反，小世界社交網(wǎng)絡(luò)在CFMSN機制中聯(lián)盟形成的協(xié)商次 數(shù)最大，但是由于SOCNCF機制中的協(xié)作度很好地反應(yīng)了小世界社交網(wǎng)絡(luò)的特性，使得它隨著協(xié)作度信息的累集有很明顯的協(xié)商次數(shù)改進，以至于到了SOCNCF-10時，它的協(xié)商次數(shù)最少.這反映了的SOCNCF機制更適合應(yīng)用于小世界社交網(wǎng)絡(luò)中，在不同的社交網(wǎng)絡(luò)中具體的各項性能對比將在實驗的第2部分進行.

實驗的第2部分是為了對比CFMSN機制和SOCNCF在不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的性能，從而驗證SOCNCF機制的有效性.實驗中Agent社交網(wǎng)絡(luò)環(huán)境分別取5.1節(jié)中所示的兩種；Agent的初始協(xié)作度是實驗1中3種協(xié)商策略隨機選擇的，SOCNCF機制的數(shù)據(jù)取的是第10次形成聯(lián)盟時（SOCNCF-10）的數(shù)據(jù)；每次形成聯(lián)盟時重復(fù)試驗100次，取置信度為95%的置信區(qū)間作為結(jié)果.Agent網(wǎng)絡(luò)環(huán)境為第1種時，實驗結(jié)果如表1所示；Agent網(wǎng)絡(luò)環(huán)境為第2種時，實驗結(jié)果如表2所示.其中協(xié)商輪數(shù)是聯(lián)盟形成中協(xié)商交互提議最多的次數(shù)；協(xié)商成功率是聯(lián)盟形成后，Agent集中收斂的Agent占的比分比，聯(lián)盟大小是形成的所有聯(lián)盟的平均值；而平均個體效用是所有收斂的Agent獲得的效用的平均值.

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

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

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

6總結(jié)

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

參考文獻(xiàn)

[1]RAHWAN T， MICHALAK T， WOOLDRIDGE M， et al. Anytime coalition structure generation in multiagent systems with positive or negative externalities[J]. Artificial Intelligence， 2012， 186： 95-122.

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

LI Shaofang， HU Shanli， SHI Chunyi. 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 Jinglei， ZHANG Wei， TONG Xiangrong， et al. 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 MultiAgent 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 SystemsVolume 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 SystemsVolume 1. International Foundation for Autonomous Agents and Multiagent Systems.New York：ACM， 2012： 365-374.

[7]SOH L，TSATSOULIS C. Allocation algorithms in dynamic negotiationbased 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.Negotiationbased coalition formation model for agents with incomplete information and time constraints[R]. Lincoln， USA：Department of Computer Science and Engineering， University of NebraskaLincoln， 2002.

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

HU Jun， DENG Lei， SONG Yinghui. Research on interdependenceoriented bilateral multiissue 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，et al.Practical distributed coalition formation via heuristic negotiation in social networks[C]//Fifth International Workshop on Optimisation in Multiagent Systems（OPTMAS）.Valencia ES，2012：205.

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

WANG Xiaofan， LI Xiang， CHEN Guanrong. 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.