多Agent系統(tǒng)協(xié)作求解的粒子模型方法

趙旭寶，李靜，董靚瑜

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

0 引言

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

目前多Agent分布式系統(tǒng)協(xié)作求解方法的研究基本上有兩種類型:一種類型是Agent個(gè)體各自尋求自身最大利益的方法;另一種是Agent個(gè)體共同尋求整個(gè)系統(tǒng)最大效益的方法.但前者協(xié)作求解中沒(méi)有全局的優(yōu)化目標(biāo)，缺乏統(tǒng)一的全局控制策略;后者又難以描述Agent個(gè)體自變與自組織現(xiàn)象.同時(shí)，這兩種類型雖然都涉及到Agent間的協(xié)作和交互，但協(xié)作交互也僅僅是一些簡(jiǎn)單的社會(huì)交互行為，在問(wèn)題求解過(guò)程中不能及時(shí)處理環(huán)境和Agent本身的動(dòng)態(tài)變化以及社會(huì)交互行為的隨機(jī)性和并發(fā)性的問(wèn)題.

為此，本文提出了一種多Agent系統(tǒng)協(xié)作求解的粒子模型方法.將系統(tǒng)協(xié)作求解轉(zhuǎn)換為多粒子共同尋優(yōu)過(guò)程，克服了Agent本身認(rèn)知屬性和社會(huì)屬性動(dòng)態(tài)變化及隨機(jī)性和并發(fā)性的問(wèn)題，使得Agent個(gè)體在協(xié)作求解中既獲取自身的最大利益，又促進(jìn)系統(tǒng)的總體效益.最后，引入了協(xié)作程度變化參數(shù)，給出了Agent協(xié)作求解的需求強(qiáng)度計(jì)算公式和系統(tǒng)效益目標(biāo)函數(shù)及優(yōu)化算法，經(jīng)過(guò)算法迭代計(jì)算求得了協(xié)作求解的資源分配優(yōu)化解.仿真結(jié)果表明該方法具有很好的收斂性和實(shí)用性.

1 求解粒子模型

1.1 求解問(wèn)題描述

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

1.2 求解粒子模型

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

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

1.3 需求強(qiáng)度的計(jì)算

在實(shí)際應(yīng)用中，對(duì)于任務(wù)對(duì)資源需求強(qiáng)度的取值，不但要考慮Agent意愿、目標(biāo)等自身認(rèn)知屬性的變化，更要考慮復(fù)雜社會(huì)交互行為對(duì)協(xié)作求解中需求強(qiáng)度的影響.對(duì)于群體Agent協(xié)作求解過(guò)程中所涉及的社會(huì)交互行為類型大致可分為兩類:

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

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

其中，ρijk的含義為:對(duì)于子任務(wù)AgentTk，如果資源AgentRi與資源AgentRj具有相同的意愿和目標(biāo)，且產(chǎn)生交互行為能加速對(duì)任務(wù)的執(zhí)行，或產(chǎn)生更多的效益，則將加強(qiáng)任務(wù) AgentTk對(duì)資源AgentRi粒子與AgentRj粒子的需求，加強(qiáng)的強(qiáng)度為ρijk.相反則消弱.

同理，ρ'kji的含義為:對(duì)于子資源 AgentRi，如果任務(wù)AgentTk與任務(wù)AgentTj之間產(chǎn)生交互合作行為，能簡(jiǎn)化任務(wù)執(zhí)行的復(fù)雜度，并能節(jié)約資源的消耗，則將加強(qiáng)資源AgentRi對(duì)任務(wù)AgentTk粒子與AgentTj粒子的分配.加強(qiáng)的強(qiáng)度為ρ'kji.相反則消弱.

假定不同類型的交互行為產(chǎn)生的效果具有疊加性.因此，根據(jù)上述社會(huì)交互行為的分類，在協(xié)作求解交互過(guò)程中，任務(wù)對(duì)資源的需求強(qiáng)度可通過(guò)式(2)計(jì)算取得.

其中，wij為關(guān)聯(lián)權(quán)值，在［0，1］之間取值.它表示協(xié)作求解中各Agent粒子間關(guān)聯(lián)程度.它隨Agent粒子的動(dòng)態(tài)變化而改變.如新陳代謝、隨機(jī)故障以及協(xié)作交互的競(jìng)爭(zhēng)、利用、欺騙等.在Agent粒子生命周期結(jié)束時(shí)wij=0.為了簡(jiǎn)化問(wèn)題求解的復(fù)雜度，本文假定交互行為對(duì)需求強(qiáng)度的加強(qiáng)與消弱程度相同，即ρijk和ρ'kji取相同的小數(shù)值.

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

