复杂系统研究中基于agent的模型化方法

江世杰, 韩战钢

(北京师范大学管理学院,北京 100875)

Agent-based modeling(简称ABM)是一种研究复杂系统的模型化手段,它可以方便地将一些不易数学化的规则纳入模型,并且易于表示学习、发展(develop)等外生的信息,这使得它有别于传统模型方法,如微分方程、统计分析及系统动力学等[1].其与微分方程模型化方法的主要区别在于微分方程使用宏观的变量,如密度,而基于agent的模型方法使用微观变量,如描述具体的某个分子或个体.

在社会系统等复杂系统中,包含大量个体,个体间相互影响,并且通过学习调整自己的行为以更加适应周围的环境.ABM由相互作用的自主agent组成,每个agent有自己的行为规则,既能够影响其他的agent或环境,也能被其他的agent或环境所影响.在基于agent的模型的微观层面,每个agent所遵循的具体规则都比较简单,但是,在宏观层面上,agent可以通过自组织,产生并不一定可以直观想象出来的宏观效果、整体行为(collective behavior)[2].相关研究使得人们可以在规则制定时预计到会产生的系统整体行为,并使得人们可以修改这些规则,让系统向着有利于系统整体效益的方向发展.这种在微观、宏观多尺度上产生的并不能用简单相加解释的宏观效果,被称为是涌现性(emergence)[1].虽然涌现这一概念已经提出很久,但是,其出现机制和效能并没有被彻底解决.加州州立大学的Abbott教授也曾明确指出涌现性是复杂系统研究的重点关注对象(原文为“圣餐”——holy grail)[3].

ABM为观察和研究复杂系统中的类似现象提供了强而有力的工具.从种族冲突、免疫系统的模拟到经济政策分析等[4-6],ABM的应用已十分广泛.近年来,国际上已经有大量的学者和研究人员投身于ABM的研究和应用中,并且得出了一些十分有意义的结论,本文旨在对ABM作为一个复杂系统模型化方法的一些重要问题进行简要介绍.

1 agent与ABM的性质

ABM的雏形可以追溯到20世纪40年代.当时,第一台计算机的设计者及博弈论的创始人,Von Neumann提出了一个有趣的想法:人造机器的自我繁殖.他想象着可以制造一台机器,然后让它在充满了零件的池塘里游来游去,它可以拾起一些部件,并将不同的部件组装到一起,从而制造出一台和自己一样的机器.但是,当时的机器零部件非常昂贵,因此,这个想法几乎不可能实现.之后受到他的朋友,数学家Ulam的启发,Von Neumann在二维网格平面上实现了这一模型.这就是最初的元胞自动机.

最广为人知的元胞自动机当属英国数学家Conway在1970年构造的生命模型[7].在Conway的生命模型中,二维网格上的一个网格代表一个元胞,每个元胞都有开和关两种状态(对应生和灭),元胞的状态取决于和它相邻的元胞的生灭状态.给定不同的初始状态,模型就可以在简单的规则作用下演化出奇妙的有规律的宏观现象,它验证了复杂的宏观模式可以通过简单的个体规则演化得到.生命模型成为说明涌现和自组织的典型例子.

早期基于平面空间作用关系的ABM大都模仿了生命模型的结构,例如,Epstein和Axtell的Sugarscape模型[8].在这一模型中,agent的拓扑关系更加复杂,agent可以在二维平面上的格子之间移动,即格子成为agent的环境而非agent本身.agent可以在环境中移动并获取能量.类似的工作还有Schelling的种族分离模型[9].

从1940年至今,ABM更多地作为一种思想方法,而非仅仅是技术[10],已经被应用到科学研究的各个方面,ABM的建模形式也是多种多样的.但是,一个基本的ABM还是要包含以下3个元素[11]:

a.一定数量的agent;

b.一套完备的agent拓扑关系和作用规则;

c.agent的环境,agent在环境中相互作用,并且与环境相互作用.

