多重纳什均衡解的粒子群优化算法

《多重纳什均衡解的粒子群优化算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第19卷第2期2010年4月运筹与管理OPERATIONSRESEARCHANDMANAGEMENTSCIENCEV01．19，No．2Apr．2010多重纳什均衡解的粒子群优化算法瞿勇，张建军，宋业新(海军工程大学理学院。湖北武汉430033)摘要：提出了一种求解双矩阵对策多重纳什均衡解的粒子群优化算法。该算法通过随机初始点以及迭代粒子的归一化，保证粒子群始终保持在对策的可行策略空间内，避免了在随机搜索中产生无效的粒子，提高了粒子群优化算法求解纳什均衡解的计算性能。最后给出了几个数值例子，说明了粒子群优化算法的高效性。关键词：粒子群优化算

2、法；双矩阵对策；纳什均衡解；策略空间中图分类号：0225文章标识码：A文章编号：1007—3221(2010)02—0052-04ParticleSwarmOptimizationAlgorithmforSolvingMultipleNashEquilibriumSolutionsQUYong，ZHANGJian-jun，SONGYe-xin(CollegeofScience，NavalUniversityofEngineering，Wuhan430033，China)Abstract：AParticleSwarmOptimization(

3、PSO)algorithmforsolvingmultipleNashequilibriumsolutionsofbimatrixgameispresentedinthispaper．BynormalizingrandominitialparticlesanditerativeparticlesintheproposedPSOalgorithm，particlesarealwaysinthefeasiblestrategyspacethatavoidsproducingineffectiveparti-tiesintherandomsear

4、chprocedure，SOthatthecomputationperformanceofthePSOalgorithmforsolvingtheNashequilibriumsolutionsisimproved．Finally，somenumericalexamplesaregiventoillustratetheproposedal·gorithm．Keywords：PSOalgorithm；bimatrixgames；Nashequilibriumsolution；strategyspace在对策论中，一般的双矩阵对策的求解是通过L

5、emke．Howson算法⋯求解的，但是3阶以上的双矩阵对策用此方法求解比较困难，过程比较麻烦，尤其是当矩阵的阶数很大时，人工几乎不能求解．文献[2]给出了用Lingo软件求解双矩阵对策的平衡解的方法和程序，对于具有多重均衡解的情形，也需要对某个变量分区间段讨论分别求解，但当矩阵的阶数较大时，就需要对多个变量分区间段讨论求解，比较繁琐．对此，本文基于粒子群优化(ParticleSwarmOptimization，简称PSO)¨”1给出了一种新的针对双矩阵对策的求解算法。本文设计的粒子群优化算法，通过构造合适的适应度函数，只要求得适应度为0的

6、解，即为纳什均衡解，很好地解决了多重纳什均衡解的求解问题．1双矩阵对策的纳什均衡解双矩阵对策可以由两个m×n矩阵表示收稿13期：2009．02．28基金项目：国家自然科学基金项目(60774029，70471031)。海军工程大学自然科学基金项目(HGDJJ07007)。作者简介：瞿勇(1968一)，男，武汉人，讲师，硕士．研究方向：对策理论．系统优化与决策及进化算法；张建军(1966一)。男．副教授，博士，研究方向：高性能计算，网络安全；宋业新(1968一)．男．教授。博士，研究方向：不确定系统建模。优化与决策，对策理论。第2期瞿勇，等：

7、多重纳什均衡解的粒子群优化算法53厂口lI⋯口l。．}r6ll⋯61。1A：I!‘．；l，召：I；。．；l(1)l口。。⋯口。。j【b。。⋯b。。j其中局中人I有m个纯策略S。={理。，⋯，a。}，局中人II有n个纯策略S，={卢。，⋯，J8。}．即当局中人I选择一个纯策略a；∈S。，局中人1／选择一个纯策略岛∈S：时，局中人I得到支付口Ⅱ，局中人II得到支付6玎。记x={菇∈R“I∑石；=1，z。≥o，i=1，⋯，m}，Y={，，ER4l∑乃=1，乃≥0，_『=1，⋯，n}，则当局中人I选择一个混合策略石∈x和局中人Ⅱ选择一个混合策略YE

8、Y时(记为一对策略(茗，Y))，局中人I的支付以期望支付E。(舅，Y)=xAy7表示；局中人lI的支付以期望支付E：(髫，Y)=xBy7表示，通常用r=(x，Y，A，B)表示二人