社會系統(tǒng)MAS分布仿真中的Agent優(yōu)化調度算法

戴華，林杰

（同濟大學經(jīng)濟與管理學院，上海 200092）

社會系統(tǒng)MAS分布仿真中的Agent優(yōu)化調度算法

戴華，林杰

（同濟大學經(jīng)濟與管理學院，上海 200092）

針對分布式多Agent系統(tǒng)在復雜社會系統(tǒng)仿真應用中的運算特性，設計了一個基于分布式結構的Agent調度框架并提出了Agent的動態(tài)優(yōu)化調度算法.該算法綜合考慮了仿真過程中仿真節(jié)點運算負載和Agent通信結構的變化，通過優(yōu)化Agent的調度和分配實現(xiàn)各仿真節(jié)點負載的動態(tài)均衡以及多Agent系統(tǒng)中跨節(jié)點全局通信量的減少.仿真實驗分析表明提出的算法能夠有效提高此類仿真應用的運算性能以及減少仿真執(zhí)行的時間.

多Agent系統(tǒng)；復雜系統(tǒng)；分布式仿真；調度優(yōu)化

1 引言

隨著計算機技術的發(fā)展和廣泛應用，在許多復雜社會系統(tǒng)（如制造系統(tǒng)，供應鏈系統(tǒng)等）的分析和研究中，利用計算機進行建模與仿真是廣泛使用的一類分析方法和技術［1-3］.特別是當前流行的基于Agent的微觀仿真建模方法，成為了研究復雜社會系統(tǒng)的重要方法之一［4，5］.多Agent系統(tǒng)（MAS）能夠對復雜社會系統(tǒng)中的各個對象實體進行有效的定義以及功能特性上的模擬，并在計算機系統(tǒng)中進行仿真實驗，通過實驗的數(shù)據(jù)和評估指標對系統(tǒng)運作和性能進行直觀的量化分析和評價，具有很好的可重復性、可試驗性、可擴展性等優(yōu)點.

為適應復雜和更大規(guī)模仿真應用的需要，分布式的仿真運行架構成為必然的選擇.對于基于分布式多Agent系統(tǒng)的仿真應用而言，大量參與仿真的Agent由于仿真過程中運算量的可變性和不可預知性，極易會造成局部某些仿真節(jié)點的運算負載過重，從而影響整個仿真運算的效率甚至使仿真過程崩潰.同時，在分布式環(huán)境下Agent之間的動態(tài)消息通信也會帶來大量冗余的網(wǎng)絡通信量而影響仿真的執(zhí)行時間和效率［6，7］.因此在有限的計算資源條件下，實施較大規(guī)模的系統(tǒng)仿真實驗時，平衡運算節(jié)點的負載并減少節(jié)點間冗余的消息通信成為提高此類系統(tǒng)仿真運算效率和性能的關鍵.在傳統(tǒng)分布式計算的負載均衡調度問題中，主要是針對計算任務如何在運算節(jié)點間進行合理有效地調度和分配［8，9］，而基于Agent的分布式仿真中，Agent作為運算的基本單元和載體，負載的平衡過程主要依賴于Agent在各個仿真節(jié)點之間的調度和分配.此外，在基于Agent的系統(tǒng)仿真中，參與仿真的Agent都是基于某個特定功能和結構進行劃分，并不是同質的計算單元，在仿真過程中不能將一個Agent的計算任務簡單分配給另一個Agent.同時，復雜社會系統(tǒng)的仿真過程往往是基于離散事件驅動，仿真Agent之間有復雜的邏輯關聯(lián)，Agent的行為會受到其他某些Agent的影響，在不破壞各個事件邏輯執(zhí)行序列的情況下進行Agent的動態(tài)調度也是一個復雜的過程.在已有的相關研究中.如將Agent視為獨立且相互關聯(lián)的計算單元，通過對Agent計算任務的進行合理調配實現(xiàn)任務的高效執(zhí)行［10，11］.此外，基于某些設定的計分規(guī)則來對Agent的移動和調度進行判斷的方法［12］被設計出來以解決局部計算資源的過載問題，文獻［6，7，13，14］針對MAS中Agent的消息通信特性，提出了在相關應用中減小和優(yōu)化MAS消息通信的一些方法.經(jīng)濟市場領域中資源分配的博弈機制也被用于解決和實現(xiàn)MAS負載動態(tài)均衡問題［15］.