对于agent的定义,学者们并未达成一个明确的共识.Jennings[12]提出了一个面向agent的软件工程(agent-oriented software engineering)概念,即系统中的agent不需要全局的优化计算,而是通过个体间相互作用得出最优的配合方式,他认为这一思路将成为解决分散控制和复杂系统控制的途径.以一个柔性制造系统为例[12],有多个工件需要经过多个机器的多道工序加工时,现有的思路是预先设定一个全局优化的时序,这会受到加工时间延迟或机器加工失误的影响.而面向agent的思路是,每个工件和机器上都附着一个agent,工件agent需要与机器agent协商,协调加工顺序,以避免集中式预先计划的弊端.也有学者认为,系统的任意独立成分都可以视作agent[10].还有学者则认为agent必须能够针对以往的“经验”学习和改变自己的行为.Casti[13]提出agent应该包含两层规则.一层基本的规则用于指导agent对外界的反应;一层高级的规则指导agent学习和调整基本规则.

还有一些研究人员给出了agent应该具有的性质[14-16],现将它们列出来.

自主性(autonomy):agent是自主的个体,没有中央控制,能够处理数据并与其他agent交换数据. agent可以与其他的agent发生相互作用,或在一定的范围内发生相互作用,这并不影响自主性.agent是主动的而不是被动的.

异质性(heterogeneity):平均意义上的个体是没有意义的,个体是自主的.可以存在agent群体,但是,这是自底向上形成的、相互类似的自组织个体的集合.agents的属性设置或属性值如果都相同,则定义为是同质的(homogeneous);agent的属性设置或属性值有所不同,则定义为是异质的.

积极主动与目标引导(pro-active/goal-directed):agent的行动要达成一定的目标.

反应与感知(reactive/perceptive):agent可以被设计成具有对周围环境的感知能力.agent也可以被赋予先验的知识.

有限理性(bounded rationality):agent可以通过异质性的形式被设置为有限理性.

相互作用与通讯(interactive/communicative): agent有能力进行频繁的通讯.

移动性(mobility):agent具有可移动性,即可以在模型的空间中移动,与agent的可相互作用性并具有智能属性结合,可以发挥出很多应用.

自适应性与学习(adaptation/learning):agent可以设计为具有自适应性,构成复杂自适应系统[17].这样的设计允许agent以记忆与学习的形式适应环境变化.agent的自适应可以通过个体层次(如通过学习改变竞争被关注程度的规则的概率分布)或群体层次(如通过学习改变agent竞争复制的概率分布)实现.

人们对以上agent性质的描述,有很多不同的观点.例如,异质性就不一定是agent的必有特性.很多情况下,同质性或异质性是在设计agent系统时事先设计好的,也就是说,agent的属性设置和属性值预先就被设计成都相同或是不同.而已有的工作表明,异质性的agent可以从同质的agent演化而来[18].另外,可移动性也并不一定是 agent系统必须具备的性质.例如,最初的元胞自动机[7].

对agent定义的不同见解,并未影响到人们对这一工具的使用,ABM已经被应用到了物理、生物、社会及经济系统等各个领域,相关工作建立的模型从基本粒子的运动,到恐慌人群的疏散[19,20],覆盖面非常广泛.

2 基于agent的模型介绍

Vicsek等[20]在1996年提出了经典的 Vicsek模型,该模型从统计力学的角度出发,验证了简单的规则可以产生复杂的群体行为.Vicsek模型由大量独立的agent组成,agent以固定的速度移动,移动方向则是周围邻居agent移动方向的平均,并且受到随机噪声的影响.他们发现,系统只要满足agent密度足够大、噪声足够小的条件,就会演化出相变行为——系统中所有的agent由随机的运动转化为都向同一个方向运动.这种一致性现象受到了很多人的关注,之后Jadbabaie等相继给出了Vicsek模型在各种条件下能够达到一致性的理论证明[21-24].实际上,这种一致性行为在由大量个体组成的系统里十分常见.从癌细胞的扩散,到鱼群的运动、鸟类的迁徙、大规模的蝗虫灾害,在上面系统中的个体,大都能够在速度、方向、或者集结位置上达到相当程度的一致性.在这种一致性形成的过程中,信息传递和相互作用的方式是怎样的,它们之间是否存在共同的基本规则,能否人为地干涉这种一致性的形成等问题受到了人们的普遍关注.

