11---曹黎侠

Size: px

Start display at page:

Download "11---曹黎侠"

句昌
7 years ago
Views:

1 ISSN CODEN JKYTA8 Journal of Frontiers of Computer Science and Technology 67-98/6/() doi:.778/j.issn Tel: *,+ 曹黎侠, 黄光球. 西安建筑科技大学管理学院, 西安 755. 西安工业大学理学院, 西安 7 Rough Game Model and Algorithm Design Based on Particle Swarm Optimization CAO Lixia,+, HUANG Guangqiu. College of Management, Xi an University of Architecture and Technology, Xi an 755, China. College of Science, Xi an Technological University, Xi an 7, China + Corresponding author: caolx_8@6.com CAO Lixia, HUANG Guangqiu. Rough game model and algorithm design based on particle swarm optimization. Journal of Frontiers of Computer Science and Technology, 6, (): Abstract: There is at least one mixed strategy Nash equilibrium in continuous game, but there are little related research results in existing literature about infinite mixed strategy Nash equilibrium and uncertainty game problem. The uncertainty game refers to the game equilibrium problem that the players strategy set or benefit function are uncertainty. This paper creates an approximation algorithm of infinitely mixed strategy Nash equilibrium, using the advantages of particle swarm optimization, fewer parameters, simple coding and not strictly required to objective function. This paper also proposes the concept of rough game theory, and gives a method converting rough game to a classic game theory based on rough set and vague set theory. This paper provides a theoretical basis for game problem when the strategy sets and benefit function problem are fuzzy. The examples show that the approximation algorithm of infinite mixed strategy Nash equilibrium based on improved particle swarm algorithm and rough game theory solution are feasible and effective. Key words: rough set; particle swarm optimization; mixed strategy Nash equilibrium; Vague set * The Natural Science Basic Research Program of Shaanxi Province under Grant No. 5JZ ( 陕西省自然科学基础研究计划 ); the Social Science Foundation of Shaanxi Province under Grant No. P7 ( 陕西省社会科学基金 ); the Science & Technology Association Decision-Making Advisory Issue of Xi an under Grant No. 57 ( 西安市科协决策咨询课题 ); the Fund Project of Xi an Technological University under Grant No. XAGDXJJ ( 西安工业大学校长基金项目 ). Received 5-7, Accepted 5-. CNKI 网络优先出版 : 5--,

