Agent任務調度與遷移策略研究

殷鋒社

（陜西工業職業技術學院 陜西 咸陽 712000）

為解決目前市場應用中電子商務在效率、成本和業務智能化方面的問題，文中在詳細論述移動Agent技術的基礎上提出了一種新的電子商務模式。

1 Multi-Agent系統

1.1 概念解析

Agent的5個概念：Agent組織、Agent平臺、系統Agent、Multi-Agent系統和Agent應用系統是容易被人們混淆的，在研究移動Agent系統之前，有必要對他們進行診釋。

1）Agent組織

Agent組織可以認為是Agent的集合和移動Agent系統的分布式問題求解機制，也是多Agent系統社會性的一個重要的方面。Agent組織是MAS研究的模型、組織和交互語言3個主要問題之一，組織的形成和演化問題是基于Agent的計算和Agent合作問題求解的關鍵。多Agent在問題求解中表現的組織形態就是組織結構。面向結構的Agent組織形成方法與人類社會的組織產生機制相符合，是一種目標明確的組織形成方法。一個為了完成一組目標的組織結構[1]為：

其中，A_ID是組織結構標識符，Role是非空的角色集合，Relation是角色關系集合，A_Goal是非空的組織目標集合，Manager是非空的組織管理者集合。

目前，關于Agent組織的形成方法有：①基于協商的合同網協議。當一個Agent發現自己面臨的問題難以獨立求解或者合作求解更有效時，通過與其他Agent的協商，將其部分或全部任務委托其他Agent來完成，在他們之間形成顧客與服務員關系型組織：②基于依賴關系的社會推理。通過對Agent之間依賴關系的社會推理，發現與其目標有依賴關系的其他Agent，與他們形成不同形式的合作組織；③基于對策論的聯盟形成。通過聯盟效用的計算與分配，依據Agent個體、聯盟和群體理性原則，在Agent之間形成不；一習的聯盟：④基于價洛調控的市場機制，通過市場價格的調整，Agent形成供求平衡下的買賣關系；⑤面向結構的組織形成。

組織結構的設計過程一般由5個步驟完成[2]：

①由不同Agent的共同目標出發，確定組織目標.；

②根據組織目標進行任務分解，劃分出不同的子任務；

③由子任務設計組織角色。

設一個組織中的Agent a和Agent b有部分共同求解目標，Agent a有目標集Ga，Agent b有目標集Gb

其中goalcl，goalc2是Agent a和Agent b的共同目標。在進行組織結構設計時，用戶向系統發出任務請求，Agent模板創建兩個Agent a和Agent b，系統Agent根據請求首先設計一個空的組織結構框架。并通知Agent a和Agent b，Agent a和Agent b收到組織結構框架設計成功的消息后，向系統發送各自的求解目標，供事務服務Agent進行任務分解，進一步完成組織目標和組織角色的設計。如果Agent a和Agent b沒有共同目標，則組織結構設計失敗，系統終止。

Agent組織角色的創建基于組織目標。通過把組織目標分解成各個子任務，并把相同或相似的子任務合并，由角色承擔不同的子任務，完成組織角色的創建。已創建的角色統一放入角色字典中。在創建過程中如果遇到相同或相似的組織角色則進行合并，并記錄組織角色的需求數量，供具體組織形成時參考使用。

在二演算中引入了一個新的操作原語new，用來表示創建一個空的組織結構，表示為new os，其中create org表示組織結構創建成功以后，啟動該進程建立具體的Agent組織。Milner給出了基本演算的形式語義。組織結構設計的語義[3]可描述如下：

