多agen系統(tǒng)任務(wù)組織的選擇

多agen系統(tǒng)任務(wù)組織的選擇

在多媒體系統(tǒng)中，各自治機(jī)構(gòu)必須通過(guò)共同分工完成各自的任務(wù)。協(xié)作的成功與否,質(zhì)量好壞,很大程度上取決于任務(wù)委托時(shí)Agent之間進(jìn)行的協(xié)商,因此,多Agent系統(tǒng)中任務(wù)委托協(xié)商的研究一直是多Agent系統(tǒng)研究中的熱門(mén)話題。Smith和Davis提出了合同網(wǎng)協(xié)議1aprcationadge資源多Agent系統(tǒng)組織模型描述多Agent系統(tǒng)中各個(gè)獨(dú)立實(shí)體之間的關(guān)系(圖1)。在多Agent系統(tǒng)中,圍繞所承擔(dān)的任務(wù)構(gòu)成多個(gè)Agent組,根據(jù)Agent在多Agent系統(tǒng)中的地位,本文將多Agent系統(tǒng)中的Agent分為3種:UserAgent、ManagerAgent和ApplicationAgent。UserAgent是一個(gè)接口Agent,負(fù)責(zé)多Agent系統(tǒng)與用戶的交互;ManagerAgent負(fù)責(zé)多Agent系統(tǒng)的組織、管理和協(xié)調(diào);ApplicationAgent則負(fù)責(zé)完成與具體應(yīng)用相關(guān)的任務(wù)。多個(gè)AplicationAgent承擔(dān)任務(wù)的不同部分,在ManagerAgent的管理和協(xié)調(diào)下共同完成用戶提交的任務(wù)其中,ua∈U,ma∈M,aa∈A.AgentGroup的組織結(jié)構(gòu)如圖1所示。每個(gè)Agent組(AgentGroup)由一個(gè)ua,一個(gè)ma和一至多個(gè)aa組成。Agent組具有動(dòng)態(tài)性,每次在完成任務(wù)時(shí)通過(guò)協(xié)商、選擇形成Agent組。ua通常和4種實(shí)體發(fā)生聯(lián)系,和用戶實(shí)體的聯(lián)系負(fù)責(zé)接受用戶的任務(wù)請(qǐng)求,進(jìn)行任務(wù)求解過(guò)程中的參數(shù)交互以及用戶模板的維護(hù);和ma實(shí)體的聯(lián)系負(fù)責(zé)選擇合適的ma進(jìn)行任務(wù)委托及任務(wù)求解過(guò)程中的參數(shù)交互;和其它ua實(shí)體的聯(lián)系負(fù)責(zé)學(xué)習(xí)其它ua實(shí)體求解任務(wù)的經(jīng)驗(yàn);和名字服務(wù)器實(shí)體的聯(lián)系負(fù)責(zé)獲取系統(tǒng)中用戶、ua實(shí)體的分布情況。一個(gè)節(jié)點(diǎn)上只能有一個(gè)ua,而一個(gè)ua上可以有多個(gè)用戶。系統(tǒng)中設(shè)有一個(gè)名字服務(wù)器,負(fù)責(zé)提供與節(jié)點(diǎn)名、用戶名及Agent名相關(guān)的名字服務(wù)并維護(hù)上述關(guān)系。任務(wù)的委托和求解過(guò)程如下:(1)ua接受用戶的任務(wù)委托。(2)ua根據(jù)多級(jí)top-n隨機(jī)選擇算法選擇與其合作的ma,并將任務(wù)提交給選定的ma。(3)ma得到任務(wù)后,根據(jù)需要進(jìn)行任務(wù)分解。(4)對(duì)分解后的子任務(wù),根據(jù)選擇算法選擇合適的aa進(jìn)行子任務(wù)委托。(5)ma監(jiān)控aa執(zhí)行任務(wù),并最后進(jìn)行解綜合,將結(jié)果經(jīng)ua送給用戶。2多級(jí)to-n隨機(jī)選擇算法在ua向ma委托任務(wù)和ma向aa委托子任務(wù)時(shí)都可以采用多級(jí)top-n隨機(jī)選擇算法來(lái)選擇任務(wù)的承攬者。本文以u(píng)a和ma之間的任務(wù)委托為例對(duì)選擇算法進(jìn)行說(shuō)明。在多Agent系統(tǒng)中,ua僅作為用戶代理,而任務(wù)的實(shí)施由ma組織一組aa來(lái)完成。因此,如何選擇ma,對(duì)保證任務(wù)完成的質(zhì)量是至關(guān)重要的。一個(gè)好的ua應(yīng)該能代替用戶選擇合適的ma,通常ua在選擇ma時(shí)應(yīng)考慮以下幾點(diǎn):(1)考慮ma完成任務(wù)t的能力以及以往成功完成任務(wù)t的情況;(2)嘗試與新的ma合作,給每個(gè)ma較公平的機(jī)會(huì);(3)均衡ma的負(fù)載。ma本身是具有學(xué)習(xí)能力的智能體,其能力是不斷變化的,通常是隨著經(jīng)歷的豐富而逐漸增強(qiáng)。因此,ua在選擇與其合作的ma時(shí),既要考慮盡量多地和有成功經(jīng)歷的ma合作,也要考慮給其它ma參與的機(jī)會(huì),不斷挖掘出具有潛力的ma。這樣才能不斷提高系統(tǒng)的性能。為此,本文提出了多級(jí)top-n隨機(jī)選擇算法來(lái)滿足以上要求。算法根據(jù)ma的能力和完成任務(wù)t的情況,將M劃分為如圖2所示的3個(gè)互不相交的子集:上式中can＿do(ma,t)表示該ma具有完成任務(wù)t的能力,succ＿d(ma,t)表示ma完成任務(wù)t的成功度。成功度是對(duì)ma完成任務(wù)情況的一個(gè)綜合評(píng)價(jià),該評(píng)價(jià)可以由系統(tǒng)的評(píng)價(jià)體系完成,也可以由用戶給出評(píng)價(jià),0≤succ＿d(ma,t)≤1。top＿n(x)表示x的值位于前n位,n值是可設(shè)置的。L為一常量,表示ma進(jìn)入MA由MA設(shè):|M定義1:ua完成任務(wù)t的成功率ρ為:N定義2:ua完成任務(wù)t的平均成功度θ為:ua選取ma的算法既要保證完成任務(wù)的高成功率,同時(shí)也應(yīng)考慮到ma能力的變化,一方面ma可能向系統(tǒng)中的其它ma學(xué)習(xí)而提高能力,另一方面其它ua與ma的合作也可能提高ma的能力。為了保證完成任務(wù)的高成功率,ua應(yīng)盡量在集合MA在集合MA多級(jí)top-n隨機(jī)選擇算法描述如下:(1)集合的初始化(1)將MA(2)若系統(tǒng)中已有ua涉及過(guò)任務(wù)t,則ua通過(guò)向有經(jīng)驗(yàn)的ua學(xué)習(xí)完成MA否則ua從服務(wù)器中獲取各ma的能力信息。若有can＿do(ma(2)選取ma(或委托任務(wù),或獲取其能力)//*i,j和k分別用于在MA(1)若i≤ck(2)若i>ck(3)若i>ck(4)若對(duì)于所選的ma有:ma∈MA則將ma移入MA轉(zhuǎn)向(7)。(5)若對(duì)于所選的ma有:轉(zhuǎn)向(7)。若對(duì)于所選的ma有:則將ma將ma插入到MA轉(zhuǎn)向(7)。(6)若對(duì)于所選的ma有:ma∈MA則將ma移入到MA轉(zhuǎn)向(7)。(7)完成。算法中的ma3平均成功度由上述算法可知,若MA由上述表達(dá)式可知MA由此可見(jiàn),多級(jí)top-n隨機(jī)選擇算法既保證了ua完成任務(wù)t的成功率,又可以使系統(tǒng)隨ma的進(jìn)化而不斷提高ua完成任務(wù)t的平均成功度。而且通過(guò)參數(shù)c、L和n的調(diào)整可以使系統(tǒng)在完成任務(wù)的成功率和適應(yīng)性之間進(jìn)行調(diào)節(jié),從而使系統(tǒng)具有較好的靈活性。采用該算法時(shí),不必實(shí)時(shí)地跟蹤ma能力的動(dòng)態(tài)變化,算法通過(guò)對(duì)MA另外,可以將多級(jí)top-n隨機(jī)選擇算法的基本思想引入到傳統(tǒng)的合同網(wǎng)中。傳統(tǒng)的合同網(wǎng)通常采用廣播方式招標(biāo),這種方式在承攬者位于不同物理網(wǎng)絡(luò)(如Internet環(huán)境)時(shí)不太適合,若采用單播(unicast)方式進(jìn)行一對(duì)一的招標(biāo),當(dāng)承攬者較多時(shí)會(huì)造成較大的招投標(biāo)開(kāi)銷(xiāo)。若將合同網(wǎng)的招標(biāo)對(duì)象限制在集合MA4創(chuàng)新的算法本文針對(duì)合同網(wǎng)所存在的不足提出了Agent選擇合作伙伴的一種多級(jí)top-n隨機(jī)選擇算法,和合同網(wǎng)相比本算法實(shí)現(xiàn)簡(jiǎn)單,省去了招標(biāo)時(shí)的通信開(kāi)銷(xiāo)和時(shí)間開(kāi)