任子儀，童向榮

（煙臺大學 計算機與控制工程學院，山東 煙臺 264005）

聯(lián)盟生成是多Agent系統(tǒng)(multi-agent system，MAS)研究基本問題之一[1-2]，主要將Agent進行合作或協(xié)商，使其效用增加。Agent聯(lián)盟基本上被認為在MAS的框架內(nèi)的一組Agent，愿意與這組中的其他Agent合作，共同合作活動的目的是達到最佳的標準。當Agent通過組建聯(lián)盟共同工作時，聯(lián)盟結(jié)構(gòu)生成就會發(fā)生[3]。目標就是求一種最優(yōu)的聯(lián)盟結(jié)構(gòu)，使得所求的社會福利最大，并返回其值[4-5]。

Agent在聯(lián)盟生成時達到最優(yōu)方案不一定是全局最優(yōu)解，但是應(yīng)該是Nash最優(yōu)解[6-7]或者次優(yōu)解，因此聯(lián)盟生成主要包括以下活動：

1) 聯(lián)盟結(jié)構(gòu)生成：Agent之間進行協(xié)商生成聯(lián)盟，但不考慮各個聯(lián)盟之間的協(xié)商。

2) 解決每個聯(lián)盟優(yōu)化問題：將Agent的任務(wù)和資源集中在一起，共同解決問題。Agent之間進行協(xié)商使聯(lián)盟的社會福利盡可能最大化，即尋找最優(yōu)的方法使得聯(lián)盟本身的效用最大化。

3) 劃分值：在進行收益分配的時候，常用的方法有兩種，即公平(每個Agent所得到的收益是Agent在博弈中的貢獻的體現(xiàn))和穩(wěn)定(存在沒有和其他Agent協(xié)商而單獨形成自己的自私利益聯(lián)盟)。

同樣，存在很多方法尋找和創(chuàng)建一個最優(yōu)的聯(lián)盟——協(xié)商或搜索以及用于找出解決問題的幾種潛在的方法，例如：遺傳算法、博弈論、粒子群算法等。但是，隨著研究的不斷深入，在現(xiàn)實世界的應(yīng)用中有一些聯(lián)盟結(jié)構(gòu)是不允許生成的[8]。目前，聯(lián)盟研究的熱點問題主要是約束條件下聯(lián)盟生成。在現(xiàn)有研究中，很多文獻已經(jīng)考慮將聯(lián)盟進行廣泛應(yīng)用，例如：通過形成聯(lián)盟，自主傳感器可以改善某些區(qū)域的監(jiān)控情況[9]；認識無線電網(wǎng)絡(luò)可以增加它們的吞吐量[10]；購買者可以通過批量購買而獲得較低的價格[11]；自主連接車輛進行護航工作[12]；形成聯(lián)盟促進社交網(wǎng)絡(luò)關(guān)系[13-14]等。

在Agent聯(lián)盟研究發(fā)展中，Sandholm等[15]最先提出最壞情況有限界聯(lián)盟結(jié)構(gòu)生成；Yeh等[16]首次使用動態(tài)規(guī)劃算法聯(lián)盟生成并求得精確最優(yōu)解；隨著研究的不斷深入，Agent數(shù)量的增加，先前的算法越來越不能滿足當前的需求，Dang等[17]首次提出建立次優(yōu)聯(lián)盟結(jié)構(gòu)并求得次優(yōu)解；Greco等[18]經(jīng)過進一步研究，提出了一種新的聯(lián)盟結(jié)構(gòu)生成的方式——約束聯(lián)盟結(jié)構(gòu)，即在生成聯(lián)盟的過程對聯(lián)盟添加約束。

1 基本定義

1.1 主要定義

假設(shè)所有的Agent都是理性的，并使用合作博弈建模進行Agent之間的合作和協(xié)商。在博弈中，令 N 是一個 A gent集，其中 n = |N| 表 示 N 中Agent的個數(shù)，則 N =(a1,a2,···,an)， 聯(lián) 盟即 N 中非空的子集。

