基于煙花算法的非合作博弈Nash均衡問題求解

楊彥龍　向淑文，　夏順友　賈文生

1(貴州大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院　貴州 貴陽 550025) 2(貴州大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院　貴州 貴陽 550025)

0　引　言

隨著經(jīng)濟(jì)全球化深入發(fā)展，博弈論研究持續(xù)活躍，特別是諾貝爾經(jīng)濟(jì)學(xué)獎多次授予從事博弈論研究與應(yīng)用的學(xué)者，博弈論被廣泛地應(yīng)用到經(jīng)濟(jì)學(xué)、社會學(xué)、計算機(jī)科學(xué)等許多領(lǐng)域。Nash均衡是非合作博弈最核心的概念，關(guān)于Nash均衡的研究主要涉及存在性、穩(wěn)定性及機(jī)制設(shè)計等。由于Nash均衡問題的算法是PPAD-Complete，因此關(guān)于Nash均衡問題的算法研究相對較為棘手。Lemke和Howson提出了二人有限非合作博弈模型的互補(bǔ)轉(zhuǎn)軸算法，即Lemke-Howson算法[1]；Govindan等[2]利用結(jié)構(gòu)定理及同論方法提出了一種全局Newton算法；Zhang等[3]利用擬變分不等式提出了廣義博弈模型的投影算法；Herings等[4]提出了的同倫算法；Yuan[5]利用信賴域算法計算Nash均衡，并證明了在一定條件下該算法是全局收斂且局部超線性逼近。以上算法為數(shù)值算法，該類算法保證了算法的收斂性，意義在于證明了博弈問題的可計算性，但計算方法較為復(fù)雜且運(yùn)行時間較長。近年來，學(xué)者受某些自然界生物進(jìn)化的啟發(fā)，利用一些智能算法計算Nash均衡，比如：蟻群算法、遺傳算法、粒子群算法等智能算法[6-9]。智能算法為Nash均衡計算提供了新的研究方法和途徑。受煙花在夜空中爆炸產(chǎn)生火花照亮周圍區(qū)域這一現(xiàn)象的啟發(fā)，Tan等[10]提出了煙花算法(FWA)。煙花算法屬于啟發(fā)式算法，利用爆炸算子、高斯變異和選擇策略較快地尋找到全局最優(yōu)解，隨后許多學(xué)者對煙花算法進(jìn)行了研究及應(yīng)用，關(guān)于煙花算法的最新研究進(jìn)展參考文獻(xiàn)[11-12]。文獻(xiàn)[13]提出了融合佳點(diǎn)集變異機(jī)制的動態(tài)搜索煙花爆炸算法。文獻(xiàn)[14]引入淘汰機(jī)制，提出了一種混沌煙花搜索算法。文獻(xiàn)[15]將煙花算法應(yīng)用于云計算多目標(biāo)任務(wù)調(diào)度。文獻(xiàn)[16]應(yīng)用煙花算法求解JSP問題。文獻(xiàn)[17]提出了多目標(biāo)煙花算法并應(yīng)用于施肥問題。本文基于煙花算法求解N人有限非合作博弈的Nash均衡，并通過與文獻(xiàn)[8-9]中免疫粒子群算法的比較，實(shí)驗(yàn)結(jié)果驗(yàn)證了該算法的有效性。

1　問題描述

設(shè)N人有限非合作博弈模型用三元組Γ(N,{Si}i∈N,{ui}i∈N)表示，其中N表示局中人的個數(shù)，Si={si1,si2,…,sim}表示局中人i的有限個策略的策略集，S=S1×S2×…×SN表示N個局中人的策略乘積空間，ui:S→表示局中人i的收益函數(shù)。對于任意策略組合s=(s1,s2,…,sN)∈S，為了表述方便，用表示在策略組合s中局中人i的策略替換為其他局中人的策略不變；以下公式中出現(xiàn)類似的表示，意義與此相同。

稱Si={si1,si2,…,sim}的凸組合集Xi={(xi1,xi2,…,xim)|xi1+xi2+…+xim=1,xij≥0}為局中人i的混合策略空間，xi∈Xi表示局中人i選取純策略的概率分布，X=X1×X2×…×XN表示N個局中人的策略乘積空間，局中人i的收益函數(shù)仍用ui:X→表示。

顯然，純策略Nash均衡是混合策略Nash均衡的特殊情況。

性質(zhì)1混合策略均衡x*是Γ的Nash均衡解的充分必要條件是：對于任意的局中人i的每一個純策略sij(1≤j≤im)，有ui(x*)≥ui(x*;sij)成立。

