基于混合蟻群算法的ＭＡＳ任務分配
2009-01-01 00:00:00嚴建峰李偉華劉明
計算機應用研究 2009年1期
（西北工業大學 計算機學院， 西安 710072）
摘 要：在MAS（多agent系統）中，由于任務的復雜性和agent求解問題能力的不同，任務和agent不再是傳統的一對一的關系。為解決MAS的任務分配問題，提出了任務與agent之間多對多的任務分配模式。首先建立了任務分配的數學模型，并導出分配優化的目標函數；其次利用混合蟻群算法快速收斂和分布式求解的特點實現任務分配的組合優化。對實驗仿真的結果分析表明，多對多的任務分配模式能夠明顯提升多agent系統的性能。
關鍵詞：多代理系統； 多對多模式； 任務分配； 混合蟻群算法
中圖分類號：TP18 文獻標志碼：A
文章編號：10013695(2009)01006803
Task allocation for MAS based on hybrid ant colony algorithm
YAN Jianfeng， LI Weihua， LIU Ming
（School of Computer Science， Northwestern Polytechnical University， Xi’an 710072， China）
Abstract:In multiagent systems (MAS)， the relation of tasks and agents are no longer the traditional onetoone relation because of complexity of tasks and performance difference between respective agents. To solve task allocation problem in MAS， put forward a manytomany task allocation mechanism. First， established the mathematical model of task allocation and further deduced the target function. Then applied a hybrid ant colony algorithm to accomplish combinatorial optimization of task allocation. Finally， the simulation experiments show that the manytomany task allocation mechanism can significantly enhance the performance of MAS.
Key words：MAS; manytomany mode; task allocation; hybrid ant colony algorithm
0 引言
任務分配問題是影響多agent系統(MAS)性能的關鍵問題，已經有大量的工作致力于發展有效的任務分配策略。例如文獻[1，2]以多機器人為對象進行了實驗與分析，對多機器人任務分配進行了組合優化；文獻[3]提出一種多階段的分層次任務分配方法；文獻[4，5]利用計算智能方法強大的尋優能力進行任務分配設計。然而這些工作主要研究任務與agent之間是一對一的關系時的任務分配，即同一任務只需分配給一個agent且agent在完成現在任務之前不會接受新的任務。這種一對一的任務分配模式易于實現，但在很多復雜問題中對提高系統性能已經力不從心。
在MAS中，任務分配存在以下特殊性：a）采用不同方法設計的agent對同一任務的處理結果允許存在差異，因此在MAS中往往將同一任務分配給多個agent并行求解，然后通過結果融合的方式得到比單一agent處理更高的求解精度[6]；b）為充分發揮MAS的并行處理能力，允許agent同時接受多個任務，形成任務列表。因此，有必要研究任務與agent之間多對多關系時的任務分配策略。
本文根據MAS中任務分配的特殊性建立了多對多的任務分配模型，并導出分配優化的目標函數，將MAS任務分配問題轉換成一個典型的組合優化問題。由于多agent系統中的任務分配問題是一個典型的NPhard問題，而混合蟻群算法兼具遺傳算法快速收斂和蟻群算法分布式求解的特點，因此利用混合蟻群算法實現該模型。最后對實驗結果進行了分析和對比。
1 多對多任務分配問題
MAS中多對多任務分配問題可描述為：有m個任務需要分配給n個agent完成，一個任務最多可以分配給u個agent并行求解，通過將不同agent所有結果進行沖突消解得到最終解；每個agent最多能接收v個任務。根據多對多任務分配的定義，首先給出任務分配的數學模型，設計了任務分配代價函數來求解任務分配代價；其次，根據任務分配的設計目標，引入性能影響因子與任務分配代價函數相結合，給出了任務分配進行組合優化時所遵循的目標函數。
1.1 任務分配模型
為衡量并對比不同agent執行任務的代價差異，首先計算系統中每個agent對每個任務類型的求解代價，并用矩陣的方式來表示求解代價。矩陣的行表示任務類型，矩陣的列表示agent，矩陣的元素對應該任務分配給對應agent的代價，稱為全局代價矩陣。基于全局代價矩陣，可以構建任務分配中的以下三個數學模型：
a)從全局代價矩陣中提取與具體問題相關的元素來構建問題的代價矩陣，稱為局部代價矩陣；
b)根據局部代價矩陣構建無約束分配矩陣和約束分配矩陣；
c)根據約束分配矩陣和局部代價矩陣構建該問題對應的分配代價矩陣。
1)全局代價矩陣和局部代價矩陣
設系統中共有p個任務類型、q個agent，任務i分配給agent j完成的代價為cij，可構建代價矩陣Cp×q=(cij)。其中cij包括時間、系統軟硬件開銷等資源?？紤]到在各類代價中時間代價是一個重要的因素，在各類MAS中的重要性可能有所不同，因此將cij表述為
cij=ω1×tij+ω2×∑sk=1λijk
(1)
其中：tij為時間資源開銷；λijk為其他資源開銷；s為其他資源開銷的數量；ω1、ω2為對應權重，且ω1+ω2=1，可以根據不同的系統應用需求來調整ω1、ω2的值。約定若該agent不能完成某類任務，則cij=N。
設某問題被分解成m個任務，共有n個agent是潛在任務中標者。從全局代價矩陣中提取與該問題相關的元素即可構成局部代價矩陣。具體方式為從全局代價矩陣的p行（任務）中抽取m行，q列（agent）中抽取n列，則m行與n列交叉的元素組成的矩陣Cm×n為局部代價矩陣。
2)無約束分配矩陣和約束分配矩陣
對局部代價矩陣中的元素作一定變換即可構成無約束分配矩陣Rm×n。變換方式為
rij=N cij=N1 cij≠N
(2)
分配問題的約束條件u，v可以表述為
∑ni=1rij≤v(3)
∑mj=1rij≤u(4)
在滿足約束條件的前提下，對無約束分配矩陣Rm×n中的每一個元素作進一步變換，可構建約束分配矩陣Rm×n=(rij)。具體的變換如式（5）所示：
rij=1 若rij=1且任務分配給該agent
0 若rij=1且任務不分配給該agent
N 若rij=N(5)
3)分配代價矩陣
根據具體問題的約束分配矩陣和局部代價矩陣，直接建立該問題對應的分配代價矩陣Dm×n=(dij)。其中元素dij=rij×cij。若rij或cij的值為N，則dij=N，即如果agent不能完成任務，那么不需要計算對應分配代價。
4）任務分配代價
建立問題的分配代價矩陣后，給出任務分配代價如式（6）所示：
C(x)=∑mj=1∑ni=1dij(6)
1.2 目標函數
為實現任務分配機制，必須建立任務分配的目標函數指導agent與任務進行組合優化，求解理想的任務分配方案。在多數情況下，增加中標agent的數量能夠提高MAS的性能[1]，但也會增加系統的資源開銷，因此引入性能影響因子來評估MAS中中標agent的數量對性能的影響。
根據任務分配矩陣，定義性能影響因子如式（7）所示：
λ=∑mj=1∑ni=1rij-3(7)
約定當rij=N時，直接跳過對應元素的計算。
根據任務分配代價函數和性能影響因子，建立目標函數如式（8）所示：
F（x)=λ×C(x)=∑mj=1∑ni=1dij×∑mj=1∑ni=1rij-3
(8)
建立任務分配的數學模型和目標函數以后，應用各類方法對任務分配矩陣進行組合優化并達到性能與代價之間的平衡的判斷依據即為F(x)最小。
2 混合蟻群算法
蟻群算法（ant colony algorithm，ACA）是受螞蟻搜索食物過程啟示而提出的啟發式優化算法，屬于模擬進化算法。旅行商問題（traveling salesman problem，TSP）和蟻群系統有很多相似性，是蟻群算法最早的成功應用。蟻群算法具有分布式計算的特點且易于與其他模擬進化算法結合，適用于求解可用圖表示的NPhard問題。蟻群算法及各類改進算法已經被廣泛應用于求解車輛路由問題、模糊規則提取、供應鏈管理和圖像識別等領域，并且取得較好結果。
混合蟻群算法[7]是一種改進的蟻群算法，其機制分成以下兩步:
a)使用遺傳算法，利用其快速性、隨機性、全局收斂性的特點產生次優解；
b)利用蟻群算法分布式計算、易于與其他模擬進化算法結合的特點，對次優解進行優化。
在處理大規模問題時，算法顯示出很好的時間性能。仿真實驗表明在求解大規模問題時，相比傳統蟻群算法，蟻群系統收斂的時間縮短了60%左右，并且解的質量有顯著改善。
本文討論的多agent系統中的任務分配問題是一個典型的NPhard問題。應用混合蟻群算法，綜合利用遺傳算法快速收斂和蟻群算法分布式求解的特點，能夠較好地解決這類任務分配問題。
3 基于混合蟻群算法的任務分配
根據混合蟻群算法的求解機制，基于該方法的任務分配也相應地分成兩個階段，分別利用遺傳算法和蟻群算法進行求解。在第一階段，需要生成初始種群，并利用選擇、交叉、變異等算子生成任務分配的次優解；在第二階段，根據遺傳算法生成的次優解，給出蟻群算法的初始信息素分布，利用蟻群算法的全局收斂能力對次優解進行優化。
3.1 基于遺傳算法的初始任務分配
與理想情況下的任務分配不同，在多對多分配模式下應用遺傳算法完成任務分配有一定的特殊性。首先，特定的agent能夠求解的任務類型是有限的，有一些任務類型是該agent無法求解的，體現在分配矩陣中值為N的元素。因此，在利用遺傳算法對任務分配矩陣中的元素進行組合優化時，跳過所有值為N的元素，避免不必要的各類遺傳操作。其次，任務分配必須保證由式（3）（4）描述的限定條件，因此在執行三大遺傳操作時須保證中標agent數和中標任務數不超出上限閾值u、v。最后，在多對多分配模式下的任務分配易于應用遺傳算法進行編碼和解碼。根據任務分配模型，要獲得高質量的任務分配方案只需通過對任務分配矩陣中的元素進行組合優化。由式（5），任務分配矩陣中的元素取值為0，1，N三類，而值為N的元素無須處理，導致需要遺傳算法處理的元素取值只有0、1兩類。因此直接使用最常用的二進制編碼作為任務分配問題編碼方式。
由于本文采用的貪心遺傳算法與傳統遺傳算法思想非常類似，不再贅述該算法的三大遺傳操作。給出基于遺傳算法的初始任務分配過程如下：
a）設定初始化群體規模、進化代數、雜交概率、變異概率、選擇概率等控制參數；
b）生成初始種群；
c）評價各個解的適應函數值F(x)；
d）在中標agent數不超出閾值u，中標任務數不超出閾值v的前提下，執行復制、雜交、變異操作；
e）當迭代次數到達設定值時，得到初始任務分配矩陣，否則返回c）。
3.2 基于蟻群算法的任務分配優化
與遺傳算法相類似，使用蟻群算法對初始任務分配矩陣進行優化時，直接跳過所有值為N的元素。在算法設計上，參考應用蟻群算法求解TSP的機制。設有m個城市、n個螞蟻分別對應任務和agent的數量。在代價矩陣、分配矩陣和分配代價矩陣之外，引入信息素矩陣Tm×n和轉移概率矩陣Pm×n，k。其中，元素tij∈Tm×n表示任務i分配給agent j對應的信息素值，初值為常數t；元素pij，k∈Pm×n，k表示第k只螞蟻的循環迭代過程中任務i分配給agent j的概率。計算方法如式（9）所示：
pm×n，k=[(tij)α×（cij)-β]/[∑nj=1(tij)α×(cij)-β](9)
由于使用蟻群算法進行任務分配優化與求解TSP有較大的相似性，不詳述算法的實現細節，只給出算法主要步驟如下：
a）設定信息素揮發系數、信息素強度、啟發式因子、期望啟發式因子、循環次數等控制參數；
b）根據遺傳算法求解初始任務分配矩陣，設定螞蟻的位置；
c）根據式（8）計算第k只螞蟻完成m項任務的概率pkj，k，選出其中概率最大的分配，將該任務分配給對應agent，重復該步驟直到k=n；
d）根據信息素揮發系數，更新信息素矩陣Tm×n；
e）重復步驟d）、e），直到循環次數達到設定的最大值。
4 實驗分析
為驗證算法提出的任務分配機制的可行性和有效性，本文以故障診斷MAS作為應用對象進行實驗，并與一對一的配對模式進行對比分析。設MAS中需要分配任務個數m=9，任務處理agent個數n=12?；旌舷伻核惴ǖ闹饕獏翟O置為：遺傳算法方面，雜交概率為0.85，變異概率為0.05，交叉概率為0.7，迭代次數300；蟻群算法的主要參數設置為：信息素強度Q=100，啟發式因子α=0.1，信息素揮發系數ρ=0.1，期望啟發式因子β=2，循環次數300次。在故障診斷MAS中，用戶關注的代價是任務執行時間，為簡化問題分析，設任務分配的代價僅為時間代價而不考慮其他代價，置權重ω1=1，ω2=0。分別用一對一分配模式的方法和多對多分配模式的方法進行任務分配。引入二維向量D={u，v}，稱D為閾值向量。對于一對一分配模式，D1={1，1 }；在多對多分配模式下，D取四組值：D2={2，2}，D3={3，3}，D4={4，4}和D5={5，5}。應用文中算法，得到性能、時間和D的關系如圖1所示，圖中橫坐標表示D的下標。可以看出在[D1，D3]，增大閾值u和v而獲得的性能提升超出付出的時間代價；而在[D4，D5]，增大閾值u和v能夠獲得的性能提升已經不明顯，而相應的時間代價增長迅速。
5 結束語
本文提出了MAS中多對多的任務分配模式，建立了相應的數學模型。該模型綜合考慮多對多的任務分配模式下性能與代價之間的平衡，設計了相應的目標函數，并應用混合蟻群算法進行任務分配的組合優化。仿真實驗表明，多對多的任務分配模式不僅是有效的，而且當任務分配的上限閾值μ、v限定于2、3時，表現出比一對一分配模式更高的性能。今后的工作將進一步優化組合上限閾值μ、v，獲得更佳的性能與代價的平衡點。
參考文獻：
［1］GERKEY B P， MATARIC M J. A formal analysis and taxonomy of task allocation in multirobot systems[J].International Journal of Robotics Research，2004，23(9):939954.
[2]GERKEY B P， MATARIC M J. Multirobot task allocation:analyzing the complexity and optimality of key architectures[C]//Proc ofIEEE International Conference on Robotics and Automation. 2003:38623868.
[3]REHAK M， VOLF P， PECHOUCEK M. Multilevel approach to agentbased task allocation in transportation[C]//Lecture Notes in Computer Science，vol 4149. Berlin:Springer， 2006:273287.
[4]ZHU Anmin， YANG Simen. A neural network approach to dynamic task assignment of multirobots[J]. IEEE Trans on Neural Networks ，2006，17(5):12781287.
[5]SHIMA T， RASMUSSEN S J， SPARKS A G，et al. Multiple task assignments for cooperating uninhabited aerial vehicles using genetic algorithms[J]. Computers Operations Research，2006，33(1):32523269.
[6]WOOLDRIDGE M. An introduction to multi agent systems[M].石純一，等譯. 北京：電子工業出版社，2003.
[7]嚴建峰，李偉華，杜北. 基于規模壓縮的混合蟻群算法[J]. 控制與決策， 2007，22(9):10611064.
