一種基于三維編碼修正的重疊聯(lián)盟形成方案

韓 露， 聶艷艷， 程文麗， 臧思雨

(安徽理工大學(xué) 經(jīng)濟(jì)與管理學(xué)院， 安徽 淮南 232001)

0 引 言

團(tuán)隊(duì)協(xié)作已漸成為在面對(duì)并行多任務(wù)時(shí)的首要選擇。個(gè)人與個(gè)人之間、小組與小組之間、企業(yè)與企業(yè)之間相互合作已成為新時(shí)代的常態(tài)。由于每個(gè)個(gè)體擁有的能力不同，所獲的資源不同，在面對(duì)并行的、綜合的任務(wù)時(shí)，合理組成有效聯(lián)盟進(jìn)行任務(wù)求解將在一定程度上實(shí)現(xiàn)效率最大化、資源浪費(fèi)最小化以及任務(wù)總收益最大化的完美結(jié)合[1]。

隨著計(jì)算機(jī)科學(xué)技術(shù)的迅速發(fā)展，agent理論、多agent系統(tǒng)(Multi-agent systems，MAS)等概念應(yīng)運(yùn)而生，基于MAS的聯(lián)盟研究也受到廣泛關(guān)注[2]。多agent系統(tǒng)中的重疊聯(lián)盟形成(overlapping coalition formation，OCF)，在求解復(fù)雜并行分布式任務(wù)時(shí)，各agent之間取長補(bǔ)短、親密協(xié)作，求解任務(wù)靈活性強(qiáng)，解決了單個(gè)agent因資源不足而無法滿足任務(wù)需求或勉強(qiáng)完成任務(wù)但效率低下的問題。為此，蔣建國等提出了一種基于能力向量發(fā)揮率和拍賣的聯(lián)盟形成策略，在面向任務(wù)的領(lǐng)域中可以達(dá)到全局優(yōu)化解，較好地滿足了穩(wěn)定性、時(shí)效性、分布等要求[3]；張國富等提出將有效聯(lián)盟的剩余能力轉(zhuǎn)移給一個(gè)動(dòng)態(tài)的虛擬聯(lián)盟，由虛擬聯(lián)盟幫助解決其他無效聯(lián)盟，研究如何把一個(gè)無效的二維二進(jìn)制編碼修正為一個(gè)合法的編碼[4]。

基于上述背景，本文將二維二進(jìn)制編碼擴(kuò)充至三維整數(shù)編碼，構(gòu)建“任務(wù)”、“資源”、“agent”于一體的三維空間坐標(biāo)系，更直觀、有效地完成智能資源體的快速分配，并針對(duì)聯(lián)盟形成過程中可能出現(xiàn)的資源沖突與聯(lián)盟無效問題，提出相應(yīng)的三維編碼修正方案。

1 OCF數(shù)學(xué)模型

設(shè)MAS中的agent個(gè)數(shù)為n，A={a1,a2,…,an}，需要求解的任務(wù)數(shù)為m，T={t1,t2,…,tm}。

(1)

(4)用V(Ci)表示聯(lián)盟Ci的值，式(2)[6]：

(2)

其中，φ(ti)為完成任務(wù)ti獲得的報(bào)酬，一般為常數(shù)；θ(Ci)為聯(lián)盟Ci中所有agent成員的總資源成本，即為聯(lián)盟中各成員實(shí)際貢獻(xiàn)的資源和；Π(Ci)為任務(wù)ti的求解聯(lián)盟Ci中各agent成員兩兩之間的通信成本之和，πi1i2為ai1與ai2之間的通信成本。重疊聯(lián)盟形成問題即為在滿足上述約束條件的基礎(chǔ)上使V(Ci)值盡可能大。

2 三維整數(shù)編碼

2.1 符號(hào)約定

為了方便描述與理解，將方案中涉及的相關(guān)概念符號(hào)整理見表1。

表1 修正方案符號(hào)說明

2.2 編碼修正方案

Step1計(jì)算此時(shí)每個(gè)任務(wù)的完成情況，式(3)、式(4)：

(3)

(k∈1,2,…,r;i∈1,2,…,m.)

(4)

(5)

Step2計(jì)算此時(shí)每個(gè)agent的資源消耗情況，式(6)、式(7)為：

(6)

(k∈1,2,…,r;j∈1,2,…,n).

(7)

(8)

Step3根據(jù)step1中計(jì)算結(jié)果，做出調(diào)整以保證所有任務(wù)皆可完成，具體步驟如下：

Step6根據(jù)最終更新的結(jié)果，做出調(diào)整以滿足所有agent的資源貢獻(xiàn)均在其能力范圍內(nèi)，即避免資源沖突，具體步驟如下：

3 實(shí)例分析

假設(shè)有2個(gè)agent，其所擁有的資源向量分別為B1=[2,3],B2=[3,2]，需求解的任務(wù)數(shù)為2，其對(duì)應(yīng)的資源需求向量分別為D1=[4,3],D2=[1,1]，如圖1所示。

圖1 三維空間坐標(biāo)系示意圖

根據(jù)能力約束條件產(chǎn)生的初始聯(lián)盟如下：

編碼修正過程：

Step1首先計(jì)算此時(shí)每個(gè)任務(wù)對(duì)應(yīng)每種資源的完成情況：

Step2計(jì)算此時(shí)每個(gè)agent的每種資源消耗情況：

4 結(jié)束語

為了更直觀、有效的挖掘重疊聯(lián)盟，本文采用了三維整數(shù)編碼的表示方式，并提出一種新型的三維編碼修正方案。傳統(tǒng)的二維二進(jìn)制編碼只能表示各Agent成員是否參與聯(lián)盟，而不能顯示各成員在聯(lián)盟中貢獻(xiàn)的資源量，二維二進(jìn)制編碼和整數(shù)混合編碼過于復(fù)雜和冗余。因此，本文構(gòu)建了“任務(wù)”、“資源”、“agent”于一體的三維空間坐標(biāo)系，并針對(duì)初始化賦予任意值可能產(chǎn)生的聯(lián)盟無效與資源沖突問題，設(shè)計(jì)了相應(yīng)的編碼修正策略，以確保任何一個(gè)無效編碼都能夠被修正為一個(gè)合法編碼。