定義1 聯(lián)盟 結(jié) 構(gòu)。對 于任意 聯(lián) 盟 C ， 在 C 上形成的聯(lián)盟結(jié)構(gòu) C S ={C1,C2,···,Ck}， 其 中 ∪ C S=C，并 且 對 于 任 意 i , j∈ { 1,2,···,k},i≠ j 都 需 要 滿 足Ci∩Cj=?。

例1 一個集合 N ={a1,a2,a3}，N上的聯(lián)盟一共 有7種 情 況，分 別 是 { a1}、 { a2} 、 { a3} 、 { a1,a2}、{a1,a3}、 { a2,a3}、 { a1,a2,a3}，聯(lián)盟結(jié)構(gòu)一共存在5種情況，分別是 {{ a1},{a2},{a3}}、 { { a1},{a2,a3}}、 { { a2},{a1,a3}}、{{a3},{a1,a2}}和 { a1,a2,a3}。

定義2 社會福利。社會福利即為聯(lián)盟結(jié)構(gòu)CS中所有的聯(lián)盟 Ci,i∈ { 1,2,···,k} 的收益之和，將聯(lián)盟的值記為 v ( Ci)， 并 且要求 v ( Ci)≥0，聯(lián)盟結(jié)構(gòu)的社會福利記為 V ( CS)，將具有最大的社會福利聯(lián)盟結(jié)構(gòu)稱為最優(yōu)聯(lián)盟結(jié)構(gòu)，記為 C S?，其最優(yōu)社會福利記為 V ( CS?)，則

定義3 次加性。對于任意的不相交的聯(lián)盟S,T∈N ， 都 存 在 v ( S ∪T)≤v(S)+v(T)。換 言 之，{{a1},{a2},···,{an}}為最大社會福利的聯(lián)盟結(jié)構(gòu)。

定義4 特征函數(shù)。給定一個 n 個Agent的博弈， C 是一 個 聯(lián)盟， v ( C) 是 指 C 和 N - C 兩個Agent博弈中 C 的最大效用， v ( C) 稱 為聯(lián)盟 C 特征函數(shù)(characteristic function)，規(guī)定 v ( ? )=0。

1.2 博弈類型

在常用的聯(lián)盟博弈模型中，通常用貨幣來表示聯(lián)盟的價值(或獎勵[19])。在進行博弈的過程中，假設(shè)存在一個在Agent之間可以自由流動的交換媒介(如貨幣)，每個Agent可以根據(jù)自己的績效得到相應(yīng)的貨幣，這種博弈被稱為“單邊支付”博弈或可轉(zhuǎn)移效用(transferable utility，TU)博弈。相反，聯(lián)盟的績效是用向量表示的，直接指定每個成員的績效，Agent只能服從這種分配方案，不能對分配方案進行修改，這種博弈被稱為不可轉(zhuǎn)移效用(non-transferable utility，NTU)博弈。在多Agent系統(tǒng)中，可轉(zhuǎn)移效用博弈受到了很大的關(guān)注。

1) 特征函數(shù)博弈

特征函數(shù)博弈(characteristic function games，CFGs)是聯(lián)盟的價值完全取決于它所包含的Agent的值。將特征函數(shù)博弈定義為 ( N ,v)，其中N表示Agent數(shù)據(jù)集，v 是一個函數(shù)，稱為特征函數(shù)，對于每個聯(lián)盟C映射到函數(shù)中的值 v ( C ) 記為v:2N→R。

2) 分區(qū)博弈

在分區(qū)博弈(partition function games，PFGs)中聯(lián)盟的價值不僅僅取決于所包含的Agent的值，也會受非成員分區(qū)的影響。將分區(qū)博弈定義為(N,w)， 其 中 N 表 示Agent數(shù)據(jù)集， w 是一個分區(qū)函數(shù)，每個嵌入式聯(lián)盟 ( C ,CS) 映射到函數(shù)中的值是 w ( (C,CS)) 或 w ( C,CS)。

CFGs是PFGs的子集，聯(lián)盟C在CFGs中有一個精確值，但在PFGs中卻存在很多值，這是因為使用PFGs有不同的方法對 N / C 中的Agent進行分區(qū)。因此，在進行研究的過程中，使用CFGs更容易得到解決方案，提高算法的效率。

1.3 空間表示

