CA与生命游戏演化的组合模型*

基于摩尔奇偶型CA,提出一种结合生命游戏的演化模型.首先设置初始构型进行摩尔奇偶型规则演化,再引入生命游戏规则,按游戏规则演化;最后依此重复摩尔奇偶规则和生命游戏规则,直到演化整个元胞空间.证实在摩尔奇偶型CA的基础上,结合生命游戏在很大程度上减小了演化过程对初始构型的依赖,出现更为丰富的图元以及基于图元和演化框架的动态图案,且演化过程仍然符合摩尔奇偶型CA的演化规律.结合模型可以避免演化过度依赖初始构型以及演化过程的单调性,而且组合演化模型可以应用于图案生成,生成保持风格的规则几何纹理图案,丰富图案的生成方法.     

基于二维元胞自动机的图案设计方法研究

研究者们常常根据元胞自动机的演化机制,模拟人类的社会现象、自然界中的物质变化等。元胞自动机在绘制图案的应用研究中,通常是用于对自然界、人体器官等实体仿真。而文中则是根据元胞自动机演化的多样性和随机性,提出了一种基于二维元胞自动机的图案设计方法。该方法可以根据算法的描述,结合参数的可控、规则的研究和元胞的不同大小,并最终在VC＋＋6．0上编程实现。实验结果显示,可以绘制出更加美妙、精确的图案,这些图案可以用来装饰壁毯、地毯、窗帘等。     

初等元胞自动机的界面设计及稳定性分析

建立了所有规则下的初等元胞自动机的可视化模型及界面,设计了用于判断初等元胞自动机稳定性的应用程序,并可直接计算得到演化类型及周期.在此基础上,模拟得到了不同元胞数m,随机产生的不同的初始状态,不同规则数R以及各种边界条件下初等元胞自动机的演化结果,并分析了以上因素对稳定性的影响.结果表明:元胞数m,初始状态,规则数R以及边界条件,均对初等元胞自动机的演化类型,演化周期产生较大影响.充分反映了元胞自动机的复杂性.模型从模拟的角度出发,为元胞自动机的复杂性研究提供了一个简单的、可视的计算机仿真工具,并可为复杂的理论推导提供参考或验证.     

元胞自动机的演化行为研究*

基于元胞自动机演化行为研究与仿真系统,通过对元胞自动机的一、二、三维演化行为的研究,从统计和渐进的角度对元胞自动机进行了分类,将元胞自动机的演化行为动态统计图与沃尔弗拉姆对于元胞自动机的分类对应起来研究.这些从不同视角得到的结果有助于对元胞自动机的演化行为进行深入研究;但从统计和渐进的角度对元胞自动机进行分类是否具有普适性,是需要进一步研究探讨的问题.     

一种基于元胞自动机的无线传感器网络拓扑控制方法

设计良好的网络拓扑控制方法能够减少能量消耗,实现网络能量的高效利用.利用二维元胞自动机,考虑节点的随机分布和工作/休眠/失效三态,建立无线传感器网络系统拓扑的演化规则.在设定初始条件下研究得到了演化规则的最佳控制参数,利用该参数的仿真表明,优化的元胞自动机网络拓扑控制在保证覆盖率和连通度的前提下延长了网络寿命.     

基于元胞自动机的交通流计算机模拟

元胞自动机是把复杂系统量化为简单的个体,在元胞自动机模型中.空间、时间都被离散化,每一个相互作用的单元仅为有限的状态.以元胞自动机理论为基础,把车辆在路段上交通流中运动的变化规律表述为元胞自动机的演化规则,建立了基于元胞自动机理论的交通流模拟模型,标定了元胞长度和最大速度等参数,分析了元胞变换的原则;详细探讨了元胞自动机在道路交通模拟中的应用,设计出了交通元胞自动机的结构,分析了交通元胞自动机所采取的状态变换原则,建立了一维(单车道)交通流模拟模型;并利用C语言编程实现模拟.模拟结果符合实际交通流的特点.     

一种基于仿生元胞自动机的图像加密算法

针对一维元胞自动机加密密钥空间小、扩散速度慢、安全性不高,以及有些二维元胞自动机需额外增加规则存储空间,加密后效果不理想等问题,提出一种基于仿生元胞自动机的图像加密算法。该算法首先将明文图像像素值转换为二进制矩阵,再将二进制矩阵分成大小相同的2部分作为仿生元胞自动机的2个初始状态,然后选取一个仿生元胞自动机规则作为密钥,利用仿生元胞自动机的演化进行加密。实验结果表明,本文提出的图像加密方案具有较大的密钥空间,对明文和密钥敏感,可以更好地保障加密图像的安全。     

元胞遗传算法演化规则的研究*

在Conway提出的“生命游戏”规则的基础上,为提高生命繁殖和生存的概率,通过改变周围邻居元胞的状态提出一种改进的演化规则。实验证明,结合元胞自动机的遗传算法,加入改进的演化规则后,用于求解复杂多峰函数优化问题获得了较好的效果。     

软件体系结构动态演化的元胞自动机模型研究

目前软件体系结构动态演化的元胞自动机模型存在描述单一、元胞间关系不明确、没有详细阐述动态演化过程应用约束条件的缺点。针对这些不足进行相关的研究,重新定义了软件体系结构动态演化的扩展元胞自动机模型,基于扩展元胞自动机模型结合演化应用约束条件,分析了软件体系结构的动态演化过程,运用元胞间控制约束条件和行为相关约束条件来正确地指导SA动态演化。提出了动点稳态转移的概念,对演化程度和一致性进行定义分析,此方法比以往的元胞自动机模型更能准确指导SA动态演化,促进SA动态演化的进一步研究。通过案例验证了该方法的应用价值和可行性,可以更全面地应用于软件体系结构的动态演化。     

