單調(diào)重疊聯(lián)盟下的最優(yōu)聯(lián)盟結(jié)構(gòu)生成

郭志鵬，劉驚雷

（煙臺(tái)大學(xué)計(jì)算機(jī)與控制工程學(xué)院，山東煙臺(tái) 264005）

0 引言

agent 理論和技術(shù)研究起源于分布式人工智能，它是人工智能的一個(gè)非常重要的研究方向。隨著計(jì)算機(jī)科學(xué)和技術(shù)的發(fā)展，agent 理論和技術(shù)趨于成熟，相關(guān)課題逐漸脫離分布式人工智能，它可以應(yīng)對(duì)計(jì)算機(jī)支持的多種應(yīng)用需求，如協(xié)同工作［1］、虛擬企業(yè)［2］、應(yīng)急資源分配［3］、無線傳感器網(wǎng)［4］等。多agent 系統(tǒng)（Multi-Agent System，MAS）作為agent 理論的核心內(nèi)容為一些獨(dú)立的agent提供了一種協(xié)作模式，這種協(xié)作模式可以使這些agent 在一定的時(shí)間內(nèi)自發(fā)地形成一個(gè)針對(duì)特定任務(wù)的協(xié)作團(tuán)隊(duì)，形成的團(tuán)隊(duì)形式一般被稱為聯(lián)盟［5-6］。因此，聯(lián)盟形成（Coalition Formation，CF）是一組agent 為了完成一系列任務(wù)而進(jìn)行資源共享和分配的過程，它可以提高單個(gè)agent 效益并且有效地完成任務(wù)。如何在agent 之間形成高效的聯(lián)盟是MAS和人工智能一個(gè)重要的研究課題。

一般來說，CF 的研究是圍繞著聯(lián)盟結(jié)構(gòu)生成（Coalition Structure Generation，CSG）問題展開的。世界上一些權(quán)威學(xué)者對(duì)CSG 問題進(jìn)行了深入的研究，并提出了自己一些獨(dú)特的見解［7-9］。他們的大部分工作是圍繞非重疊聯(lián)盟展開的，即在MAS 中，agent 活動(dòng)范圍內(nèi)只有一個(gè)聯(lián)盟。此外，當(dāng)聯(lián)盟形成時(shí)，所有加入聯(lián)盟的agent 即使擁有足夠的資源，也不能加入其他聯(lián)盟。然而，這種情況是不合理的。首先MAS 內(nèi)會(huì)出現(xiàn)資源浪費(fèi)的情況，其次擁有豐富資源的agent為了獲取更多的利益，往往會(huì)參與多個(gè)聯(lián)盟。例如，投資公司擁有豐富的投資資源，但他們往往不會(huì)把所有的資源都投資在一個(gè)項(xiàng)目上。相反，他們把資源分成幾部分用于投資，這樣不僅可以獲得更多的利潤(rùn)，而且可以有效降低投資失敗風(fēng)險(xiǎn)。重疊聯(lián)盟的概念由此產(chǎn)生，即agent 活動(dòng)的范圍可以是多個(gè)聯(lián)盟，它們通過劃分各自的資源參與到多個(gè)聯(lián)盟中來完成不同的任務(wù)。這種方式不僅可以提高系統(tǒng)資源的利用率，還可以提高任務(wù)完成的效率和整個(gè)系統(tǒng)的效益。因此，重疊聯(lián)盟結(jié)構(gòu)生成（Overlapping Coalition Structure Generation，OCSG）問題吸引了越來越多研究人員的目光。

本文研究的主要內(nèi)容是重疊聯(lián)盟的合作博弈框架（Framework of cooperative games with Overlapping Coalitions，OCF games）中的OCSG 問題，該問題的搜索空間的大小通常與agent 的數(shù)量呈指數(shù)關(guān)系。例如，為了表示一個(gè)擁有n個(gè)agent 的傳統(tǒng)博弈，就需要為2n-1 種玩家子集（聯(lián)盟）分配一個(gè)數(shù)值。這個(gè)問題在OCF 博弈中更加突出，博弈不僅僅需要為每個(gè)聯(lián)盟分配數(shù)值，還需要表示agent的資源分配情況。因此，任何需要知道所有聯(lián)盟值的算法都不可能在多項(xiàng)式時(shí)間內(nèi)運(yùn)行，OCSG 問題一般是NP-hard。為了解決OCSG 的計(jì)算困難問題，首先要使用一種簡(jiǎn)單有效的模型來限制重疊聯(lián)盟結(jié)構(gòu)生成的規(guī)模，然后利用博弈中的某些特性實(shí)現(xiàn)OCSG 問題的剪枝搜索，這是解決OCSG問題的一般步驟。

在此背景下，主要貢獻(xiàn)如下：

1）在2.2 節(jié)中引入了一種帶有聯(lián)盟數(shù)量k約束的OCF 博弈（OCF games with number of coalitionkconstraints，kOCF games）模型。這種博弈不僅可以約束一個(gè)agent 如何很好地分割資源，而且可以限制重疊聯(lián)盟結(jié)構(gòu)生成的規(guī)模。

2）為了解決OCSG 計(jì)算困難問題，引入一種相似度量來度量?jī)蓚€(gè)聯(lián)盟結(jié)構(gòu)的相似程度。此外，基于相似度量定義9闡述了kOCF 博弈的單調(diào)性。該性質(zhì)意味著一個(gè)聯(lián)盟結(jié)構(gòu)越相似于最優(yōu)聯(lián)盟結(jié)構(gòu)，它的聯(lián)盟值就越大。

3）對(duì)于一個(gè)具有單調(diào)性的kOCF 博弈，設(shè)計(jì)了聯(lián)盟約束貪心（Coalition Constraints Greed，CCG）算法來解決OCSG 問題。在定理3 中證明了該算法時(shí)間復(fù)雜度至多為O(n2k+1)，并且是固定參數(shù)可解的。

4）通過實(shí)驗(yàn)分析了agent 個(gè)數(shù)、最大聯(lián)盟數(shù)量k值和不同聯(lián)盟值分布對(duì)算法性能的影響。實(shí)驗(yàn)結(jié)果驗(yàn)證了當(dāng)k值被常數(shù)約束時(shí)CCG 算法的搜索次數(shù)隨著agent 個(gè)數(shù)基本呈線性增長(zhǎng)這一優(yōu)點(diǎn)。通過與Zick 等［10］提出的算法在算法類型、約束條件等多方面上進(jìn)行了對(duì)比，說明了CCG 算法擁有更好的適用性。

1 相關(guān)工作

本章簡(jiǎn)要介紹了聯(lián)盟結(jié)構(gòu)生成和重疊聯(lián)盟形成的相關(guān)工作。目前的主要工作是在這兩者的基礎(chǔ)上進(jìn)行和擴(kuò)展的。

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

