三元概念分析的聯(lián)盟應(yīng)用研究

王紅敏,張 卓,王黎明

(鄭州大學(xué) 信息工程學(xué)院,鄭州 450001)

1 引 言

隨著網(wǎng)絡(luò)技術(shù)的飛速發(fā)展,互聯(lián)網(wǎng)中涌現(xiàn)出了越來越多的三維數(shù)據(jù).1995年,Wille R.等受實(shí)用主義哲學(xué)的啟發(fā)把FCA(形式概念分析)擴(kuò)展到三元背景下,提出了三元概念分析.Lehmann.和Wille 在文獻(xiàn)[1]中首次定義了三元背景、三元概念和概念三元格.文獻(xiàn)[2]介紹了如何從三元圖中讀出不同的信息.文獻(xiàn)[3]提出了一種構(gòu)造三支概念的算法CbO3C.文獻(xiàn)[4]介紹了三支概念與經(jīng)典形式概念的關(guān)系,并且在經(jīng)典形式背景給出了兩種具體的三支概念模型.文獻(xiàn)[5]從三支決策的視野探究不同概念格之間的內(nèi)在聯(lián)系.文獻(xiàn)[6]梳理了三元概念分析的研究現(xiàn)狀及發(fā)展趨勢(shì).文獻(xiàn)[7]研究了概念三元格的構(gòu)造算法及其在folksonomy分類中的應(yīng)用.文獻(xiàn)[8]研究了三元概念分析在文本分類中的應(yīng)用.

關(guān)于經(jīng)典的合作博弈,已經(jīng)存在諸多相關(guān)研究并且廣泛的應(yīng)用在多智能體協(xié)作[9,10-12]等領(lǐng)域.合作博弈的第一個(gè)主要問題是參與者如何結(jié)盟.然而,在大多數(shù)情況下,并不是N的所有子集都可以構(gòu)成一個(gè)聯(lián)盟或者是可行的,這就意味著效用函數(shù)只是映射在2N的子集F上.Aumann和Dreze[13]針對(duì)該情況提出了聯(lián)盟結(jié)構(gòu).Faigle和Kern[15]提出了限制合作.F在分布格(在交和并下封閉)[15]、凸代數(shù)[16]等一些結(jié)構(gòu)的假設(shè)中被研究.與以往研究不同的是,本文基于參與者所擁有的資源,提出受限合作博弈,在這種條件下,經(jīng)典的Shapley值將不再適用,需要重新定義.2014年,Faigle U[17]等人提出了基于概念格的博弈,但他只是從數(shù)學(xué)層面給出了一些定理,并沒有指出相關(guān)的應(yīng)用以及算法的實(shí)現(xiàn).因此本文借鑒形式概念分析上的博弈以及結(jié)合作為處理分析數(shù)據(jù)新框架的三元概念分析的特點(diǎn),提出了受限合作博弈,并且結(jié)合三元概念分析與合作博弈的特點(diǎn),提出了受限合作博弈的聯(lián)盟形式的形成算法LMXC,以及效用值分配G-shapley值法.

2 相關(guān)理論

2.1 三元概念分析基本理論

三元概念分析作為形式概念分析的推廣,是一種新的信息處理的概念和計(jì)算范式,它能夠有效的處理三維數(shù)據(jù).網(wǎng)絡(luò)上的三維數(shù)據(jù)可以表示為三維二值表,根據(jù)相應(yīng)算子的計(jì)算推理,進(jìn)而得到所有的三元概念.

定義1.[6](三元背景):三元背景被定義為四元組(G,M,B,Y),其中G是對(duì)象集合,M是屬性集合,B是條件集合,Y是G、M和B之間的三元關(guān)系,且Y?G×M×B,(g,m,b)∈Y表示對(duì)象在條件b下具有屬性m.

定義3.[6]((i)-誘導(dǎo)算子):三元背景K=(K1,K2,K3,Y),{i,j,K}={1,2,3},滿足j