MAS_ORG={user.Request

task

agent template.Create

Agent a，Agent b

agent Tran.Create

an empty os_frame&inform （msg， Agent a， Agent b））

match （msg）

Agent a.Send&Agent b.Send

Ga{goalal， goala2，……，goalcl， goalc2}

Gb{goalbl，goalb2，……，goalcl， goalc2）

Result=?common goal（Ga Gb）

if result=EMPTY

return （fail）

new os （os_frame）

task decomp （os_oal， os_task， Ga，Gb）

create_roles （os_task）

create_org（roles）

}

其中，EMPTY表示空集合。

2）Agent平臺

Agent平臺（也稱為Agent系統）是在Agent理論基礎上設計出來的提供給用戶開發或運行Agent應用系統的支撐環境，是MAS的重要組成部分。GeneralMagic公司的Telescript，IBM公司的Aglet和南京大學的Mogent等都是比較成熟的純Java的Agent平臺。Agent平臺的作用是負責為移動Agent建立安全、正確的運行環境，為其提供最基本的服務（包括創建、傳輸、執行），實施針對具體 Agent的約束機制、容錯策略、安全控制和通信機制等監督與控制功能。它還提供了一些用戶對系統進行訪問的方法，主要包括Agent和系統Agent的啟動控制、狀態的獲取、系統的輸入輸出、系統資源的維護和系統的關閉等。

Agent是用戶編程的主要對象，用戶利用Agent平臺中Agent模板創建Agent a終端用戶填寫Agent的屬性和模板中的任務字典，在平臺運行時，Agent類具體化為一個Agent實例，其屬性和行為來自模板。Agent為了實現移動，發送消息等通訊功能需要調用一些系統Agent的功能，這種調用是通過對系統Agent代理的Clone上的方法調用來實現，這樣的調用出于安全性考慮。

3）系統 Agent

系統Agent主要目的是為了實現移動Agent的定位、移動和發送消息等功能，它被分成幾個部分，每個部分實現部分相對獨立的功能。它通過注冊到自身的系統助手和平臺進行通訊，調用平臺上的函數，同時平臺可以直接對系統Agent進行訪問。在一個平臺上有多個系統Agent，承擔不同的任務，如目錄服務、事務服務、事件服務、應用服務和安全服務等，目錄服務維持Agent名字和其傳輸地址對應的目錄，提供移動Agent的定位信息，形成路由選擇；事務服務實現移動Agent的創建、移動、調度和資源分配；事件服務包含Agent傳輸協議和Agent通信協議，實現移動Agent間的事件傳遞；安全服務提供安全的執行環境；應用服務提供面向特定任務的服務接口。

4）Multi-Agent系統

Multi-Agent系統[4]（Multi-Agent System， MAS 是由一些聯合其知識、目標、職能和計劃的協作承擔任務或解決問題的不同的計算實體組成的集合，這些集合元素就是Agent，它們具有相互作用以實現到總的目標。MAS可被定義為：

其中，AP，As，Ao 分別表示 Agent平臺、 系統 Agent和Agent組織。每個目標由若干Agent協作完成。由此可見，MAS是由Agent平臺、系統Agen t和Agent組織組成的系統。

5）Agent應用系統

Agent應用系統是在Agent平臺上開發出來的程序系統，Agent是系統中的工作實體，Agent平臺是它的運行環境。實際上，Agent應用系統就是擁有一個或多個Agent組織的系統。如基于移動Agent的智能電子商務系統、智能搜索引擎等。以上五個概念之間的關系如圖1所示。

圖1 Agent應用系統Fig.1 Agent application system

1.2 研究現狀

MAS的研究始于20世紀70年代的分布式人工智能。此后，MAS的研究內容隨著年代的變化而不斷深入，MAS不僅僅是DAI領域的研究問題，同時相關科學的研究成果對它也起到了重要的影響作用，如管理科學、經濟學和社會學等。對經濟規律如市場機制、游戲理論、平衡概念等的深入研究將用于設計Agent交互策略。MAS研究者借助于游戲理論的研究成果，將其用于Agent談判策略的設計。管理學中的組織理論研究幫助我們認識并設計Agent組織。社會學中關于人類行為的研究則能使Agent具有人類社會某些特征，如角色分配、團隊和競爭等。MAS為AI的研究提供了一個新的機器學習、知識發現和知識表達模型。

1.3 Agent管理模型

為了加快移動Agent技術[5]的發展和推動其具體應用，一些標準化組織制紛紛訂了Agent規范，最有影響力的國際組織有OMG下屬的Agent Working Group和FIPA的MASIF規范、FIPA的FIPA97-99規范對Agent的名稱、管理、遷移、語言等進行了標準化。IBM提出了ATP （Agent Transport Protocol）框架結構，是一個Agent傳輸協議的最小實現。Agent管理是其應用的前提，負責Agent的的創建、注冊、agent定位、通信和移植等操作。Agent管理模型如圖2所示。

圖2 Agent管理模型Fig.2 Agent management model

1.4 典型的Multi-Agent系統

1）General Magic公司的Telescript

Telescript是General Magic公司推出的第一個商用移動Agent系統。它是用Telescript語言（一種面向對象的解釋性語言）編寫的。在Telescript中，Agent被編譯成為一種虛擬機的字節碼，該虛擬機是每個服務器的一部分。每一個網絡站點運行一個服務器來維護一個或多個虛擬的地點，地點通過檢查Agent加密的信任狀來識別其主人}`'1}a Agent之間的通信方式有：運行在同意地點的Agent可以相互調用對方的方法；在不同地點運行時需要建立連接，互相傳遞對象。Telescript是一個比較成功的移動Agent系統，其安全性、容錯性較好，執行效率較高，但由于Java的流行和優勢，必然導致它的失敗。General Magic公司開發了基于Java的Odyssey系統。

2）IBM公司的Aglet

Aglet是agent與applet合成的，是由日本IBM公司用純Java開發的移動Agent系統，并提供著實用的平臺一Aglet Workbench，讓人們開發或執行移動Agent系統。到目前為止，Aglet是非常成功和全面的系統，這主要表現在：Aglet系統首先提供一個上下文環境來管理Agent的基本行為，如創建、復制、分派、召回、喚醒以及清除等。Aglet采用消息傳遞的方式來傳遞消息對象進行通信。此外，基于安全上的考慮，Aglet并非讓外界直接存取其信息，而是透過一個代理（proxy）提供相應的接口與外界溝通。Workbench是一個可視化環境，用來建立使用移動Agent的應用系統.

2 基于組織的動態資源分配

2.1 資源描述

網絡結點上的資源是Agent完成任務的基礎，把與網絡結點配置有關的情況稱為該結點的系統資源。將資源分為設計資源、系統資源和Agent資源，并給出了系統資源的描述。實際上，任務設計和Agent都屬于MAS討論的問題，其系統資源的描述也不全面。文中將Agent執行任務所需的資源歸結為系統資源，包括機器硬件資源、軟件資源、網絡設備資源和信息資源。系統資源[6]具體描述如下：

Structure Sys Source

{

Integer NetNode 一 umber；

Structure Hard_Source；//機器硬件資源

Structure Soft_Source；//軟件資源

Structure NetDevice_Source；//網絡設備資源

Structure Info_Source；//信息資源

}

Structure Hard Source

{

CmpString Cmp_CPU；

CmpString Cmp_RAM；

CmpString Cmp_HD；

CmpString Cmp_Multi-Media_Dev；

CmpString Cmp_Input_Dev；

CmpString Cmp_Output_Dev；

}

Structure Soft Source

{

SoftString Soft_OS；

SoftString Softes Net；

SoftString Softes Application；

}

Structure NetDevice Source

{

NDString ND_Router；

NDString ND_Switcher；

NDString ND_Gateway；

}

Structure Info Source

{

InfoString Info_DB；

InfoString Info_KB；

InfoString Info_Files；

}

2.2 動態資源分配策略

隨著移動Agent應用的發展，如何為不同服務質量要求的用戶合理的分配有限的資源、提高使用效率，成為近期研究的熱點。近來研究者把微觀經濟學的方法引入移動Agent的資源分配領域，為這一領域研究提出了嶄新的思路。它們存在以下問題：1）只考慮了Agent的競爭，沒有考慮Agent的協作；2）沒有考慮資源的時間性；3）由于算法較復雜，導致了較大的系統開銷。可以采用操作系統中關于資源分配的策略進行Agent資源分配，但由于Agent資源含義不僅局限于硬件資源及Agent的動態、移動、協作等特性，簡單的操作系統資源分配策略是難以適應Agent資源分配的要求。由多個子目標組成的Agent組織執行用戶提交的任務，子目標由Agent協作完成，為了實現組織的目標，組織就應成為資源分配的基本單位考慮到資源的動態性及組織任務的執行時間、緊迫性和重要性等因素，這里給出了一種基于組織的動態資源分配算法。

3 基于EP算法的Agent任務調度

3.1 調度方法概述

Agent調度問題就是如何利用有限的網絡資源和時間完成指定的多個任務，屬于Job-shop問題。Job-shop是一類復雜且極具代表性的生產調度問題，其復雜性超乎想象，為解決這一問題，學者們作了大量研究工作，嘗試了許多方法，這些方法可分為兩類：指派方法和進化計算。

3.2 EP算法原理

進化規劃（Evolutionary Programming，EP）最早是由美國的L.J.Fogel，A.J.Owens等人首先提出的，EP是進化計算中的代表算法之一。文獻證明了他的動態尋優機理。算法流程如圖3所示。

圖3 EP算法流程Fig.3 EP algorithm flow

1）將問題的解編碼為數字串；

2）隨機產生S個可行解構成的初始種群，S為種群規模；

3）將當前種群中的S個個體進行變異，產生新的個體：

4）計算所產生的個體適應度函數值；

5）采取父子競爭策略，從2S個體中選出S個個體作為新一代種群，返回步驟③，重復此過程直到獲得滿意的解或達到給定的迭代次數。

以上算法是標準的EP算法，變異算子采用的是高斯變換，終止條件采用最大進化代數或出現滿意的個體。

3.3 Agent任務調度

調度任務是基于時間的序列，任務之間除了具有邏輯上的相關性外，還具有時間上的相關性，即任務必須在規定的時間內完成。調度方案S可以被描述為一個定時任務的序列集合，即

其中，Pl（t）代表第 1 個任務。

Pa（t）存在的約束如下：

1）定時

必須滿足下列時間約束is（i>+t（L）ate（1）

2）資源限制

任務的合理調度以使網絡負載均衡，充分發揮系統資源的效用。Agent的自治性、自適應性、協同性和可移動性等顯著特點為解決分布任務處理問題提供了新途徑。多Agent系統中的任務通過Agent調度器統一調度。系統任務分解Agent將求解的問題分解為若干子任務，并提出調度請求，調度器考慮到各任務的執行條件，如資源、時間、優先度等，選擇一定的調度算法，確定調度方案。系統資源由資源管理器管理和調配。執行任務的各Agent根據系統資源分布和實時要求派遣到相應的目標主機進行任務處理。調度模型如圖4所示。

圖4 Agent調度模型Fig.4 Agent scheduling model

4 移動Agent遷移

4.1 遷移機制分析

移動Agent（Mobile Agent，MA）的遷移與分布式對象的交互及Java Applet的下載有著很大的不同。在基于CORBA或DCOM的分布式對象系統中，一個對象能夠通過網絡遠程地調用其他對象的方法。但是，在兩個對象的交互過程，沒有任何一個是移動的。WWW中Applet的下載也僅是提供了一種從Web服務器把代碼下載到Web瀏覽器的機制，并沒有為相應狀態信息的遷移提供任何機制。

4.2 基于Java的動態遷移機制

MA的體系結構應包括Agent代碼部分、運行環境部分和Agent狀態部分。代碼部分是MA遷移過程中不可缺少的部分，是傳送給“數據”執行“計算”的部分；為了能在異構網絡環境中遷移，MA應具有與平臺無關，安全性要求高等特點，而Java可以較好的滿足這些要求。因為Java代碼的平臺無關性和Java虛擬機的廣泛分布性，為MA提供了良好的運行環境，具體包括MA所需的資源，對MA代碼的執行和遷移請求的響應，提供安全性認證的信息等：狀態部分保存MA在移動之前的狀態信息，以便當Agent遷移到另一個結點后重新獲取這些狀態信息，提高運行效率。

5 結束語

本章介紹了MAs的研究現狀與研究內容，解析了Agent組織、Agent平臺、系統 Agent，Multi-Agent系統和 Agent應用系統5個概念之間的關系，討論了Agent組織結構的形成機制及形式化描述。在MAS中，為了使已分配資源的移動Agent遷移到指定的結點執行任務，需要解決Agent的資源分配、任務調度和遷移問題。

[1]Geun-Sik J，Chae Y M.Intelligent electronic commerce[J].Expert Systems with Applications，2003，24（2）:151-151.

[2]Ryszard K，Lee M.Artificial intelligence in electronic commerce[J].Lecture Notes in Computer Science，2001，21（12）:133-134.

[3]Turowski K.Agent-based e-commerce in case of mass customization[J].Int J Production Economics，2002（75）:69-81.

[4]Malcolm B，Brian S.E-commerce oriented software agents[J].Computer Law&Security Report，2003，19（3）:201-211.

[5]Maamar Z.Association of users with software agents in ecommerce Electronic Commerce[J].Research and Applications，2002（1）:104-112.

[6]Fingar P.A CEO's guide to e-Commerce using objectoriented intelligent agent[J].Commerce Net Research Report，1998，9（19）:18-20.