劉露萍 賈文生 蔡江華

(貴州大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院 貴州 貴陽 550025)

0 引 言

群智能算法是模擬自然界的群體行為構(gòu)造的一類隨機(jī)優(yōu)化算法。隨著群智能算法應(yīng)用越來越廣泛，近些年來已成為人工智能、社會(huì)經(jīng)濟(jì)、政治及生物進(jìn)化等交叉學(xué)科的研究熱點(diǎn)和前沿之一。不同于遺傳算法，群智能算法主要是模擬生物群體智能選擇行為的屬性，同時(shí)蘊(yùn)含了生物體之間互相學(xué)習(xí)與合作的特性。傳統(tǒng)的數(shù)學(xué)分析算法，比如Lemke-Howso算法[1]、全局牛頓算法[2]、單純形剖分算法[3]、同倫算法[4]、分布式原始對(duì)偶算法[5]在工程建設(shè)、網(wǎng)絡(luò)通信、非線性分析、經(jīng)濟(jì)管理等各個(gè)領(lǐng)域具有明顯的優(yōu)勢(shì)。但將其用于Nash均衡的求解時(shí)面臨計(jì)算復(fù)雜度高和計(jì)算時(shí)間長的問題，這時(shí)探究更有效的求Nash均衡解的方法是必要的。因此，考慮從群智能方面來求解和解釋博弈均衡Nash平衡點(diǎn)是一種新的嘗試和方法。博弈論的應(yīng)用廣泛而深刻，特別是非合作博弈，正如2007年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)獲得者M(jìn)yerson在文獻(xiàn)[6]中指出的，要“認(rèn)識(shí)到非合作博弈理論的基礎(chǔ)與核心地位及合作博弈理論是必不可少的補(bǔ)充作用”。非合作博弈的核心概念便是Nash均衡，Roughgarden[7]指出Nash均衡的求解是一個(gè)NP-hard問題，隨著現(xiàn)代智能算法的不斷深入研究和發(fā)展，智能算法在解決NP-hard問題上體現(xiàn)了較強(qiáng)的優(yōu)越性。

1951年，n人非合作有限博弈Nash均衡的存在性被Nash證明[8]。其中Nash均衡解并不是唯一的，Nash也未給出求解Nash均衡解的算法。近些年人們對(duì)智能算法研究越來越普遍，智能算法在計(jì)算博弈Nash均衡問題上顯露出了較強(qiáng)的優(yōu)越性，學(xué)者們也嘗試用免疫算法[9]、自適應(yīng)小生鏡算法[10]、模擬退火算法[11]、啟發(fā)搜索算法[12]、粒子群優(yōu)化算法[13]、煙花算法[14]、投影梯度算法[15]等來求解Nash均衡問題。隨著智能算法的迅速發(fā)展，將Nash均衡轉(zhuǎn)化為最優(yōu)化問題，依賴智能算法尋優(yōu)，成為一種行之有效的方法。因此，本文在量子粒子群算法中引入免疫記憶、自我進(jìn)化機(jī)制并通過概率濃度選擇公式來保持種群的多樣性，建立一種求解Nash均衡的新型協(xié)同免疫量子粒子群算法，并通過對(duì)4個(gè)經(jīng)典數(shù)值算例的計(jì)算和比較，說明了本文算法的有效性，為實(shí)際經(jīng)濟(jì)生活中的博弈活動(dòng)提供決策參考。

1 問題描述

則稱x*為此n人非合作有限博弈的Nash平衡點(diǎn)，此時(shí)每個(gè)局中人都不能單獨(dú)通過改變自己的策略而使自己獲得更大的利益。

假設(shè)是2個(gè)局中人的有限非合作博弈(雙矩陣博弈)：其中局中人1的混合策略為x=(x1,x2,…,xm)，局中人2的混合策略為y=(y1,y2,…,yn)。局中人1和局中人2的支付矩陣分別為Am×n、Bm×n。其期望收益分別為xAyT和xTBy。(x*,y*)是雙矩陣博弈的一個(gè)Nash均衡的充分必要條件是：

2 協(xié)同免疫量子粒子群算法的設(shè)計(jì)

2.1 量子粒子群算法

