SWARM—一个支持人工生命建模的面向对象模拟平台

来自集智百科
跳转到: 导航搜索

转载自系统仿真学报2002年第5月
作 者:丁 浩, 杨小平 (中国人民大学信息学院, 北京 100872)


摘 要:简要介绍了系统科学中引人注目的复杂适应系统(CAS)理论,以及在美国桑塔费研究所开发的一个模拟工具集——Swarm。Swarm平台可以支持研究者对复杂适应系统使用多主体模拟(Multi-Agent Simulation)的方法来开展研究工作。本文还介绍了Swarm的基本结构和工作原理,并且还结合一个实例简要阐述了模型的设计与实现过程,试图为复杂系统提供一个崭新的研究思路。


关键词:复杂适应系统(CAS); Swarm; 主体(Agent); 适应性; 遗传算法

SWARM An Object-Oriented Platform to Construct Artificial Life Model DING Hao, YANG Xiao-ping (Information School, Renmin University of China, Beijing 100872, China)

Abstract: This paper introduces the theory of Complex Adaptive System (CAS). It also recommends a software utility Swarm that allows researchers to construct discrete event simulations of complex systems with heterogeneous agents. In the end, we carry out an example Life Game, to help the readers to grasp the modeling method of constructing CAS. Keywords: complex adaptive system (CAS); Swarm; agent; adaptability; genetic algorithms (GA)


目录

复杂适应系统(CAS)介绍

以复杂性研究为主流的当前的新的发展阶段,我们可以看到系统科学的发展经历了从元素数量较少、关系比较单纯的系统的过程,到元素个数较多,研究系统自身演化与发展的过程,到现在元素具有主动性,能与外界交流并会根据经验改变自身的动态系统的过程。我们的重点就在于复杂性的一个侧面——适应性上。这一领域现在被称为复杂适应系统(Complex Adaptive System, CAS)是由遗传算法(Genetic Algorithms, GA)的创始人J. Holland在1994年正式提出的。 有关CAS理论的最基本的思想可以概述如下: 复杂适应系统(CAS)理论把系统的成员看作是具有自身目的与主动性的积极的主体。主体能够与环境以及其它主体进行交流,在这种交流的过程中“学习”或“积累经验”,并且根据学到的经验改变自身的结构和行为方式。整个系统因此而产生演变或进化,包括新层次的产生,分化和多样性的出现或新的、聚合而成的、更大的主体的出现等等。 更重要的是,CAS理论认为,正是这种主动性以及它与环境的反复的、相互的作用,才是系统发展和进化的基本动因。Holland把个体与环境之间这种主动的、反复的交互作用用“适应”一词加以概括。这就是CAS理论的基本思想——适应产生复杂性。 关于这个基本思想,有以下四点需要强调说明。

首先,主体(Adaptive Agent)是主动的、活的实体。这点是CAS 和其他建模方法的关键性的区别。正是这个特点,使得它能够用于经济、社会、生态等其它方法难于应用的复杂系统。 其次,在这个模型中,个体与环境(包括个体之间)的相互影响,相互作用,是系统演变和进化的主要动力。以往的建模方法往往把个体本身的内部属性放在主要位置,而没有对于个体之间,以及个体与环境之间的相互作用给予足够的重视。这个特点使得CAS方法能够运用于个体本身属性极不相同,但是相互关系却有许多共同点的不同领域。 第三,这种建模方法不象许多其他的方法那样,把宏观和微观截然分开,而是把它们有机地联系起来。它通过主体和环境的相互作用,使得个体的变化成为整个系统的变化的基础,统一地加以考察。 第四,这种建模方法还引进了随机因素的作用,使它具有更强的描述和表达能力。考虑随机因素并不是CAS理论所独有的特征。然而CAS理论处理随机因素的方法是很特别的。简单地说,它从生物界的许多现象中吸取了有益的启示,其集中表现为遗传算法(Genetic Algorithm)。 由于以上这些特点,CAS理论具有了与其他方法不同的,具有特色的,新的功能和特点。


Swarm介绍

Swarm的背景