聯(lián)盟結(jié)構(gòu)生成中的難點(diǎn)就是如何在龐大的搜索空間中找到最優(yōu)聯(lián)盟結(jié)構(gòu)，使得該聯(lián)盟結(jié)構(gòu)的聯(lián)盟值是最大的［11］。目前國(guó)內(nèi)外關(guān)于CSG 的研究已取得了一定成功，專家們一般是利用博弈中某些特性來設(shè)計(jì)算法尋找最優(yōu)聯(lián)盟結(jié)構(gòu)，并且分析了其計(jì)算的復(fù)雜性。

計(jì)算最優(yōu)聯(lián)盟結(jié)構(gòu)的相關(guān)問題在人工智能文獻(xiàn)中得到了廣泛關(guān)注，其中包括Sandholm 等［12］、Larson 等［13］的重要論文。動(dòng)態(tài)規(guī)劃算法是解決這一問題的最早算法之一。針對(duì)CSG問題，Yeh［14］提出了第一個(gè)動(dòng)態(tài)規(guī)劃算法；根據(jù)聯(lián)盟間的同構(gòu)關(guān)系，張新良等［15］提出了一種快速動(dòng)態(tài)生成算法，算法首先對(duì)聯(lián)盟結(jié)構(gòu)圖進(jìn)行剪枝，然后再利用動(dòng)態(tài)規(guī)劃方法搜索最優(yōu)聯(lián)盟結(jié)構(gòu)。

隨著agent 個(gè)數(shù)不斷地增加，CSG 問題搜索空間爆炸式增長(zhǎng)［16］。任意時(shí)間算法意味著解的質(zhì)量隨計(jì)算時(shí)間的增加而單調(diào)增加，比非任意時(shí)間算法具有更好的實(shí)際應(yīng)用價(jià)值。Sandholm 等［12］通過將搜索空間劃分成不相交的詳盡的子空間，并保證在一定約束下找到一個(gè)有保障的目前最優(yōu)解，提出了最壞保證算法；Rahwan 等［17-18］將動(dòng)態(tài)規(guī)劃方法與任意時(shí)間方法相結(jié)合，提出了改進(jìn)動(dòng)態(tài)規(guī)劃等算法。

有一些特殊的博弈，agent 之間或者agent 與聯(lián)盟之間有一種特殊的關(guān)系。例如，Greco等［19］研究了加權(quán)匹配和加權(quán)分配博弈，其中的聯(lián)盟值由圖（可能是加權(quán)圖）上匹配問題的最優(yōu)值決定。在許多現(xiàn)實(shí)的情況下，聯(lián)盟值的大小可能會(huì)受到其他agent 聯(lián)盟形成的影響。為了模擬這種情況，Lucas 等［20］提出了配分函數(shù)博弈（Partition Function Games，PFGs）。Rahwan 等［21］在PFGs 模型的基礎(chǔ)上，引入了外部性的性質(zhì)，并設(shè)計(jì)了相應(yīng)的算法；Fatima 等［8］考慮了帶有玩家序列的特殊博弈，并引入了值函數(shù)的單調(diào)性性質(zhì)，設(shè)計(jì)了一種貪心算法在多項(xiàng)式時(shí)間內(nèi)解決了CSG問題。

1.2 重疊聯(lián)盟形成

1996 年，Shehory 和Kraus 在人工智能會(huì)議上首次提出了重疊聯(lián)盟形成的概念，但他們只是簡(jiǎn)單地假設(shè)任務(wù)是串行的，并沒有解決重疊聯(lián)盟的資源沖突問題；Chalkiadakis 等［22］提出了OCF 博弈模型，該模型可用于agent 分配資源的場(chǎng)景建模，并通過元組的形式有效地表示出了重疊聯(lián)盟博弈。Zick等［10］基于OCF 博弈提出了離散重疊聯(lián)盟形成（discrete Overlapping Coalition Formation，dOCF）博弈概念，將agent 資源分配描述進(jìn)行了量化和離散化，使重疊聯(lián)盟的表示和計(jì)算更加方便。

重疊聯(lián)盟結(jié)構(gòu)生成是重疊聯(lián)盟形成重要研究?jī)?nèi)容之一，與CSG 問題不同的是它涉及到agent 之間可以形成重疊聯(lián)盟的情景。專家們通過對(duì)博弈增加一些約束或者利用博弈中存在的特殊性質(zhì)來解決OCSG 問題。Zick 等［10］在dOCF 博弈的基礎(chǔ)上增加了通信圖約束解決了OCSG 問題，并將其結(jié)果推廣到通信圖接近于樹，即有界樹寬的情況。魏冰茹等［23］構(gòu)建了以聯(lián)盟結(jié)構(gòu)成本最小化為優(yōu)化目標(biāo)的OCSG 數(shù)學(xué)模型，并提出了一種基于動(dòng)態(tài)規(guī)劃的OCSG算法。

2 相關(guān)定義

2.1 重疊聯(lián)盟和聯(lián)盟結(jié)構(gòu)

在本節(jié)中，首先說明了使用的符號(hào)，然后簡(jiǎn)要介紹OCF博弈和聯(lián)盟結(jié)構(gòu)的基本概念。特別地，使用大寫字母表示集合，用黑體字母表示向量。表1為使用的基本符號(hào)。

表1 符號(hào)描述Tab.1 Symbol description

傳統(tǒng)合作博弈G可以用元組來表示，其中N={1，2，…，n}是玩家（或agent）集合，u：2N→R+是一個(gè)可以為玩家集合子集S?N分配一個(gè)實(shí)值（聯(lián)盟值）的函數(shù)，子集S又被稱為聯(lián)盟。傳統(tǒng)合作博弈中的聯(lián)盟結(jié)構(gòu)是一組agent 的劃分，用Sc={S1，S2，…，Sm}來表示它。傳統(tǒng)合作博弈具有以下兩個(gè)性質(zhì)：

1）對(duì)于1 ≤j≤m

2）對(duì)于任意j≠k，Sj∩Sk=?。

在傳統(tǒng)的聯(lián)盟中，每個(gè)agent只能參與一個(gè)聯(lián)盟。雖然在部分情景中這是一個(gè)有效的假設(shè)，但現(xiàn)實(shí)中資源豐富的agent應(yīng)該參與多個(gè)聯(lián)盟，并將其資源分配給多個(gè)任務(wù)，形成重疊的聯(lián)盟來獲取更多的利潤(rùn)。以此為背景，Chalkiadakis 等［22］提出了OCF博弈模型，具體定義如下。

定義1 OCF博弈取消了每個(gè)agent只能參與一個(gè)聯(lián)盟的限制。一個(gè)OCF博弈也可以用一個(gè)元組來表示，其中N={1，2，…，n}是玩家集合，u：[0，1]n→R+是特征函數(shù)。