與傳統(tǒng)的并行與分布式計算或仿真過程相比，基于多Agent系統(tǒng)的社會系統(tǒng)仿真具有自身的一些特性.如上所述，目前提出的一些方法中，或是不完全適合基于Agent的社會系統(tǒng)仿真中的負載均衡與調度，如基于任務分配和調度的方式；或是在Agent的分配和遷移上沒有充分考慮到Agent之間通信交互的關聯(lián)性和動態(tài)性，此外，普遍采用固定的負載監(jiān)測閾值來作為負載調度的依據(jù)，對仿真過程中復雜多變負載狀態(tài)缺乏靈敏性而影響實施調度的效果，因此已有的一些方法不能很好地解決此類并行分布式仿真應用的負載均衡和調度問題.本文針對此類仿真的運算特性，綜合考慮了Agent之間的通信結構和各仿真節(jié)點負載的動態(tài)變化，提出了實施動態(tài)負載調度的框架及相關的Agent優(yōu)化調度算法來提高分布式仿真運算的效率和性能.仿真實驗的結果表明，所提出的算法在總體負載均衡性和仿真運行的時間上均有較好的表現(xiàn).

2 問題描述

2.1 Agent調度優(yōu)化問題

在基于分布式Agent的仿真運算中，大量Agent散布在不同分布式主機節(jié)點上，Agent以消息交互的方式進行通信和協(xié)作，Agent之間的消息通信因Agent所處節(jié)點位置的不同，包括節(jié)點內部的消息通信和跨節(jié)點的消息通信，通過Agent在節(jié)點之間的遷移能夠實現(xiàn)這兩種消息通信的轉換.由于跨節(jié)點的消息通信在處理時間的消耗上要遠大于內部的消息通信處理，因此一個最優(yōu)的Agent調度分配既要保證各個仿真節(jié)點不因為過載造成仿真失效，又要最大限度地減少Agent系統(tǒng)中跨節(jié)點的全局網(wǎng)絡消息通信量，即系統(tǒng)通信負載.式（1）定義和描述了一個最優(yōu)的Agent調度分配應滿足的條件，其中σ表示所有節(jié)點運算負載的均方差，Φ表示MAS中跨節(jié)點的Agent通信總量，α是權重系數(shù)，Wk表示任意某個節(jié)點的運算負載量，表示所有節(jié)點的平均負載量，Th是設定的節(jié)點負載上限閾值，Cij是任意兩個不同節(jié)點Hi，Hj之間的通信量，m表示分布式仿真節(jié)點的數(shù)量.

求解滿足上述條件的Agent分布是一個典型的NP問題，同時由于仿真運行中節(jié)點負載和Agent交互是動態(tài)可變的，特別在Agent數(shù)量相對較多時，在解空間中求解一個全局最優(yōu)調度方案需要消耗大量的計算時間，因此無法有效地滿足系統(tǒng)仿真過程中動態(tài)實時調度的要求.為了在動態(tài)調度過程中能實時地做出合理的Agent調度和分配，本文通過周期性監(jiān)測及調度優(yōu)化的方法，利用各周期時間點相應的節(jié)點負載狀態(tài)與Agent之間的通信結構來實時地給出一個局部優(yōu)化的Agent調度和分配方案，實現(xiàn)動態(tài)的Agent通信優(yōu)化和節(jié)點負載均衡，以此提高系統(tǒng)運算效率并加快仿真執(zhí)行時間.

2.2 基于分布式MAS的社會系統(tǒng)仿真特性

與其他分布式計算系統(tǒng)類似，基于MAS的社會系統(tǒng)分布式仿真也是一個分布式計算過程.但由于社會系統(tǒng)的運作特性，其仿真運算有如下特點：1）由于社會系統(tǒng)自身結構和功能的復雜性，仿真運算過程中的負載和Agent之間的通信結構模式較一般運算有更高的隨機性和動態(tài)性；2）社會系統(tǒng)仿真模型中，參與仿真運行的Agent往往是具有特定功能和角色的實體，運算任務在Agent之間不具備一般的傳遞性；3）在基于離散事件驅動的社會系統(tǒng)的仿真過程中，Agent的調度和遷移需要協(xié)調和維護整個仿真過程的時間同步和各個并發(fā)事件的邏輯順序.

