叢峰 劉瑞超

摘要：在采用智能體結盟的方式解決多目標約束下的合作計算調度問題通時，提出了一種提高聯盟體形成效率和可靠性的方法。首先，為定量化描述聯盟體的優(yōu)劣性，將談判集約束條件和聯盟基本理性期望作為適應度函數;其次，引入萊維飛行粒子群算法求解最優(yōu)聯盟體結構，以保證求解速度和最優(yōu)解質量;最后，通過算法性能測試驗證了方法在求解效率和可靠性方面具有明顯改善。

關鍵詞：泛集群;協同調度;聯盟體;博弈算法;萊維飛行粒子群算法

中圖分類號：TP273? ? ? ? 文獻標志碼：A

文章編號：1009-3044（2019）23-0195-05

開放科學（資源服務）標識碼（OSID）：

A Method for Coalition Structure Generation Under the Generalized-Cluster Environment

CONG Feng， LIU Rui-chao

（Daqing Oil Company Exploration & Development Research Institute， Daqing 163000， China）

Abstract： The scheduling problem under multi-objective constraint is usually solved using the agent coalition. In this paper， a method to improve the efficiency and reliability of the coalition structure is presented. First， to improve the solving speed and the optimal solution quality， the constraint conditions of the bargaining set and the coalition's basic rational expectation are taken as the fitness function. Second， the particle swarm optimization algorithm based on Levy flight is introduced to solve the optimal coalition structure. Finally， the availability of the method in solving efficiency and reliability is verified according to the experiment simulation and test in terms of convergence， effective rejection rate， algorithm performance and other aspects.

Key words： Generalized-Cluster; co-allocating scheduling; cooperation game; Coalition Structure; Levy-flight PSO

1 背景

泛聯盟是一組為完成特定任務而形成的泛集群集合，它為泛集群解決大規(guī)模科學計算問題提供了一種重要的合作方式[1]。作為一個動態(tài)性的概念，泛聯盟隨著新任務的到來而產生，又隨著任務的完成而解體。有關泛聯盟形成的研究本質是解決智能體自組織機制設計問題，科研人員熱衷于采用啟發(fā)式最優(yōu)解算法和合作博弈理論等方式解決這一問題，尤其是在多任務多目標約束的條件下如何求解最優(yōu)泛聯盟結構 （聯盟體）。

采用啟發(fā)式最優(yōu)解算法的基本思想是枚舉全部可能得到的聯盟體，通過編碼等方式轉換為可描述的對象，并由全局或局部最優(yōu)解快速算法獲取最好的泛聯盟結構。Ali.M等[2]提出了一種高效的差分進化算法求解多目標約束的最優(yōu)配置問題，雖然計算速度快、收斂性強，但在解決多目標約束的離散點問題時，最優(yōu)解的質量無法保證;Zhao Q和Zhang L Y [3]研究了離散粒子群算法（DPSO）在團隊選擇優(yōu)化中的應用，由于考慮了離散點的局部聚集問題使得求解質量更高，但應對大量離散點時候體現出算法自身的不穩(wěn)定性;張國富[4-7]近年來一直深入這一領域的研究，并在求解重疊聯盟、最大成功聯盟等問題上成果頗豐，但解決泛集群成員穩(wěn)定性的能力相對不強。

為解決上述問題，引入并改進萊維飛行粒子群算法[8] （Levy-flight PSO，L-PSO） 以提高求解的質量和穩(wěn)定性。第二部分闡述了基礎工作并提出需要解決的核心問題;第三部分討論了基于L-PSO的最優(yōu)聯盟體求解過程;第四部分通過收斂性測試、性能分析、剔除率測試等實驗證明了方法在求解的效率和質量方面具有明顯改善;第五部分總結研究成果。

2 基礎工作

構建生態(tài)場景：非超可加環(huán)境H由泛集群集合[Sn]構成，[Tm]表示一組大規(guī)?？茖W計算任務，[Tm]將由多個泛集群以聯盟形式完成，記作[Umk=N，v]。這一場景需要三個前提：1）允許[m=1];2）[Sn]在某一時刻或階段內只能參與一個泛聯盟，即僅存在完全參與或完全不參狀態(tài); 3）[Tm]是可并發(fā)的。[Umk]在完成任務后將獲得一定的效用[vmUmk]，[vmUmk]的特征函數可表示為公式（1）形式。

