《基于演化动力学的复杂网络上资源配置研究.doc》由会员分享，可在线阅读，更多相关《基于演化动力学的复杂网络上资源配置研究.doc（55页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、摘 要合作现象演化背后的机理是演化博弈论中的重要研究主题，众多基于不同博弈形式的演化框架的提出使得各种可能推动合作的机制被提出。以复杂网络为载体的演化动力学框架是对传统均匀混合群体模型的现实化拓展，这一引起广泛关注的理论模型进一步推动了对合作与公平演化的研究，对理解自然界合作行为的产生与推动人类社会发展均有重要意义。本文以复杂网络上的演化动力学为理论框架进行了不同种群结构上的资源分配行为，主要进行了以下研究：（1）基于现有演化博弈理论框架，综合各类博弈形式，选取最后通牒博弈为博弈模式，引入博弈矩阵转换，构建了两种不同的种群结构模型：一是带有边权重异质性的规则网络交互种群结构以及；二是带有度分布
2、异质性的随机网络交互种群结构模型。（2）通过C+语言环境对规则网络模型在不同异质性参数下的种群策略演化进行了计算机模拟仿真研究。研究结果表明，在规则网络上不同边之间存在适中的异质性时，种群演化表现出更加公平的资源分配倾向，同时完成了这一模型下基于微观个体层面的策略演化分析。（3）通过C+语言环境对随机网络模型在不同异质性参数下的种群策略演化进行了计算机模拟仿真研究。研究结果表明，在随机网络上度分布存在适中的异质性时，种群演化表现出更加公平的资源分配倾向。关键词：演化动力学，最后通牒博弈，复杂网络，公平性，异质性- I -本页为“6毕业论文Abstract（1页或2页）”，点击菜单“USTB本科
3、论文各部分”中的本部分菜单进行相应操作。本提示信息为非打印信息，可一直保留，不影响打印。Resource Allocation in Complex Networks with Evolutionary DynamicsAbstractThe mechanism behind the evolution of cooperative phenomena is an important research topic in evolutionary game theory. Many evolutionary frameworks based on different game forms hav
4、e been proposed, so various mechanisms that may promote cooperation have been proposed. The framework of evolutionary dynamics based on complex networks is a practical extension of the traditional uniform mixed population model. In this paper, the evolutionary dynamics on complex networks are used a
5、s the theoretical framework to carry out the resource allocation behaviors on different population structures, and the following studies are mainly conducted:(1) based on the existing evolutionary game theory framework, the author synthesizes all kinds of game forms, selects ultimatum game as the ga
6、me model, and introduces the game matrix transformation to construct two different population structure models.The second is the random network interaction population structure model with degree distribution heterogeneity.(2) a computer simulation study was conducted on the population strategy evolu
7、tion of the rule network model under different heterogeneous parameters through the C+ language. The results show that when there is moderate heterogeneity between the different edges of the rule network, the population evolution shows a more equitable tendency of resource allocation, and the strate
8、gy evolution analysis based on the micro individual level under this model is completed.(3) a computer simulation study was carried out on the population strategy evolution of the random network model under different heterogeneous parameters through the C+ language. The results show that when there
9、is moderate heterogeneity in the degree distribution of random networks, the population evolution shows a more equitable tendency of resource allocation.Key Words：evolutionary dynamics; the ultimatum game; complex networks; fairness; heterogeneity- IV -本页为“7毕业论文目录（1页或若干页）”，点击菜单“USTB本科论文各部分”中的本部分菜单进行
10、相应操作。本提示信息为非打印信息，可一直保留，不影响打印。目 录摘 要IAbstractIII插图清单VII附表清单IX1 引 言12 文献综述22.1 课题背景及研究意义22.2 复杂网络简介32.2.1 复杂网络概述32.2.2 复杂网络的性质32.3 演化博弈论简介52.3.1 经典博弈论52.3.2 演化博弈论62.4 合作演化与复杂网络上演化博弈研究进展72.5 主要研究内容93 基于演化动力学的复杂网络群体模型103.1 网络结构103.1.1 网络拓扑结构103.1.2 规则网络模型123.1.3 随机网络模型143.2 种群交互结构173.3 博弈交互范式183.4 异质性的引
11、入213.5 策略更新233.6 本章小结264 异质规则网络上的分配行为274.1 仿真描述274.2 仿真结果及分析284.2.1 平均指标及分析284.2.2 压缩策略空间与微观层面探索304.2.3 其他选择强度情形344.3 本章小结365 异质随机网络上的分配行为375.1 仿真描述375.2 仿真结果及分析385.3 本章小结406 小结41参考文献43在学取得成果45致 谢47- VI -本页为“8毕业论文图表清单页（可选，1页或若干页）”，点击菜单“USTB本科论文各部分”中的本部分菜单进行相应操作。本提示信息为非打印信息，可一直保留，不影响打印。插图清单图 2-1 不同领域
12、中的合作行为2图 2-2 七桥问题示意图3图 2-3 推动合作演化的五种机制7图 2-4 主要研究内容9图 3-1 不同拓扑结构网络模型10图 3-2 不同规则网络12图 3-3 带周期性边界的方格网络14图 3-4 WS小世界网络的构造15图 3-5 NW小世界网络的构造16图 3-6 不同交互结构上的群体17图 3-7 公平策略设置下的策略收益空间19图 3-8 武断策略设置下的策略收益空间19图 3-9 个体间的同步博弈20图 3-10 n=2时的带权边规则网络（局部）22图 3-11 生灭过程和灭生过程示意图23图 3-12 规则网络策略更新24图 3-13 随机网络策略更新25图 4
13、-1 规则网络上仿真流程示意图27图 4-2 异质规则网络上的演化平均策略（）29图 4-3 简化模型策略固定分布31图 4-4 简化模型下各策略固定次数分布图32图 4-5 三种异质性参数下策略演化快照33图 4-6 时规则网络上平均策略随变化34图 4-7 时规则网络上平均策略随变化35图 4-8 时规则网络上平均策略随变化35图 5-1 随机网络上仿真流程示意图37图 5-2 异质小世界网络上平均策略随重连概率变化图（）38图 5-3 时平均策略随变化39图 5-4 时平均策略随变化40图 5-5 时平均策略随变化40- VIII -本页为“9毕业论文注释说明清单页（可选，1页或若干页）
14、”，点击菜单“USTB本科论文各部分”中的本部分菜单进行相应操作。本提示信息为非打印信息，可一直保留，不影响打印。附表清单表 2-1 囚徒博弈收益矩阵 5表 2-2 猎鹿博弈收益矩阵6表 4-1 策略简化下的收益矩阵30- IX -本页为“10毕业论文正文页（若干页）”，点击菜单“USTB本科论文各部分”中的本部分菜单进行相应操作。本提示信息为非打印信息，可一直保留，不影响打印。1 引 言合作行为是自然界和人类社会中广泛存在的现象，对于种群进化与人类社会的发展有重要的推动作用。蚁群复杂的分工、供电系统的稳定运行、社交网络的信息传播等都蕴含着合作行为的涌现。以复杂网络为结构载体，以演化博弈为交互
15、描述的研究框架近年来受到广泛关注。复杂网络是刻画自然界、人类社会等个体间交互结构的重要理论模型，是研究合作演化的重要基体；演化博弈是经典博弈论与演化动力学的有机结合，可以描述群体中个体间的交互。在合作行为的出现与达尔文的进化学说相悖的情况下，相关学者广泛地开展了对合作演化底层机制的研究。空间结构的引入表明网络互惠复杂网络上的最后通牒博弈在演化博弈论中常被用来研究合作行为中公平性的演化。相关学者建立的自适应动力学框架描述了最后通牒博弈中的各类动力学特征，可以预测满足特定假设条件下的演化稳定策略，对解释公平性演化起到了推动作用。现有研究多在同质群体中展开，证明了中等变异率和中等选择强度下，自然选择
16、有利于公平的演化。不同种群更新规则与环境噪声的引入证明了随机性对公平演化具有促进作用。本文以复杂网络上的最后通牒博弈作为模型框架，对不同的网络引入个体异质性结构建成交互模型，利用C+程序语言进行蒙特卡洛实验仿真，进而研究不同情形下分配行为的特征以及异质性对公平行为演化的影响。2 文献综述2.1 课题背景及研究意义人类的合作行为如何发展是现存的重大科学问题之一1。如图2-1所示，在自然界与人类社会中，各物种、对象之间的合作现象均广泛存在。生态学的研究中，不同物种之间存在着互惠共生的生存模式，不同物种之间通过特有的合作方式，获取正常生存所需的资源；在电力系统中，各级供电厂、各处送电装置组成的电力网
17、络，也体现出各种一对多、多对多的合作结构；人类社会中充斥着的的各类商务合作行为、劳动合作行为同样昭示着合作行为的重要性。长期以来，人类合作一直是进化理论框架里的焦点，生物科学、经济学、心理研究学等领域的学者和研究人员都对合作的演化机制产生了极大的兴趣。 图 2-1 不同领域中的合作行为利他主义，即个体自身付出一定的代价，使得他人获利的行为，被解释为合作行为出现的原因。显而易见利他行为不利于自身获益的最大化，研究合作行为从本质上也是研究利他主义产生的机理。在近年来研究合作行为的历程中，一个重要的理论框架是基于复杂网络结构的演化博弈。传统博弈论中多样的博弈形式与演化动力学中各种更新规则的结合，使得
18、群体策略演化模型被抽象出来；空间结构的引入进一步增强了理论、仿真模型的现实性。公平性的演化机制又是合作问题中的一个重点，最后通牒博弈作为常用博弈形式被广泛运用到公平性的研究之中。理解合作行为背后的机理，洞悉公平行为出现的内因，对理解自然界物种进化、种群合作，人类社会稳定发展有着重要的启示意义；对复杂系统中的优化控制、环境反馈强化学习机制的改进有着巨大的推动作用。2.2 复杂网络简介2.2.1 复杂网络概述网络在数学上是图论的一部分，用于研究一些节点按照特定方式连接组成的多点系统。网络广泛存在于工业制造内、自然界物种之间、日常生活之中。热带雨林的植被分布、人体内错综复杂的神经元、日新月异的互联网
19、等等，网络在我们的世界中已随处可见。“Konigberg七桥问题”（图2-2）一般被视作最早的实际网络问题。该问题需要一条路线，能穿过每块陆地，且只经过每座桥一次，尽管这个问题后来被欧拉证明无解，但却因此推动了图论的发展。图 2-2 七桥问题示意图有关复杂网络上相关理论的研究开始以迅猛的趋势发展始于20世纪60年代。随机图理论的建立使得复杂网络系统性研究得到创立。ER随机网络这一模型2建立后，随着研究的深入，又有小世界网络、无标度网络等各类更加接近真实世界的网络模型被用于理论、实验分析。步入21世纪。复杂网络相关理论的研究也越来越受到各界学者们的关注，各类研究成果层出不穷。2.2.2 复杂网络
20、的性质网络拓扑结构多种多样，代表性的复杂网络模型有规则网络、小世界网络、随机网络、无标度网络等。复杂图的平均路径长度、网络聚类性质、网络中节点的度函数满足的规律等是研究复杂网络时需要重点关注的几个基本概念3,4。其相关从定义如下：（1）平均路径长度在一给定网络上，两个不同节点和之间可能存在多条或不存在路径，在所有存在的路径中，如果有一条历边最少，穿过顶点对少，则称为最短路径，这一路径的长度一般记作。则表示上述两点之间不存在连通的路径。顾名思义，最大路径指的是给定网络上所有中的最大值，记作，在个节点的网络上，其可以表示为 （2-1）一般用表示平均路径长度，其定义为所有节点之间距离的平均值，可以表
21、示为 （2-2）（2）聚类系数在不同节点表示性质的网络关系中，跨节点之间也可能存在着连通性，即所谓的聚类性质。考虑一个具有条边的节点，该节点的聚类系数用以下表达式进行计算 （2-3）其中，的含义是个邻居之间存在的连边数量。规则网络一般指二维方格等任意节点都具有相同个数近邻节点的网络，而随机网络则是两两节点间以一定的概率进行连边。典型的随机网络5有如下几种：（1）ER随机图。ER随机图具有聚类系数小、平均距离小等性质。（2）小世界网络。Watt和Strogatz二人通过随机重连的方法建立了小世界网络模型6，这种网络具有的特征是大聚类系数、小最短距离。（3）无标度网络。无标度网络7则是一种网络中度
22、分度满足幂律的特殊结构。表现在网络中只有少数节点具有密集的度分布，而大多数节点处在网络中的边缘区。网络上的群体行为研究一般有以下几个类型的指标8,9：（1）个体行为评价指标。节点的度及其分布在表征上有代表性作用，其一般可以对网络结构的局部特征进行相关描述，节点的中心性则可以体现节点在网络中的位置重要性和其他节点对其的依赖性。行为波动性是描述个体在演化过程中改变策略的频繁程度，行为扩散度则可以描述网络中某个节点的决策传播能力。（2）群体行为评价指标。连接紧密性从群体整体视角出发，衡量网络中节点间的分布疏密；模块化度可以刻画网络社区结构的相关性质，用来方便研究人员进行网络的结构区划；（3）群体间行
23、为指标。这一刻画指标一般用来描述多个网络结构之间的群体行为相关性，在网络构成的社会组成中研究观点、策略如何演化。网络结构分析的发展历经规则到随机，一维至多维，对真实世界的结构机理研究都有一定影响。2.3 演化博弈论简介2.3.1 经典博弈论博弈论最初是在经济学上建立起来的，用以研究决策个体的行动战略相互发生直接作用时，各种战略决策问题以及战略策略之间的稳定平衡问题。在参与人进行决策的过程中，一方的行为规范会受到其他参与人的影响，同时又会反馈与其他决策主体上，对其行为规范造成影响。经典博弈论的研究有助于预测均衡局面，制定科学战略。从各类经济寡头竞争模型到纳什均衡的提出，博弈论的研究被逐渐范式化。
24、经典博弈论中的基本要素，如行动、参与人、策略、信息透明度、收益、结果、均衡等均在研究中得到充分分析。随着研究深入，博弈论也被引入军事、政治、管理等各类其他领域，得到重要应用。表 2-2 囚徒博弈收益矩阵收益矩阵囚徒2选择合作囚徒2选择背叛囚徒1选择合作-1，-1-10，0囚徒1选择背叛0，-10-5，-5常见的博弈形式有猎鹿博弈、囚徒困境博弈、公共品博弈、雪堆博弈和最后通牒博弈10等等。利用收益矩阵的形式可以直观地看出博弈参与人采取不同策略时得到的收益大小。如表2-1所示，在囚徒困境博弈中，如果两名囚犯保持沉默（合作），双方供述虚假口供，则都可以使入狱时间降到最低；如果一方保持沉默，另一方坦白
25、（背叛），那么坦白的一方由于立功可以免除刑罚，保持沉默的一方由于被供出，遭受更高的入狱年限。猎鹿博弈描述的是在一片森林中，有两名猎人每天打猎为生，但由于个人能力有限，单独行动每人只能捕获一只兔子，每只兔子可以使用两天，如果合作行动则可以捕获一头鹿，一头鹿可供二人食用五天。此博弈的收益矩阵如表2-2所示。表 3-2 猎鹿博弈收益矩阵收益矩阵猎人2选择猎鹿猎人2选择猎兔猎人1选择猎鹿5，50，2猎人1选择猎兔2，01，1公共品博弈不同于以上两种博弈形式，其参与人数目大于2，是一种多人博弈模型。其具体内容是，名博弈参与人面对一个公共财产池，每名参与人拥有同样的初始资金，其可以选择将其投入或不投入财产
26、池中，投入的资金会以系数扩增并平均分配给所有博弈参与人。例如，如果群体中存在个选择投放资金，那么投入者将会获得收益，那些不选择投放资金的参与人将获得收益。尽管每名参与人都选择投放资金的情况下群体能够获得最大收益，但是，出于个人理性，群体会陷入都不投放的博弈困境。最后通牒博弈是一种博弈双方按照一定比例分配一笔资金的非零和博弈11。在这种博弈中，博弈双方分别被称作提议者和响应者。面对一批可分配资源，提议者拟定一种分配比例的方案，如果响应者接受其提所提出的分配比例安排，则双方按分配比例获得资源作为收益，如果响应者不接受该拟定的比例，则双方均无收益。不同的博弈形式被用于研究合作行为中的不同方面，如囚徒
27、困境博弈、雪堆博弈常用于合作演化研究，最后通牒博弈则常被用于研究群体中公平行为的产生。2.3.2 演化博弈论演化动力学是用于描述特定群体演化过程的理论分析工具，其包括复制、选择、变异等群体策略演化过程中的基本要素12。传统博弈论与演化动力学的有机结合，形成了演化博弈论，这一理论完成了从传统博弈论中的个体完全理性假设向现实中个体有限理性的过渡，使得该理论可以用来分析、预测给定种群条件下的策略演化动态。复杂网络上的演化博弈理论的研究可以分为理论研究、仿真研究、实证研究三种13。理论研究通常从复杂网络理论出发，利用数学理论工具研究种群演化过程中的各类动力学；实证研究则是通过社区或互联网等渠道组织一定
28、数量的被试，进行行为实验，进而统计分析得到结论；而仿真研究则是建立交互、演化模型，利用蒙特卡洛方法进行计算机程序仿真。由于在复杂网络上的模型中，种群里每个个体的策略、收益等状态与网络拓扑结构相耦合使得理论分析十分困难，所以仿真研究成为近年来受到广泛关注的研究手段。通过不同种群结构、博弈形式、策略更新动力学的组合，可以研究网络上的合作演化特性14。演化动力学中的一个关注焦点是表现型，即策略在演化过程中的固定。准种方程15的提出，使得常数适应度空间中无限数目种群的突变和选择过程得到数学描述，其形式为 （2-4）其中，表示策略个体的频率随时间的倒数，为策略个体的适应度，为从到的突变概率，则表示平均适
29、应度，这一方程揭示了在种群中不同策略个体如何依据适应度、繁殖速率随时间演化。2.4 合作演化与复杂网络上演化博弈研究进展合作演化的机理是演化博弈研究的一个重要主题。近年来，许多不同的机制和特性被提出来试图解释这一论题，比如Nowak等人提出的亲缘选择、直接互惠、间接互惠、网络互惠、群组选择16等机制（图2-3）。图 2-3 推动合作演化的五种机制网络结构被引入到演化博弈当中，从Nowak和May二人17开创性地研究网络结构对合作涌现的影响开始。他们将空间结构促进合作行为的原因归纳为空间互惠，即上文提到的网络互惠。在此模型中，合作者在有周期边界的平面方格上，通过形成团簇抵御背叛策略者的入侵而得以
30、生存。自这项开创性工作以来，许多研究者运用计算机仿真路线，结合各种网络结构和网络动力学设计了许多合作机制，探索复杂网络上的合作行为演化。Santos等人18采用囚徒困境博弈、雪堆博弈作为博弈形式，在无标度网络上开展了合作演化的相关研究，他们发现，当种群中的个体在无标度网络这种通过依附优先连接方式生成的网络上进行博弈时，相互之间会产生强相关性，这种强相关性导致了合作的产生。邓丽丽等人19构建了一个双层相互依赖的网络结构，两层网格之间的对应个体具有相互联系。通过定义一个耦合系数，在对称耦合和非对称耦合的情况下，以最后通牒博弈为博弈形式进行了相关研究，该研究发现对称耦合的条件下，两层网络之间信息能够
31、互通，相较于单项联系的非对称耦合更能够使得利他策略固定下来。汪小芳等人20开展了关于零行列式策略在异质性种群中的演化动态研究。引入了敲诈系数，并研究其对群体异质性的影响，同时研究了不同网络拓扑结构对群体异质性维持的作用。该文章研究发现，一定范围内的敲诈系数能够有效维持群体异质性，同时这种作用也存在饱和区间；而在随机网络上，加边的模型建立方式能够对群体边缘策略个体进行连通，使得异质性得以维持。Rand等人21基于最后通牒博弈，研究了不同选择强度与变异率情况下提议者与响应者的策略演化，他们发现，在中等变异率和中等选择强度下，自然选择会有利于公平的演化，即提议者给出高于避免拒绝的出价，而响应者的要价
32、均大于0。对均匀混合的种群，相互背叛是唯一的稳定态，合作者无法生存。但改变种群网络结构，合作者可以生存。无标度网络、小世界网络的提出，引发了研究热潮，而异质性网络结构、不同更新方式的提出有效地促进了人们对不同结构系统、混合策略更新方式的认识。通过调整博弈模型、策略更新规则等设计博弈设计动力学机制，如扩充策略空间（引入孤立策略、奖励策略、惩罚策略、零行列式策略等）、动态收益矩阵、同异步更新策略等可以促进合作的演化22,23。通过调整网络结构的拓扑性质，如个体之间连接的差异程度，都会在一定程度上影响其动力学。纵览近年来有关复杂网络上演化博弈理论研究进展，可以看到各式研究成果如雨后春笋，越来越多地展
33、露出美好的前景。2.5 主要研究内容近年来，复杂网络上的演化博弈成为研究结构群体上策略竞争的有效工具，并吸引了国内外学者持续增长的关注。利用复杂网络上的演化动力学结合相关博弈形式，按照“建模-分析”的研究思路，对个体间交互异质性在复杂网络中的资源配置问题进行深入系统的研究。图 2-4 主要研究内容基于现有研究，综合不同博弈形式和复杂网络结构，从资源异质性、结构动态性等出发，构建合理的复杂网络上个体交互异质性模型。在建立模型的基础上，利用C+语言进行仿真模型搭建，并对多种参数进行仿真，研究规则网络、随机网络的给定异质性特征对分配行为有无、如何影响。在分析仿真结果的同时，从个体微观层面给出合理的解
34、释。主要研究内容如图2-4所示。3 基于演化动力学的复杂网络群体模型3.1 网络结构3.1.1 网络拓扑结构图 3-1 不同拓扑结构网络模型复杂网络作为图论的分支，是研究节点性质与群体行为的综合领域。如图3-1（a）所示为一规则网络，又称作最近邻耦合规则网络。这种网络的拓扑结构特点是每个节点都有等同的邻居顶点数量。图3-1（b）所示是一类ER随机网络结构，其建立方法如下：在个网络节点中，根据排列组合知识，最多可以生成条连边，从所有可能出现的边中每次按照一定概率挑选，共条，就可以得到一个ER网络模型，显然，可能生成的网络共有种，这些可能的网络出现的可能性均相等。另一可与上述生成方法得到等价模型的
35、途径是利用二项式模型：在个给定的节点中，两两节点间连边概率为。通过这种方式可以得出网络上连边数目为一个满足二项式分布的随机变量，其数学期望为。可以用泊松分布的形式来近似表示ER随机网络的度分布，即如下表达形式 （3-1）其中，代表该结构的平均度，在ER随机网络中，。如图3-1（c）所示，是一类小世界网络结构。NW网络模型中的度在分布上满足如下表达形式： （3-2）如图3-1（d）所示是一类无标度网络模型。常见的BA无标度网络模型可建立在优先连接的现有网络上，以偏好依附模型方式5建立：首先考虑一个具有个节点的完全图，然后每次增加个节点（），增加的每个节点都有可能与现存节点中任意节点相连，但它们选
36、择连边的概率不同，某个现存节点被选中的概率为 （3-3）其中，表示新出现的节点与已经存在的任一节点的连接概率。在网络中度的分布形式上，无标度网络满足以下表达形式： （3-4）3.1.2 规则网络模型图 3-2 不同规则网络规则网络是一种节点具有等价度分布的确定性网络模型。常见的规则网络有完全图、环形图、最近邻规则耦合网络、方格网络等（如图3-1所示）。网络上各个顶点代表的个体之间如果均有连边存在，这种结构就可以称为完全图；环状图则是指一种所有节点个体首尾相连成环的网络结构。在以往的研究中，大多数情况下规则网络结构只为创建更现实的社交网络构建基础结构，例如最近邻耦合网络是创建小世界网络的基本前提
37、。在规则网络上的许多随机连通结构会引起多个拓扑特征的同步性变化。对于规则网络结构的各项统计性质以及相关特点，目前已经有了较为完备的理论研究基本框架。例如，对于某个最近邻耦合网络，设表示该网络的所有顶点构成的集合，而表示该网络的所有连边构成的集合，如果该网络上每个个体的邻居数目均为，那么对于任意节点的邻居集合来说，可以将其分为左右两个部分，分别记作和。考虑一个由顶点集和其中连边合集组成的子图，可以得到各个顶点的度总数为 （3-5）在无向图中，所有顶点的度之和是该图中连边量的两倍，所以可以得到子图连边总数为 （3-6）根据式（2-3）中聚类系数的定义，可以计算得到该网络上节点的聚类系数为 （3-7
38、）由此求得最近邻规则网络上的聚类系数为 （3-8）由上式可以看出，节点度均匀分布的最近邻规则耦合网络具有聚类系数较高的特点，同时也说明这样的网络模型中具有较强的节点相互连通性。图 3-3 带周期性边界的方格网络对于一般空间模型，固定的个体交互博弈网络由方格位置和距离固定的连边定义，最常用的结构定义是具有纽曼邻域条件和摩尔邻域条件的正方形网格，同时也可以将方格网络拓展至更高维数。为研究规则网络上的演化博弈问题，选取带有周期性边界条件的方格网络作为种群空间结构。在方格网络上，与节点个体有边相连的顶点称作其邻居节点，周期性边界条件代表方格最外侧四周的个体也均有4个邻居节点，如图3-2所示，个体A的四
39、个邻居节点分别为个体B、C、D、E，依此类推。记为方格网络边长，种群个体总数。3.1.3 随机网络模型随机网络模型是一类节点之间连边存在一定概率分布的模型，由于节点之间的关系存在不定关系，需要用概率统计的方式进行性质表述。主要分为小世界网络、无标度网络等。WS小世界网络和NW小世界网络分别采用均匀随机重新连接节点的方法、均匀随机加上新边的方法对规则图进行生长或改造。图 3-4 WS小世界网络的构造如图3-4所示，WS小世界网络模型的建立方法主要分为两步：首先建立一个节点数目为的规则图，该规则图上，每个节点均与离其最近的个节点有边连接（图3-4中），这一均匀规则网络又称最近邻耦合网络；随后遍历该
40、规则图上的节点，在每一节点的边中任选一条，给定一个重连概率，进行节点之间边的随机重连，将该节点选中的连边终点在剩余个节点中随机均匀选择并重连。易知，当时，生成网络为规则网络，时，则生成一个完全随机网络。除了上述的小世界生成模型另一种小世界网络生成模型为NW小世界网络。这一模型与WS小世界不同之处在于，建立第一步种的规则网络后，采取的是随机加边方式（图3-5）。图 3-5 NW小世界网络的构造本文为研究随机网络上的分配行为特性时，采用WS小世界网络作为群体随机网络结构框架。小世界网络模型是一类很好地表现现实世界个体度分布特征的随机网络结构，在人类组成的社会集群中，大多数个体仅与亲邻好友进行人际往
41、来，也有少数交互对象距离较远，例如远在异乡的家人、朋友。小世界网络类似于ER随即图模型，所有的节点具有近似相等的度分布。但通过后文异质性的引入，可以研究不同异质参数下的性质。由式（3-2）可知，通过最近邻耦合规则网络上的概率连边方法构建的NW小世界网络中，任意取一个节点，该节点度为的概率为。若初始规则网络上的节点度为4，当时，可以得到。在该模型中，任意节点的度可以表示为，其中。又可以将分为两种类型的边，一类为该节点的原始存在的边，一类是在随机过程中重连的新边，其中。可以得出 （3-9） （3-10）若，当一个节点被随机从该网络上选出时，其度为的概率为 （3-11）在本文模型中，WS小世界网络上
42、的一个节点代表一个博弈主体，其可以与其各个邻居进行博弈交互式获得收益。种群规模为。3.2 种群交互结构图 3-6 不同交互结构上的群体常见的种群交互结构有均匀混合种群、规则网络上的种群、随机网络上的种群、多群组组合等（如图3-6所示）。例如，均匀混合种群是指种群中的任意两个个体均可以进行博弈交互，个体之间的交互关系完全对等，在演化博弈研究的起步阶段经常采用这种模型；具有空间结构的种群则是在网络上各占据一个节点，每个个体只能与其邻居节点上的个体进行交互，对于多群组选择，不同群组中的个体首先进行组内相关博弈，然后以群组总收益或其他指标作为组间选择的比较依据。本模型采用的是规则网络上的交互结构，即博
43、弈交互、策略学习等过程只能发生在同一个体与其邻居节点之间。3.3 博弈交互范式为研究规则网络上的资源分配行为所存在的特征，采用最后通牒博弈作为博弈范式。博弈中，提议者的提议量用表示，指该个体在博弈时愿意分给响应者的资源比例。响应者可以接受的提议量用表示，同样地，。记为个体作提议者时的提议比例，为个体作响应者时可以接受的分配比例。那么，可以记种群中任意一个个体的策略。在最后通牒博弈中，只有响应者提议的分配比例大于等于响应者最低可接受分配比例时，双方才能得收益，分配行为才得以产生。记个体在与个体博弈中作提议者时的收益为，作响应者时的收益为。当博弈中总分配资源量为1时，可以得到个体在以作不同身份与个
44、体博弈时的收益分别为： （3-12） （3-13）本模型中，当个体与其邻居节点上的个体进行交互时，以提议者身份和响应者身份各进行一次博弈。典型的最后通牒博弈存在几种不同的策略设置类型：（1）公平策略设置。即的情形，这种情形下，个体的提议量与响应阈值相等。当个体与个体相遇，且时，双方总是能达成一次分配行为。如图3-7所示，若，双方个体的博弈收益分别为、。其策略的收益空间如图3-4。和均在0.5以下，且时，由于个体作提议者可以达成分配行为，故其可以获得的收益，这一收益大于0.5，而个体得到的收益为，所以可以得出；和均在0.5以下，且时，达成分配行为后个体得到的收益大于0.5，故。图 3-7 公平策
45、略设置下的策略收益空间（2）武断策略设置。这种情形下，即持这种策略的个体希望从作响应者身份的博弈中获得自己作提议者时相同的分配比例。在这种设置下只有时双方才能达成分配行为，此时双方收益分别为、。图 3-8 武断策略设置下的策略收益空间如图3-8所示如果参与博弈的两个个体的策略值满足条件，那么由于无法达成分配行为产生的条件，双方的收益都为0；相反，只有时双方才会得到非零收益，这种情况下，如果，由于博弈环节可以达成以个体为提议者的分配行为，而，其得到的分配资源比例会少于个体，从而可以得到。（3）独立策略设置。即个体的提议比例与响应阈值互相独立，这种情况下双方可以得到的收益可用式（3-8）、（3-9
46、）表示。在这一模型中，采用独立策略设置。由式（3-8）、（3-9）可以得到个体在与个体一次交互中得到的总收益为 （3-14）本文采用C+程序语言建模，并进行蒙特卡洛方法模拟仿真，为合理计算每个个体的博弈收益，在每一个蒙特卡洛时间步内，网络上的所有个体同步进行最后通牒博弈，亦即每个个体同时与其周围的邻居个体进行二人最后通牒博弈（如图3-9所示，a、b、c、d四个交互在同一时间进行）。图 3-9 个体间的同步博弈在每个个时间步末，结束博弈后，个体的收益用表示，可以得到： （3-15）其中，表示个体的邻居个体集合。在现实生活中，决策主体经常会发生战略记忆，对以往和自己进行过博弈交互的个体采取的策略以及博弈时己方得到的收益进行记忆，故本文在模型中加入分配总额的转换。若当个体与个体在博弈中产生分配行为，即或时，双方下次进行博弈时可分配的资源总量为1，若两个体在博弈中没有达成分配行为，即或时，双方下次进行博弈可分配的资源变为0.5。由式（3-1）、（3-2）可知，当可分配资源总量为0.5时，个体的收益为 （3-12）