杨彦龙　向淑文，　夏顺友　贾文生

1(贵州大学计算机科学与技术学院　贵州 贵阳 550025) 2(贵州大学数学与统计学院　贵州 贵阳 550025)

0　引　言

随着经济全球化深入发展，博弈论研究持续活跃，特别是诺贝尔经济学奖多次授予从事博弈论研究与应用的学者，博弈论被广泛地应用到经济学、社会学、计算机科学等许多领域。Nash均衡是非合作博弈最核心的概念，关于Nash均衡的研究主要涉及存在性、稳定性及机制设计等。由于Nash均衡问题的算法是PPAD-Complete，因此关于Nash均衡问题的算法研究相对较为棘手。Lemke和Howson提出了二人有限非合作博弈模型的互补转轴算法，即Lemke-Howson算法[1]；Govindan等[2]利用结构定理及同论方法提出了一种全局Newton算法；Zhang等[3]利用拟变分不等式提出了广义博弈模型的投影算法；Herings等[4]提出了的同伦算法；Yuan[5]利用信赖域算法计算Nash均衡，并证明了在一定条件下该算法是全局收敛且局部超线性逼近。以上算法为数值算法，该类算法保证了算法的收敛性，意义在于证明了博弈问题的可计算性，但计算方法较为复杂且运行时间较长。近年来，学者受某些自然界生物进化的启发，利用一些智能算法计算Nash均衡，比如：蚁群算法、遗传算法、粒子群算法等智能算法[6-9]。智能算法为Nash均衡计算提供了新的研究方法和途径。受烟花在夜空中爆炸产生火花照亮周围区域这一现象的启发，Tan等[10]提出了烟花算法(FWA)。烟花算法属于启发式算法，利用爆炸算子、高斯变异和选择策略较快地寻找到全局最优解，随后许多学者对烟花算法进行了研究及应用，关于烟花算法的最新研究进展参考文献[11-12]。文献[13]提出了融合佳点集变异机制的动态搜索烟花爆炸算法。文献[14]引入淘汰机制，提出了一种混沌烟花搜索算法。文献[15]将烟花算法应用于云计算多目标任务调度。文献[16]应用烟花算法求解JSP问题。文献[17]提出了多目标烟花算法并应用于施肥问题。本文基于烟花算法求解N人有限非合作博弈的Nash均衡，并通过与文献[8-9]中免疫粒子群算法的比较，实验结果验证了该算法的有效性。

1　问题描述

设N人有限非合作博弈模型用三元组Γ(N,{Si}i∈N,{ui}i∈N)表示，其中N表示局中人的个数，Si={si1,si2,…,sim}表示局中人i的有限个策略的策略集，S=S1×S2×…×SN表示N个局中人的策略乘积空间，ui:S→表示局中人i的收益函数。对于任意策略组合s=(s1,s2,…,sN)∈S，为了表述方便，用表示在策略组合s中局中人i的策略替换为其他局中人的策略不变；以下公式中出现类似的表示，意义与此相同。

称Si={si1,si2,…,sim}的凸组合集Xi={(xi1,xi2,…,xim)|xi1+xi2+…+xim=1,xij≥0}为局中人i的混合策略空间，xi∈Xi表示局中人i选取纯策略的概率分布，X=X1×X2×…×XN表示N个局中人的策略乘积空间，局中人i的收益函数仍用ui:X→表示。

显然，纯策略Nash均衡是混合策略Nash均衡的特殊情况。

性质1混合策略均衡x*是Γ的Nash均衡解的充分必要条件是：对于任意的局中人i的每一个纯策略sij(1≤j≤im)，有ui(x*)≥ui(x*;sij)成立。

若N=2，则Γ是双矩阵博弈，局中人的收益分别用矩阵A、B表示，则是双矩阵博弈一个Nash均衡解的充分必要条件是：

2　烟花算法的设计

2.1　烟花算法的基本思想

烟花算法是受烟花在夜空中爆炸产生火花这一现象的启发演变而来的群体智能算法。在烟花算法中，每一个火花被看作问题解空间的一个可行解，根据火花爆炸的范围和强度，设定的爆炸搜索机制产生下一代火花群体，对于适应度值较好的火花，在下一代中在较小范围内产生较多的火花；对于适应度较差的火花，在下一代中消失或者发生变异。允许一定数量的火花发生变异，增加火花种群的多样性，避免算法过早陷入局部收敛。如此循环下去直到产生满意的火花为止。在烟花算法中，有三个重要组成部分：爆炸算子、变异算子和选择策略。各类算子的设计决定了烟花算法的优劣。

烟花算法具体步骤如下：

Step1在可行域内随机产生一定数量的烟花。

Step2根据爆炸算子，计算每个烟花的爆炸半径和火花数量，生成每个烟花的火花，根据变异算子产生变异火花。

