Non-uniform cellular automata based associative memory: Evolutionary design and basins of attraction

This paper presents the synthesis and analysis of a special class of non-uniform cellular automata (CAs) based associative memory, termed as generalized multiple attractor CAs (GMACAs). A reverse engineering technique is presented for synthesis of the GMACAs. The desired CAs are evolved through an efficient formulation of genetic algorithm coupled with the reverse engineering technique. This has resulted in significant reduction of the search space of the desired GMACAs. Characterization of the basins of attraction of the proposed model establishes the sparse network of GMACAs as a powerful pattern recognizer for memorizing unbiased patterns. Theoretical analysis also provides an estimate of the noise accommodating capability of the proposed GMACA based associative memory. An in-depth analysis of the GMACA rule space establishes the fact that more heterogeneous CA rules are capable of executing complex computation like pattern recognition.     

Error correcting capability of cellular automata based associative memory

This paper reports the error correcting capability of an associative memory model built around the sparse network of cellular automata (CA). Analytical formulation supported by experimental results has demonstrated the capability of CA based sparse network to memorize unbiased patterns while accommodating noise. The desired CA are evolved with an efficient formulation of simulated annealing (SA) program. The simple, regular, modular, and cascadable structure of CA based associative memory suits ideally for design of low cost high speed online pattern recognizing machine with the currently available VLSI technology.     

基于混沌边缘的决策行为分析

在简单地回顾了混沌边缘的历史之后,通过建立A gen t的一般决策模型,并仿照L angton关于混沌边缘的讨论,找到了一个刻画决策A gen t的行为是否处于混沌边缘的行为模式的系数.通过一个进化的人工生命实验,证明了混沌边缘的决策与个体适应性之间的关系.最后指出,混沌边缘的决策概念对于个体决策和组织管理具有重要的意义和作用.     

Two-dimensional patterns and images reconstruction with use of cellular automata

An approach based on an application of cellular automata (CA) to the problem of two-dimensional (2D) patterns or images reconstruction from ones with only partial information available is presented in the paper. 2D CA are used to process patterns/images, and genetic algorithm (GA) is applied to discover CA rules, which will be able to reconstruct original patterns/images from, e.g. destroyed or modified ones. A number of experiments have been conducted to reconstruct patterns and human face images with use of the proposed approach. Results of experiments show that CA rules discovered by GA in the learning process allow to reconstruct images with large number of damaged pixels.     

Evolving cellular automata for location management in mobile computing networks

Location management is a very important and complex problem in mobile computing. There is a need to develop algorithms that could capture this complexity yet can be easily implemented and used to solve a wide range of location management scenarios. The paper investigates the use of cellular automata (CA) combined with genetic algorithms to create an evolving parallel reporting cells planning algorithm. In the reporting cell location management scheme, some cells in the network are designated as reporting cells; mobile terminals update their positions (location update) upon entering one of these reporting cells. To create such an evolving CA system, cells in the network are mapped to cellular units of the CA and neighborhoods for the CA is selected. GA is then used to discover efficient CA transition rules. The effectiveness of the GA and of the discovered CA rules is shown for a number of test problems.     

基本和混合元胞自动机的伪随机数发生器研究

针对基本元胞自动机（Cellular Automata,简称CA）、混合CA的伪随机数发生器进行了深入的研究,通过对比实验观察到混沌型基本CA输出的伪随机序列质量稳定并较优,而混合CA输出伪随机序列的相关性,尽管优于基本CA的平均表现,但远差于混沌型基本CA的表现。针对混合CA的伪随机数发生器,提出了一种基于混合CA与粒子群优化（Particle Swarm Optimization,简称PSO）算法融合的伪随机数产生算法。在该算法中,元胞对应于PSO的粒子,每个元胞按照各自不同的规则进行迭代演化,其对应粒子在迭代规则空间中飞行。该算法通过计算每个元胞产生伪随机序列的熵值作为粒子的适应度函数值,有效地实现每个元胞最佳规则的搜索,一定程度上提高了混合CA产生伪随机序列的质量。给出了基于小生境技术、构造出最优CA-PSO耦合伪随机数发生器的研究方向。     

