元胞自动机的进化与计算研究

论文摘要

自然进化产生了许多系统,其中一些行为简单、局部联系的结构往往能产生全局影响。为了模拟这种现象,本文采用元胞自动机模型,按照一定的局部规则在离散的时间维上进行进化与计算,通过个体元胞以及元胞之间的相互作用来体现整个复杂系统。首先,对元胞自动机原理进行阐述,在此基础上研究其自身的进化特征。对于一维二状态的元胞自动机,通过判断“0”、“1”状态的元胞数量研究密度分类问题,提出了正确解决密度分类的两个必要条件并进行了有效证明。对于边界条件是周期型的二维元胞自动机,按元胞状态变化曲线对其特性进行描述。其次,利用元胞间的并行性及其交互作用来模拟信号传递和逻辑门功能,研究同步2状态5邻居型元胞自动机和异步6状态5邻居型元胞自动机的计算能力;并设计了多种规则构成功能不同的元胞模块,使得由元胞构成的信号能够顺利通过复杂的元胞空间,最终不改变其信号结构。最后,将元胞自动机进化机制应用于机器人路径规划,对移动机器人及其周围环境建立元胞自动机模型。机器人环境空间完全已知时,利用启发式算法与元胞自动机模型结合的方法,通过反复遍历具有最低耗费值的一系列元胞生成最优路径。并利用多层次的交互式元胞自动机,在方向有约束和地形耗费不同的环境中寻找机器人最优路径。机器人环境空间部分未知时,利用人工势场法和元胞自动机模型结合的方法,以寻找临时目的地为途径,最终寻找到终点目标,仿真表明两者结合后机器人能成功搜索到无碰路径。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 概述
• 1.2 元胞自动机在各领域中的应用
• 1.2.1 元胞自动机在社会领域的应用
• 1.2.2 元胞自动机在经济领域的应用
• 1.2.3 元胞自动机在计算机科学领域的应用
• 1.3 本文的研究内容和结构安排
• 第二章 元胞自动机理论及其发展
• 2.1 元胞自动机的概念
• 2.2 元胞自动机的构成
• 2.2.1 元胞
• 2.2.2 元胞空间
• 2.2.3 邻居
• 2.2.4 规则
• 2.3 元胞自动机的特征
• 2.4 元胞自动机理论的发展
• 2.4.1 沃尔夫拉姆对元胞自动机的分类
• 2.4.2 元胞自动机与“混沌边缘”学说
• 2.4.3 元胞自动机与人工生命
• 第三章 元胞自动机的进化机制
• 3.1 引言
• 3.2 一维元胞自动机的进化机制
• 3.2.1 初等元胞自动机的进化
• 3.2.2 密度分类分析
• 3.2.3 密度分类的必要条件
• 3.2.4 同步化分析
• 3.3 二维元胞自动机的进化机制
• 3.3.1 平稳型元胞自动机
• 3.3.2 周期型元胞自动机
• 3.3.3 复杂型元胞自动机
• 3.3.4 交互式二维元胞自动机
• 3.4 小结
• 第四章 元胞自动机的通用计算
• 4.1 引言
• 4.2 图灵机与元胞自动机的计算
• 4.3 非统一2 状态5 邻居型元胞自动机
• 4.3.1 信号与通道
• 4.3.2 逻辑门
• 4.3.3 时钟信号和内存单元
• 4.4 异步6 状态5 邻居型元胞自动机
• 4.4.1 异步元胞自动机的定义
• 4.4.2 信号传送
• 4.4.3 模块配置
• 4.4.4 模块的组合应用
• 4.5 小结
• 第五章 基于元胞自动机模型的移动机器人路径规划
• 5.1 引言
• 5.2 启发式的元胞自动机模型
• 5.2.1 建立环境和机器人的元胞自动机模型
• 5.2.2 启发式算法描述
• 5.2.3 启发式算法步骤
• 5.2.4 算法应用仿真
• 5.2.5 元胞自动机模型的扩展
• 5.3 基于人工势场法的元胞自动机模型
• 5.3.1 人工势场法
• 5.3.2 基于元胞自动机模型的人工势场法
• 5.3.3 算法应用仿真
• 5.4 小结
• 第六章 总结与展望
• 6.1 论文工作总结
• 6.2 研究与展望
• 参考文献
• 致谢
• 在学期间研究成果及发表的学术论文