X→X(i):={(aj,ak)∈Kj×Kk|(ai,aj,ak)∈Y,?ai∈X}

Z→Z(i):={ai∈Ki|(ai,aj,ak)∈Y,?(aj,ak)∈Z}

定義4.(預(yù)序和等價(jià)關(guān)系):三元背景K=(K1,K2,K3,Y),S為三元背景下所有三元概念的集合,對(duì)于任意的(A1,A2,A3)∈S,(B1,B2,B3)∈S,定義預(yù)序關(guān)系≤i和等價(jià)關(guān)系～i為:

(A1,A2,A3)≤i(B1,B2,B3) Ai? Bi,

(A1,A2,A3)～i(B1,B2,B3) Ai= Bi,

i={1,2,3}.

2.2 合作博弈

用N={1,…,n}表示有限個(gè)參與者的集合,在這n人的博弈中,N的任何一個(gè)子集S就作為一個(gè)聯(lián)盟,與結(jié)盟相關(guān)的是特征函數(shù).空集Φ和全集N也可以稱作聯(lián)盟,單點(diǎn)集{i}仍是一個(gè)聯(lián)盟.然而,在多數(shù)情況下,合作是受限的,比如當(dāng)只有他人加入到此聯(lián)盟時(shí)一些人才加入該聯(lián)盟.本文我們考慮一般情況,即合作是受限的.

一個(gè)合作博弈(F,ν),對(duì)于任意一個(gè)S?N的聯(lián)盟,一個(gè)分配向量就是一個(gè)向量x∈Rn,對(duì)每個(gè)參與人i∈N分配一個(gè)實(shí)值參數(shù),形成n維向量x={ x1,…,xn}.

3 三元概念分析的聯(lián)盟應(yīng)用

本文首先利用三元概念分析的理論解決受限合作博弈聯(lián)盟形式形成問題,然后結(jié)合三元概念分析與Shapley值法提出G-shapley值法,進(jìn)而能夠有效分配聯(lián)盟的效用值,得到每個(gè)參與者的平均邊際貢獻(xiàn).

3.1 聯(lián)盟形式形成

針對(duì)聯(lián)盟的形成問題,經(jīng)典的合作博弈理論假設(shè)N局中人任意的子集都成為一個(gè)聯(lián)盟,比如,有N={A,B,C}三個(gè)參與者,那么依據(jù)其理論,就形成B={Φ,A,B,C,AB,AC,BC,ABC}八種聯(lián)盟形式.然而,實(shí)際的很多情況下,參與者并不是一成不變的,即參與者所擁有的資源與它所處的條件息息相關(guān),就比如,參與者A在a條件下有資源1,隨著環(huán)境的變化,參與者在條件b下就不一定還擁有資源1,因此,參與者的個(gè)體狀況依賴于它所處的環(huán)境.針對(duì)此種情況,本文結(jié)合三元概念分析與合作博弈各自的優(yōu)勢(shì)提出一種新的理論,稱之為受限合作博弈這種合作方式仍然有一定的聯(lián)盟優(yōu)勢(shì).類似于合作博弈聯(lián)盟的概念,本文提出如下聯(lián)盟形式的概念:

定義5.(聯(lián)盟形式)聯(lián)盟形式以三元組(A,B,C)的形式刻畫,A代表參與者集合,B表示參與者在條件C下共同擁有的資源集,C表示條件集合.

為有效處理受限合作博弈的聯(lián)盟形式形成問題,同時(shí)為了清晰描述本文理論,本節(jié)借鑒Faigle U[17]提出的基于概念格的博弈論,并結(jié)合三元概念分析的特點(diǎn),以提出問題并解答問題的方式解析聯(lián)盟形式的形成過程.

