基于勢結構的給定限界的聯盟結構生成算法

摘 要:聯盟結構生成是多agent系統中的一個關鍵問題。Sandholm等人證明了要建立最壞情況下的限界k， 搜索聯盟結構圖的最底兩層是必要且是充分的，如何進一步搜索是一個長期以來未能解決的問題。當實際應用提出最壞情況的具體限界要求時，如何通過部分的搜索達到這個限界?胡山立和石純一給出了一種以層為單位的最優搜索算法， Dang等人和蘇射雄等人給出了以勢結構為單位的聯盟結構生成算法。新算法MCCS提出在搜索最底兩層及頂層后，搜索勢結構集合MCCS(n， k)對應的聯盟結構，以更少的勢結構達到給定限界k。實驗表明，在已有的算法中其所搜索的勢結構最少，具有一定的理論和實踐意義。

關鍵詞:聯盟結構; 勢結構; 給定限界; 算法MCCS

中圖分類號:TP301.6文獻標志碼:A

文章編號:1001-3695(2009)09-3232-03

doi:10.3969/j.issn.1001-3695.2009.09.008

Coalition structure generation algorithm based oncardinality structure with given required bound

LI Shao-fang， HU Shan-li2

(1.Dept. of Electronic Information Engineering，Putian College，Putian Fujian 351100， China; 2.Dept. of Computer Science Technology， Fuzhou University， Fuzhou 350108， China)

Abstract:Coalition structure generation is a key topic in multi-agent system. Sandholm et al. proved that it was necessary and sufficient to search the lowest two levels of the coalition structure graph in order to establish a worst-case bound k. How to do a further search after? That is a problem which hasnt been resoled for a long time. When practical applications could present required real bound in the worst case， how to attain this bound via partial search? HU Shan-li and SHI Chun-yi gave an optimal searching algorithm whose searching unit was level. Dang et al. and SU She-xiong et al. gave their coalition structure generation algorithms whose searching unit was cardinality structure. New algorithm MCCS proposed that searching all coalition structures corresponding to the set of cardinality structure MCCS(n， k) could attain the given required bound k with more less cardinality structures after searching the lowest two levels and the top level in the coalition structure graph. Finally， comparing to the existing algorithms， it obviously searches less cardinality structures and has some theoretical and practical meaning.

Key words:coalition structure; cardinality structure; given required bound; algorithm MCCS

0 引言

聯盟形成已經在合作的對策論中被長久研究[1]。聯盟形成是多agent系統中的一個重要主題。其中一個隊列的agent通常需要最大化它們的個體或它們的集體效益。舉例來說，agent通常必須形成有效的群組去購買大量貨物[2]。設A中有n個agent，A={a1，a2 ，a3 ，…，an }。 A中的一個非空子集C稱為一個agent聯盟，而A的一個完全的劃分稱為一個聯盟結構CS。例如，A={a1 ，a2 ， a3 }，存在七個可能的聯盟:{a1}，{a2}，{a3}，{a1，a2}，{a1，a3}，{a2，a3}，{a1，a2，a3}和五個可能的聯盟結構:{{a1}，{a2}，{a3}}，{{a1，a2}， {a3}}，{{a1，a3}，{a2}}，{{a2，a3}，{a1}}，{{a1，a2，a3}}。聯盟形成過程包括三個階段[3，4]:a)聯盟值計算，注意到這需要處理2n個可能的聯盟;b)聯盟結構生成，搜尋空間是 O(nn) 和ω (nn/2);c)效益分配，通常是 NP-完全。

通常人們著重于特征函數對策(CFGs)下的聯盟結構生成問題[4~6]:a)每個聯盟 C 的值由一個特征函數V(C)給定，V(C)值與非該聯盟成員的活動無關，而聯盟結構CS的值等于該聯盟結構中所有聯盟值的和，即V(CS)=∑C∈CSV(C);b)每個聯盟的值是有限的，不妨假設是非負的，即對任意的聯盟C，有V(C)≥ 0;c)在非超加對策中研究聯盟形成，即聯盟不具有超加性，或超加性事先不知道。超加性是指對任意兩個不相交的聯盟C1，C2A，有V(C1∪C2)≥V(C1)+V(C2)，否則最優聯盟結構就是由所有agent組成的全聯盟了。在尋求最優聯盟結構時，算法的輸入可以只包含一部分聯盟的聯盟值，而其余的約定為0。