玩家集合N中的一個(gè)部分聯(lián)盟表示為向量c=(c1，c2…，cn)∈[0，1]n，為了簡(jiǎn)潔，當(dāng)談到這樣的聯(lián)盟經(jīng)常會(huì)省略限定詞“部分”，稱c是一個(gè)聯(lián)盟。c的第i個(gè)坐標(biāo)分量表示玩家i貢獻(xiàn)給聯(lián)盟c的資源比例。與傳統(tǒng)博弈不同是，v是一個(gè)特征函數(shù)，它定義在形式為[0，1]n的所有向量上，并為每個(gè)聯(lián)盟c分配一個(gè)非負(fù)的實(shí)值。在這種情況下，如果想要完全定義一個(gè)OCF 博弈，需要在[0，1]n的每個(gè)實(shí)點(diǎn)上指定特征函數(shù)v的值。由于一個(gè)聯(lián)盟結(jié)構(gòu)可以包含很多聯(lián)盟，在agent數(shù)目比較多的情況下，OCF 博弈很難表示和計(jì)算。為了解決這個(gè)問題，本文引入了OCF博弈的離散化版本。

定義2一個(gè)dOCF 博弈是一個(gè)元組其中N={1，2，…，n}是玩家集合，向量W={W1，W2，…，Wn}表示玩家擁有權(quán)值，W的分量Wi對(duì)應(yīng)著agenti∈N所擁有的權(quán)值，v是特征函數(shù)。

集合WA是agent為單個(gè)任務(wù)貢獻(xiàn)資源的所有可能方法的集合。與傳統(tǒng)的OCF 博弈不同的是，離散化OCF 博弈中是通過權(quán)重向量c∈WA來表示聯(lián)盟。向量c的每個(gè)分量ci表示agenti∈N對(duì)聯(lián)盟c的貢獻(xiàn)值。特別地，特征函數(shù)在dOCF 博弈中被定義為v：WA→R+，接受聯(lián)盟c∈WA作為輸入值，輸出值表示該聯(lián)盟所能產(chǎn)生的收益（聯(lián)盟值）。

定義3OCF 博弈中的聯(lián)盟結(jié)構(gòu)定義為一個(gè)有限的聯(lián)盟列表CS=(c1，c2，…，cm)，其中

特別地，采用上標(biāo)號(hào)形式可以表示不同的聯(lián)盟結(jié)構(gòu)CSi，用|CS|來表示聯(lián)盟結(jié)構(gòu)CS中聯(lián)盟的數(shù)量，并且用v(CS)來表示聯(lián)盟結(jié)構(gòu)CS的收益，即v(CS)=同時(shí)用CSA來表示所有可能由N中成員組成的聯(lián)盟結(jié)構(gòu)集合。

例1 考慮到以下4 個(gè)玩家參與的dOCF 博弈，其中玩家組成重疊聯(lián)盟來完成一組任務(wù)。玩家的權(quán)值表示為W={2，2，1，1}。有以下6種類型的任務(wù)：

1）類型為t12的任務(wù)需要玩家1 和玩家2 一半的資源來完成，收益為4。

2）類型為t14需要玩家1 一半的資源和玩家4 所有的資源來完成，收益為4。

3）類型為t24需要玩家2 一半的資源和玩家4 所有的資源來完成，收益為5。

4）類型為T23需要玩家2 和玩家3 所有的資源來完成，收益為6。

5）類型為T34需要玩家3 和玩家4 所有的資源來完成，收益為3。

6）類型為t1234需要所有玩家都貢獻(xiàn)出一個(gè)資源來完成，收益為9。

考慮聯(lián)盟結(jié)構(gòu)CS1=(c1，c2)和CS2=其中：

根據(jù)特征函數(shù)v的定義，可以得到：

那么很容易可以算出v(CS1)=13。似乎v(CS2)=但事實(shí)上，聯(lián)盟結(jié)構(gòu)CS2是無效的，因?yàn)橥婕? 消耗的權(quán)重超過了它實(shí)際擁有的。

定義4重疊聯(lián)盟結(jié)構(gòu)生成問題是在玩家集合N上找到一個(gè)聯(lián)盟值最大的聯(lián)盟結(jié)構(gòu)，這樣的聯(lián)盟結(jié)構(gòu)被稱為最優(yōu)聯(lián)盟結(jié)構(gòu)，即：

在例1 中，可以很容易地計(jì)算得到CSOPT=CS1。接下來將介紹一種帶有約束了聯(lián)盟結(jié)構(gòu)中聯(lián)盟最大數(shù)量的特殊OCF博弈，也被稱為kOCF博弈。

2.2 kOCF博弈

考慮到一個(gè)有n個(gè)玩家的dOCF 博弈G=并假設(shè)玩家所擁有的最大權(quán)值為Wmax，即Wmax=

這個(gè)博弈G可以用|WA|=≤(Wmax+1)n個(gè)非負(fù)值列表來描述，其中每一個(gè)實(shí)值都代表agent可能形成的聯(lián)盟。對(duì)于所有的i∈N都有Wi≥1，這種表示形式的大小是以玩家數(shù)目n為指數(shù)，而聯(lián)盟結(jié)構(gòu)的數(shù)目往往是更高數(shù)量級(jí)的，這對(duì)于大多數(shù)的應(yīng)用程序是不可接受的。為了解決這個(gè)問題，往往是對(duì)博弈增加某種約束來限制聯(lián)盟結(jié)構(gòu)生成的規(guī)模。在日常工作中，一個(gè)系統(tǒng)被分配的任務(wù)數(shù)量往往是有限的。例如在一個(gè)公司部門中，他們有多個(gè)客戶同時(shí)委派一些項(xiàng)目，那么就需要把員工們劃分成固定數(shù)量的小組，即形成相應(yīng)的聯(lián)盟去完成任務(wù)。換句話說，這是一種約束了聯(lián)盟結(jié)構(gòu)中最大聯(lián)盟數(shù)量的博弈。下面給出滿足約束的kOCF 博弈具體定義。

定義5給定一個(gè)dOCF 博弈G=如果對(duì)于所有的CS∈CSA且|CS|＞k，都有v(CS)=0，那么該博弈被稱為kOCF博弈。

簡(jiǎn)單來說，在kOCF 博弈中所有聯(lián)盟結(jié)構(gòu)CS∈CSA包含的聯(lián)盟數(shù)量都是小于等于k的。對(duì)于聯(lián)盟數(shù)量大于k的聯(lián)盟結(jié)構(gòu)，由于增加了其特征函數(shù)為0 的設(shè)定，意味著agent 通過參與聯(lián)盟合作不會(huì)產(chǎn)生任何利潤(rùn)，同時(shí)也違背了合作博弈的個(gè)體合理性原則，從而約束了聯(lián)盟結(jié)構(gòu)的生成規(guī)模。

在dOCF 博弈中，聯(lián)盟是由向量c表示的，其中向量中的分量ci表示agenti∈N對(duì)聯(lián)盟的貢獻(xiàn)。為了更好地描述下節(jié)中的單調(diào)性性質(zhì)，在kOCF博弈中，定義ci的取值是0或1，即：

