合作博弈的連續(xù)蟻群算法求解

李壯闊，常凱旋

桂林電子科技大學(xué) 商學(xué)院，廣西 桂林541004

1944年，von Neumann和Morgenstern的專著Theory of games and economic behavior的問世，標(biāo)志著博弈論的誕生。在該書中，作者用大量篇幅討論了合作博弈的相關(guān)理論，同時考慮了聯(lián)盟的內(nèi)部穩(wěn)定性和外部穩(wěn)定性，從占優(yōu)的角度提出了穩(wěn)定集，這為合作博弈的發(fā)展奠定了理論基礎(chǔ)[1]。此后，許多學(xué)者從不同方向探討了合作博弈的解概念。合作博弈求解的核心思想是合作均衡，經(jīng)典合作博弈的解概念可以分為兩類：以核為代表的優(yōu)超法和以Shapley值為代表的賦值法[2]。占優(yōu)法以“占優(yōu)”和“異議”為主要準(zhǔn)則，體現(xiàn)了穩(wěn)定性和聯(lián)盟信息。Gillies考慮局中人的個體理性和聯(lián)盟的有效性，從占優(yōu)角度出發(fā)，提出核的概念來研究穩(wěn)定集[3]。Aumann和Maschler將分配結(jié)果的形成過程視作局中人的談判過程，提出了談判解，體現(xiàn)了分配方案的合理性[4]。Davis和Maschler通過引入了內(nèi)核的概念來研究談判解，主要分析了不同局中人對分配方案異議大小的度量的相關(guān)問題[5]。Schmeidler提出了核仁的概念，利用超出值來度量局中人對分配方案的不滿意程度，從而找出聯(lián)盟對分配方案集中不滿意程度最低的分配方案[6]。賦值法構(gòu)造一種考慮沖突各方要求的折中的合理結(jié)果，通過公理化方法描述解的性質(zhì)，進(jìn)而得到唯一的分配方案。Shapley從分配方式的合理性與公平性出發(fā)，通過不同局中人對聯(lián)盟的邊際貢獻(xiàn)來計(jì)算局中人的分配，提出了Shapley值[7]。Myerson提出并研究了具有圖限制結(jié)構(gòu)的合作博弈，在Shapley值基礎(chǔ)上給出了圖限制結(jié)構(gòu)合作博弈的解——Myerson值[8]?；贛yerson的工作，Herings利用圖限制博弈和有向樹定義了平均樹解（A-T解）[9]。Banzhaf考慮聯(lián)盟中各局中人的權(quán)力不同，將局中人的權(quán)力大小看作獲勝聯(lián)盟中的關(guān)鍵加入者的個數(shù)，使用權(quán)力指數(shù)比來刻畫Banzhaf權(quán)力指數(shù)[10]。

經(jīng)典的合作博弈解概念中的假設(shè)與現(xiàn)實(shí)博弈環(huán)境相比過于簡單，并且沒有考慮到現(xiàn)實(shí)中聯(lián)盟的形成方式。英國著名經(jīng)濟(jì)學(xué)者布勞格認(rèn)為：博弈論的全部力量都用于滿足經(jīng)濟(jì)學(xué)家對形式主義模型的沉溺，卻不關(guān)心模型的現(xiàn)實(shí)性如何[11]。合作博弈的求解目標(biāo)是要找到一個能夠形成與維系聯(lián)盟的分配方案?，F(xiàn)實(shí)中，聯(lián)盟分配方案的達(dá)成通常是局中人互相影響，不斷調(diào)整、妥協(xié)和趨同的互動過程。如何描述局中人為了合作而競爭，同時又在談判中趨同是建立合作博弈求解模型的難點(diǎn)。近年來，有學(xué)者嘗試將復(fù)雜的多目標(biāo)優(yōu)化問題模型與合作博弈結(jié)合在一起。葉文海等提出Isight的博弈多目標(biāo)優(yōu)化設(shè)計(jì)方法，通過合作博弈模型解決多目標(biāo)系統(tǒng)的求解問題，建立了兩者之間的聯(lián)系，并用遺傳算法進(jìn)行求解[12]。劉雨瀟等針對云任務(wù)調(diào)度優(yōu)化問題，提出一種基于納什議價解的多目標(biāo)合作博弈調(diào)度算法[13]。潘穎慧等研究了不確定性多智能體在交互環(huán)境下如何優(yōu)化本身決策，并總結(jié)歸納了模型的具體表達(dá)方式和求解方法，克服了傳統(tǒng)的博弈論求解多智能體決策的局限性[14]。侯德飛等將合作博弈理論應(yīng)用于部隊(duì)彈藥調(diào)度策略問題之中，分別建立合作、競爭合作競爭博弈框架，并用遺傳算法對模型進(jìn)行求解[15]。Xu等將執(zhí)行器的控制精度優(yōu)化問題看作一種多目標(biāo)優(yōu)化問題，結(jié)合合作博弈理論提出了一種分布式模型預(yù)測方法[16]。丁陽等針對配電網(wǎng)重構(gòu)問題，將目標(biāo)函數(shù)作為合作博弈的局中人，通過螢火蟲算法計(jì)算最終的重構(gòu)方案[17]。