若N=2，則Γ是雙矩陣博弈，局中人的收益分別用矩陣A、B表示，則是雙矩陣博弈一個Nash均衡解的充分必要條件是：

2　煙花算法的設(shè)計

2.1　煙花算法的基本思想

煙花算法是受煙花在夜空中爆炸產(chǎn)生火花這一現(xiàn)象的啟發(fā)演變而來的群體智能算法。在煙花算法中，每一個火花被看作問題解空間的一個可行解，根據(jù)火花爆炸的范圍和強(qiáng)度，設(shè)定的爆炸搜索機(jī)制產(chǎn)生下一代火花群體，對于適應(yīng)度值較好的火花，在下一代中在較小范圍內(nèi)產(chǎn)生較多的火花；對于適應(yīng)度較差的火花，在下一代中消失或者發(fā)生變異。允許一定數(shù)量的火花發(fā)生變異，增加火花種群的多樣性，避免算法過早陷入局部收斂。如此循環(huán)下去直到產(chǎn)生滿意的火花為止。在煙花算法中，有三個重要組成部分：爆炸算子、變異算子和選擇策略。各類算子的設(shè)計決定了煙花算法的優(yōu)劣。

煙花算法具體步驟如下：

Step1在可行域內(nèi)隨機(jī)產(chǎn)生一定數(shù)量的煙花。

Step2根據(jù)爆炸算子，計算每個煙花的爆炸半徑和火花數(shù)量，生成每個煙花的火花，根據(jù)變異算子產(chǎn)生變異火花。

Step3判斷是否滿足停止條件，否則進(jìn)入Step4。

Step4根據(jù)選擇策略，選出下一代煙花，返回Step2。

2.2　Nash均衡求解的煙花算法設(shè)計

算法中每一個煙花表示所有局中人的混合策略x=(x1,x2，…,xm)，定義N人有限非合作博弈Nash均衡求解的適應(yīng)度值函數(shù)為：

根據(jù)性質(zhì)1可知，若x*為N人有限非合作博弈的Nash均衡解的等價條件為：f(x*)=0。

特別地，對于2人有限非合作博弈Nash均衡求解的適應(yīng)度值函數(shù)為：

式中:Ai.表示矩陣A的第i行向量，B.j表示矩陣B的第j列向量。同理可知，若x*為2人有限非合作博弈的Nash均衡解的等價條件為：f(x*)=0。

2.2.1爆炸算子

根據(jù)爆炸算子計算出煙花爆炸的半徑ri及產(chǎn)生的火花數(shù)量ki，其中:

2.2.2變異算子

為了避免算法過早陷入局部收斂，增加下一代火花種群的多樣性，引入高斯變異火花，即在煙花種群產(chǎn)生的火花中隨機(jī)選取1個(或幾個)火花xi，然后對選中的火花的1個(或幾個)維度xik執(zhí)行如下操作：

式中：e～N(1,1)，即e服從均值為1，方差為1的高斯分布。

2.2.3選擇策略

在由煙花、火花、變異火花組成的候選集中，選出適應(yīng)度值最小的n個個體作為下一代煙花。

本文算法的實(shí)現(xiàn)步驟如下：

Step1確定煙花的數(shù)目n，煙花爆炸最大半徑R，煙花群生成火花總數(shù)目K，最大迭代次數(shù)N，精度ε0。

Step2隨機(jī)產(chǎn)生n個煙花，計算每個煙花的適應(yīng)度值，若適應(yīng)度值滿足ε0，則進(jìn)入Step7。

Step3根據(jù)爆炸算子計算煙花xi的爆炸半徑ri，及產(chǎn)生火花的數(shù)目ki，生成煙花xi的ki個火花，對火花進(jìn)行越界檢測。

Step5計算火花、變異火花的適應(yīng)度值，若滿足精度要求且未達(dá)到最大迭代次數(shù)則進(jìn)入Step6，否則進(jìn)入Step7。

Step6根據(jù)選擇策略選，在所有煙花、火花、高斯變異火花中選擇n個個體作為下一代煙花，進(jìn)入Step2。

Step7運(yùn)算停止。

3　數(shù)值實(shí)例

例1囚徒困境博弈Γ(X1,Y1,A1,B1)。

例2監(jiān)察博弈Γ(X2,Y2,A2,B2)。

例3博弈Γ(X3,Y3,A3,B3)。

例4博弈Γ(X4,Y4,A4,B4)。

利用煙花算法求解例1，經(jīng)過5次實(shí)驗(yàn)，平均迭代9次給出了精確解，雖然文獻(xiàn)[8]用免疫粒子群算法平均迭代7次，但其適應(yīng)度值的精度低于10-3。