那在kOCF 博弈中，聯(lián)盟可以使用玩家編號(hào)的形式來表示，將向量中所有非0 分量的編號(hào)寫入到聯(lián)盟C中。同時(shí)定義一種SFi(j)函數(shù)，它可以遍歷出標(biāo)識(shí)為i的聯(lián)盟結(jié)構(gòu)中擁有玩家編號(hào)j(l＜j≤n)的所有聯(lián)盟編號(hào)。例1 中的聯(lián)盟結(jié)構(gòu)CS1=(c1，c2)就等價(jià)于CS={C1，C2}，其中C1={1，2}，C2={1，2，3，4}，對(duì)應(yīng)有SF(1)={1，2}，即在聯(lián)盟結(jié)構(gòu)CS中玩家1同時(shí)出現(xiàn)在C1和C2中。

命題1 OCSG 問題在kOCF 博弈中是計(jì)算困難的，即使是在聯(lián)盟結(jié)構(gòu)中聯(lián)盟數(shù)量約束k值和玩家最大權(quán)重Wmax值比較較小的情況，該命題依舊成立。

證明 由于聯(lián)盟結(jié)構(gòu)中的聯(lián)盟最大數(shù)量是k，聯(lián)盟結(jié)構(gòu)初始化為CS={?，?，…，?}，即聯(lián)盟結(jié)構(gòu)CS中含有k個(gè)空集。OSCG 問題形成的搜索空間就是一個(gè)組合排列問題。假設(shè)所有集合N={1，2，…，n}中的玩家都擁有相同數(shù)量的資源，即所有玩家的權(quán)值都為Wmax。由于玩家最多貢獻(xiàn)一個(gè)單位的權(quán)值到單個(gè)聯(lián)盟中，玩家資源數(shù)量較多、形成聯(lián)盟數(shù)量較小的博弈研究意義較小，所以k值應(yīng)該大于Wmax。那么對(duì)于任意一個(gè)玩家，有最多Wmax個(gè)該玩家編號(hào)插入到空集中形成聯(lián)盟，插入的所有可能性最多有種。那么對(duì)于N中的所有玩家，OCSG 問題的搜索空間大小為是n的指數(shù)級(jí)，所以是計(jì)算困難的。

為了解決kOCF 博弈中的OCSG 計(jì)算困難問題，需要利用博弈中的一種特殊性質(zhì)稱之為單調(diào)性來簡(jiǎn)化計(jì)算問題，實(shí)現(xiàn)聯(lián)盟結(jié)構(gòu)的減枝搜索。

2.3 相似度量與單調(diào)性

生活中的很多例子可以表明，兩個(gè)事物如果擁有較高的相似度，那么兩者會(huì)存在相同或者相似的性質(zhì)。如果把這種相似性引入到OCSG 問題中，認(rèn)為與最優(yōu)聯(lián)盟結(jié)構(gòu)越相似的聯(lián)盟結(jié)構(gòu)，它的值就越大，這種性質(zhì)被稱為單調(diào)性。在本節(jié)中，首先介紹了玩家序列性質(zhì)，這是單調(diào)性的基礎(chǔ)；然后引入了一種相似度量來度量?jī)蓚€(gè)聯(lián)盟結(jié)構(gòu)的相似程度；最后在kOCF博弈中定義了單調(diào)性性質(zhì)，并證明了滿足這種性質(zhì)的博弈是存在的。

在kOCF 博弈中，聯(lián)盟是一組玩家編號(hào)。聯(lián)盟的最小元素是集合中最小的玩家編號(hào)，且空集的最小元素認(rèn)為是+∞。

例如，對(duì)于聯(lián)盟C1={1，2，3}，聯(lián)盟C1的最小元素是1，即minC1=1。給定一個(gè)kOCF 博弈G=其中非空玩家子集N={1，2，…，n}。在不失一般性的前提下，對(duì)于1 ≤m≤k，假設(shè)聯(lián)盟結(jié)構(gòu)CS={C1，C2，…，Cm}按照以下定義排序。

定義6玩家序列。所有的玩家都應(yīng)參與到聯(lián)盟中，即對(duì)于任意的1 ≤i＜j≤m，聯(lián)盟Ci和Cj中的最小元素只存在以下兩種情況：

1）聯(lián)盟Ci的最小元素小于聯(lián)盟Cj的最小元素，即minCi＜minCj。

2）聯(lián)盟Ci的最小元素等于聯(lián)盟Cj的最小元素。設(shè)相同最小元素集合為S，將其從聯(lián)盟Ci和Cj去除再比較兩者的最小元素，直至出現(xiàn)1）中的情況。等價(jià)為：

注意，此方法定義的聯(lián)盟結(jié)構(gòu)具有以下性質(zhì)：如果前i-1個(gè)玩家都在前l(fā)(1 ≤l≤k)個(gè)非空聯(lián)盟中，則玩家i一定屬于其中的前min {k，l+Wi}個(gè)聯(lián)盟。簡(jiǎn)單來說，這種玩家序列性質(zhì)可以有效地縮小OCSG問題搜索空間。

在日常工作中，滿足玩家序列的kOCF 博弈也是有跡可循的?；叵?.2節(jié)中部門員工之間形成的kOCF 博弈情景，在這個(gè)情景中，由于每個(gè)員工的能力不同，擅長(zhǎng)完成的項(xiàng)目也不同。部門可以按照這個(gè)標(biāo)準(zhǔn)對(duì)員工進(jìn)行等級(jí)評(píng)判，同時(shí)按照任務(wù)的難度、利潤(rùn)對(duì)項(xiàng)目編號(hào)排序。其中高等級(jí)的員工對(duì)應(yīng)著編號(hào)較小的agent，高難度、高利潤(rùn)的項(xiàng)目對(duì)應(yīng)編號(hào)較小的聯(lián)盟。對(duì)于高等級(jí)的員工（也就是企業(yè)中常說的“核心員工”），部門會(huì)盡可能地將其分配到高難度、高利潤(rùn)的項(xiàng)目中，這樣不僅可以充分利用人力資源，還可以提高整個(gè)部門完成項(xiàng)目的效率和收益。為了方便起見，之后所提及的kOCF 博弈均滿足該性質(zhì)。

為了可以量化并計(jì)算兩個(gè)聯(lián)盟結(jié)構(gòu)的相似程度，接下來介紹了一種特殊的輔助運(yùn)算。對(duì)于1 ≤i≤n，集合{1，2，…，i}表示為[i]。

定義7一個(gè)聯(lián)盟結(jié)構(gòu)CS=(C1，C2，…)到[i]的約束CS|[i]定義為：

基于這種約束，聯(lián)盟結(jié)構(gòu)的相似度量定義如下：

定義8相似度量。給定一個(gè)kOCF 博弈G=其中玩家子集N={1，2，…，n}。對(duì)于任意兩個(gè)聯(lián)盟結(jié)構(gòu)CS1，CS2∈CSA，若存在中的集合是中對(duì)應(yīng)位置集合的子集，那么認(rèn)為相似度增加1，并且用|[i]|表示存在這種關(guān)系集合的數(shù)量。相似度量Δ定義為：

