基于自适应邻域模拟退火算法的非合作对策求解

摘要/Abstract

摘要：

对有多个Nash平衡点的非合作n人有限对策问题进行了研究。首先构造了其非合作n人有限对策的数学规划模型,证明了此模型的解与对策问题的解的等价性; 然后提出了求解此类问题的一种自适应邻域模拟退火算法,基于此算法,在不减少问题解的条件下,解决了多解的非合作n人对策问题。通过数值实验说明了此算法的收敛性及稳定性; 通过与粒子群算法、免疫粒子群算法、传统模拟退火算法的比较,说明了本文算法的优越性。

关键词: 非合作n人有限对策, 模拟退火算法, 自适应邻域, 连续变量, 全局优化, 多解问题

Abstract:

We study the problem of npersons’ noncooperative finite game with multiple Nash equilibrium points. Firstly, we construct a mathematical programming model and prove that the solution to this model is equal to that of the npersons’ noncooperative finite game. We also propose a simulated annealing algorithm with selfadaption neighborhood for such problems. Based on this algorithm, we solve the multisolution problem without reducing the number of solutions. Numerical experiments show that the proposed algorithm is convergent and stable, and it outperforms the particle swarm algorithm, the immune particle swarm algorithm and the traditional simulated annealing algorithm.

Key words: npersons noncooperative finite game, simulated annealing algorithm, selfadaption neighbourhood, continuous variable, global optimization, multisolution problem

朱康宁，谢政，戴丽. 基于自适应邻域模拟退火算法的非合作对策求解[J]. 计算机工程与科学.

ZHU Kangning,XIE Zheng,DAI Li.

Solving noncooperative game based on simulated

annealing algorithm with selfadaption neighborhood

[J]. Computer Engineering & Science.

参考文献［20］

［1］	Xie Zheng.Introduction to game theory［M］.Beijing:Science Press,2010:168189．(in Chinese)
［2］	Nash J F.Equilibrium points in nperson games［J］.Proceedings of National Academy of Sciences of the USA,1950,36（1）:4849．
［3］	Conitzer V, Sandholm T. Complexity results about Nash equilibria［C］∥Proc of IJCAI’03,2003:765771．
［4］	Daskalakis C, Goldberg P W, Papadimitriou C H. The complexity of computing a Nash equilibrium［J］.SIAM Journal on Computing,2009,39(1):195259．
［5］	Lemke C E. Bimatrix equilibrium points and mathematical programming［J］.Management Science,1965,11:681689．
［6］	Dreves A, Heusinger A V, Kanzow C, et al.A globalized Newton method for the computation of normalized Nash equilibria［J］.Journal of Global Optimization,2013,56（2）:327340．
［7］	Govindan S,Wilson R.A global Newton method to compute Nash equilibria［J］.Journal of Economic Theory,2003,110（1）:6586．
［8］	Yuan Y X.A trust region algorithm for Nash equilibria problems［J］.Pacific Journal of Optimization,2011,7（1）:125138．
［9］	Bi Peipei.Selfadaptive projection method with BB stepsize for solving generalized Nash equilibrium problem［D］.Nanjing:Nanjing Normal University,2013．(in Chinese)
［10］	Pearson M,La Mura P.Simulated annealing of game equilibria:A simple adaptive procedure leading to Nash equilibrium［C］∥Proc of the International Workshop on the Logic and Strategy of Distributed Agents,2000:1419．
［11］	Lung R I, Dumitrescu D. Computing Nash equilibria by means of evolutionary computation［J］.International Journal of Computers,Communications & Control,2008,3(3):364368．
［12］	Chen Shijun,Sun Yongguang,Wu Zongxin.A genetic algorithm to acquire the Nash equilibrium［J］.Systems Engineering,2001，19（5）:6770．(in Chinese)
［13］	Shi Sihong,Luo Maokang,Li Shilun.Applications of genetic differentiation algorithm in solving many person noncooperative game’s Nash equilibrium［J］.Journal of Sichuan University（Nature Science Edition）,2010,47（3）:415419．(in Chinese)
［14］	Yu Qian,Wang Xianjia.Evolutionary algorithm for solving Nash equilibrium based on particle swarm optimization［J］.Journal of Wuhan University,2006，52（1）:2529．(in Chinese)
［15］	Qu Yong,Zhang Jianjun,Song Yexin.Particle swarm optimization for solving multiple Nash equilibrium solutions［J］.Operations Research and Management Science,2010,19（2）:5255．(in Chinese)
［16］	Wu Wen, Meng Xiangru, Tang Qiaoyan, et al.New PSO based algorithm for finding mixed strategy approximate Nash equilibrium［J］.Application Research of Computers,2014,31（8）:22992302．(in Chinese)
［17］	Qu Yong,Luan Bing,Song Yaxin.Solution of mixed fuzzy bimatrix games based on particle swarm optimization［J］.Computer & Digital Engineering,2010,38（11）:1316．(in Chinese)
［18］	Jia Wensheng,Xiang Shuwen,Yang Jianfeng,et al.Solving Nash equilibrium for Npersons’ noncooperative game based on immune particle swarm algorithm［J］.Application Research of Computers,2012,29（1）:2831．(in Chinese)
［19］	Jia Wensheng, Xiang Shuwen, Yang Jianfeng. Solving multiple Nash equilibria based on adaptive niched swarm algorithm［J］.Computer Applications and Software,2015,32（1）:247250．(in Chinese)
［20］	Hu Shanying,Chen Bingzhen,He Xiaorong.A simulated annealing method for global optimization to the continuous variable problems［J］.Systems Engineeringtheory & Practice,1995，15(9):7380．(in Chinese)
	附中文参考文献：
