用计算的观点探索夊杂适应系统

Size: px

Start display at page:

Download "用计算的观点探索夊杂适应系统"

寄单
5 years ago
Views:

1 计算模型与复杂适应系统北京交通大学经管学院张江

2 个体会因为小的改变而适应环境, 累积起来就可以形成系统的进化复杂适应系统什么是复杂系统? 简单系统什么是复杂适应系统? 复杂系统无组织的随机系统

3 复杂性科学的圣菲学派圣菲研究所的兴起 20 世纪 80 年代, 一批物理学家经济学家计算机科学家生物学家聚集到 Santa Fe, 建立了著名的 SFI 研究所面对复杂系统, 我们如何分析? 隐喻 : 不同学科之间的概念可以相互借鉴计算模型 : 计算机不仅是一个计算系统, 它本身是一个很好的隐喻系统

4 基于 Agent 的计算机仿真对复杂系统不去试图建立大的模型, 而是建立个体的 Agent 模型, 让这些简单的代码在机器中相互作用简单代码的相互作用可以在机器中产生超出建模者想象的行为或现象, 也就是涌现现象通过隐喻类比, 可以把机器中的涌现现象映射到现实系统中

5 Boid 一个简单有趣的涌现系统靠近对齐避免碰撞三条规则涌现出的灵活生动的复杂行为 Boid 被广泛的应用于计算机动画游戏等领域甚至激发人们开发了 PSO 算法网站 :

6 Tierra 机器中的数字生命将计算机中的内存空间比喻成空间, CPU 时间片比喻成时间, 计算机程序体比喻成生命寄生与反寄生进化的军备竞赛断点均衡等丰富的生态系统现象得以在数字系统中涌现网站 :

7 Sugarscape 模拟的人工社会 Sugarscape 被誉为基于 Agent 的社会学仿真的经典作品他用简单的计算机模型, 探讨了从 : 财富分配性别与继承战争文化传播经济交往等广泛的社会学现象 Epstein 和 Axtell 将 Sugarscape 中的涌现现象写成了一本书 : Growing Artificial Societies: Social Science from the Bottom Up

8 我的工作对生态系统的探索 : Autolife 模型对经济系统的探索 : AEM 模型

9 Autolife 模型的背景研究动机对人工生命模型的着迷能否用进化的方法进化出一个直观良好界面的人工生命模型?

10 模型的预期要求应该让 Agent( 数字生命 ) 生活在一个二维空间中自由移动每个 Agent 应该是一个可以任意进化的程序体 Agent 简单的移动操作可以组合成复杂的轨迹不能简单的采用适应度函数, 而应该让适应度函数自发涌现

11 模型的设计 (I) 环境一个二维的生态环境世界

12 环境食物食物的分布构成了 Agent 的环境影响食物的因素包括 : 空间的分布食物可以被动态的添加食物的分布可以表达为 : x i =f i (t), y i =g i (t)

13 模型的设计 (II) Agent 仅能够感知到它眼前三个方格的情况如果方格有食物则标为 0, 没有则标为 1, 这样 Agent 的输入集合就是 : I={000,001,010,011,100,101,111}

14 Agent 的输出集合 Agent 的可能输出动作为前移左转右转, 另外还包括繁殖自身因此输出动作集合 O={0,1,2,3} Agent 如何根据输入选择输出变成了一个映射 : F: I O 然而, 此映射的可能性过于简单, 共有 8*4=32 种可能性