該相似度量的實(shí)際意義是，按照玩家1，2，…，n的次序，兩個(gè)聯(lián)盟結(jié)構(gòu)每有一個(gè)相同位置的玩家編號(hào)，相似度量的值就會(huì)至少增加1。

定理1對(duì)于n個(gè)玩家的kOCF 博弈，任意兩個(gè)聯(lián)盟結(jié)構(gòu)CS1，CS2的相似度量取值范圍在1 到nk之間，即1 ≤Δ(CS1，CS2)≤nk。

證明 由于博弈滿足玩家序列的性質(zhì)，且每個(gè)玩家都要參與到聯(lián)盟中，那么在任意聯(lián)盟結(jié)構(gòu)中玩家1 一定是在第一個(gè)聯(lián)盟中的。對(duì)于CS1和CS2到[1]上的約束一定存在定義8中的對(duì)應(yīng)子集關(guān)系，所以它們的相似度量一定是大于等于1的正整數(shù)。在kOCF 博弈中，聯(lián)盟結(jié)構(gòu)中最大聯(lián)盟數(shù)量是k，則| [i]|的取值最大為k。由式（6）可得，Δ(CS，CS′)最大值為nk。

定理1 說明了任意兩個(gè)聯(lián)盟結(jié)構(gòu)的相似度量都是存在且有界的。有了這種相似度量就可以度量任何聯(lián)盟結(jié)構(gòu)與最優(yōu)聯(lián)盟結(jié)構(gòu)之間的相似程度。然后基于這種相似度量，提出kOCF 博弈的單調(diào)性定義，并且通過引理1 證明了這種單調(diào)性是存在的。

定義9kOCF 博弈的單調(diào)性。給定一個(gè)kOCF 博弈G=如果它的特征函數(shù)v滿足以下兩條性質(zhì)，它就是一個(gè)單調(diào)的kOCF博弈。

1）只有一個(gè)最優(yōu)值，也就是只有一種最優(yōu)聯(lián)盟結(jié)構(gòu)。

2）特征函數(shù)v在聯(lián)盟結(jié)構(gòu)與CSOPT的相似度量上是單調(diào)遞增的。即對(duì)于聯(lián)盟結(jié)構(gòu)CS1和CS2，有

引理1存在單調(diào)的kOCF博弈。

證明 表2 是一個(gè)kOCF 博弈G=的例子，更確切來說是3OCF 博弈，其中N={1，2，3}，W={2，2，1}。特別地該博弈假設(shè)每個(gè)任務(wù)只可以完成一次，即聯(lián)盟結(jié)構(gòu)中不允許有重復(fù)的聯(lián)盟出現(xiàn)。該kOCF 博弈滿足定義9中的單調(diào)性，其中最優(yōu)聯(lián)盟結(jié)構(gòu)CSOPT=({1，2，3}，{1，2})。

表2 單調(diào)的3OCF博弈實(shí)例Tab.2 Example of monotonous 3OCF games

引理1 通過列舉一個(gè)3OCF 博弈實(shí)例證明了單調(diào)的kOCF博弈是存在的。這是第3 章中算法1 和重要定理2 的前提條件。

3 基于單調(diào)kOCF博弈的CCG算法設(shè)計(jì)

在本章中，對(duì)于單調(diào)的kOCF 博弈使用了貪心方法設(shè)計(jì)了CCG 算法來解決最優(yōu)聯(lián)盟結(jié)構(gòu)生成問題。假設(shè)所求的最優(yōu)聯(lián)盟結(jié)構(gòu)如果一個(gè)聯(lián)盟結(jié)構(gòu)CS中玩家i的位置與CSOPT中情況相同，則稱玩家i在最優(yōu)位置上。最優(yōu)聯(lián)盟結(jié)構(gòu)可以認(rèn)為是所有玩家都在其對(duì)應(yīng)的最優(yōu)位置上的聯(lián)盟結(jié)構(gòu)。聯(lián)盟約束貪心算法是通過逐步確定玩家1，2，…，n的最優(yōu)位置來解決OCSG問題，具體算法如下

算法1 基于單調(diào)kOCF博弈的聯(lián)盟約束貪心算法。

輸入 單調(diào)kOCF博弈G=和最大聯(lián)盟數(shù)量k。

輸出 最優(yōu)聯(lián)盟結(jié)構(gòu)CSOPT。

3.1 求解過程

在2.2 節(jié)中，kOCF 博弈中聯(lián)盟可以用玩家編號(hào)的形式來表示，所以一個(gè)聯(lián)盟結(jié)構(gòu)可以認(rèn)為是插入不同玩家種類和多個(gè)玩家編號(hào)形成的。例如，在一個(gè)kOCF 博弈G=中，其中N={1，2，3}，玩家的權(quán)值向量W={2，2，2}。由于玩家的數(shù)量有3個(gè)且每個(gè)玩家的權(quán)值都是2，在算法處理中認(rèn)為有3種不同的玩家種類，且每個(gè)玩家種類都包含2個(gè)編號(hào)。算法需要解決的問題由確定每個(gè)玩家的最優(yōu)位置轉(zhuǎn)向到如何將這些玩家編號(hào)一一插入到最優(yōu)聯(lián)盟結(jié)構(gòu)當(dāng)中。下面給出算法的關(guān)鍵定理及其證明。

定理2給定一個(gè)單調(diào)的kOCF 博弈G=，假設(shè)前i-1(1 ≤i≤n)個(gè)玩家均在最優(yōu)位置上，且它們都屬于前l(fā)個(gè)聯(lián)盟中，換句話說l代表的是前i-1 玩家都在最優(yōu)位置上的最大聯(lián)盟編號(hào)。那么玩家i所在聯(lián)盟編號(hào)取值一定是在1到min{k，l+Wi}之間，即i∈{C1，C2，…，對(duì)于玩家i，假設(shè)CS1是玩家i在最優(yōu)位置上的聯(lián)盟結(jié)構(gòu)，即SF1(i)=SFOPT(i)，聯(lián)盟結(jié)構(gòu)CS2則相反。由于定義9 的單調(diào)性性質(zhì)，CS1是唯一的，而CS2可以有多種情況。那么一定有

證明 在單調(diào)kOCF 博弈中，如果前i-1 個(gè)玩家都屬于前l(fā)個(gè)聯(lián)盟中，由于定義6 和式（3）的限制，玩家i所在聯(lián)盟編號(hào)取值一定是在1到l+Wi之間。根據(jù)式（6）有：

其中Wi代表的是玩家i的權(quán)值，是一個(gè)大于等于1 的正整數(shù)。那么根據(jù)式（7）單調(diào)性的性質(zhì)可得v(CS1)＞v(CS2)。

簡(jiǎn)單來說，定理2 的作用是根據(jù)前i-1 個(gè)玩家所在聯(lián)盟位置可以確定玩家i所在聯(lián)盟位置的范圍。相對(duì)于遍歷搜索空間解決OCSG 問題，它僅僅需要搜索少數(shù)聯(lián)盟結(jié)構(gòu)，可以有效地縮小算法的搜索空間。在這些被搜索的聯(lián)盟結(jié)構(gòu)中，通過比較聯(lián)盟值來確定玩家i的最優(yōu)位置SFOPT(i)。特別地，參與比較的聯(lián)盟結(jié)構(gòu)是不可以隨意選取的。這是因?yàn)橥婕襥+1，i+2，…，n參與聯(lián)盟結(jié)構(gòu)的消耗的權(quán)值不同，聯(lián)盟結(jié)構(gòu)與最優(yōu)聯(lián)盟結(jié)構(gòu)的相似度也會(huì)受到影響，違背了算法研究的是單調(diào)kOCF 博弈的前提，所以采用最大玩家權(quán)重原則來生成比較使用的聯(lián)盟結(jié)構(gòu)。所謂最大玩家權(quán)重原則是指讓玩家i+1，i+2，…，n盡可能地形成規(guī)模較大的聯(lián)盟來插入到聯(lián)盟結(jié)構(gòu)中，如果聯(lián)盟結(jié)構(gòu)中有空集的情況下，則優(yōu)先插入到空集中。這種方式旨在提高系統(tǒng)里多個(gè)agent的資源利用率，進(jìn)而提高整個(gè)系統(tǒng)的收益，同時(shí)保證單調(diào)kOCF博弈的算法前提。

