合作博弈的連續蟻群算法求解

李壯闊，常凱旋

桂林電子科技大學 商學院，廣西 桂林541004

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

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

現實中聯盟最終分配方案的達成通常是局中人基于個體理性與判斷進行多輪談判，互相影響、相互妥協、最終趨同的結果。對此，本文將合作博弈的求解過程視作局中人個體博弈和群體趨同的多目標優化問題。考慮到談判過程中局中人的個體調整和群體趨同行為，引入分配方案、理性因子與控制因子等現實影響因素，構建考慮互動行為的合作博弈模型。在此過程中，對傳統連續優化蟻群算法進行改進，提出合作博弈的連續蟻群優化算法對合作博弈模型進行求解。

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

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

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

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

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

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

在談判過程中，局中人對某條分配方案的評價標準主要考慮兩個要素，即個體最優信息和群體平均信息。

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

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

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

在談判過程中，本文采用談判檔案作為局中人間的信息交流機制，從而實現局中人在談判過程中的互動行為。采用這種非直接通信的方式好處在于當局中人的數目增加時，整個系統的通信開銷的增幅較小，使得群體智能算法具有較好的擴展性。談判檔案的結構包括分配方案和適應度兩個部分。談判檔案的構造過程為：通過適應度函數計算分配方案的適應度，按照適應度從小到大的順序對分配方案排序，將分配方案和適應度存入談判檔案中。具體形式如圖1所示。

圖1 談判檔案結構Fig.1 Structure of solution archive

定義4群體最優信息為使聯盟群體最滿意的一條分配方案，即適應度最小的分配方案，也是談判檔案中第一條分配方案，記為局中人對個體最優信息的學習表示為

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

定義6局中人的控制因子θm(θm∈[0,1])表示局中人對個體最優信息和群體最優信息的偏重程度，體現了不同談判階段局中人對個體最優和群體最優追求的變化。通常局中人在談判前期更追求個體最優分配，在談判后期為了維持聯盟而更側重群體最優分配。較大的控制因子可以提高全局搜索能力，避免陷入局部最優，較小的控制因子可以提高局部開發能力，從而加快收斂速度。控制因子的取值方式有線性策略和非線性策略兩類，采用線性策略會使得控制因子在迭代過程中呈線性變化，易使收斂速度過慢和陷入局部最優，無法適應實際情況。本文采用一種反余弦的非線性策略來調整控制因子，基本思想是前期加快控制因子的改變速度，從而較快地進入局部搜索，避免陷入局部最優，后期通過較大的控制因子使算法更注重群體信息，保持解的多樣性。反余弦控制因子構造方式如下：

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

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

通過控制因子對迭代次數m求導可知控制因子的變化速度為：

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

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

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

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

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

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

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

2 合作博弈的連續蟻群算法求解

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

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

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

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

步驟2所有局中人提出初始分配方案，為了使各局中人不會因為對分配方案不滿而退出聯盟，局中人提出的分配方案必須滿足個體理性和有效性。所有分配方案構成了分配方案矩陣X0。

步驟3計算分配方案的適應度，排序后存入談判檔案中。通過式（4）計算分配方案的適應度，按照適應度從小到大的順序對分配方案進行排序，將排序后的分配方案存儲在談判檔案中，此時談判檔案中分配方案的適應度滿足，根據談判檔案計算個體最優信息和群體最優信息。

步驟4判斷談判檔案中分配方案的適應度是否相等且為0。若是，此時談判檔案中所有分配方案相同，得到最優分配方案，迭代結束。否則，進入下一步。

步驟5判斷是否達到預設的最大迭代次數。若達到最大迭代次數，無法取得令所有局中人都滿意的最優分配方案，停止迭代，輸出談判檔案；否則，進入下一步。

步驟6構建新的分配方案。根據當前的個體最優信息和群體最優信息調整談判檔案中的分配方案，通過式（6）計算局中人的調整值，通過式（7）計算局中人的調整后的分配方案。轉至步驟3。

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

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

3 算例分析

三家企業決定建立聯盟生產某種產品投入市場，單獨生產的收益為r1=1 200,r2=2 000,r3=900。兩兩合作生產的收益為r12=3 500,r13=1 600,r23=3 300。三家企業合作生產的收益為r123=4 540。當三家企業結成聯盟合作進行生產時，應如何分配聯盟的收益。

3.1 Shapley值法求解

Shapley值是目前應用最廣的合作博弈解概念，它根據局中人i對聯盟S的邊際貢獻來確定對局中人i分配的收益，具體計算方式為：

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

3.2 改進連續蟻群算法求解

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

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

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

根據式（4）計算各分配方案的適應度，按照適應度從小到大的順序將分配方案存入談判檔案中，談判檔案的形式為：

第一次談判后各分配方案的適應度不等于0，迭代次數未達到預設的最大迭代次數。進入下一輪談判，依次循環迭代134次，各分配方案的適應度函數為0，談判檔案中的分配方案不再變化，求解得到的最終談判檔案為：

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

圖4 適應度隨迭代次數收斂圖Fig.4 Value of optimal objective function varying with iteration times

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

3.3 實驗結果分析

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

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

表1 3種算法的實驗數據Table 1 Experimental data of 3 algorithms

實驗結果表明，在求解合作博弈問題時，相較于其他兩種算法，本文提出的改進算法跳出局部極值的能力強，收斂速度快，收斂精度高。相較于原始連續蟻群算法易陷入局部最優，收斂速度慢，收斂精度低等缺點，本文提出的考慮互動行為等改進策略可以明顯提高算法的性能。

4 結束語

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