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

李少芳

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

?

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

李少芳

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

勢結(jié)構(gòu){3，2}中的3對應(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)中選取。勢結(jié)構(gòu){3, 2}中的2對應(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)中選取。因此， 較快找到勢結(jié)構(gòu){2, 3}對應(yīng)的最優(yōu)聯(lián)盟結(jié)構(gòu){{1, 3}，{2, 4, 5 }}和{{4, 5}，{1, 2, 3 }}， 值都為270。

勢結(jié)構(gòu){3, 1, 1}中的3對應(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對應(yīng)的單聯(lián)盟， 根據(jù)max[1]=60和avg[1]=40， 只從{1}(50)、{2}(40)、{5}(60)中選取。因此， 較快找到勢結(jié)構(gòu){1, 1, 3}對應(yīng)的最優(yōu)聯(lián)盟結(jié)構(gòu){{1}, {2}, {3, 4, 5 }}， 值為280。

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

勢結(jié)構(gòu){1, 1, 1, 2}中的2對應(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對應(yīng)的單聯(lián)盟， 根據(jù)max[1]=60和avg[1]=40， 只從{1}(50)、{2}(40)、{5}(60)中選取。因此， 較快找到勢結(jié)構(gòu){1, 2, 2}對應(yīng)的最優(yōu)聯(lián)盟結(jié)構(gòu){{1}, {2}, {5}, {1, 3}}(50+40+60+90=240)。

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

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

4算法的基本信息對比

表3　各算法的基本信息對比

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

5結(jié)語

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

目前研究中的一些進(jìn)展包括：一是不以層為搜索單位，而以更小的搜索粒度，如勢結(jié)構(gòu)、聯(lián)盟組合等進(jìn)一步減少搜索的結(jié)點(diǎn)數(shù)，從而加快搜索；二是研究給定聯(lián)盟值的情況，如何充分利用這些信息減少搜索空間；三是給定限界的情況搜索算法的進(jìn)一步優(yōu)化；四是對已提出算法之間的更詳盡的比較分析。這些進(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合作博弈中的計算復(fù)雜性及相關(guān)算法研究[D].南京:南京大學(xué),2013.

[4]胡山立,石純一.給定限界要求的聯(lián)盟結(jié)構(gòu)生成[J].計算機(jī)學(xué)報,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]胡山立,石純一,李少芳.給定限界的勢結(jié)構(gòu)分組與聯(lián)盟結(jié)構(gòu)生成[J].計算機(jī)學(xué)報, 2012,35(12):2618-2624.

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

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

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

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

[12]劉驚雷,張偉,童向榮,等.一種O(2.983n)時間復(fù)雜度的最優(yōu)聯(lián)盟結(jié)構(gòu)生成算法[J]. 軟件學(xué)報,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

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

中圖分類號：TP393

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

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

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

收稿日期：2015-10-12