協同免疫量子粒子群算法求非合作博弈Nash均衡解

劉露萍 賈文生 蔡江華

(貴州大學數學與統計學院 貴州 貴陽 550025)

0 引 言

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

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

1 問題描述

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

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

2 協同免疫量子粒子群算法的設計

2.1 量子粒子群算法

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

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

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

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()表示產生一個[0,1]之間服從均勻分布的隨機數。

在QPSO算法中，用波函數來描述量子粒子空間中粒子的位置。對于波函數，通過求解粒子在δ勢阱場中運動的定態Schr?dinger方程的方法得到粒子在量子空間中某一點出現的概率密度函數，再通過用MonteCarlo方法得到粒子位置更新公式：

(4)

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

2.2 協同免疫量子粒子群算法

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

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

由文獻[18]，我們將第i個粒子的濃度定義如下：

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

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

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

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

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

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

2.3 協同免疫量子粒子群算法實現

協同免疫量子粒子群算法實現步驟如下：

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

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

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

Step4根據適應度函數計算每個粒子適應度值，找到個體極值pbest和全體最好極值gbest，并將gbest對應的粒子位置存入記憶庫；

Step5Q個粒子隨機生成；

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

Step7用記憶庫中的粒子代替粒子群中適應度較差的粒子，生成新一代粒子群p1的同時再進行下一次迭代；

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

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

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

算法實現流程如圖1所示。

圖1 CIQPSO算法流程圖

2.4 算法性能的評價

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

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

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

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

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

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

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

從而:

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

兩邊求極限得:

兩邊求極限可得到：

3 數值算例

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

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

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

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

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

將上面4個例子的數據代入協同免疫量子粒子群算法中得到的運行結果如表1-表4所示。

表1 Γ(X1,Y1,A1,B1)運行結果

表2 Γ(X2,Y2,A2,B2)運行結果

表3 Γ(X3,Y3,A3,B3)運行結果

表4 Γ(X4,Y4,A4,B4)運行結果

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

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

由圖2可知，兩條曲線分別表示CIQPSO算法和IPSO算法求解例1博弈均衡解的離線性能曲線。CIQPSO算法收斂比較快，明顯優于IPSO算法，又因文獻[8]給出的IPSO算法求解博弈的離線性能優于文獻[12]給出的PSO算法。所以，本文提出的CIQPSO算法優于文獻[23]和文獻[9]提出的算法。另外，當迭代次數到達121代左右時，離線性能基本趨近于0，說明CIQPSO算法求出的近似解基本接近精確解，具有較好的收斂性能。

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

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

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

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

例4，針對策略為10×10階的高維雙矩陣博弈，本文提出的CIQPSO算法平均進化到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)。進一步探討了該算法可以進一步推廣到求解高維的雙矩陣博弈。

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

4 結 語

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