李少芳

(莆田學(xué)院　信息工程學(xué)院，福建莆田　351100)

?

與聯(lián)盟值有關(guān)的聯(lián)盟結(jié)構(gòu)生成優(yōu)化

李少芳

(莆田學(xué)院信息工程學(xué)院，福建莆田351100)

摘要：基于勢(shì)結(jié)構(gòu)與聯(lián)盟值無(wú)關(guān)的聯(lián)盟結(jié)構(gòu)生成算法的研究成果,可以應(yīng)用到與聯(lián)盟值有關(guān)的聯(lián)盟結(jié)構(gòu)生成優(yōu)化中。同時(shí)，在與聯(lián)盟值有關(guān)的問(wèn)題研究中，充分利用給定的聯(lián)盟值信息進(jìn)一步優(yōu)化計(jì)算，提高效率。文中介紹了同勢(shì)的聯(lián)盟值信息提取方法，并給出應(yīng)用實(shí)例，減少的搜索空間接近一半。

關(guān)鍵詞：多Agent；聯(lián)盟結(jié)構(gòu)；勢(shì)結(jié)構(gòu)；算法優(yōu)化；聯(lián)盟值

聯(lián)盟結(jié)構(gòu)生成問(wèn)題已經(jīng)被證明是NP-完全的。對(duì)于n個(gè)Agent產(chǎn)生的搜尋空間以O(shè)(nn)和 ω(nn/2)指數(shù)增長(zhǎng)[1-3]，通過(guò)遍歷所有聯(lián)盟結(jié)構(gòu)來(lái)找到一個(gè)最優(yōu)聯(lián)盟結(jié)構(gòu)是行不通的。通常在有限時(shí)間內(nèi)只能有選擇地搜索部分聯(lián)盟結(jié)構(gòu)，得到一個(gè)滿足給定限界k的次優(yōu)聯(lián)盟結(jié)構(gòu)。

與聯(lián)盟值無(wú)關(guān)的聯(lián)盟結(jié)構(gòu)生成算法，以不同搜索單位、不同搜索路徑加以區(qū)分，取得很大進(jìn)展。Sandholm等的算法[1]采用對(duì)聯(lián)盟結(jié)構(gòu)圖首先搜索L1、L2、Ln層(它們只占聯(lián)盟結(jié)構(gòu)圖的極小部分)，可得到收益不低于最優(yōu)收益1/[n/2]的聯(lián)盟結(jié)構(gòu)。然后再執(zhí)行自上往下逐層搜索方法，任意時(shí)間停止，可以得到一個(gè)滿足一定限界要求的解，但是要得到全局最優(yōu)解，必須搜索完所有可能的Agent聯(lián)盟結(jié)構(gòu)。胡山立等的算法[4]在搜索L1、L2、Ln層后，采用隔層搜索的方法，以最少的搜索層改進(jìn)Sandholm等的算法。Dang等人[5]首次提出不是以層為搜索單位的算法。搜索所有最大聯(lián)盟的勢(shì)不大于[n(q-1)/q]的聯(lián)盟結(jié)構(gòu)，可得到收益不小于最大收益1/(2q-1)的聯(lián)盟結(jié)構(gòu)。蘇射雄等[6-7]明確提出基于更小的搜索粒度勢(shì)結(jié)構(gòu)的搜索算法。劉驚雷等[8]提出一種快速構(gòu)建最優(yōu)聯(lián)盟結(jié)構(gòu)的DP算法。這些算法也適用于與聯(lián)盟值有關(guān)的問(wèn)題研究中[9-10]，可以針對(duì)任意的Agent聯(lián)盟收益函數(shù)，但是如果要得到最優(yōu)的聯(lián)盟結(jié)構(gòu)，這些算法仍需要搜索完所有可能的Agent聯(lián)盟結(jié)構(gòu)，搜索量非常大。利用已知的聯(lián)盟值信息，可以更有效地減小搜索空間。張新良等[9]的SCS算法在Agent收益函數(shù)滿足合作收益獨(dú)立性的前提下，對(duì)具有同構(gòu)關(guān)系的的Agent聯(lián)盟結(jié)構(gòu)按收益大小排序，通過(guò)將收益不是最大的剪枝來(lái)減少了搜索量。

1勢(shì)結(jié)構(gòu)CCS