在聯(lián)盟結(jié)構(gòu)生成問題中，通過聯(lián)盟結(jié)構(gòu)搜索得到最優(yōu)聯(lián)盟結(jié)構(gòu)。

1) 聯(lián)盟結(jié)構(gòu)圖

Sandholm等[15]提出的聯(lián)盟結(jié)構(gòu)圖中，每個節(jié)點代表一個聯(lián)盟結(jié)構(gòu)，并且將節(jié)點進行了劃分，表示為其中表示由i個聯(lián)盟組成的所有的聯(lián)盟結(jié)構(gòu)的節(jié)點；邊緣連接兩個聯(lián)盟結(jié)構(gòu)，當且僅當它們屬于不同的劃分，如和；其中中的聯(lián)盟結(jié)構(gòu)是由中的聯(lián)盟分裂成兩個聯(lián)盟形成的。圖1所示為具有4個Agent集聯(lián)盟結(jié)構(gòu)圖。

圖 1 4個Agent聯(lián)盟結(jié)構(gòu)Fig. 1 The coalition structure graph with 4 Agents

2) 整數(shù)分區(qū)圖

在聯(lián)盟結(jié)構(gòu)圖中，能直接看出具有i個聯(lián)盟所組成的聯(lián)盟結(jié)構(gòu)的情況。而Dean等[20]提出的整數(shù)分區(qū)圖中，則是基于聯(lián)盟結(jié)構(gòu)中所包含的聯(lián)盟的數(shù)量，將聯(lián)盟結(jié)構(gòu)中的空間劃分成不相交的子空間，每個子空間是由n個整數(shù)分割表示的。整數(shù)n的分區(qū)值可以通過遞歸的方法計算[21]，用Pn表 示整數(shù)分區(qū)。例如：P4={{4},{1,3},{2,2},{1,1,2},{1,1,1,1}}。

假設(shè) I ∈ P ， 定 義 ΠIC∈ΠC是所有聯(lián)盟結(jié)構(gòu)組成的子空間，其中聯(lián)盟的大小受 I 部分的影響。例如：表示是由2個只有1個Agent聯(lián)盟和1個有2個Agent組成的聯(lián)盟形成的聯(lián)盟結(jié)構(gòu)。對于這種表示一般用整數(shù)分區(qū)圖來表示。整數(shù)分區(qū)圖也是一個無向圖，其中每個節(jié)點代表一個子空間。兩個節(jié)點 I , I′∈ Pn是通過邊連接的，當且僅當 i , j ∈ I 時 ， I′=(I{i,j})Ξ{i+j}( Ξ 表示多重集的結(jié)合操作)。圖2給出了有4個Agent整數(shù)分區(qū)圖。

圖 2 4個Agent整數(shù)分區(qū)圖Fig. 2 The integer-partition graph representation of 4 Agents

2 聯(lián)盟生成的復(fù)雜度

2.1 輸入值的大小

對于具有n個Agent的數(shù)據(jù)集，會產(chǎn)生2n-1個非空的子集，生成 2n-1 個聯(lián)盟，在進行運算時需要輸入 2n-1 個值。聯(lián)盟結(jié)構(gòu)生成算法的輸入值和Agent的個數(shù)之間呈指數(shù)關(guān)系。

理論上，在進行輸入操作時即可排除一些不合理的聯(lián)盟，或者在進行聯(lián)盟結(jié)構(gòu)生成的時候就可以忽略一部分的輸入。但是在接下來進行的操作過程中無法保證存在單一的聯(lián)盟與其他的聯(lián)盟進行合作之后的社會福利不是最佳社會福利，這是因為：被排除在外的聯(lián)盟中可能存在比其他的聯(lián)盟社會福利更大的聯(lián)盟。

2.2 聯(lián)盟結(jié)構(gòu)的數(shù)量

隨著聯(lián)盟結(jié)構(gòu)不斷發(fā)展，Agent數(shù)量的增多，新問題也隨之產(chǎn)生。聯(lián)盟結(jié)構(gòu)的個數(shù)表示為

其中：n代表數(shù)據(jù)集中的Agent個數(shù)； Z ( n,i) 表示具有i個聯(lián)盟組成的聯(lián)盟結(jié)構(gòu)的個數(shù)； Z ( n,i) 滿足第2類Striling數(shù)的特征，即

