多Agent系統協作求解的粒子模型方法

趙旭寶，李靜，董靚瑜

(大連交通大學 軟件學院，遼寧 大連 116021)*

0 引言

在分布式人工智能中，基于Agent結構提供了柔性和魯棒性，適合解決動態、不確定和分布式的問題.系統中各Agent個體都是具有自主性的智能體，存在自己的信念、愿望、目標等認知屬性和承諾、義務、協作、競爭等社會屬性［1-2］.系統中各Agent個體通過對自身知識的表示和對問題域的描述，構成分布的、異構的、面向特定問題的Agent求解子系統，完成指定任務的求解.但在多Agent分布式系統中由于每個Agent個體所具有的知識資源和執行能力是有限的，當單個Agent難以獨立完成指定任務，或多個Agent一起完成會產生更大的效益時，多個A-gent個體之間就傾向于利用協作機制進行信息的交流、知識的共享來完成任務的協作求解.為了保證多Agent系統協作求解的性能，很多學者在關于多Agent系統協作求解模型建立和協作求解方法方面做了大量研究.文獻［3］提出面向共同目標的合作求解策略，重點在于尋求系統的最大效益;文獻［4-5］提出基于彈簧網絡的多Agent系統協作求解方法，通過自組織動力學策略來實現Agent之間的協調;文獻［6-7］提出基于合同網協議的合作求解方法，先協商結盟再規劃求解，并通過協商的方式解決沖突.

目前多Agent分布式系統協作求解方法的研究基本上有兩種類型:一種類型是Agent個體各自尋求自身最大利益的方法;另一種是Agent個體共同尋求整個系統最大效益的方法.但前者協作求解中沒有全局的優化目標，缺乏統一的全局控制策略;后者又難以描述Agent個體自變與自組織現象.同時，這兩種類型雖然都涉及到Agent間的協作和交互，但協作交互也僅僅是一些簡單的社會交互行為，在問題求解過程中不能及時處理環境和Agent本身的動態變化以及社會交互行為的隨機性和并發性的問題.

為此，本文提出了一種多Agent系統協作求解的粒子模型方法.將系統協作求解轉換為多粒子共同尋優過程，克服了Agent本身認知屬性和社會屬性動態變化及隨機性和并發性的問題，使得Agent個體在協作求解中既獲取自身的最大利益，又促進系統的總體效益.最后，引入了協作程度變化參數，給出了Agent協作求解的需求強度計算公式和系統效益目標函數及優化算法，經過算法迭代計算求得了協作求解的資源分配優化解.仿真結果表明該方法具有很好的收斂性和實用性.

1 求解粒子模型

1.1 求解問題描述

不失一般性，本文以多Agent分布式環境下對問題實施任務資源規劃分配的協作求解為背景，討論多Agent系統協作求解方法與優化算法.設待解決的任務Agent集合和知識與執行能力構成的資源Agent集合分別為 Task={AgentT1，AgentT2，…， AgentTn} 和 Res = {AgentR1，AgentR2，…，AgentRm}，且每個子資源AgentRi個體擁有的資源容量為mi.子資源AgentRi個體分配給子任務AgentTk個體的資源量為rik(rik≤mik)，供其完成規劃的任務.同時子任務AgentTk個體付給子資源AgentRi個體單位資源報酬為pik.設第k個子任務AgentTk對各種子資源Agent需求資源總量為Sk和第k個子任務AgentTk所能支付總的資源報酬代價為Pk.子任務AgentTk在執行任務時使用何種子資源Agent取決于子任務AgentTk對子資源AgentRi的需求強度xik(1≤i≤m，1≤k≤n).xik表示第k個任務需要第i個資源.因此，在多Agent分布協作求解中，任務資源規劃目標則為尋找一個優化的任務資源規劃分配方案，在各資源用量最下的前提下，取得系統整體收益最大值.

1.2 求解粒子模型