設(shè)n個(gè)Agent的集合A={a1, a2, a3, …, an}，A中的一個(gè)非空子集C稱為Agent的一個(gè)聯(lián)盟。聯(lián)盟C中Agent的個(gè)數(shù)稱為聯(lián)盟C的勢(shì)，記為|C|。A的一個(gè)完全的劃分稱為一個(gè)聯(lián)盟結(jié)構(gòu)CS。最優(yōu)聯(lián)盟結(jié)構(gòu)用CS*表示。設(shè)聯(lián)盟結(jié)構(gòu)CS={C1, C2,…, Cp}，不失一般性地，設(shè)|C1|≥|C2|≥…≥|Cp|≥1。令n1=|C1|,n2=|C2|,…,np=|Cp|,n=n1+n2+…+np，稱{n1,n2,…,np}為聯(lián)盟結(jié)構(gòu)CS的勢(shì)結(jié)構(gòu)[5]，記為CCS。整數(shù)n的每一種劃分對(duì)應(yīng)一種勢(shì)結(jié)構(gòu)，例如，整數(shù)6的一種劃分表示為6=2+2+1+1，正好對(duì)應(yīng)勢(shì)結(jié)構(gòu){2, 2, 1, 1}。在正整數(shù)n的所有不同的劃分中，將最大加數(shù)n1不大于m的劃分個(gè)數(shù)記做f(n，m)，其值可以通過(guò)如下的遞歸方法計(jì)算[11]。n個(gè)Agent的勢(shì)結(jié)構(gòu)數(shù)就是整數(shù)n的劃分?jǐn)?shù)，值等于f(n，n)，時(shí)間復(fù)雜度為O(n2)。

以n=5為例，5個(gè)Agent的所有7個(gè)勢(shì)結(jié)構(gòu)分別是{5}、{4, 1}、{3, 2}、{3, 1, 1}、{2, 2, 1}、{2, 1, 1, 1}、{1, 1, 1, 1, 1}，它們對(duì)應(yīng)的聯(lián)盟結(jié)構(gòu)數(shù)分別為1、5、10、10、15、10、1，總共52個(gè)。

2同勢(shì)的聯(lián)盟值信息提取

可以根據(jù)勢(shì)結(jié)構(gòu)CCS劃分聯(lián)盟結(jié)構(gòu)空間，并盡可能找到包含最優(yōu)解或次優(yōu)解的勢(shì)結(jié)構(gòu)后，再對(duì)其所對(duì)應(yīng)的聯(lián)盟結(jié)構(gòu)進(jìn)行搜索，減少搜索量，在合理時(shí)間內(nèi)找到最優(yōu)解或次優(yōu)解。下面表1給出n=5時(shí)的一組聯(lián)盟值?？疾觳煌瑒?shì)的聯(lián)盟值，計(jì)算各勢(shì)的聯(lián)盟上界值和平均值，對(duì)低于平均值的聯(lián)盟進(jìn)行剪枝。

表1　n=5時(shí)各聯(lián)盟值

算法主要分三步進(jìn)行：

Step 1：算法要求輸入所有聯(lián)盟C的v(C)值，并給定一個(gè)限界k,1/k∈[0.5, 1]，這時(shí)可能返回的局部最優(yōu)解，其質(zhì)量保證至少是最優(yōu)解的1/2?？梢杂寐?lián)盟的勢(shì)|C|作為下標(biāo)，定義兩個(gè)一維數(shù)組max和avg，用以存放勢(shì)|C|的所有聯(lián)盟的上界值和平均值。單聯(lián)盟如{{1},{2}, …,{n}}和全聯(lián)盟{(lán)1, 2, …, n}的值首先作為局部最優(yōu)解。

Step 2：對(duì)應(yīng)勢(shì)結(jié)構(gòu)，用保留的聯(lián)盟構(gòu)造出聯(lián)盟結(jié)構(gòu)，搜索找到該勢(shì)結(jié)構(gòu)對(duì)應(yīng)的最優(yōu)解或次優(yōu)解的聯(lián)盟結(jié)構(gòu)。

Step 3：對(duì)比第二個(gè)階段找到的各聯(lián)盟結(jié)構(gòu)，在合理時(shí)間內(nèi)找到最優(yōu)解或次優(yōu)解CS*。

后兩個(gè)階段只要找到最優(yōu)解(k=1)或是足夠好的解(也就是0.5< k< 1)，算法停止。

在循環(huán)遍歷勢(shì)結(jié)構(gòu)的搜索過(guò)程中，不創(chuàng)建任何多余或無(wú)效的聯(lián)盟結(jié)構(gòu)。

