讲义第1部分第4章agent模拟原理.doc

第4章 Agent模拟原理4.1 多Agent模拟20世纪70年代，人工智能领域启用了Agent的概念，其含义指，分布式系统由多个Agent组成，Agent之间以及Agent与环境之间的活动都是并发的，具有自主性、交互性、反应性和主动性特征，常简称为多智能体4.1.1 多Agent模拟原理运用多Agent系统方法，对复杂系统（如生物、生态、社会、经济、管理等系统）建立多Agent模型，运用专用Agent模拟语言或一般计算机语言，将多Agent模型转换为多Agent模拟模型，通过模拟运行来研究复杂系统的行为及行为表现的机理这整个过程称为多Agent模拟1）多Agent建模原理多Agent模型的主要特征是，即便Agent的设计只遵循一些非常简单的规则，集体的行为也会由于Agent并发引起的非线性关系而呈现出非常复杂的模式其原理包括复杂系统中的涌现原理、以及生物学中的自组织原理1）涌现原理指要属之间局部简单的行为交互，可导致系统整体复杂行为的涌现涌现这个概念在复杂性研究中非常重要当低层次单元间交互导致高一层次新的现象发生时，我们称之为涌现如温度是分子运动的涌现，单个分子没有温度特性，但是许多分子就涌现出温度。

2）自组织原理自组织关注的是一个机体或组织自产生、自维持的现象在社会、经济、管理领域，系统中也存在大量的自组织聚集的现象，如城市、供应链、企业集群、专业市场等2）多Agent建模过程（1）通过实际系统分析，建立多Agent模型在对模拟对象进行分析时，是从系统的底层入手，即分析系统的基本要素，包括：a. 确定Agent类型及数目即分析被模拟对象的基本组成例如社会系统中的社会组织有权利组织、盈利组织等不同类型，那么，就可以分别用不同类型的Agent来代表；权利组织、盈利组织有几个，那么相应的不同类型的Agent就设置几个b. 分析Agent的行为分析现实系统中每个Agent的行为，这要从两两Agent之间的相互作用来分析，包括：不同类型Agent之间、以及同类型Agent之间c. 分析Agent行为的原因分析现实系统中每个Agent行为发生变化（即采取行动）的条件，这就是Agent两两互动的规则将上述分析结果用符号模型表述出来，即成为多Agent模型统一建模语言（Unified Modelling Language, 简称UML）可以胜任该项工作，具体为：a. 多Agent模型的静态结构的描述。

对于Agent类型及数目，可以运用UML中的类图和对象图来描述，一个类对应一种类型的Agent，而对象则为同种类型Agent中的各个Agentb. 多Agent模型的动态行为的描述对于Agent之间的相互作用，表现为对象之间互发消息，可以运用UML中的顺序图来描述对象之间的这种行为而对于行为原因，即对象之间发送消息的条件，那就要运用实际系统所属的领域问题所特有的模型了，例如经济系统的经济增长模型，企业管理系统的效益分析模型等，其中具有随机特征的变量，则要用到概率分布函数来描述2）运用计算机语言，建立多Agent模拟模型即运用专用的多Agent建模与模拟软件、或者运用一般计算机语言，编成实现多Agent模型这里面要着重解决如下关键问题：a. 搭建一个平台即建立一个模仿现实系统中Agent相互影响、相互作用的一个平台，类似于沙盘模型的一个台面模拟运行时，Agent就在该台面上工作b. 确定Agent的空间特性即确定每个Agent的空间位置是移动的还是静止的如果是移动的，那么每个Agent就可以在平台上到处移动，与相遇的Agent或资源发生行为互动；Agent如果是静止的，那么每个Agent在平面上的各自的位置都相对固定，只与其周边的Agent发生行为互动，元胞自动机就是这种方式。

c. 实现所有Agent行动的迸发过程在现实系统中，所有Agent的行动是同时发生的，不是一个一个地进行的，这就要求编程实现时要采用并行处理方式，不能是串行方式而计算机CPU的工作方式在理论上是无法实现并行方式的因此，并行模拟一直是计算机模拟领域的热门研究课题目前，已出现的多Agent建模与模拟软件有多种，Swarm就是其中最负盛名的，还有借鉴Swarm的原理，但比Swarm使用更方便的Reparst，以及当前新出现的AnyLogic，都可以实现多Agent模型4.1.2 多Agent模拟示例1）模拟过程初始状态终止状态2）原理图4中，红、黑元胞将移动到新的位置（箭头所指的位置），在此条件下，我们讨论灰色区域中心的蓝点（称为中心点）的移动规则图x 蓝点的移动根据Moore相邻关系模式，中心点有8个邻居，我们标注为元胞1、元胞2、…、元胞8，这8个元胞是中心点可能的移动去向根据2.1节讨论的人的本性，本文将员工特征分为三种类型：经济型、社会型和双重型（二者兼顾型）当管理措施发生变化时，不同类型员工的行为有不同的变化，即不同类型中心点有不同的移动令DXEk(t, t+1) = XEk(t+1)-XEk(t)，E Î{f, i}，中心点的移动规则如下：情形1：如果DXEk(t, t+1) > 0，则中心点向离红、黑元胞近的邻居移动，例如，在图4中，如果DXfk(t, t+1) > 0, 则中心点向元胞1、2或8移动。

