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

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

作　　者：张国强[1,2] 赵国党 ZHANG Guoqiang;ZHAO Guodang(College of Management and Economics,Tianjin University,Tianjin 300072,China;School of Business,Xuchang University,Xuchang 461000,China)

机构地区：[1]天津大学管理与经济学部,天津300072 [2]许昌学院商学院,河南许昌461000

出　　处：《运筹与管理》2023年第3期36-42,共7页Operations Research and Management Science

基　　金：国家社会科学基金资助项目(19BJY046)。

摘　　要：博弈分析的目的就是根据博弈规则预测博弈的均衡结果。基于相对占优策略概念的挖掘,改进了一种求解非线性连续博弈的纳什均衡问题(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

关 键 词：纳什均衡 广义纳什均衡 Nikaido-Isoda函数 微分进化算法 

分 类 号：O225[理学—运筹学与控制论]