3搜尋優(yōu)化示例

以表1數(shù)據(jù)為例來(lái)說(shuō)明算法的搜索優(yōu)化過(guò)程如下。5個(gè)Agent的所有7個(gè)勢(shì)結(jié)構(gòu)分別是{5}、{4, 1}、{3, 2}、{3, 1, 1}、{2, 2, 1}、{2, 1, 1, 1}、{1, 1, 1, 1, 1}。勢(shì)為1, 2和5的聯(lián)盟必須先被搜索， 得到k=2.5的局部最優(yōu)解。勢(shì)結(jié)構(gòu){5}對(duì)應(yīng)的由唯一的全聯(lián)盟構(gòu)成的聯(lián)盟結(jié)構(gòu){1, 2, 3, 4, 5}的值=250， 勢(shì)結(jié)構(gòu){1, 1, 1, 1, 1}對(duì)應(yīng)的由單聯(lián)盟構(gòu)成的聯(lián)盟結(jié)構(gòu){{1},{2},{3}, {4},{5}}的值=200， 首先比較這兩個(gè)值， 取較大者250為局部最優(yōu)解。

勢(shì)結(jié)構(gòu){4, 1}中的4對(duì)應(yīng)的聯(lián)盟， 根據(jù)max[4]=220和avg[4]=190， 只從{1, 2, 4, 5}(190)、{1, 3, 4, 5}(220)、{2, 3, 4, 5}(200)中選取。勢(shì)結(jié)構(gòu){4, 1}中的1對(duì)應(yīng)的單聯(lián)盟， 根據(jù)max[1]=60和avg[1]=40， 只從{1}(50)、{2}(40)、{5}(60)中選取。因此， 較快找到勢(shì)結(jié)構(gòu){1, 4}對(duì)應(yīng)的最優(yōu)聯(lián)盟結(jié)構(gòu){{1,3, 4, 5}, {2}}， 值為260。

勢(shì)結(jié)構(gòu){3，2}中的3對(duì)應(yīng)的聯(lián)盟， 根據(jù)max[3]=190， avg[3]=142， 只從{1，2，3}(160)、{1, 4, 5}(150)、{2, 3, 4}(150)、{2, 4, 5}(180)、{3, 4, 5}(190)中選取。勢(shì)結(jié)構(gòu){3, 2}中的2對(duì)應(yīng)的聯(lián)盟， 根據(jù)max[2]=120和avg[2]=79， 只從{1, 3}(90)、{1, 4}(80)、{1, 5}(90)、{2, 3}(90){2, 5}(120)、{4, 5}(110)中選取。因此， 較快找到勢(shì)結(jié)構(gòu){2, 3}對(duì)應(yīng)的最優(yōu)聯(lián)盟結(jié)構(gòu){{1, 3}，{2, 4, 5 }}和{{4, 5}，{1, 2, 3 }}， 值都為270。

勢(shì)結(jié)構(gòu){3, 1, 1}中的3對(duì)應(yīng)的聯(lián)盟， 根據(jù)max[3]=190， avg[3]=142， 只從{1, 2, 3}(160)、{1, 4, 5}(150)、{2, 3, 4}(150)、{2, 4, 5}(180)、{3, 4, 5}(190)中選取。而1對(duì)應(yīng)的單聯(lián)盟， 根據(jù)max[1]=60和avg[1]=40， 只從{1}(50)、{2}(40)、{5}(60)中選取。因此， 較快找到勢(shì)結(jié)構(gòu){1, 1, 3}對(duì)應(yīng)的最優(yōu)聯(lián)盟結(jié)構(gòu){{1}, {2}, {3, 4, 5 }}， 值為280。

勢(shì)結(jié)構(gòu){2, 2, 1}中的2對(duì)應(yīng)的聯(lián)盟， 根據(jù)max[2]=120和avg[2]=79， 只從{1，3}(90)、{1, 4}(80)、{1, 5}(90)、{2, 3}(90)、{2, 5}(120)、{4, 5}(110)中選取。而1對(duì)應(yīng)的單聯(lián)盟， 根據(jù)max[1]=60和avg[1]=40， 只從{1}(50)、 {2}(40)、 {5}(60)中選取。因此， 較快找到勢(shì)結(jié)構(gòu){1, 2, 2}對(duì)應(yīng)的最優(yōu)聯(lián)盟結(jié)構(gòu){{2}, {1, 3}, {4, 5}}(40+90+110=240)。