針對上述運算特性，在本文設計的Agent動態(tài)優(yōu)化調度算法中，進行了以下前提條件的假設：1）仿真Agent在計算資源使用權限上是一致的且其運算不依賴于某個特定的仿真節(jié)點；2）Agent之間跨節(jié)點的消息交互時間遠大于在節(jié)點內部的通信；3）Agent在不同節(jié)點之間移動的代價是相同的.

3 動態(tài)負載均衡調度算法

3.1 調度框架

本文設計了一個層次化的分布式Agent調度框架來實現(xiàn)對仿真Agent的動態(tài)調度和分配，圖1給出了調度框架的基本結構，其中全局負載調度Agent（GLSA）是進行全局調度和控制的Agent，區(qū)域負載調度Agent（DLSA）是分布在各個仿真節(jié)點上負責對應節(jié)點區(qū)域調度操作的Agent.GLSA與各DLSA共同構成了層次化的調度控制結構，分散在各節(jié)點的DLSA執(zhí)行與所在節(jié)點相關的Agent調度與分配操作，GLSA則在更高的層面對全局調度進行協(xié)調，該結構模式有效地分解了實施調度控制操作的運算任務，充分發(fā)揮了分布式計算的優(yōu)點.在系統(tǒng)運行過程中，GLSA以及分散的DLSA均常駐于對應的仿真節(jié)點上，其他參與仿真的Agent則根據(jù)設計的調度分配算法在各仿真節(jié)點之間進行動態(tài)地調度.

圖1 Agent層次調度框架Fig.1The level scheduling framework for agent

在需要進行Agent調度操作時，提出的算法通過選擇一個最佳Agent組的方式來實施Agent在相應節(jié)點的調度遷移，算法定義的Agent組是包含若干Agent的一個集合，組中Agent的選取充分考慮了當前Agent之間的通信關聯(lián)和聚集性.相比于提出的對Agent進行逐個單獨選取并遷移的調度方式，基于選取最佳Agent組的調度方式不僅能快速有效地降低過載節(jié)點的負載，還能避免逐個調度方法中由于未充分考慮Agent之間的通信結構和關聯(lián)性而增加額外的跨節(jié)點通信量的情況，從而利用Agent的優(yōu)化調度最大限度地減少MAS中的全局網(wǎng)絡通信量.框架中動態(tài)調度的實現(xiàn)主要包括兩個過程，一個是在仿真過程中對節(jié)點負載進行周期性監(jiān)測與控制；另一個是發(fā)生節(jié)點運算過載后進行Agent的優(yōu)化分配和調度，該過程包括對過載節(jié)點中最佳遷移Agent組的選取及Agent組向目標節(jié)點的遷移. 3.2負載動態(tài)監(jiān)測和調度控制

負載動態(tài)監(jiān)測過程通過設定的某個周期時間對節(jié)點的負載狀態(tài)進行監(jiān)控，當某個周期監(jiān)測點發(fā)生節(jié)點負載超過特定閾值時，將執(zhí)行相應的Agent優(yōu)化調度操作，此時仿真的邏輯時間推進將暫停，直至整個調度過程完成；反之仿真過程將不會停止.為了能更好的實現(xiàn)各個節(jié)點負載的均衡調度以提高節(jié)點的計算效率，本文運用了可變閾值的監(jiān)測方法，并利用式（2）給出了可變閾值的定義.其中Th（t）表示在監(jiān)測周期時間點t的負載閾值，（t）表示所有節(jié)點在t時間點的平均負載值，λ是時序相關的負載平均值的比重系數(shù)，γ是負載閾值的調節(jié)系數(shù)，主要是控制可承受的負載擾動范圍.

下面的算法給出了GLSA和各DLSA共同實施負載監(jiān)測和控制操作的描述.

步驟1在監(jiān)測時間周期時間點t，GLSA接收來自各個DLSA發(fā)送來的節(jié)點負載值Wi（t）；

步驟3將各個仿真節(jié)點按當前負載量的從大到小排列得到負載狀態(tài)隊列Q，判斷Q中是否有節(jié)點負載值大于當前的Th（t），如果成立轉入步驟4，否則轉入步驟7；

步驟4掛起當前的仿真推進進程，并向超過當前負載閾值的仿真節(jié)點的DLSA發(fā)送負載調度信息和當前負載狀態(tài)隊列Q；

