收稿日期
: 2013-08-28;
修回日期
: 2013-10-28
基金项目
:
国家自然科学基金资助项目
( 61003252,61201209)
作者简介
:
伍文
( 1985-) ,
女
,
陕西西安人
,
博士
,
主要研究方向为网络可生存性
( w. w. 850608@ 163. com) ;
孟相如
( 1963-) ,
男
,
教授
,
博士
(
后
) ,
主要研究方向为宽带网络通信技术
;
康巧燕
( 1978-) ,
女
,
副教授
,
博士
,
主要研究方向为组播拥塞控制
;
李巧丽
( 1983-) ,
女
,
硕士
,
主要研究方向为
计算智能
.
粒子群算法求解混合战略近似纳什均衡
*
伍 文
1,2
,
孟相如
1
,
康巧燕
1
,
李巧丽
3
( 1.
空军工程大学 信息与导航学院
,
西安
710077; 2. 93868
部队
,
银川
750025; 3. 94326
部队
,
济南
250023)
摘 要
:
为了有效降低纳什均衡求解的复杂度并提高其计算效率
,
提出了一种粒子群算法近似求解混合战略纳
什均衡的新方法
。
在介绍混合战略纳什均衡理论的基础上
,
提出了混合战略纳什均衡定义的计算形式
,
并据此
提出了混合战略近似纳什均衡的概念
,
给出了粒子群算法求解混合战略近似纳什均衡的方法步骤
。
通过仿真验
证了近似纳什均衡理论及粒子群求解过程的正确性
,
与原粒子群算法进行比较
,
得到新粒子群算法时效性更强
的结论
。
关键词
:
博弈论
;
近似纳什均衡
;
粒子群算法
;
混合战略
中图分类号
: O225
文献标志码
: A
文章编号
: 1001-3695( 2014) 08 -2299-04
doi: 10. 3969 /j. issn. 1001-3695. 2014. 08. 013
New PSO based algorithm for finding mixed strategy
approximate Nash equilibrium
WU Wen
1,2
,MENG Xiang-ru
1
,KANG Qiao-yan
1
,LI Qiao-li
3
( 1. School of Information & Navigation,Air Force Engineering University,Xi’an 710077,China; 2. Unit 93868,Yinchuan 750025,China ;
3. Unit 94326,Jinan 250023,China)
Abstract: This paper proposed a new method for solving mixed strategy pseud Nash equilibrium using particle swarm algo-
rithm to reduce the complexity and consuming time of the solving process. After it introduc e d the mixed strategy Nash equilib-
rium theory
,and gave the calculatio nal form of mixed strategy Nash equilibrium and the concept of mixed strategy approximate
Nash equi li brium. It gave the procedures for solving mixed strategy approximate Nash equilibrium by particle swarm algorithm.
The simulation results show that approximate Nash equilibrium theory and the process of particle swarm algorithm are correct.
Also the new particle swarm algorithm is more effectiv e compared to former particle swarm algorithm.
Key words: game theory; approximate Nash equilibrium; particle swarm algorithm; mixed strategy
纳什均衡理论作为博弈论的核心概念
,
被广泛应用于经
济
、
政治
、
军事
、
计算机科学等领域的最优策略选取中
[1 ~ 3]
。
但
纳什均衡的求解一直以来都是一个难点问题
,
采用反应函数方
法求解纳什均衡只能求解简单的
2
人或
3
人博弈
[4]
;
现有的
Lemke-Howson
算法
[5]
、
全局牛顿算法
[6]
、
同伦算法
[7]
等求解算
法计算过程复杂
、
难于实现
;
随着智能算法的发展
,
将纳什均衡
转换为最优化问题
,
依赖智能算法寻优
,
成为求解纳什均衡的
新途径
[8]
。
粒子群算法作为一种新兴的群体智能算法
,
计算简单
、
易
于实现
。
文献
[9]
提出了基于粒子群优化的纳什均衡求解方
法
;
文献
[10]
提出了一种基于粒子群优化求解纳什均衡的演
化算法
,
给出了算法的迭代步骤
,
并确保每次迭代参与人的混
合策略在其策略空间内
;
文献
[11]
提出了基于量子行为粒子
群优化的纳什均衡求解方法
,
对基本粒子群算法进行了改进
,
提高了算法的全局收敛能力
。
以上三篇文章算法的适应度函
数均采用
Liapunov
函数
;
文献
[12]
采用定点迭代算法将纳什
均衡求解问题分解为一系列相关的最优化问题
,
并采用共同进
化粒子群算法求解
;
文献
[13]
将粒子群算法应用于求解电力
系统博弈纳什均衡中
,
未明确给出统一的适应度函数
。
本文首先提出了近似纳什均衡概念
,
降低混合战略纳什均
衡均衡条件
,
得到解空间内可满足实际工程应用的近似纳什均
衡值
,
实现策略的
“
适度最优
”
选择
。
采用粒子群算法求解该近
似纳什均衡
,
其中适应度函数是依据近似纳什均衡概念给出的
。
1
理论背景
1. 1
混合战略纳什均衡
[14]
一个有限
n
人非合作博弈中
,
假设参与人
i
有
K
i
个纯战
略
,
表示为集合
S
i
= { s
i1
,…,s
iK
i
} ,
σ
ik
( k = 1,…,K
i
)
表示参与人
i
选择
s
ik
的概率
,
其中
,0
≤σ
ik
≤
1,
∑
K
i
k
= 1
σ
ik
= 1,
则概率分布 σ
i
=
(
σ
i1
,…,
σ
iK
i
)
为参与人
i
的一个混合战略
。
∑
i
表示参与人
i
的混合战略空间
(
σ
i
∈Σ
i
) ,
σ
= (
σ
1
,…,
σ
n
)
表示混合战略组
合
,
Σ
= ×
i
Σ
i
表示混合战略组合空间
(
σ∈Σ
) 。
在纯战略情况下
,
参与人
i
的收益
u
i
为纯战略组合
s =
( s
1
,…,s
n
)
的函数
,
表示为
u
i
= u
i
( s
1
,…,s
n
) 。
在混合战略纳
什均衡中
,
参与人关心的是给定的纯战略收益组成的期望收
益
,
参与人
i
的期望效用函数 υ
i
(
σ
i
,
σ
- i
)
可由式
( 1)
计算得到
。
υ
i
(
σ
i
,
σ
- i
) =
∑
s
∈
S
(
∏
n
j = 1
σ
j
( s
j
) ) u
i
( s) ( 1)
第
31
卷第
8
期
2014
年
8
月
计算机应用研究
Application Research of Computers
Vol. 31 No. 8
Aug. 2014