基本信息
- 项目名称：
- 基于组合规则熵的元胞自动机行为研究
- 来源：
- 第十二届“挑战杯”省赛作品
- 小类：
- 机械与控制
- 大类：
- 自然科学类学术论文
- 简介：
- 本项目在分析Langton参数的基础上提出了用组合规则熵来描述元胞规则的方法，并通过数学推理和计算机实验的方法证明了其在进一步刻画元胞自动机规则及其动力学行为时的有效性．
- 详细介绍：
- 元胞自动机是von Neumann提出的一种时间、空间、状态都离散的动力学模型．目前，它已成为非线性科学领域的一种重要研究方法，是人工生命科学研究的重要方向，其动力学行为研究也成为复杂性理论和计算普遍性研究的重要内容．元胞自动机的应用已引起国内外学者的高度关注，但其理论发展相对缓慢．Conway证明了元胞自动机具有通用图灵机的计算能力，并在适当条件下可以模拟任何计算机．Wolfram在计算机实验基础上仿照动力系统理论的分类将元胞自动机演化行为定性的分为四类，由此奠定了元胞自动机动力学行为研究的理论基础．迄今为止，引人注目的研究是Langton通过对元胞自动机规则和其动力学行为关系研究提出的Langton参数及“混沌的边缘”． 元胞自动机研究面临两类问题．一是给定元胞自动机规则，分析和研究其性质；二是搜索具有指定演化类型的元胞自动机规则．但元胞自动机行为的不可判定性为这两类问题的解决带来了不小的困难．Langton参数通过将元胞规则空间参数化来研究元胞自动机的动力学行为,是统计意义下对元胞自动机规则整体性质的刻画．因此，即使在初始构型一定的情况下，它对元胞自动机演化行为的描述也比较困难．图1给出了Langton参数等于0.5，相同初始构型下不同的元胞自动机演化行为示例．为进一步对元胞自动机规则及其动力学行为进行细致的刻画，本文在分析Langton参数的基础上提出了用组合规则熵来描述元胞规则的方法，并通过数学推理和计算机实验的方法证明了其在进一步刻画元胞自动机规则及其动力学行为时的有效性．
作品专业信息
撰写目的和基本思路
- 元胞自动机已成为非线性科学领域的一种重要研究方法。引人注目的研究是Langton通过对元胞自动机规则和其动力学行为关系研究提出的Langton参数及“混沌的边缘”． 本项目在分析Langton参数的基础上提出了用组合规则熵来描述元胞规则的方法，并通过数学推理和计算机实验的方法证明了其在进一步刻画元胞自动机规则及其动力学行为时的有效性
科学性、先进性及独特之处
- 元胞自动机是von Neumann提出的一种时间、空间、状态都离散的动力学模型．本项目从信息学、数学和计算机实验相结合的方法出发，针对半径为3的一维二值元胞自动机给出了不同Langton参数下各类型元胞自动机的分布情况并提出了用组合规则熵刻画元胞自动机规则的方法．
应用价值和现实意义
- 虽然经典数学在加法元胞自动机和初等元胞自动机的研究方面取得了一系列理论成果，但当元胞半径变大时研究难度变大．本项目针对半径为3的一维二值元胞自动机给出了不同Langton参数下各类型元胞自动机的分布情况并提出了用组合规则熵刻画元胞自动机规则的方法．组合规则熵有利于在Langton参数的基础上实现对元胞自动机性质及动力学行为更为细致的刻画，并可以提高对指定动力学演化类型的元胞自动机的搜索效率．
学术论文摘要
- 为在Langton参数的基础上对一维二值元胞自动机的性质及其动力学行为进行更细致的分析，提出了用组合规则熵刻画元胞自动机规则的方法并证明了一维二值元胞自动机组合规则熵的最大值和最小值定理．实验还进一步表明组合规则熵能够在Langton参数的基础上对元胞自动机的规则进行更细致的刻画，有利于对元胞自动机动力学行为的分析和提高对指定类型元胞自动机的搜索效率．
获奖情况
- 无
鉴定结果
- 无
参考文献
- [1] von Neumann J．The general and logical theory of automata．New York：Wiley，1951，1-26 [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] 周成虎，孙战利，谢一春．地理元胞自动机研究．北京：科学出版社，2001，29-31 [6] Wolfram S．Computation theory of cellular automata．Communi-cations in Mathematical Physics，1984，96(1)：15-57 [7] Langton C．Computation at the edge of chaos：Phase transitions and emergent computation．Physica D，1990，42(1)：12-27 [8] Bastien Chopard，Michel Droz著，祝玉学，赵学龙，译．Cellular Automata Modeling of Physical Systems．北京：清华大学出版社，2003，16-18
同类课题研究水平概述
- 元胞自动机是von Neumann提出的一种时间、空间、状态都离散的动力学模型．目前，它已成为非线性科学领域的一种重要研究方法，应用已引起国内外学者的高度关注，但其理论发展相对缓慢．国内研究也刚刚起步。 采用什么手段来研究是至关重要的．本项目在Langton参数的基础上对元胞自动机的规则进行更细致的刻画，有利于对元胞自动机动力学行为的分析和提高对指定类型元胞自动机的搜索效率．
