（通信与信息系统专业论文）基于元胞自动机的停车场照明控制的研究.pdf

原创性声明 本人郑重声明 所呈交的学位论文 是本人在导师的指导下 独立进行研究所取得 的成果 除文中已经注明引用的内容外 本论文不包含任何其他个人或集体已经发表或 撰写过的科研成果 对本文的研究作出重要贡献的个人和集体 均已在文中以明确方式 标明 本声明的法律责任由本人承担 学位论文作者 毛辛龟鲁日期 2 科 年j 月 日 学位论文使用授权声明 本人在导师指导下完成的论文及相关的职务作品 知识产权归属郑州大学 根据郑 州大学有关保留 使用学位论文的规定 同意学校保留或向国家有关部门或机构送交论 文的复印件和电子版 允许论文被查阅和借阅 本人授权郑州大学可以将本学位论文的 全部或部分编入有关数据库进行检索 可以采用影印 缩印或者其他复制手段保存论文 和汇编本学位论文 本人离校后发表 使用学位论文或与该学位论文直接相关的学术论 文或成果时 第一署名单位仍然为郑州大学 保密论文在解密后应遵守此规定 学位论文作者 罐奉 日期 沙f 年j 月洳日 摘要 摘要 随着社会经济的不断发展 人民的生活质量也不断的提高 汽车的数量也不断的增 多 造成了出门 停车难 难停车 的问题日益严重 各商场 饭店的停车位也拥挤不 堪 地下停车场或者立体停车位的开发成了必然的趋势 合理的管理停车场也是非常关 键的 有地下停车场虽然适量缓解了停车难的现象 但停车位少 车辆拥挤作为一大因 素制约着社会经济的发展 停车场一般都有多个入口和多个出口 对于这样的停车场一般面积都比较大 光线 都比较差 很多地方都需要长期照明 这样不仅造成能源的浪费 还导致照明设备的寿 命减少 如果用原来的的控制方法来控制灯光 不仅需要的线路长 照明设备也多 而 且回路复杂 由于各出入口与行车通道之间不是简单的一一对应关系 因此很难实现停 车场内部照明的自动控制 所以只能采用连续照明方式 有的停车场虽然采用红外或声 控开关来控制照明 但是只能对某一个小区域实现自动控制 而不能对全部停车场照明 实现自动控制 这样不仅造成巨大的能源浪费 也给停车场的物业管理造成很大的经济 负担 合理的 科学的管理停车场迫在眉睫 本文利用z i g b e e 无线传感器 通过控制台 发送无线的命令 控制停车位照明灯的开关 利用元细胞自动机的随机变换控制停车场 整体的灯光 利用n a s c h 模型诱导驾驶员在最短时间内快捷 迅速的找到停车位 这 个系统对于停车需求在时间和空间上分布的不均匀 提高停车场得使用率 减少由于寻 找停车位而产生的道路交通堵塞 减少为了停车而造成的等待时间 提高整个停车场的 使用的效率 改善停车场的经营条件以及增加商业区域的经济活力等方面有着极其重要 的作用 关键词 灯光照明 n a s c h c h s c h 元细胞自动机 停车场 a b s t r a c t w i t ht h es o c i o e c o n o m i cd e v e l o p i n ga n dt h eq u a l i t yo f p e o p l e sl i f ea l s oi m p r o v i n g t h e n u m b e ro fc a r sh a sa l s ob e e ni n c r e a s i n g i tc a u s e dt h es e r i o u sp r o b l e mo f p a r k i n gd i f f i c u l t t h ep a r k i n ga r e ao fe a c hs t o r ea n dr e s t a u r a n ti sa l s oc r o w d e d i ti sa ni n e v i t a b l et r e n dt os t a r t t h eu n d e r g r o u n dp a r k i n go rt h et h r e e d i m e n s i o n a lp a r k i n gs p a c e i ti sp i v o t a lt om a n a g e p a r k i n gr e a s o n a b l y t h eu n d e r g r o u n dp a r k i n gl o tr e l i e v et h ep a r k i n gp h e n o m e n o 玛b u tl e s s p a r k i n gs p a c ea n dn u m e r o u sv e h i c l ea r et w of a c t o r sw h i c hr e s t r i c tt h ed e v e l o p m e n to f s o c i o e c o n o m i c t h e r ea r em a n ye n t r a n c e sa n de x i t st ot h ep a r k i n gl o t g e n e r a l l y f o rs u c hp a r k i n g p l a c e t h ea r e ai sl a r g e r t h el i g h ti sp o o r e ra n dal o to fp l a c e sn e e dl o n g t e r ml i g h t i n g t h i sn o t o n l yc a u s e daw a s t eo fe n e r g y b u ta f f e c tt h el i f eo fl i g h t i n ge q u i p m e n t i fu s et h eo r i g i n a l c o n t r o lm e t h o dt oc o n t r o lt h el i g h t i tn o to n l yn e 圮 d sl o n gc o n t r o ll i n ka n dm u c hm o r el i g h t i n g e q u i p m e n tb u ta l s oh a sc o m p l e xc o n t r o ln e t w o r k e a c he n t r a n c eo re x i ta n dd r i v i n gc h a n n e l a r cn o tb e t w e e ns i m p l eo n e t o o n er e l a t i o n s h i p s oi ti sd i f f i c u l tt or e a l i z et h ea u t o m a t i c c o n t r o lp a r k i n gf o rt h ei n t e r i o rl i g h t i n g s oi th a st ot a k et h ec o n t i n u o u s l yl i g h t i n gm o d e s o m eo ft h ep a r k i n g su s ei n f r a r e do rs o n i cs w i t c ht oc o n t r o ll i g h t i n g b u to n l yt oas m a l la r e a a n dc a n n o ta c h i e v ea u t o m a t i cc o n t r o lf o ra l lp a r k i n gl i g h t i n g s on o to n l yc a u s eh u g ee n e r g y w a s t e a l s oc a u s e dg r e a te c o n o m i cb u r d e nt ot h ep a r k i n gl o tp r o p e r t ym a n a g e m e n t ni si m p o r t a n tt om a n a g et h ep a r k i n gl o tr e a s o n a b l ya n ds c i e n t i f i c t h i sa r t i c l eb a s e do n t h ez i g b e ew i r e l e s ss e n s o rn e t w o r k u s et h ec o n s o l et os e n dw i r e l e s sc o m m a n d c o n t r o lt h e l i g h ts w i t c h t h ep a r k i n gl i g h ti sc o n t r o l l e du s i n gr a n d o mt r a n s f o r mo fc e l l u l a ra u t o m a t a 1 1 1 e d r i v e r sc o u l df i n dap a r k i n gs p a c ea n das h o r tr o u t et ot h ep a r k i n gs p a c eq u i c k l y t h i si s a c h i e v e db yt h el i g h to ft h ep a r k i n gl o tu s i n gn a s c hm o d e l 1 1 硷s y s t e mi si m p o r t a n tt ot h e u n e v e nd i s t r i b u t i o no fp a r k i n gd e m a n di nt i m ea n ds p a c e i m p r o v et h e p a r k i n gs p a c e u t i l i z a t i o nr a t e s r e d u c et of i n dp a r k i n gs p a c ea n dp r o d u c er o a dt r a f n cb e c a u s eo ft h ep a r k i n g l o t r e d u c ew a i t i n gt i m ec a u s e db yp a r k i n g i m p r o v et h ee f f i c i e n c yo ft h eu s eo ft h ep a r k i n g l o t i m p r o v et h eo p e r a t i o nc o n d i t i o n sa n di n c r e a s et h ee c o n o m i cv i t a l i t yo fb u s i n e s sa r e a s a n d s oo n i tp l a y sa ne x t r e m e l yi m p o r t a n tr o l e k e y w o r d s l a m p l i g h ti l l u m e n a s c h c h s c h c e l l u l a ra u t o m a t o n p a r k i n gl o t i i 目录 目录 6 8 1 4 1 8 则上分析 1 8 1 9 1 9 2 2 6 1w o l f r a m 的1 8 4 规则和n a s c h 交通模型 2 0 2 6 2 其它一维模型 2 3 2 6 3 二维c a 交通模型 2 4 2 6 4b 虬模型 2 4 2 6 5b m l 的扩展模型及c h s c h 模型 2 5 第三章地下停车场行人和车流量的仿真模型 2 8 3 1 行人流的微观行为和宏观群体特征 2 8 3 2 汽车进入地下停车场的仿真系统 2 8 3 3 地下停车场模拟环境的建立 3 0 3 4 车辆运动规则 3 0 3 5 改进的n a s c h 模型对车流量的仿真 3 l 第四章 基于元胞自动机模型的停车场控制的研究 3 5 4 1 地下停车场状态控制模型 3 5 4 2 停车场车辆进出口控制 3 6 4 2 1 整体区域控制方法 3 7 4 2 2 基于元胞自动机的停车场灯光导航模挺 3 8 4 2 3 车辆区域分配控制方法 3 9 4 3 基于元胞自动机的地下照明系统的控制 3 9 4 3 1 灯光控制的原理 4 0 4 3 2 所采用的元胞自动机模弛及演化规则 4 0 n 图和附表清单 2 1 一维元细胞模型 2 2 元细胞邻居的状态 2 3 细胞邻居的输出规则 2 4 几种常见的一维元细胞的图形 2 5 几种常见的二维图形 2 6m o o r e 邻居形式 2 7 生命游戏的状态图形 2 8 元细胞自动机的基本元素 2 9 元细胞空间的几何划分 2 1 0 反射边界 图2 1 l 细胞自动机的邻居模型 图2 1 2 格子气泡 图2 1 3w o l f r a m1 8 4 号规则 图2 1 4n a s c h 模型演化规则示意图 图2 1 5b 虬的模型示意图 图2 1 6c h s c h 模型示意图 图2 1 7 减速示意图 图3 1 模拟路网图 图3 2 行车通道的示意图 图和附表清单 图3 3 汽车通道流最基本参数仿真结果图 图4 1 地下停车场示意图 图4 2 地下停车场分区圈 图4 3 灯光控制原理图 图4 4 元胞模魁示意图 图4 5 仿真模型示意图 i i 第一章绪论 第一章绪论 1 1 停车场国内外研究现状 目前国内外停车场大多是针对某一方面的研究 例如停车场的停车诱导系 统 停车场管理的停车收费系统等都取得了良好的效果 为停车场合理停车和 景观照明的研究提供了理论与实践基础 早在1 9 7 1 年 在德国的亚琛市就建立了停车诱导系统 l l 这也被认为是世 界上最早的停车诱导系统 该系统对市内的1 2 处停车场在主要的交叉路口设置 了光电显示的停车场诱导标志 截至1 9 8 0 年控制对象增加到了4 0 处 诱导标 志由远距离控制 促进了现有停车场的有效利用 日本于1 9 7 3 年在柏市建立了 日本最早的停车诱导系统 所提供的信息以停车场的使用状况 车位数以及停 车场的位置等为主 日本的停车诱导信息发布系统集成在日本警察厅开展的 u t m s u n i v e r s a lt r a 伍cm a n a g e m e n ts y s t e m 项目中 通过u t m s 的交通管理综 合集成系统发布停车诱导信息 日本采用区域 主要路口 停车场内三级引导 电子显示牌 显示停车场在区域中的位置 停车场的行车方向和是否有空车位 的信息 大约同一时期在法国 英国 瑞士等国也相继建立了类似的系统 北京于2 0 0 1 年起先后在王府井 北京站以及西单等地区建立了停车诱导系 统 2 j 上海于2 0 0 2 年起在黄浦区建立了 停车诱导系统示范 工程 3 整个工程 共有3 6 处 6 4 块停车诱导发布牌 覆盖了整个黄浦区中心区域 包括3 9 个对 外开放停车库的5 9 0 0 多个车位 对停车难的解决起到了一定的辅助作用 近年 来 广州 沈阳 太原 青岛等城市相继建立了停车诱导系统 取得了一定的 效果 随着社会经济的发展 机动车拥有量迅速增长 居民乘小汽车出行的次数 增多 许多城市 停车难 难停车 的问题日益显著 供需紧张 乱收费 违 章停车 进出停车场不易 寻找停车场困难等现象复变存在 影响了城市景观 更影响着与动态交通的和谐发展 不仅如此 目前大部分城市的停车设施在数 量上严重不足 质量上简陋 许多停车场内的停车标志 停车泊位线 导向箭 头 减速鹅 车辆有道标志等停车管理设施严重短缺 自动收费设备缺乏 乱 收费现象严重 泊位引导系统不完善 驾驶人停车取车困难 停车诱导信息缺 第一章绪论 乏 驾驶人寻找可利用的停车位比较困难 部分停车场只管收取停车费 根本 不管车辆停车的安全 一旦丢失 把责任推卸的一干二净 这在一定程度上导 致了车主放弃在停车场停车 而选择在路边 单位的门口等空闲地方乱停乱放 违章停车现象严重 其实这也不是车主愿意做的 有时还会被交警部门贴罚单 停车场利用率很低 要缓解 停车难 难停车 的现象 首先需要在停车场法规规章制度的约 束下 根据城市经济 人口 面积 道路状况 功能分区 车辆拥有量等因素 进行系统的 科学的停车场规划 其次根据停车场规划 车流运行特性和道路 网布局 进行路外停车场和颅内停车场的配置与建设 在停车规划与配置建设 完成后 需要进行合理完善的停车场管理 而经国内外实践表明单纯依靠停车 场的供应无法满足日益增长的停车需求 加上我国目前城市的停车位 绝对不 足 和 相对过剩 的矛盾现象普遍存在 停车场的科学化管理尤为重要 近年来各国政府越来越重视进行合理停车的研究和该问题的解决 因为它 一旦发生瘫痪不仅给社会带来巨额的经济损失 而且对人们的生命构成了严重 威胁 有些时候当车辆进来时还显示停车场内有空位 但当进来以后已经被从 其它的进口进来的车辆先停放了 造成车辆的拥堵 在城市人口与日俱增 城 市交通压力不断增加 停车较难的今天 通过对车辆流微观特征和宏观特征的 研究 建立科学的地下停车场的车辆诱导和景观照明 指导车辆设施的规划和 车辆流的管理和控制 有效避免和缓解停车难 实现车辆设施利用限度的最大 化 是车辆流研究的热点 在日本 为获得舒适的城市环境 发展停车场是重 要的 而在拥挤的城市中有效利用地下空间尤为必要 然而 在地下停车场保 持适合的环境 使之有代表性的地下停车场需要更多的设备和消耗更多的能量 本论文基于元胞自动机模型建立了用m a t l a b 仿真理论 在分析研究车辆 微观行为特征的基础上 建立车辆流仿真模型 通过仿真车辆流中微观个体的 微观行为特征 实现由单个个体之间相互作用形成的宏观车辆流的特征研究 1 2 地下停车场的照明 在地下停车场的入口处设置岗亭照明 栏杆上设置灯光反射条 岗亭的灯 光照明是为了辨识驾驶员的面部以及岗亭工作台及其附近区域的照明 栏杆上 设置灯光反射条以及入i z l 两侧设施以及地面均须提供相应的照明 以保证驾驶 2 第一章绪论 员的安全驾驶 在停车场应设置很多标志 有些是自发光的 反光条 有些是 通过照明设备才能被看到 在设计照明时应从多个方面考虑 例如行车通道长 明灯的话照成资源的浪费 如果有车出入或者有车通过时 通道的灯应自动点 亮 如果是没有车通过或者是没有车进出 通道的灯自动熄灭 在通过的两侧 还应该设置自发光的展示标线或者是路边地下灯长期照明 使驾驶员能够清楚 的判断通道的边界 在停车位处也应清楚的展现地面的变现 地面车锁 隔离栏杆灯 使驾驶 员清楚辨认自己停车的位置 车停放到车位后车身需通过适当的照明展示出来 假设元细胞自动机的每一个元胞是一个停车位的话 使该元胞点亮 一方面是 给其他的驾驶员声明改车位已停车 每个车辆虽然有自身的前后车灯 要观察 全部情况 仅靠车灯是不够的 该元胞点亮也可以使驾驶员朋友观察停车以及 车身的全部情况 还要考虑行人的路线 行人在停车或取车离开时 都会有一段步行道路道 电梯口或者是人行出口 在此通道上应按照普通人行道路考虑照明 不仅需要 提供合适的地面照明而且还得实现垂直面照明 此外 导向性照明也是必要的 在整个停车场也应该有一些长期照明 以方便驾驶员在停车场内辨别方向 和和安全方面的考虑 此外 在停车场周边通过设置连续的灯杆形成一种阵列 能起到视线屏障的作用 使停车场内外达到一种隔离的效果 降低停车场对场 外环境氛围的影响 毕竟车辆或停车场地不是公共环境中的美观装饰品 它们 有可能破坏环境本来的和谐 灯具的造型也在一定程度上有调剂环境的作用 4 1 3 地下停车场照明系统的仿真 用计算机来来对地下停车场的照明系统分进行仿真是近年来常用的一种技 术手段 它可以进行微观的仿真 也可以进行宏观的 能够通过照明系统的仿 真来得到一些数学模型 并且掌握元细胞的变化状态 规律的分布 并且得出 目前全世界有很多仿真的软件 比较著名的有德国的v i s s i m 5 1 v i s s i m 是一种微观 基于时间间隔和驾驶行为的仿真建模工具 用以建模 和分析各种交通条件下 车道设置 交通构成 交通信号 公交站点等 城市 交通和公共交通的运行状况 是评价交通工程设计和城市规划方案的有效工具 3 第一章绪论 v i s s i m 由交通仿真器和信号状态产生器两部分组成 它们之间通过接口交 换检测器数据和信号状态信息 v i s s i m 既可以在线生成可视化的交通运行状 况 也可以离线输出各种统计数据 如 行程时间 排队长度等 英国的p a r a m i c s 软件的开发始于1 9 8 6 年 6 并于1 9 9 7 年成功投入商业 使用 自问世以来 一直是英国应用最广泛的微观仿真软件 领先的软件开发 技术和优良的售后服务确保了p a r a m i c s 一直是英国中央及地方政府 私营企 业和其他交通运输规划顾问公司的首选 p a r a m i c s 软件不仅在英国得到了广泛地应用 还遍及了世界上许多国家 和地区 典型应用实例包括爱丁堡 格拉斯哥 曼彻斯特 米兰 阿姆斯特丹 都柏林 基督城 以及英国最为繁忙的伦敦m 2 5 环形高速路等 p a r a m i c s 的应用范围包括城市中心区和各种主次路 其具体应用包括道 路环岛和各种交叉口设计 公共汽车优先措施和专用道 高速公路设计 车辆 尾气排放控制 收费站点设置 城市交通控制 大区域的交通管理 道路施工 管理 停车场的选址和管理 以及事件管理等 p a r a m i c s 具有的独特的动态车辆分配功能 并可以与各种标准的u t ca n d i t s 系统相连 如s c o o t s c a t s m o v a a l i n e a c c o l m i d a s a t m 等 m a t hw o r k s 公司的m a t l a b l 7 j m a t l a b 是由美国m a t h w o r k s 公司发布的 主要面对科学计算 可视化以及交互式程序设计的高科技计算环境 7 它将数值 分析 矩阵计算 科学数据可视化以及非线性动态系统的建模和仿真等诸多强 大功能集成在一个易于使用的视窗环境中 为科学研究 工程设计以及必须进 行有效数值计算的众多科学领域提供了一种全面的解决方案 并在很大程度上 摆脱了传统非交互式程序设计语言 如c f o r t r a n 的编辑模式 代表了当今国 际科学计算软件的先进水平 m a t l a b 主要应用于工程计算 控制设计 信号 处理与通讯 图像处理 信号检测 金融建模设计与分析等领域 本系统的仿 真就是通过m a t l a b 实现的 同济大学研发的m i c r o s i m 清华大学的 t r a s i m u l 还有许多高校也在仿真方面有很多成果 引 通过元胞自动机的随机变换和邻居的互相影响来仿真停车场照明系统 另 外元胞自动机在仿真上面有许多的研究 取得了很多成果 最典型的一维元胞 自动机是n a s c h 模型 9 l 最常用的二维元胞自动机交通模型是b m l 模型 1 0 l 还 有许多上述两模型的改进版 4 第一章绪论 1 4 论文的主要的内容和章节结构 本文基于元细胞自动机理论 分析研究了基于元胞自动机的地下停车场的 照明仿真模型 并且对n a s c h 模型进行了改进 使其更加符合地下停车场的照 明的实际情况 运用m a t l a b 编程 对不型号的进入车辆和停车位上是否有停 车进行仿真 结果发现 能够引导车辆找到合适的停车空间 但并不是从入口 到停车位的最佳路径 还有待改善 整个文章的组织结构如下 第一章主要是介绍地下停车场的现状 和对地下停车场照明的需求 以及 解决改问题的办法 第二章介绍元胞自动机的概念和他的发展过程 元细胞的各种基本模型 以及基于元胞自动机的模型在各个方面的应用 第三章研究地下停车场的诱导停车问题 驾驶员和车辆进入停车场的活动 状态的仿真 当有车辆出入时 建立一个基于元胞自动机的出入口的模型 针 对相同类型和不同类型的车辆进行仿真分析 并对进入车辆和出去车辆提出了 一种可行的信号灯的改进的算法 第四章主要介绍了基于元胞自动机模型的停车场控制的研究 控制地下停 车场的车辆进入 当达到某一饱和度是禁止入内 利用m a t l a b 建立停车场的 仿真模型 第五章是对本论文的工作的总结 并对下一步的工作的开展进行了展望 本论文的主要贡献是第三章和第四章 用元细胞自动机的模型来分割化停 车场 把停车位细胞化 根据停车场的利用率来确定景观照明 用m a t l a b 来 仿真地下停车场 根据停车场的停车密度来判断车辆是否可以进入 根据入口 的车辆的特征来诱导停车 至于出口 任意车辆都可以随时出 根据出车的情 况在判断停车场的停车密度 来决定是否允许进入 5 第二章元细胞自动机的理论桀础 第二章元细胞自动机的理论基础 2 1 元细胞自动机的概念 元细胞自动机简称c a 也被译为元胞自动机 细胞自动机 分子自动机 点格自动机或单元自动机 是一个在空间和时间上都离散的动力学系统 散布 在规则网格中的每一个元胞 c e l l 取有限的离散状态 遵循同样的有效规则 依 据确定的部分规则作同步更新 大量元细胞通过简单的相互作用而构成动力学 系统的演化 l 元细胞不同于一般的动力学模型 元胞自动机不是由严格定义 的物理定义或数学函数所确定 而是由一系列模型构造的规则而构成 只要是 满足这些有效规则的模型都可以看做是元胞自动机模型 因此 元细胞自动机 没有一个明确的框架和方程形式 而是一类模型的总称 或者说是一个大的方 法框架 元细胞的特点是空间 时间和状态都是离散的 每个细胞只能取有限 多个状态 且其状态改变的有效规则在时间和空间都是局部的 最早的元细胞 自动机的模型是由冯 诺依曼和乌拉姆提出来的 在此后 元胞自动机在各个领 域都得到了研究 它是一个纯正的 混血儿 它是由是计算机科学家 数学学 家 生物学家还有物理学家共同研究的结果 所以 对元胞自动机的定义也存 在不同的解释 物理学家将其视为离散的 无穷维的动力学系统 数学家将其视 为描述连续现象的偏微分方程的对立体 是一个空间离散的数学模型 计算机科 学家将其视为新兴的人工智能 人工生命的分支 而生物学家则将其视为生命现 象的一种抽象i l z l 1 元细胞自动机在物理学上的定义 元胞自动机是被定义在一个具有离散 有限状态的元胞组成的元胞空间上 并按照一定局部规则 在离散的时间维上演化的动力学系统 1 3 l 具体来说 构成元胞自动机的部件被称为 元胞 每个元胞具有一个状态 这个状态只能是取某个有限状态集中的一个 例如或 生 或 死 或者是2 5 6 中颜色中的一种 等等 这些元胞规则地排列在被称为 元胞空间 的空间格网 上 它们各自的状态随着时间变化 而根据一个局部规则来进行更新 也就是说 6 第二章元细胞自动机的理论堆础 一个元胞在某时刻的状态取决于上一时刻该元胞的状态以及该元胞的所有邻居 元胞的状态 元胞空间内的元胞依照这样的局部规则进行同步的状态更新 整个 元胞空间则表现为在离散的时间维上的变化 6 2 5 1 2 元细胞自动机在数学上的定义 在9 0 年代初 美国数学家l e h u r d 和k c u l i k 等人 分别从集合论和拓扑 学等角度对元胞自动机进行了严格地描述和定义1 1 7 2 0 1 1 在集合论中的定义 假设用d 表示空间维数 用k 表示元胞的状态 并在一个有限集合s 中取 值 r 表示元胞的邻居半径 z 是整数集 表示一维空间 t 表示任意时刻的时间 为叙述和理解简单起见 在一维空间上考虑元细胞自动机 即假定d i 那么整个元细胞空间就是在一维空间 将整数集z 上的状态集s 的分布 记为 s z 元胞自动机的动态演化就是在时间和空间的变化可记为 f s f 专s 二1 2 1 这个动态的演化是由每一个元胞的局部演化规则f 来决定的 对于一维空 间 元胞及其邻居可以记为s 2 r l 局部函数规则可以记为 厂 砰h 1js t l 2 之 在局部规则函数f 中 参数的输入 输出集均为有限集合 实际上 它是一 个有限的参照表 假设元胞的邻居半径r l f 的形式则形似如下 0 0 0 一0 0 0 1 一l o l 0 0 o 1 1 一0 1 0 0 1 1 0 l 0 l l 0 0 l l l 一l 对元胞空间内的元胞 套入上述局部函数 则可得到全局的演化 f c 0 厂 c 一 c c i 押 协3 7 第二章元细胞自动机的理论桀础 c i t 表示在位置i 处的元胞 我们就得到了一个元胞自动机模型 2 在拓扑学中的定义 假设元细胞空间的维数d 为l 设s 为一个有限集 这个有限集中有k 个符 号 z 为整数的全体集台 称z 到s 的映射s z 为构形空间 显然s z 就是用有限 集s 中的符号组成的双向的无限的符号序列的全部元素 是一维元胞自动机的 所有构形的集合 称a 乱i a o a l 为构形空间中的点 在s z 中引进任意两点 m 和n 之间的距离 d m 圪 万 m 咒膨一卜 2 4 其中当m i n i 时8 m i n i o 当m f i l n i 时8 m i n i l 然后 在s z 中可以建立起开 闭 紧等拓扑概念 在s z 中定义移位算子6 为6 m i m i 1 i e z 若连续映射f s z s z 产与6 可交换 即f 6 6 f 或对任意 的x s z 有f 6 m 6 f m 则称f 为元胞自动机 2 0 l 对于以上定义 我们很容易将它扩展到一个任意维空间 所要做的工作只 是将s z 记为s z q s 撕1 记为s 1 n 等 同时对一些描述作相应改变即可 总之 元细胞自动机是时间和空间都离散的动力学系统 分布在规则格网 l a t t i c eg r i d 中的每一个元胞 c e l l 取有限的离散状态 遵循同样的局部规则 依 据局部规则作同步更新 大量的元胞通过简单的相互作用构成动态系统的演化 形成不同的图形 元细胞自动机不同于一般的动力学模型 它不是由严格定义 的物理方程或函数确定来确定的 而是用一系列模型构造的规则 凡是满足这 些规则的模型都可以称作是元胞自动机模型 因此 元胞自动机是一类模型的 总称 或者说是一个方法框架 其特点是时间 空间 状态都离散的 每个变 量只取有限多个状态 且其状态改变的规则在时间和空间上都是局部的 2 2 元细胞的发展过程和种类 在元细胞的发展过程中 科学家们构造出了各种各样的细胞自动机 最初 的元细胞自动机 c e l l u l a ra u t o m a t a 由澳大利亚的数学家s t a n i s l a wm u l a m 1 9 0 9 1 9 8 4 与计算机之父冯诺曼j o h ny o nn e u m a n n 1 9 0 3 1 9 5 7 在1 9 4 0 年 都开始研究细胞自动机 于1 9 5 0 年代所提出 在形态表现上 细胞自动机是一 个离散型的动力系统 d i s c r e t ed y n a m i c a ls y s t e m s 在四十年代 j o h ny o n 8 第二章元细胞自动机的理论綦础 n e u m a n n 与共事的科学家们合作设计了可储存程式的数位电脑之后 他就对自 我复制发生兴趣 能储存程式的机器能不能自我复制 j o h nv o nn e u m a n n 逝世 后 a w b u r k s 完成了j o h nv o nn e u m a n n 的研究 4 早期的元细胞自自动机主 要集中于理论方面的研究 并且由于早期细胞自动机结构的复杂性而限制了其 发展应用 在2 0 世纪8 0 年代初 s w o f r a m 提出对细胞自动机进行简化 他建 议简化细胞自动机的状态空间和邻域半径 以获得具有组成单元结构的局部规 则性 单元之间作用的局部互连性和信息处理的高度并行性等优点的细胞自动 机 并提出了具有两个状态 邻域半径为一体的初等的元胞自动机 简化后的 元胞自动机不仅具有适合简单的层次结构 而且具有复杂的动力学特性 s w o l f r a m 对细胞自动机的简化极大推动了细胞自动机理论及其应用研究 事实上 有些科学家们进一步猜测 我们存在的这个地球上是否就是一种 极其复杂的细胞自动机 我们的生活环境的确与细胞自动机有很多相似的地方 宇宙是平行处理的 宇宙中的每一点受邻近状态的影响最大 宇宙各处遵循著 同样的自然律 虽然与整个宇宙相比 细胞自动机的规则是过于简单 但是它 里面所蕴含的道理可能与宇宙的机制是相通的 理论物理学家s t e p h e nw o l f r a m 1 9 5 9 就指出 1 4 1 细胞自动机的数学架构 与一些造成真实世界的复杂物理 系统之数学架构是完全一样的 也许这正是掌管遗传重任的d n a 所赖以工作的 原理 当你看到自然界那些贝壳或指纹曲折的图案时 不免要问 这么复杂的 图案要如何编码到d n a 里头呢 w o l f r a m 说 如果我猜的不错 那些图形是由 类似於细胞自动机的简单法则所产生的 而这样的编码显然是易如反掌 1 一维元细胞 初等元胞自动机 初等元胞自动机1 15 1 e l e m e n t a r yc e l l u l a ra u t o m a t a 简称e c a 就是一维元细胞 自动机它的状态集s 只有两个状态 o l 即状态个数k 2 邻居是一个以半径 r l 的一维元胞自动机 假设用每一个方格表示一个元胞的话 也就是每一个方 格的左 右两个方格是它的邻居 用图形表示每一个方格单元和它的邻居可以 表示如下 册 图2 1 一维元细胞模型 9 第二章元细胞自动机的理论基础 黑色的方格是当前细胞 两边的白色方格是它的邻居 由于状态集只有 0 l 或者说黑白两个状态 对于任意的一个方格加上它的两个邻居就三个方格 用 这3 个方格的状态组合一共就有2 3 8 种 这8 种情况为下图示 皿 皿叩咀 皿 口即l 图2 2 元细胞邻居的状态 它们表示的状态分别是 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 对于 状态数为2 邻居半径r l 的所有初等细胞自动自身和其邻居的状态组合就这8 种 作为最简单的元细胞自动机我们还可以用静止和运动 黑和白或者用生与 死来判断 不管用什么方式都无所谓 我们主要考虑它的运动规则 假设当前 的元细胞为c a 他在b 时刻的状态为s 咖 而它的两个邻居状态为s a 1 b s l 1 b 则c a 在b 1 时刻的状态就为s 咖i 如果用函数来表示的话就是 s a b r f s l b s a b s 1 b 2 5 其中 s 咖 0 1 从以上函数可以看出来 对于任意的一个初等元细胞和其邻居可以组合出 来的状态就8 种 所以元细胞的输入就是上面8 种状态组合之一 输出表示的 是每个元细胞的下一时刻状态 状态只可能有黑白两种 则规则的输出要么是 黑 要么是白 这样 任何一个输出规则就是一个或者一组转换 比如下图表 示的就是一个规则 这种规则也可以用图形表示如下 黑色方块代表l 白色方块代表0 1 0 奠定了基石 1 6 1 尊卵分别选择状态数为2 和3 半径为l 不同元胞自动机的编码 比如1 8 1 7 8 来比较一下元胞的状态 他们的状态图形如下 图2 4 几种常见的一维元细胞的图形 l l 第二章元细胞自动机的理论基础 图2 5 几种常见的二维图形 通过以上图形我们可以看出元细胞自动机经过若干步计算后任然停留在一 个固定的状态 它是在几种状态之间来回循环 是一个完全无序的随机状态 2 二维元细胞 生命游戏 在2 0 世纪6 0 年代末j h c o n w a y 提出了一种计算机游戏即生命游戏 c a m e o fl i f e 1 2 这种游戏与围棋游戏在某些特征上有相似之处 在围棋中有黑白两 种棋子 生命游戏中的元胞有 白 黑 两个状态 o 1 围棋的棋盘是规则 划分的网格 黑白两子分布在网格的交叉点上 棋子在空间的分布决定对方的 死活 而生命游戏的规则也是划分的网格 它的两个状态分布在网格内 根据 元胞的局部空间构形来决定生死 只不过规则比围棋还简单 生命游戏的构成 及规则如下 1 元细胞分布在规则的四方网格内 2 元细胞具有生与死两种状态 用o 代表 死 用l 代表 生 3 元细胞以相邻的8 个元细胞为邻居 即m o o r e 邻居形式 1 2 第二章元细胞自动机的理论基础 翻 图2 6 m o o r e 邻居形式 4 一个元细胞的生与死由其在该时刻本身的生死状态和八个邻居的状态来决 定 a 活细胞如果有二或三个邻居生存则可以活到下一世代 否则就会死于独居或 拥挤 b 死细胞如果恰好有三个活细胞邻居 则可以使之复活 也就是生出活细胞 二维元细胞具有产生动态图案和动态结构能力的元胞自动机模型 当元胞 半径和状态发生改变时它就能产生丰富的 有趣的图案 经过若干步的运算 有的图案会很快消失 而有的图案则固定不动 有的周而复始重复两个或几个 图案 有的婉蜒而行 有的则保持图案定向移动 形似阅兵阵等等 r j 晦i o 毋 r 竹 t tc i 膏 舢 u j a l e a t 睁 二 钔l 簟 l e d t ik 毗俯1 6 n o 母 屯 晦o iv 6 h ho l l l p 飘 l i t j u o蛔k a j t 龟 o o 和 l l l l o i d m l t h l 图2 7 生命游戏的状态图形 1 3 第二章元细胞自动机的理论幕础 还有很多类型的元胞自动机 由于能力有限 其他的不再做研究 2 3 细胞自动机的基本元素 元细胞胞自动机最基本的元素包括细胞 细胞空间 邻居及规则四部分 如图所示 简单讲 元胞自动机可以视为由一个元胞空间和定义于该空间的变 换函数所组成 图2 8 元细胞自动机的基本元素 1 细胞 细胞又可称为单元 基元或者是元胞 是细胞自动机的最基本的耶是最小 的组成部分 元胞分布在离散的一维 二维或多维的规则的空间网格上 拥有 自己的初始状态 并把每一个元胞的状态生与死的集合叫做元胞的状态集 状 态可以是 0 1 的二进制形式 或是 s o s 2 s i s d 整数形式的离散集 元胞 自动机的元胞某一时刻只能有一个状态变量 但在实际应用中 往往将其进行 了扩展 例如每个元胞可以假设拥有多个状态变量 2 细胞空间 元细胞在空间的分布形态就是元胞空间 1 7 l 1 元胞空间的几何划分 理论上讲元细胞可以使任意维数的欧几里德空间规则划分 但目前的研究 是主要集中在一维和二维的元胞自动机上 对于一维元胞自动机 元胞按等间 隔方式分布在一条向两侧无限延伸的直线上 二维的元胞自动机 元胞空间的划 分则可能有多种形式 常见的有三角形 四方形或者六边形三种网格排列 这 1 4 第二二章元细胞自动机的理论摹础 三种网格排列图如图所示 圈 口露 三角网格四方网格六边形网格 图2 9 元细胞空间的几何划分 这三种元胞空间的划分在构模时各有利弊 三角形的网格的优点是邻居的数目相对较少 在某些时候很有用 其缺点是 用计算机来表达和显示图形不方便 需要转换为四方形 四方形网格图形的优点是简单直观 特别适合于在计算机环境下进行图形 式的表达显示 其缺点是不能很好的模拟元细胞各向同性的状况 本文就是利 用四方网格来定位停车的 六边形网格图形的优点是能较好地模拟各向同性的现象 模型能更加自然 而真实 如格子气模型中的f h p 模型 其缺点同三角网格一样 在表达显示上 较为困难 复杂 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 指在边界外邻居的细胞状态是以边界为轴 的镜面反射 1 5 第二章元细胞自动机的理论基础 珊 i 纱 图2 1 0 反射边界 定值型边界 c o n s t a n tb o u n d a r y 指所有边界外细胞均取某一不变的常量 如 生 或 死 等 有时 在应用中 定值型更加客观 自然地模拟实际现象 还有可能采用 随机型边界 r a n d o mb o u n d a r y 即在边界实时产生随机值 需要指出的是 这几种边界类型在实际应用中 尤其是二维或更高维数的 建模时 可以相互结合 如在二维空间中 上下边界采用反射型 左右边界可 采用周期型 3 邻居 以上的细胞和细胞空间只表示了元细胞系统的静态部分 为了将动态部分 引入系统 必须加入演化规则 在元细胞自动机中 这些演化规则是定义在空 间局部范围内的 即一个元胞在下一时刻的状态决定于本身在该时刻状态和它 的邻居的细胞的状态 因而 在指定演化规则之前 必须明确哪些细胞是该细 胞的邻居 在一维细胞自动机中 通常以半径来确定邻居 与一个细胞相距在 一个半径的距离之内的所有细胞均被称为是该细胞的邻居 二维细胞自动机的 邻居定义较为复杂 但通常有以下几种形式 我们以最常用的规则四方网格划 分为例 见下图 黑色细胞为中心细胞 灰色细胞为其邻居 它们的状态一起 来计算中心细胞在下一时刻的状态 嬲 隧 疆 幽 圈髑 1 v o nn e u m a n n 2 m o o r e 3 m o o r e 的扩展 图2 1 l 细胞臼动机的邻居模型 1 6 第二章元细胞自动机的理论慕础 1 冯 诺依曼 v o nn e u m a n n 型细胞 一个细胞的上 下 左 右相邻四个细胞为该细胞的邻居 这里 邻居半 径r 为1 2 摩尔 m o o r e 型细胞 一个细胞的上 下 左 右 左上 右上 右下 左下相邻八个细胞为该 细胞的邻居 3 扩展的摩尔 m o o r e 型细胞 将以上的邻居半径r 扩展为2 或者更大 即得到所谓扩展的摩尔型邻居 4 马哥勒斯 m a r g o l u s 型细胞 图2 1 2 格子气泡 这是一种同以上邻