基于空间数据挖掘的分区异步元胞自动机模型研究

传统的元胞自动机模型采用统一的转换规则和相同的演化速率进行演化,忽略了地理现象演变的时空差异性：演化规律的空间异质性和演化速率的空间差异性。针对这一问题,提出了基于空间数据挖掘的分区异步元胞自动机模型,采用双约束空间聚类的方法对元胞空间进行分区,用分区转换规则替代统一转换规则可以体现地理现象演化规律的空间差异性;采用标准格网划分的方法求取异步元胞演化速率,用异步演化速率替代同步演化速率可以体现地理现象演化速率的空间差异性。以杭州市土地利用变化为例对基于空间数据挖掘的分区异步元胞自动机模型进行了实证研究,结果表明：与传统的元胞自动机模型相比,基于空间数据挖掘的分区异步元胞自动机模型具有较高的模拟精度,并且适用于较大区域较长时间段地理现象的动态变化模拟。基于空间数据挖掘的分区异步元胞自动机模型是地理元胞自动机研究的新视角,它将地理现象演变的空间异质性和时间差异性引入到地理元胞自动机模型中,使模型对地理过程的模拟更接近实际地理过程。然而,由于有关分区异步的元胞自动机模型还处于尝试性研究阶段,在元胞空间分区方法、双约束空间聚类算法中权重的确定方法、元胞演化速率的获取方法、元胞转换规则的获取方法、模拟精度评估以及分区异步元胞自动机模型在较大区域较长时间的地理现象模拟中的应用等方面有待进一步的研究与探讨。     

基于元胞自动机的小样本集分类算法

样本集中的数据数量过少会影响最后的分类精度。为此,提出基于元胞自动机模型的小样本集分类算法,利用元胞自动机的状态转换规则和分类规则,通过元胞空间的演化实现对数据集的分类。对标准数据集的测试结果表明,在小样本集和样本集中数据分布不均匀的情况下,该算法具有较高的分类精度。     

基于元胞自动机扩展模型的图的最短路径算法

利用元胞自动机在元胞空间上的并行特性，采用元胞动态邻居，时间段自适应调整的方法，构造出一种新的基于元胞自动机扩展模型的最短路径搜索算法，即通过简单规则的元胞状态演化，得到带权图的最短路径；该方法经过优化，能够达到Dijkstra算法的时间效率；并且为基于元胞自动机扩展模型解决图的问题的提供了新的思路。     

基于元胞自动机模型的新型二值图像压缩算法

不同于传统的去相关,去冗余的压缩方法,提出一种基于元胞自动机模型的二值图像压缩算法。该算法用遗传规划算法搜索出较优的元胞自动机规则后,对分块后的二值图像矢量进行元胞自动机变换,利用元胞自动机的变换状态多样性等特点,生成相邻矢量,将变换次数作为码本。实验表明：该算法经过4次以内的元胞自动机变换即可生成较优的相邻矢量,具有编码时间短、重建图像的质量好、压缩率高、适应性强等特点,并且与其它压缩算法结合性好。     

智能优化算法在聚类分析中的应用

聚类分析是数据挖掘的重要技术,可根据数据间的相似程度,将数据进行分类,现已广泛应用于工程和技术等领域中。元胞蚁群算法是在将元胞自动机的邻居和规则引入传统蚁群算法的基础上,利用元胞在离散元胞空间的演化规律和蚁群寻优特点的新型优化算法。针对聚类分析的特点,利用元胞蚁群算法进行求解,经实验测试和验证,获得了较好的结果。     

Structure and reversibility of 2D hexagonal cellular automata

Cellular automata are used to model dynamical phenomena by focusing on their local behavior which depends on the neighboring cells in order to express their global behavior. The geometrical structure of the models suggests the algebraic structure of cellular automata. After modeling the dynamical phenomena, it is sometimes an important problem to be able to move backwards in order to understand it better. This is only possible if cellular automata is reversible. In this paper, 2D finite cellular automata defined by local rules based on hexagonal cell structure are studied. Rule matrix of the hexagonal finite cellular automaton is obtained. The rank of rule matrices representing the 2D hexagonal finite cellular automata via an algorithm is computed. It is a well known fact that determining the reversibility of a 2D cellular automata is a very difficult problem in general. Here, the reversibility problem of this family of 2D hexagonal cellular automata is also resolved completely.     

一种基于元胞自动机的无向图剖分优化算法

运用元胞自动机理论,针对无向图剖分优化问题进行了分析和建模,提出了一种元胞自动机模型以及基于该模型的无向图剖分优化算法。在该元胞自动机模型中,元胞对应于无向图中的结点,元胞的邻居对应于邻接结点,元胞空间对应于无向图中的结点集,元胞的状态对应于所在的结点子集。实验及分析表明该算法不仅能找到无向图的近似最优剖分,而且有效地降低了空间复杂度和时间复杂度。     

Analysis of complemented CA derived from linear hybrid group CA

In this paper, we analyze complemented group Cellular Automata (CA) derived from Linear Hybrid Group CA with rules 60, 102 and 204. We analyze some properties of the CA. And we give rule vectors which determine the state transition of the CA dividing the entire state space into smaller spaces of equal lengths, and find conditions for the complement vectors corresponding to the rule vectors. And we extend and generalize Mukhopadhyay’s results [D. Mukhopadhyay, D.R. Chowdhury, Characterization of a class of complemented group cellular automata, in: Proc. ACRI 2004, in: LNCS, vol. 3305, 2004, pp. 775–784].