1、计算模型与复杂适应系统,北京交通大学经管学院张江2005.9,系统科学的新进展,信息论、控制论、系统论耗散结构、协同、突变混沌、分形复杂适应系统理论、复杂性科学复杂性科学的代表：SFI学派钱学森：开放的复杂巨系统,复杂适应系统,什么是复杂系统？,什么是复杂适应系统？个体会因为小的改变而适应环境，累积起来就可以形成系统的进化,复杂性科学的圣菲学派,圣菲研究所的兴起20世纪80年代，一批物理学家、经济学家、计算机科学家、生物学家聚集到Santa Fe，建立了著名的SFI研究所。面对复杂系统，我们如何分析？隐喻：不同学科之间的概念可以相互借鉴计算机模型：计算机不仅是一个计算系统，它本身是一个很好的隐
2、喻系统。,基于Agent的计算机仿真,对复杂系统不去试图建立大的模型，而是建立个体的Agent模型，让这些简单的代码在机器中相互作用。机器中的涌现现象：超出了建模者的想象。通过隐喻类比，可以把机器中的涌现现象映射到显示系统中。,Boid一个简单、有趣的涌现系统,Tierra机器中的数字生命,Sugarscape模拟的人工社会,我的工作,对生命系统的探索：Autolife模型对经济系统的探索：AEM模型,Autolife模型的背景,研究动机对人工生命模型的着迷Boid虽有趣，但是行为规则是建模者付给Agent的。什么样的简单规则能造就复杂行为呢？该问题没有答案Tierra中的数字人工生命具有“任
3、意的”自编程能力，但却不具备良好的界面表现力能否用进化的方法进化出一个直观、良好界面的人工生命模型？,模型的预期要求,应该让Agent（数字生命）生活在一个二维空间中自由移动每个Agent应该是一个可以任意进化的程序体。Agent简单的移动操作可以组合成复杂的曲线不能简单的采用适应度函数，而应该让适应度函数自发涌现。,模型的设计(I)环境,一个二维的生态环境世界,模型的设计(II)Agent,仅能够感知到它眼前三个方格的情况。如果方格有食物则标为0，没有则标为1，这样Agent的输入集合就是：I=000,001,010,011,100,101,111,Agent的输出集合,Agent的可能输出
4、动作为前移、左转、右转，另外还包括繁殖自身当Agent移动到的方格刚好有一个食物，则把它吃掉因此输出动作集合O=0,1,2,3Agent如何根据输入选择输出变成了一个映射：F: IO然而，此映射的可能性过于简单，共有3*4=12种可能性,增加Agent的内部状态,给Agent加入一个内部状态集合S=0,1,2,9这样Agent的决策就是映射：于是，Agent的决策就变成了一个决策规则表,Agent的繁殖与进化,每当Agent选择了繁殖动作输出的时候，系统就繁殖该Agent首先，在母亲Agent的旁边诞生一个新的Agent。其次，子Agent继承母Agent的各种属性，包括拷贝母亲的决策表同时，
5、在拷贝决策表的过程中会发生变异变异1：决策表中的某一项发生任意突变变异2：决策表的项数随机增加或减少变异3：Agent的内部状态数增加或减少,Agent的计算能力,Agent耦合它的局部环境等价于图灵机什么是图灵机？Click通过变异，Agent原则上可以写出“任意的”程序。将每个Agent看作一台画图的机器，它可以通过组合输出动作（前移和转弯）可以组合成任意的曲线。继续,图灵机,理论计算机一切计算机的抽象模型,图灵机的计算能力,通过变化图灵机的规则表以及增加它的内部状态就能用图灵机执行任意的算法过程丘奇-图灵论题：(Church-Turing thesis)宇宙中的一切计算过程都可以用图灵机
6、来建模返回,隐性适应度,每个Agent都有一个能量水平Energy吃掉食物，则增加能量：Efood运动能够消耗能量：Enormal, Emove,Eturn,EpEnergy=0则Agent就会死去新生的Agent会得到固定的能量Ep每个Agent都必须巧妙的利用能量消耗获得更多的食物进行能量增殖每个Agent并不知道什么规则是好的，但是如果规则不能指导它有效利用能量，那么该Agent就会很快死去。因此，Agent并不知道什么是“好”，只不过“不好”的Agent都不存在了。Agent还必须能够有效的繁殖，只有繁殖才能把自己的规则传下去。没有适应度，自然选择、进化依然发生。,环境食物,食物的分布
7、构成了Agent的环境影响食物的因素包括：空间的分布时间上的动态分布食物的分布可以表达为：xi=fi(t), yi=gi(t),实验1：随机分布的环境,每个周期，随机的往二维方格的每个点均匀的下“食物雨”,Agent人口的变化曲线,规则表长度的变化,实验2：动态曲线添加食物,Agent群体会适应环境的变化,一些Agent群体会适应性的记住食物添加的轨迹位形一些Agent会对食物添加进行预测Agent群体会柔性的适应外界环境,复杂系统的柔性控制,添加新的规则,目前的模型Agent不能任意的写环境，只能把食物吃掉，即将10。考虑到对称性，如果让Agent能把01会怎样？这意味着Agent不仅能吃掉
8、食物，还能自我产生食物为了让比喻更恰当，我们将添加Agent的行动可能：O=0,1,2,3,4，其中4表示播种每当Agent进行一次播种，都消耗Efood的能量每隔20周期，种子会变成两个食物Agent能够通过播种而带来更多的食物，我们不用从外界再人为加入食物,组织的涌现,一旦Agent的生产和消费产生了闭圈，组织就能出现,组织的自修复现象,组织的生与死,只要存在着因果毕圈，组织就能生长时间的运行会导致组织的衰败组织中间会诞生大量的寄生虫，它们不进行播种，但是会大量的消耗食物、繁殖最终，组织都要自然死亡,Autolife总结,用少数的规则建立了Agent模型和环境模型模型进化、涌现出了丰富的结
9、果：Agent群体会进行人口的自我学习与控制不同的环境会造就完全不同的Agent群体行为当Agent和它所在的环境构成毕圈就会产生组织组织具有自然的生死、自我修复等生命现象,对Autolife的改进,当加入多样化的食物会有什么不同？每个Agent既消费有生产会有什么不同？如何让Agent涌现出的组织更具有活力？例如生命体最基本的应激性？,用计算机模型探索经济系统,Artificial Economy Model (AEM)：最小经济系统一个经济系统的Toy Model什么是一个经济系统的本质？生产、消费、交换构成了最小的经济系统资源、Agent、交互构成了AEM模型,基本设定,本模型受到Sug
10、arscape模型的启发一个网格的空间，分布着资源和Agent资源有两种：糖和香料Agent仅仅能观察到局部的环境、获取资源，两种资源同时需要资源可以以一定的概率再生,Agent遵循的游戏规则,Agent需要采集糖和香料资源每一时刻，Agent都需要通过新陈代谢把糖和香料转换成能量Energy。糖和香料的新陈代谢率分别是m1和m2如果糖或香料含量有一个为0，则不能进行新陈代谢能量是Agent需要的唯一生存标准Agent的每一次移动都会消耗一定能量Energy=0则Agent就死掉Agent必须通过聪明的决策才能更好的谋生Agent的动作包括：行走、交换、繁殖等等不同的动作消耗不同的能量，同时也
11、会带来更多好处Agent需要智能的学习算法才能更好谋生,Agent的决策模型,Agent面临的决策问题：根据环境的输入：当前位置周围糖资源的密度、香料的密度、Agent密度，当前的能量水平、资源水平，确定Agent动作的输出我们采用分类器系统+规则进行建模,感知环境,Agent面对的所有局部环境以及自身的状态都可以用一个12位长的01字符串编码,对局部环境的编码,Agent维持了一组分类器规则，每一条规则都形如：If then 01*表示通配符，01为对选择决策规则的编码。所有的分类器按照匹配的程度进行排序,决策规则集合,随机游走（M） 寻觅资源（F） 聚集规则（A） 交易规则（T） 繁殖(P
12、),Agent的学习与进化,个体学习交易过程中的学习社会学习寻找资源的社会学习遗传学习每个Agent都会从它的双亲处继承分类器规则，并进行交叉和变异的操作物理模型的进化新陈代谢率视力范围,Agent之间的交易,背景在AEM中，两个Agent如果相遇（在彼此的视力范围内）就有可能发生商品交换首先，双方Agent是否愿意交换？其次，用多少比例（糖和香料的比例）来完成交换？每个Agent都是有限理性的、信息不完全的每次交易不一定是公平的，有可能出现欺诈、分配不均的情况,Agent之间的交易模型假设,假设1：每个Agent都用下式效用函数计算效用，并且按照效用函数值衡量自己的偏好。,假设2：每个Age
13、nt都会根据自己对资源的偏好、交易的历史价格信息以及贪心的程度来确定本次交易的价格。,假设3：两个Agent的讨价还价结果可以用两价格的平均值来近似替代,交易过程(I),根据边际替代率确定偏好 设Agent拥有糖x，香料y，则MRSyx=m1y/m2x确定各自的初始价格糖的价格p=y/ x当某Agent想买入糖的时候，他希望p越小越好当Agent想卖出糖的时候，希望p越大越好,交易过程（I）,其中为贪心程度是历史平均价格,卖糖,买糖,交易过程(II),讨价还价用平均价格近似确定交换方向交换的方向，也就是说谁买入糖，谁买入香料 以提出交易者为准，得到下列表格,交易算法,i.A计算本次交易的提价：
14、p0Aii.B计算本次交易的提价：p0Biii.系统确定本次交易价格：piv.根据表格1确定交易的方向，也就是a) 如果MRSA1，那么A买入糖，卖出香料；b) 如果MRSAInput,重新看待计算机,计算机似乎天生是模拟的工具CPU计算时间对应真实的时间内存空间对应真实的空间一切过程都可以看成是计算计算机是对真实世界部分的镜像,可能的应用涌现计算(Emergent computation),构造涌现计算系统涌现计算就是模仿自然界，利用一些简单的规则涌现出来的宏观规律去解决计算的问题实例：用遗传算法解决TSP问题用蚁群算法解决路径规划问题用PSO解决规划问题,涌现计算,用类似Autolife的
15、方法解决图形边缘检验,可能的应用：数字娱乐,计算机动画用人工生命的灵活适应性创造更富有生气的动画计算机游戏游戏本身就是一个模型的世界设计游戏规则就是在设计复杂系统用复杂性的思想，让游戏能够自然的涌现出有趣的可玩性,谢谢！,参考文献约翰.卡斯蒂(著),王千祥(译): 虚实世界-计算机仿真如何改变科学的疆域. 上海科技教育出版社, 1998约翰.霍兰,周晓牧等译: 隐秩序-适应性造就复杂性. 上海:上海科技教育出版社, 2000-8Epstein, J.M., and Axtell, R. : Growing artificial societies. Social science from the bottom up. Washington, D.C.: Brookings Institution Press; Cambridge, Mass.: MIT Press., 1996,
