188宝金博页面版

第 l9卷 第4期 计算机仿真 2O O 2年7月 文 章编 号 ： 1 006 —93z,s (x ~n ) o4—0027 —04 基 于 M atlab 的 元 胞 自动 机 的 仿 真 设 计 金 小 刚 (浙 江 大学计算 机 系 ． 浙 江 杭 州 310028) 摘要 ： 元胞 自动 机不 仅是理 论 计算机 科学 领域 的一个 重要 的计 算模 型 ， 而且 可视 为一无 限 维的 离散 动力 系统 。 被 广 泛应 用 于 自然科 学 和杜会 科学 各领 域 的复杂性 的研 究 中 ， 是 一个重 要 的研 究 方法 和 工具 。该 文 以 Maf l ab 为开 发 工 具 ， 开发 了元胞 自 动机 的可 视模 型 ， 为 其在各 个 领域 的复杂 性研 究提供 了一 个 简易 、 可行 的计算 机仿 真工 具 。 关键 词 ： 元 胞 自动机 ； 复 杂性 ； 仿 真 软件 中图分 类号 ： TP301 文 献标 识码 ： A l 引 言 元胞 自动机? (Cen~ ar Automata， 简称 CA )是 von Neumann 最 早 提 出用 于模 拟生 命 系统 所具 有 的 自复 制 功 能 的 ， 其 数 学 构 造 非常 简单 ： 时 问 、 空 间和状 态 变 量都 是 离 散集 ， 且 状 态 有 限 ， 根据 简 单 的局 部规 则 同时运 行 而得 到 所 有 元胞 在 某 时 刻 的状 态全体 ， 即 CA 的一 个构 形 ( Conf i guration) ， 元 胞 自动 机 的 构 形 随时 间 变化 而呈 现 出丰 富而 复 杂 的瞬 时 演 化过 程 ， 因 此 元 胞 自动 机可 作 为一 个无 穷 维动 力 系 统 ， 它 不 仅是 计 算 理 论 的重 要模 型 ， 吸引 了大批 计 算 机领 域 的科 学 去研 究 其 计算 能 力 ， 而且 广 泛应 用 于 如数 学 、 物理 学 、 生 物 学 、 化 学 、 地理 学 和 经济 学等 各学 科 中 的非 线 性 现 象 和分 形 结 构 的研 究 。 在 美 国 的 Santa Fe Inst i tute 汇 集 了一批 各 个 领域 的杰 出科 学 家 ， 他 们在 “ 复杂性 ” (co mplexiq )A旗 帜 的弓 l 导 下 ， 对 元 胞 自动 机 进 行 广泛 的研究 ： “ 元 胞 问 如 此 简 单 的 局 部 相 互 作 用 组 成 的 系统 为何 会 产 生复 杂 的计算 过 程 ， 而且 会 突 现 出 某种 未 知 的 模 式 ? ” 在 中 国 ， 元 胞 自动 机 应 用 也是 方 兴 未 艾 ， 它 被应 用 于 包括 计算 ( Computation) 、 构 造 ( Construction) 、 生 长 (Growth) 、 复 制( Repro duct i on) 、 竞 争 ( Competit i on) 与 演 化 ( Evolution) 等现 象 的研 究 ， 同 时 ， 也 为 动 力 学 理 论 中 有 关 混 沌 ( Chaos) 、 分 形 ( Fraeta1)等 系统整 体 行为 与 复杂 现象 的研 究 提 供 了 一个 有 效 的模 型工 具 。本 文利 用 已被 广 泛使 用 的 Madab 为 开发 工 具 ， 利用 其提 供 的 图形 化 用 户 界 面 ( GUI) ， 实 现 了元 胞 自动 机 的 可视 化 编程 ， 为不 同领 域 的研 究 工作 者提 供 了一个 简单 的工 具 。 2元胞 自动机理论 自从 von Neuman 六 十年代 提 出元 胞 自动 机模 型 后 ， 其 研 究一 直停 滞 了十余 年 ， 直 到 1970 年 J ． H． Conway 编 制 了一 个 名 为“ 生命 游 戏 ” 的游 戏程 序后 才再 次 掀 起 ， 特别 是 从八 十年 基金 项 目： 国家 自然 科学 基金 ( 60103015) 和 浙江 省 教委 科研 基 金 的 资 助 收稿 日期 ： 2001一I I 一30 代 起 ， 元胞 自动 机 的理 论研 究 出 现 了新 的 进展 ， 科 学 家们 成 功 的利 用 这个 模 型在 简单 规则 下 使 系统 涌 现 出 了 吸引 子 、 分 叉 、 自组织 和 自复制 等 现 象 ， 这 一研 究 结果 使 得 元胞 自动 机 成 为研 究 复杂 系统 的重要 工具 。 元 胞 自动 机 是 由分 布 在 规 则 网 格 中 的每 一 个 元 胞取 有 限的离 散状 态 ， 遵 循 确 定 的局 部 规则 做 出 同 步 更新 ， 即大 量 元 胞通 过 简单 的 局 部 相 互 作 用 而 构 成 的动 力 系 统 。不 同于 般 的动 力 学 模 型 ， 元 胞 自动 机 不 是 由严 格 的物 理 方 程 确 定 ， 而是通 过 构造 一 系 列模 型 的 规则 来 实现 的 ， 这 恰 恰 增 强 了其表 达 复 杂关 系 的能力 ， 为其 在 复杂 性 领 域 的应 用 奠定 了 一基 础 。 元胞 自动 机 由 元胞 、 元 胞 的状 态 空 间 、 邻 居 及 局 部 规 则 四部分 组 成 ， 可 用一 个 四元 组表 示 ： A = ( ， S ， N ， f ) 其 中 A 为一 个 元 胞 自动 机 ； 间 的维 数 ； S 为 元胞 的有限 状 态集 ； N 表 示一 个所 有邻 域 内元 胞 的组 合 ， 为 包 含 n 个 不 同 元 胞 的 空 间 矢 量 ， 表 示 为 Ⅳ = ( s1， s2， ? ， s ) ， n是 邻居 元 胞个 数 ， s ∈ z ( 整数 集 ) ， i = l ， 2， 为元 胞 空 间 ， d 为 元 胞空 ?， n； 厂 表 示 将 1) 元 胞 和元胞 空 间 ： 元 胞 又 可 称 为 基元 ， 是 元胞 自动 机 的最基 本 的 组成 部分 ， 分 布在 离散 的一 维 、 二 维 或 多维 欧几 里德 空 间 的格点 上 。 而 元胞 所 分布 在 的空 间 网格集 合 就 是 元 胞空 间 ， 它 可 以是任 意维 数 欧 几 里德 空 间 的规 则 划 分 。 由 于 计 算机 显示 的原 因 ， 目前研 究 集 中在 一维 和二 维 ， 对 于一 维 元胞 自动机 ， 元 胞 空间 的划 分 只有 一 种 ， 而二 维 元胞 自动 机 ， 二维 元胞 空 间通 常 可 以按三 角 、 正 方形 或六 边 形 三种 网格 排 列 。 三 种元 胞空 间划 分 在 模 拟 时 各有 优 缺 点 ， 三 角 网 格 和 六 边形 网格 在 计算 机 的表 达 和显示 不 方便 ， 通 常 都 要借 助 影 射 转换 正方 形 网格 处 理 。 另 一 个 需 要 考 虑 的 问题 是 ， 理 论 上 的 元胞 空 问通 常是 在 各维 上是 无 限 的 ， 但 却无 法 在 计算 机 上 实 现 ， 因此 ， 我 们 需 要 定 义 不 同 的边 界条 件 。 归纳 起 来 ， 边 界 条 件 主要 有 三种类 型 ： 周期 型 、 反 射 型 和定 值 型 ， 这 三种 边 界 类 型在 实 际应 用 中 ， 尤 其 是 二 维 或 更 高 维 数 的构 模 时 ， 可 以相 映射 到 S 上 的一个 状 态转 换 函数 。 一2 7— 维普资讯 http://www.cqvip.com