算法1是利用了貪心方法解決了單調(diào)kOCF中的OCSG問題。算法的總體流程是按照玩家編號(hào)的順序，將玩家1，2，…，n分別插入到其對(duì)應(yīng)最優(yōu)位置。其中玩家1，2，…，n的最優(yōu)位置SFOPT(i)確定是通過定理2 來判別的。當(dāng)循環(huán)結(jié)束時(shí)，也就是每個(gè)玩家都插入到了其對(duì)應(yīng)的最優(yōu)位置，算法生成的聯(lián)盟結(jié)構(gòu)就是最優(yōu)聯(lián)盟結(jié)構(gòu)。

3.2 算法實(shí)例

為了簡(jiǎn)潔明了地描述算法實(shí)例，使用了表2 中的博弈聯(lián)盟值。

例2 給定一個(gè)3OCF 博弈G=其中N={1，2，3}，W={2，2，1}。算法的具體步驟如下。

初始化 初始化CSOPT=(?，?，?)，和當(dāng)前最大玩家聯(lián)盟編號(hào)l=0。

確定玩家1 的最優(yōu)位置 由于當(dāng)前最大玩家聯(lián)盟編號(hào)為0，玩家1 的最大權(quán)值為2，那么根據(jù)定義6 玩家1 可能參與了一個(gè)或兩個(gè)聯(lián)盟，且所在聯(lián)盟編號(hào)范圍在1和2之間?？赡艿穆?lián)盟位置如下：

1）1 ∈C1；

2）1 ∈C1并且1 ∈C2。

按照玩家權(quán)重最大原則，對(duì)于第1）種情況生成的聯(lián)盟結(jié)構(gòu)為CS1=({1}，{2，3}，{2})，即SF1(1)={1}。對(duì)于第2）種情況生成的聯(lián)盟結(jié)構(gòu)為CS2=({1，2}，{1}，{2，3})，即SF2(1)={1，2}。由于v(CS1)＜v(CS2)，所以SFOPT(1)=SF2(1)。此時(shí)的最優(yōu)聯(lián)盟結(jié)構(gòu)CSOPT=({1}，{1}，?)，更新l=2。

確定玩家2 的最優(yōu)位置 玩家2 可能的聯(lián)盟位置有以下4種情況：

1）2 ∈C1；

2）2 ∈C1并且2 ∈C2；

3）2 ∈C3；

4）2 ∈C1并且2 ∈C3。

