元胞自动机动力学行为分析及反问题研究

论文摘要

本文研究了一维二值元胞自动机的有关数学性质、动力学演化行为和反问题,主要内容如下：研究了Galois域上的一类一维二值元胞自动机,即GF(2)元胞自动机,又称加法元胞自动机。介绍了加法元胞自动机的工作原理并给出了环状元胞自动机和非环状元胞自动机的算例。给出了GF(2)元胞自动机有长度K的环的必要条件和长度K的周期环中含有O元素的充分必要条件,即K环定理Ⅰ和K环定理Ⅱ。研究了元胞自动机动力学行为的复杂性。通过分析元胞自动机“混沌的边缘”思想以及复杂系统的涌现性,给出了“混沌的边缘”成为复杂科学研究核心概念的理由。利用元胞自动机演化信息熵和文字熵刻画了半径为3的一维二值元胞自动机在时间意义上的动力学行为,给出了元胞自动机演化信息熵—文字熵平面与元胞自动机行为的域对应关系,一定程度上实现了元胞自动机定性行为的定量度量。分析了Langton参数及其变化规律与元胞自动机动力学行为的关系。提出了组合规则熵刻画元胞自动机规则的方法,并给出了组合规则熵的相关性质及其与Langton参数间的关系。统计出了Langton参数下不同组合规则熵区间所对应的元胞自动机动力学类型的分布情况。研究了元胞自动机的反问题。给出了“混沌的边缘”对仿生算法生命的新解释,为算法的构造和改进提供了指导思想。根据一维二值元胞自动机的特点,提出了基于离散粒子群求解元胞自动机反问题的通用算法,并利用该算法对元胞自动机的密度分类问题和准周期三行为规则的搜索问题进行了实验,给出了与基于遗传操作的元胞自动机规则搜索算法的对比。提出了通过组合规则熵压缩元胞规则空间来提高搜索效率的新算法,并与通过Langton参数来搜索具有某一特定动力行为元胞自动机的方法进行了对比。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 元胞自动机的研究背景及意义
• 1.2 元胞自动机理论研究的历史及现状
• 1.3 元胞自动机的应用
• 1.4 本文的主要工作
• 第二章 元胞自动机简介
• 2.1 元胞自动机模型的构成
• 2.2 元胞自动机的有关定义
• 2.3 元胞自动机的动力学分类
• 2.4 两种典型的元胞自动机
• 2.4.1 生命游戏
• 2.4.2 Langton蚂蚁
• 第三章 GF（2）元胞自动机分析
• 3.1 GF（2）元胞自动机
• 3.1.1 Galois域
• 3.1.2 GF（2）元胞自动机的定义
• 3.2 GF（2）元胞自动机描述及K环定理
• 3.2.1 GF（2）元胞自动机的矩阵描述
• 3.2.2 GF（2）元胞自动机的K环定理
• 3.3 小结
• 第四章 元胞自动机复杂性研究
• 4.1 元胞自动机与复杂性
• 4.1.1 复杂性理论
• 4.1.2 元胞自动机"混沌的边缘"与复杂系统的涌现性
• 4.2 元胞自动机演化行为复杂性度量
• 4.2.1 熵
• 4.2.2 元胞自动机与熵
• 4.2.3 元胞自动机演化行为的度量
• 4.3 Langton参数与复杂性分析
• 4.3.1 Langton参数
• 4.3.2 Langton参数与元胞自动机动力学行为研究
• 4.4 元胞自动机组合规则熵与复杂性分析
• 4.4.1 组合规则熵的定义及性质
• 4.4.2 组合规则熵与Langton参数
• 4.4.3 组合规则熵与元胞自动机动力学行为研究
• 4.5 小结
• 第五章 元胞自动机反问题研究
• 5.1 元胞自动机反问题研究介绍
• 5.2 基于仿生算法的元胞自动机反问题研究
• 5.2.1 基于遗传算法的元胞自动机反问题研究
• 5.2.2 基于粒子群算法的元胞自动机反问题研究
• 5.2.3 元胞自动机"混沌的边缘"与演化算法
• 5.3 元胞自动机的全局计算问题规则搜索
• 5.3.1 密度分类问题
• 5.3.2 同步问题
• 5.4 元胞自动机准周期三行为规则搜索
• 5.4.1 准周期三行为
• 5.4.2 实验结果及分析
• 5.5 基于组合规则熵的元胞自动机反问题研究
• 5.5.1 基于组合规则熵的元胞自动机规则的搜索算法
• 5.5.2 实验结果及分析
• 5.6 小结
• 第六章 总结与展望
• 参考文献
• 致谢
• 附录