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

(安徽理工大學 經濟與管理學院， 安徽 淮南 232001)

0 引 言

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

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

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

1 OCF數(shù)學模型

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

(1)

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

(2)

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

2 三維整數(shù)編碼

2.1 符號約定

為了方便描述與理解，將方案中涉及的相關概念符號整理見表1。

表1 修正方案符號說明

2.2 編碼修正方案

Step1計算此時每個任務的完成情況，式(3)、式(4)：

(3)

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

(4)

(5)

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

(6)

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

(7)

(8)

Step3根據step1中計算結果，做出調整以保證所有任務皆可完成，具體步驟如下：

Step6根據最終更新的結果，做出調整以滿足所有agent的資源貢獻均在其能力范圍內，即避免資源沖突，具體步驟如下：

3 實例分析

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

圖1 三維空間坐標系示意圖

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

編碼修正過程：

Step1首先計算此時每個任務對應每種資源的完成情況：

Step2計算此時每個agent的每種資源消耗情況：

4 結束語

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