普林斯顿大学的Couzin[25]通过一个简单的矢量相叠加的ABM,展示了掌握信息(食物源、迁徙方向、天敌位置等)的个体在不发出公共信号的情况下,如何通过个体间的相互作用将信息传达给其他个体.他们还发现,随着群体规模的增大,只要其中一小部分的个体(小于20%)掌握信息,整个群体就可以基于已有的信息达成一致性的行为.这一工作对群体决策中信息的作用进行了定量化的分析,为人们通过控制少量的个体达到影响全局宏观效果的需要提供了一定的理论基础.

Sumpter[26]通过观察和模拟蝗虫的移动,得到了和Vicsek模型类似的结果,随着蝗虫密度的增加,蝗虫群体的移动由无序转向有序,这和Vicsek模型[20]得出的群体密度增加导致一致性出现的结论吻合得很好.他们还研究了鱼群并利用ABM手段对其模拟[27],认为多个体系统中,个体之间不需要知道具体掌握信息的个体是哪一个,只是通过个体间的相互作用,即发现周围做出相同决策的个体数量超过一定数量就跟随它们的动作,便可以产生一致性的群体决策.并且,这一非线性的决策规则优于单个个体的决策和线性化的决策规则.

欧洲未来研究所的 Martinoli和 Deneubourg等[28]还做了这样一个实验,将几个机器人和一群蟑螂放在一起,通过设计基于局部信息的非线性反馈规律,最终发现在这个混合系统的行为决策中,机器人和蟑螂所处的地位是一样的.通过控制在群体中占少数的机器人,可以影响蟑螂的群体决策,从而产生原蟑螂群体不具有的集体行为.这为人们利用自治的机器装置研究和干涉多个体系统的行为提供了可能性.

此外,ABM还常和复杂网络一起被用来进行疾病传播的研究和模拟[29].研究者通过模型可以具体地分析人群流动的模式和人们通过社会关系相互接触的方式,而这正是疾病传播的基本途径.在这类模拟中,ABM主要用于寻找疾病形成大规模传播的条件和遏制其发生的手段.

其他方面,T aylor等[30]用ABM建立了一个针对鲸鱼迁徙过程中对阿拉斯加海狮的捕食模型.他们认为,传统捕食模型的作用关系根本不适用于临时过境生物对境内生物生存影响的分析和研究,而ABM为这种新式的捕食模型研究提供了有效的手段.在微观领域,ABM则主要用于模拟细胞的行为和相互作用、免疫系统的工作机制、还有组织的增长和疾病的产生[5].

在非生命系统方面,T roisi等[31]利用ABM模拟了分子的自组装行为,他们用agent代表单个分子,agent的行为规则遵循分子相互作用的物理规律.这种类型的模拟已经被用于发现纳米材料自组装行为中的模式形成以及材料科学中其他自组织模式的研究.

在社会经济系统中,早期较为典型的成果是诺贝尔奖获得者 Schelling[9]对种族隔离的研究. Schelling构造了一个人类群居分离的模型,在模型中,每种人群都希望避免成为少数人,人们都倾向于与同类居住在一起,基于这一简单的条件,Schelling发现只有完全的隔离才是稳定的均衡点.这一模型说明了个人动机是如何转化成为集体行为的,并得出结论,种族隔离是个人选择的结果.

美国波士顿 NECSI(New England Complex Systems Institute)的Bar-Yam带领的研究小组将种族隔离的模型对应到了现实世界中,利用ABM研究了种族居住区域之间暴力冲突的产生[4].他们利用已有的人口数据作为初始群体,放置于实际地图中,地图上的每个像素点代表一个agent,所有的agent都偏好和同种族的人居住.演化的结果说明在特定规模大小的群体居住区或者边界定义不清晰的区域,最容易产生暴力冲突.充分的混居和清晰划分的边界都会有效地降低暴力发生的可能性.他们将模型应用于前南斯拉夫以及印度的种族冲突中,对暴力冲突发生地区进行了预测,与新闻报道中暴力冲突发生地区符合得很好.这一工作为调节地区关系和避免种族冲突的发生提供了政策指导.