Step3判断是否满足停止条件，否则进入Step4。

Step4根据选择策略，选出下一代烟花，返回Step2。

2.2　Nash均衡求解的烟花算法设计

算法中每一个烟花表示所有局中人的混合策略x=(x1,x2，…,xm)，定义N人有限非合作博弈Nash均衡求解的适应度值函数为：

根据性质1可知，若x*为N人有限非合作博弈的Nash均衡解的等价条件为：f(x*)=0。

特别地，对于2人有限非合作博弈Nash均衡求解的适应度值函数为：

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

2.2.1爆炸算子

根据爆炸算子计算出烟花爆炸的半径ri及产生的火花数量ki，其中:

2.2.2变异算子

为了避免算法过早陷入局部收敛，增加下一代火花种群的多样性，引入高斯变异火花，即在烟花种群产生的火花中随机选取1个(或几个)火花xi，然后对选中的火花的1个(或几个)维度xik执行如下操作：

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

2.2.3选择策略

在由烟花、火花、变异火花组成的候选集中，选出适应度值最小的n个个体作为下一代烟花。

本文算法的实现步骤如下：

Step1确定烟花的数目n，烟花爆炸最大半径R，烟花群生成火花总数目K，最大迭代次数N，精度ε0。

Step2随机产生n个烟花，计算每个烟花的适应度值，若适应度值满足ε0，则进入Step7。

Step3根据爆炸算子计算烟花xi的爆炸半径ri，及产生火花的数目ki，生成烟花xi的ki个火花，对火花进行越界检测。

Step5计算火花、变异火花的适应度值，若满足精度要求且未达到最大迭代次数则进入Step6，否则进入Step7。

Step6根据选择策略选，在所有烟花、火花、高斯变异火花中选择n个个体作为下一代烟花，进入Step2。

Step7运算停止。

3　数值实例

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

例2监察博弈Γ(X2,Y2,A2,B2)。

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

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

利用烟花算法求解例1，经过5次实验，平均迭代9次给出了精确解，虽然文献[8]用免疫粒子群算法平均迭代7次，但其适应度值的精度低于10-3。

利用本文的烟花算法求解例2，经过5次实验，平均迭代12.8次，适应度值的精度达到10-3，文献[8]用免疫粒子群算法平均迭代14次，但其适应度值的精度低于10-3。

在例4中，针对博弈策略矩阵为10阶的高维方阵，引入离线性能函数比较烟花算法与粒子群算法搜索Nash均衡的能力，从图形可以看出，在初始阶段烟花算法较慢，但在后阶段，烟花算法搜索效果明显较好。

例1-例3的运算结果见表1-表3；例4的运算结果见图1。

表1　例1的运算结果

表2　例2的运算结果

表3　例3的运算结果

图1　fwa算法与pso算法的离线性能比较

4　结　语

通过以上的实例结果可知，烟花算法是求解N人有限非合作博弈Nash均衡问题的一种有效算法。烟花算法是一种群体智能算法，算法中参数设置较少，对目标函数要求较低，由于Nash均衡求解问题的计算是PPAD-Complete，其构造的适应度值函数又非一般意义下的函数甚至非光滑，这些问题本身的限制，使得烟花算法在求解Nash均衡时具有一定的优势。今后将考虑分析不同的爆炸算子、变异算子和选择策略对Nash均衡求解的影响，并考虑更复杂的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] 邱中华,高洁,朱跃星. 应用免疫算法求解博弈问题[J].系统工程学报,2006,21(4):398-404.

[7] 王志勇,韩旭,许维胜,等.基于改进蚁群算法的纳什均衡求解 [J].计算机工程,2010,36(14):166-171.

[8] 贾文生,向淑文,杨剑锋,等.基于免疫粒子群算法的广义Nash均衡问题求解[J].计算机应用研究,2013,30(9):2637-2640.

[9] 贾文生,向淑文,杨剑锋,等.基于自适应小生境粒子群算法的多重Nash均衡求解[J].计算机应用与软件,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].智能系统学报,2014,9(5):515-528.

[12] 谭营.烟花算法引论[M].北京：科学出版社,2015:23-28.

[13] 王培崇.融合佳点集机制的动态搜索烟花爆炸搜索算法[J].计算机应用与软件,2015,32(8):248-251.

[14] 王培崇,李丽荣.改进的混合混沌烟花爆炸搜索算法[J].微电子学与计算机,2014,31(11):69-73.

[15] 黄伟建, 郭芳. 基于烟花算法的云计算多目标任务调度[J].计算机应用研究, 2017,34(6):1718-1720.

[16] 包晓晓, 叶春明, 黄霞. 烟花算法求解JSP问题的研究[J].计算机工程与应用, 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.