利用本文的煙花算法求解例2，經(jīng)過5次實(shí)驗(yàn)，平均迭代12.8次，適應(yīng)度值的精度達(dá)到10-3，文獻(xiàn)[8]用免疫粒子群算法平均迭代14次，但其適應(yīng)度值的精度低于10-3。

在例4中，針對博弈策略矩陣為10階的高維方陣，引入離線性能函數(shù)比較煙花算法與粒子群算法搜索Nash均衡的能力，從圖形可以看出，在初始階段煙花算法較慢，但在后階段，煙花算法搜索效果明顯較好。

例1-例3的運(yùn)算結(jié)果見表1-表3；例4的運(yùn)算結(jié)果見圖1。

表1　例1的運(yùn)算結(jié)果

表2　例2的運(yùn)算結(jié)果

表3　例3的運(yùn)算結(jié)果

圖1　fwa算法與pso算法的離線性能比較

4　結(jié)　語

通過以上的實(shí)例結(jié)果可知，煙花算法是求解N人有限非合作博弈Nash均衡問題的一種有效算法。煙花算法是一種群體智能算法，算法中參數(shù)設(shè)置較少，對目標(biāo)函數(shù)要求較低，由于Nash均衡求解問題的計算是PPAD-Complete，其構(gòu)造的適應(yīng)度值函數(shù)又非一般意義下的函數(shù)甚至非光滑，這些問題本身的限制，使得煙花算法在求解Nash均衡時具有一定的優(yōu)勢。今后將考慮分析不同的爆炸算子、變異算子和選擇策略對Nash均衡求解的影響，并考慮更復(fù)雜的Nash均衡求解問題。

[1] Lemke C, Howson J. Equilibrium points of bimatrix games[J].Journal of Society for Industrial and Applied Mathematics,1964,12(2):431-423.

[2] Govindan S, Wilson R. A global Newton method for computing Nash equilibria[J].Journal of Economic Theory,2003,110(1):65-86.

[3] Zhang Jian-zhong, Qu Biao, Xiu Nai-hua. Some projection-like methods for the generalized Nash equilibria[J].Computational Optimization and Applications, 2010, 45(1):89-109.

[4] Herings P J J,Peeters R. Homotopy methods to compute equilibria in game theory[J].Economic Theory, 2010,42(1):119-156.

[5] Yuan Ya-xiang. A trust region algorithm for Nash equilibria problems[J].Pacific Journal of Optimization, 2011,7(1):125-138.

[6] 邱中華,高潔,朱躍星. 應(yīng)用免疫算法求解博弈問題[J].系統(tǒng)工程學(xué)報,2006,21(4):398-404.

[7] 王志勇,韓旭,許維勝,等.基于改進(jìn)蟻群算法的納什均衡求解 [J].計算機(jī)工程,2010,36(14):166-171.

[8] 賈文生,向淑文,楊劍鋒,等.基于免疫粒子群算法的廣義Nash均衡問題求解[J].計算機(jī)應(yīng)用研究,2013,30(9):2637-2640.

[9] 賈文生,向淑文,楊劍鋒,等.基于自適應(yīng)小生境粒子群算法的多重Nash均衡求解[J].計算機(jī)應(yīng)用與軟件,2015,32(1):247-250.

[10] Tan Y, Zhu Y. Fireworks algorithm for optimization[C]//International Conference on Advances in Swarm Intelligence. Springer-Verlag,2010:355-364.

[11] 譚營,鄭少秋.煙花算法研究進(jìn)展[J].智能系統(tǒng)學(xué)報,2014,9(5):515-528.

[12] 譚營.煙花算法引論[M].北京：科學(xué)出版社,2015:23-28.

[13] 王培崇.融合佳點(diǎn)集機(jī)制的動態(tài)搜索煙花爆炸搜索算法[J].計算機(jī)應(yīng)用與軟件,2015,32(8):248-251.

[14] 王培崇,李麗榮.改進(jìn)的混合混沌煙花爆炸搜索算法[J].微電子學(xué)與計算機(jī),2014,31(11):69-73.

[15] 黃偉建, 郭芳. 基于煙花算法的云計算多目標(biāo)任務(wù)調(diào)度[J].計算機(jī)應(yīng)用研究, 2017,34(6):1718-1720.

[16] 包曉曉, 葉春明, 黃霞. 煙花算法求解JSP問題的研究[J].計算機(jī)工程與應(yīng)用, 2017,53(3):247-252.

[17] Zheng Y J,Song Q,Chen S Y.Multiobjective fire-works optimization for variable-rate fertilization in oil crop production[J].Applied Soft Computing,2013,13(11):4253-4263.