2 566 Journal of Frontiers of Computer Science and Technology 计算机科学与探索 6, () 连续博弈中至少存在一个混合策略 Nash 均衡, 但是关于无限策略混合策略 Nash 均衡的解法, 以及局中人的策略集或是效益函数是不确定性博弈均衡问题, 国内外相关的研究成果还比较少运用粒子群算法对目标函数没有严格要求, 参数较少, 编码简单的优势, 创立了一种计算无限策略混合策略的近似算法 ; 并在此基础上提出了粗糙博弈论的概念, 以粗糙集和 Vague 集的理论为基础, 发现了一种粗糙博弈论转化为经典博弈论的方法无限策略混合策略 Nash 均衡的近似算法和粗糙博弈论的研究为策略集和效益函数不确定时的博弈问题提供了理论依据算法示例结果表明, 基于改进的粒子群算法的无限策略混合策略 Nash 均衡近似算法和粗糙博弈论的解法是有效可行的粗糙集 ; 粒子群算法 ; 混合策略纳什均衡 ;Vague 集 A O5 经典博弈论只解释了纳什均衡的含义, 但没有给出计算纳什均衡的通用计算方法 [-] 作为博弈论应用的关键, 许多学者研究了纳什均衡的计算方法及其计算复杂度 [5-8] 这些研究成果主要解决的是有限策略的混合策略纳什均衡和无限策略的纯策略纳什均衡, 而无限策略的混合策略纳什均衡研究成果较少文献 [9] 给出了无限策略的混合策略纳什均衡解的存在性定理和一种迭代算法 [9], 但其只适用于确 [] 定性的博弈模型, 并没有解决不确定博弈论均衡解的问题文献 [] 介绍了种方法将各目标的支付矩阵 A k 转化为清晰的支付矩阵, 再选择合适的目标权重把多目标的对策问题转化为单目标对策问题, 或者根据 Vague 线性规划法求解但其只研究了支付矩阵不确定时的矩阵博弈混合策略纳什均衡, 没有解决策略集为粗糙集时的博弈问题关于 n 人不确定性博弈及博弈的均衡解国内外相关的研究成果还比较少而当前政治经济文化等博弈论的应用领域普遍存在着策略集和效益函数不确定时的博弈和需要求解无限策略混合策略的纳什均衡问题因此, 本文首先运用极限法的基本思想和粒子群算法对 n 人无限策略的混合策略纳什均衡进行了系统的研究 ; 然后提出了粗糙博弈论的概念和求解的基本思想与方法 ; 最后通过实例说明本文方法的有效性. [-] 博弈论就是研究和帮助在相互依存情况中, 理性人应当如何做决策使得自己利益极大化的数学理论它源于历史上一些颇为有趣的游戏, 也是一门学问艰深的理论, 目前已经广泛应用于政治经济旅游国际关系等诸多领域, 因此博弈理论及其应用也日益受到人们的关注与重视常见的博弈分类包含非合作博弈和合作博弈, 其中非合作博弈包括完全信息静态博弈完全信息动态博弈不完全信息静态博弈和不完全信息动态博弈种类型对于完全信息静态博弈来说, 如果存在一种策略组合, 使得每个参与人的策略是对其他参与人策略的最优反应, 如果某种情况下无一参与者可以独自行动而增加收益 ( 即为了自身利益的最大化, 没有任何单独的一方愿意改变其策略 ), 则此策略组合被称为纳什均衡 [-] 设局中人 i 的策略集 S i ={s i,s i,,s i m}, 若局中人 i 对于每个纯策略 S i k 以概率 X i k 进行选择, 则 X i = {x i,x i,,x i m} 被称为局中人 i 的一个混合策略其中 m i X i k,k =,,,m i, x i k =, 局中人 i 混合策略就是 k = 定义在纯策略集 S i 上的一个概率分布混合策略的 n 人非合作博弈由下列三因素确定 : () 局中人的集合 N ={,,,n} ; () 每个局中人 i 有一个混合策略集 X i ={x i, m i x i,,x i m},i=,,,n, 其中 x i k = ; k = () 每个局中人 i 有一个支付函数 μ i = μ i (x) 若局中人 i 的策略集 S i =[a i,b i ], 则博弈 G =[N,

3 曹黎侠等 : 基于粒子群算法的粗糙博弈模型与算法设计 567 {S i }, μ i {S,S,,S N }] 混合策略为 S i 上的一个概率分布 F i (x), x i [a i,b i ] 本文采取连续博弈离散化的方法得到混合策略纳什均衡近似值 [] 现高效优化鉴于粒子群算法对目标函数没有连续性等要求的优势, 并且粒子群算法较其他智能优化算法具有参数较少, 容易编码实现, 收敛速度快, 易于与其他智能算法嫁接等特点, 给出一种用粒子. 98 年,Pawlak 发表了经典论文 Rough Sets, 宣群算法来求解无限策略的博弈论混合策略纳什均衡 [] 的算法告了粗糙集理论的诞生此后, 粗糙集理论引起了许多数学家逻辑学家和计算机研究人员的兴趣, 他. 假设有 n 个局中人, 每个局中人 i 的策略集 S i 都们在粗糙集的理论和应用方面做了大量的研究工作目前, 粗糙集已成为人工智能领域中一个较新的学术热点, 在机器学习知识获取决策分析过程控制等许多领域都得到了广泛的应用与本文相关 [] 的基本概念如下粗糙集 : 给定知识库 S=(U,R), 对于每个子集 X U 和一个等价关系 R ind(s), 可以根据 R 的基本集合的描述来划分集合 X, 定义 X 的 R 下近似集和上近似集分别如下 : 是有界闭区间, 其效益函数 μ i (x) 关于 X i 在策略集 S i 上只有有限个第一类间断点由文献 [9] 知, 该博弈存在无限策略混合策略纳什均衡下面依据数学分析中极限法的基本思想以定量代变量, 结合粒子群 [-5] 算法的基本原理, 给出无限策略博弈论混合策略纳什均衡近似解的基本思想首先把局中人 i 的策略集分成 m 个区域, 如果有间断点, 把间断点作为划分时的分界点, 则在第 j 个子区域上的纳什均衡解实质是最优化问题 () 的解 : R - (X) ={x U:x R X} ìmax μ j (X),max μ j (X),,max μ nj (X) í R - (X) ={x U:x R X } î s.t. s i d Δ ij,i =,,,n; j =,,,m () 也把 pos R (X) = R - (X) 称为 X 的 R 正域,nes R (X) = U - R - (X) 称为 X 的 R 负域, 而集合 bn R (X) = R - (X) - R - (X) 为 X 的 R 边界域如果集合 bn R (X) 是空集, 则称 X 关于 R 是清晰的 ; 如果 bn R (X) 非空, 则称 X 关于 R 是粗糙的知识依赖性的度量 :S =(U,R) 为知识库, 且 C,D R, 定义 k = r c (D) = card(pos c (D)/ card(u)) 为知识 D 是 k 度可推导的这里 card(pos c (D)) 表示根据 C U 中所有一定能归入 D 的元素的数目 ; 系数 r c (D) 可以看作 C 和 D 间依赖性的量度其中,S i d 是第 i 个局中人的一个纯策略 ;x i 是第 i 个粒子的位置 x i S i ;Δ ij 是局中人 i 的策略集 S i =[a i,b i ] 的第 j 个小区域然后在每个子区域上运用粒子群算法对最优化问题 () 进行求解, 即为该子区域上的纯策略纳什均衡解在粒子群算法中, 每个粒子代表博弈的一个混合局势, 它们在混合策略组合的空间内搜寻最优的位置在博弈的纳什均衡中, 博弈参与人的策略都是对对方策略的最优反应, 因此代表纳什均衡的粒子具有最优的适应度在算法迭代中, 粒子会根据观察到的博弈结果向个体自身最优解学习, 且向群文献 [9] 给出了当效益函数只有有限个第一类间断点时,n 人非合作完全信息静态博弈混合策略纳什均衡解是存在的, 并给出了一种无限策略混合策略纳什均衡的近似解法这种解法是将无限策略博弈均衡问题转化为有限策略博弈, 运用非线性规划法达到求其混合策略均衡解的目的, 但是当支付函数比较复杂, 表现为维数比较高的多峰函数时, 难以实体中表现更优的同伴学习通过学习, 每个局中人会调整自己的策略, 因此粒子在博弈的混合策略组合的空间内不断发生移动, 并最终趋向博弈的均衡点最后, 根据极限法中以常量代变量的基本思想, 以该区域上的纯策略纳什均衡解代替该区域上其他各点的值, 就得到了博弈混合策略纳什均衡解的近似值

