崔 瑩

(南京財(cái)經(jīng)大學(xué) 信息工程學(xué)院,南京 210023)

求解虛擬企業(yè)資源結(jié)盟博弈的啟發(fā)式群智能優(yōu)化算法①

崔 瑩

(南京財(cái)經(jīng)大學(xué) 信息工程學(xué)院,南京 210023)

通過(guò)對(duì)求解虛擬企業(yè)資源結(jié)盟博弈問(wèn)題與求解經(jīng)典SAT問(wèn)題相似性的分析,提出了一種求解虛擬企業(yè)資源結(jié)盟博弈的啟發(fā)式群智能優(yōu)化算法.算法融合螢火蟲優(yōu)化算法與布谷鳥優(yōu)化算法部分原理,并設(shè)計(jì)可行的交叉算子以及變異優(yōu)化算子,能夠修復(fù)不可行解并保持種群多樣性.實(shí)驗(yàn)結(jié)果表明本文算法的迭代次數(shù)與搜索到的穩(wěn)定聯(lián)盟數(shù)成線性增長(zhǎng),較啟發(fā)式遺傳算法有著更好的爬山性能和搜索能力.

資源結(jié)盟博弈;虛擬企業(yè);SAT問(wèn)題;群智能優(yōu)化算法

虛擬企業(yè)是指分布在不同地區(qū)的常規(guī)企業(yè),利用網(wǎng)絡(luò)信息技術(shù),為快速響應(yīng)環(huán)境需求和變化而組織起來(lái)的動(dòng)態(tài)聯(lián)盟[1-2].在虛擬企業(yè)中,經(jīng)常出現(xiàn)企業(yè)持有資源不能滿足生產(chǎn)需求的問(wèn)題,而建立企業(yè)資源結(jié)盟可有效解決該問(wèn)題,因此虛擬企業(yè)結(jié)盟問(wèn)題越來(lái)越受到關(guān)注.

文獻(xiàn)[3]結(jié)合任務(wù)導(dǎo)向性和間續(xù)式結(jié)盟特征對(duì)虛擬企業(yè)治理機(jī)制進(jìn)行了研究,文獻(xiàn)[4]討論了電子市場(chǎng)買方結(jié)盟問(wèn)題.文獻(xiàn)[5]提出了資源約束和目標(biāo)約束下企業(yè)的結(jié)盟問(wèn)題,可能的結(jié)盟數(shù)隨企業(yè)數(shù)后的增長(zhǎng)呈指數(shù)增長(zhǎng),是NP-hard問(wèn)題.虛擬企業(yè)資源結(jié)盟博弈問(wèn)題的目標(biāo)是搜索穩(wěn)定聯(lián)盟并非優(yōu)化聯(lián)盟結(jié)構(gòu),即解具有可滿足性即可,與經(jīng)典SAT問(wèn)題有著相似之處.文獻(xiàn)[6]提出了一種利用近似解的求解SAT問(wèn)題的算法,將近似解原理與多種群智能算法融合設(shè)計(jì)出一種可用于搜索虛擬企業(yè)資源結(jié)盟博弈的可行解的啟發(fā)式群智能優(yōu)化算法.

本文結(jié)合螢火蟲優(yōu)化算法與布谷鳥優(yōu)化算法的部分理念設(shè)計(jì),提出求解虛擬企業(yè)資源結(jié)盟博弈的啟發(fā)式群智能優(yōu)化算法,同時(shí)基于聯(lián)盟及其目標(biāo)之間的約束關(guān)系,設(shè)計(jì)交叉算子以及變異優(yōu)化算子.

1 問(wèn)題描述及分析

資源結(jié)盟博弈問(wèn)題可以看做是資源的分配問(wèn)題,本節(jié)主要對(duì)資源結(jié)盟博弈進(jìn)行了形式化描述.

其中,Gi為企業(yè)ai所對(duì)應(yīng)的目標(biāo).

聯(lián)盟的穩(wěn)定性是解決資源結(jié)盟博弈問(wèn)題的核心,虛擬企業(yè)資源結(jié)盟問(wèn)題的求解是資源結(jié)盟博弈的重要應(yīng)用問(wèn)題,實(shí)際上也是依賴于求解穩(wěn)定聯(lián)盟及其可達(dá)目標(biāo)而實(shí)現(xiàn)的.

2 應(yīng)用啟發(fā)式群智能優(yōu)化算法求解資源結(jié)盟博弈問(wèn)題

本節(jié)具體地介紹了采用啟發(fā)式群智能優(yōu)化算法求解資源結(jié)盟博弈的穩(wěn)定聯(lián)盟,基于可行及相容的概念,分別定義評(píng)價(jià)函數(shù),設(shè)計(jì)交叉算子和變異優(yōu)化算子.