粒子群優(yōu)化算法(Particle Swarm Optimization algorithm, PSO)具有迭代搜索尋優(yōu)和群體智能等特點(diǎn)，但2001年Bergh證明了PSO算法不能保證收斂到全局最優(yōu)解甚至是局部最優(yōu)解[16]。盡管眾多學(xué)者分別從算法理論分析、算法的改進(jìn)方法、算法在各種工程優(yōu)化領(lǐng)域的應(yīng)用做了大量的研究工作，但實(shí)際上其優(yōu)化效果仍是非常有限的。

2004年，孫俊等[17]從量子力學(xué)的角度提出了一種新型粒子群優(yōu)化算法。該算法建立δ勢(shì)阱勢(shì)能場(chǎng)模型，提出了具有量子行為的粒子群算法(Quantum-Behaved PSO Algorithm, QPSO)。QPSO算法在迭代進(jìn)化計(jì)算過程中終究保持兩個(gè)最優(yōu)位置：1) 粒子i(i=1,2,…,M,M為種群規(guī)模)所經(jīng)歷過的個(gè)體最好位置(有最好的適應(yīng)度值)表示為Pi(t)=[Pi,1(t),Pi,2(t),…,Pi,N(t)]T(N表示問題維度)，記作pbesti(t)。2) 種群中所有粒子經(jīng)歷過的最好位置表示為Pg(t)=[Pg,1(t),Pg,2(t),…,Pg,N(t)]T，記作gbest(t)。其粒子更新公式為：

式中：粒子i的吸引子是由pbesti和gbest之間的隨機(jī)點(diǎn)pi(t)=[pi,1(t),pi,2(t),…,pi,N(t)]T產(chǎn)生，坐標(biāo)為：

pi,j(t)=φi,j(t)·Pi,j(t)+[1-φi,j(t)]·Pg,j(t)

(3)

式中：φi,j(t)=rand()，j=1,2,…,N,rand()表示產(chǎn)生一個(gè)[0,1]之間服從均勻分布的隨機(jī)數(shù)。

在QPSO算法中，用波函數(shù)來描述量子粒子空間中粒子的位置。對(duì)于波函數(shù)，通過求解粒子在δ勢(shì)阱場(chǎng)中運(yùn)動(dòng)的定態(tài)Schr?dinger方程的方法得到粒子在量子空間中某一點(diǎn)出現(xiàn)的概率密度函數(shù)，再通過用MonteCarlo方法得到粒子位置更新公式：

(4)

在QPSO算法中，引入mbest(t)表示平均最好位置，記為C(t)，即：

2.2 協(xié)同免疫量子粒子群算法

免疫算法具有抗原識(shí)別、免疫記憶、抗體抑制和促進(jìn)的特點(diǎn)，是抗體對(duì)抗抗原的過程。本文的協(xié)同免疫量子粒子群算法(Cooperative Immune Quantum Particle Swarm Optimization Algorithm, CIQPSO)將免疫記憶、自我調(diào)節(jié)機(jī)制引入到量子粒子群算法，所有粒子之間信息共享、共同進(jìn)化。為了避免丟失一些適應(yīng)度差但保持較好進(jìn)化趨勢(shì)的粒子，文中引入概率濃度選擇公式來保持粒子種群的多樣性。在CIQPSO中，目標(biāo)函數(shù)和約束條件被視作抗原，問題的解被視作抗體(粒子)。在算法的搜索空間中，每個(gè)抗體都表示問題的一個(gè)解。粒子在可行解空間搜索過程中通過其自身位置最優(yōu)信息和群體位置最優(yōu)信息不斷地調(diào)整自己的當(dāng)前位置，并向全局最優(yōu)解靠攏。

對(duì)于n人有限非合作博弈混合策略的最優(yōu)化問題，Nash均衡點(diǎn)的函數(shù)值最小，適應(yīng)度函數(shù)值最好。在CIQPSO算法中，xi表示粒子i的位置，f(xi)表示粒子i的適應(yīng)度函數(shù)值，i=1,2,…,M+Q。集合X由M+Q個(gè)抗體組成，定義粒子f(xi)到集合X的距離如下：

由文獻(xiàn)[18]，我們將第i個(gè)粒子的濃度定義如下：

定義基于上述粒子濃度的概率選擇公式如下：

