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

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

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