（计算机系统结构专业论文）基于元胞自动机的股票市场价格行为的研究.pdf

上海大学硕士学位论文 摘要 随着行为金融理论和复杂性磷究工具的兴起与发展，入们发现传统的有效 市场假说存在很多局限性，一般情况下是不成立的。股票价格收益是不稳定的 随机序列，收益分布不是正态分布，股票价格收益表现出非线性，廖刊宣相关 性等。越来越多的经济学家和物理学家致力于股票价格机制的研究并借助于复 杂性研究工具建立了许多模型。 最近，元胞自动机作为复杂系统和复杂性研究的重要工具已经得到了广泛 的应用。本文利用元胞巍动机结合模糊控制和随机过程理论，构建基于元胞盘 动机的股票市场模拟模型。 醛经有若干个模拟股票市场的元胞自动机模型被提出，它们都在不同侧西模 拟并解释了股票市场的某些特征。但是现有的基于元胞自动机模型的复杂性，难 戬清楚遣表明是模型中的那个因素产生了这些特点，并且也难以确定是否所有的 因素在解释这些特点上是必须的。本文在建立模型时采用嘲简到繁的3 个步骤， 在每一个步骤中加入影响股票市场的因素，最终建立模型。本文将投资者划分为 两类，重新定义了投资者属性，使之更加符合现实股票市场。 剥焉m a t l a b 对本文提出的模型进行了仿真模拟，数篷结果表明，该模型能 够很好地反映股票市场的一些非线性特征，如股票收益率的尖峰厚尾性、波动聚 集性、波动的长期记忆憔等。通过对3 个模型的仿真结果进行对比，分析了产生 这些特征的原因。利用本文所提出的模型，本文还研究了交易者比例不同的情况 下殷票市场的稳定性。 关键谰：元胞囊动机；模糊控制；随机过程；尖峰厚尾；波动聚集 v 上海大学硕：学位论文 a b s t r a c t i n f l u e n c e db yt h ed e v e l o p m e n ti nt h eb e h a v i o rf i n a n c ea n dt h et h e o r yo fc o m p l e x s y s t e m s ，p e o p l ef o u n d t h a te f f i c i e n tm a r k e th y p o t h e s i s ( e m h ) w a sn o tv a l i d s t o c k r e t u r n sa r eu n a b l es t o c h a s t i cs e r i e s t h ed i s t r i b u t i o no fs t o c kr e t u r n si sn o tg a u s s i a n d i s t r i b u t i o n s t o c kr e t u r n se x h i b i tc h a r a c t e r so fn o n 1 i n e a ra n da u t o e o r r e l a t i o n s m o r ea n dm o r ee c o n o m i s t sa n dp h y s i c i s t sh a v e b e e na t t r a c t e dt of i n d p r i c e m e c h a n i s m ，a n de s t a b l i s h e dal o to fm o d e l sb yu s i n gc o m p l e xs y s t e m st o o l s 。 i nr e c e n ty e a r s ，c e l l u l a ra u t o m a t a ( c a ) h a sb e e nu s e dw i d e l yt os t u d yc o m p l e x s y s t e m s i nt h i sp a p e r , w ee s t a b l i s ht h es t o c km a r k e tb a s e do nc e l l u l a ra u m m m a w i t hf u z z yr e a s o n i n ga n ds t o c h a s t i cp r o c e s s m a n ys t o c km a r k e tm o d e l sb a s e do nc e l l u l a ra u t o m a t ah a db e e np r o p o s e d t h e y e x p l a i ns o m ec h a r a c t e r so fs t o c km a r k e tf r o md i f f e r e n tp o i n t so fv i e w b u tw ec a n n o t k n o ww h i c hf a c t o rb r i n g st h ec h a r a c t e r sa n dw h i c hf a c t o ri si n t e g r a n t i nt h i sp a p e r , w ee s t a b l i s ht h es t o c km a r k e tm o d e lf r o ms i m p l et oc o m p l e x 。w ed i v i d et r a d e s p a r t i c i p a t ei nt h et r a d i n gi l l t ot w og r o u p sa n dr e d e f i n en e wa t t r i b u t e st om a k ei tf i t f o rr e a ls t o c km a r k e t t h ec o m p u t e rs i m u l a t i o no fo u rm o d e l si sp r o v i d e db yu s i n gm a t l a bi nt h i sp a p e r i tp r o v e st h a tt h em o d e l sc a nd e s c r i b en o n l i n e a rc h a r a c t e r so fs h a r em a r k e tv e r y w e l l ，e g ：融t a i l s ，v o l a t i l i t yd u s t e r b yc o m p a r i s o no fs i m u l a t i o no f t h r e em o d e l s ，w e h a v ec o n c l u d e dt h er e a s o n sw h yt h ec h a r a c t e r se x i s t 。i nt h i sp a p e r , t h er e s e a r c ho f s t a b l ec h a r a c t e ri ns h a r em a r k e ti sa l s og i v e ni nd i f f e r e n td e a l e rp r o p o r t i o n s 。 k e y w o r d s ：c e l l u l a ra u t o m a t a ；f u z z yr e a s o n i n g ；s t o c h a s t i cp r o c e s s ；f a tt a i l s ； v o l a t i l i t yc l u s t e r v i 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：j l 鞋牵le t 期：- 趔氆4 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 1 1 年隰斟 j ：海大学硕：l ：学位论文 1 。1 课题的背景 1绪论 有效市场假说( e f f i c i e n tm a r k e th y p o t h e s i s ，e m l l ) ，在现代证券理论中 占有重要的位置，它认为股价能反映所有的相关信息。即使股价在短期内可能 偏离股票的基本价值，但随着时间的流逝，投资者获取的信息越来越全恧，股 价最终必定回归其基本价值。e m i t 假定投资者都是理性的，有秩序和有条理的。 由于投资者对新信息立即做出反应，所有的信息都反映在价格变化中，每天的 价格行为只同当前的信息有关，而与以前的价格无关，因而价格是独立的随机 变量，当投资者足够多的时候，收益率分布趋于歪态分布。 但是，随着金融市场的发展和非线性理论7 叫的广泛应用，人们发现越来 越多的现象已经无法在有效市场假说的糕架下得到合理的解释。曼德尔布罗特 ( b b m a n d e l b r o t ) 在1 9 6 3 年指比股票收益分布严重偏离有效市场假说下的高 靳分布，呈现尖蜂肥尾的特征，两且收益率序列还呈现出长期相关性。曼德尔 布罗特据此提出了股票价格的“诺亚效应 ( n o a he f i e c t ) 和“约瑟效应 ( t o s c p h e f f e c t ) 。所谓“诺亚效应是指股票徐格偶尔会发生不连续，突发性的大跳跃， 并且在一个大跳跃后面常跟着一个大跳跃，在一个小跳跃后面常跟着一个小跳 跃，这就是蜃采在金融学中常说的波动聚集( v o l a t i l i t yc l u s t e r ) 现象，常常导 致股票收益的分布出现尖峰肥尾的现象，而不是有效市场假说的正态分布。“约 瑟效巍 是指股票价格存在长麓持续与嚣周期的循环现象，这导致收益存在长 期相关性。越来越多的研究表明，金融价格时间序列存在着丰富的内在特征和 结构，如不同尺度的时阚相关性和宣相似特性等，这些都是复杂性的典型特征。 这些发现吸引了国内外很多物理学家、经济学家探索金融市场的运行规律，其 中，基于菲线性动力学的金融毒场演化机制研究是近年来的热点课题，同时也 是复杂性研究的一个重要方向。 1 2 国内外研究现状 麓翁，金融市场的菲线性动力学特征研究主要集中在两个方| 向上：第一是 对金融市场是否存在分形、混沌等非线性特征的检验以及检验方法的研究；第 上海大学硕：l 学位论文 二是建立非线性动力学模型来描述金融价格的动态演变过程，探询金融市场价 格波动行为的是形成机理。 前者是对金融市场的价格是否具有混沌分形特征进行有关的统计检验，这 也是当前股票市场非线性研究的热点。这些检验包括长期记忆与r s 分析，b d s 检验、l y a p u n o v 指数检验和标度理论等。然而这方面的工作仅限于给出实际数 据检验金融市场是否具有自相似性、混沌和标度不变性等菲线性特征的证据， 缺乏对其产生原因的深入分析，因丽难以真正揭示其菲线性结构。 后者通过大量的研究发现，产生波动聚集及j # 周期循环现象的原因是由于 多个单元的相互作用形成的，也就是所谓的“羊群效应”，基于这个思想建立了 一些相应的多主体模型，包括争当少数者博弈模型、渗透模型、旋转模型，以 及其它金融市场微观结构模型。其中以c o n t ，b o u c h a u d 模型( c b 模型) 1 l 、 l u x m a r c h e s i 模型( l m 模型) 2 - 3 最为著名。 t h o m a sl u x 与m i c h e l em a r c h e s i 设计了一个随机的多经理入模型。在此模 型中，所有的交易者被分成两群，群入遵德有效市场假设，认为资产的榆格 是瞧其基本值决定的。所谓基本值是资产未来被期待的利润摄成现值所造成的 该资产的价值，这群人被称为基本派( f u n d a m e n t a l i s t ) 。另一群人不相信价 格有立即恢复为基本值的倾向，他们认为价格是由价格的倾向，价格的发展以 及其他交易者的行为所决定的。他们由“技术面 来判断价格的变化。由于他 们考虑别人的行为以致常常会造成群聚( h e r d i n g ) 现象，这一群入被称为“哄 传交易者 或“噪声交易者”( n o i s e 螽赫e r ) 。哄传交易者又分为乐观派与悲观 派。在这模型中，有趣的动态行为是圭个别交易者在不同群之间变换角色促成 的。角色变换是虫基本僮改变的外在原因及交易者市场操作的内在原因一起造 成的。此模型明确地定义角色切换的机率，这个机率随着时间作改变。角色变 换，价格改变以及基本值改变所假设的细节在此略去。 c b 模型是成功地将渝渗理论用于金融系统建模的一个模型，它提出的羊群 效应是产生肥尾和股市泡沫的主要原因。在该模型中，网络上的每一个点代表 一位投资者，每一步迭代时，以一定的概率使任意两格点之间相连的边成为连 逶边，连通的格点形成一个簇。每个簇被看成是意见一致著采取相同投资行为 的投资团体，其参与交易的概率为2 露，其中买入概率、卖出概率均为a ，处于 2 上海大学硕士学位论文 观望状态的概率为l 一2 口，交易的量与簇的规模s 成正比，收益率为： a p 芘5 珂；一s 巧l _4 - - 一 js 其中，甩j 表示规模为s 处于买入状态的簇的个数，酊表示规模为s 处于卖出的 状态的簇的个数，即价格是由供求关系之间的差异所决定的。 上述这些模型的一个共同特点是，摒弃了经典金融研究中简化的典型的理 性人假设，将其建立在投资者是有限理性的基础上，然而这些模型很少着眼于 多个体行为互动以及整体行为在时间和空间上的相互关联。每个经济个体，都 处在它们所共同创生的整体经济模式中，并对该模式进行反应和适应。当个体 作出反应，整体模式会变化；当整体模式变化，个体重新作出反应。这样，经 济系统一直处在随时间不断地演化和展现的过程中，而不是达到某种定态或均 衡点。而且，经济个体在对整体经济模式的反应中会预测他们所采取行为的后 果，并采取相应的策略行动，这些预测和策略行为会使经济个体互动和整体模 式创生更具有复杂性。 1 3 研究目标和内容 ( 1 ) 在跟踪国内外股票市场复杂性研究及建模基础上，构建新的基于元胞 自动机的股票市场模型； ( 2 ) 利用m a t l a b 对所建的股票市场模型进行仿真模拟，描述股票价格行为 特点； ( 3 ) 利用仿真的数值结果，分析产生股票价格行为特点可能的原因： ( 4 ) 为股票市场价格预测提供可借鉴的理论模型。 1 4 创新点 ( 1 ) 已经有若干个模拟股票市场的元胞自动机模型被提出，它们都在不同侧 面模拟并解释了股票市场的某些特征。但是现有的基于元胞自动机模型的复杂 性，难以清楚地表明是模型中的那个因素产生了这些特点，并且也难以确定是否 所有的因素在解释这些特点上是必须的。 对此，本文提出一个尽可能简单的元胞自动机模型，通过元胞的相互作用和 简单规则来模拟并解释主要的特点。为了尽可能简单而清楚地说明几种不同的因 上海大学硕j ：学位论文 素所产生的相应特征现象，本文在建立模型时采用由简到繁逐步的3 个步骤，逐 步加入影响股票市场的因素，最终得出模型。利用m a t l a b 软件，对每一个步骤 建立的模型都通过计算机进行模拟，并对模拟仿真结果进行分析，确定那些因素 可以解释股票市场的某些特征。 ( 2 ) 重新诠释股票市场的投资者的属性。本文对投资者划分为两类，一类是 基于基本面交易的投资者，一类是模仿者。在初等模型中，对这两类投资者的定 义等同于其他元胞自动机中对投资者的定义。但是在现实股票市场中，每个投资 者并不是确切的基于基本面交易的投资者或是模仿者，他们或多或少都会受股市 中的消息以及历史价格波动的影响，所以我们在含有消息因素的模型及含有价格 波动的模型中，把消息因素和价格波动因素加入投资者的交易规则中。因此，本 文定义的基于基本面交易的投资者和模仿者并不是传统意义的两类投资者，更加 符合股票市场的现实性，并且为股票市场微观结构的研究提供了一个新思路。 ( 3 ) 股票市场的演化存在许多不确定因素，使得系统的演化过程随机性与模 糊性并存。本文将模糊控制、随机过程与元胞自动机结合起来，把系统演化需要 的某些参数模糊化，演化规则随机化。因此模型更加符合系统演化的不规则、不 确定的特征。 1 5 研究意义 ( 1 ) 从简到繁建立模型，研究股票市场，更加清晰地分析股票市场的特征 和规律。 ( 2 ) 重新诠释股票市场的投资者属性，由于投资者对市场复杂性的认识、 情绪和信息形式的不同，其决策过程大相径庭。对这个问题的研究有助于理解 股票市场价格的形成过程。 ( 3 ) 将元胞自动机原理与模糊控制、随机过程相结合，不但可以更好的处 理经济系统中不确定的问题，而且使元胞自动机更加智能化。将其应用到股票 市场的模拟中，更加符合实际情况。 1 6 本文的组织结构 第一章“绪论”：介绍了课题背景、国内外现状、研究目标和内容、创新点 及研究意义。 4 上海大学硕上学位论文 第二章“元胞自动机 ：主要是对元胞自动机理论、模型以及在经济系统中 的应用作介绍。 第三章“基于元胞自动机的股票市场模型”：首先介绍了有效市场假说理论 并分析了有效市场假说的局限性：然后从简到繁建立基于元胞自动机的模型； 最后利用m a t l a b 对每一个步骤所建立的模型进行模拟仿真。 第四章“数值结果分析”：根据仿真结果及其数值分析，对股票市场中的某 些特征进行分析。 第五章“结论与展望”：对全文进行总结，论述基于本文所建立的模型在今 后的发展方向和灵活性方面的思考。 5 j ：海大学硕士学位论文 2 元胞自动机 元胞自动机是2 0 世纪4 0 5 0 年代由冯诺依曼( y o nn e u m a n n ) 提出的f 鞠。 为了模拟生物学中的自我复制行为并且能在计算机上得以实现，冯诺依曼提 出了一个简荤的模式，即把一个长方形平面分成若干个网格，每一个格点表示 一个元臌或一个基本单元，其状态赋值为0 或1 ，对应予网格中的空格和实格， 在事先设定的局部规则下，网格中的空格和实格按一定的规律进行演化，这就 是元胞囱动机。 2 。1 元胞自动机的理论基础 2 1 董元胞自动枧的概念 尽管元胞自动机有着比较宽松，甚至近乎模糊的构成条件。但它作为一个数 学模型，元胞自动机有羲严格的科学定义。同时，元胞囊动机原理及应用涉及多 学科交叉，众多物理学家、数学家，计算机科学家和生物学家为其作出了贡献。 因此，对元胞自动机的含义也存在不同的解释。下面仪从几个方面对它描述【9 】： 数学：与描述连续现象的偏微分方程不同，它是一个时空离散的数学模型。 计算机科学：新兴的人工智能、人工生命的分支。 生物学；生命现象的一种抽象。 物理学：具有离散、有限状态的元胞组成的元胞空间上，并按照一定局部规 则，在离散的时闻维上演化的动力学系统。 2 1 。2 元胞自动机的构成 元脆自动机由如下最基本4 部分组成：元胞、元胞空闻、邻屠及规则。简单 讲，元胞自动机可以视为女一个元胞空闻和定义于该空闻的变换露数所组成【1 0 1 。 其构成见图2 1 ： 6 上海大学硕士学位论文 i 规则变换函数 么 3 图2 - 1 元胞自动机的构成 1 元胞 元胞又可称为单元( 或基元) ，是元胞自动机的最基本的组成部分。元胞分 布在离散的一维、二维或多维欧几里德空间的晶格点上。 2 状态 状态可以是 o ，1 ) 的二进制形式。或是冬。，s ：，s 一，s 。) 整数形式的离散集， 一般地，元胞自动机的的每个元胞只有一个状态变量。但在实际应用中，往往将 其进行了扩展，可能使每个元胞可以拥有多个状态变量。 3 元胞空间( l a t t i c e ) 元胞所分布在的空间网点集合就是这里的元胞空间。 ( 1 ) 元胞空间的几何划分 理论上，它可以是任意维数的欧几里德空间规则划分。目前研究多集中在 一维和二维元胞自动机上。对于一维元抱自动机。元胞空间的划分只有一种。 而高维的元胞自动机。元胞空间的划分则可能有多种形式。对于最为常见的二 维元胞自动机，二维元胞空间通常可按三角、四方网格等排列，见图2 2 。 a 三角网格b 四方网格 图2 - 2 元胞空间的几何划分 上海大学硕上学位论文 ( 2 ) 边界条件 在理论上，元胞空间通常在各维的方向上是无限延展的，这有利于在理论 上的推理和研究。但是在实际应用过程中，我们无法在计算机上实现这一理想 条件，因此，我们需要定义不同的边界条件。归纳起来，边界条件丰要有三种 类型：周期型、反射型和定值型。有时，在应用中，为更加客观、自然地模拟 实际现象，还有可能采用随机型，即在边界实时产牛随机值。 周期型( p e r i o d i cb o u n d a r y ) 是指相对边界连接起来的元胞空问。对于一维空 间，元胞空间表现为一个首尾相接的“圈”。对于二维空间，上下相接，左右相 接。而形成一个拓扑圆环面( t o m s ) ，形似车胎或甜点圈。周期型空问与无限空 间最为接近，因而在理论探讨时，常以此类边界条件进行数值实验。 反射型( r e f l e c t i v eb o u n d a r y ) 指在边界外邻居的元胞状态是以边界为轴的镜 面反射。例如在一维空间中，当r = l 时的边界情形，见图2 3 ： 图2 - 3 边界处理 定值型( c o n s t a n tb o u n d a r y ) 指所有边界外元胞均取某一固定常量，如o 或 1 等。 需要指出的是，这三种边界类型在实际应用中，尤其是二维或更高维数的 构模时，可以相互结合。如在二维空间中，上下边界采用反射型，左右边界可 采用周期型。 ( 3 ) 构形 在这个元胞、状态、元胞空间的概念基础上，我们引入另外一个非常重要 的概念，构形( c o n f i g u r a t i o n ) 。构形是在某个时刻，在元胞空间上所有元胞状态 的空间分布组合。通常，在数学上，它可以表示为一个多维的整数矩阵。一维 元胞自动机在f 时刻的构形可表示为 s 。= ( 一，s ；，) 其中_ ，表示空间位置 8 上海大学硕十学位论文 4 邻居( n e i g h b o r ) 以上的元胞及元胞空间只表示了系统的静态成分，为将“动态”引入系统， 必须加入演化规则。在元胞自动机中，这些规则是定义在空间局部范围内的， 即一个元胞下一时刻的状态决定于本身状态和它的邻居元胞的状态。因而，在 指定规则之前，必须定义一定的邻居规则，明确哪些元胞属于该元胞的邻居。 在一维元胞自动机中，通常以半径，来确定邻居，距一个元胞距离在，内的所 有元胞均被认为是该元胞的邻居。二维元胞自动机的邻居定义较为复杂，但通 常有以下几种形式( 以最常用的规则四方网格划分为例) 。见图2 4 ，黑色元胞为 中心元胞，灰色元胞为其邻居，它们的状态一起来计算中心元胞在下一时刻的 状态。 ( 1 ) v o nn e u m a n n 型( 2 ) m o o r e( 3 ) 扩展m o o r e 图2 4 元胞自动机的邻居 ( 1 ) 冯诺依曼( v o nn e u m a n n ) 型 一个元胞的上、下、芹、右相邻四个元胞为该元胞的邻居。这里，邻居半 径，为1 ，相当于图像处理中的四邻域、四方向。 ( 2 ) 摩尔( m o o r e ) 型 一个元胞的上、下、左、右、左上、右上、右下、左下相邻八个元胞为该 元胞的邻居。邻居半径，同样为1 ，相当于图像处理中的八邻域、八方向。 ( 3 ) 扩展的摩尔( m o o r e ) 型 将以上的邻居半径，扩展为2 或者更大，即得到所谓扩展的摩尔型邻居。 ( 4 ) 马哥勒斯( m a r g o l u s ) 型 这是一种同以上邻居模型迥然不同的邻居类型，它是每次将一个2 2 的元 胞块做统一处理，而上述前三种邻居模型中，每个元胞是分别处理的。这种元 胞自动机邻居是由于格子气的成功应用而受到人们关注的。 9 上海大学硕士学位论文 5 。规刚( r u l e ) 根据元胞当f j 状态及其邻居状况确定下一时刻该元胞状态的动力学函数。简 单讲，就是一个状态转移送数。我们将一个元匏的所有可能状态连网负责该元愆 的状态变换的规则一起称为一个变换函数。这个函数构造了一种简单的、离散的 空间时闻豹局部物理成分。要修改篦范圈里采焉这个局部物理成分对其结构的 “元胞 重复修改。这样，尽管物理结构的木身每次都不发展。但是状态在变化。 可以记为： f t ”= 厂( s ；，) i 力参时亥的邻居f 的状态组合，称厂为元胞鲁动机的局部映射或局部规则。 6 。时间( t i m e ) 元胞自动机是一个动态系统，它在时间维上的变化是离散的，醚p 时间芒是一 个整数值，丽且连续等间距。假设时间间距a t = l ，若t ：0 为初始时刻。那么。 t = l 为其下一时刻。在上述转换函数中，个元胞在t + l 时刻的状态直接决定于 t 时刻的该元胞及其邻居元胞的状态，在卜1 时刻的元胞及其邻居元胞的状态闻 接( 时问上的滞后) 影响了元胞在t + l 的时刻的状态。 由以上砖元胞自动机的组成分析，我们可以更加深入地理解元胞自动机的 概念。用数学符号来表示，标准的元胞自动机是一个四元组： a = ( 厶，s ，n ，f ) 这里a 代表一个元胞自动机系统：厶表示元胞空间，d 是一正整数，表示元 胞鲁动枧内元胞空| 、曩的维数；s 是元胞的有戳的、离散的状态集合；表示个 所有邻域内元胞的组合( 包括中心元胞) ，即包含7 个不同元胞状态的一个空问矢 量，记为： = ( s 。，s 2 ，s n ) ，n 是元胞的邻居个数，墨z ( 整数集合) ，f l ，2 ，n ) 。 ，表示将s 欧射n s 上的一个局部转换函数。所有的元胞位于d 维空闻上， 其位髓可用一个d 元的整数矩阵z d 来确定。 2 1 3 元胞自动机的一般特征 1 同质性、齐性 同质性反映在元胞空间内的每个元胞的变化都服从相同的规律，h 口元胞自动 机的规则，或称为转换函数。 1 0 上海大学硕士学位论文 齐性指元胞的分布方式相同，大小、形状福霹，空闻分布规则整齐。 2 空间离散 元脆分布在按照一定规则划分的离散翡元胞空闻上。 3 时间离散 系统的演化是按照等问隰时闻分步进行的，时瓣变量t 只能取等步长的时 刻点，形似整数形式的t ，t + l ，t + 2 ，。而且，t 时刻的状态构形只对其下 时刻，郄毋l 时刻的状态构形产生影响，丽壮2 时刻的状态构形完全决定于转羔 的状态构形及定义在上面的转换函数。元胞自动机的时间变量区别于微分方程 中的时间变量t ，那里手通常是个连续值变量。 4 状态离散有限 元胞自动器的状态只能取有限( 茚个离散值g 。，s ：，s 。) 。相对于连续状态 的动力系统，它不需要经过褪粒化处理就能转化为符号序列。两在实际应用中， 往律需要将有些连续变量进行离散化，如分类，分级，以便于建立元胞自动机 模型。 5 同步计算( 并行性) 各个元胞的在时刻友+ l 的状态变化是独立的行为，相瓦没有任何影响。若 将元胞自动机的构形变化看成是对数据或信息的计算或处理，则元胞自动机的 处理是同步进行的，特别适合于并行计算。 6 时空局部性 每一个元臆的下一时刻p l 的状态，取决于其闳墨半径为r 的邻域( 或者其 它形式邻居规则定义下的邻域) 中的元胞的当前时刻t 的状态，即所谓时间、空 闻的嗣部性。从信息传输的角度来看，元胞自动枫中信息的传递速度是有限的。 7 维数高 在动力系统中一般将变量的个数称为维数。例如，将区间映鸯季生成的动力 系统称为一维动力系统；将平面映射生成的动力系统称为二维动力系统；对于 偏微分方程描述的动力系统则称为无穷维动力系统。从这个角度来看，由予任 何完备元胞自动机的元胞空间是定义在维、二维或多维空间上的无限集，每 个元胞的状态便是这个动力学系统的变量。因此，元胞自动机是一类无穷维动 力系统。在具体应用中或计算机模拟时当然不可能处理无限个变量，但一股也 上海大学硕士学位论文 总是处理数量很大的元胞组成的系统。因此可以说维数高是元胞自动机研究中 的一个特点 1 2 】。 2 1 4 元胞自动机的分类 元胞自动机的分类目前尚未有一个统一的标准，但是基于不同的出发点， 元胞自动机可以有很多分类。其中，最简单和最常用的划分方法是基于空间维 数的元胞自动机的分类【i l 】。 理论上，元胞自动机是可以任意维数的，但实际上，通常分为： 1 一维元胞自动机 元胞等间隔方式分布在一条向两侧无限延伸的直线上，每个元胞具有有限 个状态j ，s s = 冬。，s ：，j 。) ，定义邻居半径，元胞的左右两侧共有2 r 个元 胞作为其邻居集合。现阶段，对于元胞自动机的理论研究多集中在一维元胞 自动机上。 2 二维元胞自动机 元胞分布在二维欧几里德平面上规则划分的网格( 方格) 点上。现在的多 数应用模型都是二维元胞自动机模型，它的应用最为广泛。 3 三维元胞自动机 是一维和二维元胞自动机的拓展，元胞分布在三维欧几里德空间上规则划 分的网格点上。 4 高维元胞自动机 有些理论探讨，实际应用的系统模型很少。 s w o l f r a m 在8 0 年代初进行的基于动力学行为的元胞自动机分类是最具影 响力的。他在大量的计算机实验的基础上，将所有元胞自动机的动力学行为归 纳为四大类： ( 1 ) 平稳型 自任何初始状态开始，经过一定时间演化后，元胞空间趋于一个空间平稳 的构形，这里空间平稳即指每一个元胞处于固定状态，不随时间变化而变化。 ( 2 ) 周期型 经过一定时间演化后，元胞空间趋于一系列简单的固定结构或周期结构。 ( 3 ) 混沌型 1 2 上海大学硕士学位论文 自仟何初始状态开始，经过一定时f h j 演化后，元胞自动机表现出混沌的非 周期行为，所牛成的结构的统计特征不明显，通常表现为分形分维特征。 ( 4 ) 复杂型 出现复杂的局部结构，或局部的混沌，其中有些会不断地传播。 另外，按照元胞自动机的元胞空间可以分为有限元胞自动机和无限元胞自 动机：根据状态函数地不同可以分为b o o l e a n 元胞自动机和t h r e s h o u l d 元胞自 动机；按照元胞状态的演化方式可以分为有串行元胞自动机和并行元胞自动机 等等。 2 2 元胞自动机的模型 元胞自动机是在有限元胞自动机基础上发展起来的，用于模拟和分析几何 空间内的各种现象。在元胞自动机的发展过程中，科学家们构造了各种各样的 元胞自动机模型【13 1 。其中，以下几个典型模型对元胞自动机的理论方法的研究 起到了极大的推动作用，因此，它们又被认为是元胞自动机发展历程中的几个 里程碑。 2 2 1s w o l f r a m 初等元胞自动机 初等元胞自动机( e l e m e n t a r yc e ll u l a ra u t o m a t a ，简记e c a ) 是状态s 只 有两个元素 s 。，岛) ，即状态个数七= 2 ，邻居半径，= l 的一维元胞自动机。 它几乎是最简单的元胞自动机模型。由于在5 中具体采用什么符号并不重要， 它可取 0 ，1 ) ， 一1 ，1 ) ， 静止，运动) ， 黑，白) ， 生，死) 等等，这里重 要的是s 所含的符号个数，通常我们将其记为 0 ，1 ) 。此时，邻居集的个数 2 ，一2 ，局部映射f ：s s 可记为： s ，1 = 厂 三_ 。，s ；，s 0 。) 其中变量有三个，每个变量取两个状态值，那么就有2 2 2 - - 8 种组合， 只要给出在这8 个自变量组合上的值，f 就完全确定了。例如以下映射便是其 中的一个规则： 1 1l1 1 01 0 11 0 00 1 10 1 00 0 l0 0 0 豺110o1100l 通常这种规则也可表示为以f 图形方式( 黑色方块代表l ，白色方块代表 0 ) 如图25 表示： t ：一叩一_ 口l 甲ii 口口口叩口口口严口甲 一：自自自自 图2 - 5 规则1 5 3 ( 1 0 0 1 1 0 0 1 ) 这样，对于仟何一个一维的o ，l 序列，应用以上规则，可以j ”乍下 时 刻的相应的序列。以r 序列就是应用以上规则j 。十的： f ：0 0 0 0 0 1 0 1 0 1 0 0 0 1 1 1 0 1 1 1 0 1 1 l 以上8 种组合分别对应0 或l ，i 捌而这样的蛐合j e 有2 8 = 2 5 6 种，即初等元 胞门动机只u ，能有2 5 6 种小同规则。s w u lr ra l l 】定义山上述8 种邻域状态产牛 的8 个结果缨成一个二进制( 沣意高低位顺序) ，如上u r 得1 0 0 1 1 0 0 1 ，然后讣算 它的十进制值r + 1 = 7 r = s x 2 = 1 5 3 j 厅在 0 ，2 5 5 内，sw o l f r a m 定义r 为初等元胞自动机的编号，则上面的 元胞门动机模型就是1 5 3 号初等元胞a 动机，其演化如图2 - 6 所不： 普：j 、；- 二 图2 - 61 5 3 号元胞自动机的演化 上海大攀硕士学位论文 s w o l f r a m 对这2 5 6 种模型一进行了详细蕊深入的研究。研究表明，尽 管初等元胞自动机是如此简单，但它们表现出各种各样的高度复杂的空间形态。 经过一定时间的演化，有些元胞国动机牛成一种稳定状态，或静止，或产生周 期性结构；有些产牛自组织、自相似的分形结构。s w o l f r a m ( 1 9 8 3 ) 借用分形 理论计算了它们的维数约为1 5 9 或l 。 s w o l f r a m 对一维元胞自动机，尤其是初等元胞自动机的深入研究奠定了 元胞翔动机理论的基石。对元您警动机的理论研究，以及恁来的人工生命研究 和近来兴起的复杂性科学( s c i e n c eo fc o m p l e x i t y ) 研究做出了卓越的贡献。 2 2 2 毒。c o n w a y 和“生命游戏劳 牛命游戏( g a m eo fl i f e ) 是j h c o n w a y 在2 0 世纪6 0 年代末设计的一 种单人玩的计算机游戏。它与我匿韵隧棋游戏在莱些特征上略有相似： 围棋中仪有黑白两种棋子，牛命游戏中的元胞有 “生，“死 两个状 态；隧棋的棋盘是规粪雩划分麴网格，黑自两子在空闷的分布决定双方的死活， 而牛命游戏也是规则划分的网格。根据元胞的局部空间构形来决定牛死。只不 过规剃更为简单。下瑟分绍生命游戏的构成及规则： ( 1 ) 元胞分布在规则划分的网格上； ( 2 ) 元胞熬有0 ，l 两种状态，0 代表“死”，l 代表“牛 ； ( 3 ) 元胞以相邻的8 个元胞为邻居，即m o o r e 邻居形式： ( | 唾) 一个元脆的牛死由其窿该时刻本身酶牛死状态和周围夕个邻詹的状态 ( 确切讲是状态的和) 决定。 尽管它的规则看上去很简单。但生命游戏是具有产牛动态图案和动态结构 能力的元胞自动机模型。它能产牛丰富的、有趣的图案。牛命游戏的优化与初 始元胞状态值的分布有关，绘定任意的初始状态分布。经过若干步的运算，有 的图案会很快消失。而有的图案则圃定不动，有的周而复始重复两个或几个图 案，有的蜿蜒而行。有的则保持图案定| 幻移动，形似阅兵阵，其中最为著 名的是“滑翔机( g 1 i d e r ) ”的图案。 生命游戏模型已在多方面得到应用，其演化规则近似地描述了牛物群体的 生存繁殖规律：在牛命密度过小( 相邻元胞数之2 ) 时，由于孤单、缺乏配种繁殖 机会、缺乏瓦助也会出现牛命危机，元胞状态值由l 变为0 ；在牛命密度过大( 相 1 5 上海大学硕士学位论文 邻元胞数 3 ) 时，由于环境恶化、资源短缺以及相互竞争而出现牛存危机，元 胞状态值由1 变为0 ；只有处于个体适中( 相邻元胞数为2 或3 ) 位置的牛物才 能牛存( 保持元胞的状态值为1 ) 和繁衍后代( 元胞状态值由0 变为1 ) 。正由于 它能够模拟牛命活动中的牛存、灭绝、竞争等等复杂现象，因而得名“牛命游 戏”。j h c o n w a y 还证明，元胞自动机具有通用图灵机的计算能力，与图灵机 等价，也就是说给定适当的初始条件，元胞自动机模型能够模拟任何一种计算 机。 2 2 3 格子气自动机 格子气自动机( l a t t i c eg a sa u t o m a t a ，l g a ) ，是元胞自动机在流体力学与 统计物理中的具体化，也是元胞自动机在科学研究领域成功应朋的范例。相对 于“生命游戏”来说，格子气自动机更注重于模型的实用性。它利用元胞自动 机的动态特征，来模拟流体粒子的运动。 第一个时空、速度等变量完全离散的格子气自动机是1 9 7 3 年由法围的j h a r d y , yp o m e a u 和op a z z i s 提出的h p p 模型，该模型的模拟结果已经很接近 流体力学中描述流体运动的n a v i e r - s t r o k e s 方程。但模型中的流体粒子的运动只 允许有四个方向，造成应力张量各向异性的致命弱点，尚不能充分反映流体的 特征，因此在较长时问内没有受到足够的重视。直到2 0 世纪8 0 年代，sw o l f r a m 等人的研究工作使得元胞自动机理论产生了质的1 5 i 跃，同时也带动了格子气自 动机的进一步发展。1 9 8 6 年，法国的uf r i s h ，yp o m e a u 和美同的bh a s s l a c h e r 在h p p 模型的基础上提出了一个有实用价值的、基二f 六角彤网络的格子气自动 机模型，得名为f h p 模型，并证明该模型的宏观行为符合标准的n a v i e r - s t o k e s 方程。f h p 模型是第一个成功的格子气模型，并激发了研究格子气模型研究的 热潮，人们在几年内发表了数百篇论文，其中包括g e r h a r t ( 1 9 9 5 ) ，l i m ( 1 9 8 8 ) ， x i a o g u a n gw u ( 1 9 9 4 ) ，李元香( 1 9 9 1 ) 等人的进一步工作。在9 0 年代中后期，一 种被称为格子波尔兹曼方法( l a t t i c eb o l z m a n nm e t h o d ，l b m ) 的改进模型逐步 取代了原有的格子气模型。 应当说，格子气自动机是一种特殊的元胞自动机模型，或者说是一个扩展 的元胞自动机模型( e x t e n d e dc e l l u l a r a u t o m a t a ) 。以早期的格子气模型为例，描 述其特征如下： 1 6 上海大学硕上学位论文 ( 1 ) 由于流体粒子不会轻易从摸型空润中消失。即需满足质毒= 守恒，同时 还需满足动量守恒及能超守恒律。 ( 2 ) 格子气自动机的邻屠模誉通常采用m a r g u l o s 类型，邸它的规烫| j 是基于 一个2 2 的网格空间的。它的规则形似如图2 7 所示： 图2 7 格子气自动机的邻居模型 这里黑色球代表流体粒子，白色球代表空的元胞。可以看出，格子气自动 机不同于其它的元胞自动机模型，以一个元胞( 常被称为中心元胞) 为研究对象， 考虑其状态的转换，而是考虑包含四个元胞的一个四方块。 ( 3 ) 依照上述规则和邻居模型在计算完一次后，需要将这个2 2 的模板沿 对角方向滑动，再计算一次。那么，一个流体粒子的运动需要两步r 一盼l 一盼2 才能完成。 从时间和空间的角度看，格子气自动机相对其他的元胞自动机模型具有较 为独特的特征。格子气臼动机以及其后发展的格子b o l t z m a n n 方法作为一种特 殊类型的元胞融动机已成为计算流体动力学中的一个重要方法，具有广泛的应 用。 2 3 元胞自动机在经济系统研究中的应用 经济系统是一个复杂系统，它具有组成要素的系统性、状态的不确定一陡和 组成要素状态随时问演化的相互依赖性等基本特征。因而，描述复杂系统的元 胞自动机方法通常被应用于经济学的研究之中，构成非线性经济学的组成部分。 2 3 。l 在寡头垄断行力中的应用 2 0 世纪7 0 年代，在c o u r n o t ，b e t - r a n d 和e d g e w o r t h 关于寡头垄断经济模型 1 7 上海大学硕士学位论文 研究的基础l z ，c y e r t 和d e g r o o t 提出了适合于寡头垄断行为研究的新的经济模 型 14 1 。仿照一维元胞自动机的分布特征，并在周期边界条件限定下，他们把同 定数隧的公司看作是沿环形分布的格点。顾客对称地分布在公司周圈，链缃根 据两个公司公布的价格来决定它们从哪个邻近的公司购买商品。假定顾客有同 样的偏好，由于顾客是对称分布的，所以，每个公司面临翔同的竞争环境。 在完全短期行为的公司中，每个公司要使它的利润最大化，它们的价格决 策最终只依赖于它的邻居公司所提出的价格，缝 f l 翻邻屠公司一起分享鑫鸯躲 市场。在这里假设处于奇数位置的公司在第奇数个周期里调整它们的价格，处 于偶数位置的公司在第偶数个周期里调整它们的价格。在这模型中，时间和 公司的定价都是离散的，假设爿是在t 时刻第f 个公司的价格，公司下一时刻 的价格f “依赖f 该时刻相邻公司的定价，即： 彳”= 厂( 鼍，爱，) c y e r t 和d e g r o o t 的垄断竞争模跫是元胞自动机的早期应用，其设计的一维 元胞露动视模型对当时的垄断竞争行为研究有一定的借鉴意义；同时对元胞囱 动机囱身应用的发展也起到了重要作用。他们设计了一种特殊的一维元胞自动 机演化方式，因为它规定在奇数个时闯周期里，处于偶数位置的公蠲的价格保 持不变，在偶数个时间周期里处于奇数位置的公司的价格保持不变。可以认为 这是对元胞自动机同步性的一种扩展。很是从现实的角度来考虑这个模型，便 会发现其所设的元胞空间跟实际情况有很大的差距，因为在现实牛活中，每个 垄断公司的分布是平面型的，这时可以考虑用二维元胞自动机。另外，在制定 演化规则的同时，此模型没有考虑环境变量的影响，比如宏观的经济政策所施 加的影响。 2 3 ，2 在市场营销中的应用 市场中消费者的购灭行为往往受到其他消费者的影响，