現(xiàn)實(shí)中聯(lián)盟最終分配方案的達(dá)成通常是局中人基于個體理性與判斷進(jìn)行多輪談判，互相影響、相互妥協(xié)、最終趨同的結(jié)果。對此，本文將合作博弈的求解過程視作局中人個體博弈和群體趨同的多目標(biāo)優(yōu)化問題?？紤]到談判過程中局中人的個體調(diào)整和群體趨同行為，引入分配方案、理性因子與控制因子等現(xiàn)實(shí)影響因素，構(gòu)建考慮互動行為的合作博弈模型。在此過程中，對傳統(tǒng)連續(xù)優(yōu)化蟻群算法進(jìn)行改進(jìn)，提出合作博弈的連續(xù)蟻群優(yōu)化算法對合作博弈模型進(jìn)行求解。

1 考慮互動行為的合作博弈模型

傳統(tǒng)的合作博弈模型是基于團(tuán)隊(duì)合作的求解，是集中控制下的資源配置。這種方法存在一個問題，集中配置很容易引發(fā)不滿，影響局中人間的合作關(guān)系。從多個局中人競爭的角度研究聯(lián)盟分配問題是新的思路，但也需滿足合作的要求。相比于傳統(tǒng)的求解方法，建模的難點(diǎn)在于如何分析局中人競爭行為與達(dá)成共同接受的分配方案兩者的協(xié)調(diào)關(guān)系。

聯(lián)盟中的利益分配過程實(shí)際上是一種談判協(xié)商過程，聯(lián)盟成員會在分配利益時進(jìn)行談判博弈。博弈的基本要素有局中人、局中人的分配方案、信息和行動等。在談判開始前，局中人會根據(jù)信息及偏好提出預(yù)分配方案。受局中人個體理性，個體偏好和成員關(guān)系等因素影響，不同局中人對最優(yōu)策略的評判標(biāo)準(zhǔn)往往各不相同。因此，在求解過程中需要一個確定的適應(yīng)度函數(shù)作為分配方案的統(tǒng)一評價標(biāo)準(zhǔn)。在每輪談判過程中，使用談判檔案作為局中人的間接通訊機(jī)制，談判檔案可以提供信息流通的渠道進(jìn)而實(shí)現(xiàn)局中人在談判中的互動行為。局中人通過對談判檔案中的信息進(jìn)行收集和處理，得到個體最優(yōu)信息和群體最優(yōu)信息，依據(jù)自身策略、理性、學(xué)習(xí)情況調(diào)整自己的分配方案。局中人對這兩種信息的重視程度分別體現(xiàn)了局中人的兩種博弈態(tài)度。第一種為競爭，局中人追求更高的個人收益，會更看重個體最優(yōu)信息；第二種為合作，局中人更希望達(dá)成合作，會更看重群體最優(yōu)信息?，F(xiàn)實(shí)中，局中人對兩種信息的重視程度會隨局勢不斷變化，通常表現(xiàn)為前期更看重個體最優(yōu)信息，后期更看重群體最優(yōu)信息。最終，通過多輪談判實(shí)現(xiàn)分配方案的趨同。