式中： Z ( n,i)=Z(n,1)=1； i Z (n-1,i) 表示在現(xiàn)有存在的聯(lián)盟中增加一個新的Agent形成的聯(lián)盟結(jié)構(gòu)的個數(shù)； Z (n-1,i-1) 表示將一個新的Agent加入到已有的聯(lián)盟中，因為現(xiàn)在的聯(lián)盟結(jié)構(gòu)中只有i-1個聯(lián)盟被計算。有以下基本結(jié)果[22-24]：

命題1 對于具有n個Agent的集合，具有2n-1個 聯(lián)盟， O (nn) 和 ω ( nn/2) 個聯(lián)盟結(jié)構(gòu)(即聯(lián)盟結(jié)構(gòu)的個數(shù)的階介于～n之間)。

命題2 尋找最優(yōu)聯(lián)盟結(jié)構(gòu)是NP難問題。

隨著Agent數(shù)量的增加，聯(lián)盟結(jié)構(gòu)的數(shù)量也隨之增加。經(jīng)過實驗的證明，當數(shù)據(jù)集中Agent個數(shù)超過15時，使用窮舉法列舉出所有聯(lián)盟結(jié)構(gòu)是不可行的。

3 最壞情況有限界聯(lián)盟結(jié)構(gòu)生成

Dean和Boddy在時間依賴規(guī)劃(time dependent planning)的基礎(chǔ)上提出了Anytime算法，其本質(zhì)是一種反復(fù)求解使得結(jié)果更加精確的算法。在算法的運行過程中，能夠很快得到一個不精確的解，然后進行若干次的重復(fù)過程，經(jīng)過重復(fù)后逐步提高解的質(zhì)量，Anytime算法一個最顯著的優(yōu)點就是能夠很好地權(quán)衡計算時間和解的質(zhì)量。Sandholm等[15]使用Anytime算法開創(chuàng)性地提出了一種最壞情況有限界聯(lián)盟結(jié)構(gòu)生成。

命題1表明，在聯(lián)盟結(jié)構(gòu)圖上找到最優(yōu)的聯(lián)盟結(jié)構(gòu)是不可行的。所以，在進行聯(lián)盟結(jié)構(gòu)圖的搜索的時候設(shè)定一個限界。

對聯(lián)盟結(jié)構(gòu)的子集N進行搜索，目的在于尋找搜索中的最優(yōu)聯(lián)盟結(jié)構(gòu)，即局部最優(yōu)聯(lián)盟結(jié)構(gòu)，記：

同時，為了保證設(shè)定的聯(lián)盟結(jié)構(gòu)在最佳范圍內(nèi)，即存在一個有限的但是盡可能小的值k，k被稱為搜索的解的界限，也是衡量局部最優(yōu)解的標準。能夠建立起界限的最小的k記為

通常，如果沒有對聯(lián)盟結(jié)構(gòu)進行完全搜索，設(shè)定一個正確的界限是很難的。這是因為：在剪枝的過程中雖然可以減少一些聯(lián)盟結(jié)構(gòu)的搜索，但是很難保證沒有剪掉的比剪掉的具有更優(yōu)性。在進行社會福利的定義的時候，令任意一個聯(lián)盟Ci的值 v ( Ci)≥0，并且一個聯(lián)盟結(jié)構(gòu)的社會福利這兩點就保證了上述假設(shè)是不存在的，即在沒有對聯(lián)盟結(jié)構(gòu)進行搜索的前提下設(shè)置一個界限來縮小搜索聯(lián)盟結(jié)構(gòu)的數(shù)量。

3.1 建立界限

本節(jié)主要討論如何盡可能地減少對圖的搜索的前提下，建立一個界限k。

定理1 對于界限k，可以只搜索聯(lián)盟結(jié)構(gòu)圖的最低的兩級(圖1中第、層)。在這個搜索中，界限k=n，需要搜索的聯(lián)盟結(jié)構(gòu)節(jié)點的數(shù)量是 2n-1，這也是能夠建立起界限的最小的搜索，即nmin=2n-1。并且，沒有其他的算法對于聯(lián)盟結(jié)構(gòu)的搜索的數(shù)量會比 2n-1少。