4 568 Journal of Frontiers of Computer Science and Technology 计算机科学与探索 6, (). pbest k h = ì pbest k - h, if f (Xh) k < f (pbest k - h ) í î Xh, k otherwise () 根据算法的基本思想, 对粒子群算法进行改进, gbest k h = max(pbest k h), h =,,,H () 设计算法步骤如下 : 算法基于粒子群算法的博弈均衡解的求解算法步骤将局中人 i 的策略集 S i 任意划分为 m 个 () 从记忆库中选择 J 个粒子来替换粒子群中那些适应函数值排在整个粒子群中后 J 位的粒子 (5) 由式 () 动态调整惯性权重 ω : 区域 Δ i,δ i,,δ im, 如果有间断点, 把间断点作为划分的分界点步骤当 m 足够大时, 对任意的 j=,,,m, 有 Δ ij - - Δ ij δ 成立,δ 是给定的一个阈值, 如果在区间 Δ ij 上, 对 x,x,,x i -,x i +,,x n, 恒有 f x,i =,,,n, 则在该小区域上纯策略纳什均衡存在 ; 如果在区域 Δ ij 上, 对 x,x,,x i -,x i +,,x n 存在 f x,i =,,,n 的点, 用这些点处的切平面来代替这一小片曲面, 则在该区间上也满足 x,x,,x i -, ìï íï î ω = ω max - ω max - ω min iter max iter () (6) 由式 (5) 更新粒子的速度和位置, 然后转入 () v k + hd = ϖv k hd + c r k (pbestk hd - x k hd) + c r k (gbestk hd - x k hd) (5) hd = x k hd + v k + hd x k + 步骤当 j 依次取,,,m, 重复 ()~(6), 得表即为局中人 i 的混合策略纳什均衡解 X i Table Mixed strategy Nash equilibrium solution of player i i X * i X * i X * im x i +,,x n, 恒有 f x, i =,,,n ; 因此, 局中人 i 的每个子域 Δ i,δ i,,δ im 上, 纯策略纳什均衡均存在步骤在每个子区域上使用粒子群算法求出该子区域上 n 人博弈纳什均衡解, 具体步骤如下 : () 对于给定的 j, 确定种群的规模粒子数 H =, 维数 D, 学习因子 c = c =.6 ; 记忆更新粒子数 J = 8, 惯性权重 ω =.79 8; 迭代终止条件为最大迭代次数 5 次或适应值 f (x) -6 ; 并令进化代数 k = () 初始化所有粒子的位置和速度 ( 随机取 ) () 计算粒子的适应值计算粒子经历过的最好位置和种群经历过的最好位置, 并更新记忆库粒子的适应值可以由目标函数来计算, 令 pbest k h 表示第 h 个粒子进化 k 代所经历的最好位置, 令 gbest k h 表示整个种群进化 k 代所经历的最好位置如果 k=, 则 pbest k h = X h, 否则 pbest k h 可由式 () 来计算 gbest k h 可由式 () 来计算, 并将 gbest k 存入记忆库检查是否满足迭代终止条件, 如果是, 则此时的位置和适应函数值为 (X * j,f (X * j )), 转入步骤 ; 如果否, 转入 (), 其中 X * j = ( X,X,,X n ) P i μ * i m μ * ij j = μ * i m μ * ij j = 此算法还可以通过对初始粒子可行化以及对算法迭代步长加以控制, 保证粒子在算法迭代过程中始终保持在博弈的混合策略组合空间内对 n 个局中人的博弈, 只要局中人的策略集是有界闭区间, 效益函数在策略集上有有限个第一类间断点, 则其混合策略纳什均衡解都可以用算法求解算法的建立有着广泛的应用领域, 能够满足经济金融效益函数的基本要求, 为不确定博弈均衡问题的求解奠定了理论基础. 算法中每个粒子由所有局中人的混合策略来表示, 即 X =(X,X,,X n ), 根据纳什均衡的定义与性质, 粒子的适应度函数如下 : n f (X) = max μ i (X S i d) - μ i (X),i =,,,n,d =,,,m i i = 显然, 当且仅当混合局势为纳什均衡解时, 适应度函数取得最小值, 因此博弈的混合策略组合空间内只有纳什均衡点的适应度为最小 μ * im m μ * ij j =