由上述問題分析可知，單個子任務AgentTk對各子資源AgentRi的需求是關于rik，pik，xik的函數，函數表示為Aik=F(rik，pik，xik).所有任務對資源需求可以表示成如下的分配矩陣T_R=［Aik］m×n(1 ≤ i≤ m，1≤ k≤ n).矩陣如下:

在上述分配矩陣中，每個子任務AgentTk(1≤k≤n)在完成任務時，可能對每個資源Agent Ri(1≤i≤m)個體存在需求.也就是說，每個子資源AgentRi個體可能分配給不同的子任務(rikxik≤ mi(?i=1，2，…，m)).這樣當多個子任務同時需要某資源時，就可能產生資源使用的沖突.為此，本文提出了資源協作求解的粒子模型.將每個子資源AgentRi個體視為不可再分的個體，稱為粒子，每個子資源粒子每次僅能分配給一個子任務粒子.這樣，當多個子任務需要同時使用某子資源時，Agent粒子就會傾向于進行協作求解共同完成多個子任務.或當多個子資源Agent粒子一起完成所規劃任務會更有效時，也會傾向協作求解.多Agent粒子之間是否進行協作，取決于協作求解強度xik的值.

1.3 需求強度的計算

在實際應用中，對于任務對資源需求強度的取值，不但要考慮Agent意愿、目標等自身認知屬性的變化，更要考慮復雜社會交互行為對協作求解中需求強度的影響.對于群體Agent協作求解過程中所涉及的社會交互行為類型大致可分為兩類:

(1)對于子任務 AgentTk，子資源 AgentRi粒子與子資源AgentRj粒子的協作交互行為ρijk;

(2)對于子資源AgentRi，子任務AgentTk粒子與子任務AgentTj粒子之間的協作交互行為ρ'kji.

其中，ρijk的含義為:對于子任務AgentTk，如果資源AgentRi與資源AgentRj具有相同的意愿和目標，且產生交互行為能加速對任務的執行，或產生更多的效益，則將加強任務 AgentTk對資源AgentRi粒子與AgentRj粒子的需求，加強的強度為ρijk.相反則消弱.

同理，ρ'kji的含義為:對于子資源 AgentRi，如果任務AgentTk與任務AgentTj之間產生交互合作行為，能簡化任務執行的復雜度，并能節約資源的消耗，則將加強資源AgentRi對任務AgentTk粒子與AgentTj粒子的分配.加強的強度為ρ'kji.相反則消弱.

假定不同類型的交互行為產生的效果具有疊加性.因此，根據上述社會交互行為的分類，在協作求解交互過程中，任務對資源的需求強度可通過式(2)計算取得.

其中，wij為關聯權值，在［0，1］之間取值.它表示協作求解中各Agent粒子間關聯程度.它隨Agent粒子的動態變化而改變.如新陳代謝、隨機故障以及協作交互的競爭、利用、欺騙等.在Agent粒子生命周期結束時wij=0.為了簡化問題求解的復雜度，本文假定交互行為對需求強度的加強與消弱程度相同，即ρijk和ρ'kji取相同的小數值.

在式(3)中，當計算所得需求強度值超過給定的某閾值μ后，使得xik=1，否則為0.構造后，某次任務資源規劃協作求解狀態可用圖1表示.圖1中圓點表示子資源粒子對子任務粒子的分配.有向邊表示各粒子之間的協作求解過程.如有向邊 ＜x12，x24＞表示子任務粒子T2在使用資源粒子R1時，還需要使用資源粒子R2，但R2已被T4使用.因此資源粒子R1和R2建立協作關系.在圖1中有向邊越多表明系統內部協作求解規模越大.另外，如果從資源分配角度描述群體Agent粒子間的協作求解交互過程，還可以表示成有向圖，如圖2.圖2中每條邊上的權值代表系統消費代價.在協作求解中由于Agent粒子自身的動態變化和社會交互行為隨機性、并發性等因素的影響，使得這種協作求解是以通信開銷和資源耗費為代價.本文將第i個Agent粒子和第j個Agent粒子協作求解產生的資源消費代價定義為cij.在圖2中有向邊的多少也體現了系統協作求解交互程度.用變量e∈［0，1］表示系統協作交互程度.