為解決上述問題,首先將上述條件通過三元背景的形式進(jìn)行描述,利用三元背景的對(duì)象集K1代表參與者的集合、屬性集K2代表參與者所擁有的資源或能力、條件集K3表示參與者所屬條件的集合.如果參與者在某個(gè)條件下具有某種資源或者能力,在相應(yīng)的位置上就用1表示,否則用0表示,最終通過三元背景描述了參與者、參與者在特定條件下所擁有的資源、參與者所屬的條件之間的三元關(guān)系.聯(lián)盟形式的形成借鑒了文獻(xiàn)[18]的CTLA算法的思想,具體的形成過程主要包括兩部分:一:在單個(gè)條件下,類似于合作博弈理論中,單點(diǎn)集{i}也稱為聯(lián)盟,本文將單個(gè)參與者依靠自身所擁有的所有資源或能力也看作一種聯(lián)盟形式,多個(gè)參與者為形成強(qiáng)強(qiáng)聯(lián)合,提高效率,依賴他們共同擁有的資源組成多參與者合作的聯(lián)盟形式,基于此就形成了單個(gè)條件下所有的聯(lián)盟形式.二:在多個(gè)條件下,有時(shí)參與者在不同的條件下具有某些同種類的資源,為了使本文研究粒度更加細(xì)化同時(shí)為了對(duì)后續(xù)聯(lián)盟效益分配更加精確,針對(duì)此種情況將某些條件下參與者共同擁有某些資源也看作一種聯(lián)盟形式,有時(shí)還表示在不同的條件下存在相同參與者及同種資源的合作方式,為了減少冗余,將條件進(jìn)行合并.

定義6.(穩(wěn)定聯(lián)盟):如果一個(gè)聯(lián)盟是任一三元概念的外延,那么這個(gè)聯(lián)盟是有效的或者說是穩(wěn)定的.在相同的條件下(S′′,S′)是一個(gè)二元概念,形成的聯(lián)盟也是穩(wěn)定的.

定義7.(受限合作博弈):受限合作的博弈是一個(gè)三元組T=(N,F,ν),N是有限個(gè)參與者的集合,F是N的子集構(gòu)成的有效聯(lián)盟的集合,ν是F→R的效用值函數(shù),并且ν(Φ)=0.

算法1.LMXC()

輸入:預(yù)處理后的三元背景(K1,K2,K3,Y)

輸出:所有的聯(lián)盟形式C

1.begin

2. for(every a∈K3)

3. 在模式a下所有的聯(lián)盟形式以概念的形式存入f[a]