2.1 編碼問(wèn)題

求解虛擬企業(yè)資源結(jié)盟博弈中的穩(wěn)定聯(lián)盟,可以轉(zhuǎn)化為在兩個(gè)冪集中分布搜索聯(lián)盟和目標(biāo)子集在聯(lián)盟C下可達(dá).搜索空間為兩個(gè)冪集的笛卡爾積.將一個(gè)解表示為一個(gè)二進(jìn)制串且滿足:

2.2 解之間的距離

隨機(jī)從種群中選出要進(jìn)行交叉的個(gè)體,形成交叉配對(duì)池,然后對(duì)配對(duì)池中的每個(gè)對(duì)解搜索與其距離最近的個(gè)體進(jìn)行交叉操作得出一個(gè)新解.對(duì)解表示成二進(jìn)制串,本文選擇通過(guò)計(jì)算海明距離獲得兩個(gè)對(duì)解之間的距離.

2.3 評(píng)價(jià)函數(shù)

在虛擬企業(yè)資源結(jié)盟博弈的問(wèn)題中,需要通過(guò)評(píng)價(jià)函數(shù)對(duì)對(duì)解進(jìn)行判定.一個(gè)解可宏觀定義為可行解與不可行解.可行解只有一種即在聯(lián)盟C下可達(dá),不可行解可以根據(jù)資源約束和目標(biāo)約束具體分為四種,本文根據(jù)不可行解類型設(shè)置評(píng)價(jià)函數(shù)如下:

2.4 近似解交叉算子

文獻(xiàn)[7]利用近似解加速求解SAT問(wèn)題,有效地結(jié)合了局部搜索算法和完全算法的優(yōu)點(diǎn),首先利用局部搜索算法在較短的時(shí)間內(nèi)得到一個(gè)近似解,然后將其作為初始輸入導(dǎo)算子優(yōu)先搜索近似解所在子空間可能存在的近似解,使得效率有了很大的提高[7].虛擬企業(yè)資源結(jié)盟博弈問(wèn)題的基本思路與其解決SAT問(wèn)題的基本思路具有很高的相似性,本文根據(jù)SAT問(wèn)題的解決思路,同時(shí)結(jié)合螢火蟲優(yōu)化算法[7]以及其應(yīng)用[8]設(shè)計(jì)出近似解交叉算子.本文提出的近似解交叉算子主要是將一個(gè)解與在空間距離中距離最近的解進(jìn)行交叉更新,獲得新的解,而新的解即有可能為潛在的可行解.假設(shè)一個(gè)解為在交叉配對(duì)池中與其距離最近的解為,在區(qū)間(0,1)內(nèi)獲取兩個(gè)隨機(jī)數(shù)a和概率閾值p,根據(jù)隨機(jī)數(shù)a與概率閾值p的大小進(jìn)行交叉更新,所得到的新解為,其更新式如下:

在對(duì)種群中的對(duì)解進(jìn)行交叉操作,即實(shí)現(xiàn)通過(guò)優(yōu)先搜索在可行解附近的空間找出潛在的可行解,可以保證搜索到的聯(lián)盟數(shù)量穩(wěn)定增長(zhǎng).

2.5 啟發(fā)式變異優(yōu)化算子

不可行解包含多種類型,每一類型反映著資源、企業(yè)及目標(biāo)子集之間的需求供應(yīng)關(guān)系.因此針對(duì)不同的類型的不可行解需要通過(guò)不同的方法進(jìn)行優(yōu)化,獲取潛在的可行解,從而增加種族中可行解的數(shù)量.本文詳細(xì)地分析了不同類型的不可行解的特點(diǎn),分別設(shè)計(jì)了不同的變異優(yōu)化算子以更好地適應(yīng)具有差異的不可行解的問(wèn)題的解決,達(dá)到“對(duì)癥下藥”的效果.啟發(fā)式變異優(yōu)化算子應(yīng)用到的概念如下.

并將Gwait中頻繁度計(jì)數(shù)最大的目標(biāo)定義為則待變異頻繁目標(biāo)記做gfreq:

根據(jù)不可行解的類型進(jìn)行了分析,針對(duì)不同類型的不可行解設(shè)計(jì)的變異優(yōu)化算子具體內(nèi)容如下:

2.6 聯(lián)盟企業(yè)反置算子