n人合作博弈記作(N,v)，參與博弈的人稱為局中人，所有局中人構(gòu)成了局中人集N={1,2,…,n},N的任意一個非空子集S為一個聯(lián)盟，由全體局中人組成的聯(lián)盟稱為大聯(lián)盟N。大聯(lián)盟給局中人j分配的收益記為x({j}),x({j})表示局中人j不加入任何聯(lián)盟時獲得的最大收益，v(S)表示聯(lián)盟S獨(dú)立活動時獲得的最大收益。下面本文將對考慮互動行為的合作博弈模型的相關(guān)概念進(jìn)行定義，并證明相關(guān)定理。

在第m輪談判中，設(shè)局中人i提出的分配方案為表示局中人i給j分配的收益，分配方案應(yīng)滿足以下約束：

式（1）為分配方案的有效性約束，即聯(lián)盟將收益全部分配給聯(lián)盟成員。式（2）為分配方案的個體理性約束，即局中人的分配不小于自己單干或加入小聯(lián)盟時的收益。所有局中人提出的分配方案構(gòu)成了分配方案矩陣Xm：

在談判過程中，局中人對某條分配方案的評價標(biāo)準(zhǔn)主要考慮兩個要素，即個體最優(yōu)信息和群體平均信息。

定義1個體最優(yōu)信息體現(xiàn)了局中人對自己收益最大化的追求，局中人i的個體最優(yōu)分配方案是在除了局中人i自己所提出的分配方案外的其他分配方案中，使局中人i收益最大的分配方案。即在第m輪談判協(xié)商中，找出當(dāng)前分配方案矩陣中對局中人i分配收益的最大值該最大值所在的分配方案為局中人i的個體最優(yōu)分配方案，記為局中人對個體最優(yōu)信息的學(xué)習(xí)表示為

定義2群體平均信息為聯(lián)盟對局中人的收益分配的平均值，體現(xiàn)了聯(lián)盟整體對個體的判斷與偏好，即

定義3分配方案的適應(yīng)度定義為局中人對分配方案的滿意程度，第i條分配方案的適應(yīng)度為：

在談判過程中，本文采用談判檔案作為局中人間的信息交流機(jī)制，從而實(shí)現(xiàn)局中人在談判過程中的互動行為。采用這種非直接通信的方式好處在于當(dāng)局中人的數(shù)目增加時，整個系統(tǒng)的通信開銷的增幅較小，使得群體智能算法具有較好的擴(kuò)展性。談判檔案的結(jié)構(gòu)包括分配方案和適應(yīng)度兩個部分。談判檔案的構(gòu)造過程為：通過適應(yīng)度函數(shù)計(jì)算分配方案的適應(yīng)度，按照適應(yīng)度從小到大的順序?qū)Ψ峙浞桨概判?，將分配方案和適應(yīng)度存入談判檔案中。具體形式如圖1所示。

圖1 談判檔案結(jié)構(gòu)Fig.1 Structure of solution archive

定義4群體最優(yōu)信息為使聯(lián)盟群體最滿意的一條分配方案，即適應(yīng)度最小的分配方案，也是談判檔案中第一條分配方案，記為局中人對個體最優(yōu)信息的學(xué)習(xí)表示為

在現(xiàn)實(shí)博弈世界中，由于局中人在個體信息、形勢判斷、利益訴求等方面與理想狀態(tài)存在差距，因此局中人在談判過程中追求的是有限理性。在談判過程中，局中人會對個體最優(yōu)信息和群體最優(yōu)信息進(jìn)行一定程度的學(xué)習(xí)。本文使用理性因子來描述局中人的有限理性，使用控制因子來描述局中人對不同信息的學(xué)習(xí)程度。

定義6局中人的控制因子θm(θm∈[0,1])表示局中人對個體最優(yōu)信息和群體最優(yōu)信息的偏重程度，體現(xiàn)了不同談判階段局中人對個體最優(yōu)和群體最優(yōu)追求的變化。通常局中人在談判前期更追求個體最優(yōu)分配，在談判后期為了維持聯(lián)盟而更側(cè)重群體最優(yōu)分配。較大的控制因子可以提高全局搜索能力，避免陷入局部最優(yōu)，較小的控制因子可以提高局部開發(fā)能力，從而加快收斂速度?？刂埔蜃拥娜≈捣绞接芯€性策略和非線性策略兩類，采用線性策略會使得控制因子在迭代過程中呈線性變化，易使收斂速度過慢和陷入局部最優(yōu)，無法適應(yīng)實(shí)際情況。本文采用一種反余弦的非線性策略來調(diào)整控制因子，基本思想是前期加快控制因子的改變速度，從而較快地進(jìn)入局部搜索，避免陷入局部最優(yōu)，后期通過較大的控制因子使算法更注重群體信息，保持解的多樣性。反余弦控制因子構(gòu)造方式如下：