對(duì)于一般的博弈模型，所有局中人都會(huì)追求其自身利益的最大化，其最優(yōu)解也將遵循一定的游戲規(guī)則最終達(dá)到一個(gè)動(dòng)態(tài)的平衡。用CIQPSO算法求解n人非合作有限博弈的Nash均衡問題時(shí)，將每一個(gè)Nash均衡解視為一個(gè)粒子，此時(shí)所有博弈方皆采取混合策略，即完全重復(fù)地進(jìn)行博弈，博弈方在其純策略空間上服從概率分布。支付函數(shù)則為各參與人的期望，它是關(guān)于各局中人選擇不同的純策略的概率的多重線性形式。算法中的每一個(gè)粒子由所有局中人的混合策略表示，即x=(x1,x2,…,xn)。定義CIQPSO算法中的適應(yīng)度函數(shù)如下：

因此，由Nash均衡的定義知：x*是n人非合作有限博弈混合策略意義下的一個(gè)Nash均衡解的充分必要條件是：?x*，s.t.f(x*)=0，?x≠x*，f(x)>0。

設(shè)為雙矩陣(m×n維)博弈，算法中每個(gè)粒子由兩個(gè)局中人的策略混合，即z=(x,y)。局中人1、局中人2的混合策略集分別表示為：

即局中人1、局中人2分別在支付矩陣A、B上所有概率分布的集合分別為X、Y。雙矩陣博弈適應(yīng)度函數(shù)定義如下：

式中：Ai.為矩陣Am×n的第i行；B.j為矩陣Bm×n的第j列。同理，若混合局勢(shì)z*是該雙矩陣博弈的一個(gè)Nash均衡解的充分必要條件是：?z*=(x*,y*)， s.t.f(z*)=0，?z≠z*，f(z)>0。

2.3 協(xié)同免疫量子粒子群算法實(shí)現(xiàn)

協(xié)同免疫量子粒子群算法實(shí)現(xiàn)步驟如下：

Step1參數(shù)初始化。確定最大迭代次數(shù)Tmax、精度ε、群體規(guī)模M；

Step2用式(5)計(jì)算粒子平均最好位置mbest；

Step3用式(1)和式(2)更新個(gè)體最好位置和全體最好位置；

Step4根據(jù)適應(yīng)度函數(shù)計(jì)算每個(gè)粒子適應(yīng)度值，找到個(gè)體極值pbest和全體最好極值gbest，并將gbest對(duì)應(yīng)的粒子位置存入記憶庫；

Step5Q個(gè)粒子隨機(jī)生成；

Step6根據(jù)粒子的概率濃度選擇式(6)，從M+Q個(gè)粒子中選取M個(gè)粒子；

Step7用記憶庫中的粒子代替粒子群中適應(yīng)度較差的粒子，生成新一代粒子群p1的同時(shí)再進(jìn)行下一次迭代；

Step8用式(3)計(jì)算粒子群p1得到一個(gè)隨機(jī)位置；

Step9用式(4)計(jì)算粒子新位置；

Step10判斷最大迭代次數(shù)或精度是否達(dá)到要求？是則停止迭代，否則返回Step3。

算法實(shí)現(xiàn)流程如圖1所示。

圖1 CIQPSO算法流程圖

2.4 算法性能的評(píng)價(jià)

協(xié)同免疫量子粒子群算法是一種生物演化的群體智能算法，它與遺傳算法效仿生物界 “物競(jìng)天擇、適者生存” 的演化法則有許多相似之處。所以，可以借鑒Dejong在文獻(xiàn)[19]中提出的定量分析方法，用離線性能來測(cè)試算法的收斂性。

2.5 協(xié)同免疫量子粒子群位置收斂性證明

定理1在N維搜索空間中，按照式(4)進(jìn)化的粒子i的位置依概率收斂到其吸引子pi(t)=[pi,1(t),pi,2(t),…,pi,N(t)]T的充分必要條件是：每一維坐標(biāo)Xi,j(t)都依概率收斂于pi,j。

① 對(duì)于任意的j∈{1,2,…,N)}，恒有

|Xi,j(t)-pi,j|<ε

② 當(dāng)|Xi(t)-pi|≥ε時(shí)，存在j∈{1,2,…,N}使得|Xi,j(t)-pi,j|≥ε，此時(shí)有以下事件包含關(guān)系成立:

