In this paper a method is proposed which uses data mining techniques based on rough sets theory to select neighborhood and determine update rule for cellular automata (CA). According to the proposed approach, neighborhood is detected by reducts calculations and a rule-learning algorithm is applied to induce a set of decision rules that define the evolution of CA. Experiments were performed with use of synthetic as well as real-world data sets. The results show that the introduced method allows identification of both deterministic and probabilistic CA-based models of real-world phenomena.
@cite_9: This paper studies a method for identifying cellular automata rules (CA rules). Given a sequence of CA configurations, we first seek an appropriate neighborhood of a cell and collect cellular changes of states as evidences. The collected evidences are then classified using a decision tree, which is used for constructing CA transition rules. Conditions for classifying evidences in a decision tree are computed using genetic programming. We perform experiments using several types of CAs and verify that the proposed method successfully identifies correct CA rules.
@cite_3: 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.
@cite_6: Cellular automata are discrete dynamical systems which evolve on a discrete grid. Recent studies have shown that cellular automata with relatively simple rules can produce highly complex patterns. We develop likelihood-based methods for estimating rules of cellular automata aimed at the re-generation of observed regular patterns. Under noisy data, our approach is equivalent to estimating the local map of a stochastic cellular automaton. Direct computations of the maximum likelihood estimates are possible for regular binary patterns. The likelihood formulation of the problem is congenial with the use of the minimum description length principle as a model selection tool. We illustrate our method with a series of examples using binary images.
@cite_15: Abstract We outline a method for extracting two-dimensional cellular automaton (CA) rules directly from experimental data. The data consist of discrete-space patterns evolving in discrete time. We employ a learning algorithm, the genetic algorithm, to search efficiently through a space of probabilistic CA rules for a local rule that best reproduces the observed behavior of the data. Included are the results of an analysis of patterns generated by the dendritic solidification of NH 4 Br from a supersaturated acqueous solution.
@cite_13: The identification of probabilistic cellular automata (PCA) is studied using a new two stage neighborhood detection algorithm. It is shown that a binary probabilistic cellular automaton (BPCA) can be described by an integer-parameterized polynomial corrupted by noise. Searching for the correct neighborhood of a BPCA is then equivalent to selecting the correct terms which constitute the polynomial model of the BPCA, from a large initial term set. It is proved that the contribution values for the correct terms can be calculated independently of the contribution values for the noise terms. This allows the neighborhood detection technique developed for deterministic rules in to be applied with a larger cutoff value to discard the majority of spurious terms and to produce an initial presearch for the BPCA neighborhood. A multiobjective genetic algorithm (GA) search with integer constraints is then evolved to refine the reduced neighborhood and to identify the polynomial rule which is equivalent to the probabilistic rule with the largest probability. A probability table representing the BPCA can then be determined based on the identified neighborhood and the deterministic rule. The new algorithm is tested over a large set of one-dimensional (1D), two-dimensional (2D), and three-dimensional (3D) BPCA rules. Simulation results demonstrate the efficiency of the new method.
@cite_17: Form generation or morphogenesis is one of the main stages of both artificial and natural development. This paper provides results from experiments in which a genetic algorithm (GA) was used to evolve cellular automata (CA) to produce predefined 2D and 3D shapes. The GA worked by evolving the CA rule table and the number of iterations that the model was to run. After the final chromosomes were obtained for all shapes, the CA model was allowed to run starting with a single cell in the middle of the lattice until the allowed number of iterations was reached and a shape was formed. In all cases, mean fitness values of evolved chromosomes were above 80.
Most of the works related to the CA identification problem use genetic algorithms as a tool to extract update rule and neighborhood from spatio-temporal patterns produced in CA evolution @cite_13 @cite_9 @cite_3 . In @cite_15 a genetic algorithm was employed to learn probabilistic rules directly from experimental data for two-dimensional binary-state CA. Several methods were proposed that use genetic algorithms to learn CA rules and neighborhood size for image processing tasks @cite_17 @cite_6 .