求解虛擬企業資源結盟博弈的啟發式群智能優化算法①

崔 瑩

(南京財經大學 信息工程學院,南京 210023)

求解虛擬企業資源結盟博弈的啟發式群智能優化算法①

崔 瑩

(南京財經大學 信息工程學院,南京 210023)

通過對求解虛擬企業資源結盟博弈問題與求解經典SAT問題相似性的分析,提出了一種求解虛擬企業資源結盟博弈的啟發式群智能優化算法.算法融合螢火蟲優化算法與布谷鳥優化算法部分原理,并設計可行的交叉算子以及變異優化算子,能夠修復不可行解并保持種群多樣性.實驗結果表明本文算法的迭代次數與搜索到的穩定聯盟數成線性增長,較啟發式遺傳算法有著更好的爬山性能和搜索能力.

資源結盟博弈;虛擬企業;SAT問題;群智能優化算法

虛擬企業是指分布在不同地區的常規企業,利用網絡信息技術,為快速響應環境需求和變化而組織起來的動態聯盟[1-2].在虛擬企業中,經常出現企業持有資源不能滿足生產需求的問題,而建立企業資源結盟可有效解決該問題,因此虛擬企業結盟問題越來越受到關注.

文獻[3]結合任務導向性和間續式結盟特征對虛擬企業治理機制進行了研究,文獻[4]討論了電子市場買方結盟問題.文獻[5]提出了資源約束和目標約束下企業的結盟問題,可能的結盟數隨企業數后的增長呈指數增長,是NP-hard問題.虛擬企業資源結盟博弈問題的目標是搜索穩定聯盟并非優化聯盟結構,即解具有可滿足性即可,與經典SAT問題有著相似之處.文獻[6]提出了一種利用近似解的求解SAT問題的算法,將近似解原理與多種群智能算法融合設計出一種可用于搜索虛擬企業資源結盟博弈的可行解的啟發式群智能優化算法.

本文結合螢火蟲優化算法與布谷鳥優化算法的部分理念設計,提出求解虛擬企業資源結盟博弈的啟發式群智能優化算法,同時基于聯盟及其目標之間的約束關系,設計交叉算子以及變異優化算子.

1 問題描述及分析

資源結盟博弈問題可以看做是資源的分配問題,本節主要對資源結盟博弈進行了形式化描述.

其中,Gi為企業ai所對應的目標.

聯盟的穩定性是解決資源結盟博弈問題的核心,虛擬企業資源結盟問題的求解是資源結盟博弈的重要應用問題,實際上也是依賴于求解穩定聯盟及其可達目標而實現的.

2 應用啟發式群智能優化算法求解資源結盟博弈問題

本節具體地介紹了采用啟發式群智能優化算法求解資源結盟博弈的穩定聯盟,基于可行及相容的概念,分別定義評價函數,設計交叉算子和變異優化算子.

2.1 編碼問題

求解虛擬企業資源結盟博弈中的穩定聯盟,可以轉化為在兩個冪集中分布搜索聯盟和目標子集在聯盟C下可達.搜索空間為兩個冪集的笛卡爾積.將一個解表示為一個二進制串且滿足:

2.2 解之間的距離

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

2.3 評價函數

在虛擬企業資源結盟博弈的問題中,需要通過評價函數對對解進行判定.一個解可宏觀定義為可行解與不可行解.可行解只有一種即在聯盟C下可達,不可行解可以根據資源約束和目標約束具體分為四種,本文根據不可行解類型設置評價函數如下:

2.4 近似解交叉算子

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

在對種群中的對解進行交叉操作,即實現通過優先搜索在可行解附近的空間找出潛在的可行解,可以保證搜索到的聯盟數量穩定增長.

2.5 啟發式變異優化算子

不可行解包含多種類型,每一類型反映著資源、企業及目標子集之間的需求供應關系.因此針對不同的類型的不可行解需要通過不同的方法進行優化,獲取潛在的可行解,從而增加種族中可行解的數量.本文詳細地分析了不同類型的不可行解的特點,分別設計了不同的變異優化算子以更好地適應具有差異的不可行解的問題的解決,達到“對癥下藥”的效果.啟發式變異優化算子應用到的概念如下.

并將Gwait中頻繁度計數最大的目標定義為則待變異頻繁目標記做gfreq:

根據不可行解的類型進行了分析,針對不同類型的不可行解設計的變異優化算子具體內容如下:

2.6 聯盟企業反置算子

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

2.7 求解資源結盟博弈問題的啟發式智能優化算法

算法步驟如下:

Step 1.設置種群數后pop_size,(種群中的每一個個體對應著資源結盟博弈問題的一個解),企業數后n,最大目標數m,資源數t,交叉式子概率閾值p,最大迭代次數ItMax,穩定聯盟計數count.

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

Step4.判斷是否到達最大迭代次數ItMax.若到達,停止迭代,輸出穩定聯盟計數count;否則重復Step 2～Step 3.

3 仿真實驗與結果分析

3.1 實驗 1

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

表1 企業資源持有表

3.2 實驗 2

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

表2 企業目標需求表

表3 目標需求資源表

圖1 本文算法與啟發式遺傳算法[5]對比結果圖

表4 企業資源持有表

表5 企業目標需求表

表6 目標需求資源表

圖2 本文算法與啟發式遺傳算法[5]對比結果圖

3.3 結果分析

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

4 結語

制造企業聯合生產產品問題可以歸結為一類企業資源結盟博弈問題,從資源約束角度討論企業的結盟問題具有重要應用價值.本文通過對比虛擬企業資源結盟博弈問題與SAT問題的相似性,結合了多種新型群智能優化算法的部分原理,設計出一種可用于求解資源結盟博弈問題的啟發式群智能優化算法,為此類資源結盟的大規模問題提出一種可行的數學模型.接下來進一步的工作是對算法的精確度進行進一步的提高.

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 胡欣悅,湯勇力,李從東.任務導向的虛擬企業間續式結盟治理機制.系統工程理論與實踐,2007,(11):34–42.[doi:10.3321/j.issn:1000-6788.2007.11.005]

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

5 韓偉,呂捷,陳優廣.虛擬企業資源結盟博弈的啟發式遺傳算法.計算機集成制造系統,2008,14(4):744–748,756.

6 荊明娥,周電,唐璞山,等.利用近似解加速求解SAT問題的啟發式完全算法.計算機輔助設計與圖形學學報,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 周永權,黃正新,劉洪霞.求解TSP問題的離散型螢火蟲群優化算法.電子學報,2012,40(6):1164–1170.

9 李煜,馬良.新型元啟發式布谷鳥搜索算法.系統工程,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

崔瑩.求解虛擬企業資源結盟博弈的啟發式群智能優化算法.計算機系統應用,2017,26(9):195–199.http://www.c-s-a.org.cn/1003-3254/5976.html

① 基金項后:科技部科技支撐項后(BAH29F01);江蘇省農業科技自主創新資金項后(CX(15)1051);國家自然科學基金(71372188)

2017-01-02;采用時間:2017-02-13