ABM在社会学方面的另一个重要应用是人群流动的研究.人群中的个体之间存在着内在的协同性和排斥性,造成了人群流动的整体复杂性.这一研究方向的标志性工作是Helbing于1995年在PRE (Physical Review E)上发表的文献[32],他在文中提出以社会力(social force)的形式对行人间相互作用具体化和模型化,并用Langevin方程描述行人移动的动力学过程.2000年Helbing等在Nature上发表的文章又以社会力模型为基础,建立了一个恐慌人群疏散的的模型[19].在这个模型中,他们利用社会力来作为agent之间相互作用的基本方式,使得个体之间会尽量靠近但又避免碰撞.利用这一模型,他们系统地分析了在恐慌人群疏散时可能出现的问题.模型的演化结果揭示,在出口处放置障碍物反而会提高人群疏散的效率.这一工作为检测和提高大型集会场所人群疏散能力提供了基本的研究思路.

个体之间协作与分工的演化同样是一个ABM研究的前沿问题[17].Santa Fe研究所的 Bonabeau等受社会型昆虫行为研究的启发,提出了一个劳动分工合作模型[33].在该模型中,基于信息素的信息共享机制可使系统涌现出分工与合作的机制.这一研究的立意在于,定义在微观层次的相互作用过程可以涌现出宏观层次的模式(pattern),并可以推广到社会型昆虫系统.展现了复杂的集体行为(collective behavior)可以从个体简单相互作用中涌现.

洛桑的瑞士联邦理工(EPFL)与加州理工(Caltech)的学者们还设计了一个非常有趣的拔棍实验[34],该实验以一种巧妙的方式展示了分工与合作在群体中如何涌现.这一研究源于如下认识:任何单独的结构复杂的系统都无法保证覆盖实际应用中无法预计的复杂任务,而单独的结构复杂的系统设计困难、成本高、故障率高、维护困难.所以,应该设计多个体系统,每个个体具有简单的功能,他们相互合作以完成复杂的任务.在此实验中,agent之间没有任何信息共享,合作也可以形成.

经济学方面,ABM同样是一个有效的研究手段.Tesfatsion将这方面的研究称为ACE(agentbased computational economics),并于2001年 10月为IEEE的相关杂志组织了专辑[35].此外,Macy等[36]还利用ABM分析了流动性对美国市场和日本市场信任机制形成的影响.一般认为流动性高的社会个体间不容易相互信任,不易形成大的市场;流动性低的社会大家容易互相信任,容易形成大的市场.这与美国(流动性相对高,市场相对完善)和日本(流动性相对低,市场相对没有美国完善)的情况不符.Macy的研究得到了信任度与流动性的倒U型关系,解释了这一现象.这一工作连同Berry[37]和Henrickson等[38]发表在PNAS(Proceedings of the National Academy of Sciences)的一系列文章反映了这一研究领域正在受到学界的高度关注.

在宏观经济学方面,Fagiolo等[39]认为,新古典主义经济学要成为一门真正的科学,必须要找到一个新的理论框架来替代以前的思路,而目前最有可能成为这一新理框架的正是agent-based computational economics(ACE).Hommes则设计了一个资产定价模型[40],利用真人控制的agent对资产进行估价,分析了预期形成的过程.这一研究方式超越了传统的数据分析手段,将人类的真实行为引入了模拟.我们相信这种方法在发掘宏观涌现的微观机制的研究工作中将会越来越受到重视.Chen等[6]还将ABM用于模拟彩票市场,对彩票收入的征税额度进行优化,其中的agent自适应机制采用了遗传算法的规则,并且基于模糊逻辑做出选择,最终的演化结果给出了制定税率的最佳区间.这一工作为分析和研究宏观政策的制定和影响提供了很好的范例.

需要补充的是,ABM的模型具体设计本文并未具体介绍,这里只涉猎一下其中最重要的一点,自适应性.agent通过对历史信息的记忆,通过学习达到对环境的适应.agent系统的学习机制有多种,其中,一种被广泛使用的学习机制是自增益学习.自增益学习的基本思路是:如果一个动作的效果是正面的,则这个动作应该更多地被鼓励;相反,如果一个动作的效果是负面的,则这个动作应该被抑制.例如,Roth和Erev[41]提出了一个很好的自增益学习机制,Tesfatsion等[42]后来又进行了改进.这个机制对于可能采取的每个动作都设置一个采用概率,并通过执行后的收益情况调整这些概率的值,达到自适应的目的.

