泛集群環(huán)境下聯(lián)盟體形成方法研究

叢峰 劉瑞超

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

關(guān)鍵詞：泛集群;協(xié)同調(diào)度;聯(lián)盟體;博弈算法;萊維飛行粒子群算法

中圖分類號(hào)：TP273? ? ? ? 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1009-3044（2019）23-0195-05

開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（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 背景

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

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

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

2 基礎(chǔ)工作

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

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

[Umk]的性價(jià)比[bmUmk=vmUmk/tmk]，在此反應(yīng)了泛集群的個(gè)體理性為期望性價(jià)比最高，如公式（2）所示，其中[tmk]表示[Umk]完成[Tm]的預(yù)期完成時(shí)間。

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

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

[fx=argmaxbUmkbUmk=maxo

定義1.根據(jù)Branzei等[9]關(guān)于合作博弈模型的描述可知，聯(lián)盟體由若干個(gè)泛聯(lián)盟構(gòu)成，每個(gè)泛聯(lián)盟負(fù)責(zé)完成一個(gè)任務(wù)，聯(lián)盟體[M]要求滿足公式（4）描述。

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

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

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

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

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

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

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

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

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

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

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

3.1 問題的轉(zhuǎn)化

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

定義2.定義合作博弈[GSn，vU]的分配向量[x=IvSmk，U]，任意成員[Sc，Sι∈U]。 [Sc]對(duì)[Sι]的異議可表示為[Pιc，y]，其中[Pιc]表示一組泛聯(lián)盟，[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]對(duì)[Sι]的任何異議都不存在反異議，記做[Sc?nxSι]。因此合作博弈G[Sn，vU，M]的Mas-Colell談判集為如下集合：[MC=Sc?nxSι，MC∈U]。

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

對(duì)問題進(jìn)一步描述：取談判基礎(chǔ)聯(lián)盟[Smk]，根據(jù)公式（1）可知[xs=p-e+c]，[p]恒定，于是求解[vmaxMs]等價(jià)于求解期望[maxxs≡minm1em，k+cm，k]。根據(jù)公式（2）引入高性價(jià)比因子，得到距離公式[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）給出目標(biāo)函數(shù)如公式（12）所示。

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

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

3.2 L-PSO的求解算法描述

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

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

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

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

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

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

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

2） 給出加入慣性權(quán)重的基本粒子群形式。

已知泛集群數(shù)量[N=Sn]，粒子數(shù)量為P，由所有聯(lián)盟結(jié)構(gòu)的分配向量組成離散點(diǎn)集合[X]，則第[j]個(gè)粒子[j

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

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

為了防止速度過快而直接飛過最優(yōu)解，算法引入[?]表示慣性權(quán)重用于決定粒子的當(dāng)前速度;給定[c1，c2∈0，2]表示學(xué)習(xí)因子，表示向全局最優(yōu)的學(xué)習(xí)能力;均勻隨機(jī)數(shù)[ζ，η=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）

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

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

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

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

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

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

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

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

[pgworst]表示上一次迭代的劣勢(shì)解，[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)定聯(lián)盟體[Ms-best]，算法的詳細(xì)計(jì)算步驟如算法2描述。

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

4 實(shí)驗(yàn)對(duì)比

4.1 實(shí)驗(yàn)準(zhǔn)備

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

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

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

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

4.2 算法性能的對(duì)比分析

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

4.2.1 搜索速度測(cè)試（平均計(jì)算時(shí)間對(duì)比）

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

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

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

隨機(jī)選擇并記錄10次測(cè)試過程，三種測(cè)試實(shí)例通過L-PSO和DE算法計(jì)算獲得的平均聯(lián)盟體效用和標(biāo)準(zhǔn)差如表2所示。由表2數(shù)據(jù)可知，對(duì)于測(cè)試實(shí)例SEVR和OBR25，L-PSO算法獲得的平均聯(lián)盟體效用始終高于DE算法;而對(duì)于測(cè)試實(shí)例OBR40，L-PSO算法獲得的平均聯(lián)盟體效用普遍略低于DE算法。

表3給出了三種測(cè)試實(shí)例在兩種算法中的8項(xiàng)重要測(cè)試數(shù)據(jù)，其中聯(lián)盟體效用極值[vmaxM]作為衡量求解質(zhì)量的標(biāo)準(zhǔn)，[vmaxM]越大，優(yōu)化質(zhì)量越出色;方差[Λ]描述了算法的絕對(duì)穩(wěn)定性，[Λ]越小，算法的絕對(duì)穩(wěn)定性越高。

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

4.2.3 收斂性測(cè)試

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

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

4.3 不同理性因子的效果對(duì)比

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

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

5 結(jié)束語

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

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

參考文獻(xiàn)：

[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] 桂海霞， 蔣建國(guó)， 張國(guó)富. 面向并發(fā)多任務(wù)的重疊聯(lián)盟效用分配策略[J]. 模式識(shí)別與人工智能， 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ìn)粒子群算法[J]. 系統(tǒng)仿真學(xué)報(bào)， 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.

【通聯(lián)編輯：謝媛媛】