基于LabVIEW的复杂网络演化博弈实验软件

刘海洋，刘歌群，任宁春，张嘉楠

(上海理工大学 光电信息与计算机工程学院，上海 200093)

基于LabVIEW的复杂网络演化博弈实验软件

刘海洋，刘歌群，任宁春，张嘉楠

(上海理工大学 光电信息与计算机工程学院，上海 200093)

复杂网络演化博弈能够揭示丰富的物理现象和规律，复杂网络演化博弈实验软件对于演化博弈过程的理解和认知具有重要作用。目前对网络演化博弈进行可视化的软件并不多见，因此文中基于LabVIEW开发了一种演示网络演化博弈过程的实验软件。软件在LabVIEW开发环境下，规划人机交互界面，实现软件流程。软件的输入包含了网络模型、博弈模型和策略更新规则，对节点策略、节点收益以及网络合作频率进行动态显示。可以对众多网络演化博弈过程进行演示，并文中给出了软件运行结果。

复杂网络；实验软件；演化博弈；LabVIEW

随着博弈论的广泛应用，博弈个体之间的关系变得越来越复杂，博弈结果的形成过程也引起了学者们的关注，因而诞生了网络演化博弈论。在网络演化博弈理论中，将网络上的节点看作博弈个体，边代表博弈关系，博弈个体随着时间演化，不断地与其邻居进行博弈并更新其策略[1]。网络演化博弈理论为复杂网络上的交互行为提供了强有力的解释和恰当的模型，近些年引起了学术界广泛的关注和兴趣。在对网络演化博弈理论的学习中，理解网络上博弈和演化的过程至关重要。

目前进行网络演化博弈仿真分析，主要使用Matlab[2]、Repast[3]和Netlogo[4]等软件。但是能够直观展示各方博弈策略及其演化过程的专用软件包尚不多见，因此提供一种对网络演化博弈过程进行可视化的专用软件已成为一种需要。

本文设计开发了基于LabVIEW的网络演化博弈实验软件，对网络演化博弈过程中节点收益、节点策略以及网络合作频率的变化进行可视化，从而可以帮助实验者更好的理解和掌握网络演化博弈的理论知识。

1 网络演化博弈简述

博弈论为解释自私个体间的交互行为提供了强有力的理论框架[5]，从而得到了快速发展和广泛应用。在传统博弈论的基础上，演化博弈论进行了补充和完善，结合生物演化理论，揭示了个体间的自私行为和群体广泛的合作行为之间的内在统一。而以复杂网络为框架进行演化博弈称为网络演化博弈。

1.1 博弈论

博弈是指参加斗争或竞争的各方为了达到各自的目标和利益选取对自己最为有利或最为合理的方案[6]，日常生活中的下棋、打牌和著名的囚徒困境[7]等都是博弈。一个完整的博弈应当包括以下几方面的内容：(1)博弈的参与者，即博弈中独立决策、独立承担后果的个人或组织，又称为局中人；(2)博弈个体的策略，即每个局中人可选择的全部行为；(3)博弈信息，即博弈者所掌握的对选择策略有帮助的情报资料；(4)博弈的次序，即局中人做出策略选择的先后；(5)博弈收益，即博弈方做出决策后的所得与所失。

在博弈过程中每个局中人在选择博弈策略时必须考虑其他局中人的策略，与此同时每个局中人的博弈收益还依赖于其他个体所采用的策略。博弈论就是研究博弈中是否存在着最合理的行为方案，以及如何找到这个合理的行为方案的数学理论和方法。博弈论对简单博弈最直观的表述就是将博弈用收益矩阵来描述，这种表述形式又称为矩阵表述。一个典型的矩阵表述举例如图1所示。

图1 博弈的矩阵表述

图中，博弈局中人分别为vi，vj。局中人vi可以选择的策略有：A1，A2；局中人vj可以选择的策略有：B1，B2，B3。矩阵中元素Umn表示局中人vi和vj对于策略组合(Am，Bn)的收益组合。

1.2 经典博弈论和演化博弈论

经典博弈论在局中人是完全理性的情况下研究博弈的均衡问题，而对均衡的解释为在均衡状态下没有个体可以通过单方面改变自己的策略而增加收益。但是经典博弈论存在一些缺陷:首先，“完全理性”观点认为局中人总是选择使自己利益最大化的策略，在复杂环境下，局中人很难获取全部信息，因此局中人“完全理性”的观点是不切实际的；其次，经典博弈论虽给出了均衡解释，但并没有给出均衡的形成过程[8]。

