Effects of cell size and configuration in cellular automata based prey–predator modelling

Cellular automata (CA) have shown to be a viable approach in ecological modelling, in particular when dealing with local interactions between species and their environment. In CA modelling complex patterns emerge on a global scale through the evolution of interactions at a local level. Although the validity of a cell-based approach has successfully been demonstrated in numerous cases, very few studies have been reported that address the effects of cell size and configuration on the behaviours of CA-based models. In this paper, the performance of a cellular automaton based prey–predator model (EcoCA) developed by the author was first calibrated against the classical Lotka–Volterra (LV) model. The model was then used to investigate effects of cell size and cellular configurations (viz. the ‘computational stencil’). By setting up systematic simulation scenarios it was observed that the choice of a particular cell size has a clear effect on the resulting spatial patterns, while different cellular configurations affect both spatial patterns and system stability. On the basis of these findings, it is proposed to use the principal spatial scale of the studied ecosystem as CA model cell size and to apply the Moore type cell configuration. Methods for identifying principal spatial scales have been developed and are presented here.     

基于元胞自动机和模糊理论的人群疏散仿真

基于元胞自动机和模糊理论建立了人群疏散模型,对教学楼内的人群疏散过程进行了模拟。该模型根据人员对建筑物的熟悉程度、周围人员的吸引力设计元胞行为准则,并且采用模糊隶属度定义人员的体能状态及人员对环境的熟悉程度。实验结果表明,该仿真模型能够较好地模拟紧急状况下的人群疏散过程。     

The ergodic theory of cellular automata

Ergodic theory is the study of how a dynamical system transforms the information encoded in an invariant probability measure. This article reviews the major recent results in the ergodic theory of cellular automata.     

Decidability and undecidability in cellular automata

We survey results on decidability questions concerning cellular automata. Properties discussed include reversibility and surjectivity and their variants, time-symmetry and conservation laws, nilpotency and other properties of the limit set and the trace, properties chaoticity related such as sensitivity to initial conditions and mixing of the space, and dynamics from finite initial configurations. We also discuss briefly the tiling problem and its variants, and consider the influence of the dimension of the space on the decidability status of the questions.     

An analysis of the effect of the stochastic component of urban cellular automata models

Urban cellular automata models have proved useful tools in urban growth prediction because of their simplicity and their ability to reproduce complex emergent dynamics. Complex emergent dynamic systems involve processes that are difficult to predict, in which randomness plays a key role. In view of the fact that randomness is particularly relevant to complex processes, the aim of this paper is to analyze the sensitivity of the results of urban cellular automata models to the different methods used to incorporate the stochastic component in the models. The urban growth patterns obtained using different stochastic components are analyzed and compared using a number of spatial metrics. The results show that the differences observed in the simulated patterns are sufficiently relevant to justify the need for this type of analysis, which allows for the selection of the stochastic component that best suits the dynamics of the area.     

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.     

基于元胞自动机的传染病传播模型研究

从复杂适应系统的观点,通过建立元胞自动机模型的方法模拟疾病传播这个复杂的过程.并对SARS地传播过程成功地进行了模拟。同时以此为基础针对可能对传染病产生影响的几种因素作了具体地考察,如人员的移动、及时就医等,考察这些因素对控制传染病达到稳定的具体影响,并给出一些控制这类问题的建议。     

Computational classification of cellular automata

We discuss attempts at the classification of cellular automata, in particular with a view towards decidability. We will see that a large variety of properties relating to the short-term evolution of configurations are decidable in principle, but questions relating to the long-term evolution are typically undecidable. Even in the decidable case, computational hardness poses a major obstacle for the automatic analysis of cellular automata.     

基于GPU的元胞自动机熔岩流动模拟

为解决基于元胞自动机进行熔岩流动模拟的计算效率问题,提出一种应用在元胞自动机上的GPU并行计算方法。将元胞自动机中每一个方形网格映射到GPU的一个逻辑计算单元上,通过并行计算,提高模拟的效率,解决传统串行计算方法的不足,使模拟达到实时性。模拟结果表明,在元胞自动机的物理模型理论基础上,用GPU并行计算进行加速,在模拟效果和时间效率上均取得了良好的效果。     

元胞自动机方法在MEMS工艺模拟中的应用

随着计算机技术的发展和MEMS(micro-electro-mechanical system)自身发展的需要,应用元胞自动机方法模拟MEMS加工工艺的研究发展迅速.首先,简要介绍了元胞自动机原理,然后,综述了元胞自动机方法在MEMS工艺模拟中的应用现状,分析了应用元胞自动机方法模拟MEMS加工工艺的前景和方向.     

Review on cellular automata simulations of microstructure evolution during metal forming process: Grain coarsening, recrystallization and phase transformation

