协同免疫量子粒子群算法求非合作博弈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算法仍是一种群体智能迭代算法，在算法迭代搜索过程中，每一个粒子记录自身的最优位置，并向其他粒子学习。通过粒子的个性化学习和彼此间的协作，促使群体不断向问题最优解逼近，同时所有局中人都会向个体极值和群体极值学习，最终趋向博弈的均衡点。下一步研究中，可将该算法应用于更加复杂的博弈求解问题。