演化博弈论借鉴生物进化理论对经典博弈论进行了完善。演化博弈论使用“有限理性”观点代替了经典博弈论中的“完全理性”观点。有限理性结合适者生存的概念，认为局中人通常是在掌握有限信息的情况下，以优化自己的收益为目标选择策略，与此同时借鉴生物种群的进化和稳定机制，模拟均衡的动态实现过程。因此，演化博弈被广泛地用于研究各式各样的合作现象[9]。

演化博弈论的关键是如何在具体情况下构造动态机制来模拟局中人的学习和决策过程，最终目标是寻找促进合作行为涌现的动态机制。目前，支持合作行为产生的机制大体有：亲缘选择，直接互惠，间接互惠，网络互惠以及群体选择[10]。亲缘互惠是指具有亲缘关系的个体之间的合作关系，例如：当地震来临时，父母会奋不顾身的保护子女。直接互惠通常指朋友间相互帮助，这种相互帮助会促进合作的涌现，例如重复对手的策略就是直接互惠。间接互惠则发生在陌生人之间，倾向合作的个体拥有较高的声誉，同时可以得到别人的合作。网络互惠主要指描述个体联系的网络的结构对于合作涌现具有影响。群体选择指多个群体之间虽然是斗争的，但是作为一个整体时它们之间却是合作的，一个形象的例子就是公司内部的各个部门之间。

1.3 网络演化博弈论

以复杂网络为框架进行演化博弈研究的理论称为网络演化博弈论。在演化博弈论中，通常假设所有个体是相同的，相互之间均匀混合，即群体中任意两个个体等可能地进行博弈[11]。而现实世界中，种群的个体通常不能与所有的个体相互接触，他们之间存在复杂且不均匀的相互关系。复杂网络理论的飞速发展，为这种复杂且不均匀的相互关系提供了描述框架：网络中的节点表示博弈个体，边代表博弈关系。

局中人在复杂网络上随着时间的演化和他的邻居进行博弈称为网络演化博弈，通常用vi，i=1,2,…,N表示第i个局中人；用Si={ei1,ei2,…,eiQ}表示局中人vi采取的策略集合；s=(s1,s2,…,sN)表示N个局中人采取的策略在策略空间的一个策略组合，其中si∈Si；用ui(s)表示此策略集合下第i个局中人的收益。这样一个演化博弈表述为Y={s1,s2,…,sN;u1,u2,…,uN}。

复杂网络演化博弈具有3个要素：博弈模型、策略更新规则以及网络模型。博弈模型包含经典博弈论中的博弈模型等，比如囚徒困境、雪堆模型和猎鹿模型等；网络模型则包含各式复杂网络模型：随机网络或小世界网络等。而策略更新规则的选取对于网络演化博弈至关重要，目前主要有如下几种更新规则：模仿收益最大的邻居策略，即个体确定性的选择收益最大的邻居策略作为自己下一轮博弈的策略[12]；按概率选择优胜邻居的策略，即考虑收益高于自己的所有邻居,按正比于其收益的概率选择其策略[13]；配对比较个体随机选择某个邻居进行收益比较，以某个概率转变为对方的策略[14]。

2 网络演化博弈实验软件设计

为了直观演示网络演化博弈的演化过程，本文所介绍的网络演化博弈实验软件在LabVIEW开发环境下开发。为体现软件控件的关联性，如图2所示，将实验软件的前面板分为参数设置区、博弈演示区以及数据显示区。

根据网络演化博弈条件，设计参数设置区包含复杂网络演化博弈3个要素和博弈轮数。为了充分演示复杂网络演化博弈过程，设计博弈演示区包含网络拓扑结构以及节点策略进行。同时设计数据显示区包括了本轮收益数组、累积收益数组以及合作频率图表，以显示博弈过程中网络和节点统计信息的变化。

图2 前面板以及网络拓扑结构图生成

复杂网络演化博弈实验软件以网络演化博弈相关理论为依据，设计了以下功能性步骤：软件启动后的初始化状态；参数设置环节；演化博弈过程中的实时动态演示和数据更新；一次完整的演化博弈实验结束后的状态返回。

为使软件具有更好的可读性和拓展性，演化博弈过程分为博弈计算、策略更新以及效果显示3个子过程。博弈计算过程进行博弈的本轮收益计算。策略更新计算过程则根据策略更新规则进行策略的更新计算。效果显示过程对本轮收益、总体收益和策略进行更新。软件运行流程如图3所示。

图3 软件流程图

软件流程的几个主要环节为初始化、参数设置、博弈计算、策略更新计算和效果显示。