在布谷鳥算法[9]設(shè)計(jì)中提出有鳥窩主人有一定概率發(fā)現(xiàn)鳥蛋并隨機(jī)改變鳥窩的位置,該做法可理解為增加種群多樣性.受此原理啟發(fā),本文將布谷鳥算法應(yīng)用到聯(lián)盟企業(yè)反置算子中,用來(lái)找到潛在的更優(yōu)解.具體方法為:將每一個(gè)鳥巢里的鳥蛋看做是一個(gè)解,那么隨機(jī)選擇計(jì)生在鳥巢里的布谷鳥蛋則代表了一個(gè)新的解,可以利用新的以及潛在的可行解來(lái)取代一個(gè)在鳥巢里并不那么好的解.假設(shè)一個(gè)解的聯(lián)盟企業(yè)反置算子為若xi=1則令xi=0,若xi=0則令xi=1.

2.7 求解資源結(jié)盟博弈問(wèn)題的啟發(fā)式智能優(yōu)化算法

算法步驟如下:

Step 1.設(shè)置種群數(shù)后pop_size,(種群中的每一個(gè)個(gè)體對(duì)應(yīng)著資源結(jié)盟博弈問(wèn)題的一個(gè)解),企業(yè)數(shù)后n,最大目標(biāo)數(shù)m,資源數(shù)t,交叉式子概率閾值p,最大迭代次數(shù)ItMax,穩(wěn)定聯(lián)盟計(jì)數(shù)count.

Step 2.隨機(jī)從種群中選出要進(jìn)行交叉的個(gè)體,形成交叉配對(duì)池,然后對(duì)配對(duì)池中的每個(gè)對(duì)解搜索與其距離最近的個(gè)體進(jìn)行近似解交叉得出一個(gè)新解

Step4.判斷是否到達(dá)最大迭代次數(shù)ItMax.若到達(dá),停止迭代,輸出穩(wěn)定聯(lián)盟計(jì)數(shù)count;否則重復(fù)Step 2～Step 3.

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

3.1 實(shí)驗(yàn) 1

設(shè)置實(shí)驗(yàn)參數(shù):種群數(shù)后pop_sizem=300,企業(yè)數(shù)后n=12,最大目標(biāo)數(shù)m=4,資源數(shù)t=8,交叉式子概率閾值0.5,最大迭代次數(shù)ItMax=1000.隨機(jī)生成仿真數(shù)據(jù)如表1、表2、表3所示.圖1為實(shí)驗(yàn)結(jié)果圖.

表1 企業(yè)資源持有表

3.2 實(shí)驗(yàn) 2

設(shè)置實(shí)驗(yàn)參數(shù):種群數(shù)后pop_sizem=300,企業(yè)數(shù)后n=14,最大目標(biāo)數(shù)m=6,資源數(shù)t=8,交叉式子概率閾值p=0.5,最大迭代次數(shù)ItMax=1000.隨機(jī)生成仿真數(shù)據(jù)如表4、表5、表6所示.圖2為實(shí)驗(yàn)結(jié)果圖.

表2 企業(yè)目標(biāo)需求表

表3 目標(biāo)需求資源表

圖1 本文算法與啟發(fā)式遺傳算法[5]對(duì)比結(jié)果圖

表4 企業(yè)資源持有表

表5 企業(yè)目標(biāo)需求表

表6 目標(biāo)需求資源表

圖2 本文算法與啟發(fā)式遺傳算法[5]對(duì)比結(jié)果圖

3.3 結(jié)果分析

通過(guò)觀察圖1和圖2可以發(fā)現(xiàn)啟發(fā)式遺傳算法[5]在迭代前期收斂較快,原因是啟發(fā)式遺傳算法采用的啟發(fā)式交叉修正算子每次可以修復(fù)2個(gè)子代個(gè)體,而本文采用的啟發(fā)式群智能優(yōu)化算法每次交叉修復(fù)1個(gè)子代個(gè)體.但是,隨著迭代次數(shù)的增加,啟發(fā)式遺傳算法容易出現(xiàn)“早熟”現(xiàn)象,而本文的算法通過(guò)對(duì)種群中的解進(jìn)行變異優(yōu)化之后,種群中可行解數(shù)后增多,近似解交叉算子的優(yōu)勢(shì)逐漸體現(xiàn),優(yōu)先搜索到可行解附近的潛在可行解,保證搜索到的聯(lián)盟數(shù)量可以穩(wěn)步增長(zhǎng),并設(shè)置聯(lián)盟企業(yè)反置算子以保證種群的多樣性,防止算法過(guò)早停滯,從而避免“早熟”現(xiàn)象的發(fā)生.另外,當(dāng)問(wèn)題規(guī)模增加,搜索空間擴(kuò)大時(shí),啟發(fā)式群智能優(yōu)化算法搜索到的穩(wěn)定聯(lián)盟數(shù)后與迭代次數(shù)幾乎呈線性增長(zhǎng),相比于啟發(fā)式遺傳算法具有更強(qiáng)的爬山性能和搜索性能,所以本文提出的啟發(fā)式遺傳算法可用于求解虛擬企業(yè)資源結(jié)盟博弈問(wèn)題,且具有較強(qiáng)的魯棒性.

