童向榮 任子儀

(煙臺大學(xué)計算機與控制工程學(xué)院 煙臺 264005)

1 引言

5G網(wǎng)絡(luò)切片、導(dǎo)頻分配和云計算等資源分配問題是研究的熱點，但是該問題通常是NP難的，近年來，聯(lián)盟和可信聯(lián)盟逐漸被應(yīng)用到資源分配領(lǐng)域，智慧等人[1]用聯(lián)盟分裂形式的思想，即隨機劃分的方法提出了一種聯(lián)合用戶分組和聯(lián)盟博弈的動態(tài)導(dǎo)頻分配方案，用戶被分成若干個互不相交的子聯(lián)盟。聯(lián)盟形成(Coalition Formation, CF)是多智能體系統(tǒng)(Multi-智能體 System, MAS)的重要研究內(nèi)容之一，通過對智能體集合進(jìn)行劃分得到聯(lián)盟結(jié)構(gòu)(Coalition Structure, CS)，其中包含若干不相交的集合，即聯(lián)盟(Coalition, C)。CF的過程通常以最大化社會福利和個體效用為目標(biāo)[2]，稱為聯(lián)盟結(jié)構(gòu)生成(Coalition Structure Generation, CSG)。合作博弈論是CF研究的基礎(chǔ)，例如特征函數(shù)博弈[3]、不可轉(zhuǎn)移效用的博弈[4]和享樂博弈[5]。聯(lián)盟博弈論一般假設(shè)特征函數(shù)具有超加性，即生成的主聯(lián)盟是最優(yōu)的。核[6]、Shapley值[7]為聯(lián)盟博弈提供了劃分收益的解決方案。最近，研究人員考慮特征函數(shù)不是超加性的情況，有的模型使用對稱可加性可分離特征博弈[8]。

CSG存在著諸多約束[9]，如通常情況下信任是合作的基礎(chǔ)，信任是一方對另一方實現(xiàn)承諾的主觀評估。信任程度越高越容易形成長期穩(wěn)定的合作關(guān)系，而信任的傳遞性可以促進(jìn)不熟悉的智能體之間的合作關(guān)系。信任關(guān)系對最終效用有直接的影響，因而，將信任信息融入到效用中是合理的。王海艷等人[10]提出了基于可信聯(lián)盟的服務(wù)推薦方法，將信任關(guān)系融入相似度計算；Sless等人[11]將社交關(guān)系引入聯(lián)盟形成，負(fù)值社交關(guān)系表示合作很難成功。童向榮等人[12]和Wang等人[13]對信任傳遞的特性進(jìn)行了研究。Mao等人[14]提出信任傳遞取最小信任值或信任值相乘的方式，信任聚合取最大信任值或?qū)Χ鄺l路徑信任值進(jìn)行加權(quán)平均。

近年來，研究人員在圖上研究博弈，假設(shè)有向帶權(quán)圖的邊表示智能體之間的關(guān)系。邊收縮方法可以枚舉智能體集的所有可行分區(qū)，Karger[15]應(yīng)用該方法解決Min-Cut問題，但未應(yīng)用在聯(lián)盟形成中。圖割將圖劃分為互不相交的區(qū)域，在同一區(qū)域內(nèi)的特征具有較高的相似性，而不同的區(qū)域內(nèi)的特征則具有明顯的差異性，其原理正是一種劃分。受圖割s-t-cut算法的啟發(fā)，研究了基于信任和效用關(guān)系約束的CSG，在保證智能體理性和聯(lián)盟穩(wěn)定(無塊)的情況下，使用信任和效用關(guān)系對網(wǎng)絡(luò)進(jìn)行切割，從而形成聯(lián)盟。由此，提出了兩種多項式時間的精確算法：信任約束下CSG和信任效用關(guān)系約束下CSG，均能夠求解設(shè)定情況下的最優(yōu)CS。仿真實驗結(jié)果驗證了所提方法的有效性。

本文主要貢獻(xiàn)：(1)將CF的效用關(guān)系擴展為信任和效用關(guān)系，即不僅關(guān)注效用約束，還關(guān)注信任約束，并用信任和效用二元組表示，以此作為CSG的依據(jù)。(2) 在保證智能體個體理性和聯(lián)盟穩(wěn)定(不存在塊)的前提下，用分割信任網(wǎng)絡(luò)的方法，生成有k個聯(lián)盟的穩(wěn)定CS，提出了兩種多項式時間的精確算法。

2 基本定義

傳統(tǒng)的聯(lián)盟形成只基于效用關(guān)系，沒有考慮社交關(guān)系對效用的影響，近年來，學(xué)者們注意到社交關(guān)系對合作成功有必然的影響，因此，信任關(guān)系應(yīng)該與效用關(guān)系一起考慮，這能提高聯(lián)盟形成的效率和速度。

如果CS的智能體可以通過組建一個新聯(lián)盟，在不降低新聯(lián)盟內(nèi)其它智能體收益的前提下，達(dá)到提高自身收益的目的，那么這個新聯(lián)盟將破壞原有的CS，該CS是不穩(wěn)定的。而這個新聯(lián)盟是有更大信任和效用值的聯(lián)盟，稱為塊。