勢(shì)結(jié)構(gòu){1, 1, 1, 2}中的2對(duì)應(yīng)的聯(lián)盟， 根據(jù)max[2]=120和avg[2]=79， 只從{1, 3}(90)、{1, 4}(80)、{1, 5}(90)、{2, 3}(90)、{2, 5}(120)、{4, 5}(110)中選取。而1對(duì)應(yīng)的單聯(lián)盟， 根據(jù)max[1]=60和avg[1]=40， 只從{1}(50)、{2}(40)、{5}(60)中選取。因此， 較快找到勢(shì)結(jié)構(gòu){1, 2, 2}對(duì)應(yīng)的最優(yōu)聯(lián)盟結(jié)構(gòu){{1}, {2}, {5}, {1, 3}}(50+40+60+90=240)。

對(duì)比得到， 本例的最優(yōu)聯(lián)盟結(jié)構(gòu)為{{1}, {2}, {3, 4, 5 }}， 值為280。經(jīng)表2統(tǒng)計(jì)， 搜索空間減少44%。

表2　n=5時(shí)優(yōu)化前后的聯(lián)盟結(jié)構(gòu)計(jì)算量對(duì)比

4算法的基本信息對(duì)比

表3　各算法的基本信息對(duì)比

任一時(shí)間算法是指算法可以在任意時(shí)間中止，返回一個(gè)解，并隨著時(shí)間的增加，解更優(yōu)，其相對(duì)于非任一時(shí)間算法具有更好的實(shí)際應(yīng)用。搜索單位可以是層、勢(shì)結(jié)構(gòu)、聯(lián)盟組合或聯(lián)盟結(jié)構(gòu)結(jié)點(diǎn)等。搜索路徑是否受聯(lián)盟值影響也是衡量算法通用性的一個(gè)重要方面，一些算法的搜索路徑是固定不變的，另一些則根據(jù)給定的聯(lián)盟值的不同而發(fā)生變化。限界表示在最壞情況下搜索得到的局部最優(yōu)解的質(zhì)量。各算法的基本信息對(duì)比，如表3所示。

5結(jié)語(yǔ)

DP算法[9]利用最優(yōu)聯(lián)盟結(jié)構(gòu)問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問(wèn)題性質(zhì)，通過(guò)避免尋找整個(gè)空間來(lái)保證最優(yōu)解，速度較快，時(shí)間復(fù)雜度為O(3n)，但是它不能夠在任一時(shí)間產(chǎn)生解，要在內(nèi)存中保留具有2n-1個(gè)輸入的三張表。對(duì)于中等規(guī)模數(shù)量(大于26)的Agent，DP方法很快地變得不適用。如果試圖通過(guò)限制能被形成的聯(lián)盟的大小來(lái)減少問(wèn)題的復(fù)雜性，從而使返回解的速度加快，然而，這樣的限制也大大地減少了可能解的有效性，因?yàn)樵谶@種情況下被選擇的解可能任意地遠(yuǎn)離最優(yōu)解。大多數(shù)的DP算法和啟發(fā)式算法的搜索路徑與給定的聯(lián)盟值有關(guān)，或者是在滿足一定的假設(shè)條件的前提下提出的[12-14]，當(dāng)沒(méi)有任何啟發(fā)信息的條件下，只能選擇搜索路徑不受聯(lián)盟值影響的算法。文中的算法與聯(lián)盟值有關(guān)，首先要求輸入所有2n-1個(gè)聯(lián)盟的值，需要進(jìn)行2n-1次賦值運(yùn)算，在實(shí)際應(yīng)用中也只對(duì)較小的n有效。其中勢(shì)結(jié)構(gòu)計(jì)算的時(shí)間復(fù)雜度為O(n2)，算法保留的聯(lián)盟數(shù)多少與給定的聯(lián)盟值信息有關(guān)，進(jìn)一步的優(yōu)化計(jì)算可以將搜索空間減少近一半。

目前研究中的一些進(jìn)展包括：一是不以層為搜索單位，而以更小的搜索粒度，如勢(shì)結(jié)構(gòu)、聯(lián)盟組合等進(jìn)一步減少搜索的結(jié)點(diǎn)數(shù)，從而加快搜索；二是研究給定聯(lián)盟值的情況，如何充分利用這些信息減少搜索空間；三是給定限界的情況搜索算法的進(jìn)一步優(yōu)化；四是對(duì)已提出算法之間的更詳盡的比較分析。這些進(jìn)一步的研究工作都值得期待。