3 结 论

无论是自顶向下的模型方法(如用微分方程建模)还是自底向上的模型方法(如ABM),都是对客观世界现象的描述,不存在孰优孰劣之分.ABM更适合描述基于规则演化的系统或者微观相互作用的性质,但对于大规模的多个体相互作用系统,如1023量级的分子相互作用,ABM的计算效率极低,不如基于微分方程的模型更有效.ABM也与其他的模型化手段一样,会面临模型验证的问题(validation)的挑战.与实际实验数据、观测数据符合,并能够预测新的现象,也同样是ABM研究需要遵循的基本原则.

[1] HOLLAND J H.Studying complex adaptive systems [J].Journal of Systems Science and Complexity, 2006,19(1):1-8.

[2] HOLLAND J H.HiddenOrder:How Adaptation Builds Complexity[M].San Francisco:Addison Wesley Publishing Company,1995.

[3] ABBOTT R.Challenges for biologically-inspired computing[C]//Proceedings of the 2005 Workshops on Genetic and Evolutionary Computation.Washington, DC:ACM,2005:12-22.

[4] LIM M,M ETZLER R,BA R-YAM Y.Global pattern formation and ethnic/cultural violence[J].Science, 2007,317(5844):1540.

[5] FOLCIK V A,AN G C,OROSZ C G.The basic immune simulator:An agent-based model to study the interactions between innate and adaptive immunity [J].Theoretical Biology and Medical Modelling, 2007,4(1):39.

[6] CHEN S H,CHIE B T,LEE C W.Lottery marketsdesign,micro-structure,and macro-behavior:an agentbased computational approach[C].Proceedings of 4th Computational Intelligence in Economics and Finance, 2005:21-26.

[7] GARDNER M.Mathematical games:The fantastic combinations of John Conway's new solitaire game‘Life' [J].Scientific American,1970,223(4):120-123.

[8] EPSTEIN J M,AXT ELL R.Growing Artificial Societies[M].Cambridge,MA:MIT Press,1996.

[9] SCHELLING T C.Micromotives and Macrobehavior [M].New York:Norton&Company,1978.

[10] BONABEAU E.Agent-based modeling:Methods and techniques for simulating human systems[J].Proceedings of the National Academy of Sciences of the United States of America,2002,99(Suppl 3):7280.

[11] MACA L C M,NORTH M J.Tutorial on agent-based modelling and simulation[J].Journal of Simulation, 2010,4(3):151-162.

[12] JENNINGS N R.On agent-based software engineering[J].Artificial Intelligence,2000,117(2):277 -296.

[13] CASTI J L.Would-beworlds:How simulation is changing the frontiers of science[M].New York:John Wiley&Sons Inc,1997.

[14] WOOLDRIDGE M,JENNINGS N R.Intelligent agents:Theory and practice[J].The Knowledge Engineering Review,1995,10(2):115-152.

[15] FRANKLIN S,GRAESSER A.Is it an agent,or just a program?:A taxonomy for autonomous agents[J]. Intelligent AgentsⅢ,Agent Theories,Architectures, and Languages,1997(1193):21-35.

[16] NORTH M,MACAL C,CAM PBELL P.Oh behave! Agent-based behavioral representations in problem solving environments[J].Future Generation Computer Systems,2005,21(7):1192-1198.

[17] HOLLAND J H.Complex adaptive systems[J].Daedalus,1992,121(1):17-30.

[18] ZHAO E,LIU G,LUO D,et al.Evolving specialization,market and productivity in an agent-based coop-eration model[J].Complex Sciences,2009(5):1564 -1574.

[19] HELBING D,FARKAS I,VICSEK T.Simulating dynamical features of escape panic[J].Nature,2000,407 (6803):487-490.

[20] VICSEK T,CZIRÓK A,BEN-JACOB E,et al.Novel type of phase transition in a system of self-driven particles[J].Physical Review Letters,1995,75(6): 1226-1229.

[21] JADBABAIE A,LIN J,M ORSE A S.Coordination of groups of mobile autonomous agents using nearest neighbor rules[J].IEEE Transactions on Automatic Control,2003,48(6):988-1001.