圖1 不同聯(lián)盟結(jié)構(gòu)的效用

圖2 智能體信任網(wǎng)絡(luò)

根據(jù)定義3易知，如果有一個聯(lián)盟是塊，那么CS中的智能體傾向于離開原聯(lián)盟而形成新的聯(lián)盟，這說明塊破壞了聯(lián)盟結(jié)構(gòu)的穩(wěn)定性，因此在滿足超加性的前提下，沒有可能的塊就成為了聯(lián)盟穩(wěn)定的條件。若聯(lián)盟的數(shù)量固定為常數(shù)k，則不允許出現(xiàn)塊，要求智能體集合恰好生成k個聯(lián)盟，當(dāng)k＝2時，分別記為聯(lián)盟s和t，s和t組成新的聯(lián)盟結(jié)構(gòu)。

3 信任傳遞

圖3 2-聯(lián)盟核成員

信任網(wǎng)絡(luò)中，智能體之間能否形成聯(lián)盟與其信任值直接相關(guān)，信任值越大，概率越高，通過歸一化處理后，ai與aj在t時刻能夠形成聯(lián)盟的條件概率記為pij(t)。

圖4 信任網(wǎng)絡(luò)

可以證明h步信任生成概率，證明：根據(jù)邊緣分布

4 MT-s-t-cut和MTU-s-t-cut算法

定義5k-切割:Cut2(C1,C2)表示將信任網(wǎng)絡(luò)G根據(jù)信任值切割成互不相交的兩部分，每部分組成一個聯(lián)盟，稱為2-切割。Cutk(C1,C2,···,Ck)表示將信任網(wǎng)絡(luò)G切割成互不相交的k個部分，組成k個聯(lián)盟，稱為k-切割。

4.1 MT-s-t-cut算法

表1 算法1：MT-s-t-cut算法

4.2 MTU-s-t-cut算法

除了考慮信任對于社會福利的影響，還應(yīng)該綜合考慮信任和效用關(guān)系。給定信任網(wǎng)絡(luò)G＝＜A,E,ω,ρ ＞，cf(p)為尋找路徑的殘余容量 (路徑p中最小的切割對象，此處為信任效用關(guān)系)。根據(jù)G的信任關(guān)系和效用關(guān)系計算Pij和?ij。然后計算智能體之間的信任和效用關(guān)系fρ,ω(ai,aj)。循環(huán)智能體點，根據(jù)fρ,ω(ai,aj)的值進(jìn)行圖割，并輸出最優(yōu)社會福利的CS及其最優(yōu)社會福利值。具體步驟見表2的算法2。

表2 算法2：MTU-s-t-cut算法

算法2的詳細(xì)描述：第(1)步，算法初始化。根據(jù)式(1)–式(4)計算得到聯(lián)盟形成的生成概率Pij與智能體之間的效用值?ij；第(2)步，將第(1)步計算結(jié)果應(yīng)用于信任效用關(guān)系函數(shù)的計算，綜合考慮信任和效用關(guān)系在聯(lián)盟形成過程中的影響；第(3)步，根據(jù)信任效用關(guān)系將智能體集劃分為互不相交的兩部分，即兩個聯(lián)盟，并輸出最優(yōu)社會福利的CS及其最優(yōu)社會福利。

5 實驗

仿真實驗驗證了智能體數(shù)量、算法運行時間與最終得到的社會福利之間的關(guān)系，并與幾種典型算法進(jìn)行了對比，驗證了所提算法的效率。

5.1 實驗環(huán)境與數(shù)據(jù)

計算機的系統(tǒng)環(huán)境是Windows7，64位操作系統(tǒng)，8 GB內(nèi)存，3.2 GHz主頻，i5-6500英特爾處理器。軟件設(shè)計采用Java程序語言，Eclipse運行環(huán)境。實驗數(shù)據(jù)規(guī)模即為智能體數(shù)量，隨機生成從1個到25個智能體，實驗數(shù)據(jù)滿足超加性，智能體數(shù)量最大設(shè)置為25個，25個智能體的聯(lián)盟結(jié)構(gòu)生成，如果使用精確算法，DP和ODP-IP需要的時間是325，是指數(shù)級的，本文提出的算法的復(fù)雜度是2 53，是多項式級的。

實驗所用方法為求解s-t-cut的經(jīng)典算法最大流FF(Ford-Fulkerson)算法，圖的最小cut問題可以轉(zhuǎn)換為最大流問題，即最小割問題和最大流問題是等價的。

5.2 對比算法

本文所提算法與以下幾種算法進(jìn)行對比。

(1) 動態(tài)規(guī)劃法(Dynamic Programming,DP)：Yeh[17]提出使用DP方法用于解決完整的集合劃分問題，進(jìn)而求解CSG問題，通過DP所求得的聯(lián)盟結(jié)構(gòu)為最優(yōu)聯(lián)盟結(jié)構(gòu)。