注意，2 ∈C2和2 ∈C2并且2 ∈C3這種情況是不存在的，因?yàn)樗`背了定義6 中的玩家序列定義。按照玩家最大權(quán)重準(zhǔn)則，對(duì)于第1）種情況生成的聯(lián)盟結(jié)構(gòu)為CS1=({1，2}，{1}，{3})，SF1(2)={1}；對(duì)于第2）種情況生成的聯(lián)盟結(jié)構(gòu)為CS2=({1，2，3}，{1，2})，SF2(2)={1，2}；對(duì)于第3）種情況生成的聯(lián)盟結(jié)構(gòu)為CS3=({1，3}，{1}，{2})，SF3(2)={3}；第4）種情況生成的聯(lián)盟結(jié)構(gòu)為CS2=({1，2，3}，{1}，{2})，SF4(2)={1，3}。由于v(CS2)＞v(CS4)＞v(CS1)＞v(CS3)，有SFOPT(2)=SF2(2)。此時(shí)的最優(yōu)聯(lián)盟結(jié)構(gòu)CSOPT=({1，2}，{1，2})，更新l=2。

確定玩家3的最優(yōu)位置 同理，玩家3可能的聯(lián)盟位置只可能有一種：

3 ∈C1

這是因?yàn)橥婕? 的權(quán)值只有1，如果玩家3 出現(xiàn)聯(lián)盟2 或聯(lián)盟3中，那么它會(huì)違背玩家序列的定義。所以玩家3只能在聯(lián)盟1 中。算法計(jì)算得到的最優(yōu)聯(lián)盟結(jié)構(gòu)CSOPT=({1，2，3}，{1，2})。

這樣通過4 次比較（1 次比較為玩家1 尋找最優(yōu)位置，3 次比較為玩家2 尋找最優(yōu)位置，0 次比較為玩家3 尋找最優(yōu)位置）找到了最優(yōu)聯(lián)盟結(jié)構(gòu)。相對(duì)于搜索表2 中全部的17 種聯(lián)盟結(jié)構(gòu)，CCG算法只搜索6次就解決了OCSG問題。

3.3 復(fù)雜度分析

定理3對(duì)于單調(diào)kOCF 博弈，CCG 算法可以在至多O(n2k+1)時(shí)間內(nèi)確定CSOPT，并且是參數(shù)可解的。

證明 在算法1中，第1）～2）行初始化操作的時(shí)間復(fù)雜度為O(k)。第4）～8）行的循環(huán)遍歷出玩家i擁有不同權(quán)重時(shí)所在最優(yōu)位置的所有可能性。循環(huán)生成的聯(lián)盟結(jié)構(gòu)有種。如果忽略玩家序列的限制，且假設(shè)每個(gè)玩家i的最優(yōu)位置選擇范圍q都為最大值k（聯(lián)盟結(jié)構(gòu)的中聯(lián)盟數(shù)量最大值為k，實(shí)際中編號(hào)前一部分玩家的最優(yōu)位置選擇范圍是小于k的）。所有玩家的權(quán)值都為Wmax=k，即玩家的資源足夠參與到所有的聯(lián)盟中（對(duì)于一個(gè)博弈來說，Wmax=是比較合理的，即每個(gè)玩家最多可以參加聯(lián)盟結(jié)構(gòu)中一半的聯(lián)盟）。對(duì)于這種最壞的情況，生成的聯(lián)盟結(jié)構(gòu)種類數(shù)目有那么第4）～8）行操作的時(shí)間復(fù)雜度為O(2k)。第9）行操作是遍歷生成的聯(lián)盟結(jié)構(gòu)并找到一個(gè)聯(lián)盟值最大的情況，時(shí)間復(fù)雜度也是O(2k)。第10）行操作需要遍歷聯(lián)盟結(jié)構(gòu)中的每個(gè)聯(lián)盟插入玩家編號(hào)，時(shí)間復(fù)雜度為O(k)。算法1 是對(duì)玩家1，2，…，n的循環(huán)操作，所以整體的時(shí)間復(fù)雜度至多為O(n2k+1)。當(dāng)k值固定時(shí)，CCG 算法復(fù)雜度是關(guān)于n的多項(xiàng)式，所以是固定參數(shù)可解的。

4 算法的實(shí)驗(yàn)分析

本章首先對(duì)不同參數(shù)對(duì)CCG 算法的影響進(jìn)行了實(shí)驗(yàn)和分析，然后與Zick 等［10］基于有界樹寬通信圖提出的OCSG 算法進(jìn)行對(duì)比，目的是評(píng)估本文提出CCG算法的性能。

4.1 實(shí)驗(yàn)環(huán)境

所有算法均使用Matlab R2017a 實(shí)現(xiàn)。實(shí)驗(yàn)是在一臺(tái)配備2.20 GHz Intel Core CPU、8.0 GB RAM 和Windows 10 操作系統(tǒng)的計(jì)算機(jī)上進(jìn)行的。每個(gè)實(shí)驗(yàn)重復(fù)5～8 次，取平均結(jié)果為最終實(shí)驗(yàn)結(jié)果。

4.2 實(shí)驗(yàn)結(jié)果分析

算法的運(yùn)行時(shí)間和搜索次數(shù)可以作為評(píng)價(jià)算法性能的標(biāo)準(zhǔn)，主要是利用控制變量法實(shí)驗(yàn)并分析了agent 個(gè)數(shù)、最大聯(lián)盟數(shù)量值k和不同聯(lián)盟值分布對(duì)CCG算法性能的影響。

4.2.1 agent個(gè)數(shù)對(duì)CCG算法性能的影響

在重疊聯(lián)盟結(jié)構(gòu)生成算法中，agent 個(gè)數(shù)是影響算法性能的主要因素。隨著agent 個(gè)數(shù)的不斷增加，OCSG 問題的搜索空間也變得極其龐大。在接下來的CCG 算法參數(shù)實(shí)驗(yàn)中，取玩家集合中agent個(gè)數(shù)從16增加到20，其中聯(lián)盟最大數(shù)量k值取為［24］，聯(lián)盟值分布的情況采用后文中的Normal 型分布，對(duì)CCG算法運(yùn)算時(shí)間和搜索次數(shù)進(jìn)行了統(tǒng)計(jì)。

通過表3和圖1可以分析得出，CCG算法擁有較短的運(yùn)行時(shí)間。此外相對(duì)于遍歷整個(gè)搜索空間，表3和圖2中的數(shù)據(jù)說明了CCG 算法實(shí)現(xiàn)了聯(lián)盟結(jié)構(gòu)的減枝搜索，僅僅需要搜索少量的聯(lián)盟結(jié)構(gòu)就解決了OCSG問題。

表3 不同agent個(gè)數(shù)下CCG算法的運(yùn)行時(shí)間和搜索次數(shù)Tab.3 Running time and search times of CCG algorithm with different agent numbers

圖1 不同agent個(gè)數(shù)下CCG算法運(yùn)行時(shí)間Fig.1 Running time of CCG algorithm with different agent numbers

圖2 不同agent個(gè)數(shù)下CCG算法搜索次數(shù)Fig.2 Search times of CCG algorithm with different agent numbers

圖3 是固定k值為8 到10 得出的實(shí)驗(yàn)數(shù)據(jù)，它說明了在k值固定的情況下，CCG 算法的搜索次數(shù)與agent個(gè)數(shù)基本呈線性關(guān)系。這與定理3 中證明的算法復(fù)雜度是O(n2k+1)相符合的，并且是固定參數(shù)可解的，同時(shí)也是CCG 算法的優(yōu)點(diǎn)之一。

圖3 k值固定時(shí)不同agent個(gè)數(shù)下CCG算法搜索次數(shù)Fig.3 Search times of CCG algorithm with different agent numbers under fixed k value

4.2.2k值對(duì)CCG算法性能的影響

研究使用的kOCF 博弈模型是一種限制了聯(lián)盟結(jié)構(gòu)中聯(lián)盟最大數(shù)量的博弈，所以k值的取值范圍也可能是影響CCG算法的重要因素之一。本文在不同agent數(shù)目下對(duì)不同k值的CCG 算法進(jìn)行了實(shí)驗(yàn)測(cè)試。實(shí)驗(yàn)結(jié)果如圖4 所示，可以分析得到以下結(jié)論：在k值較小的情況下，CCG 算法的運(yùn)行時(shí)間基本與k值呈指數(shù)關(guān)系。當(dāng)k值較大的時(shí)候，k值的增長(zhǎng)對(duì)CCG算法搜索次數(shù)的影響逐漸變小，這也從側(cè)面驗(yàn)證了CCG 算法復(fù)雜度證明的正確性。

這是由于定理3 是在最壞假設(shè)下證明的，其中每個(gè)玩家擁有的權(quán)值都為Wmax且與k值相等。在實(shí)際實(shí)驗(yàn)中，雖然k值是逐漸增大的，但生成的玩家權(quán)值集合是固定的。不失一般性，在算法實(shí)驗(yàn)中假設(shè)每個(gè)玩家的可能的最大權(quán)值為4，且玩家權(quán)值是符合均勻分布的，即每個(gè)玩家擁有的權(quán)值都會(huì)小于k。相比于最壞情況下的假設(shè)，實(shí)際情況k值對(duì)CCG 算法搜索次數(shù)影響更小，所以隨著k值的增大，CCG 算法的搜索次數(shù)增長(zhǎng)速度逐漸減緩。

圖4 不同k值下的CCG算法搜索次數(shù)Fig.4 Search times of CCG algorithm under different k values

4.2.3 聯(lián)盟值分布對(duì)CCG算法性能的影響

Rahwan 等［25］研究發(fā)現(xiàn)，對(duì)于他們提出的IP（Integer-Partition based）算法如果實(shí)驗(yàn)使用的聯(lián)盟值數(shù)據(jù)符合正態(tài)分布和均勻分布，算法會(huì)生成更小聯(lián)盟數(shù)量的解，從而，他們得出了某些算法實(shí)驗(yàn)聯(lián)盟值分布如果采用正態(tài)分布和均勻分布定義可以優(yōu)于其他算法的結(jié)論。

CCG 算法最重要的一步是根據(jù)玩家編號(hào)不同的分布情況，按照最大玩家權(quán)重原則生成聯(lián)盟結(jié)構(gòu)并挑選出聯(lián)盟值最大的聯(lián)盟結(jié)構(gòu)，所以聯(lián)盟值分布也是可能影響算法性能的因素之一。接下來的實(shí)驗(yàn)研究了不同聯(lián)盟值分布對(duì)CCG 算法性能的影響。具體來說，本文使用了文獻(xiàn)［13，25］中的以下標(biāo)準(zhǔn)分布：

1）Normal：v(C)～|C|× N(μ，σ2)，其中μ=1且σ=0.1。

2）Uniform：v(C)～|C|× U(a，b)，其中a=0且b=1。

3）NDCS：v(C)～N(μ，σ2)，其中μ=|C|且σ=

然后取玩家集合中agent 個(gè)數(shù)從16 增加到20，其中聯(lián)盟最大數(shù)量k值取為，玩家的權(quán)值集合W符合均勻分布。對(duì)以上三種聯(lián)盟值分布分別進(jìn)行了實(shí)驗(yàn)并統(tǒng)計(jì)運(yùn)行時(shí)間和搜索次數(shù)。

綜合分析圖5和圖6中的數(shù)據(jù)很容易得到以下結(jié)論：CCG算法在聯(lián)盟值為NDCS 類型分布的情況下?lián)碛休^短的運(yùn)行時(shí)間和較少的搜索次數(shù)，即更好的算法性能。

圖5 不同聯(lián)盟值分布下CCG算法運(yùn)行時(shí)間Fig.5 Running time of CCG algorithm under different coalition value distributions

圖6 不同聯(lián)盟值分布下CCG算法搜索次數(shù)Fig.6 Search times of CCG algorithm under different coalition value distributions

4.3 算法對(duì)比

為了更好地體現(xiàn)CCG 算法的有效性和適用性，將CCG 算法和Zick 等［10］基于有界樹寬通信圖約束提出的OCSG 算法進(jìn)行了方法類型、約束條件等以下方面的對(duì)比分析，如表4所示。

兩種算法使用的貪心方法和動(dòng)態(tài)規(guī)劃方法都是解決OCSG 問題有效的方法之一。兩種算法同樣都使用了離散化OCF博弈模型，該模型更有利于進(jìn)行復(fù)雜的理論分析。OCSG問題中約束條件是必不可少的，它可以有效地縮小算法的搜索范圍。通信圖約束是指在通信圖中只有鄰接點(diǎn)之間才可以形成聯(lián)盟。這種約束固定了聯(lián)盟結(jié)構(gòu)中聯(lián)盟的種類和agent成員，而玩家系列約束實(shí)際是對(duì)玩家和任務(wù)等級(jí)的一種排序，相比之下玩家序列約束較為寬松且適用于多種情景。

表4 CCG算法和Zick等［10］提出算法的對(duì)比Tab.4 Comparison between CCG algorithm and the algorithm proposed by Zick et al.［10］

時(shí)間復(fù)雜度的計(jì)算與約束條件息息相關(guān)，CCG 算法中約束了聯(lián)盟結(jié)構(gòu)中最大聯(lián)盟數(shù)量，且模糊了聯(lián)盟中agent的資源分配（聯(lián)盟c的分量是0或1），再加上重疊聯(lián)盟博弈本身agent權(quán)值限制，可以很好地限制聯(lián)盟結(jié)構(gòu)的生成規(guī)模，它的時(shí)間復(fù)雜度只和agent個(gè)數(shù)n和最大聯(lián)盟數(shù)量k有關(guān)，且固定參數(shù)k可解。Zick提出的算法只討論了聯(lián)盟中最大agent數(shù)量k′=2和k′=3的情況，從通信圖葉子節(jié)點(diǎn)到根節(jié)點(diǎn)分別使用動(dòng)態(tài)規(guī)范的方法進(jìn)行計(jì)算，它的時(shí)間復(fù)雜度與agent最大權(quán)值Wmax和當(dāng)前節(jié)點(diǎn)i的子節(jié)點(diǎn)數(shù)目|Ci|有關(guān)。當(dāng)k′值比較大時(shí)，Zick 提出的算法過程就顯得極其復(fù)雜。CCG算法是通過插入玩家編號(hào)來生成最優(yōu)聯(lián)盟結(jié)構(gòu)，適用于需要計(jì)算最優(yōu)聯(lián)盟結(jié)構(gòu)中的聯(lián)盟種類和成員的博弈。Zick提出的算法是基于有界樹寬通信圖上的計(jì)算，適用于需要計(jì)算出agent 之間合作程度（agent 資源分配情況）的博弈?？偟膩碚f，相對(duì)于Zick 提出的算法，CCG算法擁有更好的適用性。

5 結(jié)語

本文主要研究了OCF 博弈中最優(yōu)聯(lián)盟結(jié)構(gòu)生成問題。為了簡(jiǎn)化計(jì)算問題，使用了約束了最大聯(lián)盟數(shù)量的離散OCF博弈。對(duì)于滿足玩家序列定義的kOCF 博弈，引入了一種相似度度量來度量任意一對(duì)聯(lián)盟結(jié)構(gòu)之間的相似度?；谶@種相似度量又定義了單調(diào)性性質(zhì)，該性質(zhì)認(rèn)為與最優(yōu)聯(lián)盟結(jié)構(gòu)相似度越高的聯(lián)盟結(jié)構(gòu)的值越大。針對(duì)單調(diào)kOCF 博弈，利用貪心方法提出了CCG 算法來解決OCSG 問題。并通過實(shí)驗(yàn)分析了agent 個(gè)數(shù)、最大聯(lián)盟數(shù)量k和不同聯(lián)盟值分布對(duì)算法性能的影響，實(shí)驗(yàn)結(jié)果驗(yàn)證了CCG算法的搜索次數(shù)與agent個(gè)數(shù)基本呈線性關(guān)系這一優(yōu)點(diǎn)，這說明算法是固定參數(shù)可解的。最后通過與Zick 提出的算法在約束條件等多方面的對(duì)比，說明了CCG算法擁有更好的適用性。

有多種方法可以進(jìn)行進(jìn)一步的研究。目前使用的模型是kOCF 博弈，該博弈對(duì)參與者的序列有一定嚴(yán)格的設(shè)定，但在許多聯(lián)盟博弈中，玩家是無序的。如何將所提出的方法推廣到這類博弈中仍有待研究。在agent 個(gè)數(shù)和玩家最大權(quán)值較大的情況下，隨機(jī)生成單調(diào)的kOCF 博弈在實(shí)際中運(yùn)行時(shí)間是比較長(zhǎng)的，如何快速地生成這種博弈也是可以進(jìn)一步研究的。