Cellular automata (CA) algorithm has become an effective tool to simulate microstructure evolution. This paper presents a review on CA modeling of microstructural evolution, such as grain coarsening, recrystallization and phase transformation during metal forming process which significantly affects mechanical properties of final products. CA modeling of grain boundary motion is illustrated and several aspects of recrystallization are described, e.g. nucleation and growth, the development of static and dynam...     

基于FDS和元胞自动机动态耦合的火灾疏散模型

为研究火灾场景下温度、烟气和CO浓度等灾害因子对疏散的影响,建立基于FDS和元胞自动机动态耦合的火灾疏散模型。将FDS的网格和元胞自动机的元胞一一对应,将由FDS运行得到的灾害数据通过Python等技术手段实时加载到元胞中,使灾害数据持续影响行人转移概率,从而实现灾害和疏散的动态耦合;以单层教学楼作为仿真场景进行模拟分析,对火源位置和热释放速率等因素进行讨论,得出这些因素对行人疏散进程的影响规律;将模型与传统软件和同类方案进行对比。研究表明,火灾导致的高温和烟气会影响行人对疏散路径和安全出口的选择;热释放速率越大,行人越早处于危险状态,同时处于危险状态的行人也越多;该模型相比传统疏散软件不仅能考虑火灾产生的致灾因子对行人疏散的动态影响,还能确定行人最早处于危险状态的位置和时间,并用可视化的方式表现出来。     

基于元胞自动机的模糊控制换道模型

根据元胞自动机理论建立改进的交通流模型,给出每辆车的演化规则。在此基础上依据实际车辆行为建立换道规则,利用模糊推理来模拟人在换道过程中的主观判断过程,建立换道模型。仿真表明该方法能较好的模拟车辆的实际行为。     

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

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

Simulation of one-way cellular automata by boolean circuits

We present a relationship between two major models of parallel computation: the one-way cellular automata and the boolean circuits. The starting point is the boolean circuit of small depth designed by Ladner and Fischer to simulate any rational transducer. We extend this construction to simulate one-way cellular automata by boolean circuits.     

Non-deterministic cellular automata and languages

We summarize results on non-deterministic cellular language acceptors. The non-determinism is regarded as limited resource. For parallel devices, it is natural to bound the non-determinism in time and/or space. Depending on the length of the input, the number of allowed non-deterministic state transitions as well as the number of non-deterministic cells at all is limited. We centre our attention to real-time, linear-time, and unrestricted-time computations and discuss the computational power of these machines. Speed-up results and the possibility to reduce the non-determinism as well as closure properties of languages acceptable with a constant number of non-deterministic transitions are presented. By considering the relations with context-free languages, several relations between the devices in question are implied. We do not prove these results but we merely draw attention to the big picture and some of the main ideas involved, and open problems for further research.     

因特网舆情传播的协同元胞自动机模型

现有的因特网舆情传播研究或者从话题文本增长—消亡过程的数学统计或智能学习出发,或者采用元胞自动机或隐马尔可夫模型(HMM)分析主题倾向度的演化过程。但这些研究均缺乏有关舆情主体属性对因特网舆情传播影响的分析。基于因特网舆情空间的系统协同性,首先计算元胞状态协同转移概率,同时将整体协同转移概率与中心元胞之九邻居局域状态概率比较,确定中心元胞状态是否转换。经过若干次时间序列的迭代计算,获得舆情整体传播趋向“+”或“-”的程度(磁化率)。通过观察磁化率—时间变化曲线,能清楚地了解舆情传播的演化。在此基础上,提出一个扩展的协同元胞自动机模型及算法。仿真结果表明环境适应度参变量表达了网络舆情主体从众心理,其变化影响磁化率向多数人意见靠拢;而偏好参变量使网络舆情整体快速向“偏好”方向传播。该模型比较接近现实社会网络的舆情传播方式。     

Sand automata as cellular automata

In this paper, we exhibit a strong relation between the sand automata configuration space and the cellular automata configuration space. This relation induces a compact topology for sand automata, and a new context in which sand automata are homeomorphic to cellular automata acting on a specific subshift. We show that the existing topological results for sand automata, including the Hedlund-like representation theorem, still hold. In this context, we give a characterization of cellular automata which are sand automata, and study some dynamical behaviors such as equicontinuity. Furthermore, we deal with simple sand automata. We show that the classical definition of nilpotency is not meaningful for sand automata. Then, we introduce the suitable new notion of flattening sand automata. Finally, we prove that this simple dynamical behavior is undecidable.     

复杂网络病毒传播元胞自动机模型及研究

为了研究免疫有效时间对复杂网络中病毒传播的影响,基于元胞自动机建立复杂网络不完全免疫的病毒传播模型,并分别在最近邻耦合网络、Erdos-Renyi随机网络、Watts-Strogatz小世界网络和Barabasi-Albert无标度网络中进行仿真研究。结果表明：节点免疫有效时间的增大,能够有效地遏制复杂网络病毒传播范围并增大病毒传播阈值。