[vmUmk=pTm-cUmk-eUmk]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （1）

[Umk]的性價比[bmUmk=vmUmk/tmk]，在此反應了泛集群的個體理性為期望性價比最高，如公式（2）所示，其中[tmk]表示[Umk]完成[Tm]的預期完成時間。

[fx=argmaxbmUmkbmUmk=pTm-cUmk-eUmk/tmk]? ? ? ? （2）

定義表示[Umk]在完成[Tm]中所能獲得的最大效用值（也成為聯盟值[14，16]），即。更新公式（2）得到個體理性期望如公式（3）描述。

[fx=argmaxbUmkbUmk=maxo

定義1.根據Branzei等[9]關于合作博弈模型的描述可知，聯盟體由若干個泛聯盟構成，每個泛聯盟負責完成一個任務，聯盟體[M]要求滿足公式（4）描述。

[?M=U1…UdUi?Ut=?，i≠t，Ui，Ut∈UdUdc=1Uc=R]? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（4）

所有可能形成的聯盟體集合表示為[Ms]，定義[xs=x1s，x2s…xns]表示由[Ms]的所有成員獲得的效用構成的一個分配向量。已知聯盟體必然滿足集體理性，具體表現為：1）所有效用需分配給所有的泛集群成員（如公式（5）所示）;2）聯盟體總是期望總支出[om]最少（如公式（6）所示）。

[xs=pTm-cUmk]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（5）

[argminomk，omk=cUmk+eUmk]? ? ? ? ? ? ? ? ? ? ? ? ? （6）

在泛集群環(huán)境下，[vmUmk]為非超可加的[2]，理論可形成的泛聯盟數量為[count=2n]。

由合作博弈理論可知，聯盟體的基本理性期望要求同時滿足個體理性和集體理性[10]。根據公式（3）、（5）、（6）給出聯盟基本理性期望可描述為公式（7）形式。

[Rb=pm，k=fxgm，k=∑pTm-cUmkhm，k=argmincUmk+eUmk]? ? ? ? ? ? ?（7）

為描述成員（泛集群）的傾向意圖，引入理性因子[ωRb=ωp，ωg，ωh]，[ωp+ωg+ωh=1]作為衡量理性期望的指標，定義閾值[?]，給出基本理性期望函數如公式（8）所示。

[fRb=ωp×pm，k+ωg×gm，k+ωh×hm，k]? ? ? ? ?（8）

泛聯盟既定所有的效用均分配給所有成員，為降低[ωg]的影響，設定[ωg=0.1]。[ωp，ωh]分別表達了聯盟體的主觀意愿，根據公式（2）可知：[ωp]體現了個體理性，當[ωp]變大時，個體成本支出將降低，但是聯盟合作支出將提高，即[ωp↑→cUmk↓，eUmk↑];[ωh]反應了聯盟理性，當[ωh]變大時，個體成本支出將提高，但是聯盟合作支出將降低，即[ωh↑→cUmk↑，eUmk↓]。效用分配向量直接反應泛集群的意圖，并將決定聯盟體結構。因此，如何快速準確的求解最穩(wěn)定分配向量問題是需要解決的核心問題之一。

3 最穩(wěn)定聯盟體的選擇

3.1 問題的轉化

最穩(wěn)定分配向量決定最終的聯盟體結構。將談判集約束作為最優(yōu)聯盟求解的適應性函數，從場景[H]的角度給出定義2。

定義2.定義合作博弈[GSn，vU]的分配向量[x=IvSmk，U]，任意成員[Sc，Sι∈U]。 [Sc]對[Sι]的異議可表示為[Pιc，y]，其中[Pιc]表示一組泛聯盟，[Sc?Pιc，Sι∈Pιc]。于是[Pιc]的分配向量[y]必然滿足：[yPιc=vPιc，yi>xi，i∈Pιc]。[Pιc，y]的反異議可表示為[Pιz，z]，[Sl?Pιz，Sc∈Pιz]，于是[Pιz]的分配向量[z]必然滿足：[zPιz=vPιz，zi>yi，zj>xj，i∈Pιc?Pιz，j∈Pιc＼Pιz]。

如果[?Pιc→Pιz=?]，則表示[Sc]對[Sι]的任何異議都不存在反異議，記做[Sc?nxSι]。因此合作博弈G[Sn，vU，M]的Mas-Colell談判集為如下集合：[MC=Sc?nxSι，MC∈U]。

[MC]的求解使泛聯盟的基數[?2n]，對[MC]的所有成員進行降序排列，搜索可以覆蓋全部成員的聯盟組合，取其成員密度最高的[h]項即構成[Ms]。因此問題2可以描述為以[Ms]為樣本，求分配向量[xs]的似然最優(yōu)解問題，等價于求解效用最高的聯盟結構體（即[vmaxMs]）的問題。

對問題進一步描述：取談判基礎聯盟[Smk]，根據公式（1）可知[xs=p-e+c]，[p]恒定，于是求解[vmaxMs]等價于求解期望[maxxs≡minm1em，k+cm，k]。根據公式（2）引入高性價比因子，得到距離公式[disc，e=em，k/tmk+cm，k/tmk]。

[xs]可由[em，k，cm，k]表示為

[xs=e11+c11…em1+cm1???e1k+c1k…ekk+ckk]

以[em，k，cm，k]分別表示[xs]的空間位置。令[em，k>1，cm，k>1]，由公式（7）、公式（8）給出目標函數如公式（12）所示。

[fRb=ωp×argmaxbUmk+ωg×pTm-cUmk+ωh×argmincUmk+eUmk]? ? （12）

于是最穩(wěn)定分配向量的求解問題最終可以描述為：搜索以公式（12）為目標函數的最優(yōu)解問題。

3.2 L-PSO的求解算法描述

PSO算法是一種基于群體智能的全局隨機搜索算法，具有規(guī)則簡單、實現容易、精度高和收斂快等特點[11]。在解決最優(yōu)團隊選擇問題方面，與差分進化 （Differential Evolution，DE） 算法相比，PSO算法具有以下優(yōu)勢：PSO算法的全局收斂能力相比較弱，但求解離散點最優(yōu)解問題的能力較強[11];離散粒子群算法能夠更好地解決具有局部聚集特征的最優(yōu)團隊選擇問題[12];PSO算法更加成熟，參數設置難度較低，并能夠更好地保證求解質量。

基本的PSO算法往往會陷入局部最優(yōu)，需要引入一種策略擴大搜索范圍，增加種群多樣性。采用L-PSO的算法作為最穩(wěn)定分配向量的求解算法，對基于L-PSO的算法改進和應用過程描述如下：

1） 初始種群的編碼過程及表達形式。

[Ms]集合的第i個元素[Mi][Mι]的分配向量可表示為

[Mι=ΔTmx1ix2i?xmiΔS1ΔS2…ΔSnc1i1+e1i1c1i2+e1i2…c1in+e1inc2i1+e2i1c2i2+e2i2…c2in+e2in??…?cmi1+emi1cmi2+emi2…cmin+emin]

[ΔSn]表示[Sn]用于聯盟的支出和任務的開銷，當[cpik+epik=0，p∈1，m，k∈[1，n]]時，表示[Sk]不參與完成[Tp]。于是[Ml]的編碼規(guī)則可描述為：

[Mι=x1i，…，xmi，…，]。

2） 給出加入慣性權重的基本粒子群形式。

已知泛集群數量[N=Sn]，粒子數量為P，由所有聯盟結構的分配向量組成離散點集合[X]，則第[j]個粒子[j

[Vjd+1=vVjd+c1ζpjd-Xjd+c2ηpgd-Xjd]? ? （13）

[Xjd+1=Xjd+Vjd+1]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（14）

為了防止速度過快而直接飛過最優(yōu)解，算法引入[?]表示慣性權重用于決定粒子的當前速度;給定[c1，c2∈0，2]表示學習因子，表示向全局最優(yōu)的學習能力;均勻隨機數[ζ，η=Rand0，1];[Vjd+1]取決于[Vjd，pjd，pgd]。

3） 離散化L-PSO算法。

由于[X]為非連續(xù)的樣本集合，因此首先給出PSO算法的離散化表述形式如公式（15）-（16）所示。

[Vjd+1=vVjd+c1ζpjd-Xjd+c2ηpgd-Xjd]? ?（15）

[Xjd+1=Xjd⊕Vjd+1]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（16）

作為一種非高斯隨機過程，萊維飛行[4，12-14]具有以下特點：發(fā)生長程跳遠[14];具有馬爾可夫性質[15];過程隨機性[15]。萊維飛行可描述為公式（17）形式。

[Ls，γ，μγ2π×exp-γ2s-μ×s-μ320<μ

其中[μ]為位移參數，[γ>0]為尺度參數，將其離散化并得到公式（18）形式。

[Xjd+1=Xjd+ξ⊕Ls，γ，μ]? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（18）

其中[Ls，γ，μ]決定行進方向和步長，轉移概率[ξ]和[d]代位置將決定[d+1]代的位置。以公式（19）模擬萊維分布的隨機搜索路徑并進一步離散化[Ls，γ，μ]。

[Ls，γ，μ=μ/u1β]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （19）

給定[β=1.5][13]，因此離散萊維飛行可更新為公式（20）描述形式。

[Xjd+1=Xjd+ξ⊕0.01μu1βXjd+1-pgworst]? ? ? ? ? ? （20）

[pgworst]表示上一次迭代的劣勢解，[W：N0，1]，[β：N0，σ2μ]。公式（20）的目的是增加種群多樣性，為保證這種多樣性，以[Xjd+1-pgworst]作為交換序集合[W]，[W]中因子發(fā)生的概率[Prob]將由因子[τ=μu1β]決定，并可表示為公式（21）。

[Prob=τ/Stepsizemax-Stepsizemin]? ? ? （21）

其中[Stepsizemax=maxτ，Stepsizemin=minτ]，至此完成L-PSO的離散化。

4）給出基于L-PSO的最穩(wěn)定聯盟體[Ms-best]，算法的詳細計算步驟如算法2描述。

[算法2 L-PSO的最穩(wěn)定聯盟體選擇 Input [U，c1，c2，d，X] Output [Ms-best] 1： Begin 2： define [pgworst，pj，pg，V]; 3： for d

4 實驗對比

4.1 實驗準備

1）樣本描述：在油田化學化工領域，計算高分子準晶體納米結構的弱互斥力對分子穩(wěn)定性的影響程度時，通常選用[OBR25]（6，12，15）、[OBR40]（24，6，6）和[SEVR]（12，3，30）作為弱互斥力計算函數，括號內數值分別表示這三種函數的維度（[dimensionality，dim]）、階數（[power，pow]）、單次線性操作數（[operation，op]）。三種函數的維度、階數和單次線性操作數差別較大，實驗對比效果明顯，具有一定的代表性，因此選用這三種函數作為實驗的測試實例。設定整體任務的總效用為100，可分解為7個獨立任務，給出第m個獨立任務[Tm]的效用為：

[pTm=3m，m∈1，637，m=7]

2）環(huán)境構建：在一個由兩級交換機組成的網絡覆蓋區(qū)域內，每一個二級交換機及下屬的所有工作終端可視為一個泛集群，共計18個泛集群。

3）算法的基本參數設置：除理性因子的影響力實驗外，設定理性期望絕對傾向聯盟理性，即[ωp=0.2]、[ωh=0.7];在剔除談判無關聯盟的實驗中，初始隨機點數量的取值范圍[v∈2，18]，累計17次實驗;在L-PSO算法的性能測試實驗中，設定學習因子[c1，c2]為均勻隨機數[Rand0，2]，飛行最大速度[vmax=90]，慣性權重為0.4，迭代次數[d=1000]。

4.2 算法性能的對比分析

選用差分進化算法（Differential Evolution， DE）[2]作為對比算法，其應用場景和求解意圖與L-PSO算法相似。兩種算法的對比測試包括搜索速度測試、求解質量和穩(wěn)定性測試及收斂性測試。

4.2.1 搜索速度測試（平均計算時間對比）

隨機選擇并記錄10次測試過程，三種測試實例在L-PSO和DE算法中的平均計算時間及±95%置信區(qū)間[5]時間如表1所示（單位為毫秒）。

由表1數據可知，L-PSO算法計算測試實例SEVR的平均時間略低于DE算法，表明L-PSO算法計算高操作數的測試實例速度更快;兩種算法計算測試實例OBR25的平均時間基本一致，說明兩種算法對于高階測試實例的計算速度是相同的;而對于高維度的測試實例OBR40，L-PSO算法的計算時間明顯高于DE算法。

4.2.2 求解質量和穩(wěn)定性測試

隨機選擇并記錄10次測試過程，三種測試實例通過L-PSO和DE算法計算獲得的平均聯盟體效用和標準差如表2所示。由表2數據可知，對于測試實例SEVR和OBR25，L-PSO算法獲得的平均聯盟體效用始終高于DE算法;而對于測試實例OBR40，L-PSO算法獲得的平均聯盟體效用普遍略低于DE算法。

表3給出了三種測試實例在兩種算法中的8項重要測試數據，其中聯盟體效用極值[vmaxM]作為衡量求解質量的標準，[vmaxM]越大，優(yōu)化質量越出色;方差[Λ]描述了算法的絕對穩(wěn)定性，[Λ]越小，算法的絕對穩(wěn)定性越高。

對于測試實例SEVR和OBR25，L-PSO算法獲得的最優(yōu)聯盟體效用極值相比DE算法提高了8%-10%，表明L-PSO算法在低維度測試實例的優(yōu)化質量優(yōu)于DE算法;對于測試實例OBR40，L-PSO算法獲得的最優(yōu)聯盟體效用極值相比DE算法下降了2.4%，表明DE算法在高維度測試實例的優(yōu)化質量略優(yōu)于L-PSO算法;兩種算法的[Λ]值相差幅度小于4%，表明兩種算法的絕對穩(wěn)定性差異較小，但L-PSO算法的[Λ]值最小，表明其絕對穩(wěn)定性略優(yōu)于DE算法。

4.2.3 收斂性測試

根據表3進一步分析兩種算法的收斂性：定義取得極值前相鄰兩次聯盟體效用差值[εa，a-1=va-va-1];極值差[E=vmaxM-vminM]，反應了算法的相對穩(wěn)定性;第[a]次迭代的峭度[K=εa，a-1/E]，峭度越小，收斂性越好。

取誤差[ε=vmaxM-vaMvmaxM<0.005]，表4給出在取得極值時的測試結果，分析并給出如下說明：（1）在不同的測試實例中，DE算法的峭度值始終高于L-PSO算法，說明DE算法的收斂性略高于L-PSO算法;（2）L-PSO算法的極值差[E]始終小于DE算法，說明L-PSO的相對穩(wěn)定性高于DE算法。

4.3 不同理性因子的效果對比

分別測試在不同主觀意愿下，不同泛集群數量組成最優(yōu)聯盟體的效用情況。測試要求保持任務數量不變;泛集群數量[k∈7，18];參與測試的主觀意愿傾向集合如表4所示。L-PSO算法對維度較為敏感，同時高階數的測試實例將使實驗的時空復雜度呈幾何級數增長，加重了實驗噪音因素的影響，因此綜合考慮選用維度較高、階數較低的SEVR作為不同理性因子的效果對比實驗的測試實例。

測試結果如圖1所示，[vmaxM]出現的位置取決于泛集群的數量和[ωh]值，因此可以得到以下結論：聯盟理性傾向越高，越適合泛集群數量多的環(huán)境;[vmaxM]的極大值將出現在[ωp?ωh]時，此時聯盟體的穩(wěn)定性和性價比最高;此外，不同理性因子所取得的[vmaxM]浮動不大，說明基本理性期望滿足的主觀意圖是聯盟理性。

5 結束語

作為一種新型計算環(huán)境，泛集群將成為未來普適計算解決大規(guī)模科學計算問題的重要手段，而解決多個泛集群間的協同作業(yè)問題也是推進這一領域發(fā)展的重要研究內容。本文以泛聯盟的形成為背景，研究最優(yōu)聯盟體的求解方法，并通過實例測試驗證了方法的有效性，為解決多任務下的多集群協作問題提供了一種新的解決方案。

本文提出的方法在應對談判反噬效應和解決局部離散點聚集問題依舊存在有待完善之處，例如如何找到最優(yōu)[v]解和聚集特征因素的搜索等，這也是下一步需要繼續(xù)研究的課題。

參考文獻：

[1] Ueda S， Iwasaki A， Conitzer V， et al. Coalition structure generation in cooperative games with compact representations[J]. Autonomous Agents and Multi-Agent Systems， 2018（6）： 1-31.

[2] Ali M， Siarry P， Pant M. An efficient Differential Evolution based algorithm for solving multi-objective optimization problems[J]. European Journal of Operational Research， 2018， 217（2）： 404-416.

[3] Zhao Q， Zhang L Y. Research on the Effect of DPSO in Team Selection Optimization under the Background of Big Data[J]. Complexity， 2018， 2018（8）： 1-14.

[4] 桂海霞， 蔣建國， 張國富. 面向并發(fā)多任務的重疊聯盟效用分配策略[J]. 模式識別與人工智能， 2016， 29（4）： 332-340.

[5] Zhang G F， Su Z， Li M， et al. A Task-Oriented Heuristic for Repairing Infeasible Solutions to Overlapping Coalition Structure Generation[J]. IEEE Transactions on Systems Man & Cybernetics Systems， 2017， （99）： 1-17.

[6] Liu Y， Zhang G F， Su Z P， et al. Using Computational Intelligence Algorithms to Solve the Coalition Structure Generation Problem in Coalitional Skill Games[J]. Journal of Computer Science and Technology， 2016， 31（6）： 1136-1150.

[7] Zhang G， Yang R， Su Z， et al. Using binary particle swarm optimization to search for maximal successful coalition[J]. Applied Intelligence， 2015， 42（2）： 195-209.

[8] Hakl? H， U?uz H. A novel particle swarm optimization algorithm with Lévy flight[J]. Applied Soft Computing Journal， 2014， 23（5）： 333-345.

[9] Branzei R， Dimitrov D， Tijs S. Models in Cooperative Game Theory[M]. Springer Berlin Heidelberg， 2005.

[10] Goyal T， Kaushal S. An Intelligent Scheduling Scheme for Real-Time Traffic management using Cooperative Game Theory and AHP-TOPSIS methods for Next Generation Telecommunication Networks[J]. Expert Systems with Applications， 2017（86）： 125-134.

[11] Pandit D， Zhang L， Chattopadhyay S， et al. A Scattering and Repulsive Swarm Intelligence Algorithm for Solving Global Optimization Problems [J]. Knowledge-Based Systems， 2018（156）： 12-42.

[12] 李榮雨， 王穎. 基于萊維飛行的改進粒子群算法[J]. 系統仿真學報， 2017， 29（8）： 1685-1691.

[13] Chechkin A V， Metzler R， Klafter J， et al. Introduction to the theory of Lévy flights[C]. Anomalous Transport： Foundations and Applications. Weinheim： John Wiley Sons， 2008： 129-162.

[14] Yang X S. Cuckoo search via Lévy flights[C]. World Congress on Nature & Biologically Inspired Computing. Coimbatore： IEEE， 2009： 210-214.

[15] Souidi M， Piao S， Li G， et al. Coalition formation algorithm based on organization and Markov decision process for multi-player pursuit evasion[J]. Multiagent & Grid Systems， 2015， 11（1）： 1-13.

【通聯編輯：謝媛媛】