[22] REN W,BEARD R W.Consensus seeking in multiagent systems under dynamically changing interaction topologies[J].IEEE Transactions on Automatic Control,2005,50(5):655-661.

[23] OLFATI-SABER R,M URRAY R M.Consensus problems in networks of agents with switching topology and time-delays[J].IEEE T ransactions on Automatic Control,2004,49(9):1520-1533.

[24] FAX J A,MURRAY R M.Information flow and cooperative control of vehicle formations[J].IEEE Transactions on Automatic Control,2004,49(9):1465 -1476.

[25] COUZIN I D,KRAUSE J,FRANKS N R,et al.Effectiveleadership and decision-making in animal groups on the move[J].Nature,2005,433(7025):513 -516.

[26] BUHL J,SUMPTER D,COUZIN I D,et al.From disorder to order in marching locusts[J].Science, 2006,312(5778):1402.

[27] WARD A,SUMPTER D,COUZIN I D,et al.Quorum decision-making facilitates information transfer in fish shoals[J].Proceedings of the National Academy of Sciences,2008,105(19):6948.

[28] HALLOY J,SEM PO G,CAPRARI G,et al.Social integration of robots into groups of cockroaches to control self-organized choices[J].Science,2007,318 (5853):1155.

[29] CARLEY K M,FRIDSMA D B,CASM AN E,et al. BioWar:Scalable agent-based model of bioattacks[J]. IEEE Transactions on Systems,M an and Cybernetics,Part A:Systems and Humans,2006,36(2):252 -265.

[30] TAYLOR C,KOYUK H,COYLE J,et al.An agentbased model of predator-prey relationships between transient killer whales and other marine mammals [R].Anchorage,AK:University of Alaska Anchorage,2007.

[31] TROISI A,WONG V,RATNER M A.An agentbased approach for modeling molecular self-organization[J].Proceedings of the National Academy of Sciences of the United States of America,2005,102 (2):255.

[32] HELBING D,M OLNAR P.Social force model for pedestrian dynamics[J].Physical Review E,1995,51 (5):4282-4286.

[33] CAMPOS M,BONABEAU E,THERAULAZ G,et al.Dynamic scheduling and division of labor in social insects[J].Adaptive Behavior,2000,8(2):83.

[34] LI L,MARTINOLI A,ABU-MOSTAFA Y S.Learning and measuring specialization in collaborative swarm systems[J].Adaptive Behavior,2004,12(3/ 4):199.

[35] LEBARON B,IZUM I K,UEDA K,et al.Special issue on the agent-based modeling of evolutionary economic systems[J].IEEE Transactions on Evolutionary Computation,2001,5(5):437-560.

[36] MACY M W,SATO Y.Trust,cooperation,and market formation in the US and Japan[J].Proceedings of the National Academy of Sciences of the United States of America,2002,99(Suppl 3):7214.

[37] BERRY B,KIEL L D,ELLIOTT E.Adaptive agents,intelligence,and emergent human organization:Capturing complexity through agent-based modeling[J].Proceedings of the National Academy of Sciences of the United States of America,2002,99(Suppl 3):7187.

[38] HENRICKSON L,MCKELVEY B.Foundations of“new” social science:Institutional legitimacy from philosophy,complexity science,postmodernism,and agent-based modeling[J].Proceedings of the National Academy of Sciences of the United States of America, 2002,99(Suppl 3):7288.

[39] FAGIOLO G,ROVENTINI A.On the scientific status of economic policy:a tale of alternative paradigms [R].Verona:Università di Verona,2008.

[40] HOMMES C,SONNEMANS J,TUINST RA J,et al. Coordination of expectations in asset pricing experiments[J].Review of Financial Studies,2005,18 (3):955.

[41] ROTH A E,EREV I.Learning in extensive-form games:Experimental data and simple dynamic models in the intermediate term[J].Games and Economic Behavior,1995,8(1):164-212.

[42] NICOLAISEN J,PET ROV V,TESFATSION L. Market power and efficiency in a computational electricity market with discriminatory double-auction pricing[J].IEEE T ransactions on Evolutionary Computation,2002,5(5):504-523.