步驟5結合當前負載狀態(tài)隊列Q，過載節(jié)點的DLSA選擇相應的遷移Agent組和遷移目標節(jié)點，并將組中的Agent遷移進行遷移，實現(xiàn)負載的均衡調度；

步驟6繼續(xù)當前仿真運算進程；

步驟7在下一個監(jiān)測周期返回步驟1.

3.3 Agent優(yōu)化分配與調度

如上所述，提出的算法在實施Agent優(yōu)化調度時，采用了基于Agent組的分配和調度方式.Agent組的選擇則由Agent之間的通信關聯(lián)度來確定.Agent之間的消息交互是MAS運行的基礎和引起系統(tǒng)通信量變化的因素，因此本文中通過Agent之間的消息交互數(shù)量來度量Agent之間的關聯(lián)程度和Agent內部及外部的通信量大小.在式（3）中利用Agent的消息量定義并量化了在兩個節(jié)點之間遷移某個Agent組引起的全局通信量變化指標，其中mij表示任意兩個Agent，ai,aj之間的消息通信量，G表示某個包含若干Agent的備選Agent組，Ai和Aj分別表示對應節(jié)點當前包含的Agent集合.

由式（3）的定義可知，為盡量減少跨節(jié)點的Agent通信量，在選擇要遷移的Agent組時，其Δ（G）數(shù)值越大，則表明該組越適合作為實施調度遷移的Agent組.因此式（3）可以作為選定最佳遷移Agent組的判定指標.在下面的算法中給出了當需要進行負載調度操作時，在對應過載節(jié)點中DLSA進行目標遷移節(jié)點和最佳遷移Agent組選擇的算法步驟：

步驟1利用過載節(jié)點（Hi）當前的負載量（Wi），通過公式OutNum=「（Wi-Th）Ni/Wi」來量化需遷移的Agent數(shù)量；

步驟2在當前節(jié)點負載狀態(tài)隊列Q中，選取隊尾負載最小且未被選擇過的節(jié)點（Hj）作為調度遷移的目標節(jié)點，并結合Hj當前的負載量Wj用公式InNum=「（Th-Wj）Nj/Wj」計算Hj可容納的Agent數(shù)量；

步驟3從當前過載節(jié)點Hi中選取某個未被遍歷過的Agent（ai），并將ai放入備選遷移Agent組G′中；

步驟4將與ai關聯(lián)的所有Agent放入一個臨時Agent集合T中；

步驟6將ak從S中取出，并加入G′中，同時將與ak存在通信關聯(lián)的且不在G′中的Agent放入臨時集合T中；

步驟7判斷G′中的Agent數(shù)量是否小于min（InNum,OutNum），若是則轉入步驟5，否則將本次得到的備選組G′放入一個備選組的集合S中；

步驟8如果Hi中的Agent遍歷未完成，則轉入步驟3；

步驟9在備選組集合S中查找具有最大Δ（G）值的備選組，并將該組選定為遷移到Hj的Agent組G，并得到本次優(yōu)化調度的Agent組與目標節(jié)點的組合〈G,Hj〉；

步驟10若遷移組G中累計的Agent的數(shù)量小于OutNum，則返回步驟2.

算法在Agent組中成員Agent的選取上利用了Agent之間的通信關聯(lián)性以及動態(tài)交互結構，通過當前的負載狀態(tài)隊列信息，并結合定義的InNum和OutNum來量化平衡各節(jié)點負載時所需調度的Agent數(shù)量，將隊首過載節(jié)點中的Agent以優(yōu)化分組的形式向負載相對較輕的隊尾節(jié)點進行調度遷移.

3.4 算法性能分析

在上述算法實現(xiàn)中，對目標遷移節(jié)點的選擇主要根據(jù)負載狀態(tài)隊列來實現(xiàn)，求解并實現(xiàn)隊列的排序計算時間主要取決于主機的數(shù)量，其時間復雜度為O（m2）.在最佳Agent組的生成和選擇上，設ρ=n/m表示節(jié)點的Agent平均密度，其中n,m分別是Agent總數(shù)和節(jié)點數(shù).可知過載節(jié)點中選取Agent組的大小為（1-Th/Wi）ρ，確定最佳Agent組需要對該節(jié)點的所有Agent（數(shù)量為ρ）進行遍歷，所以組選擇過程的時間復雜度為O（ρ2）.

