两阶段多峰优化算法求解纳什均衡

两阶段多峰优化算法求解纳什均衡 Two-Stage Multimodal Optimization Algorithm for Solving Nash Equilibrium 1 2 first-author 李焕哲，男，博士生，讲师，研究方向为智能计算、机器学习. E-mail:lihuanzhe@whu.edu.cn 李焕哲，男，博士生，讲师，研究方向为智能计算、机器学习. E-mail: lihuanzhe@whu.edu.cn lihuanzhe@whu.edu.cn 1 corresp E-mail:zhijianwu@whu.edu.cn E-mail:zhijianwu@whu.edu.cn zhijianwu@whu.edu.cn 3 武汉大学 计算机学院/软件工程国家重点实验室, 湖北 武汉 430072 武汉大学 计算机学院/软件工程国家重点实验室, 湖北 武汉 430072 State Key Laboratory of Software Engineering/School of Gomputer, Wuhan University, Wuhan 430072, Hubei, China State Key Laboratory of Software Engineering/School of Gomputer, Wuhan University, Wuhan 430072, Hubei, China 河北地质大学 信息工程学院,河北 石家庄 050031 河北地质大学 信息工程学院,河北 石家庄 050031 School of Information Engineering, Hebei GEO University, Shijiazhuang 050031, Hebei, China School of Information Engineering, Hebei GEO University, Shijiazhuang 050031, Hebei, China 江西理工大学 理学院, 江西 赣州 341000 江西理工大学 理学院, 江西 赣州 341000 School of Science, Jiangxi University of Science and Technology, Ganzhou 341000, Jiangxi, China School of Science, Jiangxi University of Science and Technology, Ganzhou 341000, Jiangxi, China 提出了一种两阶段多峰优化算法用于求解一个博弈中的全部纳什均衡.第一阶段首先运行带有邻域变异策略的NCDE算法进行粗粒度搜索，定位最优解的粗略位置.第二阶段运行多个CMA-ES实例在已找的位置上同时进行局部精细搜索.此外，提出了一种搜索点补充策略，用于增强演化初期的搜索能力及保持子种群的稳定性.提出的算法和6个经典算法在10个纳什均衡问题上进行了比较.实验结果表明提出的算法在5个问题上取得了最好结果，4个问题上取得的结果与其他算法相同. This paper proposed a two-stage multimodal optimization algorithm for solving all Nash Equilibrium of a game. The neighborhood based crowding differential evolution (NCDE) algorithm with neighborhood mutation is firstly conducted to search approximate positions of global optima. After NCDE runs a certain number of iterations, multiple covariance matrix adaptation evolution strategy (CMA-ES) instances are simultaneously used to perform fine search on all positions which are found by NCDE. Additionally, search point replenishment strategy (SPRS) is put forward to enhance search ability in the initial stage of evolution, and to maintain the stability of subpopulations. The proposed algorithm is compared with six state-of-the-art algorithms on ten Nash Equilibrium problems. Experimental results manifest that the proposed algorithm achieves the best results on five problems, and same results on four problems. 纳什均衡 非合作博弈 邻域变异 协方差矩阵自适应演化策略 Nash Equilibrium non-cooperative game neighborhood mutation covariance matrix adaptation evolution strategy 引 言 1 纳什均衡(Nash Equilibrium)又被称为非合作博弈均衡，是博弈论中的一个重要研究内容.纳什均衡是一种策略组合，它要求每个参与人的策略对其他参与人的策略均是最优反应.纳什均衡理论被广泛应用于社会、经济、军事、政治、科研等领域.纳什在文献 [ 1 1 , 2 2 ] 中给出了纳什均衡的定义并证明了纳什均衡解的存在性.实际上，一个博弈可能存在多个纳什均衡，而在有限策略博弈中纳什均衡的计算是一项具有挑战性的任务.求解纳什均衡的算法主要有Lemke-Howson 算法 [ 3 3 ] 、单纯型剖分算法 [ 4 4 ] 、全局牛顿算法 [ 5 5 ] 、同伦算法 [ 6 6 ] 、函数极小化算法 [ 7 7 ] 和多矩阵迭代算法 [ 8 8 ] 等，这些算法大多计算过程复杂难于实现.为了简化求解过程，学者们提出了一系列的算法来解决此问题.例如，禁忌搜索算法 [ 9 9 ] 、退火回归神经网络极值搜索算法 [ 10 10 ] 和演化算法 [ 11 11 ~ 13 13 11~13 ] 等.其中演化算法 [ 14 14 , 15 15 ] 因具有自适应、自组织、内在并行性、易实现等特点，它的寻优过程仅依赖于问题适应度信息，不需要待解问题连续可微，所以演化算法经常用于求解常规优化算法难于处理的非线性的、约束的问题.纳什均衡问题可被转换为带约束的最优化问题，通过演化算法的自动寻优进行问题求解，这为求解纳什均衡问题开辟了一条新途径. 演化算法中多数算法着重研究求解单个纳什均衡点，若想找出博弈中的全部纳什均衡点则需要运行算法多次.本文提出了一种用于求解多峰优化问题的两阶段多峰优化算法，并将该算法应用于求解纳什均衡问题，旨在通过一次算法的运行，尽可能多的求出纳什均衡点，这有利于在多个纳什均衡点中找出精化解.第一阶段运行的NCDE算法 [ 16 16 ] 是带有邻域变异策略的排挤差分演化算法，实验向量的生成被限制在一定数量的相似个体(个体的相似性通过个体之间的欧氏距离来衡量)之间，这有助于更好的保持种群的多样性.NCDE算法有两个主要优点：其一，它具有很强的全局搜索能力以及良好的保持种群多样性的能力.其二，NCDE是一种隐式小生境技术，在保持种群多样性上对种群的大小要求不高，在极端情况下，甚至每个个体都可以独立保持一个小生境.但是，有利必有失，NCDE这种低选择压力机制无疑会降低它的收敛速度.第二阶段运行的CMA_ES [ 17 17 ] 算法克服了一些传统演化算法相关的典型问题，例如在严重缩放和高度不可分问题上的低性能、对大种群的内在需求以及种群的早熟问题.然而，在其本质上，CMA-ES算法是一种局部搜索算法，它具有很强的局部搜索能力，但在全局搜索能力上相对较弱.我们提出的算法，简称为NBC-CMA，正好弥补了NCDE收敛速度慢及CMA-ES全局搜索能力弱的缺点.NBC-CMA算法和另外6个较新的多峰优化算法进行了比较，在比较实验中我们提出的算法表现出了更优的性能. 问题描述 1 一个包含有限策略的 N 人非合作博弈，可形式化定义为Γ=(( N,S i ,u i ), i =1,…, N ) [ 10 10 , 13 13 ] .其中，N代表参与人的数量；对每个参与人 i ∈{1,…, N }， S i ={ s i 1 , s i 2 ,…, s im }代表参与人 i 有 m 个可用策略； S = S 1 × S 2 ×…× S N 代表博弈中所有可能的策略组合的集合.对每个参与人 i ∈{1,…, N }， u i : S→R 代表支付函数. 令 p ij ( j =1,…, m i )表示参与人 i 选择策略 s ij 的概率，其中 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464914&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464914&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464914&type=middle ，概率分布 p i =( p i 1 , p i 2 ,… ,p im i ) 为参与人i的一个混合策略. P i 代表参与人i的混合策略空间( p i ∈ P i )， p =( p 1 , p 2 ,…, p N )表示所有参与人的一个混合策略组合， P =× i =1,…, N P i 表示混合策略组合空间( p∈P ).令 m = http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464919&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464919&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464919&type=middle ，则 P 与${{\mathbb{R}}^{m}}$是同构的. 在纯策略的情况下，参与人 i 的收益 u i 为纯策略组合 s =( s 1 ,…, s N )的函数，表示为 u i (s) = u i ( s 1 ,… s N ).在混合策略纳什均衡中，参与人关心的是给定的纯策略收益组成的期望收益，参与人 i 的期望支付函数 u i (p) 有定义域${{\mathbb{R}}^{m}}$，可由公式(1)计算得到. http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464856&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464856&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464856&type=middle 其中，实值函数 p i :S i →$\mathbb{R}$足公式(2). http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464861&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464861&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464861&type=middle 定义1 一个混合策略组合 p * =( p 1 * , p 2 * ,…, p N * ) ∈ P 是一个纳什均衡，如果对于所有的 i ∈{1,…, N }满足 u i ( p i , p － i * )≤ u i ( p * ), p i ∈ P i . p － i * 为除i之外的所有其他参与人的混合策略组合 [ 12 12 , 13 13 ] . 寻找一个博弈的纳什均衡问题可被构造为寻找一个实值函数的全部全局最小值问题.这个函数可由 x,z,g 三个子函数构造，三个子函数定义域均为 P . http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464866&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464866&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464866&type=middle http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464871&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464871&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464871&type=middle http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464874&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464874&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464874&type=middle 其中， S ij 表示参与人i采取一个纯策略，即选取策略 s ij 的概率 p ij 为1. v:P →$\mathbb{R}$由公式(6)定义.函数v是连续可微的且对于所有的 p ∈ P 有 v(p) ≥0，一个策略组合 p * 是一个纳什均衡当且仅当 v ( p * )=0. http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464877&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464877&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464877&type=middle 本文的算法 1 NBC-CMS算法在第一阶段充分发挥NCDE算法全局搜索能力强的特点进行粗粒度搜索，尽可能多的定位最优解的大概位置.在NCDE演化一定代数之后，调用 DMC (Detect Multimodal Clustering) [ 18 18 ] 聚类方法，以识别当前种群中形成的聚类.然后，根据识别出的聚类数量，相同数量的CMA-ES实例被生成，每一个CMA-ES实例对应一个不同的聚类.每个聚类的最好搜索点作为CMA-ES的起始搜索点，每个聚类与其最近相邻聚类欧氏距离的六分之一作为CMA-ES的起始搜索步长，每个实例被独立的运行直到终止条件满足.为了充分地利用剩余的评价次数，算法采用了CMA-ES实例重新初始化和档案存储机制.在算法的运行过程中，为了增强演化初期搜索新峰的能力及保持子种群的稳定性，我们提出搜索点补充策略(search point replenishment strategy,SPRS). 搜索点补充策略 2 SPRS的主要思想是在演化初期增加小生境间搜索点的迁移，以增强搜索新峰的能力、平衡子种群的大小以及保持子种群的稳定性.为了减少由于搜索点迁移对原小生境的影响，我们对包含搜索点数量最多的小生境，选择其最相似且更差的搜索点进行迁移，把它迁移到包含搜索点数最少的小生境内，并在该小生境半径内随机均匀地重新初始化该搜索点.随演化的进行，这种搜索点迁移会被逐渐减少，以降低对种群结构的破坏.另外，搜索点迁移后的重新初始化半径也会逐渐收缩，以保证种群收敛.在进行搜索点补充前需要对当前种群进行聚类操作，我们采用Preuss提出的Nearest-Better Clustering (NBC)聚类方法 [ 19 19 ] 进行子种群划分，NBC方法被认为是一个无参数的聚类方法，而且有着优秀的聚类性能.这里之所以没有采用DMC方法进行子种群划分，因为DMC方法依赖于适应度景观上的种群拓扑结构来划分聚类.这种机制会消耗额外的适应度评价次数，不适于被多次调用，但该方法却有更好的聚类性能.SPRS伪代码如算法1所示. 输入：MIN indi , C,R 1. 从聚类集合 C 中分别选择包含最多和最少搜索点数量的聚类 c max 和 c min 2. 如果 c min 中的搜索点数目大于等于MIN indi ，则算法终止 3. 从聚类 c max 中选择一对具有最大相似性(以欧氏距离度量)的搜索点 4. 从被选择的一对搜索点中选择适应度较低的搜索点 p k ，并把它加入到 c min 中 5. 根据公式(7)计算重新初始化半径 r reinit 6. 在半径 r reinit 内均匀随机地初始化搜索点 p k 7. 跳转到step 1 MIN indi 是聚类中允许的最少搜索点数量，它可由种群数量除以聚类数目CN求得.聚类集合 C 和聚类数量CN由NBC方法获得. R 用于计算重新初始化半径 r reinit . http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464879&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464879&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464879&type=middle d n ( c min , C )计算 c min 到离它最近的聚类之间的距离(两个聚类中最好搜索点之间的距离)， c min 代表包含最少搜索点的聚类. R 为收缩因子用于限制重新初始化半径的大小，如果演化代数小于4, R =1，否则 R =iter－3，iter为当前演化代数.这样做的目的是保证在算法运行早期有更大的初始化半径，随着演化代数的增加，初始化半径逐渐缩小. 算法框架 2 在算法的迭代过程中，算法分两个阶段执行.在第一阶段执行NCDE算法进行粗粒度搜索，当满足一定条件时SPRS会被调用.首先，只有当前迭代次数等于阈值 α 时，SPRS才会被调用.这样做可以使得对SPRS的调用随演化的进行逐渐减少.其次，为了进一步限制对SPRS的调用，如果当前消耗的评价次数大于等于总评价次数的1/5时，则不再调用SPRS. 阈值 α 的取值如下，其中 D 为问题维度， http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464881&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464881&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464881&type=middle 下面要解决何时转入第二阶段的问题，首先要明确在转入第二阶段前，并不需要精确定位最优值的位置.只要知道最优值的大概位置即可，所以转换的时机并不需要非常准确.根据这一点，我们引入了一个自适应的启发式参数 θ : http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464886&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464886&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464886&type=middle 当已消耗的评价次数大于等于阈值 θ 时，终止第一阶段并转入第二阶段的准备阶段.公式(9)中的MaxFEs代表允许的最大评价次数.在第二阶段开始前的准备阶段，需要精确的对种群划分聚类，所以此时调用DMC方法进行聚类划分，以期望获得更准确的划分结果.然后和已获得聚类数目相同的CMA-ES实例被生成，每一个CMA-ES实例对应一个聚类并覆盖搜索空间中的一个不同区域.取聚类中的最好搜索点作为CMA-ES实例的起始搜索点，并定义当前实例与它最邻近实例之间欧氏距离的二分之一为覆盖距离，则取覆盖距离的三分之一作为当前实例的起始步长(即用于控制变异强度的标准偏差)，这样做的目的在于希望在CMA-ES随机抽取的搜索点中，有99%的搜索点落在覆盖距离之内，可以从统计上避免邻近CMA-ES实例间覆盖范围的相互重叠.为了充分利用剩余的评价次数，引入了CMA-ES实例重新初始化和档案存储机制.重新初始化机制是指当一个实例被终止并且有剩余的评价次数时，该实例会被重新随机初始化并重新启动它.档案存储机制是指实例在重新初始化之前，存储它已找到的最优解.档案的大小不超过种群的数量，若档案被存满时，则采用替换原则，用优质解替换档案中劣质解.整个算法框架的伪代码如算法2所示. FEs代表目前消耗的评价次数. 1. 初始化种群 2. 执行NBC聚类方法识别聚类，执行SPRS进行搜索点补充 3. converged=false,iter=0, t =2 4. while FEs＜MaxFEs do a) if not converged then i. 如果iter== α and FEs＜MaxFEs/5，则执行NBC聚类算法和SPRS并令 t = t +1 ii.执行NCDE算法 iii.如果FEs≥ θ ，则执行DMC划分聚类并初始化CMA-ES实例，并令converged=true b) else i. 分别执行所有CMA-ES实例 ii. 若条件满足执行档案存储和实例重启 c) iter=iter+1 5. end while 实 验 1 测试问题 2 从软件GAMBIT(ver. 0.2007.12 .4 ) [ 20 20 ] 中选择10个不同难度的博弈问题，每个问题都包含多个纳什均衡.博弈问题描述见 表 1 表 1 所示，在GAMBIT文件中给出了所有参与人的支付矩阵.选定的博弈问题可被转化为4维到12维之间的约束优化问题.这些测试问题的纳什均衡即包含纯策略又包含混合策略.其中 F 6 ， F 7 和 F 10 ，由于它们包含的可用策略总数多，搜索空间大且计算量大，这给求解造成一定困难.求解纳什均衡问题主要有两个难点：一是计算量大，通常情况下计算量随策略总数(问题维度)的增加急剧增长，博弈 F 6 单次函数评价的计算量大约是 F 1 的37.5倍，是 F 10 的1.88倍；二是对解空间的约束给问题的求解造成困难，生成的实验向量经常不在可行解空间内.为了解决这一问题，通常先在解空间进行搜索生成一个实验向量，然后把这个实验向量映射到可行解空间再进行函数评价，很明显这种映射是满射.映射按下式进行， http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464900&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464900&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464900&type=middle 其中, X =( x ij ) i =1,…, N ; j =1,…, m i 代表一个混合策略组合. 性能评价方法 2 本文使用峰比率和找到的纳什均衡数量的平均值进行算法的性能评价，峰比率(peak ratio,PR)按以下式计算， http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464905&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464905&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464905&type=middle NPF i 代表算法第 i 次运行结束后找到的纳什均衡数量，NKP是由 表 1 表 1 所列出的已知纳什均衡数量，PR度量在NR次运行中找到已知纳什均衡数量的平均比例.找到的纳什均衡数量的平均值(Mean)计算公式如下 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464908&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464908&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464908&type=middle 博弈 参与人 数量 策略数量 纳什 均衡 GAMBIT 文件 F 1 2 2×2 3 coord2.nfg F 2 2 3×3 7 coord3.nfg F 3 2 4×4 15 coord4.nfg F 4 3 2×2×2 9 2×2×2.nfg F 5 3 3×3×3 5 3×3×3.nfg F 6 3 5×4×3 3 5×4×3.nfg F 7 3 8×2×2 5 8×2×2.nfg F 8 4 2×2×2×2 3 2×2×2×2.nfg F 9 4 2×2×2×2 5 g3.nfg F 10 5 2×2×2×2×2 5 2×2×2×2×2.nfg 实验设置 2 本实验中所有算法代码均由Visual C++2012编写，操作系统为Windows 7.为了检验NBC-CMA算法的性能，我们选择了6个对等的算法进行比较.大多数算法是最近提出的新算法，它们在和其他算法的比较实验中都表现出了优秀的性能.它们是NEA [ 19 19 ] 、S-CMA [ 21 21 ] 、IPOP-CMA-ES [ 22 22 ] 、NCDE [ 16 16 ] 、LIPS [ 23 23 ] 和FERPSO [ 24 24 ] .其中IPOP-CMA-ES是基于重启机制、时间上串行运行的算法，这里以它作为一个测试基准，来检验所有算法的性能. 求解精度设置为 e =1.0E-8， F 1 的最大评价次数设置为10 000， F 2 设置为20 000， F 6 、 F 7 设置为100 000，其余问题均设置为50 000. 为了保证比较的公平性，所有算法都在不同种群大小下(种群大小从25开始，以步长25递增)被独立执行30次.对于每一个种群大小，所有算法都被独立执行30次，最后计算其PR值及平均找到的纳什均衡数量，然后从所有运行结果中选择最好运行结果作为最终结果参与比较. 我们提出的算法共引入了3个新参数gradations， α 和 θ .NBC-CMA的参数gradations(DMC聚类中插入点的个数)被设置为固定值8. α 和 θ 是两个自适应参数，不需要设置.对于NCDE算法有3个参数，邻域大小 m 被设置为种群大小的1/15，收缩因子 F 设置为0.5，交叉概率 C r 设置为0.9(因为纳什均衡问题属于不可分问题，较大的 C r 值有利于问题的求解).CMA-ES除了stopTolFun和stStopFitness外均使用默认参数值，stopTolFun设置为1.0E-7，stStopFitness设置为要搜索的最优值.当CMA-ES实例找到最优值或陷入停滞时，CMA-ES实例会被终止以节省评价次数.IPOP-CMA-ES算法的种群增长因子设置为1.1，并保证每次重启种群大小至少增加一个个体.对于NEA和S-CMA算法，它们的最大允许小生境数量设置为要搜索的纳什均衡数量.为了保证和其他CMA算法比较的公平性，在原IPOP-CMA-ES和S-CMA算法的基础上为其增加了档案存储机制.其他算法的参数均取其默认值. 实验结果分析 1 图 1 图 1 给出了在精度要求为 e =1.0E-8时，对每个种群大小所有算法都独立运行30次求得PR值的曲线图. 图 1 图 1 的运行结果中，对每个博弈问题计算每种算法在最好种群下找到的纳什均衡点的平均值，其结果如 表 2 表 2 所示.求得的最好结果在表格中用黑体显示，小括号中的数字代表该算法的秩，表格最后一行为算法在所有测试问题上的秩和. F 1 、 F 2 、 F 8 和 F 9 是相对简单的问题，取得全部均衡点相对容易，其中 F 2 由于评价次数设置得少，大部分算法没能每次运行都取得全部均衡点，仅NBC-CMA和NEA能在多数种群规模下每次都取得全部均衡点. F 3 和 F 4 由于包含的纳什均衡点较多，求解维度增加，NBC-CMA、NEA和LIPS算法表现出了优于其他算法的性能. F 5 ， F 6 ， F 7 和 F 10 是较难的问题，尤其 F 6 和 F 7 在所有测试问题中最难求解，不仅问题维数高，而且计算量显著大于其他测试问题.在这4个测试问题上，NBC-CMA在3个问题上是最好的，在 F 7 上劣于LIPS算法，这可能和LIPS算法采用了基于邻域变异的策略有关，领域变异策略具有很好的保持种群多样性的能力，该策略使得算法具有很好的稳定性.在实验结果的总体效果上，NBC-CMA算法最好，LIPS次之.在 F 2 ， F 3 ， F 5 ， F 6 和 F 10 上，NBC-CMA的结果优于所有其他算法.在 F 1 ， F 4 ， F 8 和 F 9 上，NBC-CMA取得了与其他算法相同的结果. 小括号中的数字代表该算法的秩，黑体为求得的最好结果 博弈 FERPSO IPOP-CMA LIPS NBC-CMA NCDE NEA S-CMA F 1 3.00(1) 3.00(1) 3.00(1) 3.00(1) 3.00(1) 3.00(1) 3.00(1) F 2 5.93(7) 6.40(5) 6.97(3) 7.00(1) 6.77(4) 7.00(1) 6.00(6) F 3 7.73(6) 10.00(5) 12.90(3) 14.93(1) 11.40(4) 13.90(2) 4.00(7) F 4 8.20(4) 7.10(6) 9.00(1) 9.00(1) 7.40(5) 9.00(1) 6.63(7) F 5 3.43(6) 3.67(4) 3.90(2) 4.10(1) 2.83(7) 3.77(3) 3.50(5) F 6 1.70(5) 1.73(4) 1.93(3) 2.30(1) 2.13(2) 1.6(6) 0.63(7) F 7 4.47(3) 2.97(6) 5.00(1) 4.80(2) 3.60(5) 4.00(4) 2.00(7) F 8 3.00(1) 3.00(1) 3.00(1) 3.00(1) 3.00(1) 3.00(1) 3.00(1) F 9 5.00(1) 4.27(7) 5.00(1) 5.00(1) 4.50(5) 5.00(1) 4.30(6) F 10 4.00(4) 3.88(5) 4.40(2) 4.50(1) 3.43(7) 4.37(3) 3.73(6) 秩和 38 44 18 11 41 23 53 结 论 1 通过把 N 人非合作博弈的纳什均衡问题转化为带约束的传统优化问题，实现了用多峰优化算法对纳什均衡问题的求解.通过算法的一次运行可求出多个纳什均衡解，这对纳什均衡解的精化提供了方便.实验结果表明我们提出的NBC-CMA多峰优化算法是有效的，尤其在 F 3 ， F 5 ， F 6 和 F 10 这4个较难的博弈问题上表现出了优于其他算法的性能. 将来的研究工作围绕以下两点展开：首先，对NBC-CMA算法进行改进，尝试用其他优秀算法替代NCDE和CMA-ES算法，以期获得更好的性能；其次，把NBC-CMA算法应用于动态环境中的多峰优化问题. 参考文献 NASH J F. Equilibrium points in n -person games[J]. The National Academy of Sciences of the United States of America, 1950, 36 (1): 48-49.DOI:10.1073/pnas.36.1.48. NASH J F. Non-cooperative games[J]. The Annals of Mathematics , 1951, 54 (2): 286-295. LEMKE C E, HOWSON J J T. Equilibrium points of bimatrix games[J]. Journal of the Society for Industrial & Applied Mathematics , 1964, 12 (2): 413-423. van Der LAAN G, TALMAN A J J, van HEIJDEN L. Simplicial variable dimension algorithms for solving the nonlinear complementarity problem on a product of unit simplices using a general labelling[J]. Mathematics of Operations Research , 1987, 12 (3): 377-397. GOVINDAN S, WILSON R. A global newton method to compute Nash equilibria[J]. Journal of Economic Theory , 2003, 110 (1): 65-86. HERINGS P J, PEETERS R J. A differentiable homotopy to compute Nash equilibria of n -person games[J]. Economic Theory , 2001, 18 (1): 159-185. GOVINDAN S, WILSON R. Computing Nash equilibria by iterated polymatrix approximation[J]. Journal of Economic Dynamics and Control , 2004, 28 (7): 1229-1241. SUREKA A, WURMAN P R. Using Tabu best-response search to find pure strategy Nash equilibria in normal form games[C]// Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multiagent Systems . New York: ACM, 2005. 1023-1029. 查旭，左斌，胡云安. 利用退火回归神经网络极值搜索算法求纳什均衡解[J]. 控制与决策, 2006, 21 (10): 1167-1171. ZHA X, ZUO B, HU Y A. Nash equilibrium solution by extremum seeking algorithm based on annealing recurrent neural network[J]. Control and Decision, 2006, 21 (10): 1167-1171(Ch). LUNG R, DUMITRESCU D. An evolutionary model for solving multi-player non-cooperative games . . http://www.cs.ubbcluj.ro/~studia-i/2007-kept/314-LungDumitrescu.pdf http://www.cs.ubbcluj.ro/~studia-i/2007-kept/314-LungDumitrescu.pdf . PAVLIDIS N G, PARSOPOULOS K E, VRAHATIS M N. Computing Nash equilibria through computational intelligence methods[J]. Journal of Computational and Applied Mathematics , 2005, 175 (1): 113-136. 余谦，王先甲. 基于粒子群优化求解纳什均衡的演化算法[J]. 武汉大学学报(理学版), 2006, 52 (1): 25-29. YU Q, WANG X J. Evolution algorithm for solving Nash Equilibrium based on particle swarm optimization [J]. J Wuhan Univ ( Nat Sci Ed ), 2006, 52 (1): 25-29. 伍文，孟相如，康巧燕，等. 粒子群算法求解混合战略近似纳什均衡[J]. 计算机应用研究, 2014, 31 (8): 2299-2302. WU W, MENG X R, KANG Q Y, et al . New PSO based algorithm for finding mixed strategy approximate Nash equilibrium[J]. Application Research of Computers, 2014, 31 (8): 2299-2302. GUO Z, YUE X, ZHANG K, et al . Enhanced social emotional optimisation algorithm with generalised opposition-based learning[J]. International Journal of Computing Science and Mathematics , 2015, 6 (1): 59-68. GUO Z, YUE X, WANG S, et al . Self-adaptive differential evolution with elite opposition-based learning[J]. ICIC Express Letters , 2016, 10 (2): 405-410. QU B Y, SUGANTHAN P N, LIANG J J. Differential evolution with neighborhood mutation for multimodal optimization[J]. IEEE Transactions on Evolutionary Computation , 2012, 16 (5): 601-614. HANSEN N, OSTERMEIER A. Completely derandomized self-adaptation in evolution strategies[J]. Evolutionary Computation, 2001, 9 (2): 159-195. STOEAN C, PREUSS M, STOEAN R, et al . Multimodal optimization by means of a topological species conservation algorithm[J]. IEEE Transactions on Evolutionary Computation , 2010, 14 (6): 842-864. PREUSS M. Niching the CMA-ES via nearest-better clustering[C]// Proceedings of the 12th Annual Conference Companion on Genetic and Evolutionary Computation .New York: ACM, 2010: 1711-1718. MCKELVEY R D, MCLENNAN A M, TUROCY T L. Gambit: Software tools for game theory . http://sourceforge.net/projects/gambit/files/gambit-stable/0.2007:12.04/ http://sourceforge.net/projects/gambit/files/gambit-stable/0.2007:12.04/ . SHIR O M, EMMERICH M, BACK T. Adaptive niche radii and niche shapes approaches for niching with the CMA-ES[J]. Evolutionary Computation , 2010, 18 (1): 97-126. AUGER A, HANSEN N. A restart CMA evolution strategy with increasing population size . . http://ieeexplore.ieee.org/xpls/icp.jsparnumber=1554902 http://ieeexplore.ieee.org/xpls/icp.jsparnumber=1554902 . QU B Y, SUGANTHAN P N, DAS S. Adistance-based locally informed particle swarm model for multimodal optimization[J]. IEEE Transactions on Evolutionary Computation , 2013, 17 (3): 387-402. LI X D. Amultimodal particle swarm optimizer based on fitness Euclidean-distance ratio[C]// Proc of the 9th Annual Conference on Genetic and Evolutionary Computation . New York: ACM, 2007: 78-85. 10.14188/j.1671-8836.2016.05.007 TP 311 whdxxblxb-62-5-444 国家自然科学基金(61364025,61402481); 江西省自然科学基金(20151BAB217010); 河北省自然科学基金(F2015403046); 武汉大学软件工程国家重点实验室开放基金(SKLSE2014-10-04)资助项目 2015-09-07 2020-12-10 版权所有 © 《武汉大学学报(理学版)》编辑部 Copyright © 2016 Journal of Wuhan University (Natural Science Edition). All rights reserved. 2016 武汉大学学报(理学版) 5 62