［1］	谢政.对策论导论［M］.北京：科学出版社,2010:168189．
［9］	毕培培.带BB步长的自适应投影法解广义纳什均衡问题［D］.南京:南京师范大学,2013．
［12］	陈士俊,孙永广,吴宗鑫.一种求解Nash均衡解的遗传算法［J］.系统工程,2001，19（5）:6770．
［13］	史思红,罗懋康,李世伦.种群分化遗传算法在求解多人非合作对策Nash均衡解中的应用［J］.四川大学学报（自然科学版）,2010,47（3）:415419．
［14］	余谦,王先甲.基于粒子群优化求解纳什均衡解的演化算法［J］.武汉大学学报,2006，52（1）:2529．
［15］	瞿勇,张建军,宋业新.多重Nash均衡解的粒子群优化算法［J］.运筹与管理,2010,19（2）:5255．
［16］	伍文,孟相如,唐巧燕,等.粒子群算法求解混合战略近似纳什均衡［J］.计算机应用研究,2014,31（8）:22992302．
［17］	瞿勇,栾兵,宋亚新.基于粒子群优化的混合模糊双矩阵对策求解［J］.计算机与数字工程,2010,38（11）:1816．
［18］	贾文生,向淑文,杨剑锋,等.基于免疫粒子群算法的非合作博弈Nash均衡问题求解［J］.计算机应用研究,2012,29（1）:2831．
［19］	贾文生,向淑文,杨剑锋.基于自适应小生境粒子群算法的多重Nash均衡求解［J］.计算机应用与软件,2015,32（1）:247250．
［20］	胡山鹰,陈丙珍,何小荣.连续变量问题全局优化的模拟退火算法［J］.系统工程理论与实践,1995，15(9):7380．

[1]	赵炳巍, 贾峰, 曹岩, 孙瑜, 刘一鸿. 基于模拟退火算法的人工势场法路径规划研究[J]. 计算机工程与科学, 2022, 44(04): 746-752.
[2]	袁也, 王刚, 刘晓光, 李雨森. 新型电路版图布局布线算法设计[J]. 计算机工程与科学, 2021, 43(07): 1185-1191.
[3]	马晗，常安定，陈童，李江杰. 基于文化混合优化算法的旅行商问题求解[J]. 计算机工程与科学, 2019, 41(07): 1273-1278.
[4]	黄洪涛1，武继刚1，郑露露1，缪裕青2. 面向无线内容分发网络的树形拓扑生成算法[J]. 计算机工程与科学, 2018, 40(12): 2133-2140.
[5]	吉慧，周磊. 面向温度优化的片上网络任务调度方法[J]. 计算机工程与科学, 2018, 40(09): 1527-1533.
[6]	南敬昌，胡婷婷，盛爽爽，高明明. Doherty功放的贝叶斯正则化神经网络逆向建模研究[J]. 计算机工程与科学, 2018, 40(08): 1496-1502.
[7]	邓见凯1,2，王磊1,2，尹爱华3. 一种求解二维矩形Packing问题的拟人型全局优化算法[J]. 计算机工程与科学, 2018, 40(02): 331-340.
[8]	杨宏宇,赵明瑞,谢丽霞. 基于自适应进化神经网络算法的入侵检测[J]. J4, 2014, 36(08): 1469-1475.
[9]	潘章明，唐川. 搜索空间边界连接的微粒群优化算法[J]. J4, 2012, 34(7): 154-159.
[10]	张聚梅1,王洪伦2. 基于遗传算法和模拟退火算法的B样条曲线拟合[J]. J4, 2011, 33(3): 191-193.
[11]	王旭阳,白增亮,李永民,彭堃墀. 全光纤分离调制连续变量量子密钥分发[J]. J4, 2011, 33(10): 57-59.
[12]	曹〓炬,殷〓哲. 云搜索优化算法[J]. J4, 2011, 33(10): 120-125.
[13]	刘彦秀，姜华，潘全科. 基于全局和声搜索的模拟退火算法改进[J]. J4, 2010, 32(11): 82-84.
[14]	许智宏宋勃董建波. 用蚂蚁算法和模拟退火算法解大规模TSP问题的研究[J]. J4, 2008, 30(10): 43-44.
[15]	夏桂梅曾建潮. 一种基于轮盘赌选择遗传算法的随机微粒群算法[J]. J4, 2007, 29(6): 51-54.