(1)初始化及参数设置阶段。初始化阶段进行前面板按钮状态和数据的初始化。参数设置相关控件以组合控件形式，集中在参数设置区。其中网络模型的设置采用按钮的形式，点击按钮进入相应子VI进行对应网络的设置。可设置的网络模型不仅包含了常见的BA无标度网络、WS小世界网络和ER随机网络，还设计了自定义网络按钮以满足实验者的特定需求。对称博弈模型的设置则采用二维矩阵的形式。策略更新规则的设置采用组合框的形式，包含了两个比较常见的更新规则：模仿最优更新和随机更新规则。此外，参数设置阶段还包含了博弈演示区节点策略的设置。节点策略设置以布尔控件实现，灰色表示合作，黑色表示背叛；

(2)博弈计算阶段。博弈计算阶段根据网络拓扑结构，对有博弈关系的节点进行两两博弈收益的计算，再通过循环嵌套完成所有博弈关系的本轮收益计算，如图4所示。图中邻接矩阵变量为网络的邻接矩阵，策略数组和本轮收益变量分别为16个策略和本轮收益，按节点编号组成两个1维数组。

图4 博弈计算阶段程序图

如图4所示，两两博弈的博弈收益计算使用“二维索引数组控件”实现。该控件的数组接线端连接博弈模型数组，行和列的索引接线端都连接代表节点策略的0或1常量。例如：行接线端连接的节点策略为合作，列接线端连接的节点策略为背叛，策略转化的常量为(1，0)，对应数组第二行第一列的数，即行接线端节点的本次博弈收益。

由于某一节点的本轮收益是与其相关的所有两两博弈收益的累加，因此在进行新的两两博弈后，需要在本轮收益数组中对代表该节点的本轮收益进行更新。在LabVIEW中，使用“替换数组子集控件”实现这种对数组元素的更新。替换数组子集控件的数组连线端连接“本轮收益数组”，索引连线端为节点编号，子集连线端则连接求和后的节点本轮收益。

所有连边关系上的博弈计算，通过多重循环结构对邻接矩阵的行和列进行遍历实现。在循环过程中，上轮循环得到的结果作为下轮循环的输入，如图4使用“移位寄存器”的数据处理方式。移位寄存器可实现程序语言中的静态局部变量，从而实现随着每次循环体的执行而累加；

(3)策略更新计算阶段。博弈计算阶段完成后进入策略更新阶段，策略更新阶段根据选定的规则对博弈策略进行更新。

如图5所示，使用条件结构判断所选定的策略更新规则，在条件结构中使用循环嵌套计算出每个节点更新后的策略。图5中显示的是模仿最优策略更新规则，即节点将邻居中本轮收益最高节点的策略作为自己的策略。在更新过程中，使用移位寄存器进行循环结构中节点策略数组的更新。

图5 策略更新计算阶段程序图

(4)效果显示阶段。该阶段将对前面板上的数据进行更新，其中包括节点策略，节点本轮收益数组、节点累积收益数组和网络的合作频率图表。根据策略更新阶段计算获得的策略，对界面上的节点策略显示颜色进行更新。合作频率经计算后以图表形式显示，图表横坐标表示博弈的轮数，纵坐标代表合作频率。图表形式有助于更加直观地了解网络演化博弈的统计特性。

3 软件运行实例

为了说明软件对网络演化博弈过程的演示效果，以文献[15]中的网络演化博弈数据为例进行演示实验。设置节点初始策略合作和背叛各占1/2，策略更新规则选取为模仿最优更新规则，博弈模型采用联合生产博弈模型，收益矩阵如图6所示。分别在无标度网络、小世界网络，随机网络和二维格子网络模型下进行网络演化博弈实验。

图6 联合生产博弈模型

运行软件后，点击前面板网络模型区域相应的网络模型按钮，进入各自的子VI进行网络模型参数设置。网络模型设置完成后，将图6的数据输入博弈模型区域的矩阵中，选择模仿最优策略更新规则，设置博弈演示区域的节点策略初始状态。点击设置完成按钮，博弈演示区域显示所设置的网络模型的拓扑结构，如图1所示。设置博弈轮数为25，点击博弈按钮开始博弈。在博弈过程中前面板中的本轮收益数组、累积收益数组以及博弈演示区域的节点策略都在不断更新，合作频率图表中绘制网络中节点策略的合作频率并不断延伸。

图7 合作频率

在第12轮博弈后点击结束按钮，得到合作频率图。对4种不同的网络分别进行实验，得到4个合作频率图如图7所示，可以发现，随着博弈轮数的增加，合作频率最终趋于稳定。不同网络下合作频率变化不尽相同，体现了不同复杂网络模型对于网络合作频率的影响不同，这符合基本常识。而且稳定后的合作频率不同，和文献[15]的理论结果相一致。