4. for(every(S,S′)∈f[a]

5. (S,S′)→(S,S′,a)

6. end for

7. end for

8. e=|K3|;

9. for(int i=0;i

10. for(every(A1,B1,C1)∈f[i])

11. for(every(A2,B2,C2)∈f[i])

12. if(A1=A2and B1=B2)

13. Insert((A1,B1,C1∪C2))

14. end if

15. end for

16. end for

17. end for

18.end

算法2到5行,描述在單個(gè)條件下,如果不同的參與者擁有相同的能力技能,為了實(shí)現(xiàn)強(qiáng)強(qiáng)聯(lián)合,獲得更多的利益,就形成該條件下的聯(lián)盟形式.單個(gè)參與者也可不與其他參與者合作,僅使用自身所有能力形成類似于單點(diǎn)集的聯(lián)盟形式.

基于ARIMA-TREND的企業(yè)價(jià)值評(píng)估收益法探析——以A企業(yè)價(jià)值評(píng)估為例 …………… 李保嬋 王思穎 林俊良（4/36）

算法10到13行,算法10到16行,描述在不同的條件下,如果得到相同的參與者組合及相同的資源集組合,就說明此參與者組合存在不同條件下的合作,為提高效率對(duì)不同的條件進(jìn)行合并以及為了使聯(lián)盟效益分配更加合理同時(shí)使研究粒度更加細(xì)化將參與者在不同條件下共同擁有的屬性此種狀態(tài)也刻畫為聯(lián)盟形式.

為了使上述的聯(lián)盟形式的形成更加清晰、直觀,接下來引入一個(gè)算例,將該理論用在企業(yè)之間的合作.

算法實(shí)例1.在2012年在接受訪問的14家通州企業(yè)中,有12家與其他企業(yè)有合作,以其中三家企業(yè)為應(yīng)用背景,結(jié)合企業(yè)的行業(yè)特點(diǎn),綜合國內(nèi)外有關(guān)企業(yè)能力評(píng)價(jià)指標(biāo)已有的結(jié)果,建立了企業(yè)能力指標(biāo)體系及其指標(biāo)量化結(jié)果如表1所示,表1列舉了3家企業(yè)構(gòu)成的集合為N={A,B,C},a、b、c、d分別代表技術(shù)、生產(chǎn)、銷售、資金四種合作方式,1、2、3、4、5、6分別表示企業(yè)在技術(shù)力量、售后服務(wù)、資產(chǎn)負(fù)債、地理位置、市場(chǎng)影響、企業(yè)信譽(yù)六個(gè)方面的能力,用本節(jié)提出的聯(lián)盟形式的形成理論,依據(jù)企業(yè)所擁有的能力可以形成哪些聯(lián)盟形式.

首先用三元形式背景來刻畫上述問題,如表1所示.

表1 三元背景
Table 1 Triadic concext

abcd123456123456123456123456A111111111B111111111C111111111111111

針對(duì)上述問題,根據(jù)LMXC算法生成以下聯(lián)盟形式:(A,146,d),(AC,126,c)(A,15,a),(B,146,b),(C,12356,b),(BC,16,ab),(C,1246,a),(C,126,abc),(ABC,1,abcd),(B,15,cd),(AC,16,cd),(C,16,abcd),(C,136,bd).

在上述的結(jié)果中,通過LMXC算法共生成了13個(gè)聯(lián)盟形式,將聯(lián)盟形式以三元組的形式表示,分別代表企業(yè)組合、企業(yè)組合共有的技能、合作模式.根據(jù)定義2的三元概念的形成理論可知每個(gè)聯(lián)盟形式都是一個(gè)三元概念,因此這些聯(lián)盟形式又是穩(wěn)定聯(lián)盟,每個(gè)穩(wěn)定聯(lián)盟中的局中人,這里表示每家企業(yè)受外界約束不會(huì)隨意退出該聯(lián)盟.每個(gè)三元概念代表一定的合作含義比如概念(AC,126,c)就表示企業(yè)A和C在技術(shù)力量、售后服務(wù)、市場(chǎng)影響三方面較一致,進(jìn)行銷售合作.企業(yè)也有可能不進(jìn)行合作,(C,136,bd)就表示企業(yè)C依靠自身所擁有的技術(shù)力量、資產(chǎn)負(fù)債情況、企業(yè)信譽(yù)獨(dú)自完成生產(chǎn)與資金模式.每個(gè)聯(lián)盟形式又是穩(wěn)定的,比如企業(yè)A擁有能力126可以獨(dú)自完成生產(chǎn)模式.但為了形成更加穩(wěn)定的聯(lián)盟以獲得更多的利益,它會(huì)與擁有同樣能力的企業(yè)C合作.

如果運(yùn)用經(jīng)典的合作博弈理論針對(duì)上述的三家企業(yè)的合作問題,它不考慮企業(yè)合作模式的種類的狀況以及企業(yè)在不同的合作模式下所擁有資源的變化情況,只是簡(jiǎn)單的用窮舉的方法產(chǎn)生{?,A,B,C.AB,AC,BC,ABC}所有這8種聯(lián)盟形式,如果有N家企業(yè),那么也將用窮舉的方法生成2N種聯(lián)盟.顯然,本文提出的聯(lián)盟形式形成算法與經(jīng)典的合作博弈聯(lián)盟形成方法相比在粒度上更加細(xì)化,不僅考慮到參與者自身擁有的資源狀況還充分的考慮到了參與者所處的條件.

3.2 效用值的分配

效用理論的核心是效用和效用函數(shù),每個(gè)聯(lián)盟形式的形成都對(duì)應(yīng)一個(gè)效用值,效用值由特征函數(shù)描述.將聯(lián)盟的效用值進(jìn)行合理的分配,這是聯(lián)盟穩(wěn)定的關(guān)鍵因素之一.博弈論Shapley值基于參與人的邊際貢獻(xiàn)來對(duì)參與者進(jìn)行分配,比其它的方法公平.因此本文以經(jīng)典Shapley值為基礎(chǔ),又因?yàn)楸疚挠懻摰氖鞘芟藓献鞑┺?即特定條件下的合作,那么Shapley值將不在適用.基于此本文將經(jīng)典的Shapley與三元概念分析相結(jié)合提出了G-shapley值法.

定義9.(G-shapley):對(duì)于每一個(gè)三元博弈(l,V)存在唯一的G-shapley值:Φ(v)={φ1(v),φ2(v),…,φn(v)}.其中:

Φi((l,V))=

(1)

基于G-shapley的特性,可以在條件維上定義G-shapley,依據(jù)G-shapley值的最終結(jié)果可以對(duì)條件的重要程度進(jìn)行排序和加權(quán).還可以在屬性維上定義G-shapley值,這樣能夠有效的依據(jù)其結(jié)果對(duì)參與者所擁有的屬性的依賴程度進(jìn)行由經(jīng)典形式背景向模糊形式背景的轉(zhuǎn)化.

定義9.(同伴參與者):F是N上的一個(gè)閉系統(tǒng)[17].一個(gè)子集K?N,對(duì)于任意一個(gè)不為空的子集S∈F,如果K?S或者K∩S=Φ,那么|K|>1在F上是一個(gè)同伴參與者.

定理.l=(K1,K2,K3,Y)是一個(gè)三元背景,(l,v)是三元背景l(fā)上的博弈,如果K是聯(lián)盟S同伴參與者,那么Φi(l,v)=Φj(l,v).

基于上述定理可以在屬性上定義同伴參與者,當(dāng)兩個(gè)屬性滿足同伴關(guān)系時(shí),可以有效的進(jìn)行屬性消減.

算法2.G-shapley值法:

輸入:聯(lián)盟形式集合T、概念子節(jié)點(diǎn)數(shù)組S

輸出:成員利益分配D

//判斷葉子節(jié)點(diǎn)和根節(jié)點(diǎn)是否唯一,修正概念集

1. for each c∈S

2. if S[c].size==0

3. Leaf.add(c)

4. else

5. Unroot.put(S[c])

6. end if

7. end for

8. if Leaf.size > 1

9. c1 = createConcept(Leaf)

10. T.add(c1)

11. LeafNode = c1

12. else

13. LeafNode = L[0]

14. end if

15. if (T.size - Unroot.size)> 1

16. c2 = createConcept(Root)

17. T.add(c2)

18. end if

19. //重新計(jì)算聯(lián)盟間關(guān)系

20. S′ = computeRealtion(T)

21. //從葉子節(jié)點(diǎn)出發(fā)向上,遞歸得到所有鏈路

22. Links = constructLinks(T,S′,LeafNode)

23. //根據(jù)鏈路計(jì)算聯(lián)盟成員收益

24. for each p∈RootNode.Extends

25. for each r∈Links

26. for each c∈r

27. c′ = r[c+1]

28. if !c.Extends.contains(p)&

29. c′.Extends.contains(p)

30. profit +=(P[c′] P[c])/

31. (c′.Extends.size-c.Extends.size)

32. end if

33. end for

34. end for

35. D[p]= profit

36. end for

37. Output D

算法第1行到19行,根據(jù)A1?B1、A2?B2及A3?B3對(duì)所有的聯(lián)盟形式進(jìn)行聯(lián)盟形式格結(jié)構(gòu)的構(gòu)造.

算法第20行到35行,求解參與者i的能力值.如果參與者i屬于擁有全部資源的聯(lián)盟,對(duì)該聯(lián)盟值均分,否則,搜索整個(gè)格結(jié)構(gòu)的每條鏈,查找任一條鏈第一個(gè)包含i的聯(lián)盟形式,以及最后一個(gè)不包含鏈的聯(lián)盟形式,得到參與者i的平均邊際貢獻(xiàn).

為了驗(yàn)證本節(jié)提出的G-shapley值的正確性,引用文獻(xiàn)[19]中的背景數(shù)據(jù),該文獻(xiàn)將Shapley值應(yīng)用在在農(nóng)產(chǎn)品合作供應(yīng)鏈中,符合本文的研究理論,本文用到的具體數(shù)據(jù)如圖1所示.

圖1 聯(lián)盟形式格結(jié)構(gòu)圖1 Lattice structure of alliance form

在農(nóng)產(chǎn)品合作供應(yīng)鏈中有三個(gè)參與者,它們分別是:生產(chǎn)者A、物流商B、零售商C,當(dāng)A、B、C單獨(dú)經(jīng)營(yíng)時(shí),均能獲得3萬元的收益,若A和B合作獲7萬元,A和C合作獲8萬元、B和C合作獲10萬元,A和B和C合作獲10萬元.

依據(jù)上述數(shù)據(jù),采用本文提出的G-shapley值法計(jì)算三個(gè)參與者的分配利益,農(nóng)產(chǎn)品合作供應(yīng)鏈可看作單個(gè)條件下的合作問題,根據(jù)G-shapley值法的主要思想,形成圖1所示的聯(lián)盟形式格結(jié)構(gòu):

圖中的每個(gè)節(jié)點(diǎn)由聯(lián)盟形式及其對(duì)應(yīng)的效用值的有序?qū)M成,按上述聯(lián)盟形式的定義,聯(lián)盟形式應(yīng)有參與者組合,共同的資源及條件組合這三部門組成,但此處解決的是單條件在的利益分配問題,為描述簡(jiǎn)單又由于文獻(xiàn)[19]未詳細(xì)描述參與者的資源信息,因此聯(lián)盟形式用參與者集合描述.圖2共有6條鏈路組成:

第1條鏈路:8 5 2 1

第2條鏈路:8 5 3 1

第3條鏈路:8 6 2 1

第4條鏈路:8 6 4 1

第5條鏈路:8 7 3 1

第6條鏈路:8 7 4 1

求解生產(chǎn)者的分配利益ΦA(chǔ)(v)具體過程:

1.在第1條鏈路上找到最后一個(gè)不含生產(chǎn)者A的聯(lián)盟形式并獲得它的效用值,由圖2可知它為節(jié)點(diǎn)8,節(jié)點(diǎn)8的聯(lián)盟形式是?,效用值為0;

2.在第1條鏈上找到第一個(gè)含有參與者A的聯(lián)盟形式并獲得它的效用值,由圖2可知它為節(jié)點(diǎn)5,節(jié)點(diǎn)5的聯(lián)盟形式為A,效用值為3.

3.計(jì)算聯(lián)盟形式A與聯(lián)盟形式?參與者差值的模|A?|=1.

同理可得物流商分配利益ΦB(v)=8.5萬元;零售商分配利益ΦC(v)=9萬元.與文獻(xiàn)[19]中通過經(jīng)典Shapley值計(jì)算的結(jié)果是一樣的,具體的計(jì)算過程文獻(xiàn)[19]已展示,這里不再贅述.