參 考 文 獻(xiàn)

[1]Sandholm T W, Larson K, Andersson M, et al. Coalition Structure Generation with Worst Case Guarantees[J]. Artificial Intelligence, 1999,111(1-2):209-238.

[2]Talal Rahwan,Tomasz P, Michalak, et al. Coalition structure generation: A survey[J]. Artificial Intelligence,2015, 229:139-174.

[3]詹宇森.多Agent合作博弈中的計(jì)算復(fù)雜性及相關(guān)算法研究[D].南京:南京大學(xué),2013.

[4]胡山立,石純一.給定限界要求的聯(lián)盟結(jié)構(gòu)生成[J].計(jì)算機(jī)學(xué)報(bào),2001,24(11):1285-1290.

[5]Dang V D, Jennings N R. Generating coalition structures with finite bound from the optimal guarantees[C]//Proceedings of the 3rd International Joint Conference on Autonomous Agents and Multi-Agent Systems. New York:AAMAS,2004:564-571.

[6]Su She-Xiong, Hu Shan-Li, Zheng Sheng-Fu,et al.Coalition Structure Generation with Given Required Bound based on Cardinality Structure[C]// Proceedings of the 6th International Conference on Machine Learning and Cybernetics.Hong Kong:ICMLC,2007: 2505-2510.

[7]胡山立,石純一,李少芳.給定限界的勢(shì)結(jié)構(gòu)分組與聯(lián)盟結(jié)構(gòu)生成[J].計(jì)算機(jī)學(xué)報(bào), 2012,35(12):2618-2624.

[8]劉驚雷,童向榮,張偉.一種快速構(gòu)建最優(yōu)聯(lián)盟結(jié)構(gòu)的方法[J].計(jì)算機(jī)工程與應(yīng)用,2006,42(4):35-44.

[9]張新良,石純一.多Agent聯(lián)盟結(jié)構(gòu)動(dòng)態(tài)生成算法[J].軟件學(xué)報(bào),2007,18(3):574-581.

[10]陳少白,張嫚,胡朝娣.賦權(quán)合作博弈中的可行聯(lián)盟結(jié)構(gòu)與收益分配[J].武漢科技大學(xué)學(xué)報(bào),2015,38(1):77-80.

[11]王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析 [M]. 4版. 北京:電子工業(yè)出版,2012.

[12]劉驚雷,張偉,童向榮,等.一種O(2.983n)時(shí)間復(fù)雜度的最優(yōu)聯(lián)盟結(jié)構(gòu)生成算法[J]. 軟件學(xué)報(bào),2011,22(5):938-950.

[13]Rahwan T, Jennings N R. An Improved Dynamic Programming Algorithm for Coalition Structure Generation[C]// Proceedings of the 7th international conference on Autonomous Agents and Multi-Agent Systems. Estoril: AAMAS, 2008:1417-1420.

[14]Panagopoulos, Athanasios Aris, Chalkiadakis, et al. Towards optimal solar tracking: a dynamic programming approach[C]// Proceedings of the 29th AAAI Conference on Artificial Intelligence.Austin, US: AAAI,2015:695-701.

Coalition Structure Generation Optimization Related to Coalition Value

LI Shaofang

(Information Engineering College, Putian University, Putian 351100, China)

AbstractThe coalition structure generation algorithm based on cardinality structure has nothing to do with the coalition values, which results can be applied to the coalition structures generated in optimization related to the coalition value. Meanwhile, in the study of problems related to the coalition value, people can make full use of the given coalition values information for further optimal calculation and improve efficiency. The paper introduces the information extraction method of coalition values with same cardinality, giving application examples, and reducing the nearly half search space.

Key wordsmulti-agent; coalition structure; cardinality structure ; algorithm optimization; coalition value

文章編號(hào)：1009-0312(2016)01-0015-05

中圖分類號(hào)：TP393

文獻(xiàn)標(biāo)識(shí)碼：A

作者簡(jiǎn)介：李少芳(1971—)，女，福建福安市人，副教授，碩士，主要從事計(jì)算機(jī)算法及多Agent系統(tǒng)研究。

基金項(xiàng)目：福建省科技廳資助項(xiàng)目(2015H0033)；福建省教育廳資助項(xiàng)目(JK2015041)。

收稿日期：2015-10-12