一种改进的微分进化算法求解纳什均衡问题与广义纳什均衡问题

An Improved Differential Evolution Algorithm for Solving Nash EquilibriumProblem and Generalized Nash Equilibrium Problem

博弈分析的目的就是根据博弈规则预测博弈的均衡结果。基于相对占优策略概念的挖掘,改进了一种求解非线性连续博弈的纳什均衡问题(NEP)和广义纳什均衡问题(GNEP)的微分进化算法。该算法操作简单、易于实现,光谱性强,算法复杂度低、精确度高。通过随机选取三个不同位置的父代个体进行变异和交叉操作产生新个体,再根据相对占优策略实现优胜劣汰,既保持了种群多样性,又增强了算法的全局寻优能力。实验表明,该算法可以解决含有一个全局最优解的纳什均衡问题和广义纳什均衡问题,可以处理多维,非凸性等复杂的目标函数,具有一定的广泛适用性。对于NEP,对比当前最先进的算法,该算法只需较少的迭代次数和运行时间;对于GNEP,该算法可以随机选取初始点,不仅可以求得均衡解,效率也优于其它算法,具有高效性。

The purpose of game analysis is to predict the equilibrium result of the game according to the game rules,that is,Nash equilibrium.Nash equilibrium is the most basic and important equilibrium concept in the non-cooperative game model.Although some theorems have explained the existence of Nash equilibrium(including mixed strategy Nash equilibrium),the solution of Nash equilibrium is an NP-hard problem.The existing methods have strict restrictions on constraint conditions and objective functions.When the payoff function of the game player is non-concave,multimodal,or highly nonlinear,it is difficult to solve Nash equilibrium,which limits the general application of game theory.Therefore,it has become an urgent problem to develop a general and efficient algorithm for solving Nash equilibrium.Based on the mining of the concept of relatively dominant strategy,this paper improves a differential evolution algorithm for solving the traditional Nash equilibrium problem(NEP)and the generalized Nash equilibrium problem(GNEP)of nonlinear continuous games.The algorithm has three advantages:(1)simple operation and easy implementation.Only three parameters need to be assigned(population size,crossover probability and variation factor),and there is no need to set multiple parameters.(2)Wide spectrum.As we all know,it is much easier to solve a classical NEP than to solve a GNEP.The algorithm in this paper has no strict restrictions on the payment function,and can be solved without any changes to the algorithm.(3)The algorithm has low complexity and high accuracy.In the process of evolution,there is no need to traverse the entire population to find the best individual.The excellent individual can be retained by comparing two pairs,which not only maintains the diversity of the population,but also enhances the global optimization ability of the algorithm.In this paper,four NEP and GNEP in the existing literature are selected,no matter simple or complex objective functions.The experimental results show that:(1)The algorithm can solve NEP or GNEP with a global optimal solution,and can deal with multidimensional,non-convex and other complex objective functions,and has certain wide applicability.(2)For NEP,compared with the state-of-the-art algorithm(NDEMO),this algorithm only needs less iterations and running time to obtain Nash equilibrium,and its efficiency is about twice that of NDEMO.(3)For GNEP,the algorithm can randomly select the initial point,not only can obtain the equilibrium solution,but also has better efficiency than other algorithms.The main objective of this paper is to solve the equilibrium problem of complex objective functions such as nonlinear demand function and cost function in the non-cooperative continuous game model.A general algorithm for solving NEP or GNEP with a global optimal solution is given,which extends the classical non-cooperative game model,widens the application scope of Nash equilibrium in the real economy,and provides powerful research tools and new research objects.However,when the model contains multiple global solutions,the convergence conditions of the algorithm cannot be met,resulting in the solution failure.This is also the problem that this paper will study in the next step.