一维五邻居元胞自动机的演化行为.pdfVIP

第 26卷第 lO期 (总第 178期) 系 统 工 程 VoI．26．No．10 2008年 1O月 SystemsEngineering Oct．．2008 文章编号：1001—4098(2008)10—0119—04 一 维五邻居元胞 自动机的演化行为 朱留华 ，吕集尔 ，郑容森 ，孔令江。，刘慕仁 (1．玉林师范学院 物理与信息科学系，广西 玉林 537000； 2．广西师范大学 物理与电子工程学院，广西 桂林 541004) 摘 要 ：依据一维五邻居元胞 自动机 的演化特点，借助于卡诺图，导出其演化规则的函数形式 。进一步利用推 导 出的规舅l】的函数形式 ，给 出演化规则 (eOe．feOeO) 的性质及性质证 明和计算机数值模拟。 关键词 ：元胞 自动机 ；卡诺 图；函数形式 ；演化性质 中图分类号 ：TP391 文献标识码：A 元胞 自动机作为21世纪科学研究中一个异常活跃 的 来表示 ，在时刻t构形记为 ： = { ， +，…，X ，…， 前沿领域 ，是复杂性科学的核心技术之一 。元胞 自动机是 z：一，z：)，其中 — O0，每一个符号，即一个元胞 都取 一 种时间、空间、状态均离散 ，具有时空计算特征的网格动 布尔变量，即0或 1两个状态，则在下一个时刻构形演化 力学模型[1]，是一个集数学、物理学、计算机科学、生物 为： ”一 (zt一+l，zt一+l+ 一，z01十，…， ， }，其中，每 学、系统科学等多学科交叉的边缘领域 ，有广泛应用前景 一 个元胞 由上一时刻的相应元 胞按法则 z：” = 的研究方法。当前其应用领域广泛涉及到社会学、生物学、 厂(一。，，zf+。)决定。这里的厂称为元胞 自动机的局部规 生态学、信息科学、计算机科学、数学、物理学、化学、地理 则 [1]。对整个构形而言，就有 F，使得 F( )一 “，这里 学、环境学、军事学等 ，并取得 了丰硕 的成果，如用于人工 F称为元胞 自动机 的全部规则。 生命[3]、地震波模拟n]、交通系统的仿真与优化[】、国家间 为 了研究规则的特点及演化性质 ，S．Wolfram 以逻 通过战争彼此兼并的预测 [6]、地理信息系统的开发[]等 辑运算方式给 出了一维三邻居元胞 自动机演化规则 ，的 但是，元胞 自动机作为一种全新的方法 ，目前的研究仍不 形式，如 9O号规则为： = 一。0 五t+。(0 表示异或运 完整 。无论是对元胞 自动机本身的演化行为及相关理论的 算)。这种表示方法对 256种规则来说不容易求 出，且不 研究，还是应用元胞 自动机机理来研究其它学科 ，都成为 便于分析。 研究的前沿和热点。近年来 ，国内也有一些相关理论的研 文献[9]利用待定系数法，给出了一维三邻居元胞 自 究，但理论研究的焦点多集中于初等元胞 自动机 ，因为其 动机 32种合法演化规则的函数形式，若借助于此方法将 演化规则简单 ，数 目较少 ，处理起来相对容易 其推广至一维五邻居元胞 自动机较为困难 ，因为其中涉及 本文首先将初等元胞 自动机拓展到一维五邻居元胞 的变量多达 32个，同时若将二进制数所对应的十进制数 自动机，接着依据一维五邻居元胞 自动机的演化特点，对 作为此类元胞 自动机的规则代码，表示起来相当麻烦，演 演化规则系统命名；其次借助于卡诺图8【]，给出其演化规 化规则多达 2种 。 则的函数形式；最后对演化规则 (eOefeOeO) 的演化行为 进行分析和研究。本文从不同视角得到的结果有助于对元