4 結(jié)語(yǔ)

制造企業(yè)聯(lián)合生產(chǎn)產(chǎn)品問(wèn)題可以歸結(jié)為一類企業(yè)資源結(jié)盟博弈問(wèn)題,從資源約束角度討論企業(yè)的結(jié)盟問(wèn)題具有重要應(yīng)用價(jià)值.本文通過(guò)對(duì)比虛擬企業(yè)資源結(jié)盟博弈問(wèn)題與SAT問(wèn)題的相似性,結(jié)合了多種新型群智能優(yōu)化算法的部分原理,設(shè)計(jì)出一種可用于求解資源結(jié)盟博弈問(wèn)題的啟發(fā)式群智能優(yōu)化算法,為此類資源結(jié)盟的大規(guī)模問(wèn)題提出一種可行的數(shù)學(xué)模型.接下來(lái)進(jìn)一步的工作是對(duì)算法的精確度進(jìn)行進(jìn)一步的提高.

1 Mowshowitz A.Virtual organization.Communications of the ACM,1997,40(9):30–37.[doi:10.1145/260750.260759]

2 O’Leary DE,Kuokka D,Plant R.Artificial intelligence and virtual organizations.Communications of the ACM,1997,40(1):52–59.[doi:10.1145/242857.242871]

3 胡欣悅,湯勇力,李從東.任務(wù)導(dǎo)向的虛擬企業(yè)間續(xù)式結(jié)盟治理機(jī)制.系統(tǒng)工程理論與實(shí)踐,2007,(11):34–42.[doi:10.3321/j.issn:1000-6788.2007.11.005]

4 韓偉,陳優(yōu)廣.電子市場(chǎng)買方結(jié)盟的利益分配及其結(jié)盟策略.計(jì)算機(jī)集成制造系統(tǒng),2007,13(12):2487–2491.[doi:10.3969/j.issn.1006-5911.2007.12.030]

5 韓偉,呂捷,陳優(yōu)廣.虛擬企業(yè)資源結(jié)盟博弈的啟發(fā)式遺傳算法.計(jì)算機(jī)集成制造系統(tǒng),2008,14(4):744–748,756.

6 荊明娥,周電,唐璞山,等.利用近似解加速求解SAT問(wèn)題的啟發(fā)式完全算法.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2007,19(9):1184–1189.

7 Krishnanand KN,Ghose D.Detection of multiple source locations using a glowworm metaphor with applications to collective robotics.Proc.of 2005 IEEE Swarm Intelligence Symposium.Pasadena,CA,USA.2005.84–91.

8 周永權(quán),黃正新,劉洪霞.求解TSP問(wèn)題的離散型螢火蟲群優(yōu)化算法.電子學(xué)報(bào),2012,40(6):1164–1170.

9 李煜,馬良.新型元啟發(fā)式布谷鳥搜索算法.系統(tǒng)工程,2012,30(8):64–69.

Heuristic Swarm Intelligent Optimization Algorithm for Coalitional Resources Games in Virtual Enterprises

CUI Ying
(College of Information and Engineering,Nanjing University of Finance and Economics,Nanjing 210023,China)

A heuristic swarm intelligent optimization algorithm for coalitional resources games in virtual enterprises is proposed by comparing the similarity of coalitional resources games in virtual enterprises with the classic SAT problem.The algorithm fuses portions of the principles of Glowworm swarm optimization algorithm and Cuckoo Search optimization algorithm.It designs the feasible cross operator and the mutational operator,which can repair infeasible solution and maintain diversity.Experimental results indicate that the algorithm’s iterations linearly increase with the stable coalitions ever found.Compared with the heuristic genetic algorithm,it performs better in hill-climbing performance and searching efficiency.

coalitional resources;virtual enterprises;SAT problem;swarm intelligent optimization algorithm

崔瑩.求解虛擬企業(yè)資源結(jié)盟博弈的啟發(fā)式群智能優(yōu)化算法.計(jì)算機(jī)系統(tǒng)應(yīng)用,2017,26(9):195–199.http://www.c-s-a.org.cn/1003-3254/5976.html

① 基金項(xiàng)后:科技部科技支撐項(xiàng)后(BAH29F01);江蘇省農(nóng)業(yè)科技自主創(chuàng)新資金項(xiàng)后(CX(15)1051);國(guó)家自然科學(xué)基金(71372188)

2017-01-02;采用時(shí)間:2017-02-13