Swarm是析复杂适应系统建立模型而设计的软件平台。1995 年SFI 发布了Swarm 的beta 版,此后,大约30个用户团体已经安装了Swarm并用它积极地开展建模工作,并完成了一定的论文。Swarm已经帮助提供了讨论模拟技术和方法论的焦点,还提供在特定的研究团体中模型组件和库的共享,这是智力交换的一个重要形式。最终,建立一个用于模型定义的形式化框架建立一个特定用于实验科学工具的计算机程序的必要标准。 开发Swarm 的目的就是通过科学家和软件工程师的合作制造一个高效率的可信的可重用的软件实验仪器,它能给予科学家们一个标准的软件工具集,就象提供了一个设备精良的软件实验室帮助人们集中精力于研究工作而非制造工具。 Swarm 实际上是一组用Objective-C 语言写成的类库,这是一种面向对象的C 语言。一部分图形界面,如图表、按钮和窗口,是用TCL/TK 描述的。Swarm 最初只能在Unix 操作系统和X Windows 界面下运行,1998 年四月伴随着 1 .1版的发布,Swarm 推出了可以在Windows 95/98/NT 上运行的版本。1999 年Swarm又提供了对Java 的支持,从而使Swarm 越来越有利于非计算机专业的人士使用。 Swarm的建模思想就是让一系列独立的Agent通过独立事件进行交互,帮助研究由多个体组成的复杂适应系统的行为。通过这些类库包括许多可重用的类以支持模拟实验的分析、显示和控制,即用户可以使用Swarm 提供的类库构建模拟系统使系统中的主体和元素通过离散事件进行交互。由于Swarm 没有对模型和模型要素之间的交互作任何约束,所以Swarm 可以模拟任何物理系统、经济系统或社会系统。事实上在各个广泛的研究领域都有人在用Swarm 编写程序,这些领域包括生物学经济学物理学化学和生态学等。


Swarm的逻辑结构

Swarm中最主要的四个部分,往往也是一个Swarm模拟程序经常包括的四个部分是:模型swarm(ModelSwarm)、观察员swarm(ObserverSwarm)、模拟主体和环境。


模型“swarm”

Swarm就是许多个体(对象)组成的一个群体,这些个体共享一个行为时间表和内存池。显然“Swarm”有两个主要的组成部分:(1)是一系列对象(Object);(2)这些对象的行为时间表(Action)。时间表就像一个索引引导对象动作的顺序执行。 - 对象。 模型“swarm”中的每一项对应模型世界中的每一个对象(个体)。“swarm”中的个体就象系统中的演员,是能够产生动作并影响自身和其他个体的一个实体。模拟包括几组交互的个体。例如,在一个经济学模拟中,个体可能是公司、证券代理人、分红利者和中央银行。 - 时间表。 除了对象的集合,模型“swarm”还包括模型中行为的时间表。时间表是一个数据结构,定义了各个对象的独立事件发生的流程,即各事件的执行顺序。通过确定合理的时间调度机制,可以使用户在没有并行环境的状况下也能进行研究工作,也就是说,在并行系统下agent之间复杂的消息传送机制在该swarm中通过行为表的方式可以在单机环境下实现。例如,在狼/兔子这个模拟系统中可能有三种行为:“兔子吃胡萝卜”,“兔子躲避狼的追踪”和“狼吃兔子”。每种行为是一个独立的动作。在时间表中,对这三种行为按照以下顺序排序:“每天,兔子先吃胡萝卜,然后它们躲避狼的追踪,最后狼试图吃兔子”。模型按照这种安排好的事件的执行顺序向前发展,并尽量使这些事件看起来象同步发生的。 - 输入输出。 模型“swarm”还包括一系列输入和输出。输入是模型参数:如世界的大小,主体的个数等环境参数。输出是可观察的模型的运行结果:如个体的行为等等。


观察员“swarm”

模型“swarm”只是定义了被模拟的世界。但是一个实验不应只包括实验对象,还应包括用来观察和测量的实验仪器。在Swarm计算机模拟中,这些观察对象放在一个叫观察员“swarm”的“Swarm”中。 观察员“swarm”中最重要的组件是模型“swarm”。 它就像实验室中一个培养皿中的世界,是被观测的对象。观察员对象可以向模型“swarm”输入数据(通过设置模拟参数),也可以从模型“swarm”中读取数据(通过收集个体行为的统计数据)。