本文提出的G-shapley值適合任何使用經(jīng)典Shapley值計(jì)算利益分配問題,但如果是多條件下的利益分配問題,就不能再使用經(jīng)典Shapley值計(jì)算.

3.3 算法的時(shí)間復(fù)雜度分析

本文提出的模型主要包括兩個(gè)部分:LMXC()算法和G-shapley()值法,對(duì)每個(gè)部分進(jìn)行時(shí)間復(fù)雜度分析.LMXC()和G-shapley()的時(shí)間復(fù)雜度與三元概念中的外延、內(nèi)涵和條件都有關(guān)系,LMXC()算法的執(zhí)行時(shí)間主要取決于聯(lián)盟形式的形成,聯(lián)盟形式由參與者數(shù)量,參與者擁有的資源和條件種類共同決定,而在滿足三元關(guān)系的情況下,這三者可分別看作三元背景的對(duì)象數(shù)目、屬性數(shù)目和條件個(gè)數(shù).在計(jì)算每個(gè)條件下形成聯(lián)盟形式的時(shí)間復(fù)雜度時(shí),需要考慮到所有參與者的所有資源.因此,每個(gè)條件下聯(lián)盟形式的時(shí)間復(fù)雜度為O(‖L1‖*‖L2‖),那么在所有條件下形成聯(lián)盟形式的時(shí)間復(fù)雜度為O(‖L1‖*‖L2‖*‖L3‖).G-shapley值法的時(shí)間復(fù)雜度取決于LMXC()算法生成的聯(lián)盟形式的數(shù)量,假設(shè)由LMXC形成的聯(lián)盟形式個(gè)數(shù)為‖A‖,在G-shapley的格構(gòu)建過程中,在判斷任意一個(gè)聯(lián)盟形式與其他聯(lián)盟形式的關(guān)系時(shí),需要搜索除它以外所有的聯(lián)盟形式,因此格構(gòu)建的時(shí)間復(fù)雜度為O(‖A‖*‖A‖).對(duì)參與者的效用分配,需要考慮三個(gè)階段:聯(lián)盟形式的形成、聯(lián)盟形式格的構(gòu)建,格的搜索,在格的搜索過程中,考慮極限情況,在評(píng)估每個(gè)參與者復(fù)雜度為O(‖L1‖*‖A‖).綜上所述,總的時(shí)間復(fù)雜度為:O(‖L1‖*‖L2‖*‖L3‖+‖A‖*‖A‖+‖L1‖*‖A‖)

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

