胡軍等

摘要：分布式多Agent構(gòu)成的社交網(wǎng)絡(luò)通常表現(xiàn)出不同的特征，針對(duì)不同的社交網(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é)商策略，采用分布式自動(dòng)協(xié)商方式形成聯(lián)盟.通過(guò)對(duì)全連通網(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)出相對(duì)較好的性能.

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

中圖分類(lèi)號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A

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

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

設(shè)AGENT={Agent1，Agent2，…，Agenti}，表示一個(gè)用于聯(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之間是連通的，他們可以通過(guò)協(xié)商形成聯(lián)盟.

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

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

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

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

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

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

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

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

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

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

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

可見(jiàn)，形成的聯(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é)商的效用分配的波動(dòng)區(qū)間，即最小效用和最大效用

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

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

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

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

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

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

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

3.2協(xié)作度

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

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

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

4SOCNCF機(jī)制

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

算法1SOCNCFAlgorithm（）

SOCNCFAlgorithm（）{

graph = graphGen.getGg（）；

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

cooperation=cooperationInit（）；

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

cooperationTemp；//用來(lái)保存歷史協(xié)作度記錄

for times：1→MAXHISTORYTIMES

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

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

allAgents=initialiser.createAgents（）；

//Agent集初始化

cooperation=cooperationTemp；

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

for clock：1→MAX_TIME

//進(jìn)行最大輪數(shù)不超過(guò)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）//更新用來(lái)計(jì)算協(xié)作度的參數(shù)

updateState（Decision）

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

sortNeiberhour（cooperation）

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

endif

endfor //遍歷完所有的Agent

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

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

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

}

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

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

實(shí)驗(yàn)使用Eclipse平臺(tái)仿真多Agent聯(lián)盟形成過(guò)程，試驗(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部分將對(duì)比使用不同的社交網(wǎng)絡(luò)時(shí)SOCNCF機(jī)制和CFMSN在總共使用的協(xié)商輪數(shù)上的差異性，由于SOCNCF機(jī)制需要?dú)v史信息的累計(jì)，故進(jìn)行了10次聯(lián)盟形成的過(guò)程，分別是CFMSN，SOCNCF-2，SOCNCF-3，…，SOCNCF-10，可見(jiàn)第1次聯(lián)盟形成實(shí)際上就是沒(méi)有使用協(xié)作度信息的CFMSN機(jī)制；實(shí)驗(yàn)的第2部分將在平均協(xié)商輪數(shù)、協(xié)商成功率、平均聯(lián)盟大小、平均個(gè)體效用等4個(gè)方面對(duì)比分析以上兩種方法在不同的社交網(wǎng)絡(luò)下形成聯(lián)盟時(shí)的性能，由于我們的實(shí)際應(yīng)用中大多的多Agent聯(lián)盟形成環(huán)境都是小世界網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，所以我們期望SOCNCF機(jī)制相比CFMSN機(jī)制來(lái)說(shuō)在小世界網(wǎng)絡(luò)中有更好的性能.

為了對(duì)比不同網(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個(gè)，度數(shù)為20；小世界網(wǎng)絡(luò)Agent集為100個(gè)，模擬真實(shí)的社交環(huán)境，最大度數(shù)限制為20，平均度數(shù)為8.8；隨機(jī)樹(shù)網(wǎng)絡(luò)的Agent集為100個(gè)，模擬具有明顯層次結(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ī)樹(shù)網(wǎng)絡(luò)的Agent集擴(kuò)展為200，并限制最大度數(shù)為40.

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

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

實(shí)驗(yàn)的第1部分是對(duì)比使用不同的社交網(wǎng)絡(luò)時(shí)，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)盟形成的過(guò)程，為了去除試驗(yàn)中隨機(jī)因素的影響，每次聯(lián)盟形成過(guò)程重復(fù)了100次取平均值.最終實(shí)驗(yàn)結(jié)果如圖5所示.

可以看出，全連通社交網(wǎng)絡(luò)的協(xié)商次數(shù)在CFMSN機(jī)制中最少，但是它隨著協(xié)作信息的累積沒(méi)有很明顯的減少聯(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時(shí)，它的協(xié)商次數(shù)最少.這反映了的SOCNCF機(jī)制更適合應(yīng)用于小世界社交網(wǎng)絡(luò)中，在不同的社交網(wǎng)絡(luò)中具體的各項(xiàng)性能對(duì)比將在實(shí)驗(yàn)的第2部分進(jìn)行.

實(shí)驗(yàn)的第2部分是為了對(duì)比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)盟時(shí)（SOCNCF-10）的數(shù)據(jù)；每次形成聯(lián)盟時(shí)重復(fù)試驗(yàn)100次，取置信度為95%的置信區(qū)間作為結(jié)果.Agent網(wǎng)絡(luò)環(huán)境為第1種時(shí)，實(shí)驗(yàn)結(jié)果如表1所示；Agent網(wǎng)絡(luò)環(huán)境為第2種時(shí)，實(shí)驗(yàn)結(jié)果如表2所示.其中協(xié)商輪數(shù)是聯(lián)盟形成中協(xié)商交互提議最多的次數(shù)；協(xié)商成功率是聯(lián)盟形成后，Agent集中收斂的Agent占的比分比，聯(lián)盟大小是形成的所有聯(lián)盟的平均值；而平均個(gè)體效用是所有收斂的Agent獲得的效用的平均值.

由表1可以看出，當(dāng)使用第1種Agent網(wǎng)絡(luò)環(huán)境時(shí)，由于SOCNCF機(jī)制使用了基于協(xié)作度的協(xié)商策略，能夠動(dòng)態(tài)改變給對(duì)手的協(xié)商態(tài)度值，使得該機(jī)制與單純的基于網(wǎng)絡(luò)的CFMSN機(jī)制相比具有更好的性能；同時(shí)雖然使用CFMS機(jī)制時(shí)小世界社交網(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)境，這時(shí)Agent的規(guī)模擴(kuò)大，節(jié)點(diǎn)最大的度數(shù)也增加了.實(shí)驗(yàn)結(jié)果表明，本文機(jī)制對(duì)網(wǎng)絡(luò)環(huán)境做出了變換時(shí)總體的趨勢(shì)和表1是相同的，即SOCNCF機(jī)制性能比CFMSN機(jī)制好，同時(shí)采取SOCNCF機(jī)制形成聯(lián)盟時(shí)小世界社交網(wǎng)絡(luò)中的性能最好.這說(shuō)明SOCNCF機(jī)制的性能不會(huì)因?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ī)制通過(guò)引入?yún)f(xié)作度的概念，充分反映了小世界網(wǎng)絡(luò)高聚集、低平均路徑的特性，通過(guò)對(duì)協(xié)作度信息的累計(jì)后的SOCNCF在小世界網(wǎng)絡(luò)中具有最好的聯(lián)盟形成性能.而恰恰我們現(xiàn)實(shí)應(yīng)用中的多Agent系統(tǒng)大多都是小世界社交網(wǎng)絡(luò)，也就是說(shuō)我們的SOCNCF機(jī)制具有很好的實(shí)用性.

6總結(jié)

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

參考文獻(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]李少芳， 胡山立， 石純一. 一種基于勢(shì)結(jié)構(gòu)分組思想的任一時(shí)間聯(lián)盟結(jié)構(gòu)生成[J]. 計(jì)算機(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）時(shí)間復(fù)雜度的最優(yōu)聯(lián)盟結(jié)構(gòu)生成算法[J]. 軟件學(xué)報(bào)， 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é)報(bào)：自然科學(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.