地下矿CA粒子系统火灾蔓延仿真

为了对火灾在地下矿巷道中的蔓延情况进行仿真,提出了一个元胞自动机理论和粒子系统理论相结合的地下矿巷道系统中火灾蔓延仿真方法。针对地下矿巷道这个特殊环境,采取可变邻域半径的元胞自动机模型来仿真火焰在巷道中蔓延的情景;同时,引入基于粒子系统的烟雾模型,把燃烧着的元胞作为烟雾模型的粒子发射器。整个仿真系统基于同一时钟运行,把时间、空间、火烟的物理行为有效地结合起来,不仅能非常直观地仿真出火势蔓延态势和烟雾扩散运动过程,并且通过在仿真过程中计算记录不同时刻火灾蔓延距离和入侵巷道烟雾粒子数量等数据,可以获取大量巷道环境相关信息,为逃生决策和火灾预防与控制提供依据。     

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

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

基于元胞自动机的洪泽湖洪水蔓延模型研究

分析了元胞自动机的基本原理和构成,利用元胞自动机原理建立了洪泽湖洪水蔓延模型。模型以栅格空间数据结构作为基础,采用二维元胞自动机模型,确定了元胞空间和元胞状态,建立了洪泽湖洪水蔓延的规则,并根据规则以9邻域方式进行元胞状态的更新。选择性地测试了洪水蔓延模型的计算结果,模型计算数据与实际数据的比较表明,二维元胞自动机模型能够更为简单、快速地模拟洪泽湖洪水的蔓延。     

元胞自动机理论及其在图像边缘检测中的应用

元胞自动机(Cellular Automata,简称CA,大量元胞通过简单的相互作用而构成动态系统的演化)元胞自动机是一类模型的总称,或者说是一个方法框架。其特点是时间、空间、状态都离散,每个变量只取有限多个状态,且其状态改变的规则在时间和空间上都是局部的。本文基于元胞自动机理论,初步探讨了其在图像边缘检测中的应用。     

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

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

超图划分问题的元胞自动机模型及算法研究

对超图划分问题运用元胞自动机理论进行分析建模,提出一种元胞自动机模型以及基于该模型的赋权超图划分优化算法。在该模型中,元胞对应于赋权超图中的结点,邻接元胞对应于邻接超边所包含的结点,元胞的状态对应于所在的划分子集。引入二维辅助数组存储每条超边在划分子集中的结点个数,给出快速的元胞收益值和划分割切值的计算方法,从而避免遍历超边中的结点。实验结果表明,与赋权图划分算法和迁移方法相比,该算法可以取得更优的划分,且时间复杂度和空间复杂度较低。     

基于二维元胞自动机的双向触发并行加密模型

根据二维触发元胞自动机的特性,提出了一种二维元胞自动机双触发并行加//解密模型。仿真实验表明:与一维耦合触发元胞自动机相比,二维元胞自动机双触发并行加密模型在适度减慢加/解密速度的情况下,大大提高了密钥空间,具有极高的时间换空间的效率,很好地提高了健壮性和实用性。     

基于元胞自动机算法的三维玻璃微流控芯片湿法刻蚀模拟研究

以二维动态元胞自动机理论为基础,提出一种针对玻璃各向同性刻蚀特性的三维动态元胞自动机(Cellular automata)算法.利用创建刻蚀链表的方式代替传统的元胞搜索,提高了算法效率,并通过改进元胞信息的存储方式,使得三维元胞阵列得以存储于二维矩阵中.最后利用OpenGL技术对刻蚀结果进行三维成像.该算法在个人计算机上实现了较高分辨率(4000×4000像素)的三维刻蚀模拟与显示.通过对比玻璃刻蚀的实验结果和前人的研究评估模型,模拟结果完全能够实现对刻蚀结果的预测.文中的研究表明:建立的三维元胞自动机算法可以有效地应用于玻璃刻蚀过程的模拟.     

基于改进的元胞自动机的网络舆情传播模型

本文针对网络舆情传播,结合元胞自动机理论,提出了一种三维元胞自动机模型。该模型能够更加准确地模拟网络舆情的传播动态,有效地解决舆情传播过程中遇到的问题。实验结果表明新的模型和算法简便、高效,基于三维元胞自动机建立的传播模型清晰的表达了网络舆情传播的过程。     

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

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

分类回归树多吸引子细胞自动机分类方法及过拟合研究

基于多吸引子细胞自动机的分类方法多是二分类算法,难以克服过度拟合问题,在生成多吸引子细胞自动机时如何有效地处理多分类及过度拟合问题还缺乏可行的方法.从细胞空间角度对模式空间进行分割是一种均匀分割,难以适应空间非均匀分割的需要.将CART算法同多吸引子细胞自动机相结合构造树型结构的分类器,以解决空间的非均匀分割及过度拟合问题,并基于粒子群优化方法提出树节点的最优多吸引子细胞自动机特征矩阵的构造方法.基于该方法构造的多吸引子细胞自动机分类器能够以较少的伪穷举域比特数获得好的分类性能,减少了分类器中的空盆数量,在保证分类正确率的同时改善了过拟合问题,缩短了分类时间.实验分析证明了所提出方法的可行性和有效性.     