Neighborhood detection using mutual information for the identification of cellular automata.

Extracting the rules from spatio-temporal patterns generated by the evolution of cellular automata (CA) usually requires a priori information about the observed system, but in many applications little information will be known about the pattern. This paper introduces a new neighborhood detection algorithm which can determine the range of the neighborhood without any knowledge of the system by introducing a criterion based on mutual information (and an indication of over-estimation). A coarse-to-fine identification routine is then proposed to determine the CA rule from the observed pattern. Examples, including data from a real experiment, are employed to evaluate the new algorithm.     

有限理性条件下投票过程的元胞自动机模型研究

有限理性理论认为个体的决策能力是有限的,本文建立元胞自动机（CA）模型研究群体决策中有限理性个体的投票过程,给出了CA的演化规则,模拟了相互邻接的个体问的相互作用,观测到了投票过程的一些微观现象。元胞自动机理论将是推动自然科学和社会科学发展的一个有效工具。     

Self-repair ability of evolved self-assembling systems in cellular automata

Self-repairing systems are those that are able to reconfigure themselves following disruptions to bring them back into a defined normal state. In this paper we explore the self-repair ability of some cellular automata-like systems, which differ from classical cellular automata by the introduction of a local diffusion process inspired by chemical signalling processes in biological development. The update rules in these systems are evolved using genetic programming to self-assemble towards a target pattern. In particular, we demonstrate that once the update rules have been evolved for self-assembly, many of those update rules also provide a self-repair ability without any additional evolutionary process aimed specifically at self-repair.     

混沌在Hopfield联想记忆网络中的应用

将混沌应用到Hofield联想记忆网络中,利用混沌的遍历性和随机性等独特的性质,可以使待联想模式跳出伪模式的吸引域,而到达存储模式的吸引域内,从而解决了Hopfield网络在噪信比较高的情况下,联想成功率较低的问题。仿真结果证明了该方法的有效性。     

利用SLEUTH模型进行北京城市扩展模拟研究

元胞自动机模型具有较强的模拟空间复杂系统时空演变的能力,可以进行有效的城市增长和土地利用演化方面的模拟,现已成为城市地理学研究的重要工具。SLEUTH模型是元胞自动机模型的一种具体实现,它包含了四种城市增长方式和五个增长系数,再加上两个控制因素层一起作用于输入数据,能够较好地模拟城市的扩展。本文详细介绍了SLEUTH模型的校正和运行过程,并修改控制参数将其应用于北京城市扩展的模拟和预测中,通过分析模型的运行结果,深入地研究了北京城市发展的模式和成因,同时也指出了模型存在的问题。     

On the use of energy minimization for CA based analysis in elasticity

There has been recent interest in exploring alternative computational models for structural analysis that are better suited for a design environment requiring repetitive analysis. The need for such models is brought about by significant increases in computer processing speeds, realized primarily through parallel processing. To take full advantage of such parallel machines, however, the computational approach itself must be revisited from a totally different perspective; parallelization of inherently serial paradigms is subject to limitations introduced by a requirement of information coordination. The cellular automata (CA) model of decentralized computations provides one such approach which is ideally tailored for parallel computers. The proposed paper examines the applicability of the cellular automata model in problems of 2-D elasticity. The focus of the paper is in the use of a genetic algorithm based optimization process to derive the rules for local interaction required in evolving the cellular automata. Received August 28, 2000     

A multi-objective Markov Chain Monte Carlo cellular automata model: Simulating multi-density urban expansion in NYC