其中，mmax為預(yù)設(shè)的最大迭代次數(shù)，θs、θe表示控制因子的迭代初值和終值，在[0，1]范圍內(nèi)取值且θe＞θs。當(dāng)0≤θm≤1/2時，局中人更加重視個體最優(yōu)信息。當(dāng)1/2＜θm≤1時，局中人更加重視群體最優(yōu)信息。

控制因子隨迭代次數(shù)變化曲線如圖2所示。由圖2可知，控制因子的變化幅度為[θs,θe]，當(dāng)設(shè)定的θs＞1/2或θe＜1/2時，會導(dǎo)致算法只考慮一種最優(yōu)信息，影響算法的收斂精度與速度，因此在設(shè)定參數(shù)時需保證θs＜1/2＜θe。

通過控制因子對迭代次數(shù)m求導(dǎo)可知控制因子的變化速度為：

因此，控制因子的變化速度與(θe-θs)同向變化，與mmax反向變化。為了避免陷入局部最優(yōu)，前期加快控制因子的改變速度，(θe-θs)取值不宜過小，mmax取值不宜過大。

綜合群體最優(yōu)信息和個體最優(yōu)信息，局中人采用混合策略調(diào)整分配方案，局中人在第m輪談判的調(diào)整值為：

局中人在m輪談判后的分配方案為：

定理1談判過程中分配方案始終滿足有效性約束。

∴談判過程中分配方案始終滿足有效性約束。

定理2談判過程中分配方案始終滿足個體理性約束。

∴談判過程中分配方案始終滿足個體理性約束。

2 合作博弈的連續(xù)蟻群算法求解

連續(xù)蟻群算法是由Socha和Dorigo提出的一種用于求解連續(xù)變量組合優(yōu)化問題的智能優(yōu)化算法[18]，這種算法具有局部搜索能力強(qiáng)，收斂速度快等特點(diǎn)，目前已被許多學(xué)者應(yīng)用到現(xiàn)實(shí)中的優(yōu)化問題之中。針對原始連續(xù)蟻群算法尋優(yōu)能力差、易陷入局部最優(yōu)等問題，許多學(xué)者從不同角度提出了改進(jìn)方案。Mahamed等引入Lévy分布和隨機(jī)游走選擇機(jī)制提高了算法的全局搜索能力，避免了早熟[19]。夏媛等提出了一種基于跨鄰域搜索的改進(jìn)連續(xù)蟻群算法，提高了算法的尋優(yōu)能力和穩(wěn)定性[20]。Can等將人工蜂群算法和遺傳算法與連續(xù)蟻群算法相結(jié)合，提高了算法的性能[21]。本文將對原始連續(xù)蟻群算法進(jìn)行改進(jìn)，引入理性因子與控制因子，并將其應(yīng)用于合作博弈的求解之中。

在使用連續(xù)蟻群算法求解聯(lián)盟的收益分配問題時，將聯(lián)盟中的局中人視為一群螞蟻，螞蟻的爬行路徑視為該局中人的分配方案，該路徑上每個維度的值相當(dāng)于對不同局中人分配的收益。每輪談判后螞蟻會根據(jù)個體最優(yōu)信息和群體最優(yōu)信息有偏向地調(diào)整自己前行的路徑，螞蟻對路徑的調(diào)整映射為局中人對分配方案的調(diào)整。理性的局中人既希望能達(dá)成共同接受的分配方案，又希望達(dá)成對自己效用最大的分配方案，既有共同目標(biāo)，又有個體目標(biāo)。在計(jì)算過程中，群體最優(yōu)信息體現(xiàn)出群體的共同目標(biāo)，個體最優(yōu)信息體現(xiàn)出個體的不同目標(biāo)，不斷調(diào)整局中人對兩種信息的學(xué)習(xí)程度體現(xiàn)了局中人選擇策略規(guī)則的變化。隨著不斷迭代調(diào)整，所有螞蟻匯聚在同一條路徑上，所有分配方案的適應(yīng)度相等且取得最小值0，這條路徑所對應(yīng)的分配方案即為被所有局中人接受的分配方案。