4 實驗分析

4.1 實驗平臺

為了驗證所提出算法在基于MAS的社會系統(tǒng)分布式仿真應用中的有效性，本文利用面向Agent的編程工具組件JADE開發(fā)了一個實驗平臺，該平臺用于實施基于多Agent的供應鏈場景模型的運作過程仿真，同時實驗平臺利用設計的GLSA及DLSA來實現(xiàn)層次化的動態(tài)調度算法，其中實現(xiàn)算法所涉及的Agent基本功能屬性如消息交互以及遷移等都繼承JADE組件提供的底層功能接口.在平臺中有五種類型的仿真Agent來構建供應鏈仿真模型，其中包括生產(chǎn)制造Agent，生產(chǎn)計劃Agent，庫存Agent，運輸Agent以及運輸計劃Agent.在實驗分析中，用于實施仿真實驗的不同規(guī)模和結構的供應鏈場景MAS模型都由繼承這五種Agent類型的若干仿真Agent構成.

在供應鏈場景的MAS模型中包括了由仿真Agent組成的若干供應商、生產(chǎn)商以及分銷商，模型的仿真過程是基于離散事件驅動，模擬供應鏈場景模型完成一定數(shù)量的產(chǎn)品訂單的過程.在仿真時各分銷商給出一定數(shù)量的訂貨量需求，模型在訂單驅動下開始運作，各生產(chǎn)商利用供應商提供的原材料根據(jù)自身的生產(chǎn)線進行產(chǎn)品生產(chǎn)，原材料及產(chǎn)品在供應商、生產(chǎn)商及分銷商之間運輸，當各個分銷商的訂貨量滿足后仿真過程結束.仿真過程中參與仿真的Agent根據(jù)各自的角色功能自適應地交互和協(xié)作，各仿真Agent的事件活動運用保守時間管理機制來推進，直至完成設定的模型場景任務.在這個過程中，由于仿真邏輯時間的推進以及仿真Agent各自運行狀態(tài)，Agent之間的相互通信關系和運算負載都會動態(tài)地變化.

4.2 仿真實驗的環(huán)境和參數(shù)設定

在仿真實驗中利用十臺互聯(lián)的主機組成分布式仿真節(jié)點實施仿真分析實驗，其中一臺機器作為中心控制節(jié)點，其他主機作為仿真運行節(jié)點.在仿真監(jiān)測中，節(jié)點的負載狀態(tài)利用公式Wi=βUc+（1-β）Um,0＜β＜1度量，其中Uc和Um分別是主機的CPU和內存的使用率，β為兩者之間的權重系數(shù).根據(jù)仿真實驗環(huán)境和不同仿真模型，在表1中給出了實驗中實施調度算法所設定的各個參數(shù)值，其中監(jiān)測間隔周期根據(jù)仿真規(guī)模在30～60s之間進行調整.

表1 實驗參數(shù)設定Table 1Parameters in experiments

4.3 實驗對比分析

實驗分析主要從負載均衡性能和仿真執(zhí)行時間的消耗兩個方面，對所提出的優(yōu)化調度算法進行檢驗.實驗中引入了靜態(tài)Agent均勻分布方法作為參照方法與所提出算法進行對比分析.參照方法在仿真執(zhí)行前將所有仿真Agent隨機地平均分配到不同節(jié)點上，且仿真過程中不進行Agent的動態(tài)調度.由式（2）中對負載均方差的定義可知，負載值均方差σ的數(shù)值越小，說明在仿真過程中各節(jié)點的計算負載具有較好的均衡性和較小的波動，計算資源的綜合利用率就越高，同時節(jié)點的過載風險也相應降低，因此σ值可作為分布式節(jié)點綜合運算性能的一個有效指標.在圖2中將本文提出的算法（PA）和引入的參照方法（RA）在負載均衡性能方面進行了對比.