文章的第三部分已對(duì)提出的理論進(jìn)行了有效性的分析與驗(yàn)證,因此本節(jié)分別測(cè)試LMXC和G-shapley值法的性能,由于本文是從參與者所擁有資源層面進(jìn)行受限合作研究的,與經(jīng)典的合作博弈不同,由于沒有權(quán)威的聯(lián)盟形式形成算法以及效用分配算法作比較分析,因此本文的算法沒有與其它文獻(xiàn)的算法進(jìn)行對(duì)比.

實(shí)驗(yàn)環(huán)境:3.4GHz CPU,4GB內(nèi)存,Win10操作系統(tǒng),使用Java實(shí)驗(yàn)平臺(tái)對(duì)LMXC()算法及G-shapley值法的性能進(jìn)行驗(yàn)證.針對(duì)本文的研究?jī)?nèi)容,由于沒有典型的數(shù)據(jù)集,因此實(shí)驗(yàn)用到的數(shù)據(jù)是隨機(jī)生成的.

4.1 聯(lián)盟形式構(gòu)造

實(shí)驗(yàn)中分別將參與者數(shù)量、參與者向量維度作為變量執(zhí)行LMXC算法.

實(shí)驗(yàn)1.a.在參與者能力向量維度為10,條件種類為5的條件下使參與者的個(gè)數(shù)不斷增加,實(shí)驗(yàn)結(jié)果如圖2所示.

圖2 實(shí)驗(yàn)a參與者數(shù)量作為變量實(shí)驗(yàn)分析圖Fig.2 Performance of experiment a where as variable

實(shí)驗(yàn)結(jié)果表明,固定參與者能力向量維度以及條件種類的條件下,隨著參與者數(shù)量的增多,運(yùn)行時(shí)間也隨之增加.這是因?yàn)楫?dāng)參與者的個(gè)數(shù)增多時(shí),參與者的組合方式隨之增加,在單個(gè)條件下形成的聯(lián)盟形式也增加.在多個(gè)下進(jìn)行聯(lián)盟形式的合并時(shí),需要對(duì)比的聯(lián)盟形式的數(shù)量也會(huì)增加,從而導(dǎo)致算法的執(zhí)行時(shí)間增長(zhǎng).