合作博弈的連續(xù)蟻群算法分為六步，具體求解步驟如下：

步驟1設(shè)置算法參數(shù)。設(shè)置理性因子、最大迭代次數(shù)、控制因子的初值和終值等初始參數(shù)。

步驟2所有局中人提出初始分配方案，為了使各局中人不會因?yàn)閷Ψ峙浞桨覆粷M而退出聯(lián)盟，局中人提出的分配方案必須滿足個體理性和有效性。所有分配方案構(gòu)成了分配方案矩陣X0。

步驟3計(jì)算分配方案的適應(yīng)度，排序后存入談判檔案中。通過式（4）計(jì)算分配方案的適應(yīng)度，按照適應(yīng)度從小到大的順序?qū)Ψ峙浞桨高M(jìn)行排序，將排序后的分配方案存儲在談判檔案中，此時談判檔案中分配方案的適應(yīng)度滿足，根據(jù)談判檔案計(jì)算個體最優(yōu)信息和群體最優(yōu)信息。

步驟4判斷談判檔案中分配方案的適應(yīng)度是否相等且為0。若是，此時談判檔案中所有分配方案相同，得到最優(yōu)分配方案，迭代結(jié)束。否則，進(jìn)入下一步。

步驟5判斷是否達(dá)到預(yù)設(shè)的最大迭代次數(shù)。若達(dá)到最大迭代次數(shù)，無法取得令所有局中人都滿意的最優(yōu)分配方案，停止迭代，輸出談判檔案；否則，進(jìn)入下一步。

步驟6構(gòu)建新的分配方案。根據(jù)當(dāng)前的個體最優(yōu)信息和群體最優(yōu)信息調(diào)整談判檔案中的分配方案，通過式（6）計(jì)算局中人的調(diào)整值，通過式（7）計(jì)算局中人的調(diào)整后的分配方案。轉(zhuǎn)至步驟3。

合作博弈的連續(xù)蟻群算法求解流程如圖3所示。

圖3 求解流程圖Fig.3 Solving process

3 算例分析

三家企業(yè)決定建立聯(lián)盟生產(chǎn)某種產(chǎn)品投入市場，單獨(dú)生產(chǎn)的收益為r1=1 200,r2=2 000,r3=900。兩兩合作生產(chǎn)的收益為r12=3 500,r13=1 600,r23=3 300。三家企業(yè)合作生產(chǎn)的收益為r123=4 540。當(dāng)三家企業(yè)結(jié)成聯(lián)盟合作進(jìn)行生產(chǎn)時，應(yīng)如何分配聯(lián)盟的收益。

3.1 Shapley值法求解

Shapley值是目前應(yīng)用最廣的合作博弈解概念，它根據(jù)局中人i對聯(lián)盟S的邊際貢獻(xiàn)來確定對局中人i分配的收益，具體計(jì)算方式為：

Shapley值法是一種衡量局中人邊際貢獻(xiàn)的均值方法，體現(xiàn)了分配方式的公平性，但對于非凸博弈來說，不能保證聯(lián)盟的穩(wěn)定性（即不能保證滿足聯(lián)盟個體和子聯(lián)盟的合理性）。在本例中，由Shapley值計(jì)算得到局中人1的分配為1 180，小于其單干時的收益1 200，因此聯(lián)盟會由于局中人1的退出而破裂。

3.2 改進(jìn)連續(xù)蟻群算法求解

三家企業(yè)通過談判來分配收益。將連續(xù)蟻群算法的參數(shù)設(shè)置為理性因子在[0，1]范圍內(nèi)隨機(jī)取值，最大迭代次數(shù)mmax=500，控制因子初值θs=0，終值θe=1。

設(shè)企業(yè)i提出的分配方案為xi=(xi1,xi2,xi3)，各企業(yè)提出的分配方案需要滿足個體理性和有效性：

