基于遗传算法的重复囚徒困境博弈策略
在复杂网络中的演化
*
林 海 吴 晨旭
( 厦 门 大 学 物 理 系, 理 论 物 理 与 天体 物 理 研 究 所, 厦 门 3 6 1 0 0 5 ) ( 2 0 0 6 年1 1 月1 6 日 收 到; 2 0 0 7 年4 月5 日 收 到 修 改 稿)
利 用 遗 传 算 法 研 究 重 复 囚 徒 困 境 博 弈 策 略 在 复 杂 网 络 中 的 演 化. 研 究 结 果 表 明: 处 于 复 杂 网 络 中 有 记 忆 的 个 体通 过 基 因 的 复 制 、重 组 、变 异 和 选 择 能 够 进 化 出 一 种 自 组 织 的 合 作 机 制. 这 种 合 作 机 制 既 能 够 在 群 体 中 激 发 合 作 行为 的 产 生, 加 强 和 维 护 持 续 的 合 作 行 为, 同 时 又 能 对 背 叛 的 个 体 进 行 惩 罚 和 报 复, 因 此 能 够 促 使 复 杂 网 络 中 进 化 出 具 有 很 高 合 作 率 的 群 体.
关键 词: 复杂 网络, 遗 传算 法, 进 化博弈, 合作 P A C C : 0 1 7 5 , 0 5 6 5
* 国 家 杰 出 青 年 科 学 基 金( 批 准 号: 1 0 2 2 5 4 2 0 ) 资 助 的 课 题.
通 讯 联 系 人. E 2 m a i l : c x w u @ x m u . e d u . c n
1 1 引 言
达尔 文的进 化论 认为 自然 选择 会促 进有 利于 个 体生 存和 繁殖的 那些 性状 的发 展, 那么, 生物 界中 普 遍存 在的 合作行 为是 如何 在自 然选 择的 压力 下进 化 出来 的呢? 进化 博弈 论为 理解 合作 行为 的起 源及 演 化提供 了 一 个 强 有力 的 理 论 框 架
[ 1) 3 ]
. 研 究 生 物 群 体中 进化 博弈的 传统 方法 通常 假设 个体 是均 匀混 合 的, 即 群体 中的 任何 一 个 个 体 都以 同 样 的 概 率 和其 他个体 相 遇 并 进 行 博 弈. 然 而, 这 种 模 型 过 于 理 想 化, 因 为现 实中 的生 物个 体活 动范 围总 是有限 的, 由 此组成 的群 体具 有 一 定 的空 间 分 布 或 者 空间 结 构.
因此Na w a k等
[ 4 ]
又研 究了 位于 二维 规则 格点 上 的进 化博弈, 他 们假 设每 个 个 体 都 占据 一 个 格 点 并 且只 与自 己的 近邻相 互作 用. 研究 发现, 对于 囚徒 困境 博 弈, 空 间结 构有 利于 合作 行为 的演 化. 随 着近 年来 复 杂网络
[ 5 ) 8]
理 论 研 究 的 兴 起, 人 们 发 现 规 则 的 格 点 并不 能很 好地描 述 现 实中 的 各 种 关 系 网 络. 现 实中 的各种 网 络 包 括 社 会 网 络 、生 物 网 络 、技 术 网 络 等 等, 其 拓扑 结构 通常 都具 有 小 世界( sm a l l2 w orl d ) [ 9] 或
无标度( sc a l e2 fre e )
[ 1 0 ]
的特 征. 因 此, 复 杂网 络 理 论为 具有 空间 结构的 生物 群体 的进 化博 弈论 研究 提供 了
一 个 更 为 实 际的 框 架
[ 1 1 ) 1 3 ]
. 另一 方 面, 文 献
[ 1 1 ) 1 3 ] 研 究 的 个 体 可 以 认为 是 没 有 记 忆 的, 个 体
当前 的行 为仅 取 决于 上 一 轮 博 弈 的 结果. Ax e l rod [ 1 4 ] 则假设 个 体 能 够 记 忆 与 其 他 个 体 前3 轮 的 博 弈 情 况, 利 用遗 传算 法 研究 有 记 忆 的 个 体在 均 匀 混 合 群 体中 的演 化, 得到 了一些 很有 意义 的结 果, 如经 过基 因的 复制 、重组 、变 异 和 选 择, 个 体 能够 进 化 出 一 报
还一 报( ti t for ta t, 也 称 为 针 锋 相 对) 的 行 为 模 式 等
等. 本 文则 把基 于 有记 忆 个 体 的 遗 传算 法 模 型 应 用 到位 于复 杂网 络中 的群 体. 研 究发 现, 复杂 网络 中的 群体 能够 演化 出与 均匀 混合 群体 不同 的一 些行 为模 式. 这 些行 为模 式 能够 促 使 复 杂 网 络中 进 化 出 具 有 很高 合作 率的 群体.
2 1 模 型
囚徒 困境 是博 弈 论 中 的 经典 模 型. 在 囚 徒 困 境 博弈 中, 两个 个体 同时决 定是 合作 还是 背叛, 如 果两 者互 相 合 作, 则 双 方 都 得 到 R 的 收 益, 如 果 互 相 背 叛, 则得益P , 如果 甲合 作而 乙背 叛, 则 甲得 益S , 乙
得益 T . 这里T > R > P > S , 同 时2 R > S + T , 即 相
互合 作双 方 的 总 收 益 大 于 一 方 背 叛 另 一 方 的 总 收 益, 然而 对于 个体 而言, 以背 叛对 合作 得到 的收 益却
1 0 0 02 3 2 90 P 2 0 0 7 P 5 6 ( 0 8) P 4 3 1 3 2 0 6 ACTA PHYSICA SINICA n 2 0 0 7 Chi n . Phys. Soc .
要大 于以 合作对 合作. 因 此, 囚 徒困 境模 型展 示了 个 体利 益与 群体利 益 的 冲突. 生 物界 群 体 中 的 个 体经 常面 临囚 徒困境 的 局 面, 例 如 有一 种 吸 血 蝙 蝠 能够 把食物 喂给 未 吃饱 的 同 伴
[ 1 5 ]
, 猫 鼬( m e e rka t) 为 正在
觅食的 同伴 警 戒 捕 食 者
[ 1 6 ]
等 等. 在 这 类 例 子 中, 尽 管单方 面 背 叛 行 为 的 收 益 大 于 与 对 方 合 作 时 的 收 益, 然 而大 自然 还是 演化 出了 不少 相互 合作的 物种.
我们 构 建了4 种不 同 拓 扑 结构 的 复 杂网 络, 利 用遗 传算 法
[ 1 7 ]
研 究 位 于 复 杂 网 络 中 的 个 体 在 囚 徒 困境 模型 的框架 下如 何演 化出 合作 行为. 规则 网络 、 小世界 网 络、随 机 网 络 采 用Wa tts和Stroga tz
[ 9]
提 出 的WS模型 来 构 建, 在 该 模 型 中 分 别 令 重 连 概 率p
为0 , 0 1 0 1 , 1 即可 得到 上述3 种 网 络. 无标 度 网 络则
采用Ba ra bsi 和Al be rt
[ 1 0 ]
提出 的BA模型 构建. 网络 中的每 一个 节点 都代 表一 个参 与博 弈的 个 体, 这 些节 点只 和与 自 己 有 直 接连 接 的 邻 居 节 点相 互作用. 个 体可 以记 住 与 每 个 邻 居最 近 3 轮 的 博弈 历史. 用 数字 1 表示 合 作, 数 字0 表 示 背 叛, 可 以用 一个6 位 的 比 特串 来 表 示最 近3 轮博 弈 的 情况. 例
如 H i j = 1 0 0 1 1 1 表 示 i 节点 与 j 节 点最 近3 轮 的博弈
历史为: i 合 作, j 背 叛; i 背 叛, j 合 作; i 合 作, j 合 作. 3 轮博 弈 可能 的 历 史记 忆 共有6 4 种, 即0 0 0 0 0 0 ,
0 0 0 0 0 1 , , , 1 1 1 1 1 1 . 用一 个 6 4 位 的 比 特 串 表 示 个体
针对 不同 的博弈 历 史 所采 取 的 策 略. 这 个 比 特 串可 以看 成包 含6 4 个等 位基 因的 基因 组, 这 些等 位 基因 按其 所处 的位置 从0 到6 3 用十 进制 数 字编 号, 代表 6 4 种可 能的 历史 记忆. 每个 等位 基 因取 值 为1 或0 , 代表 相对 于该历 史记 忆所 采取 的策 略是 合作 还是 背 叛. 例 如, 节 点i 的 基 因 组 为 G i = 1 0 1 1 0 0 1 1 , , 其 含 义如 下: 0 号基 因 取 值 为1 , 表示 如 果 和某 邻 居 的博 弈历 史为0 0 0 0 0 0 , 则下 一步 对该 邻居 采取 合作 策略; 1 号 基 因取 值 为0 , 表 示如 果 历 史记 忆 为0 0 0 0 0 1 , 则 下一 步采 取背叛 策略; , ,
具体模 拟步 骤 如 下: 初 始 群体 中 个 体 的 每 一位 等位 基因 随机 赋值 为1 或0 , 前3 轮 博弈 随机 采取合 作或背 叛的 策略, 然 后 每 个 个 体根 据 自 己 的 基 因组 和博弈 历史 与 所 有 的 邻 居 进 行 n 轮 重 复 囚 徒 困 境 博弈. 博弈 后将 所得 的总 收益 对邻 居数 目( 即 节点 的 度) 求 平均 作为 该个 体 的 适 应 度. 对 每 一 个节 点, 以 正比 于适 应度的 概率 在其 邻居( 包 含该 节点本 身) 中 选取 两个 个体作 为 父 代, 父 代 基因 组 以 一 定 的 概率 经过交 叉重 组 和 变 异 产 生 两 个 子 代 基 因 组( 图1 ) , 用其 中之 一取代 该节 点的 基因 组.
图1 基 因 重 组 和 变 异 示 意图
模拟 参数 选取 如下: 所构 建的 网 络包 含1 0 0 0 个 节点, 节 点平 均度 为6 . 囚徒 困 境博 弈 的 支付 矩 阵 值
取为R = 1 , T = b R , b = 1 ) 2 , S = 0 , P = 0 1 1 . 参数 b
= T P R 表示 当乙 个 体采 取 合 作策 略 时, 甲 个 体 采 取 背叛 策略 所获 得的 收益 与采 取合 作策 略所 获得 的收 益之 比. b 值表征 背 叛 的 诱 惑 力, 当b 值 增 大 时, 背 叛的 个体 将可 能获 得 更 大 的 收益, 因此 背 叛 行 为 对 个体 将具 有更 大的 吸引 力. 我们 取 b 值范 围 在1 ) 2 之间, 用以 考察 系 统中 个 体 博 弈 策 略模 式 的 变 化 情 况. 模 拟 中, 交 叉 重 组 概 率 取 为 0 1 7 , 变 异 概 率 为 0 1 0 0 1 . 每 个个 体 每 一 代 都 与 邻 居 进 行1 0 0 轮 博 弈. 在需 要求 平均 值时, 则对 于4 种 不 同拓 扑 结 构 网 络 的每 一个b 值, 都 取1 0 0 个网 络样 本, 在每 一网 络样 本中 模拟1 1 0 0 代 进 化, 取 后1 0 0 代 求 各 种 平 均 值. 然后, 再将 该平 均 值对 样 本 数 求 平 均得 到 最 后 的 数 据点.
3 1 模拟结果及讨论
3 1 1 1 合作 频率
合作 频率 定义 为在 所有 个体 的总 博弈 次数 中采 取合 作 策 略的 比 例. 图2 是4 种网 络 中 合作 频 率 随 遗传 世代 变化 的关 系. 由 图2 可见, 随着 群体 的遗 传 进化, 不 同网 络中 的个体 合作 频率 都迅 速上 升, 很快 就达 到很 高的 合作 水 平, 即 经 过 遗 传进 化 之 后 系 统
中的 绝大 部分个 体都 采取 合作 的策 略.
图2 b = 1 1 5 时4 种 网 络 中 合 作 频 率 随 遗 传 世 代 的 变 化
图3 是进 化1 0 0 0 代后4 种 网络 的合作 频率 与b
值的 关系. 从图3 可以 看出, 小世 界网 络中 的合 作频 率高 于随 机网络 和 无 标度 网 络, 而 规 则 网 络 的 合作 频率相 对要 低 些. 与 文 献[ 1 2 ] 中 采 用 的 无 记 忆 模型 比较, 对于 无标 度网 络, 两 种模 型都 得到 很高 的合 作 频率, 而对 于规 则网 络, 则 由我 们的 模型 得到 的合 作 频率 远高 于无记 忆模 型.
图3 4 种 网 络 中 合 作 频 率 与b 值 的 关 系
3 1 2 1 基因 频率
我 们考 察 演 化1 0 0 0 代 后 网 络 中 个 体 的 基 因分 布情况, 以 研究 系统 通 过 遗 传 进化 出 何 种 机 制 促使 复杂 网络 中产生 高合 作率 的群 体. 为此, 统计 基因 组 中各 个位 置上值 为1 的等位 基因 在群 体中 出现 的频 率, 即
p k =
6
i G i kP N ,其中k 是 基 因编 号, G i k 表 示 个体 i 编号 为 k 的 基因 值, N 是 网 络 节 点 数. 图4 ( a ) 和( b) 给 出 了 b = 1 1 2
和 b = 1 1 9时的 p k 值. 由图4 ( a ) , ( b) 可见, 经过1 0 0 0
个世 代的 遗传 进化 之 后, 几 种 不 同 拓扑 结 构 的 网 络 中都 演化 出了 类似 的 行 为 模 式. 为 了更 清 楚 地 显 示 模式 的 共同 特 征, 把p k 值对4 种网 络 求 平 均, 得 到 图4 ( c ) , ( d ) .
从图4 ( a ) , ( c ) 可以 看出, 0 , 1 5 , 3 1 , 4 7 , 6 3 号 基因
频率 具有 正峰 值, 说明 群 体 对 相 应 的记 忆 倾 向 于 采 取合 作策 略. 从图4 ( a ) , ( c ) 还 可 以 看 出, 4 2 号 基 因 及2 1 号 基因 具有 负峰 值, 表 示群 体对 于这 两种 记 忆 倾向 于采 取背 叛的 策略. 我们 发现, 群 体演 化出 的这 种模 式能 够 促 进 合作 行 为 的 产 生 和 持 续. 0 号 基 因 对应 的历 史记 忆 为0 0 0 0 0 0 , 即 双 方 连 续3 次 互 相 背 叛. 群体 中大 部分 个体的0 号基 因 值 为1 , 说 明 当 连 续互 相背 叛使 得双 方 都 只 能 获取 低 收 益 的 情 况 下, 这些 个体 将会 尝试 与 对 方 合 作, 从 而跳 出 互 相 背 叛 的循 环. 因 此该 模 式能 够 激 发 群 体 中合 作 行 为 的 产
生. 1 5 , 3 1 , 4 7 号 基 因 对 应 的 记 忆 分 别 为 0 0 1 1 1 1 ,
0 1 1 1 1 1 , 1 0 1 1 1 1 . 这 些位 置 上 的 基 因 频率 具 有 正 峰 值
意味 着只 要有 连续 两 次 成 功 的互 相 合 作 历 史, 个 体 就倾 向于 继续 加强 合 作 关 系. 对 应 于 连 续3 次 合 作
的6 3 号 基因1 1 1 1 1 1 , 几乎 所有 的个 体都采 取合 作 策
略, 使得 该基 因频 率呈现 极高 的正 峰值. 这 说明 当较 稳定 的互 相合 作关 系 已 经 建 立起 来 之 后, 几 乎 所 有 的个 体都 倾向 于继 续维 持这 种关 系.
此外, 群 体还 演化 出 一 种 对 背 叛者 进 行 惩 罚 和 报复 的 模 式, 表现 在 4 2 号 基 因 频 率具 有 负 峰 值. 该 基因 对应 于记 忆1 0 1 0 1 0 , 即 如 果 个 体 连 续3 次 合 作 而对 方总 是背 叛情 况 下, 则 该 个 体 下一 步 将 不 再 合 作, 转变 为背 叛施 以报复. 这 种模 式使 得网 络中 背叛 的个 体无 法长 期对 合 作 者 进 行剥 削, 因 此 不 容 易 侵 入一 个由 合作 者组 成的 团簇 中.
上述 几种 基因 模式 的相 互作 用形 成了 一种 自组 织的 合作 机制. 这 种机 制 既 能 激 发 网络 中 合 作 行 为 的产 生, 又能 不断 加强和 维持 已经 建立 的合 作关 系, 同时 还能 报复 和惩 罚不 愿合 作的 个体. 因此, 能 够在 复杂 网络 中演 化出 如图2 和图3 所示 的具 有高 度 合 作率 的群 体.
除此 之外, 图4 还 显 示 出 一 个 有 趣 的 模 式, 即 2 1 号基 因 呈 现 负 峰 值. 该 基 因 对 应 于 记 忆 0 1 0 1 0 1 , 即个 体连 续背 叛而 对方 总 是 合作. 网络 中 大 约7 0 % 的个 体对 这种 情况 倾 向 于 继 续背 叛 以 获 取 高 收 益, 表现 出一 种/ 贪便 宜0 和/ 欺负 老实 人0 的倾 向.
图4 ( b) , ( d ) 是 b = 1 1 9时 群 体 演 化 出 的 模 式.
图4 基 因 频 率 模 式 ( a ) b = 1 1 2 时4 种 网 络 中 的 基 因 频 率, ( b) b = 11 9时4 种 网 络 中 的 基 因 频 率, ( c ) b = 11 2 时 基 因 频 率 对4 种 网 络 求 平 均, ( d ) b = 11 9时 基 因 频 率 对4 种 网 络 求 平 均
由图4 ( b) , ( d ) 可 见, 当b 值即 背 叛与 合 作的 收 益比
增大 时, 总 体基 因频 率沿 负方 向略 有移 动, 一 些基 因 模式消 失, 另 一 些 基 因 模 式 开 始 出 现. 但0 , 1 5 , 2 1 ,
3 1 , 4 2 , 6 3 号基 因的 基 本 模 式仍 然 保 持 不 变. 图5 给
出了 几种 典型的 基因 频率 随 b 值的 变化 曲线.
由图4 ( c ) , ( d ) 及 图5 可 以 看 出, 当 b 值 增 大
时, 个体 对 合 作 者 的 要 求 开 始 变 得/ 苛 刻0 . 4 7 号 基
因1 0 1 1 1 1 峰 值消 失, 说明 个体 不再 倾 向于 原 谅 对方
的偶尔 背 叛. 8 号 基 因0 0 1 0 0 0 , 3 2 号 基 因1 0 0 0 0 0 开 始出现 负峰 值, 说明 当 个 体 尝 试与 相 互 背 叛 的 对手 合作 却没 有得到 对 方 的回 报 时, 个 体 将 放 弃 合 作的 尝试 而报 之以背 叛的 策略.
图5 还表 明, 当b 值较 大时, 还 产生 了一 种两个 博弈个 体交 替 作 为 背 叛 者 和 合 作 者 的 模 式, 即0 1 ,
1 0 , 0 1 , 1 0 , , 的 模 式. 具 体 表 现 在2 5 号 基 因0 1 1 0 0 1
开始 出现 正峰值, 而3 8号 基 因1 0 0 1 1 0 出 现 负峰 值. 原因 是具 有这种 交替 模式 的两 个个 体每 一轮 博弈 的 平均收 益为( b + 0 1 1 ) P 2 , 而 互 相 合 作 的 两 个 个 体每 一轮 的收 益为1 , 因 此当b 增 大时, 交 替 模式 的 收益
开始 接近 甚至 超过 互 相 合 作 的收 益, 从 而 使 得 这 种 基因 模式 能够 通过 选择 在群 体中 扩散.
比较 图5 不 同网 络 中6 3 号 基 因 随 b 值 的 变 化 关系 曲线, 可以 发现: 对 于 小世 界 网 络, 6 3 号 基 因 频 率基 本 不随 b 值 增大 而 改变, 因 此 这种 网 络中 演 化 出的 合作 关系 最为 稳 定. 而 规 则 网 络中 的 个 体 则 对 b 值较 为敏 感, 一 旦b 值 增大, 规则 网络 中很 快就 出 现一 部分 自私 的背 叛者 对合 作者 进行 剥削 以获 得高 收益. 随 机网 络和 无标度 网络 则介 于两 者之 间. 这可 以解 释图3 所示 的 结 果: 小 世 界 网 络中 的 合 作 率 最 高, 其次 是随 机网 络和无 标度 网络, 规 则网 络相 对于 其他3 种网 络合 作率 最低.
3 1 3 1 与均 匀混 合群 体演 化结 果的 比较
文献[ 1 4 ] 研究 了基 于遗 传算 法的 重复 囚徒 困 境
博弈 策略 在均 匀混 合群 体中 演化 的结 果, 作 者发 现, 均匀 混合 群体 中可 以 演 化 出 如 下5 种 行 为 模 式: 个
体对2 7 号基 因0 1 1 0 1 1 , 4 7 号 基因1 0 1 1 1 1 和6 3 号 基
因1 1 1 1 1 1 倾 向 于 采 取 合 作 策 略, 而 对 0 号 基 因
图5 4 种 网 络 中 基 因 频 率 随b 值 的 变 化 关 系 ( a ) 小 世 界 网 络, ( b) 随 机 网 络, ( c ) 无 标 度 网 络, ( d ) 规 则 网 络
0 0 0 0 0 0 和6 2 号 基 因1 1 1 1 1 0 采 取 背 叛 策 略. 与 本 文
在复 杂网 络中得 到 的 结果 比 较, 我 们 发 现 两 种 模型
对1 1 1 1 1 1 的 记忆 都采 取合 作的 策 略, 说明 两 种 群体
中的 个体 都倾向 于 维 持连 续 的 合 作. 两 者 最 大 的区 别在 于对0 号基 因0 0 0 0 0 0 的 反 应: 复 杂网 络 中 的群 体倾 向于 合作, 而均 匀混 合群 体则 倾向 于背叛. 这 说 明复 杂网 络中的 群体 能够 在连 续互 相背 叛之 后尝 试 与对 方合 作, 从 而更 容易 激发 合作 行为 的产生; 而 均 匀混 合群 体一旦 落 入 互相 背 叛 的 恶 性 循 环, 则 很难 从中 跳 出. 另外, 复杂 网 络 中的 群 体 还演 化 出1 5 号
基因0 0 1 1 1 1 , 3 1 号 基因 0 1 1 1 1 1 频 率 的 正 峰 值 模 式,
使得 个体 之间的 合 作 关系 能 够 不 断 加 强, 因 此 复杂 网络 中能 够演化 出比 均匀 混合 群体 具有 更高 合作 率 的群 体. 此 外, 复 杂网 络中 合作 的个 体对 于背 叛者 的 报复显 得更 为/ 宽容0 一些, 表 现在 均 匀 混 合 群 体演 化出 的是 一报还 一报 的 策略, 即 对1 1 1 1 1 0 的 记 忆采 取背叛 的策 略, 而复 杂 网 络则 演 化 出/ 三 报 还 一 报0
的策 略, 即 对1 0 1 0 1 0 的记 忆采 取背叛 策略.
我们 的模型 综合 了无 记忆 模型 的网 络结 构特 征 及均 匀混 合群体 模 型 的记 忆 效 应, 这 两 方 面 的 因素
共同 决定 了这 样的 群 体 能 够 演化 出 更 高 的 合 作 率. 一方 面, 处 于网 络 中的 个 体 能 够 形 成由 合 作 者 组 成 的团 簇, 团 簇中 的 个体 通 过 互 相 合 作将 获 得 比 互 相 背叛 的个 体更 高的 收益
[ 4 , 1 2 ]
. 另 一 方 面, 记忆 效 应 使 得个 体能 够识 别合 作 和 不 合 作的 个 体, 从 而 有 针 对 性地 与合 作者 合作, 对背 叛者 进行 报复. 使 得背 叛的 自私 个体 无法 侵入 由 合 作 者 组成 的 团 簇 中, 因 此 无 法通 过剥 削合 作者 获 取 额 外 的高 收 益. 两 方 面 因 素 的共 同作 用使 得合 作的 个体 比背 叛的 个体 具有 更高 的适 应度. 因 此通 过自然 选择 的优 胜劣 汰机 制, 即使 在b 值 较 大的 情 况下, 合 作 行为 仍 然能 够 在网 络 中 蔓延 开来 并最 终占 据主 导地 位.
4 1 结 论
本文 利用 遗传 算法 研究 复杂 网络 中重 复囚 徒困 境博 弈策 略的 演化. 研究 结果 表明: 在 自然 选择 的压 力下, 面临 囚徒 困 境局 面 的 生 物 个 体追 求 自 身 利 益 最大 化的 结果, 并 非必然 导致 个体 的自 私行 为. 在我 们的 模型 中, 网 络 结构 和 记 忆 效 应 两方 面 的 因 素 决
定了 合作 行为能 够通 过自 然选 择从 最初 纯粹 的自 私 机制中 进化 而来. 处 于 复 杂 网 络中 与 其 直 接 邻 居进 行重 复囚 徒困境 博 弈 的具 有 记 忆 能 力 的 个体, 在经 过基因 的复 制、重组 、变异 和 选 择 之 后, 能 够 自 然地 进化出 一种 促 进 合 作 的 行 为 模 式: 0 号 基 因 模 式 能 够激 发 合 作 行 为 从 无 到有, 1 5 号 和3 1 号 等 基 因模 式促使 新建 立的 合作 关系 得 到 进 一步 的 加 强, 而6 3 号基 因模 式则能 够维 持持 续的 合作 行为. 另外, 系 统
不仅 演化 出促 进合 作的 行为 模式, 还演 化出4 2 号 基 因模 式对 背叛 个体 进 行 惩 罚 和报 复, 使 得 背 叛 个 体 无法 长期 入侵 合作 者 群 体, 保 证 合 作关 系 不 致 遭 受 破坏. 复杂 网络 中 演化 出 的 这 几 种 基因 模 式 的 相 互 作用 构成 了一 种自 组 织 的 合 作机 制, 能 够 促 使 网 络 中进 化出 比无 记忆 模型 和均 匀混 合群 体模 型具 有更 高合 作率 的群 体.
[ 1 ] Ma yn a rd S J, Pri c e G R 1 97 3 N a t u r e 2 4 6 1 5
[ 2 ] Gi n t i s H 2 0 0 0 G a m e T h e o r y E v o l v i n g ( Pri n c e ton : Pri n c e ton Un i ve rsi ty Pre ss)
[ 3 ] Ax e l rod R, Ha m i l ton W D 1 981 S c i e n c e 2 2 1 1 3 90 [ 4 ] Na w a k M A, Ma y R M 1 992 N a t u r e 3 5 9 82 6
[ 5 ] Al be rt R, Ba ra bsi A I 2 0 0 2 R e v . M o d . P h y s . 7 4 4 7
[ 6 ] Ne w m a n M E 2 0 0 3 S I AM R e v . 4 5 1 6 7
[ 7 ] Li Y, Li u Y, Sha n X M, Re n Y, Ji a o J, Qi u B 2 0 0 5 Ch i n . P h y s . 1 4 2 1 5 3
[ 8] Li J, Wa n g B H, Ji a n g P Q, Zhou T, Wa n g W X 2 0 0 6 Ac t a P h y s . S i n . 5 5 4 0 5 1 ( i n Chin e se ) [ 李 季 、汪 秉 宏 、蒋 品 群 、周 涛 、 王 文 旭2 0 0 6 物 理 学 报5 5 4 0 5 1 ]
[ 9] Wa tts D J, Stroga tz S H 1 998 N a t u r e 3 9 3 4 4 0
[ 1 0 ] Ba ra bsi A I, Al be rt R 1 999 S c i e n c e 2 8 6 5 0 9
[ 1 1 ] Li e be rm a n E , Ha u e rt C, Na w a k M A 2 0 0 5 N a t u r e 4 3 3 3 1 2 [ 1 2 ] Sa n tos F C, Pa c he c o J M 2 0 0 5 P h y s . R e v . Le t t . 9 5 0 981 0 4 [ 1 3 ] Ohtsu ki H, Ha u e rt C, Li e be rm a n E , Na w a k M A 2 0 0 6 N a t u r e 4 4 1 5 0 2 [ 1 4 ] Ax e l rod R 1 987 G e n e t i c Al g o r i t h m s a n d S i m u l a t i n g An n e a l i n g
( Lon d on : Pi tm a n ) p3 2
[ 1 5 ] Wi l ki n son G S 1 984 N a t u r e 3 0 8 1 84
[ 1 6 ] Cl u tton2 Broc k T H, O. Ri a i n M J, Brothe rton P N M, Ga yn or D, Ka n sky R, Gri ffi n A S, Ma n se r M 1 999 S c i e n c e 2 8 4 1 6 4 0 [ 1 7 ] Gol d be rg D E 1 989 G e n e t i c Al g o r i t h m s i n S e a r c h , Op t i m i za t i o n ,
a n d M a c h i n e Le a r n i n g ( Ma ssa c hu se tt s: Ad d i son2 We sl e y)
E v o l u t i o n o f s t r a t e g i e s b a s e d o n g e n e t i c a l g o r i t h m i n t h e
i t e r a t e d p r i s o n e r . s d i l e m m a o n c o m p l e x n e t w o r k s
*Li n Ha i Wu Che n 2 Xu
( I n s t i t u t e o f T h e o r e t i c a l P h y s i c s a n d As t r o p h y s i c s , De p a r t m e n t o f P h y s i c s , Xi a m e n Un i v e r s i t y , Xi a m e n 3 6 1 0 0 5 , Ch i n a ) ( Re c e i ve d 1 6 Nove m be r 2 0 0 6 ; re vi se d m a n u sc ri pt re c e i ve d 5 Apri l 2 0 0 7 )
Abstra c t
Usi n g ge n e ti c a l gori thm , w e stu d i e d the e vol u ti on of stra te gi e s i n the i te ra te d pri son e r. s d i l e m m a on c om pl e x n e tw orks. It i s fou n d tha t the a ge n ts l oc a te d on c om pl e x n e tw orks c a n n a tu ra l l y d e ve l op som e se l f2 orga n i za ti on m e c ha n i c s of c oope ra ti on by ge n om e re prod u c ti on , re c om bi n a ti on , m u ta ti on a n d se l e c ti on , w hi c h c a n n ot on l y re su l t i n the e m e rge n c e of c oope ra ti on , bu t a l so stre n gthe n a n d su sta i n the pe rsi ste n t c oope ra ti on . At the sa m e ti m e , su c h m e c ha n i c s pu n i she s a n d ta ke s re ve n ge on d e fe c ti ve a ge n ts, l e a d i n g to a hi gh c oope ra ti on ra te on c om pl e x n e tw orks.
K e y w o r d s : c om pl e x n e tw ork, ge n e ti c a l gori thm , e vol u ti on a ry ga m e , c oope ra ti on P A C C : 0 1 7 5 , 0 5 6 5
* Proje c t su pporte d by the Na ti on a l Na tu ra l Sc i e n c e Fou n d a t i on for Di sti n gu i she d You n g Sc hol a rs of Chi n a ( Gra n t No. 1 0 2 2 5 4 2 0 ) .
Corre spon d i n g a u thor. E2 m a i l : c x w u @ x m u . e d u . c n
