基于免疫粒子群算法的广义Nash均衡问题求解 (2013年)
需积分: 12 32 浏览量
2021-04-29
00:25:24
上传
评论 1
收藏 1.09MB PDF 举报
收稿日期： ２０１３０１０３； 修 回 日期： ２０１３０２２２ 基 金项 目： 国家 自 然科 学 基金 资 助项 目 （１１１６１００８）；国 家 留 学 基 金 资 助 项 目
（２０１２０１４７００３９）；国家教育部博士点基金资助项目（２０１１５２０１１１０００２）；贵州省自然科学基金资助项目（黔科合 Ｊ字［２０１２］２１３９号）
作者简介：贾文生（１９８１），男，河南南阳人，博士研究生，主要研究方向为算法博弈论（ｊｗｓ０５０５＠１６３．ｃｏｍ）；向淑文（１９６４），男（通信作者），教
授，博导，主要研究方向为博弈论、非线性分析；杨剑锋（１９８６），男，博士研究生，主要研究方向为软件可靠性分析；何基好（１９７６），男，博士研究
生，主要研究方向为算法博弈论．
基于免疫粒子群算法的广义 Ｎａｓｈ均衡问题求解
贾文生
ａ，ｂ
，向淑文
ａ，ｂ
，杨剑锋
ｂ
，何基好
ａ
（贵州大学 ａ．理学院；ｂ．计算机科学学院，贵阳 ５５００２５）
摘 要：针对广义 Ｎａｓｈ均衡求解问题，提出了一种免疫粒子群算法。首先利用非线性互补问题，将广义 Ｎａｓｈ
均衡问题转换为非线性方程组问题，然后把免疫算法中抗体的免疫记忆功能和抗体浓度抑制机制引入基本粒子
群算法，设计了一种免疫粒子群算法。最后通过数值实验表明，该算法保持了粒子群种群多样性，增强了粒子群
算法的全局寻优能力，加快了算法的收敛速度，具有较好的性能。
关键词：免疫算法；粒子群算法；广义 Ｎａｓｈ均衡；非线性互补问题
中图分类号：ＴＰ３０１；Ｏ２２５ 文献标志码：Ａ 文章编号：１００１３６９５（２０１３）０９２６３７０４
ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１３６９５．２０１３．０９．０２０
ＳｏｌｖｉｎｇｇｅｎｅｒａｌｉｚｅｄＮａｓｈｅｑｕｉｌｉｂｒｉｕｍｐｒｏｂｌｅｍｂａｓｅｄｏｎ
ｉｍｍｕｎｅｐａｒｔｉｃｌｅｓｗａｒｍａｌｇｏｒｉｔｈｍ
ＪＩＡＷｅｎｓｈｅｎｇ
ａ，ｂ
，ＸＩＡＮＧＳｈｕｗｅｎ
ａ，ｂ
，ＹＡＮＧＪｉａｎｆｅｎｇ
ｂ
，ＨＥＪｉｈａｏ
ａ
（ａ．ＣｏｌｌｅｇｅｏｆＳｃｉｅｎｃｅ，ｂ．ＣｏｌｌｅｇｅｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，ＧｕｉｚｈｏｕＵｎｉｖｅｒｓｉｔｙ，Ｇｕｉｙａｎｇ５５００２５，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：ＴｈｉｓｐａｐｅｒｐｒｅｓｅｎｔｅｄａｎｉｍｍｕｎｅｐａｒｔｉｃｌｅｓｗａｒｍａｌｇｏｒｉｔｈｍｆｏｒｓｏｌｖｉｎｇｇｅｎｅｒａｌｉｚｅｄＮａｓｈｅｑｕｉｌｉｂｒｉｕｍｐｒｏｂｌｅｍ．Ｆｉｒｓｔｉｔ
ｒｅｆｏｒｍｕｌａｔｅｄｔｈｅｇｅｎｅｒａｌｉｚｅｄＮａｓｈｅｑｕｉｌｉｂｒｉｕｍｐｒｏｂｌｅｍａｓｔｈｅｎｏｎｌｉｎｅａｒｅｑｕａｔｉｏｎｓｐｒｏｂｌｅｍｂｙｔｈｅｎｏｎｌｉｎｅａｒｃｏｍｐｌｅｍｅｎｔａｒｉｔｙ
ｐｒｏｂｌｅｍ．Ｔｈｅｎｉｔｄｅｓｉｇｎｅｄａｎｉｍｍｕｎｅｐａｒｔｉｃｌｅｓｗａｒｍａｌｇｏｒｉｔｈｍｂｙｉｎｖｏｌｖｉｎｇｔｈｅｉｍｍｕｎｅｍｅｍｏｒｙｆｕｎｃｔｉｏｎａｎｄｔｈｅａｎｔｉｂｏｄｙｃｏｎ
ｃｅｎｔｒａｔｉｏｎｉｎｈｉｂｉｔｉｏｎｍｅｃｈａｎｉｓｍｉｎｔｏｔｈｅｏｒｉｇｉｎａｌｓｗａｒｍａｌｇｏｒｉｔｈｍ．Ｆｉｎａｌｌｙｔｈｅｃｏｍｐｕｔｅｒｓｉｍｕｌａｔｉｏｎｒｅｓｕｌｔｓｄｅｍｏｎｓｔｒａｔｅｔｈａｔｔｈｅ
ｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｉｓｅｆｆｅｃｔｉｖｅａｎｄｉｔｎｏｔｏｎｌｙｋｅｅｐｓｔｈｅｖａｒｉｅｔｙｏｆｔｈｅｏｒｉｇｉｎａｌｓｗａｒｍ，ｂｕｔａｌｓｏｉｍｐｒｏｖｅｓｔｈｅａｂｉｌｉｔｉｅｓｏｆｓｅｅｋｉｎｇ
ｔｈｅｇｌｏｂａｌｏｐｔｉｍｉｚａｔｉｏｎｒｅｓｕｌｔａｎｄｔｈｅｅｖｏｌｕｔｉｏｎｓｐｅｅｄｏｆｃｏｎｖｅｒｇｅｎｃｅ．
Ｋｅｙｗｏｒｄｓ：ｉｍｍｕｎｅａｌｇｏｒｉｔｈｍ；ｐａｒｔｉｃｌｅｓｗａｒｍａｌｇｏｒｉｔｈｍ；ｇｅｎｅｒａｌｉｚｅｄＮａｓｈｅｑｕｉｌｉｂｒｉｕｍ；ｎｏｎｌｉｎｅａｒｃｏｍｐｌｅｍｅｎｔａｒｉｔｙｐｒｏｂ
ｌｅｍ
'
引言
广义 Ｎａｓｈ均 衡 问 题 由 诺 贝 尔 奖 得 主 Ｄｅｂｒｅｕ、Ａｒｒｏｗ等
人
［１，２］
提出，近年来受到了越来越多学者的关注，产生了大量
研究成果，已广泛应用于经济均衡、电力市场、环境污染治理、
计算机和交通网络等领域
［３～７］
。但遗憾的是 Ａｒｒｏｗ、Ｄｅｂｒｅｕ并
没有给出一个求解广义 Ｎａｓｈ均衡的算法，广义 Ｎａｓｈ均衡算法
的设计和求解至今仍没有一套相对成熟的理论和方法，仍是学
者关注的热点。对广义
Ｎａｓｈ均衡的求解，传统的数学分析方
法大体上有两种做法，一种思路是将广义 Ｎａｓｈ均衡问题转换
为拟变分不 等式问 题设计 求解算 法
［８］
，另一 思路是 将广 义
Ｎａｓｈ均衡问题利用 ＮＩ函数转换为带约束或无约束的最优化
问题设计牛顿类型的求解算法
［９］
。但是传统的数学分析算法
往往要求博弈局中人的支付函数和策略集具有较高的连续性
和凸（凹）性，并且算法本身往往依赖于初始点的选取，在一定
程度上限制了该类算法的应用。
Ｒｏｕｇｈｇａｒｄｅｎ
［１０］
指出 Ｎａｓｈ均
衡的求解是一个 ＮＰｈａｒｄ问题，随着博弈规模的不断增大，传
统的数学分析算法面临着计算复杂度高和计算时间长等问题。
随着现代智能算法的不断深入研究和发展，智能算法在解决
ＮＰ难问题上体现了较强的优越性。因此，本文尝试借鉴生物
进化理论和生物行为规律的免疫粒子群算法来计算和模拟广
义
Ｎａｓｈ均衡的求解，是一种新的途径和方法。通过实例的计
算和比较，表明本文提出的免疫粒子群智能算法具有较好的性
能。
!
广义
?)@ A
均衡的描述
对于一个广义博弈问题，假设有 Ｎ个局中人，第 ｖ（ｖ＝１，
２，…，Ｎ）个局中人的决策变量为 ｘ
ｖ
∈
Ｒ
ｎ
ｖ
，且将所有局中人的
决策变量所组成的向量记为
ｘ＝（ｘ
１
，ｘ
２
，…，ｘ
Ｎ
）
Ｔ
∈
Ｒ
ｎ
，其中ｎ＝
∑
Ｎ
ｉ＝１
ｎ
ｉ
。为强调向量 ｘ中的第 ｖ个变量，记 ｘ＝（ｘ
ｖ
，ｘ
－ｖ
）
Ｔ
，其中
ｘ
－ｖ
表示除局中人 ｖ之外的所有局中人所构成的决策变量。记
第 ｖ个局中人的策略集为 Ｘ
ｖ
Ｒ
ｎ
ｖ
，所有局中人所构成的策略
集记为
Ｘ＝
∏
ｊ
∈
Ｎ
Ｘ
ｖ
Ｒ
ｎ
，而 Ｘ
－ｖ
＝
∏
ｊ
∈
Ｎ，ｊ
≠
ｖ
Ｘ
ｊ
表示除局中人 ｖ之外的
所有博弈参与者所构成的策略集。博弈中每个局中人
ｖ都选
定自己的策略 ｘ
ｖ
极小化其支付函数
θ
ｖ
，即
ｍｉｎ
ｘ
ｖ
∈
Ｒ
ｎ
ｖ
θ
ｖ
（ｘ
ｖ
，ｘ
－ｖ
），
ｘ
ｖ
∈
Ｋ
ｖ
（ｘ
－ｖ
） （１）
第 ３０卷第 ９期
２０１３年 ９月
计 算 机 应 用 研 究
ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓ
Ｖｏｌ．３０Ｎｏ．９
Ｓｅｐ．２０１３
资源评论
