基于蜉蝣算法的非合作博弈Nash均衡求解

Solving Nash Equilibrium for N-Persons’Non-Cooperative Game Based on Mayfly Algorithm

鉴于凸优化问题算法在非合作博弈Nash均衡的求解中具有一定的局限性,N人非合作博弈Nash均衡求解是NP问题,提出一种N人非合作博弈Nash均衡求解问题的改进仿生算法-蜉蝣算法(MA)。算法中蜉蝣通过个体最优位置及全体最优位置调整位置来搜索最优解,同时引入高斯变异算子提高算法搜素能力。根据Nash均衡的解空间为单纯形的特性,采用固定初始化点和随机初始化点相结合的方式,提高搜索速度且结果不局限于纯策略。实验表明,蜉蝣算法求解Nash均衡效果优于烟花算法、免疫粒子群算法,特别地,对于高维博弈问题也有很好的效果。

In view of the limitation of convex optimization algorithm in solving the Nash equilibrium of non-cooperative game,the Nash equilibrium of n-person non-cooperative game is NP problem,an improved bionic algorithm for solving the Nash equilibrium of N-person non-cooperative game,Mayfly algorithm(MA),is proposed.In this algorithm,Mayfly searches the optimal solution by adjusting the position of individual optimal position and all optimal position,and introduces Gaussian mutation operator to improve the search ability of the algorithm.According to the characteristics that the solution space of Nash equilibrium is simplex,the fixed initialization point and random initialization point are combined to improve the search speed and the results are not limited to pure strategy.Experiments show that mayfly algorithm is better than fireworks algorithm and immune particle swarm algorithm in solving Nash equilibrium,especially for high dimensional game problems.