圖1 Agent協(xié)作求解模型

圖2 資源Agent協(xié)作求解過(guò)程

2 求解數(shù)學(xué)模型

λ1，λ2為(0，1)的隨機(jī)數(shù)

3 協(xié)作求解的粒子群算法

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

在此粒子群優(yōu)化算法中，采用了懲罰函數(shù)法［9］來(lái)處理了具有約束的優(yōu)化問(wèn)題，即只要是非可行解就直接丟棄.轉(zhuǎn)化后的目標(biāo)適應(yīng)值計(jì)算公式可表示為式(8).

采用這種適應(yīng)值計(jì)算方法，對(duì)式(4)經(jīng)過(guò)多次優(yōu)化迭代計(jì)算，即可求得其系統(tǒng)消費(fèi)代價(jià)最小優(yōu)化解.

協(xié)作求解的粒子群算法如下:

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

(2)利用給定的初始位置值，初始化個(gè)體最優(yōu)位置Pi解和全局最優(yōu)位置Pg解.并根據(jù)各個(gè)Agent自治性和社會(huì)交互性，利用式(2)(3)計(jì)算需求強(qiáng)度參數(shù)xik.

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

For i=1∶N

For j=1∶m

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

(4)calculation(i);//通過(guò)式(8)，計(jì)算第i次迭代適應(yīng)值.

localbest(i);//將第i次計(jì)算解與所經(jīng)歷過(guò)的當(dāng)前最好位置解Pi進(jìn)行比較，若較好，則將其作為當(dāng)前解的最好位置解;

End For

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

EndWhile

4 仿真實(shí)例

4.1 仿真實(shí)例參數(shù)設(shè)置

在仿真實(shí)驗(yàn)中，考慮到每個(gè)子資源Agent和子任務(wù)Agent有不同的優(yōu)先級(jí)、自治度、交互性等復(fù)雜的行為，在仿真實(shí)驗(yàn)中隨機(jī)生成了相關(guān)系統(tǒng)參數(shù).仿真程序中各個(gè)參數(shù)和變量分別設(shè)置如下:每次迭代中搜索空間的維數(shù)為資源數(shù)m;加速因子c1和c2設(shè)置為2.慣性權(quán)w根據(jù)經(jīng)驗(yàn)值設(shè)為w=0.9 －count*0.5/(Max_Len －1)，count代表當(dāng)前第count個(gè)粒子.種群位置的變化范圍根據(jù)所要研究的問(wèn)題設(shè)置為［1，N］，粒子速度的變化范圍設(shè)定為［1，N］;最大迭代次數(shù)Max_Len取值為500;其他參數(shù)設(shè)置為如下隨機(jī)值: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 仿真結(jié)果與收斂性分析

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

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

圖3 全局最優(yōu)適應(yīng)值變化((m，n)=(12，10))

圖4 全局最優(yōu)適應(yīng)值變化(e=0.2)

仿真計(jì)算過(guò)程中，對(duì)于不同的資源粒子數(shù)、任務(wù)粒子數(shù)和不同的e值.在run_time=30條件下，求得的全局最優(yōu)適應(yīng)平均值和標(biāo)準(zhǔn)方差值如附表所示.

在附表中全局最優(yōu)適應(yīng)值的標(biāo)準(zhǔn)均方差的變化范圍為0.22～0.42.說(shuō)明了該算法具有良好的收斂性和有效性.仿真結(jié)果也驗(yàn)證了該方法適合不同協(xié)作條件下各種任務(wù)資源規(guī)劃分配求解，該方法具有一定的通用性和有效性.

附表 任務(wù)資源規(guī)劃分配結(jié)果表

5 結(jié)論

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

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

［2］李英.多Agent系統(tǒng)及其在預(yù)測(cè)與智能交通系統(tǒng)的應(yīng)用［M］.上海:華東理工大學(xué)出版社，2004.

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

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

［5］帥典勛，王亮.一種新的基于復(fù)合彈簧網(wǎng)絡(luò)的多A-gent系統(tǒng)分布式問(wèn)題求解方法［J］.計(jì)算機(jī)學(xué)報(bào)，2002，25(8):853-859.

［6］陶海軍，王亞?wèn)|，郭茂祖，等.基于熟人聯(lián)盟及擴(kuò)充合同網(wǎng)協(xié)議的多智能體協(xié)商模型［J］.計(jì)算機(jī)研究與發(fā)展，2006，43(7):1155-1160.

［7］陳宇，陳新，陳新度，等.基于設(shè)備整體效能和多Agent的預(yù)測(cè)-反應(yīng)式調(diào)度［J］.計(jì)算機(jī)集成制造系統(tǒng)，2009，15(8):1599-1605.

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

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