圖1 Agent協作求解模型

圖2 資源Agent協作求解過程

2 求解數學模型

λ1，λ2為(0，1)的隨機數

3 協作求解的粒子群算法

在多Agent系統分布式協作求解的粒子模型中，每個規劃解xik都是一個0或1值(1≤i≤m，1≤k≤n).顯然任務資源協作求解問題屬于組合優化問題.因此，本文構造了適合求解的改進粒子群優化算法［8］.在每次求解中把子資源數粒子數m定義為算法中每次迭代求解的空間維數.即每一維空間代表一個資源粒子對任務粒子的分配情況，用一個整數來表示.如果某資源粒子在求解中沒有被任何子任務所使用，則表示為0.如Pkm代表算法中第k次求解的第m維空間;Pkm=n－1表示算法中第k次求解中第m個資源粒子分配給第n－1個子任務使用.

在此粒子群優化算法中，采用了懲罰函數法［9］來處理了具有約束的優化問題，即只要是非可行解就直接丟棄.轉化后的目標適應值計算公式可表示為式(8).

采用這種適應值計算方法，對式(4)經過多次優化迭代計算，即可求得其系統消費代價最小優化解.

協作求解的粒子群算法如下:

(1)隨機初始化粒子種群:粒子群位置X、速度V、種群規模N、學習因子C1和C2、慣性因子w和最大迭代次數Max_Len以及系統參數變量pik，rik，cij值.

(2)利用給定的初始位置值，初始化個體最優位置Pi解和全局最優位置Pg解.并根據各個Agent自治性和社會交互性，利用式(2)(3)計算需求強度參數xik.

(3)While(k＜ =Max_Len＆＆ φ ＜0.0001)//φ為優化達到的精度;

For i=1∶N

For j=1∶m

Change(X，V)//修改每個解的位置X和速度V.End For

(4)calculation(i);//通過式(8)，計算第i次迭代適應值.

localbest(i);//將第i次計算解與所經歷過的當前最好位置解Pi進行比較，若較好，則將其作為當前解的最好位置解;

End For

globalbest();//對每次求解，將其Pi與全局所經歷的最好位置解進行比較，求出全局極值Pg.

EndWhile

4 仿真實例

4.1 仿真實例參數設置

在仿真實驗中，考慮到每個子資源Agent和子任務Agent有不同的優先級、自治度、交互性等復雜的行為，在仿真實驗中隨機生成了相關系統參數.仿真程序中各個參數和變量分別設置如下:每次迭代中搜索空間的維數為資源數m;加速因子c1和c2設置為2.慣性權w根據經驗值設為w=0.9 －count*0.5/(Max_Len －1)，count代表當前第count個粒子.種群位置的變化范圍根據所要研究的問題設置為［1，N］，粒子速度的變化范圍設定為［1，N］;最大迭代次數Max_Len取值為500;其他參數設置為如下隨機值:wij=［0，1］;λ1= ［0.01，0.1］;λ2= ［0.1，0.2］;mi= ［50，100］;pik= ［2，10］;rik= ［1，5］;cij= ［5，10］;Sk= ［100，200］;Pk= ［100，200］.

4.2 仿真結果與收斂性分析

算法中的全局最優適應值變化反應了協作求解的尋優過程.種群根據自身經驗和全局經驗，不斷調整單個解的位置，最后通過迭代搜索到全局最優解.由于本文把每個解的搜索空間定義為資源數.所以每個全局最優適應值就代表了任務資源的一次規劃分配方案.在系統協作求解中，由于子任務數和子資源數是不固定的，并且協作求解的程度e也處于動態變化之中.因此，為了全面考察算法的有效性.本文針對不同的子任務、子資源和不同e值組合進行實驗分析.如圖3，4所示.