{|Xi(t)-pi|≥ε}?{|Xi,j(t)-pi,j|≥ε}

從而:

P{|Xi(t)-pi|≥ε}?P{|Xi,j(t)-pi,j|≥ε}

兩邊求極限得:

兩邊求極限可得到：

3 數(shù)值算例

分別考慮4個(gè)不同的算例，例1是文獻(xiàn)[12]和文獻(xiàn)[20]共同給出的一個(gè)博弈算例。例2是文獻(xiàn)[21]，此問題至少有6個(gè)解。例3是文獻(xiàn)[22]中非合作雙矩陣博弈模型，例3的對(duì)策問題只有唯一解。例4表示例1推廣到10×10階高維矩陣。分別用協(xié)同免疫量子粒子群算法求解4個(gè)算例，算法中參數(shù)值設(shè)置為：M=20，Q=10，最大迭代次數(shù)的參數(shù)設(shè)置為150，例1和例4適應(yīng)度函數(shù)精度為ε=10-4，例2和例3適應(yīng)度函數(shù)精度為ε=10-2。

例1考慮3×3非合作矩陣博弈Γ(X1,Y1,A1,B1)對(duì)策Nash均衡點(diǎn)，支付矩陣如下：

例2考慮4×4非合作矩陣博弈Γ(X2,Y2,A2,B2)對(duì)策的Nash均衡點(diǎn)，支付矩陣如下：

例3考慮3×4非合作矩陣博弈Γ(X3,Y3,A3,B3)對(duì)策的Nash均衡點(diǎn)，支付矩陣如下：

例4考慮10×10雙矩陣博弈Γ(X4,Y4,A4,B4)對(duì)策的Nash均衡點(diǎn)，支付矩陣如下：

將上面4個(gè)例子的數(shù)據(jù)代入?yún)f(xié)同免疫量子粒子群算法中得到的運(yùn)行結(jié)果如表1-表4所示。

表1 Γ(X1,Y1,A1,B1)運(yùn)行結(jié)果

表2 Γ(X2,Y2,A2,B2)運(yùn)行結(jié)果

表3 Γ(X3,Y3,A3,B3)運(yùn)行結(jié)果

表4 Γ(X4,Y4,A4,B4)運(yùn)行結(jié)果

例1，由6次實(shí)驗(yàn)可知，用CIQPSO算法求得該博弈的近似解為(0.333 3, 0.333 3, 0.333 3；0.333 3, 0.333 3, 0.333 3)，平均只需進(jìn)化到121代。優(yōu)于免疫粒子群算法計(jì)算的288代結(jié)果[9]，也優(yōu)于基本粒子群算法計(jì)算的376代結(jié)果[23]，更優(yōu)于遺傳算法計(jì)算的400代結(jié)果[20]。所以，本文的協(xié)同免疫量子粒子群算法的收斂速度確實(shí)得到了很大程度的改進(jìn)。在相同的計(jì)算機(jī)上，與免疫粒子群算法比較，協(xié)同免疫量子粒子群算法收斂速度更快，迭代次數(shù)更少。其離線性能如圖2所示。

圖2 協(xié)同免疫量子粒子算法與免疫粒子群算法求解Γ(X1,Y1,A1,B1)的離線性能比較

由圖2可知，兩條曲線分別表示CIQPSO算法和IPSO算法求解例1博弈均衡解的離線性能曲線。CIQPSO算法收斂比較快，明顯優(yōu)于IPSO算法，又因文獻(xiàn)[8]給出的IPSO算法求解博弈的離線性能優(yōu)于文獻(xiàn)[12]給出的PSO算法。所以，本文提出的CIQPSO算法優(yōu)于文獻(xiàn)[23]和文獻(xiàn)[9]提出的算法。另外，當(dāng)?shù)螖?shù)到達(dá)121代左右時(shí)，離線性能基本趨近于0，說明CIQPSO算法求出的近似解基本接近精確解，具有較好的收斂性能。