15 增加 Agent 的内部状态给 Agent 加入一个内部状态集合 S={0,1,2,,9} 这样 Agent 的决策就是映射 : : I S O S, i I, s S, ( i, s) ( o, s') 每个 Agent 维持一个决策规则表, 每次决策都会根据输入内部状态选择一条规则

16 能量每个 Agent 都有一个能量水平 Energy 当 Agent 移动到的方格刚好有一个食物, 则把它吃掉, 增加能量 :E food 运动能够消耗能量 :E move,e turn,e p Energy=0 则 Agent 就会死去新生的 Agent 会得到固定的能量 E p 每个 Agent 都必须巧妙的利用能量消耗获得更多的食物进行能量增殖

17 Agent 的繁殖与进化每当 Agent 选择了繁殖动作输出的时候, 系统就繁殖该 Agent 首先, 在母亲 Agent 的旁边诞生一个新的 Agent 其次, 子 Agent 继承母 Agent 的各种属性, 包括拷贝母亲的决策表同时, 在拷贝决策表的过程中会发生变异变异 1: 决策表中的某一项发生任意突变变异 2: 决策表的项数随机增加或减少变异 3:Agent 的内部状态数增加或减少

18 隐性适应度每个 Agent 并不知道什么规则是好的, 但是如果规则不能指导它有效利用能量, 那么该 Agent 就会很快死去因此,Agent 并不知道什么是好, 只不过不好的 Agent 都不存在了 Agent 还必须能够有效的繁殖, 只有繁殖才能把自己的规则传下去没有适应度, 自然选择进化依然发生

19 实验 1: 随机分布的环境每个周期, 随机的往二维方格的每个点均匀的下食物雨

20 Agent 人口的变化曲线 LifeCount v Time

21 实验 2: 动态曲线添加食物

22 Agent 群体会适应环境的变化一些 Agent 群体会适应性的记住食物添加的轨迹位形一些 Agent 会对食物添加进行预测 Agent 群体会柔性的适应外界环境

23 复杂系统的柔性控制 Agent Environment Control User Complex System Feedback

24 添加新的规则目前的模型 Agent 不能任意的写环境, 只能把食物吃掉, 即将 1 0 考虑到对称性, 如果让 Agent 能把 0 1 会怎样? 这意味着 Agent 不仅能吃掉食物, 还能自我产生食物为了让比喻更恰当, 我们将添加 Agent 的行动 : O={0,1,2,3,4}, 其中 4 表示播种每当 Agent 进行一次播种, 都消耗 E food 的能量每隔 20 周期, 种子会变成两个食物 Agent 能够通过播种而带来更多的食物, 我们不用从外界再人为加入食物

25 组织的涌现一旦 Agent 的生产和消费产生了闭圈, 组织就能出现

26 组织的生与死只要存在着因果闭圈, 组织就能生长长时间的运行会导致组织的衰败组织中间会诞生大量的寄生虫, 它们不进行播种, 但是会大量的消耗食物繁殖最终, 组织都要自然死亡

27 组织的自修复现象

28 Autolife 总结用少数的规则建立了 Agent 模型和环境模型模型进化涌现出了丰富的结果 : Agent 群体会进行人口的自我控制不同的环境会造就完全不同的 Agent 群体行为当 Agent 和它所在的环境构成闭圈就会产生组织组织具有自然的生死自我修复等生命现象

29 对 Autolife 的改进当加入多样化的食物会有什么不同? 每个 Agent 既消费又生产不同的食物会有什么不同? 如何让 Agent 涌现出的组织更具有活力? 例如生命体最基本的应激性? 关于 Autolife 更详细的讨论, 请参考文献 [4]

30 用计算模型探索经济系统 Artificial Economy Model (AEM): 一个经济系统的 Toy Model 什么是一个经济系统的本质? 生产消费交换构成了最小的经济系统 AEM 中有两种资源 : 糖和香料 Agent 可以采集资源而构成生产 Agent 需要消耗资源新陈代谢构成消费 Agent 之间可以交换糖和香料

31 基本设定本模型受到 Sugarscape 模型的启发一个网格的空间, 分布着资源和 Agent 资源有两种 : 糖和香料 Agent 仅仅能观察到局部的环境获取资源, 两种资源同时需要资源可以以一定的概率再生

32 Agent 遵循的游戏规则 Agent 需要采集糖和香料资源每一时刻,Agent 都需要通过新陈代谢把糖和香料转换成能量 Energy 糖和香料的新陈代谢率分别是 m 1 和 m 2 如果糖或香料含量有一个为 0, 则不能进行新陈代谢能量是 Agent 需要的唯一生存标准 Agent 的每一次移动都会消耗一定能量 Energy=0 则 Agent 就死掉 Agent 必须通过聪明的决策才能更好的谋生 Agent 的动作包括 : 行走交换繁殖等等不同的动作消耗不同的能量, 同时也会带来更多好处 Agent 需要智能的学习算法才能更好谋生

33 Agent 的决策模型 Agent 面临的更复杂的决策问题 : 输入信息更加复杂, 包括 : 当前位置周围糖资源的密度香料的密度 Agent 密度, 当前的能量水平资源水平, 确定 Agent 动作的输出虽然 Agent 的行动仍然是移动, 但是 Agent 需要具有较长远的眼光来决策 AEM 中的 Agent 模拟的是现实经济系统中的人, 所以采用特殊的决策模型

34 CRA(Classifiers, Rules, Actions) 体系结构分类器分类器系统决策策略 ( 交易寻找资源随机性走等 ) 决策策略集 ( 适应性工具箱 ) 行动 ( 上下左右 ) 可选行动集

35 对局部环境的编码 Agent 维持了一组分类器规则, 每一条规则都形如 : If <01**11**1*01> then 01 * 表示通配符,01 为对选择决策规则的编码所有的分类器按照匹配的程度进行排序

36 决策规则集合随机游走 (M) 寻觅资源 (F):Agent 会记住走过所有点中的资源密度最大的一个交易 (T)+ 聚集 (A)

37 Agent 的学习与进化个体学习交易过程中的学习社会学习寻找资源的社会学习遗传学习每个 Agent 都会从它的双亲处继承分类器规则, 并进行交叉和变异的操作物理模型的进化新陈代谢率视力范围

38 Agent 之间的交易一种更接近现实社会的交易算法在 AEM 中, 两个 Agent 如果相遇 ( 在彼此的视力范围内 ) 就有可能发生商品交换首先, 算法决定双方 Agent 是否愿意交换其次, 算法决定用多少比例 ( 糖和香料的比例 ) 完成交换? 每次交易不一定是公平的, 有可能出现欺诈分配不均的情况每次交易结束,Agent 会发生个体学习从而改进交易算法的参数

39 涌现结果分析 : 第一组实验 : 涌现结果 : 个体进化社会分工价格波动

40 AEM 涌现结果分析 : 适应度对比 Fitness 有交易 2000 无交易 Time

41 社会分工的形成通过分析 Agent 的个体规则, 发现不同的 Agent 会演化出不同的分类器规则各种社会分工的比例 Frequency Action:3 0.4 Action: Action:2 0.1 Action: Time

42 交易次数与交易规模 TradeTimes Volume Time

43 交易价格

44 第二组试验 : 网络与流基本规则不改变 : 从流的角度观察 AEM

45 Agent 流的形成

46 商品流不能直接观察到商品流商品流的介质 :Agent 形成的交易网络商品流传播的研究方法 : 采用资源的传播与追踪方法将一部分资源标记为红色每当 Agent 进行标记资源的交换, 资源就同时感染了两个 Agent 记录每个被标记资源在 Agent 群体中的传播路径

47 商品流的介质 : 交易网络在一个固定时间段内, 交易次数超过一定数量的两个 Agent 连接一根有向线段

48 某时刻的交易网络

49 交易网络是一个无尺度网络 Nodes 100 Log Nodes Links Log Links 节点度分布遵循幂律 (Power Low) 无尺度网络是鲁棒而稳定的少数关键节点拥有大量的连接

50 交易网络的演化动态节点数目演化节点度演化聚类系数演化 ( 与同等参数的随机网络比较 )

51 资源传播网络 Ag1 Ag2 3 1 Ag6 4 2 Ag Ag5 9 8,10 8 Ag Ag7 12 Ag10 13 Ag8 Ag Ag12 14 Ag13 Ag14 16,18 Ag15 以某一个单元资源为对象, 它在 Agent 之上的传播扩散构成了资源传播网络在任意时刻, 拥有该资源的 Agent 个数为传播宽度所有传播路径的最大长度为传播深度

52 一个传播网络实例

53 传播网络的特点该网络中存在着少数关键节点, 它们拥有大量的连接, 所以在整个商品的流通过程中起到了关键的作用该网络中存在着一些明显比其他路径更长的路径该网络中存在着环

54 网络传播宽度的演化黑色是有聚集, 灰色是无聚集

55 网络传播深度黑色是有聚集, 灰色是无聚集

56 AEM 总结 Agent 可以自发形成不同的社会角色而实现社会分工 Agent 可以通过学习和适应使得价格逐渐趋于一个较稳定的区间但是, 进一步的完全均衡的静态结果却不可能实现组织的出现还使得价格呈现了多个地理区域上的不均衡性流的出现经历了两个阶段 :Agent 流出现 Agent 群体之上的商品流出现交易网络和资源传播网络逐渐演化成无尺度网络随着社会的演化, 商品流会越来越发达

57 AEM 的改进当增加多种资源的情况下会涌现出什么现象? 如果 Agent 不仅能消费资源采集资源, 而且还能通过组合不同资源生产创造产品会怎样? 如何用人工社会的方法研究复杂网络的动态演化? 复杂适应系统中的流现象

58 总结 : 计算模型 John Holland 把模型分为三类数据驱动模型 ( 天气预报模型 ) 存在性证明模型 ( 冯诺伊曼的自我繁殖机器 ) 探索性模型 ( 人工生命 ) Autolife 和 AEM 都属于探索性模型模型不能用来预测给定一组规则集, 究竟能够有哪些现象涌现评定探索性模型的标准 : Output>Input

59 重新看待计算机计算机似乎天生是模拟的工具 CPU 计算时间对应真实的时间内存空间对应真实的空间一切过程都可以看成是计算计算机是对真实世界部分的镜像建模隐喻现实复杂系统计算机模型

60 可能的应用涌现计算 (Emergent computation) 构造涌现计算系统涌现计算就是模仿自然界, 利用一些简单的规则涌现出来的宏观规律去解决计算的问题实例 : 用遗传算法解决 TSP 问题用蚁群算法解决路径规划问题用 PSO 解决规划问题

61 涌现计算用类似 Autolife 的方法解决图形边缘检验 ( 参见参考文献 [5])

62 可能的应用 : 数字娱乐计算机动画用人工生命的灵活适应性创造更富有生气的动画计算机游戏游戏本身就是一个模型的世界设计游戏规则就是在设计复杂系统用复杂性的思想, 让游戏能够自然的涌现出有趣的可玩性

63 参考文献谢谢! 约翰. 卡斯蒂 ( 著 ), 王千祥 ( 译 ): 虚实世界 -- 计算机仿真如何改变科学的疆域. 上海科技教育出版社, 1998 约翰. 霍兰, 周晓牧等译 : 隐秩序 -- 适应性造就复杂性. 上海 : 上海科技教育出版社, Epstein, 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 张江, 李学伟 : 用数字人工生命探索复杂适应系统, 复杂系统与复杂性科学,2005 第 1 期 Jiming Liu 著, 靳小龙等译 : 多智能体原理与技术, 清华大学出版社,2003,11 欢迎光临网站 :

社会科学战线年第期跨学科研究 ( ),, (, ),,, 1 ( ), ( -, ),,,,,,,,, (, ) ( ),,,,,,,,,,,, ( ) ( ),,,, ;,,,,,,, ( ),,,,,,,, ( ), ( ),,,,, :,,, (,, ),,, :,, ( % ),,,,,

社会科学战线年第期跨学科研究 ( ),, (, ),,, 1 ( ), ( -, ),,,,,,,,, (, ) ( ),,,,,,,,,,,, ( ) ( ),,,, ;,,,,,,, ( ),,,,,,,, ( ), ( ),,,,, :,,, (,, ),,, :,, ( % ),,,,, : 汪丁丁贾拥民 (, ) 本文是一个从理论出发, 最终又回到理论的案例研究在特定的社会网络中, 人与人之间的交互作用形成习俗习俗如果能够经受住不断发生的独僻性冲击, 就可以成为传统这是对梅纳德史密斯的演化稳定策略概念的拓展独僻性相当于变异或者突变, 演化稳定策略只经受了一次独僻性的冲击, 只有在随机地不断出现的冲击下保持稳定的习俗, 才能成为培顿杨所定义的传统, 这就是随机稳定均衡义乌市场的发展,

用计算的观点 探索夊杂适应系统

用计算的观点探索夊杂适应系统