最底層具有1個聯(lián)盟結(jié)構(gòu)，第二最底層中具有 2n-2 個聯(lián)盟(N中的所有子集，除掉全集和空集)。在這一層中，每個聯(lián)盟結(jié)構(gòu)都有2個聯(lián)盟，所以一共有個聯(lián)盟結(jié)構(gòu)。只搜索最底下兩層，一共搜索個聯(lián)盟結(jié)果。

3.2 算法描述

算法1 最壞情況有保證聯(lián)盟結(jié)構(gòu)生成算法1) 搜索聯(lián)盟結(jié)構(gòu)圖的最底二層；

2) 從聯(lián)盟結(jié)構(gòu)圖的頂層(第n層)開始，作寬度優(yōu)先搜索，一直搜索到時間不允許為止或搜索完整個聯(lián)盟結(jié)構(gòu)圖；

3) 返回迄今為止所得到的最優(yōu)的聯(lián)盟結(jié)構(gòu)。

先前使用特征函數(shù)的方式[25-26]進行聯(lián)盟結(jié)構(gòu)生成，算法1是一種任意時間算法，可以在任何時間中斷。如果將第1、2層搜索完成后，還存在剩余時間，則可進一步地搜索縮小界限。

在 2n-1個節(jié)點被搜索完之前，無法建立一個界限。當搜索到 2n-1+1 個節(jié)點時，可以建立界限k=n；搜索到 2n-1+1 個節(jié)點的時候，界限變成k=。通過更多實驗驗證：當界限k變成時，搜索的層數(shù)就會增加2層。當搜索的層數(shù)每增加2層，界限k前面的除數(shù)就會加1，若只多搜索一層時，沒有明顯效果。

總之，最壞情況有限界聯(lián)盟結(jié)構(gòu)生成算法中第2步具有很強的理性，即界限k能夠迅速地下降，同時該算法的收益遞減，如圖3所示。

圖 3 界限k作為10個Agent博弈中搜索的函數(shù)Fig. 3 Ratio bound k as a function of search in a 10-Agents game

胡山立等[27-28]對算法1深入研究并進行改進，給出了解決問題的一種任一時間聯(lián)盟結(jié)構(gòu)生成算法和給定界限要求的聯(lián)盟結(jié)構(gòu)生成。Dang等[29]提出不以層為單位最壞情況有限界的聯(lián)盟結(jié)構(gòu)生成。

4 動態(tài)規(guī)劃聯(lián)盟生成求精確最優(yōu)解

動態(tài)規(guī)劃(dynamic programming，DP)算法和分治法類似，其基本思想是將待求解的問題分解成若干個次級子問題，在求解的過程中，先求解子問題，然后從子問題的解中得到要求解的問題的答案。將動態(tài)規(guī)劃算法應(yīng)用于最優(yōu)化的問題，一般分為4個步驟來完成：

1) 找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；

2) 遞歸定義的最優(yōu)值；

3) 以自頂向下的方式計算出最優(yōu)值；

4) 根據(jù)計算最優(yōu)值所得到的信息，構(gòu)造最優(yōu)解。

將動態(tài)規(guī)劃算法應(yīng)用于聯(lián)盟中的想法是Yeh 在 1986 年 首 次 提出的[16]；Rothkopf[30]及劉驚雷等[31]使用DP算法對求解最優(yōu)聯(lián)盟結(jié)構(gòu)的算法進行了改進，主要解決存在大量重復(fù)子問題計算的問題；Rahwan等[32]提出了IDP(improved dynamitic programming)算法；張新良等[33]在2007年提出了一種快速動態(tài)生成 (search of coalition structure,SCS) 算法，主要降低搜索次數(shù)。本文中，DP算法主要基于定理3。

使用定理3進行動態(tài)規(guī)劃，先計算只有一個Agent的聯(lián)盟，接著迭代具有2個Agent的聯(lián)盟，然后是具有3個Agent的聯(lián)盟，一直迭代到具有n個Agent的聯(lián)盟。對于每個聯(lián)盟C都需要使用式(1)計算。從式(1)中易知：當 |C |≠1 時，需要分別計算) 的值，然后將兩個值進行比較，得到具有較大社會福利的聯(lián)盟。在此過程中，將所產(chǎn)生的暫存結(jié)果保存在變量 t ( C ) 中。

