纳什均衡解及其QPSO算法求解_于敏(1)

衡。这时逐一检验的方法也行不通， 因为每个博弈方的混合策
略都是采用各纯策略的概率分布， 概率分布是可以连续变化
基金项目： 国家自然科学基金（ ｔｈｅ Ｎａｔｉｏｎａｌ Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｆｏｕｎｄａｔｉｏｎ ｏｆ Ｃｈｉｎａ ｕｎｄｅｒ Ｇｒａｎｔ Ｎｏ．６０４７４０３０） 。 作者简介： 于敏（ １９８０－ ） ， 女， 硕士研究生， 主要研究方向为进化计算、进化博弈； 须文波（ １９４６－ ） ， 男， 教授， 研究生博士生导师 ， 主 要 研 究 方 向 为 进
化计算、人工智能、生物信息学； 孙俊（ １９７４－ ） ， 男， 讲师， 博士生， 主要研究方向为进化计算、生物信息学。
Ｃ于ｏｍｐ敏ｕｔｅ，ｒ须Ｅ文ｎｇ波ｉｎｅ， ｅ孙ｒｉｎｇ俊ａｎ：ｄ纳Ａ什ｐｐ均ｌｉ衡ｃａｔ解ｉｏｎ及ｓ 其计算ＱＰ机ＳＯ工算程法与求应解用
２００７， ４３（ １０） ４９
的， 所以可能的混合策略数必然是无限的， 这时也必须有更有 效 的 求 纳 什 均 衡 的 方 法 。于 是 用 优 化 算 法 来 解 决 纳 什 均 衡 问 题 就成为了理想中的想法。
Ａｂｓｔｒ ａｃｔ： Ｎａｓｈ ｅｑｕｉｌｉｂｒｉｕｍ ｉｓ ｏｎｅ ｋｉｎｄ ｏｆ ｇａｍｅ ｓｏｌｕｔｉｏｎ ｃｏｎｃｅｐｔ， ｍａｙ ｍａｋｅ ｔｈｅ ｓｔｒｉｃｔ ｍａｎｙ ｆｏｒｅｃａｓｔｓ ｔｏ ｅｘｔｒｅｍｅｌｙ ｗｉｄｅｓｐｒｅａｄ ｔｙｐｅ ｇａｍｅ．Ｑｕａｎｔｕｍ－ ｂｅｈａｖｅｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ｉｓ ｉｎｔｒｏｄｕｃｅｄ ａｎｄ ｐｒｅｓｅｎｔｅｄ ｂａｓｅｄ ｏｎ ｔｈｅ ａｎａｌｙｓｉｓ ｏｆ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐ－ ｔｉｍｉｚａｔｉｏｎ．Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ｔｈｅ ｎａｓｈ ｅｑｕｉｌｉｂｒｉｕｍ ｓｏｌｕｔｉｏｎ ｉｓ ｄｉｓｃｕｓｓｅｄ ａｎｄ ｇｉｖｅｎ ｂｙ ｕｓｉｎｇ ＱＰＳＯ．Ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｓｉｍｕｌａｔｉｏｎ ｔｅｓｔｉｎｇ ａｎｄ ｔｈｅ ｃｏｍｐａｒｉｓｉｏｎ ｗｉｔｈ ｓｅｖｅｒａｌ ａｌｇｏｒｉｔｈｍ ｉｓ ｖｅｒｉｆｉｅｄ ａｎｄ ｔｈｅ ｇｌｏｂａｌ ｃｏｎｖｅｒｇｅｎｃｅ ｐｒｏｐｅｒｔｙ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｉｓ ｐｒｏｖｅｄ． Ｋｅｙ ｗｏｒ ｄｓ： ｑｕａｎｔｕｍ－ ｂｅｈａｖｅｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ； ｎａｓｈ ｅｑｕｉｌｉｂｒｉｕｍ； ｓｔｒｅｔｃｈｉｎｇ ｔｅｃｈｎｉｑｕｅ； ｒｅｐｕｌｓｉｏｎ ｔｅｃｈｎｉｑｕｅ； ｇａｍｅ
ｃ１， ｃ２： 权 重 因 子 ； ｒａｎｄ（ ） ： 随 机 函 数 ， 产 生［０， １］的 随 机 数 ； ｗ： 惯
性权重函数。
ＰＳ０ 算 法 概 念 简 单 、容 易 实 现 、搜 索 速 度 快 、搜 索 范 围 大 ，
和其他优化算法相比， 它的优点突出。
２．２ 具有量子行为的粒子群化粒子群； （ ２） 根据公式（ ３） 计算 ｍｂｅｓｔ 的值； （ ３） 求每个粒子适应度值， 比较求 ｐｉｄ； （ ４） 对于每个粒子比较 ｐｉｄ， 求得 ｐｇｄ； （ ５） 更新 ｐｇｄ； （ ６） 对 于 粒 子 的 每 一 维 ， 根 据 公 式 （ ４） ， 在 ｐｉｄ 和 ｐｇｄ 之 间 取 得一个随机点； （ ７） 根据公式（ ５） 获得一个新的位置； （ ８） 重复（ ２） － （ ７） 直到条件不满足， 迭代结束。
ｉ＝１
Ｐｉ＝（
１ Ｍ
ｉ＝１
Ｐｉ１，
１ Ｍ
ｉ＝１
Ｐｉ２， …，
１ Ｍ
Ｐｉｄ）
ｉ＝１
（ ３）
ｐｉｄ＝"＊Ｐｉｄ＋（ １－ "） ＊Ｐｇｄ "＝ｒａｎｄ
（ ４）
ｘｉｄ＝ｐｉｄ±#＊｜ｍｂｅｓｔｄ－ ｘｉｄ｜＊Ｉｎ（
１ ｕ
）
ｕ＝ｒａｎｄ
（ ５）
这里的 ｍｂｅｓｔ 是粒子群的中间位置 ， ｐｉｄ 为 Ｐｉｄ 和 Ｐｇｄ 之间的 随机点。" 和 $ 都是［０， １］的随机数。% 为 ＱＰＳＯ 的收缩扩张系数。
随着博弈论和经济学应用范围地不断扩大， 纳什均衡的影 响也越来越大， 用纳什均衡来分析和解决经济、政治、法律等各 种领域的现象和内容， 已成为引人注目的主要学术潮流。粒子 群算法（ ＰＳＯ） 是由美国社会心理学家 Ｊａｍｅｓ Ｋｅｎｎｅｄｙ 和电气工 程师 Ｒｕｓｓｅｌｌ Ｅｂｅｒｈａｒｔ 在 １９９５ 年共同提出的， 是继蚁 群 算 法 之 后有一种新的群体智能算法， 目前已成为进化算法的一个重要 分 支 。其 基 本 思 想 是 受 他 们 早 期 对 鸟 类 群 体 行 为 研 究 结 果 的 启 发， 并利用了生物学家 Ｆｒａｎｋ Ｈｅｐｐｎｅｒ 的生物群体模型。
ｋ
第 ｋ 次迭代粒子 ｉ 飞行速度矢量的第 ｄ 维分量； ｘｉｄ ： 第 ｋ 次 迭
代 粒 子 ｉ 位 置 矢 量 的 第 ｄ 维 分 量 ； ｐｉｄ： 粒 子 ｉ 个 体 最 好 位 置
ｐｂｅｓｔ 的 第 ｄ 维 分 量 ； ｐｇｄ： 群 体 最 好 位 置 ｇｂｅｓｔ 的 第 ｄ 维 分 量 ；
４８ ２００７， ４３（ １０）
Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ 计算机工程与应用
纳什均衡解及其 ＱＰＳＯ 算法求解
于 敏， 须文波， 孙 俊 ＹＵ Ｍｉｎ， ＸＵ Ｗｅｎ－ ｂｏ， ＳＵＮ Ｊｕｎ
江南大学 信息学院， 江苏 无锡 ２１４１２２ Ｓｃｈｏｏｌ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ， Ｓｏｕｔｈｅｒｎ Ｙａｎｇｔｚｅ Ｕｎｉｖｅｒｓｉｔｙ， Ｗｕｘｉ， Ｊｉａｎｇｓｕ ２１４１２２， Ｃｈｉｎａ
个没有重量和体积的微粒， 并在搜索空间中以一定的速度飞
行 。该 飞 行 速 度 由 个 体 的 飞 行 经 验 和 群 体 的 飞 行 经 验 进 行 动 态
调整。粒子 ｉ 在 Ｎ 维空间里的位置表 示 为 矢 量 ｘｉ＝（ ｘ１， ｘ２， … ， ｘＮ） ， 飞行速度表示为矢量 ｖｉ＝（ ｖ１， ｖ２， …， ｖＮ） 。每个粒子都有一个 由 目 标 函 数 决 定 的 适 应 值 （ ｆｉｔｎｅｓｓ ｖａｌｕｅ） ， 并 且 知 道 自 己 到 目
由 于 Ｆｒａｎｓ Ｖａｎ ｄｅｎ ｂｅｒｇｈ 已 经 证 明 了 ＰＳＯ 算 法 既 不 能
收敛于全局最优解， 甚至局部最优解。许多学者尝试用众多方
法来改进算法的收敛性能。２００４ 年 Ｓｕｎ 等在研究了 Ｃｌｅｒｃ 等人
关于粒子收敛行为的研究成果后， 从量子力学的角度提出了一
种新的 ＰＳＯ 算法模型［１１］。这种模型是以 ＤＥＬＴＡ 势阱为基础， 认
＊
ｉ， ｓｉ 是 （ 至 少 不 劣 于 ） 针 对 其 他 ｎ－ １ 个 参 与 者 所 选 战 略｛ｓ１ ， … ，
＊
＊
＊
＊
＊
ｓｉ－ １ ， ｓｉ＋１ ， … ， ｓｎ ｝的 最 优 反 应 战 略 ， 则 称 战 略 组 合｛ｓ１ ， … ， ｓｎ ｝是 该
博弈的一个纳什均衡。即
＊
＊
＊＊
＊
Ｕｉ｛ｓ１ ， …， ｓｉ－ １ ， ｓｉ ， ｓｉ＋１ ， …， ｓｎ ｝≥Ｕｉ
＊
＊ ＊＊
＊
｛ｓ１ ， …， ｓｉ－ １ ， ｓｉ ， ｓｉ＋１ ， …， ｓｎ ｝对所有 Ｓｉ 中的 ｓｉ 都成立。
１．２ 纳什均衡的解法
纳什均衡的定义本身并没有说明如何找博弈中的纳什均
衡的问题， 不管是纯策略纳什均衡还是混合策略纳什均衡。根
据纳什均衡的定义， 最多只能检验某个策略组合是否是纳什均
由 于 Ｆｒａｎｓ Ｖａｎ ｄｅｎ ｂｅｒｇｈ 已 经 证 明 了 ＰＳＯ 算 法 既 不 能 收敛与全局最优解， 甚至于局部最优解， 许多学者许多方法以 改进算法的收敛性能。２００４ 年 Ｓｕｎ 等在研究了 Ｃｌｅｒｃ 等人关于 粒子收敛行为的研究成果后， 从量子力学的角度提出了一种新 的 ＰＳＯ 算法模型．这种模型是以 ＤＥＬＴＡ 势阱为基础， 认为粒子 具有量子行为， 并根据这种模型提出了量子粒子群算法 （ Ｑｕａｎｔｕｍ－ ｂｅｈａｖｅｄ Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ） ， 其实验结果 证明 ＱＰＳＯ 收敛性能有了很大地改进。
１ 纳什均衡
１．１ 纳什均衡的定义
纳 什 均 衡 （ Ｎａｓｈ Ｅｑｕｉｌｉｂｒｉｕｍ） 是 博 弈 解 的 一 般 名 称 ， 是 当
前博弈理论体系的核心概念。在 ｎ 个参与者标准式博弈 Ｇ＝｛Ｓ１，
＊
＊
…， Ｓｎ； ｕ１， …， ｕｎ｝中， 如果战略组合｛ｓ１ ， …， ｓｎ ｝满足对每一参与者
为粒子具有量子行为， 并根据这种模型提出了量子粒子群算法
（ Ｑｕａｎｔｕｍ－ ｂｅｈａｖｅｄ Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ） ， 其实验结果
证明 ＱＰＳＯ 收敛性能有了很大地改进。
算法原理： 在具有量子行为的粒子群算法（ ＱＰＳＯ） 中， 粒子
的主迭代公式是：
Ｍ
Ｍ
Ｍ
Ｍ
" " " " ｍｂｅｓｔ＝ １ Ｍ
衡。当一个博弈中的博弈方数量很少， 而且每个博弈方只有很
有限的策略时， 博弈中全部可能的纯策略组合数量也比较少，
这时可以根据纳什均衡的定义， 对所有纯策略组合进行逐一检
验。找出其中的纯策略纳什均衡。但很多博弈有多个博弈方， 或
者 各 个 博 弈 方 有 多 种 甚 至 有 无 限 多 种 可 选 策 略 。这 些 博 弈 中 可
ＹＵ Ｍｉｎ， ＸＵ Ｗｅｎ－ ｂｏ， ＳＵＮ Ｊ ｕｎ．Ｎａｓｈ ｅｑｕｉｌｉｂｒ ｉａ ａｎｄ ｑｕａｎｔｕｍ－ ｂｅｈａｖｅｄ ｐａｒ ｔｉｃｌｅ ｓｗａｒ ｍ ｏｐｔｉｍｉｚａｔｉｏｎ．Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒ ｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ， ２００７， ４３（ １０） ： ４８－ ５１．