圖2（a）給出了在上述兩種情形下，同一仿真模型的仿真運行過程中各節(jié)點的負載值均方差σ隨監(jiān)測周期時間點變化的σ值.從圖中可以看到，在整個仿真運行過程中使用提出的動態(tài)調度算法后得到的σ值總體上要低于作為對比的參照方法，且該數(shù)值的波動也相對較小.此外，在圖2（b）中給出了在兩種情形下，針對不同Agent規(guī)模（NAgent）的仿真模型，對應的整個仿真過程中得到所有σ值的平均值（σav）變化.圖中σav的變化趨勢表明，隨著仿真Agent規(guī)模的增加，在整個仿真過程中兩種情況下的σav都呈逐步下降趨勢，但在PA情形下的σav總體上低于RA情形下的數(shù)值，這說明實施了提出的優(yōu)化調度算法有更好的全局負載均衡性.

圖2 負載均衡性能分析Fig.2 The analysis of load balancing performance

圖3對上述兩種情況下的仿真運行時間進行了對比分析，圖中給出了在不同Agent仿真規(guī)模NAgent下提出算法（PA）與參照方法（RA）的仿真執(zhí)行時間的比值η（η=TPA：TRA）變化趨勢.在Agent規(guī)模較小時，兩者的執(zhí)行時間比值接近且約大于1，表明此時兩者的仿真時間消耗比較接近，但PA情形下的時間消耗稍多，這是由于在動態(tài)調度算法中對Agent組選取和遷移操作會產(chǎn)生額外的時間消耗，執(zhí)行優(yōu)化調度后減少的時間消耗無法從總體上抵消算法產(chǎn)生的時間消耗.但隨著仿真Agent規(guī)模的增大及相互通信增多，所提出算法在仿真執(zhí)行時間上的占比開始逐漸減少，圖中可以看到PA與RA的仿真執(zhí)行時間比值η呈逐步下降趨勢.這表明在相對較大的Agent規(guī)模下，優(yōu)化調度后減少的時間消耗逐漸彌補了調度過程本身產(chǎn)生的時間消耗，并使總的仿真時間得到有效降低.因此運用提出的動態(tài)優(yōu)化調度算法在總的執(zhí)行時間上也有明顯的改善.

圖3 仿真時間比值η（η=TPA：TRA）與Agent規(guī)模NAgent的關系Fig.3The relationship between simulation time-ratio η（η=TPA：TRA）and Agent scale NAgent

5 結束語

基于多Agent系統(tǒng)的計算機仿真方法在社會系統(tǒng)分析和研究中越來越普遍，提高此類仿真應用的分析能力和運算效率變得十分重要.本文針對基于多Agent系統(tǒng)的分布式仿真運算特性，提出了一個優(yōu)化Agent分配的動態(tài)調度算法實現(xiàn)各仿真節(jié)點的負載均衡以及全局通信結構的優(yōu)化.該算法綜合考慮了仿真過程中仿真節(jié)點的負載狀態(tài)和MAS通信結構的動態(tài)變化，設計了相應的可變負載閾值監(jiān)測和基于Agent組選擇和遷移的優(yōu)化調度方法.通過仿真實驗對比分析，提出的方法在仿真運行時間和負載均衡性能上均要優(yōu)于作為實驗對比的靜態(tài)Agent隨機均勻分配的方法.文中提出的方法對于相關的基于分布式多Agent的仿真和運算系統(tǒng)也有一定的借鑒性.此外，當前算法設計中對一些相關前提條件進了簡化和限定，如Agent運算依附性、Agent遷移代價以及異質跨網(wǎng)段環(huán)境等，同時，Agent遷移機制設計與優(yōu)化對于提升MAS運算的執(zhí)行性能也有著一定影響，在今后的研究工作中，將會進一步考慮這些相關因素對算法進行改進和完善.

［1］盛昭瀚，張維.管理科學研究中的計算實驗方法［J］.管理科學學報，2011，14（5）：1-10.

Sheng Zhaohan，Zhang Wei.Computational experiments in management science and research［J］.Journal of Management Sciences in China，2011，14（5）：1-10.（in Chinese）

［2］劉曉平，唐益明，鄭利平.復雜系統(tǒng)與復雜系統(tǒng)仿真研究綜述［J］.系統(tǒng)仿真學報，2008，20（23）：6303-6315.

Liu Xiaoping，Tang Yiming，Zheng Liping.Survey of complex system and complex system simulation［J］.Journal of System Simulation，2008，20（23）：6303-6315.（in Chinese）

［3］Lee J H，Kim C O.Multi-agent systems applications in manufacturing systems and supply chain management：A review paper［J］. International Journal of Production Research，2008，46（1）：233-265.