通過上述操作，計算出來的最大 v ( C ) 就是我們最終要求的 V ( CS?)。 計算 C S?的迭代過程具體操作如例2所示。

例2 令數(shù)據(jù)集 N ={a1,a2,a3,a4}，假設(shè)特征函數(shù)為

表1表示算法的具體運算過程。由表1知，t(N)=({a1,a2},{a3,a4})， 能夠?qū)分裂成 { a1,a2} 和{a3,a4}， 而 t ( { a3,a4})={{a3,a4}}， 這 是 因 為 { a1,a2} 分裂成 { a1}、{a2} 后 的社會福利比較大， { a3,a4} 不需要進行分裂。所以 C S?={{a1},{a2},{a3,a4}}。

表 1 4個Agent動態(tài)規(guī)劃算法Table 1 The dynamic programming algorithm for 4 Agents

定理4 給定一組Agent集，使用動態(tài)規(guī)劃算法求得最優(yōu)聯(lián)盟結(jié)構(gòu)的時間復(fù)雜度 O ( 3n)。

DP算法在該算法的運行過程中實際做了如下幾方面：

1) 評估圖上的運動；

2) 在表t中存儲最優(yōu)結(jié)構(gòu)；

3) 從底部節(jié)點開始向上運動。

5 聯(lián)盟生成求近似最優(yōu)解

Rahwan等[34]將聯(lián)盟配置與Anytime算法進行結(jié)合提出一種聯(lián)盟結(jié)構(gòu)相似最優(yōu)解算法；為Albizuri等[35]基于整數(shù)分區(qū)對聯(lián)盟結(jié)構(gòu)進行推廣從而對聯(lián)盟配置(coalition configuration)進行了定義。

5.1 基本定義

在進行求解的過程中，設(shè) C Ls∈2n，其中s ∈ { 1,2,···,k} 是 聯(lián)盟列表， C Li是 聯(lián)盟列表 C Ls的集合(見表2)。設(shè) G1,G2,···,G?cs∈ ?cs是所有的存在的唯一配置的結(jié)合(即不存在具有相同聯(lián)盟大小的兩個元素)，令 F :?CS→ 2CS是一個函數(shù)，按照提前設(shè)定好的配置返回所有的聯(lián)盟結(jié)構(gòu)。 N 表 示一個列表，里面的每一個元素表示一組具有相同配置的聯(lián)盟結(jié)構(gòu)。形式上， N 定義為：N ={F(G1),F(G2),···,F(G|?CS|)}，N1,N2,···,N?CS∈ N 表 示N中的每個元素(見表3)。

表 2 4個Agent聯(lián)盟列表Table 2 The coalition list of 4 Agents

表 3 4個Agent配置表及具體聯(lián)盟表示Table 3 The configuration table and specific coalition representation of 4 Agents

5.2 具體實現(xiàn)

算法實現(xiàn)分為3個部分：1)預(yù)處理操作；2)構(gòu)造和選擇合適的配置；3)搜索元素。

1) 預(yù)處理操作

預(yù)處理的主要目的是計算 C Ls的 最大值maxs和平均值 a v gs并返回計算值，同時將當前搜索社會福利最大的聯(lián)盟結(jié)構(gòu)返回記為 C S′。此過程中，主要進行2種操作，分別是評估互補大小和包含配置為 { 1 , 2,···,i} 的聯(lián)盟。

①評估互補大小：將 C Ls和 C Ln-s稱為互補的，如 C L3和 C L1。在此過程中需要計算由互補中的聯(lián)盟組成的不相交的聯(lián)盟結(jié)構(gòu)的值。

②包含配置為 {1 , 2,···,i} 的 聯(lián)盟：計算G={1,2,···,i}配置的聯(lián)盟結(jié)構(gòu)的值。

