基本信息
- 项目名称：
- 基于演化熵的元胞自动机行为度量
- 来源：
- 第十二届“挑战杯”省赛作品
- 小类：
- 机械与控制
- 大类：
- 自然科学类学术论文
- 简介：
- 本项目通过计算元胞自动机演化熵实现了对一维二值元胞自动机演化行为的度量，给出了各类型域在演化熵平面的分布情况，分析了不同Langton参数下演化熵的分布，对Langton参数下动力学行为变化规律给进行了更进深入的分析．
- 详细介绍：
- 元胞自动机是von Neumann提出的一种时间、空间、状态都离散的动力学模型．目前，它已成为非线性科学领域的一种重要研究方法，是人工生命科学研究的重要方向，其动力学行为研究也成为复杂性理论和计算普遍性研究的重要内容．目前，元胞自动机的应用已引起国内外学者的广泛关注，其理论研究也取得了一定的进展．Conway证明了元胞自动机具有通用图灵机的计算能力，并在适当条件下可以模拟任何计算机．Wolfram在计算机实验基础上仿照动力系统理论的分类将元胞自动机演化行为定性的分为四类，由此奠定了元胞自动机动力学行为研究的理论基础．迄今为止，引人注目的研究是Langton通过对元胞自动机规则和其动力学行为关系研究提出的Langton参数以及“混沌的边缘”的概念．国内学者对元胞自动机的应用也进行了广泛研究，但其理论研究却刚刚起步，研究重点主要是初等元胞自动机． 本文通过计算元胞自动机演化熵实现了对一维二值元胞自动机演化行为的度量，给出了各类型域在演化熵平面的分布情况，分析了不同Langton参数下演化熵的分布，对Langton参数下动力学行为变化规律给进行了更进深入的分析．
作品专业信息
撰写目的和基本思路
- 目前，元胞自动机已成为非线性科学领域的一种重要研究方法．引人注目的研究是Langton通过对元胞自动机规则和其动力学行为关系研究提出的Langton参数及“混沌的边缘”． 本项目通过计算元胞自动机演化熵实现了对一维二值元胞自动机演化行为的度量，给出了各类型域在演化熵平面的分布情况，分析了不同Langton参数下演化熵的分布，对Langton参数下动力学行为变化规律给进行了更进深入的分析．
科学性、先进性及独特之处
- 元胞自动机是von Neumann提出的一种时间、空间、状态都离散的动力学模型．本项目通过计算元胞自动机演化熵实现了对一维二值元胞自动机演化行为的度量，给出了各类型域在演化熵平面的分布情况，分析了不同Langton参数下演化熵的分布，对Langton参数下动力学行为变化规律给进行了更进深入的分析．
应用价值和现实意义
- 本项目从信息学和计算机实验相结合的方法出发，利用元胞演化熵对半径较大元胞自动机时间意义上动力学行为进行了度量，是空间熵度量的补充，避免了拓扑熵计算的复杂性，从而可以实现指定动力学类型元胞自动机的自动搜索．实验发现一维二值元胞自动机的动力学行为变化规律具有以Langton参数为0.5为中心呈对称性的特点，是对Langton参数在描述元胞自动机动力学行为普适规律的有效补充．
学术论文摘要
- 为实现计算机自动识别和搜索特定类型的一维二值元胞自动机，通过计算其演化熵的方式，实现了对一维二值元胞自动机动力学行为描述的度量，并给出了演化熵平面类型域与其不同动力学行为之间的对应关系，最后结合演化熵分析了不同Langton参数下一维二值元胞自动机动力学行为的分布情况，发现一维二值元胞自动机的Langton参数在刻画其动力学行为时与普适规律不符，而具有以参数0.5为中心的对称性．
获奖情况
- 无
鉴定结果
- 无
参考文献
- [1] 周成虎，孙战利，谢一春．地理元胞自动机研究[M]．北京：科学出版社，2001，29-31 [2] Melanie M．Computation in cellular automata：a selected review [EB/OL]． 1~41 [3] Guisado J， Jimenez F， Fernandez F．Cellular Automata and Cluster Computing：an Application to the Simulation of Laser Dynamics．Advances in Complex System，2007，10(1)：167-190 [4] Christian D，Mario G，Marco T．Performance and Roubustness of Cellular Automata Computation on Irregular Networks．Advances in Complex System，2007，10(1)：85-110 [5] Wolfram, S．Computation theory of cellular automata[J]．Communications in Mathematical Physics，1984，96(1)：15-57 [6] Langton G．Computation at the edge of chaos：Phase transitions and emergent computation[J]．Physica D，1990，42(1)：12-27 [7] 曹兴芹，王能超．新型细胞自动机规则空间的参数化[J]．计算机科学，2007，34(3)：145-147 [8] 朱留华，陈时东，孔令江等．基于卡诺图初等元胞自动机的演化规则[J]．广西师范大学学报2007，25(1)：5-8 [9] Bastien C，Michel D．Cellular Automata Modeling of Physical Systems[M]．祝玉学，赵学龙 译．北京：清华大学出版社，2003，16-18
同类课题研究水平概述
- 目前，元胞自动机的应用已引起国内外学者的广泛关注，其理论研究也取得了一定的进展．Conway证明了元胞自动机具有通用图灵机的计算能力，并在适当条件下可以模拟任何计算机．Wolfram在计算机实验基础上仿照动力系统理论的分类将元胞自动机演化行为定性的分为四类，由此奠定了元胞自动机动力学行为研究的理论基础．迄今为止，引人注目的研究是Langton通过对元胞自动机规则和其动力学行为关系研究提出的Langton参数以及“混沌的边缘”的概念． 国内学者对元胞自动机的应用也进行了广泛研究，但其理论研究却刚刚起步，研究重点主要是初等元胞自动机． 本文通过计算元胞自动机演化熵实现了对一维二值元胞自动机演化行为的度量，给出了各类型域在演化熵平面的分布情况，分析了不同Langton参数下演化熵的分布，对Langton参数下动力学行为变化规律给进行了更进深入的分析．