<Emphasis Type="Italic">SetExp</Emphasis>: a method of transformation of timed automata into finite state automata

Real-time discrete event systems are discrete event systems with timing constraints, and can be modeled by timed automata. The latter are convenient for modeling real-time discrete event systems. However, due to their infinite state space, timed automata are not suitable for studying real-time discrete event systems. On the other hand, finite state automata, as the name suggests, are convenient for modeling and studying non-real time discrete event systems. To take into account the advantages of finite state automata, an approach for studying real-time discrete event systems is to transform, by abstraction, the timed automata modeling them into finite state automata which describe the same behaviors. Then, studies are performed on the finite state automata model by adapting methods designed for non real-time discrete event systems. In this paper, we present a method for transforming timed automata into special finite state automata called Set-Exp automata. The method, called SetExp, models the passing of time as real events in two types: Set events which correspond to resets with programming of clocks, and Exp events which correspond to the expiration of clocks. These events allow to express the timing constraints as events order constraints. SetExp limits the state space explosion problem in comparison to other transformation methods of timed automata, notably when the magnitude of the constants used to express the timing constraints are high. Moreover, SetExp is suitable, for example, in supervisory control and conformance testing of real-time discrete event systems.     

细胞自动机反向迭代加密技术研究

细胞自动机固有的组成单元的简单性、单元之间作用的局部性和信息处理的高度并行性 ,并表现出复杂的全局特性等特点使得细胞自动机尤其适合于密码学中的应用 .该文简述了细胞自动机的基本概念 ,研究了基于细胞自动机反向迭代的输出序列熵最大化加密技术 ,并对系统保密性进行了分析 .     

MapInfo中元胞自动机集成开发方案及其应用

元胞自动机与地理信息系统(GIS)的集成弥补了GIS在时空分析和时空演化方面的不足,为地理学的研究提供了新的手段。论文用实例论述了MapInfo中元胞自动机的集成开发方案。讲述了元胞自动机的原理及与GIS集成的优点和具体技术,并就二值型(城市扩张演化型)元胞自动机的应用做了示范。     

A cellular automaton model of particle motions and its applications

A natural object such as a flame with smoke is featured in terms of ambiguous boundaries and complex motion. One way of modeling natural objects is by particle systems, which need a large amount of computation time to calculate interactions among the particles. This paper deseribes another way of modeling particle motions based on a cellular automaton. Cellular automata are massively parallel computation models that can simulate complex phenomena. In our model, particle motions are simulated in a cellular space with a Margolus neighborhood, which has good conservation properties and collision detectability. This paper shows several applications in two-dimensional cellular space.     

基于多耦合元胞自动机的加密算法

提出了耦合系数的概念,构造了一个新的耦合元胞自动机模型,并分析了耦合系数对耦合元胞自动机时空演化的影响。针对已有的单耦合元胞自动机加密系统中存在的不足,提出了基于多耦合元胞自动机的加密算法,该算法将多个元胞进行耦合,增强了两个元胞自动机之间的作用,扩大了相互影响的范围,使得误差扩散更为快速。仿真结果表明,该算法具有更为理想的扩散和扰乱特性,可抵抗蛮力攻击和差分分析攻击。     

Discrete relations on abstract simplicial complexes

On the one hand, a system of discrete relations is a generalization of cellular automaton and, on the other hand, it is a set-theoretical analog of a system of polynomial equations. An approach to studying such systems that is based on set-theoretical and topological constructs is considered. The proposed approach is implemented as a C program. Results of application of this approach to some binary cellular automata are given. In the binary case, cellular automata can be represented by systems of polynomial equations, which are normally studied by the Gröbner basis method. Our approach is compared with this method on some examples.     

Modeling and animation of fracture of heterogeneous materials based on CUDA

Existing techniques for animation of object fracture are based on an assumption that the object materials are homogeneous while most real world materials are heterogeneous. In this paper, we propose to use movable cellular automata (MCA) to simulate fracture phenomena on heterogeneous objects. The method is based on the discrete representation and inherits the advantages from both classical cellular automaton and discrete element methods. In our approach, the object is represented as discrete spherical particles, named movable cellular automata. MCA is used to simulate the material and physical properties so as to determine when and where the fracture occurs. To achieve real-time performance, we accelerate the complex computation of automata’s physical properties in MCA simulation using CUDA on a GPU. The simulation results are directly sent to vertex buffer object (VBO) for rendering to avoid the costly communication between CPU and GPU. The experimental results show the effectiveness of our method.     

细胞自动机语言Cellang的扩展与应用

并行执行与并行描述是并行计算的两个方面,后者是并行软件技术的一个日益重要的问题,目前主流的并行语言都是针对特定的需求设计的。细胞自动机对许多问题具有自然而贴切的描述并行性,作为动力学系统仿真工具与并行离散计算模型近来受到广泛关注。通过对某些细胞自动机语言进行扩展,可以使其成为并行数值计算的良好工具,方便地描述与求解一大类并行数值计算问题。本文介绍我们对细胞自动机语言Cellang的扩展及在并行数值计算上的应用。