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

Two-Stage Multimodal Optimization Algorithm for Solving Nash Equilibrium

提出了一种两阶段多峰优化算法用于求解一个博弈中的全部纳什均衡.第一阶段首先运行带有邻域变异策略的NCDE算法进行粗粒度搜索,定位最优解的粗略位置.第二阶段运行多个CMA-ES实例在已找的位置上同时进行局部精细搜索.此外,提出了一种搜索点补充策略,用于增强演化初期的搜索能力及保持子种群的稳定性.提出的算法和6个经典算法在10个纳什均衡问题上进行了比较.实验结果表明提出的算法在5个问题上取得了最好结果,4个问题上取得的结果与其他算法相同.

This paper proposed a two-stage multimodal optimization algorithm for solving all Nash Equilibrium of agame.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.