Sandholm等人[4]已經證明，要建立最壞情況下的限界k，搜索聯盟結構圖的最底二層是必要且充分的，此時限界k=n。當實際問題提出比這更優的具體限界要求時，應如何作進一步的搜索，以最小的搜索量來滿足這個要求?文獻[5~7]對此作了進一步的研究，在一定程度上減少了搜索量。

1 基本定義

定義1 設n個agent的集合A={a1，a2，a3，…，an }，聯盟C是A中的一個非空子集，聯盟C中agent的個數稱為聯盟C的勢，記為|C|。

定義2 設A={a1，a2 ，a3，…，an }，A中所有勢為i∈ {1，2，…，n}的聯盟，合稱為聯盟清單CLi。記聯盟清單集合CL=∪ni=1CLi。

4個agent的聯盟清單如表1所示。

表1 4個agent的聯盟清單

CL1CL2CL3CL4

{4}{3，4}{2，3，4}{1，2，3，4}

{3}{2，4}{1，3，4}

{2}{2，3}{1，2，4}

{1}{1，4}{1，2，3}

{1，3}

{1，2}

定義3 設聯盟結構CS有p個聯盟C1，C2，NA1AD，Cp，且C1≥C2≥NA1AD≥Cp≥1。令n1=C1，n2=C2，NA1AD，np=Cp，n=n1+n2+NA1AD+np，則把{n1，n2，NA1AD，np}稱為勢結構(CCS)。

在算法描述中，以勢結構{n1，n2，NA1AD，np}為搜索單位，指的是搜索{n1，n2，NA1AD，np}所對應的所有聯盟結構的集合。顯然整數n的每一種劃分對應一種勢結構，如整數4的一種劃分表示為4=2+1+1，正好對應勢結構{2，1，1}。整數n的劃分數就是勢結構數，其值可通過遞歸方法計算[8]。一個勢結構可以對應一個或多個聯盟結構，如勢結構{2，2}對應的3個聯盟結構為{{a1， a2}，{ a3， a4}}，{{a1， a3}，{a2， a4}}，{{a1， a4}，{a2， a3}}。正整數4有五種不同的劃分，4個agent存在5個勢結構，分別為{4}，{3，1}，{2，2}，{2，1，1}，{1，1，1，1}，它們與15個可能的聯盟結構的對應情況如表2所示。輸入一個特定勢結構CCS={n1，n2，NA1AD，np}，其每個元素ni對應CLni中的一個聯盟，可通過函數F:N→CLN映射得到一個勢為ni的聯盟C，即C∈CLni，且|C|=ni，從而CCS={n1，n2，NA1AD，np}所對應的所有聯盟結構可以構造出來。最后，最優聯盟結構被表示為CS*。后面將使用上述的記號并且增加一些新的定義來描述本算法。

2 已有的基于勢結構的聯盟結構生成算法

2.1 Dang等人的算法1[6]

定義4 設SL(n，k，c)是所有正好有k個聯盟的聯盟結構的集合，且至少一個聯盟的基數不少于c。

定義5 設SL(n，c)是基數在3~n-1的所有聯盟結構的集合，且至少一個聯盟的基數不少于c。 也就是說:

SL(n，c)=∪n-1k=3SL(n，k，c)

算法1描述如下:

a)搜索聯盟結構圖的最底二層和頂層為L1、L2、Ln。

b)取q從(n+1)/4」~2， c=「n(q-1)/q，從L3~Ln-c+1中，搜索最大聯盟的勢(聯盟中agent的個數)大于或等于c的所有聯盟結構，即搜索SL(n， c) =∪n-c+1k=3SL(n，k，c)。其中SL(n， k， c)是第k層最大聯盟的勢大于或等于c的所有聯盟結構，一直搜索到時間不允許為止或搜索完整個聯盟結構圖。

c)返回至今為止所得到的最優的聯盟結構。

定理1 對某個q， 2≤q≤(n+1)/4」， 設算法2剛完成SL(n，「n(q-1)/q)的搜索，則限界K(n)=2q-1。

注意:由k=2q-1和c=「n(q-1)/q可得c=「n(k-1)/(k+1)，下文同。

2.2 蘇射雄等人的算法2[7]

定義6 取h=n/k」，余數m≡n modk。若m≥h，令CCS(n，k)=，否則CCS(n，k)為滿足以下條件的所有勢結構集合:

a)若m=0，滿足n1+n2+NA1AD+ni≥h且n1+n2+NA1AD+ni-1

b)若m=1，滿足n1+n2+NA1AD+ni≥h且n1+n2+NA1AD+ni-1

c)若m≥2，滿足n1+n2+NA1AD+ni≥h+1且n1+n2+NA1AD+ni-1

算法2描述如下:

a)獲得所要求的限界k，搜索聯盟結構圖的最底二層和頂層: L1、L2、Ln。若k≥「n/2，轉c);若1≤k<2，搜索整個聯盟結構圖，轉c)。

b)令k←k」，搜索勢結構集合CCS(n， k)(若CCS(n， k)為空，k←k-1，直到CCS (n， k)不為空)對應的聯盟結構。

c)返回至今為止所得到的最優聯盟結構。

定理2 對給定的限界k(2≤k≤「n/2-1)，k←k」， 若算法2剛搜索完勢結構集合CCS (n， k)(非空)對應的聯盟結構，則限界為k。

3 算法MCCS

3.1 算法的引例

例1 當n=50，k=5時，h=10， m=0;滿足定義6的n1+n2+NA1AD+ni，如下:

以上引例中n=50，k=5時，滿足定義6的n1+n2+NA1AD+ni，因此，算法2中的CCS(50，5)共包含45個勢結構。問題是只需搜索如下的4個勢結構集合: {{9，9，8，8，7，7，2}，{6，6，5，5，4，4，4，3，3，3，3，2，2}，{9，8，7，6，5，4，3，2，2，1，1，1，1}，{5，4，3，2，2，2，2，2， 1， NA1AD，1 28}}，就能得到給定限界的聯盟結構。

例2 當n=100，k=10時，h=10， m=0;滿足定義6的n1，n2，…ni同例1。因此，算法2中的CCS(100，10)還是包含45個勢結構，只是勢結構中1的個數有所增加。問題是只需搜索如下的兩個勢結構集合: {{9，9，8，8，7，7，6，6，5，5，4，4，4，3，3，3，3，2，2，1，1}，{7，6，5，4，3，2，2，2，2，2， 1， NA1AD，1 65}}，就能得到給定限界的聯盟結構。

從上面的例子可以看出，所提出的問題帶有普遍性，并且是可行的。如果能夠構造很少的勢結構，那么對于給定限界搜索哪些層中的哪些勢結構是一目了然的。當然兩個例子中所構造的勢結構并不是惟一的，如例2中的勢結構{9，9，8，8，7，7，6，6，5，5，4，4，4，3，3，3，3，2，2，1，1}換成{9，9，8，8，7，7，6，6，5，5，4，4，4，3，3，3，3，2，1，1，1，1}同樣是可行的。這也是算法優化過程所需考慮到的問題，即構造什么樣的勢結構更好些。

3.2 算法3描述

a)獲得所要求的限界k，搜索聯盟結構圖的最底兩層和頂層: L1、 L2、Ln。若k≥「n/2，轉c);若1≤k<2，搜索整個聯盟結構圖，轉d)。

b)令k←k」，取h=n/k」，余數m≡n mod k，顯然m

c)定義一個數組a。其中a[1]，…，a[h-2]分別用于存放h-1~2所需重復的次數，將a[i]個h-i(1≤i≤h-2)全部存入一個有序表b。當m=0所要構造的MCCS (n， k)的問題，相當于在有序表b中的所有元素構成的集合中找到使其和不超過n并盡可能接近n(不足時補1，直到和為n) 的所有子集。這些和為n的子集可以作為要構造的勢結構的基礎。在這些勢結構中檢查勢結構中元素的分布情況，進一步適當增加所需的勢結構或減少不必要的勢結構，直到滿足定義6的所有聯盟組合都出現，則MCCS (n， k)的構造完成。

d)返回至今為止所得到的最優的聯盟結構。

定理3 對給定的限界k(2≤k≤「n/2-1)，k←k」， 若算法3剛搜索完勢結構集合MCCS(n， k)(非空)對應的聯盟結構，則限界為k。

證明 由于MCCS (n， k)包含了所有滿足定義6的CCS(n， k)必須搜索的聯盟的組合情況，根據定理2，得證。