图7中小世界网络模型下的前5轮博弈演示区节点策略的变化如图8所示，灰色表示节点当前策略为“合作”，黑色表示节点当前策略为“背叛”，此图展示了每一轮各个节点当前的策略，以及策略的变化过程。其中灰色节点越来越多，表明网络的合作频率随着博弈轮数的增加在增长，趋势与图7(b)一致，体现了所设计软件的有效性。

图8 小世界网络的前5轮博弈演示区

4 结束语

本文在LabVIEW开发环境下，设计了一种基于LabVIEW的网络演化博弈实验软件，对网络演化博弈过程进行了可视化。软件的参数设置模块设计包含了网络演化博弈的各个要素，方便实验者根据不同要求进行试验，进而了解在网络演化博弈中各个参数发挥的作用。同时，软件的显示模块对网络演化博弈过程中的各个数据进行了展示，并动态地演示了网络演化博弈过程中策略与合作频率的变化。实验表明，该软件有助于帮助人们理解和学习网络演化博弈的理论知识，可在复杂网络演化博弈的实验和教学过程中发挥作用。

[1] 汪小帆,李翔，陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社,2006.

[2] 范如国,张应青,罗会军.考虑公平偏好的产业集群复杂网络低碳演化博弈模型及其仿真分析[J].中国管理科学,2015(S1):763-770.

[3] 杨中华.基于核心企业的供应链网络信息共享研究[D].武汉:华中科技大学,2013.

[4] 阮国祥,阮平南.集群网络企业间知识转移演化博弈仿真分析[J].图书情报工作,2011,55(16):77-81.

[5] 荣智海.复杂网络上的演化博弈与机制设计研究[D].上海:上海交通大学,2008.

[6] 杨涵新,汪秉宏.复杂网络上的演化博弈研究[J].上海理工大学学报,2012,34(2):166-171.

[7] 陈维春,尚丽辉.基于奖励因子的囚徒困境博弈模型研究[J].电子科技,2016,29(3):5-6.

[8] 王文宾.演化博弈论研究的现状与展望[J].统计与决策,2009(3):158-161.

[9] 姜罗罗,汪秉宏.复杂系统中的合作演化与自组织斑图[J].上海理工大学学报,2012,34(2):172-184.

[10] Nowak M A.Five rules for theevolution of cooperation[J].Science,2016,314(5805):1560-1563.

[11] 王先甲,全吉,刘伟兵.有限理性下的演化博弈与合作机制研究[J].系统工程理论与实践,2011,31(S1):82-93.

[12] Nowak M A.evolutionary games and spatial chaos[J].Nature,2002,359(6398): 826-829.

[13] Hauert C,Doebeli M.Spatial structure often inhibits the evolution of cooperation in the snowdrift game[J].Nature,2014,428 (6983):643-646.

[14] Devlin S,Treloar T.Evolution of cooperation through the heterogeneity of random networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics, 2009,79(1Pt2):100-115.

[15] 刘歌群,詹志国,胡琦,吕伟臻.联合生产博弈模型[J].电子科技,2016,29(3):1-4.

Experimental Software Developed with LabVIEW for Evolutionary Games on Networks

LIU Haiyang,LIU Gequn,REN Ningchun,ZHANG Jianan

(School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technology, Shanghai 200093,China)

Evolutionary games on complex networks can reveal abundant physical phenomena and laws. Experimental software for networked evolutionary games plays an important role in the understanding and cognition of evolutionary game process. Because the visualized software for the networked evolutionary games are rare, so we developed a software with LabVIEW to display the process of networked evolution games. In the LabVIEW development environment, we designed the human-machine interface and programmed the software process. The input of the software includes the network model, the game model and the strategy update rules. The software can dynamically show the nodes strategy, the nodes gains and the networks’ cooperation frequency. The software can demonstrate the process of lots of evolutionary games on several types of networks. At the end of this paper, the software running results.

complex networks; experimental software; evolutionary games; LabVIEW

2017- 01- 17

沪江基金(C14002)；上海理工大学光电信息与计算机工程学院教师创新能力建设项目(GDCX-Y-1212)；上海市大学生创新创业训练计划项目(SH2016030)

刘海洋(1993-)，男，硕士研究生。研究方向：复杂网络。刘歌群(1974-)，男，博士后。研究方向：复杂网络与计算机控制。

10.16180/j.cnki.issn1007-7820.2017.12.029

TP311.5

A

1007-7820(2017)12-109-05