［4］李英，馬壽峰.基于Agent的仿真系統(tǒng)建模［J］.系統(tǒng)工程學報，2006，21（3）：225-231.

Li Ying，Ma Shoufeng.Modeling of agent-based simulation system［J］.Journal of Systems Engineering，2006，21（3）：225-231.（inChinese）

［5］張少蘋，戴鋒，王成志，等.多Agent系統(tǒng)研究綜述［J］.復雜系統(tǒng)與復雜性科學，2011，8（4）：1-8.

Zhang Shaoping，Dai Feng，WangChengzhi，et al.Summary on research ofmulti-agentsystem［J］.ComplexSyatemsand Complexity Science，2011，8（4）：1-8.（in Chinese）

［6］Boukerche A，Das S K.Reducing null messages overhead through load balancing in conservative distributed simulation systems［J］. Journal of Parallel and Distributed Computing，2004，64（3）：330-344.

［7］Jang M W，Agha G.Adaptive agent allocation for massively multi-agent applications［C］//Ishida T，Gasser L，Nakashima H.Massively Multi-Agent Systems I.Berlin，Heidelberg：Springer，2005：25-39.

［8］GrosuD，ChronopoulosAT.Noncooperativeloadbalancingindistributedsystems［J］.JournalofParallelandDistributedComputing，2005，65（9）：1022-1034.

［9］Zhang Z，F(xiàn)an W.Web server load balancing：A queueing analysis［J］.European Journal of Operational Research，2008，186（2）：681-693.

［10］Oguara T，Chen D，Theodoropoulos G K，et al.An adaptive load management mechanism for distributed simulation of multiagent systems［C］//Proceedings of the 9th IEEE International Symposium on Distributed Simulation and Real-Time Applications，Montreal.Canada，2005：179-186.

［11］Ha B H，Bae J，Park Y T，et al.Development of process execution rules for workload balancing on agents［J］.Data&Knowledge Engineering，2006，56（1）：64-84.

［12］Chow K P，Kwok Y K.On load balancing for distributed multi-agent computing［J］.IEEE Transactions on Parallel and Distributed Systems，2002，13（8）：787-801.

［13］De Grande R E，Boukerche A.Dynamic partitioning of distributed virtual simulations for reducing communication load［C］//Haptic Audio visual Environments and Games，2009（HAVE 2009）.IEEE International Workshop on，IEEE，2009：176-181.

［14］Gonzalez-Pardo A，Varona P，Camacho D.Optimal message interchange in a self-organizing multi-agent system［C］//Proceedings of the 4th International Symposium on Intelligent Distributed Computing.Tangier，Morocco，2010，315：131-141.

［15］Ham M J，Agha G.Market-based coordination strategies for large-scale multi-agent systems［J］.System and Information Sciences Notes，2007，2（1）：126-131.

Algorithm for Agent optimal dispatching in MAS distributed simulations of social system

Dai Hua，Lin Jie

（School of Economy&Management，Tongji University，Shanghai 200092，China）

Accordingtothespecificcomputationalcharacteristicsofagent-basedapplicationsincomplexsocial systems，a distributed agent scheduling architecture is designed and algorithms for dynamic agent scheduling optimization are proposed.The algorithm takes into account the variation of both computation and communication during the simulation process，which implements the dynamic load balancing of each simulation node and the decrease of the overall agent communication that crosses nodes by means of optimizing the agent distribution and scheduling.The experimental results indicate that the proposed algorithms can effectively improve the computational performance and shorten the run-time of such simulation applications.

multi-Agent system（MAS）；complex system；distributed simulation；scheduling optimization

TP391.9

A

1000-5781（2015）06-0844-08

10.13383/j.cnki.jse.2015.06.012

戴華（1981-），男，湖南澧縣人，博士生，研究方向：分布式多Agent系統(tǒng)，系統(tǒng)仿真與建模等，Email：dh_myemail@126.com；

2013-11-14；

2014-09-04.

國家自然科學基金資助項目（71071114）；教育部社科支撐資助項目（11YJC630216）；上海市重點學科建設資助項目（B310）.

林杰（1967-），男，四川渠縣人，教授，博士生導師，研究方向：信息管理與信息系統(tǒng)，供應鏈管理，決策支持系統(tǒng)等，Email：linjie@#edu.cn.