在勢結構的構造過程中逐一檢查每個滿足定義6的n1，n2，NA1AD，ni，首先考慮那些需重復的h-1~2以及必須判斷h-i(1≤i≤h-2)與i個1，h-i(1≤i≤h-2)與幾個2，幾個3，…的組合情況是否都包含，以及當m=1時的h與1，當2≤m

求子集和問題是一個NP完全問題，可以得到一個完全多項式時間的近似格式，即它的計算時間是關于輸入規模n和1/ε的多項式[9]。但由于要求滿足定義6的所有聯盟組合都出現，問題會更復雜一些。

4 實驗分析結果及相關比較

為獲得給定限界k，搜索聯盟結構圖的最底兩層后，胡山立等人[5]的算法在3≤k<「n/2時，計算h=n/(k+1)」+1，l=n(h-2)。若n=h-1(mod h)且k<「n/h時，需要進一步搜索層l-1，否則搜索層l。當k=2時，計算h=n/3」+1，l=n(h-2)，若n=h-1(mod h)且k<「n/h時，令l←l-1，搜索層l(若2l-1=n，繼續搜索層l;若2l-1

本文提出的算法MCCS搜索更少的勢結構就能得到滿足限界的聯盟結構，表明在搜索最底兩層及頂層后，搜索勢結構集合MCCS(n， k)對應的聯盟結構，就能達到給定限界k。用50個agent數(n=50)比較胡等人[5]算法、Dang等人[6]的算法1、蘇等人[7]給出的算法2和本文提出的算法3所搜索的勢結構數，結果如表3所示。

5 結束語

最優聯盟結構生成是聯盟形成中的一個關鍵問題。Sandholm等人已經證明，要建立最壞情況下的限界k，搜索聯盟結構圖的最底兩層是必要且是充分的。在搜索最底兩層及頂層后，胡山立和石純一的算法以最少的搜索層數達到給定的限界要求，是以層為搜索單位的當前最好的算法。但是，其所搜索的層上包含很多的勢結構(表3)，與目前基于較小的搜索單位(勢結構)的算法相比，所搜索的勢結構數明顯偏多。最近，蘇射雄和胡山立等人提出基于勢結構的算法較好地改進了Sandholm、Dang等人給出的算法，是筆者所知的迄今最好的搜索路徑與聯盟值無關的算法。

根據給定的限界k，搜索一定的勢結構集合是必要的，但找到最優的勢結構集合是一個比較難的問題。本文的算法搜索更少的勢結構，對于給定限界搜索哪些層中的哪些勢結構是一目了然的。下一步工作將探討比勢結構更小的搜索粒度或去除冗余的搜索，提出更有效的最優生成算法;另一方面，如何以最少的搜索節點數達到給定的限界要求，仍是個有待解決有問題。

參考文獻:

[1]OSBORNE M J， RUBINSTEIN A. A course in game theory[M]. Cambridge:MIT Press，1994.

[2]DANG V D， DASH R K， ROGERS A， et al. Overlapping coalition formation for efficient data fusion in multi-sensor networks[C]//Proc of the 21st National Conference on Artifical Intelligence. Boston:AAAI Press， 2006:635-640.

[3]RAHWAN T， RAMCHURN S D， DANG V D， et al. Near-optimal anytime coalition structure generation[C]//Proc of the 20th International Joint Conference on Artificial Intelligence. Boston:AAAI Press， 2007: 2365-2371.

[4]SANDHOLM T W， LARSON K， ANDERSSON M， et al. Coalition structure generation with worst case guarantees[J]. Artificial Intelligence， 1999， 11(1-2):209-238.

[5]胡山立，石純一. 給定限界要求的聯盟結構生成[J].計算機學報，2001，24(11):1285-1290.

[6]DANG V D， JENNINGS N R. Generating coalition structures with finite bound from the optimal guarantees[C]//Proc of the 3rd International Joint Conference on Autonomous Agents and Multi-agent Systems. Washington DC:IEEE Computer Society， 2004:564-571.

[7]SU She-xiong， HU Shan-li， ZHENG Sheng-fu，et al. Coalition structure generation with given required bound based on cardinality structure[C]//Proc of the 6th International Conference on Machine Lear-ning and Cybernetics. 2007: 2505-2510.

[8]KREHER D L， STINSON D R. Combinatorial algorithms:generation，enumeration， and search[M].Boca Raton:CRC Press， 1999.

[9]王曉東.計算機算法設計與分析[M]. 2版.北京:電子工業出版社，2005:301-318.