圖3 給出了在 (m，n)=(12，10)，e=0.3，0.5，0.8條件下全局最優適應值Pg的變化過程.從圖3可以看出，當資源粒子數和任務粒子數相同，協作求解程度e不同時，全局最優適應值差別很大，由17.1變化到41.2，而收斂速度基本相同.這是因為隨著e的增加，系統協作求解的資源消費不斷增加，導致系統總消費不斷增大.但由于資源數和任務數相同，每個粒子的搜索空間維數相同.因此算法的收斂速度基本相同.這也說明了該算法的收斂速度與協作求解程度e無關.當資源數和任務數不同，協作求解程度相同時.全局最優適應值雖變化很大，但收斂速度隨資源粒子數的增加明顯變慢.這是由于資源數的增加導致粒子搜索的空間變大，迭代速度就會變慢時間變長.如圖4所示.在圖4雖然全局最優適應值變化速度不同，但最終都趨于平穩狀態.表明該方法具有良好的收斂性.同時，仿真結果也驗證了該方法適合不同協作條件下各種任務資源規劃分配求解.

圖3 全局最優適應值變化((m，n)=(12，10))

圖4 全局最優適應值變化(e=0.2)

仿真計算過程中，對于不同的資源粒子數、任務粒子數和不同的e值.在run_time=30條件下，求得的全局最優適應平均值和標準方差值如附表所示.

在附表中全局最優適應值的標準均方差的變化范圍為0.22～0.42.說明了該算法具有良好的收斂性和有效性.仿真結果也驗證了該方法適合不同協作條件下各種任務資源規劃分配求解，該方法具有一定的通用性和有效性.

附表 任務資源規劃分配結果表

5 結論

多Agent分布式系統協作求解比較復雜，需要考慮Agent本身的自治與交互行為動態性和隨機性、復雜性等問題.本文針對分布式環境下任務資源協作規劃分配問題，提出了一種多Agent分布式系統協作求解粒子模型方法，通過討論多A-gent系統分布協作求解和粒子協作之間的關系，將協作求解問題轉化為多個粒子共同尋優的過程，并構造了適合求解該方法的粒子群算法.在算法迭代過程中，盡管全局最優適應值收斂的速度不同，但都收斂達到平穩狀態，表明該算法是收斂的.仿真實驗結果表明在該方法中資源數的多少決定了算法的搜索空間，影響了收斂速度的快慢，但收斂速率與協作求解程度無關.仿真實驗結果也驗證了該模型方法即能克服了環境和Agent本身的動態變化，又能處理社會交互行為變化對系統協作求解的影響，能夠很好地解決各種復雜的任務資源規劃問題，具有很好的有效性和通用性.

［1］張新良，石純一.多Agent合作求解［J］.計算機科學，2003，30(8):100-103.

［2］李英.多Agent系統及其在預測與智能交通系統的應用［M］.上海:華東理工大學出版社，2004.

［3］WOOLDRIDGE M，JENNINGS NR.The cooperative problem-solving process［J］.Journal of Logic Computation，1999，9(4):563-592.

［4］SHUAI Dianxun，FENG Xiang.Distributed problem solving in multi-agent system:A spring net approach［J］.IEEE Intelligent System，2005，20(4):66-74.

［5］帥典勛，王亮.一種新的基于復合彈簧網絡的多A-gent系統分布式問題求解方法［J］.計算機學報，2002，25(8):853-859.

［6］陶海軍，王亞東，郭茂祖，等.基于熟人聯盟及擴充合同網協議的多智能體協商模型［J］.計算機研究與發展，2006，43(7):1155-1160.

［7］陳宇，陳新，陳新度，等.基于設備整體效能和多Agent的預測-反應式調度［J］.計算機集成制造系統，2009，15(8):1599-1605.

［8］謝曉鋒，張文俊，楊之廉.微粒群算法綜述［J］.控制與決策，2003，18(2):129-134.

［9］徐剛，于泳波.基于改進的微粒子算法求解0/1背包問題［J］.齊齊哈爾大學學報，2007，23(1):71-74.