mas環(huán)境下agen交互協(xié)作的實現(xiàn)

移動能源技術是一項新興的技術。該技術可以有效簡化分布式系統(tǒng)的設計、實現(xiàn)和維護。采用移動Agent計算模式可以有效地降低分布計算中的網(wǎng)絡負載,提高通信效率[1~3]。MAS(Multi-AgentSystem)是由自主的Agent通過協(xié)作完成某些任務或達到某些目標的計算系統(tǒng),它通過競爭或磋商等手段協(xié)調解決各Agent成員的目標和行為之間的矛盾與沖突。在MAS中,協(xié)作不僅能提高單個Agent以及由多Agent所形成的系統(tǒng)的整體行為性能,增強Agent及Agent系統(tǒng)解決問題的能力,使系統(tǒng)具有更好的靈活性。資源、能力的有限性和分布性使協(xié)作成為MAS的重要特征之一。Agent間進行協(xié)作的基礎是交互,而通信是實現(xiàn)Agent交互的一種重要方式和手段。采用何種通信模式和語言關系到能否有效地實現(xiàn)Agent的交互協(xié)作。把Agent應用于網(wǎng)絡環(huán)境中,還需要解決由Agent的移動性所帶來的問題,如:如何將代表用戶任務的Agent分配到適宜的網(wǎng)絡節(jié)點中執(zhí)行,以得到較高的效率;如何實現(xiàn)Agent的位置透明通信等。1基于遺傳算法的求解多Agent協(xié)同設計的基本目的是使參與設計的Agent各盡所能,充分利用網(wǎng)絡中的分布資源,故要將協(xié)同任務進行分解,將分解后的子任務分配給合適的Agent求解,這成為實現(xiàn)協(xié)同設計的一個重要問題,其關鍵技術是選擇何種任務調度算法。在網(wǎng)絡中,任務與資源的組合隨子任務的增加呈指數(shù)增長,在實際的協(xié)調設計中,還需兼顧到實時性,因此不能盲目搜索算法。當搜索空間過大時,不宜使用啟發(fā)式搜索方法。處理問題具有柔性和并行處理能力的遺傳算法可以在較大的狀態(tài)空間中隨機高效地采樣、搜索,很快逼近最優(yōu)解,故該算法適合作為子任務分配的調度算法。遺傳算法是一種求解問題的高效并行全局搜索方法,與其他搜索算法相比,它主要有以下特點:1)在搜索過程中能自動獲取和積累有關搜索空間的知識,并自適應控制搜索過程以逼近最優(yōu)解;2)搜索過程和優(yōu)化計算不依賴于信息梯度,適合處理傳統(tǒng)搜索方法難以解決的復雜非線性問題;3)可從任一初始化群體出發(fā),通過各種遺傳操作,逼近最優(yōu)解。遺傳算法具有“生成+檢測”的迭代過程,其基本處理流程如圖1所示。遺傳算法是一種群體型操作,它以群體中的所有個體作為對象,通過循環(huán)執(zhí)行選擇(selection)、交叉(crossover)和變異(mutation)三種操作,直到群體收斂到問題的最優(yōu)解。在遺傳算法中,可采用多種形式來描述染色體,如二進制數(shù)字串、矩陣等。下面用一個二維矩陣TN來描述:矩陣中的元素aij稱為基因,aij=1表示第j個子任務調度到第i個節(jié)點上。假設子任務個數(shù)大于網(wǎng)絡節(jié)點數(shù),故每個節(jié)點最少分配一個子任務且只能分配到一個節(jié)點上。所以TN矩陣應滿足約束條件:在任務調度問題中,先按約束條件生成一定數(shù)量的染色體,從中選取最好的個體加入初始群體,不斷重復這一過程,直到初始群體的個數(shù)達到預定的數(shù)量。遺傳算法以該初始群體為起點,通過對染色體中的基因進行各種遺傳操作,逐代進化,直到獲得一個滿足要求的染色體即是子任務調度的結果。當子任務個數(shù)較少,每個子任務可以單獨占用一個網(wǎng)絡節(jié)點時,稱為粗粒度任務調度。粗粒度任務調度只需找到一個資源配置滿足或接近資源需求的節(jié)點。當子任務個數(shù)較多,每個節(jié)點要處理多個子任務時,稱為細粒度任務調度。在調度模型中,以子任務的個數(shù)相對于系統(tǒng)可調度節(jié)點數(shù)來衡量子任務的粒度。當子任務個數(shù)小于系統(tǒng)可調度節(jié)點數(shù)時,為粗粒度調度,否則為細粒度調度。粗粒度調度多采用Agent競爭法或預先指定法,而細粒度調度則采用遺傳算法。2kqml的概念Agent通常應用于網(wǎng)絡環(huán)境中,有時要跨多個平臺,而網(wǎng)絡中各個平臺使用的語言不相同。為實現(xiàn)Agent間的通信,必須建立統(tǒng)一的Agent通信語言(AgentCommunicationLanguage,ACL)。作為Agent的通信語言,ACL須具備三個特征:1)非耦合性:要求在空間和時間上以非耦合方式協(xié)調Agent之間的交互。即當一個目標Agent并不存在時,另一個Agent也能執(zhí)行發(fā)送;2)聯(lián)合聲明:不需要直接指明建立通信的Agent名稱,而是通過向網(wǎng)絡聲明一個需求的模板,由對方根據(jù)相應的匹配機制找到符合要求的Agent;3)關系分割:要求由主程序語言導出的ACL不受主程序語言的影響。Agent在應用ACL實現(xiàn)通信時應遵循三個準則:1)真實性:Agent應說實話;2)自治性:Agent應有一定程度的獨立性;3)承擔義務:如果命令某個Agent執(zhí)行一個任務,它應當盡力完成。知識查詢與操縱語言(KnowledgeQueryandManipulationLanguage,KQML)作為一種獲得廣泛應用的ACL,正在成為Agent之間通信的事實標準。KQML是一種交換知識和信息的描述性語言,它定義了Agent間傳遞消息的格式和消息處理的協(xié)議,通過提供一套標準的通信原語實現(xiàn)Agent間信息的交流和知識的共享。它既是一種Agent間消息的表示格式,也是一種處理消息的協(xié)議。KQML是一種層次結構型語言,它可分為三個層次:1)內容層:消息所包含的內容,用相應的程序語言表示。該語言可用ASCII字符或二進制的形式表示。KQML語言的具體實現(xiàn)并不關心消息內容的具體含義;2)通信層:描述與通信雙方相關的一組屬性參數(shù),包括通信底層參數(shù),消息接收者和發(fā)送者的標識以及與通信相連的標識;3)消息層:為KQML的核心,主要確定消息傳送所使用的協(xié)議,由發(fā)送方提供一個與內涵相關的原語,指明消息中的內涵為確認、詢問、命令或其他的原語操作。KQML的語法簡單,為基于平衡的括號表。表開始為行為原語名稱,其余部分為一組以“:關鍵字”形式出現(xiàn)的參數(shù)表,為實際應用中根據(jù)需要進行修改提供了方便。KQML定義了一組預留的含義明確的行為原語,開發(fā)人員還可以根據(jù)實際應用的需要添加滿足KQML標準的新原語。習慣上,一條KQML行為原語也稱為一條消息。典型的KQML消息如下:其中,KQML消息的行為原語是ask-one;“:sender”表示的是消息的發(fā)送者;“:receiver”表示消息的接收者;“:content”表示消息內容;“:reply-with”表示下條消息對本條消息的響應;“:language”表示消息內容使用語言的名稱;“:ontology”表示消息內容使用的實體集的名稱;“:content”為內容層;“:sender,:receiver,:reply-with”構成了通信層;行為原語“ask-one,:language,:ontology”為消息層。3多agent通信模型通信模式與多Agent協(xié)作的組織方式緊密相關,通信模式的優(yōu)劣關系到整個系統(tǒng)的效能。在實踐中通常采用下面兩種方法:1)直接通信法:由Agent自己負責與其他Agent的談判。Agent實體中需集成進一定數(shù)量的專門處理談判的代碼,這使Agent實體的設計復雜化。它的另一個缺陷是當網(wǎng)絡中Agent數(shù)量較多時,Agent之間建立通信連接的時間較長。2)輔助協(xié)作法:首先把Agent分類,將處于同一地域或一定社會中的Agent組成一個Agent群,在每個Agent群中設立一個專門用于通信的裝置,此裝置也由一組具有某種特定功能的Agent組成。Agent群中的Agent只與此裝置通信,此裝置根據(jù)請求的模板,查找匹配的通信對象。當同一個Agent群中存在適合的匹配對象時,可以直接通過此裝置建立通信。但當匹配對象在其他Agent群中時,通信過程就必須加入與其他Agent群中的裝置之間的通信。多種通信方式的結合形成了一個Agent群的聯(lián)盟,它不但解決了Agent自己管理通信時復雜的設計,也解決了當Agent數(shù)量太大時直接通信耗時多的問題。下面是一個基于輔助協(xié)作法的多Agent通信模型。MobileAgent需要在一定的環(huán)境中運行,這種環(huán)境稱為碼頭(dock)。它不但使Agent可駐留于網(wǎng)絡中某節(jié)點上,訪問該節(jié)點的資源,還提供了Agent與其他Agent進行通信的場所。Agent的交互行為如圖2所示。若一個對象有自己可控制的線程稱為主動對象,否則稱為被動對象。Agent將一個內嵌在KQML中的消息,通過碼頭提供的服務,發(fā)送給接收對象(本地對象或其他Agent)。在圖2的左邊部分,Agent是主動的,在KQML的發(fā)送和接收過程中,Agent還可與其他Agent或本地對象進行通信。碼頭和本地對象是由Agent的行為引起的一種被動反應,是被動對象。在圖2的右邊部分,兩個Agent都是主動的,在它們通信的過程中,均可與其他的Agent進行通信。Agent的典型生存期有三個階段:1)Agent在某個碼頭上被創(chuàng)建;2)Agent訪問一個或多個碼頭;3)Agent終止。在Agent訪問一個碼頭的過程中,它利用KQML消息與碼頭、本地對象或其他Agent進行通信,碼頭則提供給Agent各種服務,如路由選擇、安全檢查、Agent遷移等。Agent最常見的行為是與本地對象或其他的本地碼頭上的Agent進行通信。Agent的通信模型如圖3所示。圖中的通信模型主要有Agent、碼頭和本地對象三種。本地對象是靜態(tài)的能夠理解KQML消息的對象,碼頭是提供給Agent和本地對象的服務場所,每一個Agent只可同時訪問一個碼頭。Agent通過發(fā)送和接收KQML消息這種唯一的通信方式與其他對象進行通信。KQML消息通常由碼頭進行路由選擇,使碼頭對消息進行安全的授權檢查。碼頭不必知道或解釋KQML消息的內容,使它對具體的應用細節(jié)透明,防止了可能對Agent的改變,提高了系統(tǒng)的安全性。Agent和本地對象同時只能與一個碼頭相連接。如果一個Agent希望同與另一個碼頭相連的本地對象通信時,它必須離開當前的碼頭遷移到另一個碼頭上。即KQML通信只能在同一個JVM中進行,所以,Agent要與其他的JVM中的對象通信,必須進行遷移。4添加映射表、顯示當前域內開發(fā)的信息在基于MAS的網(wǎng)絡環(huán)境中,要實現(xiàn)Agent間的通信,接收消息的Agent的地址必須明確。而Agent的位置在網(wǎng)絡中是不斷變化的,使對Agent的尋址較困難。但無論采用由發(fā)生位置遷移的Agent主動通知其他Agent的方式或其他Agent通信前進行查詢的方式來解決對Agent的尋址,都會增加網(wǎng)絡和Agent的負擔,較理想的解決方法是在MAS環(huán)境中設置一個專門提供Agent位置服務的機制——Agent位置追蹤(AgentLocationTracing,ALT)。目前所采用的Agent位置追蹤方法主要有三種:1)樹狀域追蹤:將MAS環(huán)境中的每一計算機系統(tǒng)看作一個葉子節(jié)點域,由它提供名字服務,建立當前域內所有Agent與其所在位置的映射關系表。當Agent被創(chuàng)建或發(fā)生位置改變時,通過修改相應域的映射表實現(xiàn)對Agent的位置追蹤。2)分布式追蹤:不提供名字服務,利用“前指鏈”來實現(xiàn)Agent的位置透明。即Agent每發(fā)生一次位置變化,都會在前一個駐留點留下一個指向當前位置的指針,發(fā)送者只要找到該Agent的創(chuàng)建位置即可循著該前向指針鏈找到目標Agent。3)由Agent創(chuàng)建地提供地址:當Agent發(fā)生位置改變時,系統(tǒng)在該Agent創(chuàng)建地記錄其當前位置,消息均發(fā)送到創(chuàng)建地,若該Agent不在創(chuàng)建地,則由創(chuàng)建地轉發(fā)。采用任一方法,消息發(fā)送Agent通過ALT就可找到消息接收者的當前位置,完成消息的傳送或轉發(fā),實現(xiàn)了對Agent透明尋址。在移動Agent的通信過程中,經(jīng)常會發(fā)生通信失效的情況。如:Agent1要向主機A上的Agent2發(fā)送消息,但在消息發(fā)送過程中,Agent2從主機A遷移到了主機B,該消息因無法正確找到接收者,而可能丟失,此現(xiàn)象稱為通信失效。通信失效是Multi-Agent系統(tǒng)中Agent協(xié)作的致命缺陷,它使協(xié)作中的Agent不能及時或無法正確接收協(xié)作消息,導致協(xié)作失敗。對于這個問題,如果規(guī)定在Agent遷移過程中拒絕接收任何消息,容易增加發(fā)送方的負荷并引起消息丟失。較好的解決方法是在MAS系統(tǒng)中增設一緩存機制(AgentMessageCache,AMC),在Agent完成遷移后,再將消息轉發(fā)給它。具體實現(xiàn)過程如下:1)Agent遷移到某位置時,由該位置為其分配一消息代理,負責處理發(fā)送給Agent的消息,代理的生命周期和Agent在該位置的生命周期相同;2)在Agent的遷移過程中,代理的生命周期并未結束,它仍然負責接收發(fā)送給該Agent的消息,并緩存起來;3)Agent遷移成功后,由新位置為其分配消息代理,前任代理將緩存的消息打包轉發(fā)給新代理,然后結束自己的生命周期;4)若Agent遷移失敗,仍由原代理負責接收消息。因此在Agent的整個生