經(jīng)過上述兩個操作搜索聯(lián)盟結(jié)構(gòu)，可以搜索空間的一部分(隨著n的增加而減小)。表4表示的是8個Agent搜索結(jié)果，其中配置 G ={8}，G={4,4}，G={3,5}，G={2,6}，G={1,7}， G ={1,1,6}，G={1,1,1,5} ， G={1,1,1,1,1,3} ， G={1,1,1,1,1,3}，G={1,1,1,1,1,1,2}，G={1,1,1,1,1,1,1,1}是在預(yù)處理操作中需要將被搜索的配置。

2) 構(gòu)造和選擇合適的配置

表 4 8個Agent配置表Table 4 The configuration table of 8 Agents

在搜索過程中，進行剪枝操作主要目的是減少搜索空間。 G′為 搜索完后找到可能存在最優(yōu)聯(lián)盟結(jié)構(gòu)的配置。

①構(gòu)造獨一無二的配置：保證所有的配置的集合等于所有Agent可能產(chǎn)生的整數(shù)分區(qū)。例如，有5個Agent，可能存在的整數(shù)分區(qū)的配置G 為 {5}，{4, 1}，{3, 2}，{3, 1, 1}，{2, 2, 1}，{2, 1, 1,1}和{1, 1, 1, 1, 1}。計算每個配置G對應(yīng)于F(G)的上界 U BG和 平均值 A v gG。 將 V ( CS′) 和UBG′β 進 行比較，如果 G′中所有的配置都滿足前者大于后者，那么該解即為最優(yōu)解。否則，進行②操作。

3) 搜索元素

搜索過程的關(guān)鍵在于構(gòu)建聯(lián)盟結(jié)構(gòu)。在該算法中，構(gòu)建聯(lián)盟結(jié)構(gòu)的主要問題是，在執(zhí)行時會進行重復(fù)操作，從而形成冗余和無效的聯(lián)盟結(jié)構(gòu)。

①避免重疊的聯(lián)盟結(jié)構(gòu)：重疊的聯(lián)盟結(jié)構(gòu)是 { { a1,a2}{a2,a3}} 這樣。使用快速索引技術(shù)[36]進行解決。

6 約束條件下聯(lián)盟生成求最優(yōu)解

Frankovi等[37]將關(guān)注點從所有Agent之間的聯(lián)系轉(zhuǎn)移到只關(guān)注給定Agent之間建立最優(yōu)的聯(lián)盟。Greco等[18]經(jīng)過進一步研究，提出了一種新的聯(lián)盟結(jié)構(gòu)生成方式——約束聯(lián)盟結(jié)構(gòu)，即在生成聯(lián)盟的過程對聯(lián)盟添加約束。

6.1 約束聯(lián)盟的基礎(chǔ)

在進行約束聯(lián)盟結(jié)構(gòu)形成的過程中，主要是定義在一對 ＜ N ,v> 上 的， ＜ N,v> 稱為聯(lián)盟博弈，其中N = ( a1,a2,···,an) 是Agent集，v是評估函數(shù)。

例3 假設(shè)一個聯(lián)盟博弈為 ＜ N,v>，其中N=(a1,a2,a3)，評估函數(shù)為

易知，最優(yōu)聯(lián)盟結(jié)構(gòu)是 { a1,a2,a3} 和 { { a1,a2},{a3}}，這是因為 v ( { a1,a2})+v({a3})=v({a1,a2,a3})=3。

假設(shè)在聯(lián)盟博弈 ＜ N,v> 中，Agent集上定義一個無向圖G，G稱為交互圖。聯(lián)盟C是可行的，當且僅當C在G的子圖上是連通的。

6.2 約束聯(lián)盟結(jié)構(gòu)生成

令 Γ = ＜N,v> 是 聯(lián)盟博弈， D =(N,E) 是聯(lián)盟博弈上的一個交互圖，其中圖中的交點是N中的Agent，邊是節(jié)點集，設(shè) S ∈N 是一個可能為空的Agent集，稱為樞紐Agent。規(guī)定任意一個可行聯(lián)盟結(jié)構(gòu)中不允許存在兩個及其以上的樞紐Agent。α,β : S ■→ R 是 兩個評估函數(shù)，而 x , y∈ R 是兩個實數(shù)，則 σ = ＜ D ,S,α,β,x,y> 是 ＜ N ,v> 的評估結(jié)構(gòu)。

