Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 基于动态拓扑的空间演化博弈与群体行为分析 姚灿中 ，杨建梅 ＹＡＯ Ｃａｎｚｈｏｎｇ ．ＹＡＮＧ Ｊｉａｎｍｅｉ １．华南理工大学经济与贸易学院，广州５１０００６ ２．华南理工大学工商管理学院，广州５ １ ０６４０ １．Ｓｃｈｏｏｌ ｏｆ Ｅｃｏｎｏｍｉｃｓ ａｎｄ Ｃｏｍｍｅｒｃｅ，Ｓｏｕｔｈ Ｃｈｉｎａ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ，Ｇｕａｎｇｚｈｏｕ ５ １ ０００６，Ｃｈｉｎａ ２．Ｓｃｈｏｏｌ ｏｆ Ｂｕｓｉｎｅｓｓ Ａｄｍｉｎｉｓｔｒａｔｉｏｎ，Ｓｏｕｔｈ Ｃｈｉｎａ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ，Ｇｕａｎｇｚｈｏｕ ５ １ ０６４０，Ｃｈｉｎａ ＹＡＯ Ｃａｎｚｈｏｎｇ，ＹＡＮＧ Ｊｉａｎｍｅｉ．Ｓｐａｔｉａｌ ｅｖｏｌｕｔｉｏｎａｒｙ ｇａｍｅ ｂａｓｅｄ ｏｎ ｄｙｎａｍｉｃ ｔｏｐｏｌｏｇｙ ａｎｄ ａｎａｌｙｓｉｓ ｏｆ ｅｍｅｒｇｅｎｃｅ ｏｆ ｇｒｏｕｐ ｂｅ－ ｈａｖｉｏｒｓ．Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２０１２，４８（３）：２９－３１． Ａｂｓｔｒａｃｔ：Ｔｈｅ ｐａｐｅｒ ｉｎｖｅｓｔｉｇａｔｅｓ ｔｈｅ ｒｅｌａｔｉｏｎｓｈｉｐ ｂｅｔｗｅｅｎ ｔｈｅ ａｇｅｎｔｓ’ｓｔｒａｔｅｇｙ ｓｅｌｅｃｔｉｏｎ ａｎｄ ｔｈｅ ｅｍｅｒｇｅｎｃｙ ｏｆ ｔｈｅ ｓｙｓｔｅｍ ｆｅａｔｕｒｅ ｆｒｏｍ ｔｈｅ ｐｅｒｓｐｅｃｔｉｖｅ ｏｆ ｔｈｅ ｉｎｅｒｔｉａｌ ｃｈａｒａｃｔｅｒｉｓｔｉｃ ａｎｄ ｓｐａｃｅ ｇａｍｅ．Ａ ｓｐａｔｉａｌ ｅｖｏｌｕｔｉｏｎａｒｙ ｇａｍｅ ｍｏｄｅｌ ｂａｓｅｄ Ｏｉｌ ｃｈａｎｇｉｎｇ ｔｏｐｏｌｏｇｙ ｉｓ ｂｕｉｌｔ， ａｎｄ ｔｈｅ ｅｖｏｌｕｔｉｏｎ ｓｔａｂｉｌｉｔｙ ｓｔｒａｔｅｇｙ ｏｆ ｔｈｅ ｓｙｓｔｅｍ ｉｓ ａｎａｌｙｚｅｄ ｗｈｅｎ ｔｈｅ ａｇｅｎｔｓ ａｒｅ ｉｎ ｔｈｅ ｔｉｍｅ ｄｉｍｅｎｓｉｏｎ ｃｏｎｄｉｔｉｏｎ ｏｆ ｃｏｍｐｌｅｔｅ ｉｎｅｒｔｉａ ｗｉｔｈ ｎｏｔ ｃｏｍｐｌｅｔｅ ｉｎｅｒｔｉａ ｐｒｏｐｅｒｔｉｅｓ．Ｔｈｅ ｅｍｅｒｇｅｎｃｙ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｔｈｅ ｃｌｕｓｔｅｒｓ ａｒｅ ｓｔｕｄｉｅｄ ｂｙ ａｎａ１） ｚｉｎｇ ｔｈｅ ｓｔａｂｌｅ ｓｔｒａｔｅｇｙ．Ｆｕｒｔｈｅｒ， ｂａｓｅｄ ｏｎ ｔｈｅ ｔｉｍｅ ｅｖｏｌｕｔｉｏｎ ａｎｄ ｔｈｅ ｄｙｎａｍｉｃ ｔｏｐｏｌｏｇｙ ｓｐａｃｅ，ｍｉｎｏｒｉｙ ｔｇａｍｅ ｍｏｄｅｌ ｉｓ ｂｕｉｌｔ ａｎｄ ｔｈｅ ｒｅｌａｔｉｏｎｓｈｉｐ ｂｅｔｗｅｅｎ ｔｈｅ ａｇｅｎｔｓ’ｍｉ— ｃｒｏ－ｉｎｅｒｔｉａｌ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ａｎｄ ｓｙｓｔｅｍ ｅｖｏｌｕｔｉｏｎ ｕｎｄｅｒ ｔｈｅ ｎｅｇａｔｉｖｅ ｆｅｅｄｂａｃｋ ｍｅｃｈａｎｉｓｍ ｉｓ ａｎａｌｙｚｅｄ． Ｋｅｙ ｗｏｒｄｓ：ｇｒｏｕｐ ｂｅｈａｖｉｏｒｓ；ｓｐａｔｉａｌ ｅｖｏｌｕｔｉｏｎａｒｙ ｇａｍｅ；ｅｍｅｒｇｅｎｃｙ 摘要：从惯性特征与空间博弈的角度探讨智能体的策略选择与系统涌现特征的关系。构建拓扑结构时刻变化的空间演化博弈 模型，分析了当智能体在具有完全惯性与不完全惯性这两种时间维度下系统演化的稳定策略，通过分析稳定策略探讨集群簇的 涌现、时间与空间分布等特征。进一步地，基于时刻演化的动态拓扑构建少数者空间博弈模型，分析在负反馈机制下智能体的微 观惯性特征与系统演化特征的关系。 关键词：群体行为；空间演化博弈；系统涌现 ＤＯＩ：１０．３７７８／ｊ．ｉｓｓｎ．１００２．８３３１．２０１２．０３．００８ 文章编号：１００２．８３３１（２０１２）０３．００２９．０３ 文献标识码：Ａ 中图分类号：ＴＰ３０１ １前言 群体行为在自然界和社会生活中都是一种常见的系统涌 现行为，如非洲草原上的动物迁徙、谣言的传播、游行示威、认 知趋同等，群体行为的不可预测性以及传播快速性对社会生 产与生活造成很大影响。举例来说，百度百科词条生产、以 Ｌｉｎｕｘ为代表的开放源代码运动、火星地图的绘制、维基百科 的编写等ｕ。 都是群体行为是有利的贡献，而挤兑、公地悲剧等 则是群体行为的不利表现。 讨了在二维格子上个体随机移动的形式，文献［８］从博弈的角 度结合复杂网络模型对群体合作涌现进行研究，并探讨了在 复杂网络结构上的空间博弈。而最早将空间结构与演化博弈 结合在一起，分析合作行为特征与个体关系的是哈佛大学的 Ｎｏｗａｋ等人 】，包括Ｎｏｗａｋ等人的研究在内，目前的研究在针对 空问结构方面有静态的如各种网络拓扑 、也包括有动态的分析 如随机迁徙 ，然而大部分的研究在设定空间结构的改变与个体 的策略改变之间的相关关系时往往是单向的，也即智能体之间 但是反之，智能体的这种 虽然群体行为已经成为生产和生活常见的现象之一，但 的互动关系受到来自环境因素的影响， 目前还缺乏一个关于群体行为的严格定义。许多学者探讨了 互动结果并不能改变空间拓扑结构（并进一步发生反馈作用）。本文将智能体的选择方向作为个体的策略集，智能体的 群体行为的特征，科赛［３１认为现场临时拼凑性与行为的奇特性 是群体行为的两个特征；朱力认为群体行为发生的主要包括 无结构性、感染性、狂热性、匿名性和失范性特征。对于群体 行为的形成研究有采用类似于传染病在人群中的传染过程的 传染论的观点ｔ４］，也有趋同论的观点（即认为群体行为的形成 是参加群体行为的人们已经共同具有了这样的趋势，以同样 的方式看待事物可以同样的方式行动 ）。 目前，基于计算机科学领域的Ａｇｅｎｔ建模方法为深刻挖掘 群体行为的内在机理提供了一个有利视角 ，其中，对个体决 运动取决于方向坐标因而智能体个体之间的互动拓扑是时刻 变化的，策略改变影响到拓扑空间结构，而空间结构反过来影 响到智能体的策略选择，将博弈结果出现的稳定均衡策略（如 果存在）作为系统涌现特征，进而通过时刻变化拓扑环境下的演 化博弈过程分析，探讨个体决策与群体行为涌现之问的关系。 ２动态拓扑下的演化博弈模型与群体迁徙行为 ２．１完全惯性下的迁徙行为分析 如图１所示为系统的初始状态，初始态中，智能体随机分 策与系统涌现特征的关系进行分析的文献较多，如文献［７］探 基金项日：国家自然科学基金（Ｎｏ．７１１７３０７６，７１１０３０４４）；教育部人文社会科学研究青年基金（Ｎｏ．１１ＹＪＣＺＨ２１１，０８ＪＣ７９００２３）；中央高校基本科研 业务费专项资金（Ｎｏ．２０１１ＺＢ００１１）；广东省普通高校人文社会科学研究基地重大项目（Ｎｏ．１０ＪＤＸＭ６３００５）；广东省哲学社会科学“十一 五”规划项目（Ｎｏ．０７ＧＯ０２）。 作者简介：姚灿中（１９８３一），男，博士，讲师，主要研究领域为：复杂系统、多智能体建模仿真；杨建梅（１９４６一），女，博士，博士生导师，教授。 Ｅ・ｍａｉｌ￣ｙａｏｃａｎｚｈｏｎｇ＠ｓｃｕｔ．ｅｄｕ．ｃｎ 收稿日期：２０１１－０７—２８；修回日期：２０１１－１Ｏ．１２；ＣＮＫＩ出版：２０１１—１１ １４；ｈｔｔｐ：／／ｗｗｗ．ｃｎｋｉ．ｎｅｔ／ｋｃｍｓ／ｄｅｔａｉｌ／１１．２１２７．ＴＥ２０１１１１１４．０９３８．００１．ｈｔｍｌ Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 布在二维空问上，在演化过程中智能体基于邻居的选择以及 自身固有惯性进行策略更新。在惯性保持一定的情况下，智 能体倾向于相信大多数邻居的选择具有一定的合理性，因而 ２．２不完全惯性Ｆ的迁徙行为分析 以上分析实际上均假设智能体具有完全惯性的特征，传 统的演化博弈侧重考虑近邻数量与近邻策略，在该模型中，近 保持与大多数邻居选择一致的策略。此外，在时间维度上智 能体会考虑到自身的历史选择，由于上一时间步的选择会具 邻数量、近邻策略、近邻结构都是时刻在变化。为了探讨个体 性质与群体迁徙行为的关系，将智能体的惯性设定为不是完 全继承，其他条件与２．１节设置完全相同。在不完全惯性模型 有一定的惯性，当周围的邻居的策略选择没有明显的倾ｒ口Ｊ或 者智能体本身无任何邻居时，智能体会出于限性而保持上一 时间步的策略。 中智能体在迁徙过程中以一定概率继承上个时间步的惯性。 仿真结果如图４～图６所示，图６与图３相类似，在初始阶段策 略呈随机分布，随着时问演化，策略选择或者平均运动方向为 ｛ ｌ，Ｙ＝Ｉ； ，＿１，ｙ＿－一１｝的人数在下降，而策略选择或者平均 运动方向为｛ ０，Ｙ＝Ｏ｝的人数在上升并且最终占据了系统中 绝大多数的比例，系统达到稳定状态（如图５所表示）。 对比图３与图６可以看出，系统达到稳定状态时的收敛速 度不同。从图３可知，选择｛ｊ，－０， ０｝策略的人数在完全惯性 模型中，当ｔ＝－１５０时系统基本达到稳定态，而在图６中，当ｔ＝２００ 时系统才基本达到稳定态，人数比例占绝对优势。为了更进 一智能体的策略集包含９个策略，９个不同策略分别度量了 智能体运动的平均方向，以 表示智能体沿着 轴的平均运动 方向，ｙ表示智能体沿着ｙ轴的平均运动方向，运动方向同时是 智能体的策略选择集合，通过该设置将智能体的策略集与拓 扑结构的改变联系起来。由于每个智能体在单个方向上具有 ３种状态即三种策略选择，即９种策略为｛ 一１， 一ｌ； 一１，Ｆ－－Ｏ； 一一１，ｙ＝１；Ｘ＝Ｏ， 一１；Ｘ＝Ｏ， ０；Ｘ＝Ｏ， １；Ｘ＝Ｉ， ｌ； １，Ｙ－－Ｏ； １，ｙ＝一ｌ｝。 图２显示了系统演化的稳定状态，从图２可以看出，系统 稳定时智能体群体形成少量的集群簇，在这些集群簇中，位于 中心的智能体由于邻域布满了智能体因而处于静止状态，不 再发生移动，而其他智能体由于邻域中大部分智能体倾向于 静止因而也保持静止状态。 图３中纵轴表示某种策略选择的具体人数，横轴表示时『日Ｊ 步长（图６、图９、图ｌＯ（ｃ）中的横轴与纵轴所表示含义与图３相 同），如果系统中大部分个体选择某个策略即代表了群体行为 步探讨智能体惯性的大小与群体涌现行为的关系，研究了 在更弱惯性下系统的演化情况，仿真结果如图７～图９所示。 图８结果与图５的仿真结果相类似，系统中具有智能体集群簇 的涌现，与图５不同的是系统稳定的时问，图９与图６的结果相 比系统稳定收敛的时间要较快，这是一个较为重要的现象，它 表明惯性不大的智能体群，在系统演化的过程中反而有可能 更快地达到稳定态，而惯性较大的智能体群体在决策过程中 唧籁 ５ ５ ４ ４ ３ ３ ２选择的一致性，由于方向表征智能体的某种特定策略，因而也 代表了群体策略选择的一致性。从图３可以看出，初始阶段， 策略是随机的，随着时间演化，策略选择或者平均运动方向为 ｛ １，Ｙ＝Ｉ｝的人数在下降，而策略选择或者平均运动方向为 由于反复比较自身与近邻的策略选择，从而耗费了太多的时 『日Ｊ并减缓了群体的收敛速度。 从图４～图９也说明，空问拥挤对智能体的策略选择施加 了一个外部影响，智能体在时间维度上的惯性可能会有不同， ５ ０ ５ ０ ５ ０ ５｛ ０，Ｙ＝Ｏ｝的人数在上升并且最终占据了系统中绝大多数的 比例，此时系统达到了稳定状态（如图２、图３所表示）。 与不具备空间特性的演化博弈相比，当策略选择基于多 数者原则时，空间演化博弈存在着一个空间拥挤临界，智能体 的策略选择受到空间制约，整个系统存在一个收敛极限。 但是外部空问的拥挤会导致智能体的策略偏向于某个策略， 特别是当个体选择是倾向于某种“大多数”选择的策略时。这 也解释了在现实生活中出现的一些较大规模的拥挤现象，现 实中的排队、交通拥挤等有的现象是由资源稀缺造成的，但是 应该看到个体选择的倾向性加剧了这种效率的损失。 时间步长 图１ 系统初始状态 图２系统演化的稳定态 图３群体行为的演化特征 时间步长 图４不完全惯性下系统的初始态（Ｐ＝Ｏ ５） 图５不完全惯性下系统的稳定态（户－＿Ｏ．５） 图６ 不完全惯性下群体行为的演化特征（￣－－ｏ，５） 姚灿中，杨建梅：基于动态拓扑的空间演化博弈与群体行为分析 Ｘ＝０＆ １ Ｘ＝０＆ 一ｌ Ｘ＝０＆Ｙ－０ ＝Ｉ＆ｙ＝１ ）（－１＆ｙ＿－一１ １＆Ｙ－－０ ． 一１＆ｙ－－Ｉ １＆Ｙ－－０ 一１＆ｙ＿－一１ 一０ ０．５ １ ０ １．５ ２ ０ ２．５ ３．０ ３．５ ４．０ ４．５ ５．０ 时间步长 图７不完全惯性下系统的初始态（Ｐ：ＯＬ２） 图８不完全惯性下系统的稳定态（Ｐ＝０．２） 图９ 不完全惯性下群体行为的演化特征（ｊＰ＝０．５） Ｘ＝０＆ｙ＿－Ｉ Ｘ－０＆ｙ＿－一ｌ Ｘ＝０＆ｙ＝Ｏ ｌ＆ｙ＿－１ ｌ＆ 一１ Ｘ＝Ｉ＆Ｙ－－０ ３（－－一１＆Ｙ＝Ｉ １＆ｙ＿－一１ １＆Ｙ＝０ 一０ １ ２ ３ ４ ５ ６ ７ ８ ９ 时间步长 （ａ）系统的初始态 （ｂ）系统演化终止态 图ｌＯ少数者博奔模型中系统群体行为的演化特征 （ｃ）群体行为演化特征 ３ 少数者博弈模型与群体迂徙行为 ５ ５ ４ ４ ３ ３ ２ ２１ Ｏ ５ Ｏ ５ Ｏ ５ Ｏ ５ ０ ５ ０ ５ 咖熟 卿瓤 ５ ５ ４ ４ ３ ３ ２ ２１关系。 １ Ｏ 少数者博弈模型是由Ｄ．Ｃｈａｌｌｅｔ与Ｙ．Ｃ．Ｚｈａｎｇ㈣在Ａｒｔｈｕｒ著 名的“酒吧模型”基础上提出来的，它能够有效刻画许多经济 物理现象，成为当前较为热门的一个博弈模型，国内许多学者 对少数者博弈在不同网络拓扑结构上进行相关研究ｕ”。将少 数者博弈模型放到了这个具有动态邻域拓扑结构并且策略与 行为具有一致性特征的二维拓扑结构上，对群体迁徙行为与 智能体的决策关系进行简单的模拟，仿真结果如图１Ｏ所示。 从图１０（ａ）与图１０（ｂ）可以看出，系统的初始态与终止态 ５ ０ ５ ０ ５ Ｏ ５ Ｏ ５ Ｏ ５ 实验结果表明，在空间拓扑变化的情况下，系统整体的特 征涌现不仅与内部协调机制有关，也受到系统本身结构的影 响；由于空间特性，大多数空间博弈的模型系统会出现集群簇 的效应；空问分布具有幂律特征，而时间维度上的惯性大小只 是影响系统的收敛速度；少数者空间博弈模型中由于存在负 反馈机制，空间分布没有太大变化，呈初始随机分布。 参考文献： ［１】Ｂｅｎｌｄｅｒ Ｙ．Ｃｏａｓｅ’ｓ ｐｅｎｇｕｉｎ［Ｊ］．Ｔｈｅ Ｙａｌｅ Ｌａｗ Ｊｏｕｒｎａｌ，２００２，１１２（３）： ３６９．４４６． 中智能体的分布非常类，均似呈随机形态，从图１０（Ｃ）中也可 看出，策略集合中的各个策略在系统演化过程中发展都较为 平均，并无哪个策略占绝对优势。与不具备空间特性的演化 博弈相比，如果策略选择基于少数者原则时，系统演化存在着 负反馈，智能体的策略选择与行为是跳跃式均衡。此外，基于 少数者博弈的空间演化使得系统不会出现拥挤现象，这对交 通拥堵、路径依赖等的改善治理具有启发性，也说明了内部决 策机制设置的重要性。 ［２】Ｂｅｎｋｌｅｒ Ｙ．Ｃｏｍｍｏｎｓ－ｂａｓｅｄ ｐｅｅｒ ｐｒｏｄｕｃｔｉｏｎ ａｎｄ ｖｉｒｔｕｒｅ［Ｊ］．ｈｅ Ｊｏｕｒ－Ｔ ｎａｌ ｏｆ Ｐｏｌｉｔｉｃａｌ Ｐｈｉｌｏｓｏｐｈｙ，２００６，１４（４）：３９４－４１９． ［３］李志强，胡晓峰，杨雪生，等虚拟环境中大规模群体行为建模研究 进展ｆＪ１＿计算机工程与应用，２００８，４４（８）：４５．４８． ［４］姚灿中，杨建梅．基于Ｍｕｌｔｉ．Ａｇｅｎｔ的复杂网络疾病传播仿真模型［Ｊ】． 计算机工程与应用，２０１０，４６（２０）：１２ １５． ［５】吴江，胡斌．信息化与群体行为互动的多智能体模拟［Ｊ］．系统工程 学报，２００９，２４（２）：２１８－２２５． ４结束语 系统涌现特征的出现既与内部选择机制有关，又与空间 结构特征相关，传统的以固定拓扑作为智能体空间维度上选 择参照的方法具有一定局限性，而以往较多的侧重于对智能 体时间维度上记忆长短的研究也缺乏考虑环境特征的影响。 ［６】杨志谋，司光亚，李志强，等．群体行为建模理论基础与建模方法研 究ｆＪ］．系统仿真学报，２００９，２１（１６）：４９２１—４９２５． ［７］Ｖａｉｎｓｔｅｉｎ Ｍ Ｈ，Ｓｉｌｖａ Ａ Ｔ Ｃ，Ａｒｅｎｚｏｎ Ｊ Ｊ．Ｄｏｅｓ ｍｏｂｉｌｉｔｙ ｄｅｃｒｅａｓｅ ｃｏｏｐｅｒａｔｉｏｎ？［Ｊ］－Ｊ Ｔｈｅｏｒ Ｂｉｏｌ，２００７，２４４：７２２－７２８． ［８］汪秉宏，杨涵新．人类的迁徙行为与社群合作之演化［Ｊ］．上海理工 大学学报，２０１ｌ，３３（１）：２４—２９． 【９］Ｎｏｗａｋ Ｍ Ａ，Ｍａｙ Ｒ Ｍ．Ｅｖｏｌｕｔｉｏｎａｒｙ ｇａｍｅｓ ａｎｄ ｓｐａｔｉａｌ ｃｈａｏｓ［Ｊ］． Ｎａｔｕｒｅ，１９９２，３５９（６３９８）：８２６．８２９． ［１０］Ｃｈａｌｌｅｔ Ｄ，Ｚｈａｎｇ Ｙ Ｃ．Ｅｍｅｒｇｅｎｃｅ ｏｆ ｃｏｏｐｅｒａｔｉｏｎ ａｎｄ ｏｒｇａｎｉｚａ— ｔｉｏｎ ｉｎ ａｎ ｅｖｏｌｕｔｉｏｎａｒｙ ｇａｍｅ［Ｊ］．Ｐｈｙｓｉｃａ Ａ，１９９７，２４６（３）：４０７—４１８． 本文采用惯性体现智能体的时间特征，采用智能体的飞行方 向作为策略集，从而构建了智能体在动态拓扑空间上进行博 弈的、记忆长度为０至ｌ之间的一个演化模型。通过模型本文 分别探讨了当智能体在具有完全惯性、不完全惯性以及少数 者博弈这几种情况下系统演化的稳定策略，并在几种情况下 进一步地分析智能体的微观陨性特征与系统宏观涌现特征的 【ｌ１】全宏俊，汪秉宏，杨伟松，等经纪人模仿在演化少数者博弈模型 中引入的自组织分离效应［Ｊ１．物理学报，２００２，５１（１２）：２６６７．２６７０．