学位论文 > 优秀研究生学位论文题录展示

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

作 者: 田晓东
导 师: 张庆灵;段晓东
学 校: 东北大学
专 业: 运筹学与控制论
关键词: 元胞自动机 动力学行为 元胞演化熵 组合规则熵 Langton参数 混沌的边缘 仿生算法
分类号: TP301.1
类 型: 硕士论文
年 份: 2008年
下 载: 77次
引 用: 0次
阅 读: 论文下载
 

内容摘要


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

全文目录


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

相似论文

  1. 高光谱图像空—谱协同超分辨处理研究,TN911.73
  2. 基于电子海图的海上溢油预测系统的设计与实现,X55
  3. 几种秘密共享方案的研究,TN918.1
  4. 基于Agent的无线传感器网络自组织演化机制研究,TN929.5
  5. SRAM型FPGA单粒子故障传播特性与测试方法研究,V467
  6. 基于元胞自动机和模糊控制的交通流模型研究,U491.112
  7. 基于地理元胞自动机的林火蔓延模型与模拟研究,S762
  8. 基于元胞自动机的无线传感器网络能量均衡控制研究,TP212.9
  9. 基于混合元胞自动机方法的结构拓扑优化研究,O342
  10. 荧光探针法研究硅丙核/壳乳液的聚合及其动力学行为,O631.5
  11. 基于GIS和CA模型的城市化土地利用扩展模拟与预测,P208
  12. 复杂数据多属性指标的估计模型,O242.1
  13. 基于元胞自动机方法的再结晶过程数值模拟,TG111.7
  14. 半固态铝合金浆料制备过程的多尺度模拟及优化设计,TG249.9
  15. Al-Si合金近液相线铸造组织多尺度模拟,TG249.9
  16. 基于SLEUTH模型的焦作市城市空间结构演化研究,TU984.113
  17. 基于元胞自动机的楼宇疏散仿真与疏散指挥策略优化,TU998.1
  18. 基于粒计算的三层结构的交通流模拟,U491.112
  19. 基于元胞自动机模型的公交线路系统建模与模拟,U491.17
  20. 城市道路车辆换道模型及换道影响研究,U491.112
  21. 基于元胞自动机的交通流研究,U491.112

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 一般性问题 > 理论、方法 > 自动机理论
© 2012 www.xueweilunwen.com