与模型“swarm”的设置相同,一个观察员“swarm”也由对象(即实验仪器),行为的时间表和一系列输入输出组成。观察员行为的时间表主要是为了驱动数据收集,即从模型中将数据读出,并画出图表。观察员“swarm”的输入是对观察工具的配置,例如生成哪类图表,输出是观察结果。 在图形模式下运行时,观察员“swarm”中的大部分对象被用来调节用户界面。这些对象可能是平面网格图,折线图或探测器,它们一方面与模型“swarm” 相连以读取数据,同时把数据输出到图形界面,为用户提供了很好的实验观察方式。 实验结果的图形化有助于直觉地判断,但重要的实验都需要收集统计结果。这意味着要做更多地工作并存储用于分析的数据。作为图形观察员“swarm”的另一种选择,你可以建立批处理“swarm”(batch swarms)。它和用户之间没有交互操作。它从文件中读取控制模型的数据并将生成的写入另一个文件中用于分析。它这只是观察方式不同罢了。


模拟主体

swarm不仅是一个包含其它对象的容器,还可以是一个不包含其它对象的主体本身。这是最简单的“swarm”情形,它包括一系列规则、刺激和反应。而一个主体自身也可以作为一个“swarm”:一个对象的集合和动作的时间表。在这种情况下,一个主体“swarm”的行为可以由它包含的其它个体的表现来定义。层次模型就是这样由多个“swarm”嵌套构成。例如,你可以为一个居住着单细胞动物的池塘建立模型。在最高层,生成包括个体的“swarm”:“swarm”代表池塘而每个个体代表池塘里的一个动物。动物的细胞也可以看作是由多个个体(细胞质)组成的“swarm”。这时需要连接两个模型,池塘作为一个由细胞组成的“swarm”,细胞也作为一个可分解的“swarm”。

还由于“swarm”可以在模拟运行过程中建立和释放,Swarm可用来建立描述多层次的动态出现的模型。 通过建造模型“swarm” 和观察员“swarm”, 将模型和数据收集分离开,一个完整的实验仪器就建立起来了。就像一个玻璃下的模拟世界,不同的观察员“swarm” 可用来实现不同的数据收集和实现控制协议,但是模型本身没有发生变化。


环境

在一些模型中,特别是在那些具有认知部件的个体模拟中,系统运动的一个重要因素在于一个主体对于自己所处环境的认识。Swarm的一个特点就是不必设计一个特定类型的环境。环境自身就可以看作一个主体。通常情况下,主体的环境就是主体自身。


“生命游戏”模型实例

模型背景

“生命游戏”模型是《复杂》一书中所描述的一个例子,这个例子最初是由英国科学家约翰� 康卫(John Conway)在二十年前设计的一个游戏,即在一个二维平面方格中,布满着“活着的”的黑方块和“死了的”白方块,最初的图案可以由游戏者任意摆布。但一旦可是运作这个游戏后,这些方块就会根据很少几条简单规则活过来或死过去。每一代的每一个方块首先要环顾其四周的近邻,如果近邻中造就又太多活着的方块了,则这个方块的下一代就会因为太拥挤而死去;如果其近邻中存活者过少,则这个方块就会因为孤独而死去。但如果其近邻中存有两个或三个“活着的”方块,则比例恰到好处,这个方块的下一代就能存活下去。也就是说,要么是这下一代已经活着,能够继续存活下去,如果不是这样,就会产生新的一代。 规则就这么简单。这些规则只是一种漫画式的生物学。然而“生命游戏”模型的奇妙之处就在于此,当我们将这些简单的规则变成一个计算机程序之后,就好像真的能够让计算机屏幕“活”起来。如果用心观察,就可以看到计算机屏幕沸腾着各种活动,就像是在一台显微镜下观察一滴池塘水里的微生物。开始时你可以随意设置一些活着的方块,可以观察到它们如何很快自组织成各种连贯一致的结构。其中有的结构翻滚不已,有的结构的振荡犹如野兽呼吸。你还会发现“滑翔机”,即一小簇以常速滑过屏幕的活细胞。你还会看到稳定的发射出新的滑翔机的“滑翔机枪”,以及在那里气闲心定的吞噬滑翔机的其他结构。每重玩一次,出现在屏幕上的图案都会有所不同,无法穷尽其可能性。


模型的设计