b.參與者數(shù)量為30,條件種類為8的條件下,使參與者向量維度不斷增加,實(shí)驗(yàn)結(jié)果如圖3所示.

圖3 實(shí)驗(yàn)b參與者向量維度作為變量實(shí)驗(yàn)分析圖Fig.3 Performance of experiment b where attribute as variable

實(shí)驗(yàn)結(jié)果表明,隨著參與者能力向量維度的增加,運(yùn)行時(shí)間也隨之增加.這是因?yàn)楫?dāng)參與者的能力向量維度增加時(shí),參與者的合作方式種類會(huì)增加,相應(yīng)的聯(lián)盟形式的個(gè)數(shù)也會(huì)增長(zhǎng).通過圖2和圖3觀察到,算法的執(zhí)行時(shí)間都有所增加,原因是無論是增加參與者的數(shù)量還是增加參與者的向量維度,最終都會(huì)導(dǎo)致聯(lián)盟形式的增多,從而影響算法的性能.

4.2 聯(lián)盟效用分配

實(shí)驗(yàn)中將LMXC算法得到的聯(lián)盟形式作為輸入執(zhí)行G-shapley值法并進(jìn)行分析,通過觀察該算法的運(yùn)行時(shí)間來衡量算法的性能.

實(shí)驗(yàn)2.a.在參與者能力向量維度為6,條件種類為3的條件下,參與者個(gè)數(shù)不斷增加,實(shí)驗(yàn)結(jié)果如圖4所示.

圖4 實(shí)驗(yàn)a G-shapley分配實(shí)驗(yàn)分析圖Fig.4 Performance of experiment a G-shapley

b.在參與者數(shù)量為30,條件種類為3的條件下,參與者向量維度不斷增加,實(shí)驗(yàn)結(jié)果如圖5所示.

圖5 實(shí)驗(yàn)b G-Shapley分配實(shí)驗(yàn)分析圖Fig.5 Performance of experiment b G-shapley

從圖4和圖5的實(shí)驗(yàn)結(jié)果觀察到如果將LMXC的運(yùn)行結(jié)果傳送給G-shapley,它的運(yùn)行時(shí)間隨著參與者數(shù)目的增加或者參與者向量維度的增加而有所上升這是因?yàn)樵谇蠼釭-shapley值的過程中,首先要構(gòu)建聯(lián)盟形式的格結(jié)構(gòu),隨著輸入的聯(lián)盟形式的數(shù)量的增多,所構(gòu)建的格會(huì)變大,在計(jì)算參與者的平均邊際貢獻(xiàn)時(shí),要搜索所構(gòu)建格的每條鏈,在每條鏈上查找其對(duì)應(yīng)聯(lián)盟形式的效用值時(shí),每個(gè)環(huán)節(jié)都會(huì)隨著聯(lián)盟形式數(shù)量的增多,算法的執(zhí)行時(shí)間也會(huì)增加,實(shí)驗(yàn)結(jié)果表明,只要聯(lián)盟形式的數(shù)量增多,在執(zhí)行G-shapley進(jìn)行分配時(shí)所需時(shí)間就會(huì)增大.

5 總 結(jié)

本文在三元概念分析理論的基礎(chǔ)上引入了受限博弈,主要研究了如何運(yùn)用三元概念分析解決受限合作的聯(lián)盟形成以及為了得到參與者的分配值,結(jié)合三元概念分析的理論提出了G-shapley算法,同時(shí)通過實(shí)驗(yàn)測(cè)試了本文模型的效率.該理論的提出是對(duì)三元概念分析的擴(kuò)展,同時(shí)也為三元概念的應(yīng)用奠定了基礎(chǔ).雖然三元概念分析有很大的發(fā)展空間,但本文提出的理論是三元概念分析在受限合作博弈上的初步探索,仍有許多不足之處,如本文提出的G-shapley值法,隨著參與者人數(shù)的增多,算法的運(yùn)行時(shí)間有待進(jìn)一步研究以及LMXC算法也要進(jìn)一步優(yōu)化.