其中，x·j表示分配方案對企業(yè)j的分配。三家企業(yè)根據(jù)自身的偏好在約束條件下提出各自的初始分配方案，形成初始分配方案矩陣：

根據(jù)式（4）計(jì)算各分配方案的適應(yīng)度，按照適應(yīng)度從小到大的順序?qū)⒎峙浞桨复嫒胝勁袡n案中，談判檔案的形式為：

第一次談判后各分配方案的適應(yīng)度不等于0，迭代次數(shù)未達(dá)到預(yù)設(shè)的最大迭代次數(shù)。進(jìn)入下一輪談判，依次循環(huán)迭代134次，各分配方案的適應(yīng)度函數(shù)為0，談判檔案中的分配方案不再變化，求解得到的最終談判檔案為：

圖4 給出了談判檔案中適應(yīng)度最小的分配方案的適應(yīng)度的收斂曲線圖。結(jié)果表明，適應(yīng)度隨迭代次數(shù)不斷收斂，在迭代134次后趨于平穩(wěn)，三家企業(yè)的最終分配方案為[1 234.463 4，2 366.176 7，939.359 9]。

圖4 適應(yīng)度隨迭代次數(shù)收斂圖Fig.4 Value of optimal objective function varying with iteration times

算例表明：連續(xù)域蟻群算法經(jīng)過多次迭代后，談判檔案中的分配方案趨于一致并不再變化，即聯(lián)盟成員經(jīng)過多次談判可以得到一條使全體成員都滿意的分配方案，且該分配方案滿足個體理性和有效性。

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

為增加對比性，分析本文算法有效性，采用MATLAB R2018a進(jìn)行仿真實(shí)驗(yàn)，對原始連續(xù)蟻群算法和文獻(xiàn)[20]基于跨鄰域搜索的連續(xù)蟻群算法與本文改進(jìn)后的算法進(jìn)行分析對比，得出以下實(shí)驗(yàn)結(jié)果。各算法的適應(yīng)度收斂曲線如圖5所示。各算法實(shí)驗(yàn)數(shù)據(jù)如表1所示。

圖5 不同算法收斂曲線對比圖Fig.5 Comparison of convergence curves of different algrithms

表1 3種算法的實(shí)驗(yàn)數(shù)據(jù)Table 1 Experimental data of 3 algorithms

實(shí)驗(yàn)結(jié)果表明，在求解合作博弈問題時，相較于其他兩種算法，本文提出的改進(jìn)算法跳出局部極值的能力強(qiáng)，收斂速度快，收斂精度高。相較于原始連續(xù)蟻群算法易陷入局部最優(yōu)，收斂速度慢，收斂精度低等缺點(diǎn)，本文提出的考慮互動行為等改進(jìn)策略可以明顯提高算法的性能。

4 結(jié)束語

目前，合作博弈在理論研究和解概念的數(shù)量上取得了巨大發(fā)展，但有效的現(xiàn)實(shí)應(yīng)用依然偏少。產(chǎn)生這種情況的原因很多，其中一個根本性原因是沒有考慮現(xiàn)實(shí)博弈環(huán)境中聯(lián)盟分配方案的形成過程。這是目前合作博弈研究中被忽略的研究領(lǐng)域，但也是一個非常有潛力且與現(xiàn)實(shí)中的合作問題更加契合的研究領(lǐng)域?？紤]到現(xiàn)實(shí)中合作收益（成本、風(fēng)險等）的分配方案通常是經(jīng)過多輪的談判形成的，本文基于策略博弈理論和優(yōu)化思想將合作博弈求解處理為基于個體博弈與群體趨同的多目標(biāo)優(yōu)化問題，引入了理性因子和現(xiàn)實(shí)因子構(gòu)建考慮互動行為的合作博弈求解模型，提出了合作博弈的連續(xù)蟻群優(yōu)化算法對合作博弈進(jìn)行求解。相比合作博弈的經(jīng)典解概念，這種求解思路與方法可以更好地描述局中人之間的互動決策行為，更加符合現(xiàn)實(shí)中自然人的博弈過程。這為求解合作博弈提供了新的思路與方法，對現(xiàn)實(shí)中人們描述、分析和預(yù)測聯(lián)盟分配時具有決策支持作用。