基于特殊个体的网络进化博弈群智合作激发调控_王浩淼.pdf

基于特殊个体的网络进化博弈群智合作激发调控王浩淼,魏晨*,邓亦敏北京航空航天大学自动化科学与电气工程学院,飞行器控制一体化技术重点实验室仿生自主飞行系统研究组,北京 100083*E-mail:收稿日期:2021-07-01;接受日期:2021-10-14;网络版发表日期:2022-08-09科技创新2030-“新一代人工智能”重大项目(批准号:2018AAA0102403)和国家自然科学基金项目(批准号:U20B2071,91948204,U1913602,U19B2033)资助摘要引导群体中智能行为的产生与传播是群体智能领域的重要研究方向.相互合作是自然界中常见的群体智能行为.本文建立了一种基于特殊个体的网络进化博弈模型,分析了群体激发合作水平的进化特性以及调控手段.首先通过在规则网络进化博弈模型中建立有效的干预控制体系结构,实现对群集系统的调控作用;然后通过设计基于群体智能的特殊个体控制规则,特殊个体能起到促进合作行为涌现的群智激发作用;最后利用蒙特卡罗仿真方法分析了特殊个体对群体进化特性的影响,并讨论了不同参数条件对合作水平的影响.关键词特殊个体,网络进化博弈,软控制,群智合作激发,蒙特卡罗仿真1引言近年来,群体智能的有关研究得到迅速发展,有关合作现象产生与维持的研究一直以来都受到了不同领域学者的普遍关注.合作与竞争是自然界中常见的博弈关系,与完全不合作者“坐享其成”相比,合作者需要承担额外的代价,是一种对个体生存繁衍不利的行为.然而事实上,合作行为在绝大多数群体中都得到广泛的应用,如自然界中狼群围捕猎物、工蚁寻找食物以及人类社会中的种种合作行为等,这表明合作行为具有其独特的优势机制,体现了群体层面涌现出的智能性1,2.博弈论是研究群体智能中多个利益主体间的冲突和决策而产生的一门学科,将生物进化理论与经典博弈论相结合,得到了蕴含生物学中自然选择及进化机制的网络进化博弈.与传统进化博弈相比,网络进化博弈中的个体是不完全理性的,通过不断试错和调整策略达到群体的博弈平衡.1992年,Nowak与May3发表在Nature上的文章开启了网络进化博弈研究的先河,为揭示群体智能中合作行为涌现与维持机制提供了新的研究框架.以此为起点,学者们对博弈论中影响合作行为的因素进行了广泛而深入的研究.在网络结构的研究中,Realpe-Gmez等人4在正则网络以及具有固定连接关系的复杂网络上研究了进化动力学和社会规则对合作行为的影响.在重复博弈机制的研究中,Hong等人5研究了囚徒博弈中互惠机制对合作行为的促进作用.Mcavoy等人6研究了重复博弈机制下不同策略的收益及其对群体行为的影响.Press和Dyson7引用格式:王浩淼,魏晨,邓亦敏.基于特殊个体的网络进化博弈群智合作激发调控.中国科学:技术科学,2023,53:167176Wang H M,Wei C,Deng Y M.Excitation and control of group intelligence cooperation in network evolutionary game based on special individuals(inChinese).Sci Sin Tech,2023,53:167176,doi:10.1360/SST-2021-0265 2022 中国科学杂志社中国科学:技术科学2023 年第 53 卷第 2 期:167 176SCIENTIA SINICA T群体智能激发汇聚及应用专辑论 文提出了零行列式(zero-determinant,ZD)策略,能够在重复博弈中单方面控制博弈结果.在策略更新规则的研究中,Szolnoki等人8提出了个体策略更新时的渐近学习规则,并与传统的模仿规则进行对比.Nadini等人9研究了累计收益对个体合作倾向的影响.Shu等人10研究了具有记忆机制的囚徒博弈和雪堆博弈模型,个体根据历史记忆信息和邻居信息通过异步算法进行合作演化.大量研究表明,空间结构、博弈规则、个体策略选择对合作行为具有较大影响.然而大部分研究工作主要集中于如何构建博弈模型、何种因素更有利于合作现象的涌现与维持这一问题,对群体演化效果的调控机制研究较少.在博弈模型的基础上,设计一种具有普适性的群智调控方法,具有一定的研究价值.引导智能行为产生是群体智能的重要研究领域11.在多智能体系统中,难以通过设计所有个体规则以促进群体智能行为涌现.对于这一问题,Han等人12提出了群体行为干预的框架软控制(soft control),旨在通过向原始系统中引入一定数量的可控特殊个体,达到使复杂系统朝着期望状态演化的目的.Han等人13,14进一步研究了DeGroot模型中引入可控个体对群体演化效果的影响,并在囚徒博弈模型中进行了验证.Sartoretti15研究了在群体中引入领导者的作用,并进行动力学分析.软控制的核心思想在于通过引入可控个体的方法以干预系统,在不破坏群体现有规则的前提下控制整个系统.由于群集系统中个体的同质性,增加或部分个体不会影响整个系统的性质.因此对群集系统施加软控制可以使系统向着预定的目标演化.软控制的提出为集群系统群智合作行为的研究提供了新方法,也为群体智能的激发提供了新思路.本文在规则网络进化博弈中建立了一种有效的干预控制体系结构,通过引入可控个体并设计相应的控制规则,利用蒙特卡罗仿真与统计分析工具,研究基于群体智能更新规则的特殊个体对群体进化特性的影响.研究结果不仅可揭示特殊个体对群体合作水平的激发效果,也可为复杂系统中的合作行为干预控制提供理论基础.2网络进化博弈模型2.1空间网络模型在二维正则晶格网络中,个体间具有稳定、规则、固定的连接关系,是一种简单实用的空间网络结构,因此选取具有周期性边界限制条件的LL二维正则晶格作为基本网络结构.晶格网络每一个节点上都由一个博弈参与者占据,个体按照二维晶格结构与最近的四个邻居分别进行交互,网络结构具有周期重复性.利用二维坐标表示每一个节点的位置,对网络中全体节点进行编号,任意节点(x,y),其编号nx,y及邻居集合neigh表示如下:nxyLx yxyx yxy=+(1),neigh=(,+1),(+1,),(,1),(1,),(1)x y,其中,节点编号nx,y取值范围为1L2,是对晶格网络上所有个体进行排序操作;当邻居坐标计算结果超出周期边界限制条件时,需要加减一个周期长度,即xxxLxLxLxxxxLx 1=+1,+1,+1,+1,1=1,1 0,1+,10.(2)2.2博弈策略与博弈收益选取重复囚徒困境博弈(prisoners dilemma game,PDG)作为基本博弈模型.每个博弈参与者与邻居分别进行P次囚徒困境博弈,P为重复博弈长度.单次博弈的支付矩阵如表1所示,其中甲、乙表示两个博弈参与者,b表示博弈强度.定义个体的博弈策略为平稳马尔可夫策略x=(p0,pc,pd)16.其中p0,pc,pd表示每一次博弈中的合作概率,均在0,1区间内随机取值.p0为个体在一轮重复博弈中的初次交互时选择合作的概率,pc与pd分别表示在上一次博弈中对手选择合作策略C或背叛策略D时个体在当前轮次中选择合作的条件概率,马尔可夫策略表明双方的当前决策仅取决于对手在上次博弈中的表现,而与双方历史表现无关.一轮博弈的流程如图1所示.表 1单次囚徒困境博弈支付函数Table 1Payment function of a single prisoners dilemma game甲/乙CDC(1,1)(b,1+b)D(1+b,b)(0,0)王浩淼等:基于特殊个体的网络进化博弈群智合作激发调控168其中,Xi(t)表示个体i在第t轮重复博弈中采取的策略,Wi(n)表示个体i在同一轮博弈中第n次交互时采取的行为.在同一轮博弈中,个体的博弈策略不变,每一次交互的行为依概率选取合作或背叛,并且每一次的交互结果将对下一次博弈产生影响.一轮博弈结束后,个体根据自身策略更新规则更新策略.在博弈模型中,每个个体占据网络中的一个节点,在博弈过程中与周围相邻的四个邻居进行博弈,每次博弈的收益进行累计,并以收益之和作为博弈过程中的支付值,博弈收益的定义如下:tt()=(),(3)iji j,i其中,i为个体i的邻居集合;i,j(t)为个体i与邻居j进行P次重复囚徒博弈后的累计收益,而i(t)则为在第t轮博弈过程中个体i的总收益值.定义个体单次博弈行为收益函数如下:RtP=()/4.(4)i合作频率(合作水平)fc定义为t时刻所有个体在一轮重复博弈中累计合作行为所占的比例.对于N个个体共存在4PN个单独的行动,所以合作频率计算公式如下:fPNw i=14(),(5)ciN=1其中,w(i)表示个体i在与其四个邻居进行一轮重复博弈的过程中累计采取合作行为的次数.值得注意的是,平均合作比例与平均单次收益具有相同的进化特性,这一结果可作如下证明:对于单次囚徒困境,令博弈双方均为混合策略(x,y),且x+y=1,其中x为合作概率,y为背叛概率,则个体的期望收益:E Rxxbyyb xyxbxybxyxyx xyx()=(1)+(1+)+0=+=(+)=.(6)22因此在后续仿真中,用平均合作频率fc代替平均单次合作收益R.2.3个体策略更新规则在网络进化博弈模型中,普通个体以“无条件模仿”规则进行策略更新,即在每一轮策略更新时刻t,普通个体选择其邻域中当前单轮博弈收益最大的个体所图 1单轮重复博弈流程Figure 1Flow of a single round repeated game.中国科学:技术科学2023 年第 53 卷第 2 期169采用的马尔可夫策略作为自身下一时刻t+1的博弈策略,即x txtj(+1)=(),=argmax,(7)ijjj*i*其中,argmaxjji为邻域中收益最高个体.如果最优个体数量大于1,选择其中编号最小的邻居个体作为模仿对象.在基本博弈模型的基础上,还需填入能实现调控作用的特殊个体.普通个体与特殊个体占比分别为pn与ps,且pn+ps=1,pnps.引入特殊个体能够体现出普通个体不具备的群体智能的特性,从而促进系统合作水平的提高.文献17中提出了一种基于粒子群优化(particle swarm optimization,PSO)的特殊个体设计规则,揭示了特殊个体存在时的合作进化特性.在此基础上有学者提出了基于PSO的群智激发策略更新规则,并探讨了其对混合策略、合作行为的影响18,19.众多机制下的策略更新规则体现了群体智能的激发作用,但对群体智能的设计规则较为简单,并且缺少对特殊个体产生机理的研究.本文在文献17的基础上提出了一种基于邻居信息反馈的优化策略更新规则,能够实现对群体进化特性的调控,体现群智合作激发作用.3群智激发下的特殊个体控制策略与传统的分布式控制不同,基于特殊个体的干预控制仅对群体中的少数个体施加控制作用,而非对所有个体的行为进行直接干预20.并且不需要针对特殊个体设计特定的选取规则,特殊个体从完全同质的普通个体中产生,这体现出了由部分个体行为扩散到群体智能的特性,有助于调控群体朝着期望的目标演化.特殊个体与普通个体均遵守相同的博弈规则,但也存在着显著的差别:普通个体仅能模仿上一轮对手博弈策略,特殊个体具有全局记忆的能力,能够实时掌握邻居反馈信息,并综合邻居信息和历史信息产生新的策略.为了体现特殊个体调控效果不依赖于初始状态的影响,特殊个体与普通个体具有完全相同的空间地位,在网络中随机分布.个体i在第t轮重复博弈中的马尔可夫策略为xi(t)=(p0,pc,pd),每一特殊个体等效为在三维空间R0,13进行随机搜索的粒子,其在自身历史中得到最大收益时采取的策略为xt()iL,定义为历史最优策略;当前邻居中收益最高的策略为xt()iU,定义为邻居最优策略.在前半部分迭代过程中,特殊个体i在综合考虑自身历史最优信息以及邻居信息的基础上,按照下式更新当前策略:()()x tx tv tv tv txtx txtx t(+1)=()+(+1),(+1)=()e+()(