基于细胞自动机的协同演化优化方法

《基于细胞自动机的协同演化优化方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于细胞自动机的协同演化优化方法附表索引表5．1SGA与本算法的比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．37表5．2异步并行算法与本实验的比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．38表5．3本算法的统计结果⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯39表5．4GT算法与本算法的结果比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．41表5．5不同维度自动机的收敛代数表⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯42VIn工程硕上学位论文1．1细胞自动机简介第1章绪论细胞自动机(CellulafAutomata)，简称C

2、A，也称为元胞自动机、点格自动机、分子自动机或单元自动机。它是由细胞、细胞空间、邻居及演化规则组成的。细胞自动机是定义在一个具有离散、有限状态的细胞组成的细胞空间上，并按照一定演化规则，在离散的时间上演化的动力学系统。散布在细胞自动机规则格网中的每一细胞(Cell)取有限的离散状态，遵循同样的作用规则，依据确定的局部规则作同步更新。1934年数学家Pitts与神经学家McCulloch共同提出了一种由形式神经元组成的系统(FormalNeurons)组成的系统，并赋予它具有处理和传递大脑神经元信息行为的逻辑规则。他们证明这种形式的神经元系统的计算能

3、力与“图灵一(Turing)机等价。现代的计算机之父JohnVonNeumann也在同一时期试图解决生命系统中的一个悖论，即：能否制造一类人造系统，使之具有自复制能力，这就是所谓的自繁殖【1'21。JohnVonNeumann从网格模型或称为细胞自动机入手，来模拟所要研究的具体问题。从而对细胞自动机的一些基本问题进行了研究。VonNeumann提出具有VonNeumann邻域和28状态的细胞自动机可以作为通用计算机，Codd把其状态数减少到8，Banks将之减少到4状态。假如考虑Moore邻域，那么仅仅需要二个状态就能获得通用自动机。Conway在

4、著名的计算机单人跳棋游戏一“生命游戏"，就展现了这样的通用自动机13l。很自然的我们会问这样一个问题：能不能通过1．D细胞自动机获得通用计算性，Smith给出了肯定的回答，他证明了下面的定理：给定一个图灵机，它有n个中间状态和m个字母符号，那么存在这一个l—D的具有六邻居，max(n，所)+1状态的细胞自动机能够来模拟它I41。一般来说，细胞自动机有如下几个重要的特征：1．细胞集。这一系列细胞被放置在一个n维空间中，细胞总数并不是最重要的，空间的结构也可以是多种多样的。可以将每个细胞看作一个处理单元，这些处理单元组成了系统的群体。～般研究人员研究的

5、是一维和二维的细胞自动机。2．邻居。每个细胞至少要有一个邻居。在～个固定距离的范围内，邻居可以直接访问它。而在之外，对它没有直接的影响。3．状态集。在每一个时刻，每一个细胞有一个状态。基于细胞自动机的协同演化优化方法转换规则。转换规则定义了系统的动力学行为。规则定义了某细胞在某个时刻，在某种状态下情况下将转换到什么状态。每个细胞可以有不同的转换规则。若对于每个细胞元，转换规则都是一样的，则可以称该细胞自动机是一致的，否则，称该细胞自动机是非一致的。1．2细胞自动机研究现状细胞自动机的理论化探讨在20世纪80年代成为热点。S．Wolfram从动力系统

6、的角度对细胞自动机进行了理论上的系统描述，对细胞自动机按动力学行为进行了分类，将计算理论和形式语言方法用于研究细胞自动机，开创了细胞自动机系统理论研究的新阶段；J．H．conway等人进一步对“生命游戏”的计算通用性(Computation．universa)等作了理论分析；Tofflit等人试图在理论上探讨细胞自动机能否模拟世界上一般现象以及能否直接模拟物理规律本身，其中一个重要的研究专题集中在物理可计算模型的公式建模上，这些模型具有信息保持和微观物理的基本特性，即可逆性。Tomit还把细胞自动机作为离散计算的代表与以连续性为基础的微分方程方法作

7、了对比，并指出基于细胞自动机对热和波等物理现象的模拟更加简洁而有效。在20世纪80年代末，另外一位细胞自动机理论大师、物理学家Gutowitz发表了一系列文章，从CA的局部结构理论到CA分类等理论方面作了进一步的阐述。早期细胞自动机发展的主要功臣是J．vonNeumann，但其思想起源于StanislawUlam[10J。1948年，J．vonNeumann在研究“什么逻辑组织结构的自动机具有通用图灵机那样的自我复制特性【11】"的问题时，在StanislawUlam的建议下，J．vonNeumann采用二维细胞空间即细胞自动机结构，使用具有29个

8、状态的二维细胞自动机建立了一个具有自我复制特性和通用计算能力的细胞自动机模型。后来Codd对其进行了简化，使用具有8个状态