下载文档原格式
基于元胞自动机的城市轨道交通定价双层规划李雪岩;李雪梅;李学伟【摘要】针对城市轨道交通建立了基于“通票”及“计程票”两种定价方式的双层规划模型;上层规划运用遗传算法对利润函数进行寻优;下层规划运用广义出行费用函数刻画乘客出行方式选择行为,并嵌入元胞遗传算法演化规则进行寻优.模拟结果显示:(1)乘客间的互动学习强度、对价格的敏感度是影响两种定价方式获利情况、对乘客分流情况的重要因素;(2)当乘客对票价的敏感度较低且学习进化行为较弱时,宜采用“通票”的定价方式;当乘客对票价的敏感度较高且学习进化行为较强时,宜采用“计程票”的定价方式.【期刊名称】《管理工程学报》【年(卷),期】2017(031)001【总页数】7页(P155-161)【关键词】城市轨道交通;票价;双层规划;元胞遗传算法【作者】李雪岩;李雪梅;李学伟【作者单位】北京交通大学经济管理学院,北京100044;北京交通大学经济管理学院,北京100044;北京交通大学经济管理学院,北京100044【正文语种】中文【中图分类】U231.92近年来，中国的城市轨道交通建设取得了长足的发展，继北京、上海、广州等特大城市形成城市轨道交通网后，一些经济较发达的大城市也先后启动了城市轨道交通项目。
从现阶段国内城市轨道交通的运营情况来看，大多数轨道交通线路在为居民提供出行便利的同时，也背上了沉重的财务负担，如何在保证服务质量的条件下实现收支平衡？解决这一问题，势必涉及到对轨道交通定价策略的优化以及对乘客出行需求的及时掌控。
交通运输系统是典型的复杂社会经济系统，其内部主体包括各级运营决策部门和广大乘客群体。
运营决策部门对所提供运输服务进行定价，以获取利润和满足乘客需求为目标，广大乘客是运输价格的承担者，以节省成本和满足出行需求为目标。
于是，定价成为运营商与乘客共同关注的问题。
目前有相当多学者在进行运价研究，有的研究侧重运营决策，有的研究侧重乘客需求，常常将二者分开来考虑。
元胞自动机应用概述元胞自动机的应用概述元胞自动机自产生以来被广泛地应用到社会、经济、军事和科学研究的各个领域。
到目前为止其应用领域涉及生物学、生态学、物理学、化学、交通科学、计算机科学、信息科学、地理、环境、社会学、军事学以及复杂性科学等。
下面我们将对元胞自动机在这些领域中的应用分别做简要介绍。
1.生物学领域：因为元胞自动机的设计思想本来就来源于生物学自繁殖的现象所以它在生物学上的应用更为自然而广泛。
例如元胞自动机用于肿瘤细胞的增长机理和过程模拟、人类大脑的机理探索、艾滋病病毒HIV的感染过程、自组织、自繁殖等生命现象的研究以及最新流行的克隆技术的研究等。
另外还可以用来模拟植物生长的过程。
2.物理学领域：在元胞自动机基础上发展出来的格子自动机和格子—波尔兹曼方法在计算机流体领域获得了巨大的成功。
其不仅能够解决传统流体力学计算方法所能解决的绝大多数问题并且在多孔介质、多相流、微小尺度方面具有其独特的优越性。
另外元胞自动机还被用来模拟雪花等枝晶的形成。
3.生态学领域：元胞自动机被用于兔子—草、鲨鱼—小鱼等生态系统动态变化过程的模拟展示出令人满意的动态效果元胞自动机成功的应用于蚂蚁的行走路径大雁、鱼类洄游等动物的群体行为的模拟另外基于元胞自动机模型的生物群落的扩散模拟也是当前的一个应用热点。
4.化学领域：通过模拟原子、分子等各种微观粒子在化学反应中的相互作用进而研究化学反应的过程。
5.交通科学领域：因为涉及到车辆、司机、行人、道路条件等因素以及它们之间的相互影响和联系交通系统通常被看做是一个多粒子构成的复杂巨系统。
元胞自动机在交通中的应用沿着两条主线展开：对城市交通流的研究；对城市交通网络的研究。
由于交通元素从本质上来说是离散的而元胞自动机又是一个完全离散化的模型所以用元胞自动机理论来研究交通问题具有独特的优越性。
另外20世纪80年代以来计算机水平日新月异的发展为元胞自动机的应用提供了强有力的支持。
因此在进入20世纪90年代以后元胞自动机在交通流理论研究领域中得到了广泛的应用。
基于量子细胞自动机的逻辑电路设计摘要：量子细胞自动机(Quantum Cellular Automata, QCA)的出现，让电子电路的器件的尺寸进一步缩小成为可能。
在量子细胞自动机电路研究的突破，将使微电子进入量子这个全新的领域之中。
当前量子细胞自动机的研究仅限于理论上的，它的物理实现还正在萌芽阶段。
本文的讨论只限于理论上的讨论，不考虑量子细胞自动机的物理实现方面的问题，或细胞自动机的物理实现方面所带来的问题。
本文主要阐述了如何通过使用matlab软件，合理构建元胞来搭建计数器，采用线与、基础门来搭建。
例如M门、非门、等。
关键字：量子细胞自动机计数器时钟脉冲引言：引言量子细胞自动机的概念的提出，预示着微电子领域将想一个全新的领域发展，即量子领域，但是目前的研究未能摆脱经典电路的概念，因为这是一个向着量子电路过度的时期。
本文中，本人首先介绍了有关量子细胞自动机的基础知识，包括：它产生的时代背景；元胞的基本原理及运用于微电子领域的一些过渡性的规定；用细胞自动机来进行逻辑电路设计的设计方法以及几种不同的设计方案；量子细胞自动机电路的仿真方法。
接着简要介绍了当前量子细胞自动机方面的一些已经完成的成果，他们是该邻域不同部分的具体内容，是量子电路的基本雏形。
可以说，从提出量子细胞自动机的方案，以QCA来描述经典的电路理论中的逻辑单元，通过时钟来保证计算的有序正确的进行，到最后的量子电路的仿真，都有其独特的特点。
其次，说明了近年来，单电子器件的研究与开发已成为国际的热点，国际上的一些物理学家创造了一种“量子点”，也就是说运用单个电子的存在与否及其所处的位置对信息进行编码，从而代替传统晶体管电路中用电平进行信息的加工处理。
正因如此，基于量子细胞自动机(Quantum-dot Cellular Automata, QCA)的器件应运而生，QCA是于1993 年由Lent 等最先提出的，它提供了一种新的计算和信息转换方式，具有低功耗、高集成度和无引线等优点，将会成为利用量子点进行计算的新技术[4]。
元胞自动机在城市扩展方面的应用综述摘要本文在介绍元胞自动机各要素的基础上，综述了元胞自动机用于城市扩展模拟的历史、元胞自动机用于城市扩展模拟的具体研究方向，即在具体的模型中如何确定模型的结构和参数，并对其未来的发展趋势进行了展望，并指出CA 中的转换规则的扩展是在将来的研究中的一个首要问题。
关键字：元胞自动机；城市扩展模拟；转换规则一引言元胞自动机(CA)是一种时间、空间、状态都离散,空间的相互作用及时间上的因果关系皆局部的网格动力学模型,其“自下而上”的研究思路,强大的复杂计算功能、固有的平行计算能力、高度动态以及具有空间概念等特征,使得它在模拟空间复杂系统的时空动态演变方面具有很强的能力。
在城市空间动态变化的模拟研究方面, CA模型已应用到除非洲、南极洲的所有大洲的城市模拟研究当中。
CA模型和GIS的集成,一方面增强GIS的空间模型运算及分析能力,另一方面, GIS提供的强大空间处理能力可以为CA模型准备数据和定义有效的元胞转换规则以及对模拟结果进行可视化。
同时CA模型还可以与神经网络、主成分分析、遗传算法、模糊逻辑以及其他研究方法相结合,以增强其在城市空间变化模拟研究方面的能力。
将CA与MAS技术相结合,建立一个能够模拟多个不同参与因子(自然系统) 、不同决策者(人文系统)共同影响下的城市发展模型,以此来模拟与预测城市发展的真实状况,将是CA模型在城市空间变化模拟与预测研究中的未来发展趋势。
国内元胞自动机应用研究起步较晚，受国际研究的推动，20世纪90年代末地理学界才开始类似的尝试研究，主要集中在基于元胞自动机的LUCC和城市增长模拟，罗平从经典地理过程分析的基本理论人手，分析和阐述了CA对于经典，地理过程分析概念的表达程度的局限性，综合地理系统的几何属性和非几何属性提出了基于地理特征概念的元胞自动机(GeoFeature 一CA)，周成虎等人在Batty和Xie的DUEM模型的基础上，构建了面向对象的、随机的、不同构的和两个CA模型耦合的GeoCA—Urban模型，并成功模拟了深圳特区土地利用动态演化过程。
收稿日期:2004-09-03基金项目:江西省自然科学基金资助项目(0250006);江西省科技厅资助项目作者简介:许林(1980-),男,硕士研究生. 文章编号:1006-0456(2005)02-0024-04一种用于微观组织模拟的三维元胞自动机模型许林a,郭洪民b,杨湘杰a(南昌大学a .机电工程学院,江西南昌330029;b .材料科学与工程学院,江西南昌330047) 摘要:元胞自动机是复杂体系的一种理想化模型,特别适合于处理那些难以用数学定量描述的复杂动态体系问题,如材料微观组织的演变模拟.它非常适合于计算机模拟实施.利用C ++计算机语言,运用OpenG L 图形函数库建立了一种三维元胞自动机模型.该模型具备了经典元胞自动机的基本特征,因此可以根据需要进行扩展.由于运用了OpenG L 的实时3D 技术使得模拟结果更加逼真,并可以从多角度进行观察.文中运用该模型进行了简化的枝晶生长模拟,并与二维的模拟结果进行比较,验证了该模拟的正确性.关键词:元胞自动机;三维建模;OpenG L 中图分类号:TP39119 文献标识码:A 元胞自动机(CA )是建立于细胞发育演化基础上的时空离散、状态离散的并行数学模型[1].从历史角度看,元胞自动机最早是由数学家、物理学家John Von Neu mann 和Stanisla w U la m 在1940年提出的[2].从应用角度看,直到John Hort on Con way 在1960年运用元胞自动机建立了一种“生命游戏”后[3～5],元胞自动机才得到了广泛的运用.80年代,由于元胞自动机这类简单模型能十分方便地复制出复杂的现象或动态演变过程中的吸引子、自组织和混沌现象,从而引起了物理学家、计算机科学家的极大兴趣,并在许多领域得到了应用,如混沌、分形的产生[6],模式分类[7],智能材料[8],复杂现象[1]等,并提出了许多变形的元胞自动机,如以凝固理论为演化规则的元胞自动机[9],模糊元胞自动机[10],神经元胞自动机[11]等.根据元胞自动机中元胞的空间展布,可将元胞自动机分为一维和多维(二维、三维等)的.OpenG L 是在SGI 、M icr os oft 、DEC 等著名计算机公司的倡导下,基于SGI 的G L 图形标准制定的一个通用共享的开发式三维图形标准库[12].它是一种过程性而不是描述性的图形AP I .它与操作系统无关,用OpenG L 编写的应用程序可以很容易移植到支持OpenG L 的操作系统,例如UN I X .由于它出色的3D 功能使得其在实现实时三维、科学计算可视化等方面得到了广泛的应用.本文的目的是建立一种用于微观组织模拟的三维元胞自动机模型并使其能够根据需要进行扩展.1 模型描述111 元胞自动机的定义[13]1)计算定义(Computati onal Definiti on )用元胞自动机进行模拟计算时,通常将其视为一类算法.因此可将其作为计算机程序代码按照如下步骤在计算机上运行:①定义存储元胞状态的元胞数组,这里元胞数组对应于元胞空间,数组元素对应于元胞,数组元素的值对应于元胞的状态;②定义一系列根据局部规则改变元胞数组元素值的函数;③在每个时间步内,运用函数同步更新元胞数组元素的值.2)物理学定义(Scientific Definiti on )元胞自动机最基本的组成部分包括元胞(cell )、元胞空间(lattice )、邻居(neighbor )及演变规则(rule ).它是定义在一个具有离散、有限状态的元胞组成的元胞空间上,并按照一定局部规则,在离散的时间维上演化的动力学系统.具有如下属性:①构成元胞自动机的部件被称为“元胞”,每个元胞的状态是离散有限的;②元胞规则地排列在被称为“元胞空间”的空间网格上;③元胞的状态随着时间变化,根据一个“局部第27卷第2期2005年6月 南昌大学学报・工科版Journal of Nanchang University (Engineering &Technol ogy )Vol .27No .2Jun .2005规则”进行更新,也就是说,一个元胞在某个时刻的状态值取决于且仅仅取决于上一个时刻该元胞的状态以及该元胞所有邻居元胞的状态;④元胞空间内的元胞按局部规则进行同步状态更新,整个元胞空间则表现为在离散的时间维上的变化.112 三维元胞自动机在计算机上的实现本文程序中定义了节点类、元胞类用于空间元胞的产生,定义了邻居定义函数用于定义每个元胞的邻居,定义了局部规则函数用于实现元胞状态的改变.程序实现顺序如下:1)在X、Y、Z方向定义一系列节点对象,包括节点坐标、节点号等;2)用这些节点对象定义一系列元胞对象(立方体和球),包括元胞号、包含的节点等;3)定义这些元胞对象的邻居元胞,根据不同的邻居类型定义;4)局部规则函数可以根据具体模拟情况进行定义,在本模拟中定义了一种简化的枝晶生长规则函数.113 计算机上运用OpenG L实现三维环境的关键技术1)重新设置窗口象素格式,使其符合OpenG L 对象素的需要,并按OpenG L的要求设置好窗口的属性和风格;2)先获得W indows设备描述表,然后将其与事先设置好的OpenG L绘制描述表联系起来;3)调用OpenG L命令进行图形绘制和坐标变化实现三维效果;4)退出程序,释放OpenG L绘制描述表和W in2 dows设备描述表.114 三维枝状构型元胞自动机枝晶生长是非平衡态结构模式形成的典型实例.由于自身动力学的不稳定性,微观层面的简单行为可导致宏观上非常丰富和复杂的结构.最简单地表述过冷熔体中枝晶形貌演变的确定性三维元胞自动机模型可表述为:1)元胞形状:立方体;2)元胞状态:0代表液相(未凝固),1代表固相(已凝固);3)邻居结构:6邻居(最近邻,类似与二维中的Von_numann邻居),18邻居(最近邻和次近邻,类似与二维中的Moor邻居),26邻居(元胞的最近一层邻居);4)假定元胞凝固后始终保持固相,即不考虑固相的重熔;5)演变规则:元胞状态由元胞本身的状态值与邻居元胞的状态值之和决定.即:S t+1i=f(σt i)σti=∑j∈NNS t j式中,映射f的定义域为[0,m],值域为0或1,m为邻居状态值的总和.2 模拟结果及讨论211 模拟结果本文按上述三维枝状构型元胞自动机模型中提出的规则进行了模拟.当在模拟空间内设一个元胞的状态值为1时,可能出现四种生长行为:1)无生长现象:f(σ)=0,σ∈[0,m];2)生长成平面板状(三维立方体)结构:f(σ)=1,σ∈[0,m];3)生长成非晶态:f(σ)=1,σ=2;4)呈枝状结构生长,f(σ)=1,σ=2.本文中按照第4种规则进行模拟,结果如图1,图2,图3所示:图1 二维的Von-nu mann邻居与三维6邻居模拟的对比212 讨论模拟结果中产生的枝状结构具有典型的自相似性.每2n时间步后,生长结构为立方体,之后在各个顶角方向生出枝状臂,然后所有分枝生长到彼此内・52・第2期 许林等:一种用于微观组织模拟的三维元胞自动机模型图2 二维的Moor 邻居与三维18邻居模拟的对比图3 三维的26邻居模拟循环14次部,又形成立方体,如此反复.从图3中可以明显看出这种现象.从模拟结构可以看出,演变规则4简单的局部作用可产生整体上的复杂枝晶结构.由于模拟没有考虑金属凝固的物理意义,如凝固过程中的热传导、随机形核、结晶潜热的释放等因素,所以与实际金属凝固枝晶组织存在比较大的差异.但本文的目的是建立一种模型框架,可以根据具体研究内容,加入相应的物理意义,将此模型框架进行扩展.3 结论本文建立了一种用于微观组织模拟的三维元胞自动机.由于C ++语言良好的可移植性以及Open 2G L 图形函数库的与系统无关性,所以该模型可以根据需要很容易的进行扩展和移植.运用简化的枝晶生长规则对不同邻居情况下三维枝晶生长进行了模拟并与二维的模拟情况进行了对比,验证了该模型的正确性.参考文献:[1] 赵松年.非线性科学-它的内容、方法和意义[M ].北京:科学出版社,1994.69-76.[2] Von Neu mann,J Burks,A W.Theory of Self -Rep r odu 2cing Aut omata [M ].U rbana:University of Illinois Press,1966.[3] Martin Gardner .The Fantastic Combinati ons of John Con 2way’s Ne w Solitaire Ga me of "L ife"[J ].Scientific Ameri 2can,1970,223(4):120-123.[4] De wdney A K .A cellular Universe of Debris,D r op lets,Defects and De mons[J ].Scientific American,1989,261(2):102-106.[5] De wdney A K .The Cellular Aut omata Pr ogra m s That Cre 2ate W ire world,Rug world and O ther D iversi ons [J ].Sci 2entific American,1990,262(1):146-149.[6] Karel Culik,Si m ant Dube .Fractal and recurrent behavi orof cellular aut omata [J ].Computing and I nfor mati on,1989,(3):253-267.[7] Tzi onas P G,Tsalides P G,Thanilakis A.A New CellularAut omata -based Nearest Pattern Classifier and its VLSI I m p le mentati on [J ].I EEE Trans Very Large Scale I ntegr (VLSI )syst,1994,2(3):343-347.[8] Ame m iya Yoshihit o .I nf or mati on Pr ocessing U sing I ntelli 2gentM aterials -inf or mati on -p r ocessing A rchitectures f or Material Pr ocess ors [J ].Journal of I ntelligent M aterial Syste m s and Structures,1994,5(3):418-423.[9] 郭洪民,刘旭波,杨湘杰.元胞自动机法模拟微观组织演变的建模框架[J ].材料工程,2003,(8):23-27.[10]姚国正.神经形态发生的一种细胞自动机(CA )模型[J ].科学通报,1991,19:1496-1499.[11]郭燕利,胡建军.利用OpenG L 三维图形库进行三维实体造型[J ].微型电脑应用1998,(6):93-96.[12]凌云,储林波.用V isual C ++中的M FC 和OpenG L 建立三维图形应用环境[J ].微型机与应用,1998,(4):8-10.[13]郭洪民.元胞自动机法模拟铝合金凝固组织形态演变[D ].南昌:南昌大学,2003.・62・南昌大学学报・工科版2005年 A Three -D i m ensi onal Cellul ar Auto maton M odelfor M i crostructure Si m ul ati onXU L in a,G UO Hong -m in b,Y ANG Xiang -jiea(a .School of M echanical and Electrical Engineering,N anchang U niversity,N anchang 330029;b .School of M aterial Science and Egineering,N anchang U niversity,N anchang 330047,China )Abstract:The cellular aut omat on is an ideal model f or a comp lex syste m;it is suitable t o describe the p r oble m about the comp lex dyna m ic syste m ,such as the si m ulati on f or evoluti on of m icr ostructures of materials .It is als oeasy t o be used in the computer .I n the paper,we use the OpenG L AP I t o construct a three -di m ensi onal cellular aut omat on model by C ++.This model possesses the basic ele ments,which the classic cellular aut omat on has .So this model can be expanded by peop le with different require ments .Because we use the 3D technol ogy of OpenG L,the si m ulati on results become more realistic;it can be watched fr om different angles .I n the paper,we use themodel t o si m ulate the gr owth of p redigest branch model .W e compare the 3D results with the 2D results,which val 2idate the validity of this model .Key W ords:cellular aut omat on;three -di m ensi onal model;OpenG L(上接第23页)并应用其解决一种新型微小机器人设计中遇到的困难,即获得了对复合球副的方案设计和对柔性铰链的技术设计,但该理论还处于发展阶段,40条发明原理,39个通用工程参数、冲突矩阵还有待于进一步的完善,紧密跟踪T R I Z 理论的发展动态,能为我们的创新设计工作提供更强大的支持.参考文献:[1] 檀润华.创新设计-T R I Z:发明问题解决理论[M ].北京:机械工业出版社,2002.[2] 乐万德,王可,吴通,等.基于TR I Z 的产品概念设计研究[J ].机械科学与技术,2003,22(4):531-534.[3] 蒙运红,吴昌林,黎星.创新思维的程式化方法-TR I Z 之一:解决矛盾的理论[J ].机械设计与研究,2002(增刊):45-46.[4] 薛实福,李庆祥.精密仪器设计[M ].北京:清华大学出版社,1991.The Appli cati on of Theory of I nventi ve Proble m Solvi n g i na New M i cro -Parallel Robot Desi gnZHOU Yan -hui,LUO Yu -feng,T ANG Man -hua,SH I Zhi -xin(School of M echanical and E lectrical Engineering,N anchang U niversity,N anchang 330029,China )Abstract:This paper intr oduces one theory within T R I Z,the p r ogra m method of s olving conflict .It includes for 2ty inventi on p rinci p les,thirty nine general engineering para meters,the separate p rinci p le,the conflict matrix and its app licati on .Then,the theory is used t o s olve the technol ogy conflict in a ne w m icr o -parallel r obot and the usage of the conflict matrix,and a ne w kind of compound s pherical j oint is designed .Finally,the analysis of physics conflict of the flexible j oint structure in a ne w m icr o -parallel r obot carried on,the usage of the separate p rinci p le dra ws a conclusi on corres pondingly .Key W ords:theory of inventive p r oble m s olving;conflict;r obot;ne w compound s pherical j oint;flexible j oint・72・第2期 许林等:一种用于微观组织模拟的三维元胞自动机模型。
一维元胞自动机规则一维元胞自动机规则，是一种基于简单规则运行的计算模型，其基本构成包括元胞、状态集合和局部规则。
元胞是系统中的基本单元，每个元胞都有自己的状态，而状态集合则是元胞可能的状态值的集合。
局部规则定义了元胞如何根据其自身状态以及周围元胞的状态来更新自己的状态。
在这种模型中，元胞之间的相互作用是局部的，而整个系统的行为则是由每个元胞的局部规则共同决定的。
一维元胞自动机规则可以被用来模拟各种复杂的现象，如生物群落的演化、城市交通的流动等。
在这些模拟中，元胞可以代表不同的个体或者物体，其状态可以表示不同的属性或者行为。
通过定义合适的局部规则，可以使元胞自动机展现出复杂的整体行为，从而揭示出系统内部的规律和结构。
在一维元胞自动机规则中，最常见的规则之一是元胞的状态更新规则。
这种规则通常基于元胞自身的状态以及其相邻元胞的状态来确定元胞的下一个状态。
例如，如果一个元胞的状态为1，而其左右两个元胞的状态都为0，则根据某种规则，这个元胞的下一个状态可能会被更新为0。
通过不断迭代这样的更新过程，整个系统的状态会逐渐演化出复杂的动态。
除了状态更新规则外，一维元胞自动机还可以包括边界条件、初始状态等因素。
边界条件定义了系统边界上元胞的状态更新方式，而初始状态则确定了系统在开始时每个元胞的初始状态。
这些因素的选择会对系统的演化产生重要影响，不同的选择可能导致完全不同的行为。
总的来说，一维元胞自动机规则是一种简单而强大的计算模型，可以被用来研究各种复杂系统的行为。
通过定义合适的元胞、状态集合和局部规则，可以模拟出系统的动态演化过程，揭示系统内部的规律和结构。
因此，一维元胞自动机规则不仅在计算机科学领域有着重要应用，也在生物学、物理学等其他领域展现出了巨大潜力。
改进的元胞自动机人员疏散仿真模型研究作者：王丹青巩青歌来源：《软件导刊》2014年第01期摘要：近几年来，地震、火灾等自然灾害频繁发生，恐怖袭击事件突发频率也呈日益攀升之势，公共安全问题成为社会热点，灾难突发时人员疏散问题的建模与仿真技术成为研究热点。
立足已有的元胞自动机模型，充分考虑了人员在疏散时的心理特点和行为特点，提出了一种改进的元胞自动机模型，通过改进的元胞自动机模型对人员疏散问题进行建模与仿真，更加真实再现了行为人在紧急疏散时表现出来的从众性和自组织性，其研究成果为人群疏散仿真研究提供了有力支持。
关键词：元胞自动机；蚁群算法；信息素中图分类号：TP337 文献标识码：A 文章编号文章编号：16727800（2014）001003403作者简介作者简介：王丹青（1990-），女，武警工程大学信息工程系硕士研究生，研究方向为人群疏散的计算机仿真；巩青歌（1964-），女，武警工程大学研究所教授、硕士生导师，研究方向为数据库技术、计算机仿真。
0 引言元胞自动机是一个具有行为规则的动态模型，通过它可以表现出复杂的行为，因此它已经成为复杂系统建模的一个重要工具。
其中，复杂环境下的人群疏散就是元胞自动机模型的一个重要应用领域。
在元胞自动机理论基础之上建立人员疏散模型的方法是：在均匀一致的网格上建立由元胞构成的动力系统[1]。
目前，利用元胞自动机研究人群疏散模型主要有以下几个方向：①针对大空间中的人员疏散问题，考虑偏好矩阵[2]与场地设计的元胞自动机模型；②根据人员在不同网格内的移动特性来确定其行走速度与方向，改进传统元胞自动机模型中人员行为的简单规则；③利用二维矩阵来定义元胞的状态，开发了元胞自动机的可视模型；④在经典元胞自动机模型的基础上，量化确定摩擦力和排斥力[3]等，精确行为规则运算。
通过查阅大量资料，发现种种改进的元胞自动机模型，在确定人员运动规则时，大多忽略了其紧急情况下疏散时特有的相互影响行为特点，只是单一计算各个孤立人员的行为规则，这样的模型无法准确度量人员在密度较大或情况较为紧急时，疏散行为中表现出的跟随行为和从众心理[4]。
元胞自动机理论基础 http://swarmagents.com/complex/models/ca/ca1.htm Chapter1 元胞自动机(Cellular Automata，简称CA，也有人译为细胞自动机、点格自动机、分子自动机或单元自动机)。是一时间和空间都离散的动力系统。散布在规则格网 (Lattice Grid)中的每一元胞(Cell)取有限的离散状态，遵循同样的作用规则，依据确定的局部规则作同步更新。大量元胞通过简单的相互作用而构成动态系统的演化。不同于一般的动力学模型，元胞自动机不是由严格定义的物理方程或函数确定，而是用一系列模型构造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。因此，元胞自动机是一类模型的总称，或者说是一个方法框架。其特点是时间、空间、状态都离散，每个变量只取有限多个状态，且其状态改变的规则在时间和空间上都是局部的。
1. 自动机 自动机(Automaton)通常指不需要人们逐步进行操作指导的设备(夏培肃，1984)。例如，全自动洗衣机可按照预先安排好的操作步骤作自动地运行;现代计算机能自动地响应人工编制的各种编码指令。完成各种复杂的分析与计算;机器人则将自动控制系统和人工智能结合，实现类人的一系列活动。另一方面，自动机也可被看作为一种离散数字动态系统的数学模型。例如，英国数学家A.M.Turing于1936年提出的图灵机就是一个描述计算过程的数学模型(TuringA M.，1936)。它是由一个有限控制器、一条无限长存储带和一个读写头构成的抽象的机器，并可执行如下操作: ·读写头在存储带上向左移动一格; ·读写头在存储带上向右移动一格; ·在存储的某一格内写下或清除一符号; ·条件转移。 图灵机在理论上能模拟现代数字计算机的一切运算，可视为现代数字计算机的数学模型。实际上，一切"可计算"函数都等价于图灵机可计算函数，而图灵机可计算函数类又等价于一般递归函数类。 根据存储带是否有限，可将自动机划分为有限带自动机(Finite Automaton)和无限带自动机(Infinite Automaton)。由于图灵机有无限长的存储带，所以为一种无限带自动机。有限带自动机常用作数字电路的数学模型，也用来描述神经系统和算法;而无限带自动机主要用来描述算法，也用来描述繁殖过程 (如细胞型自动机和网络型自动机)。 有限自动机是一种控制状态有限、符号集有限的自动机，是一种离散输入输出系统的数学模型。可将有限自动机设想成由一条划分为许多方格的输入带和一个控制器组成的机器:在输入带的每一个小格中可以容纳一个符号，这些符号取自一个有限符号集S-控制器具有有限个可能状态(构成集合Q)。并在每一时刻仅处于其中的一个状态q;控制器有一个读入头，可以从输入带中读入符号;时间是离散的，初始时控制器处在状态;控制器的功能是根据其当前状态g和读入头从输入带上得到的符号a,来确定控制器的下一时刻的状态实现从状态q到状态q'，实现从状态q到状态铲q'的转移，并将读入头右移一格。控制器另一功能是识别终止状态(它们构成Q的一个子集F)，也可将该识别功能视为有限自动机的输出。 从数学上来定义，有限自动机是一个五元组:
FA=(Q，S，δ，q0，F) 其中，Q是控制器的有限状态集、S是输入符号约有限集、δ是控制状态转移规律的Q×S到Q的映射 (可用状态转移图或状态转移表表示)，q0是初始状态、F是终止状态集。若δ是单值映射，则称M为确定性有限自动机;若δ是多值映射，则称M为非确定性 有限自动机。
Chapter2 在元胞自动机是由空间上各项同性的一系列元胞所组成，是在有限元胞自动机基础上发 展起来的，用于模拟和分析几何空间内的各种现象。 2.2.1 典型的元胞自动机 在元胞自动机的发展过程中，科学家们构造了各种各样的元胞自动机模型。其中，以下几个典型模型对元胞自动机的理论方法的研究起到了极大的推动作用，因此，它们又被认为是元胞自动机发展历程中的几个里程碑。
l. S. Wolfram和初等元胞自动机 初等元胞自动机(Elementary Cellular Automata，简称ECA)是状态集S只有两个元素{s1，s2}，即状态个数k=2，邻居半径r=l的一维元胞自动机(谢惠民，1994、李才伟，1997、Wolfram，S，1986)。它几乎是最简单的元胞自动机模型。由于在S中具体采用什么符号并不重要，它可取 {0，1}，{-l，1}，{静止，运动}，{黑，白}，{生，死}等等，这里重要的是S所含的符号个数，通常我们将其记为 {0，1}。此时，邻居集N的个数2r=2，局部映射f:S3→S可记为:
其中变量有三个，每个变量取两个状态值，那么就有2×2×2=8种组合，只要给出在这八个自变量组合上的值，f就完全确定了。例如以下映射便是其中的一个规则:
通常这种规则也可表示为以下图形方式 (黑色方块代表l，白色方块代表0): 这样，对于任何一个一维的0，1序列，应用以上规则，可以产生下一时刻的相应的序列。以下序列就是应用以上规则产生的:
t: 010111110101011100010 t+1:1010001010101010001
以上八种组合分别对应0或1，因而这样的组合共有28=256种，即初等元胞自动机只可能有256种不同规则。S. Wolfram定义由上述八种构形产生的八个结果组成一个二进制(注意高低位顺序)，如上可得01001100，然后计算它的十进制值R: R在[0，255]内，S. Wolfram定义R为初等元胞自动机的标号，则上面的元胞自动机模型就是76号初等元胞自动机 (谢惠民，1994；李才伟，1997)。
S. Wolfram对这256种模型一一进行了详细而深入的研究。研究表明，尽管初等元胞自动机是如此简单，但它们表现出各种各样的高度复杂的空间形态。经过一定时间，有些元胞自动机生成一种稳定状态，或静止，或产生周期性结构，那么，有些产生自组织、自相似的分形结构。S. Wolham(1983)借用分形理论计算了它们的维数约为1.59或1.69(Wolfram，S.，1983)。但256种元胞自动机中没有一种属于S. Wolfram元胞自动机动力学分类得第四种，所谓复杂型。 S. Wolfram对一维元胞自动机，尤其是初等元胞自动机的深入研究奠定了元胞自动机理论的基石。对元胞自动机的理论研究，以及后来的人工生命研究和近来兴起的复杂性科学 (Science of Complexity)研究作出了卓越的贡献。
2. J. Conway和 "生命游戏" 生命游戏 (Came of Life)是J. H. Conway在20世纪60年代末设计的一种单人玩的计算机游戏(Garclner，M.，1970、1971)。他与现代的围棋游戏在某些特征上略有相似：围棋中有黑白两种棋子。生命游戏中的元胞有{"生"，"死"}两个状态 {0，1};围棋的棋盘是规则划分的网格，黑白两子在空间的分布决定双方的死活，而生命游戏也是规则划分的网格(元胞似国际象棋分布在网格内。而不象围棋的棋子分布在格网交叉点上)。根据元胞的局部空间构形来决定生死。只不过规则更为简单。下面介绍生命游戏的构成及规则: (1)元胞分布在规则划分的网格上； (2)元胞具有0，1两种状态，0代表"死"，l代表"生"； (3)元胞以相邻的8个元胞为邻居。即Moore邻居形式； (4)一个元胞的生死由其在该时刻本身的生死状态和周围八个邻居的状态 (确切讲是状态的和)决定: ·在当前时刻，如果一个元胞状态为"生"，且八个相邻元胞中有两个或三个的状态为"生"，则在下--时刻该元胞继续保持为"生"，否则"死"去； ·在当前时刻。如果一个元胞状态为"死"。且八个相邻元胞中正好有三个为"生"。则该元胞在下一时刻 "复活"。否则保持为"死"。 尽管它的规则看上去很简单。但生命游戏是具有产生动态图案和动态结构能力的元胞自动机模型。它能产生丰富的、有趣的图案。生命游戏的优化与初始元胞状态值的分布有关，给定任意的初始状态分布。经过若干步的运算，有的图案会很快消失。而有的图案则固定不动，有的周而复始重复两个或几个图案，有的婉蜒而行。有的则保持图案定向移动，形似阅兵阵„„，其中最为著名的是"滑翔机 (叫Glider)"的图案。
生命游戏模型已在多方面得到应用。他的演化规则近似地描述了生物群体的生存繁殖规律:在生命密度过小(相邻元胞数之2)时，由于孤单、缺乏配种繁殖机会、缺乏互助也会出现生命危机，元胞状态值由1变为0;在生命密度过大 (相邻元胞数>3)时，由于环境恶化、资源短缺以及相互竞争而出现生存危机，元胞状态值由1变为0;只有处于个体适中(相邻元胞数为2或3)位置的生物才能生存(保持元胞的状态值为1)和繁衍后代(元胞状态值由0变为1)。正由于它能够模拟生命活动中的生存、灭绝、竞争等等复杂现象，因而得名"生命游戏"。J·H·Conway还证明，这个元胞自动机具有通用图灵机的计算能力(谢惠民，1994;李才伟，1997)，与图灵机等价，也就是说给定适当的初始条件，生命游戏模型能够模拟任何一种计算机。 从数学模型的角度看，该模型将平面划分成方格棋盘，每个方格代表一个元胞。 元胞状态:0 死亡，1- 活着 领域半径:1 领域类型：Moore型 其中St表示t时刻元胞的状态，S为8个相邻元胞中活着的元胞数。 另外，需要指出的是，目前随着人们对 "生命游戏"研究的深入，产生了许多变种和扩展。在80年代末，A·K·Dewdney (Dewdney，A·K，1987)和C·Bays (Bays，C，1987)Dewdney，A·K·，1990)将Conway的生命游戏扩展到了三维空间上，构建了三维生命游戏，并对其规则作了具有普遍性的扩展(图2-3)。C·Bays的学生Lee Meeker在此基础上进一步构建了四维的生命游戏。另外，Gardner (Gardner，M·，1970、1971、1983)等人也曾在这方面作了很多迸一步的研究工作。
对游戏规则的扩展主要是引入了4个参数EbEkFbFk，Eb表示对于一个"活"元胞，在下一个时刻，继续保持其状态所需要的最少的"活"邻居的数目，而Fb则表示对于一个 "死"元胞，在下一时刻，"复活"所需要的最小的"活"邻居的数目，Ek和Fk则分别表示上述情况的上限值。演化规则修改为
3.格子气自动机 格子气自动机 (Lattice一GasAutomata,LGA又称格气机)，是元胞自动机在流体力学与统计物理中的具体化，也是元胞自动机在科学研究领域成功应用的范例 (李才伟，1997)。相对于"生命游戏"来说，格子气自动机是个更注重于模型的实用性。它利用元胞自动机的动态特征，来模拟流体粒子的运动。 第一个时空、速度等变量完全离散的格子气自动机是1973年由法国的J·Hardy、Y·Pomeau和O·Pazzis提出的HPP模型，它的模拟结果已经很接近流体力学中描述流体运动的Navier-Strokes方程。但模型中的流体粒子的运动只允许有四个方向，造成应力张量各向异性的致命弱点，尚不能充分反映流体的特征，因此在较长时间内没有受到足够的重视。直到20世纪80年代，S·Wolfram等人的研究工作使得元胞自动机理论产生了质的飞跃，同时也带动了格子气自动机的进一步发展。1986年，法国的U·Frish、Y·Pomeau和美国的B·HassIacher在HPP模型的基础上提出了一个有实用价值的、基于六角形网络的格子气自动机模型，得名为FHP(Fritsch-Has，lacher-Pomeau)模型，并证明该模型的宏观行为符合标准的Navier-Stokes方程(李才伟，1997)。FHP模型是第一个成功的格子气模型，并激发了研究格子气模型研究