Cellular automata (CA) models have increasingly been used to simulate land use/cover changes (LUCC). Metaheuristic optimization algorithms such as particle swarm optimization (PSO) and genetic algorithm (GA) have been recently introduced into CA frameworks to generate more accurate simulations. Although Markov Chain Monte Carlo (MCMC) is simpler than PSO and GA, it is rarely used to calibrate CA models. In this article, we introduce a novel multi-chain multi-objective MCMC (mc-MO-MCMC) CA model to simulate LUCC. Unlike the classical MCMC, the proposed mc-MO-MCMC is a multiple chains method that imports crossover operation from classical evolutionary optimization algorithms. In each new chain, after the initial one, the crossover operator generates the initial solution. The selection of solutions to be crossed over are made according to their fitness score. In this paper, we chose the example of New York City (USA) to apply our model to simulate three conflicting objectives of changes from non-urban to low-, medium- or high-density urban between 2001 and 2016 using USA National Land Cover Database (NLCD). Elevation, slope, Euclidean distance to highways and local roads, population volume and average household income are used as LUCC causative factors. Furthermore, to demonstrate the efficiency of our proposed model, we compare it with the multi-objective genetic algorithm (MO-GA) and standard single-chain multi-objective MCMC (sc-MO-MCMC). Our results demonstrate that mc-MO-MCMC produces accurate simulations of land use dynamics featured by faster convergence to the Pareto frontier comparing to MO-GA and sc-MO-MCMC. The proposed multi-objective cellular automata model should efficiently help to simulate a trade-off among multiple and, possibly, conflicting land use change dynamics at once.     

Parametric optimisation in a 2-D cellular automata model of fundamental seismic attributes with the use of genetic algorithms

A two-dimensional (2-D) cellular automata (CA) dynamic system constituted of cells-charges has been proposed for the simulation of the earthquake process. In this paper, the study is focused on the optimal parameterisation of the model introducing the use of genetic algorithm (GA). The optimisation of the CA model parameterisation, by applying a standard GA, extends its ability to study various hypotheses concerning the seismicity of the region under consideration. The GA evolves an initially random population of candidate solutions of model parameters, such that in time appropriate solutions to emerge. The quality criterion is realised by taking into account the extent that the simulation results match the Gutenberg-Richter (GR) law derived from recorded data of the area under test. The simulation results presented here regard regions of Greece with different seismic and geophysical characteristics. The results found are in good quantitative and qualitative agreement with the GR scaling relations.     

认证中心控制下的版权保护框架研究

提出了一种认证中心控制下的版权保护框架,该框架应用了边缘检测与元胞自动机算法。首先应用边缘检测技术检测出图像的边缘点,然后应用元胞自动机对边缘点进行平滑处理,最后对平滑处理后的图像进行签名认证。仿真结果表明,该算法具有高鲁棒性,能够抵抗裁剪、旋转、噪声等攻击,适用于医学、军事等领域的版权保护。     

Extracting Boolean rules from CA patterns

A multiobjective genetic algorithm (GA) is introduced to identify both the neighborhood and the rule set in the form of a parsimonious Boolean expression for both one- and two-dimensional cellular automata (CA). Simulation results illustrate that the new algorithm performs well even when the patterns are corrupted by static and dynamic noise.     

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

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

二维触发元胞自动机加密算法的软件实现

一维触发元胞自动机加密系统的缺点是密钥空间小[1],二维触发元胞自动机在几乎不增加计算量及复杂度的同时,极大地扩张了密钥空间。简述二维触发元胞自动机的基本理论,应用其触发规则建立动态密码系统,完成加密解密,并根据程序的最终测试数据,进行性能分析。     

Incorporation of extended neighborhood mechanisms and its impact on urban land-use cellular automata simulations

Urban cellular automata (CA) models are broadly used in quantitative analyses and predictions of urban land-use dynamics. However, most urban CA developed with neighborhood rules consider only a small neighborhood scope under a specific spatial resolution. Here, we quantify neighborhood effects in a relatively large cellular space and analyze their role in the performance of an urban land use model. The extracted neighborhood rules were integrated into a commonly used logistic regression urban CA model (Logistic-CA), resulting in a large neighborhood urban land use model (Logistic-LNCA). Land-use simulations with both models were evaluated with urban expansion data in Xiamen City, China. Simulations with the Logistic-LNCA model raised the accuracies of built-up land by 3.0%–3.9% in two simulation periods compared with the Logistic-CA model with a 3 × 3 kernel. Parameter sensitivity analysis indicated that there was an optimal large window size in cellular space and a corresponding optimal parameter configuration.