情形2：如果DXEk(t, t+1) < 0，则中心点向离红、黑元胞远的邻居移动，例如，在图4中，如果DXfk(t, t+1) < 0，则中心点向元胞4、5、6或7移动情形3：如果DXEk(t, t+1) = 0，则中心点不移动但中心点究竟移动到哪一个元胞呢？这又跟员工的类型有关根据群体动力论[19]，员工喜欢和与本人有相同特征的人相处例如图4中，在情形1下，且假设中心点代表的是经济型员工，如果在相邻元胞（元胞3）上的蓝点也是经济型员工，则中心点向元胞2移动如果元胞3的蓝点是一个社会型员工，则中心点向8移动如果该蓝点是一个双重型员工，则中心点可能向元胞1、2、8中的任一个移动因此，当中心点代表一个经济型员工（或社会型员工、或双重型员工）时，其移动算法为：Select Case DXfk(t, t+1) (或 DXik(t, t+1))Case > 0搜索相邻元胞中的点if 相邻元胞中没有点 then将中心点移动到离红元胞（或黑元胞）最近的那个相邻元胞ElseIf 相邻元胞中都占满了点 then不移动中心点ElseIf 有经济型的点 (或社会型的点、或双重型的点) 移动到离红元胞和经济型点（或黑元胞和社会型点、或双重型点)最近的元胞Else 移动到与红(或黑)元胞最近的元胞End If End If End If Case = 0 中心点不移动 Case < 0搜索相邻元胞中的点If相邻元胞中没有点 then将中心点移动到离红元胞（或黑元胞）最远的一个相邻元胞ElseIf 相邻元胞中占满了点 then中心点不移动Else If 相邻元胞中有经济型的点(或社会型的点、或双重型点) then 将中心点移动到离红元胞和经济型点（或黑元胞和社会型点，双重型点）最远的元胞Else 将中心点移动到离红元胞（或黑元胞）最远的元胞End If End If End IfEnd Select3）分析图9 三个情形模拟中的Y1kf (t)和Y2 (t)4）演示（e:\paper12）4.1.3 区域经济系统Agent模拟见文件。

4.2 元胞自动机模拟4.2.1 元胞自动机的定义[9]元胞自动机（Cellular Automata，简称CA，也有人译为细胞自动机、点格自动机、分子自动机或单元自动机），是时间、空间和状态都按离散方式变化的动力系统散布在珊格（Lattice）中的每个元胞（Cell）取有限的离散状态，遵循同样的相互作用规则，同步更新各自的状态元胞之间的相互作用规则是简单的，但通过简单的相互作用确能够导致系统整体行为的动态演化具体讲，构成元胞自动机的部件被称为“元胞”，每个元胞具有一个状态这个状态只能取某个有限状态集中的一个，例如“生”或“死”、或者是256中颜色中的一种等等这些元胞规则地排列在被称为“元胞空间”的空间格网（Lattice Grid）上它们各自的状态随着时间变化，而根据一个局部规则进行更新，也就是说，一个元胞在某时刻的状态取决于上一时刻该元胞的状态、以及该元胞的所有邻居元胞的状态每个元胞依照这样的局部规则进行同步的状态更新，整个元胞空间则表现为在离散的时间维上的变化4.2.2 元胞自动机的组成[9]元胞自动机最基本的组成为元胞、元胞空间、邻居及规则四部分如图1.4.5所示图1.4.5 元胞自动机的组成1）元胞元胞又可称为单元、或基元，是元胞自动机的最基本的组成部分。

元胞分布在离散的一维、二维或多维空间上2）状态状态可以是{0,1}的二进制形式，或是{s0, s2, …, si, …, sk}整数形式的离散集3）元胞空间处于分布状态的元胞空间网点集合就是元胞空间这里涉及到几个概念：（1）元胞空间的几何划分理论上，它可以是任意维数的欧几里德空间规则划分目前研究多集中在一维和二维元胞自动机上对于最为常见的二维元胞自动机，二维元胞空间通常可按三角、四方或六边形三种网格排列，如图1.4.6所示 (a)三角网格 (b)四边网格 (c)六边网格图1.4.6 二维元胞机的三种网格划分（2）边界条件在理论上，元胞空间通常是在各维方向上是无限延展的，这有利于在理论上的推理和研究但是在实际应用过程中，我们无法在计算机上实现这一理想条件，因此，我们需要定义不同的边界条件3）构形是在某个时刻，在元胞空间上所有元胞状态的空间分布组合4）邻居（Neighbor）二维元胞自动机的邻居定义较为复杂，但通常有四种形式（以最常用的规则四方网格划分为例）：冯-诺依曼（Von Neumann）型、摩尔（Moore）型、扩展的摩尔（Moore）型和马哥勒斯（Margolus）型，前三种邻居模型如图1.4.8所示。

(a)Von Neumann型 (b)Moore型 (c)扩展的Moore型图1.4.8 元胞自动机的邻居模型5）规则（Rule）根据元胞当前状态及其邻居状况确定下一时刻该元胞状态的动力学函数，即状态转移函数，该函数可以记为：f：sit+1=f (sit, sNt)其中，sNt为t时刻的邻居状态组合，我们称f为元胞自动机的局部映射或局部规则6）时间（Time）元胞自动机是一个动态系统，它在时间维上的变化是离散的，即时间t是一个整数值，而且连续等间距假设时间间距dt = 1，若t = 0为初始时刻，那么t = 1为其下一时刻4.2.3 元胞自动机模拟示例[12]元胞自动机是一种开放的、通用的建模方法，其应用几乎涉及自然、社会、经济、管理等各个领域元胞自动机很适合于进行群体动力学的分析，下面以人群动力演化过程的模拟为例，介绍元胞自动机的运用1）民意集中模拟（1）问题当外界环境发生变化时，对于一群人如何应对环境的变化而言，在这群人里会产生多种不同的观点或意见，随着人群中个人和个人之间不断地交换意见，即随着时间的推移，意见的。