例4 給定一個聯(lián)盟博弈 Γ = ＜N,v>，其中N ={a1,a2,···,a7}。 評 估 結(jié) 構(gòu) 為 σ = (D,{a1,a2},α,β,x,y)，其中圖D如圖4所示。

圖 4 7個Agent交互圖Fig. 4 The interactive graph of 7 Agents

圖4中 C1={a1,a3}， C2={a4,a5,a6} 是2個可行聯(lián)盟，而 { a1,a2} 和 { a5,a7} 是2個不可行聯(lián)盟，前者是因為聯(lián)盟中2個Agent都是樞紐Agent，后者則是因為聯(lián)盟不是圖4的子圖。

如果C是可行聯(lián)盟結(jié)構(gòu)，將函數(shù)α、β和實數(shù)x、y 通過式({2)定義成評估函數(shù)v的映射 v a lσ。

例5 假設(shè)圖4中，估值函數(shù)為v，C是一個可行聯(lián)盟，則 v ( C ) 被定義為由C所覆蓋的邊的權(quán)值的總和，即 ∑假設(shè)函數(shù) 分別為 ，

，而實數(shù) x=0，y=-12，則 +。

6.3 邊際貢獻網(wǎng)上聯(lián)盟生成

α、β α:{a1,a2}→{1} β:{a1,a2}→ {0} valσ(C1)=1×v(C1)0=1,valσ(C2)=0×v(C2)-12=-12

邊際貢獻網(wǎng)[38]在過去的幾年里收到了相當大的關(guān)注。邊際貢獻網(wǎng)(marginal contribution network, MC-net)是包含一系列代表Agent的布爾變量的規(guī)則，每個規(guī)則的形式為 { p a ttern}→value，其中pattern可以包含正面的連接或負面的連接，value是與此pattern相關(guān)的附加貢獻。

例6 給定一個聯(lián)盟博弈 Γ =＜N,v>，其中N={a1,a2,···,a5}，v({a1,a2})=v({a2,a3})=v({a1,a3})=2；?i∈ { 1,2,···,5},v({ai})=0；v({a1,a2,a3})=5；?C ? { a1,a2,a3} ， v(C∪{a4})=v(C∪{a5})=v(C)=v(C∪{a4,a5})；根據(jù)邊際貢獻網(wǎng)，給定規(guī)則為

h≥0 Γ=＜N，v>v D σ= ＜ D,S,α,β,x,y> (Γ,σ)

定理5 令 是一個固定自然數(shù)，是一個博弈，其中 是獨立于不相交成員的評估函數(shù)，交互圖 所構(gòu)成的樹的高大于h。令，則 的聯(lián)盟結(jié)構(gòu)生成的值可以在多項式時間內(nèi)解決。

約束滿足問題具有較強的靈活性，能夠進行推廣解決文獻[32]中提到的約束問題。

7 結(jié)束語

聯(lián)盟結(jié)構(gòu)生成問題中如何能夠更快更精確地進行優(yōu)化整體性能對于研究人員一直都是挑戰(zhàn)。本文針對這一問題進行了全面的綜述：1)搜索空間的不同表示；2)動態(tài)規(guī)劃算法的時候來解決這個問題；3)使用近似最優(yōu)來代替最優(yōu)解；4)使用評估的方法，主要是添加了約束條件。所有的這些結(jié)構(gòu)都是以一種獨立的方式展示出來的。

但是，在現(xiàn)有聯(lián)盟生成的研究中，大多數(shù)是以Agent之間具有相同的協(xié)商資源和態(tài)度為前提的，只考慮了協(xié)商中的相同性，卻忽略了協(xié)商中的異質(zhì)性。在未來的工作中，可以考慮將協(xié)商的異質(zhì)性與約束聯(lián)盟中的評估結(jié)構(gòu)相結(jié)合。

同時，在約束K-means聚類算法的啟發(fā)下，可以將一般形式的無法連接的約束進行合理操作后有理性地加入到評估結(jié)構(gòu)中。另外，可以進行擴展，將允許聯(lián)盟生成的概率使用先驗知識進行檢驗或者將Agent之間的動態(tài)相互信任添加到聯(lián)盟生成的過程中。