在这个模型中,我们采用基于Agent的建模方法,赋予模型一个真实的微观基础。这里,我们采用32×32的二维平面方格,则共有1024个“活着”或“死去”的生命实体。这种模拟应该更能避免一些误差情况的出现。 生命 在模型中,每一代“活着的”生命都要向其四周“探测”是否有别的生命,并统计四周生命的数量,如果不等于2个或3个,则该生命就会死去。 所以,在方位[x, y]的“生命”主体L在下一代是否能生存下去就要看其周围的“活的”生命数: nFriends += getActiveofX$Y(x+i,y+j), 其中,i,j在[-1,1]内取值 ,getActiveofX$Y(x,y)是取得[x,y]处“生命”状态的函数。 这样,除主体L本身外,共要探测其周围8处位置的状态。(见图1)

Swarmsoft1.gif


模型的实现

我们根据前面介绍的Swarm的逻辑结构来分析,在该模型中,各类主体包含了那些类以及它们各自都起到了什么作用? “生命游戏”中的模型“Swarm”同样也包含一组主体、模拟主体行动的时间表和模型的输入和输出。在“生命游戏”中,主体行动的顺序为:首先每个主体探测周围的“活着的”生命数,然后统计生命数,根据事先规定好的规则变成死亡状态还是继续生存下去,最后所有的主体形成一个新的生命图案。 图2展示了模型中可调整的参数,这也就是模型的输入。 ObserverSwarm:ObserverSwarm同样也是Swarm类的一个子类,因此它也应该是由一组对象、对象行动的时间表和输入输出组成。在这个模型中,ObserverSwarm图表对象是每一时刻二维平面方格中的生命数。被观测的生命主体数由ModelSwarm中的Lifebeinglist决定。 模拟主体 在这个模型中,模拟主体只有一个类,就是“生命”。 环境 环境是指示模型中的一个主体,即“生命”主体的生存空间,在本模型中,由于规则比较简单,没有涉及环境和“生命”主体之间的信息传递,“生命”主体从而也不用从环境主体中获取信息,“积累经验”,所以本模型中可以不用考虑环境主体。 从以上分析,我们可以了解各个对象之间的关系如图3。

Swarmsoft2.gif


运行结果

由图4我们可以看出,在系统刚开始运行的一段时间用从环境主体中获取信息,“积累经验”,所以本模型中可以不用考虑环境主体。 从以上分析,我们可以了解各个对象之间的关系如图3。 里,生命的总个数逐渐上升,最后稳定在一个比较中性的水平上,因为在32×32的二维平面方格中共有1024个“活着”或“死去”的生命实体,而在图4中,我们也可看出系统在运行了一个较长的时间后,“生命”的总数稳定在一个较小的区间[375,450]中,但是我们同时也看到系统并没有处于一种静态的平衡状态中,而是处于一种动态的丝毫不能安顿下来的状态之中,似乎在这个系统中存在着一种永不静止的动力使“生命”图案能够不断生长、分裂和重组,生命似乎也确实是试图在混沌的边缘保持永远的平衡:一方面始终处于陷入过分的秩序的危险之中,另一方面又始终被过分的混乱所威胁。 通过这个模型,我们可以领略到由几条简单的规则所引起的令人惊奇的复杂现象。而这一点正是我们对在复杂系统中的规则发现和适应性学习等内容要深入研究的。

参考文献

[1] 米歇尔沃尔德罗普. 复杂 [M]. 三联出版社, 1997.

[2] Nelson Minar, Roger Burkhart, Chris Langton, Manor Askenazi. A Top-Down Introduction To Implementing an Experiment Using Swarm [EB/OL].http://www.santafe.edu/projects/swarm/swarmdocs/set/book149.html

[3] Eric Bonabeau, Marco Dorigo, Guy Theraulaz. Swarm Intelligence: From Natural to Artificial Systems [M]. Oxford University Press,1999.

[4] John H Holland. Hidden Order [M]. Addison-Wesley, 1995

[5] 美国桑塔菲研究所网站[EB/OL] http://www.santafe.edu/projects/swarm.

[6] Swarm官方网站[EB/OL],http://www.swarm.org. Model Swarm Action Observer Swarm Action


相关wiki

个人工具
名字空间
操作
导航
工具箱