例2，運(yùn)行6次實(shí)驗(yàn)結(jié)果輸出的6個(gè)解分別屬于6個(gè)不同的精確解，且6個(gè)精確解皆是不同的Nash均衡解。協(xié)同免疫量子粒子群算法求解例2平均進(jìn)化到12代就得到該博弈的6個(gè)不同的Nash均衡解。6次運(yùn)行結(jié)果的平均時(shí)間為0.200 947秒，可知該算法的計(jì)算時(shí)間精度優(yōu)于文獻(xiàn)[10]。而文獻(xiàn)[13]給出的算法，需要運(yùn)行30或40次才能求出5個(gè)不同的精確解，事實(shí)上，文獻(xiàn)[24]中反復(fù)運(yùn)行算法求出的多個(gè)Nash均衡解具有很大的隨機(jī)性，并不能保證每次運(yùn)行能得到不同的Nash均衡解，很有可能運(yùn)行30次以后只得到同一個(gè)Nash均衡解。文獻(xiàn)[9]雖只需運(yùn)行1次主算法，卻不能得到所有Nash均衡解，在其計(jì)算過程中，還需多次調(diào)用粒子群優(yōu)化算法來調(diào)整小生鏡半徑，計(jì)算的空間復(fù)雜度和時(shí)間復(fù)雜度都比協(xié)同免疫量子粒子群算法要求更高。其離線性能如圖3所示。

圖3 協(xié)同免疫量子粒子算法與免疫粒子群算法求解Γ(X2,Y2,A2,B2)的離線性能比較

由圖3知，兩條曲線分別表示CIQPSO算法和IPSO算法求解例2博弈均衡解的離線性能曲線。CIQPSO算法收斂比較快，明顯要優(yōu)于IPSO算法。所以，本文提出的CIQPSO算法優(yōu)于IPSO算法。

例3，只需1次實(shí)驗(yàn)運(yùn)行結(jié)果就得到例3博弈的精確解為(0, 0.714 2, 0.285 8；0.833 5, 0, 0.166 5, 0)，運(yùn)行時(shí)間只需0.058 59秒。這表明該算法的計(jì)算精確度高，收斂速度快。

例4，針對(duì)策略為10×10階的高維雙矩陣博弈，本文提出的CIQPSO算法平均進(jìn)化到2.6代后得到該博弈的近似解為(0.097 9, 0.103 4, 0.085 9, 0.101 3, 0.095 5, 0.111 8, 0.091 9, 0.098 7, 0.093 1, 0.120 5； 0.091 4, 0.081 9, 0.114 1, 0.087 8, 0.103 2, 0.106 1, 0.121 9, 0.080 7, 0.104 2, 0.108 7)。進(jìn)一步探討了該算法可以進(jìn)一步推廣到求解高維的雙矩陣博弈。

由例1-例4數(shù)值算例的計(jì)算和比較可知，用CIQPSO算法在求解Nash均衡方面具有較好的性能，在算法精度、迭代次數(shù)、迭代時(shí)間都比IPSO算法有了進(jìn)一步提高，算法的空間復(fù)雜度和時(shí)間復(fù)雜度都得到了一定改善。另外，粒子在隨機(jī)生成的過程中不依賴于初始點(diǎn)的選取，并通過概率濃度選擇公式來保持種群多樣性，避免丟失可能成為最優(yōu)解的潛在解，因此更有可能找尋到全局最優(yōu)解，避免陷入局部最優(yōu)解的早熟現(xiàn)象。

4 結(jié) 語

本文提出的CIQPSO算法將免疫記憶、自我進(jìn)化引入QPSO算法中，并通過概率濃度選擇公式來保持種群的多樣性。將該算法應(yīng)用到求解n人有限非合作博弈中，通過實(shí)驗(yàn)可以看出改進(jìn)后的算法大大節(jié)約了收斂的時(shí)間，提高了算法效率，較好地克服了量子粒子群算法的早熟現(xiàn)象。另外，CIQPSO算法仍是一種群體智能迭代算法，在算法迭代搜索過程中，每一個(gè)粒子記錄自身的最優(yōu)位置，并向其他粒子學(xué)習(xí)。通過粒子的個(gè)性化學(xué)習(xí)和彼此間的協(xié)作，促使群體不斷向問題最優(yōu)解逼近，同時(shí)所有局中人都會(huì)向個(gè)體極值和群體極值學(xué)習(xí)，最終趨向博弈的均衡點(diǎn)。下一步研究中，可將該算法應(yīng)用于更加復(fù)雜的博弈求解問題。