(2) ODP-IP算法：Michalak等人[18]在2015年結(jié)合任意時間算法和DP方法開發(fā)的一種稱為ODPIP的算法。

(3) MT-s-t-cut算法：本文提出的第1個算法。

(4) MTU-s-t-cut算法：本文提出的第2個算法。

(5) CSG-UCT算法：Wu等人[19]在2020年基于蒙特卡羅樹的搜索方法。

5.3 評價指標(biāo)

將效用和時間作為評估CSG的指標(biāo)。一方面研究信任對聯(lián)盟效用的影響，另一方面研究智能體的基|A|對社會福利和算法運行時間的影響。

5.4 參數(shù)設(shè)置與實驗結(jié)果

0＜ρ ＜0.5為低信任關(guān)系，0.5≤ρ ＜1為高信任關(guān)系，而高低信任為同時存在高、低信任關(guān)系。

5.4.1 |A|對社會福利的影響

如圖5所示，橫坐標(biāo)表示智能體數(shù)量，縱坐標(biāo)表示生成的聯(lián)盟結(jié)構(gòu)社會福利。

通常情況下，社會福利隨著智能體數(shù)量增加而增加。分析圖5易知，隨著|A|的數(shù)量增多，MT-st-cut算法、MTU-s-t-cut算法和DP算法的社會福利均增加，并且增幅基本一致。這說明在CSG過程中，智能體具有個體理性，即符合超加性原則。

圖5 |A|對社會福利的影響

5.4.2 |A|對運行時間的影響

通過信任網(wǎng)絡(luò)，分別對不同數(shù)量的智能體集進(jìn)行CSG，記錄CSG所需的時間。圖6表示兩種算法的智能體數(shù)量與運行時間的關(guān)系，圖7表示MT-s-tcut算法與MTU-s-t-cut算法的運行時間對比，3個圖的橫坐標(biāo)表示CSG的智能體數(shù)量，縱坐標(biāo)為算法運行時間，單位為ms。

分析圖6的易知，隨著|A|的增大，兩種算法的運行時間均相應(yīng)增加，但不受信任關(guān)系的影響。觀察圖7，易知MTU-s-t-cut的算法運行時間一直比MT-s-t-cut算法的運行時間短。原因在于，使用信任效用函數(shù)后，智能體間的非對稱信任效用關(guān)系被轉(zhuǎn)換為對稱關(guān)系，節(jié)省了最后一步生成聯(lián)盟的時間。

圖6 兩種算法的智能體數(shù)量與運行時間的關(guān)系

圖7 算法運行時間對比

5.4.3 運行時間對比

由圖8可知，隨著智能體數(shù)量的增加，DP算法和ODP-IP算法的工作量增加量要遠(yuǎn)大于MT-s-t-cut算法和MTU-s-t-cut算法。

圖8 工作量對比

運行時間如圖9所示，橫坐標(biāo)表示智能體數(shù)量，縱坐標(biāo)表示運行時間，單位是ms。如圖9所示，所提兩種算法的運行時間遠(yuǎn)小于DP算法與ODP-IP算法，并且隨智能體數(shù)量的增加效果越明顯。

圖9 前4種算法時間對比

Wu等人[19]在2020年基于蒙特卡羅樹的搜索方法對聯(lián)盟結(jié)構(gòu)圖進(jìn)行采樣迭代展開搜索樹，提出一種可擴展的Anytime聯(lián)盟形成方法。CSG-UCT算法找到最優(yōu)解的時間取決于實驗的迭代次數(shù)，每次迭代都需要進(jìn)行一次蒙特卡羅樹搜索過程，在尋找最優(yōu)解的過程中需要進(jìn)行大量的迭代。當(dāng)智能體數(shù)量越多時，需要的時間越多。CSG-UCT算法與MTU-s-t-cut算法時間對比如圖10。隨著智能體數(shù)量的增多，MTU-s-t-cut算法運行時間遠(yuǎn)少于CSGUCT算法，智能體數(shù)量越多，運行效果越明顯。

圖10 與CSG-UCT算法對比

6 結(jié)束語

本文研究了基于信任和效用關(guān)系的CSG問題，給出了兩個多項式時間算法計算最優(yōu)聯(lián)盟結(jié)構(gòu)。根據(jù)信任的傳遞性進(jìn)行信任和效用的傳遞；然后對傳遞后的信任網(wǎng)絡(luò)進(jìn)行圖割，得到最優(yōu)社會福利的聯(lián)盟結(jié)構(gòu)。最后通過仿真實驗，驗證了信任關(guān)系能夠影響CSG的過程，并對所得聯(lián)盟結(jié)構(gòu)的社會福利造成影響。隨智能體數(shù)量的增加，算法的運行時間相應(yīng)增加，但遠(yuǎn)小于DP算法和ODP-IP算法的運行時間。聯(lián)盟結(jié)構(gòu)中聯(lián)盟核問題及其穩(wěn)定性進(jìn)行分析會是未來的研究重點。