5 曹黎侠等 : 基于粒子群算法的粗糙博弈模型与算法设计 569 设博弈的局中人 N =, 局中人 i 的策略集为 : d = S i d =[,] [,,.5] [,], i =,, 局中人的效益函数依次为 : μ (x,x,x ) = x x x μ (x,x,x ) ={ x, x <.7 x + x,.5 x. μ (x,x,x ) = ex x + x 该博弈满足混合策略纳什均衡存在的条件, 并且设 δ= 根据算法, 把局中人 i (i =,,) 的策略集划分为个小区域, 记为 Δ,Δ,,Δ,,Δ 其中各变量分割点依次为,, ;.7,.,.9;.5,.,.5 考虑到文章篇幅以及只是为了说明算法的有效性和可行性问题, 随机抽取 6 个区域作为研究对象在此 D=, 通过 Matlab 8b 编程, 按照算法, 得到这 6 个区域上的纯策略纳什均衡解适应函数值效益函数值如表所示, 局中人的混合策略结果如表所示该算例来源于文献 [9] 文献 [9] 给出的近似算法的结果是连续型混合策略纳什均衡解 ; 本文的近似算法是用策略区间上的最优概率作为混合策略, 最大的优点就是直观, 也适用于多维多峰目标函数算法的运行结果局中人更容易做出在某小区间以多大的概率进行策略选择的决策, 而文献 [9] 还需要进一步的计算. 定义在经典博弈论的三要素中, 如果局中人的策略集具有不可分辨性, 或者效益函数是模糊的, Table Running result of improved particle 二者至少满足其一, 理性局中人应当如何做决策使 swarm algorithm 得自己利益极大化的数学理论, 称为粗糙博弈论粗糙博弈论按照博弈重复进行的次数分为动态小区间均衡点适应函数值效益函数值粗糙博弈和静态粗糙博弈 ; 按照局中人了解其他参 Δ (.6,.8,.9).5,.6,.59 与者的信息分为完全信息粗糙博弈和不完全信息粗糙 Δ (.8,.6,.56).87,.8,. Δ Δ Δ (.5,.7,.7) (.7,.78,.57) (.6,.57,.95).7,., ,.55,.7.9,.,.6 博弈本文只研究完全信息非合作静态粗糙博弈论定义在粗糙博弈中, 通过粗糙策略集的精确 [] [] 化, 效益 ( 支付 ) 函数的清晰化, 将粗糙博弈问题 Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ (.6,.9,.) (.58,.7,.88) (.58,.59,.9) (.668,.77,.6) (.75,.56,.8) (.779,.5,.58) (.9,.66,.6) (.,.99,.77) (.,.589,.7) (.6,.77,.69) (.7,.9,.885).9,.,..768,.58,.8.88,.578,.66.,.7,.75.7,.75,.9.7,.779,.57.5,.7,.96.9,.,.97.5,.86,.55.5,.6,8.56.,.759,.7 Table 局中人策略 [, ) [, ) [, ) [, ] Mixed strategies Nash equilibrium of players 概率转化为经典博弈模型, 此时局中人在精确化后的策略集清晰化后的效益函数中, 得到的经典博弈模型的均衡解作为粗糙博弈模型的粗糙均衡解定义在完全信息非合作静态粗糙博弈论中, 设博弈的局中人局中人的粗糙策略集模糊效益 ( 支付 ) 函数构成了完全信息静态粗糙博弈模型该博弈模型通过描述法的方式表示局中人 :i =,,,n ; 粗糙策略集 : 论域 U 上知识 S 的子集 X U, 关于等价关系 R ind(s) 是粗糙的策略集 ; 局中人策略 [.,.7) [.7,.) [.,.9) [.9,.5] 概率局中人策略 [,.5) [.5,.) [.,.5) [.5,.] 概率

6 57 Journal of Frontiers of Computer Science and Technology 计算机科学与探索 6, () 模糊效益函数 : 模糊效益函数的 Vague 集为 { < x, t Ai (x), - f Ai (x) > x (a i,b i )} 据定义, 可以将粗糙博弈模型转化为经典博弈模型, 达到求其均衡解的目的. 根据粗糙集上近似集下近似集正域负域边界域和粗糙度的有关概念 [], 将边界域中的元素以概率 p 划分到正域, 以 -p 的概率划分到负域, 其中 p 为常量, 以此方法完成粗糙策略集的精确化根据 Vague 集理论与方法 [], 模糊效益函数可以完成清晰化因此, 根据定义, 粗糙均衡解的计算可以分为以下三步来完成 () 粗糙策略集的精确化设局中人 i 的粗糙策略集为 (a i,b i ), 它的一个等价关系 R ind(a i,b i ), 可以根据 R 的基本集合的描述来划分集合 (a i,b i ) 为个经典集合 :pos R (a i,b i ) neg R (a i,b i ) bn R (a i,b i ) 采用连续属性离散化的方法 [] 将局中人 i 的策略集 (a i,b i ) =[pos R (a i,b i ) +(bn R (a i,b i ))p] [neg R (a i,b i ) + (bn R (a i,b i ))( - p)] 离散化设局中人 i 在 R 的 bn R (a i,b i ) 中以概率 p 选择 pos R (a i,b i ) 的策略, 以 -p 的概率选择 neg R (a i,b i ) 的策略 ; 然后对局中人的策略集进行约简 [6], 合并具有不可分辨关系的对象 ; 再以约简后的策略为决策条件, 以效益函数为目标条件, 建立决策表, 产生约简规则组合, 即为局中人 i 的精确策略集 () 效益 ( 支付 ) 函数的清晰化设局中人 i 的模糊效益函数的 Vague 集为 { < x,t Ai (x), - f Ai (x) > x (a i,b i )}, 通过式 (6) 将模糊效益 ( 支付 ) 函数清晰化 [,5] L(E(A i )) = t Ai + t Ai ( - t Ai - f Ai ) (6) 如果局中人 i 的粗糙策略集已精确化, 模糊效益函数分别在集合 [pos R (a i,b i ) +(bn R (a i,b i ))p] 和 [neg R (a i,b i ) + (bn R (a i,b i ))( - p)] 上已清晰化, 这样, 局中人 i 的效益函数取以 S i 和 S i 为权的加权平均值 : S i = card[pos R(a i,b i )] + card[(bn R (a i,b i ))p] card(a i,b i ) S i = card[neg R(a i,b i )] + card[(bn R (a i,b i ))( - p)] card(a i,b i ) 其中 card[ ] 表示元素的数目或是区间的长度 () 粗糙博弈模型的求解此时的模型转化为局中人 i(i=,,,n) 的策略集为经典集合效益函数为确定性函数的博弈模型的求解, 可以运用经典博弈论的理论与方法来完成综上所述, 只要博弈局中人的策略集和效益函数满足粗糙博弈论的概念, 都可以通过以上步骤将粗糙博弈论转化为经典博弈论, 再按照算法求出博弈模型的均衡解... 假设在电子商务交易中, 存在两个网络交易平台, 商户只能加入其中一个交易平台才能够进行电子商务活动这样网络交易平台间存在着博弈, 这两个交易平台构成了博弈的局中人影响平台效益的因素是多方面的, 如平台的管理水平广告费人气指数信誉度盈利额销售量等这些因素构成平台间博弈的策略集, 平台效益函数是局中人策略集上的一个 Vague 值, 这样建立起二人零和粗糙博弈模型.. () 策略集的精确化通过发放网络调查问卷和统计分析, 对平台的管理水平广告费人气指数信誉度盈利额销售量在平台效益中的重要程度进行评价, 评价为高中一般低, 依次赋值为, 平台的收益提高赋值为, 否则赋值为结果如表 Table Influence of players strategy on benefit Y Y Y Y Y 5 Y 6 平台的收益首先合并具有不可分辨关系的对象, 删除表的 6 7 两行 ; 然后进行属性约简, 得到约简属性集 {Y,Y } {Y,Y 5 } {Y,Y 6 } {Y,Y 5 } {Y,Y 6 } 取属性规则 {Y,Y } 进行数据挖掘, 得出规则 : Y Y 中 Y 一般平台收益高

7 曹黎侠等 : 基于粒子群算法的粗糙博弈模型与算法设计 57 即当网络平台的人气指数中或者人气指数一般且信誉度高时, 平台效益都会增加因此, 平台管理者有两种策略可以选择 : 一是设法提高平台的人气指数 ; 二是重点关注提高平台信誉度无论这两种策略的哪一种, 都需要平台管理者付出财力和精力来做, 因此二者之间存在着资源竞争关系从而, 局中人精确化的策略集为 {Y,Y 中 Y 一般 } 高 () 效益函数的清晰化根据专家打分和平台自己的统计资料, 分别得出在局中人和依次选择 Y,Y 中 Y 一般高策略时对应的精确集上的效益函数的以 S i 和 S i 为权的平均值, 则最终的效益矩阵分别为 : æ [.,.] [.,.] [.5,.7] ö A = ç [.,.] [.,.5] [.,.6] ç è-[.,.5] -[.,.6] [.,.] ø æ [.,.] [.5,.6] [.8,.9] ö A = ç [.,.] [.,.] [.,.7] ç è-[.,.] -[.,.] [,.] ø 根据式 (6) 将 A A 清晰化分别为 : B = æ...6ö ç..6.8 è ø B = æ ö ç...5 è-. -. ø 假设专家打分和平台自己的统计资料的权重分别为. 和.6, 将两个效益矩阵进行线性集结, 得到 : B = æ ö ç è-. -..ø 根据算法进行求解, 得 : x * =(.8,.96,),y * =(.577,.,), v =.8 当然, 也可以根据线性规划法来求解, 误差在. 即平台以.8 的概率选择提高平台的人气指数, 以.96 的概率选择提高平台的信誉度 ; 平台以.577 的概率选择提高人气指数, 以. 的概率选择提高信誉度, 此时双方达到混合策略纳什均衡, 其均衡值为.8 5 经典博弈论模型和均衡解的研究存在两个弊端 : 一是无限策略混合策略的纳什均衡的研究成果较少 ; 二是经典博弈论模型都只是针对确定性的策略集和效益函数所做的研究, 并没有解决不确定性博弈问题本文首先运用连续属性离散化的方法将无限策略集划分为有限个区间, 在每个区间上运用改进的粒子群算法给出了该区间上的纯策略纳什均衡解, 再根据极限理论得出无限策略的混合策略纳什均衡的一种近似解法由于粒子群算法对目标函数没有过高的要求, 收敛速度快, 适应性强, 从而该近似算法具有较强的适应性此外, 本文首次定义了粗糙博弈论粗糙博弈模型粗糙博弈模型的均衡解, 并发现了一种将粗糙博弈论转化为经典博弈论的一种方法, 实现了借助于经典博弈论纳什均衡的方法来求解粗糙博弈论的均衡解应用实例表明, 本文的定义和求解算法是有效可行的本文针对均衡解的算法研究和粗糙博弈的理论研究是对博弈论现有理论的发展, 拓宽了这门学科的应用范围 References: [] Wang Xianyu, Xiao Yuming. Game theory and its applications[m]. Beijing: Science Press, 8: 5-. [] Kuhn H W. Classic game theory[m]. Han Song, Liu Shijun, Zhang Qianwei. Beijing: China Renmin University Press, 5: 8-7. [] Liu Weibing, Wang Xianjia. Review of evolutionary game decisions design[j]. Operations Research and Managment, 8, 7(): [] Yang Ming, Khan F I, Sadiq R, et al. A rough set- based game theoretical approach for environmental decision-making: a case of offshore oil and gas operations[j]. Process Safety and Environmental Protection,, 9(): 7-8. [5] Nash J F. Non-cooperative games[j]. The Annals of Mathematics, 95, 5(): [6] Yannelis N C. Equilibrium in non- cooperative models of competition[j]. Journal of Economic Theory, 987, (): 96-. [7] Peng Shumei. Relationship between the social equilibrium existence theorem and Nash equilibrium theorem[d]. Beijing: Capital Normal University, 8: -5. [8] Pavlidis N G, ParsoPoulos K E, Vrahatis M N. Computing

8 57 Journal of Frontiers of Computer Science and Technology 计算机科学与探索 6, () Nash equilibria through computational intelligence methods[j]. Journal of Computational and Applied Mathematics, 5, 75(): -6. [9] Cao Lixia, Huang Guangqiu. Infinite mixed strategy Nash equilibrium s theory and algorithm research[j]. Northwest Normal University: Natural Science,, 5(): -7. [] Zhou Xiaoguang, Tan Chunqiao, Zhang Qiang. Based on Vague sets decision theory and method[m]. Beijing: Science Press, 8: [] Zhang Wenxiu, Wu Weizhi, Liang Jiye, et al. Rough set theory and method[m]. Beijing: Science Press, : -. [] Liang Yanchun, Wu Chunguo, Shi Xiaohu, et al. Theory and application of swarm intelligence optimization algorithm[m]. Beijing: Science Press, 9: 75. [] Liu C Y, Yan C Q, Wang J J. Hybrid particle swarm optimization algorithm and its application in nuclear engineering[j]. Annals of Nuclear Energy,, 6: [] Min Weidong, Liu Yonghui, Ke Yongzhen, et al. Using particle swarm optimization algorithm to improve multi-agents network management[j]. Journal of Computational Information Systems,, : [5] Wang Weiming, Peng Xun, Zhu Guoniu, et al. Dynamic representation of fuzzy knowledge based on fuzzy Petri net and genetic-particle swarm optimization[j]. Expert Systems with Applications,, (): [6] Wang Ling. A method of discretization base on improved particle swarm algorithm[j]. Computer Engineering and Applications,, 9(): 9-. [] 汪贤裕, 肖玉明. 博弈论及其应用 [M]. 北京 : 科学出版社, 8: 5-. [] Kuhn H W. 博弈论经典 [M]. 韩松, 刘世军, 张倩伟, 译. 北京 : 中国人民大学出版社, 5: 8-7. [] 刘伟兵, 王先甲. 进化博弈决策机制设计综述 [J]. 运筹与管理, 8, 7(): [7] 彭淑梅. 社会均衡存在定理与 Nash 均衡存在定理及其之间的关系 [D]. 北京 : 首都师范大学, 8: -5. [9] 曹黎侠, 黄光球. 无限策略的混合策略纳什均衡理论与算法研究 [J]. 西北师范大学学报 : 自然科学版,, 5(): -7. [] 周晓光, 谭春桥, 张强. 基于 Vague 集的决策理论与方法 [M]. 北京 : 科学出版社, 8: [] 张文修, 吴伟志, 梁吉业, 等. 粗糙集理论与方法 [M]. 北京 : 科学出版社, : -. [] 梁艳春, 吴春国, 时小虎, 等. 群智能优化算法理论与应用 [J]. 北京 : 科学出版社, 9: 75. [6] 汪凌. 一种基于改进粒子群的连续属性离散化算法 [J]. 计算机工程与应用,, 9(): 9-. CAO Lixia was born in 97. She is a Ph.D. candidate at Xi an University of Architecture and Technology, and an associate professor at Xi an Technological University. Her research interests include rough set, complex network, operation research and cybernetics, management decision analysis and game theory, etc. 曹黎侠 (97 ), 女, 陕西西安人, 西安建筑科技大学博士研究生, 西安工业大学副教授, 主要研究领域为粗糙集, 复杂网络, 运筹学与控制论, 管理决策分析及博弈论等 HUANG Guangqiu was born in 96. He received the Ph.D. degree from Northeast University. Now he is a professor and Ph.D. supervisor at Xi an University of Architecture & Technology. His research interests include e-business and network security, information management, systems engineering, complex system simulation and control, decision optimization and management, etc. He has completed 76 research projects including the national key scientific research projects, the national natural science foundation projects, provincial and ministerial level research projects, etc. He has published more than papers and 6 works. 黄光球 (96 ), 男, 博士, 西安建筑科技大学教授博士生导师, 主要研究领域为电子商务与网络安全, 信息管理, 系统工程, 复杂系统仿真与控制, 决策优化与管理等共完成科研课题 76 项, 其中包括国家七五八五九五重点科研项目项, 国家自然科学基金项目项 ; 在国内外重要期刊和会议上发表学术论文多篇, 出版著作 6 部

,,.,, : 1),,,,, 2),,,,, 3),,,,,,,,,, [6].,,, ( ),, [9], : 1), 2),,,,, 3),,, 2.,, [10].,,,,,,,,, [11]. 2.1,, [12],, ;, ; Fig. 1 1 Granular hier

,,.,, : 1),,,,, 2),,,,, 3),,,,,,,,,, [6].,,, ( ),, [9], : 1), 2),,,,, 3),,, 2.,, [10].,,,,,,,,, [11]. 2.1,, [12],, ;, ; Fig. 1 1 Granular hier 36 7 Vol. 36, No. 7 2010 7 ACTA AUTOMATICA SINICA July, 2010 1, 2 1, 2, 3 1, 2,,,,,,, DOI,,, 10.3724/SP.J.1004.2010.00923 Distributed Simulation System Hierarchical Design Model Based on Quotient Space