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_14: What are Cellular Automata Classification of Cellular Automata Cellular Automata Simulating Nature What is Identification Deterministic Cellular Automata Probabilistic Cellular Automata Fuzzy Cellular Automata Hierarchical Cellular Automata Exotic Cellular Automata Implantation of Cellular Automata Cyptography Three Examples of Natural Systems Design of Molecular Computers Conclusion.
@cite_4: Although cellular automata have been widely studied as a class of the spatio temporal systems, very few investigators have studied how to identify the CA rules given observations of the patterns. A solution using a polynomial realization to describe the CA rule is reviewed in the present study based on the application of an orthogonal least squares algorithm. Three new neighbourhood detection methods are then reviewed as important preliminary analysis procedures to reduce the complexity of the estimation. The identification of excitable media is discussed using simulation examples and real data sets and a new method for the identification of hybrid CA is introduced.
@cite_0: Experiments were carried out to investigate the possibility of training cellular automata (CA) to perform several image processing tasks. Even if only binary images are considered, the space of all possible rule sets is still very large, and so the training process is the main bottleneck of such an approach. In this paper, the sequential floating forward search method for feature selection was used to select good rule sets for a range of tasks, namely noise filtering (also applied to grayscale images using threshold decomposition), thinning, and convex hulls. Various objective functions for driving the search were considered. Several modifications to the standard CA formulation were made (the B-rule and two-cycle CAs), which were found, in some cases, to improve performance.
@cite_5: Cellular automata (CA) with given evolution rules have been widely investigated, but the inverse problem of extracting CA rules from observed data is less studied. Current CA rule extraction approaches are both time consuming and inefficient when selecting neighborhoods. We give a novel approach to identifying CA rules from observed data and selecting CA neighborhoods based on the identified CA model. Our identification algorithm uses a model linear in its parameters and gives a unified framework for representing the identification problem for both deterministic and probabilistic CA. Parameters are estimated based on a minimum variance criterion. An incremental procedure is applied during CA identification to select an initial coarse neighborhood. Redundant cells in the neighborhood are then removed based on parameter estimates, and the neighborhood size is determined using the Bayesian information criterion. Experimental results show the effectiveness of our algorithm and that it outperforms other leading CA identification algorithms.
@cite_12: This paper describes an automatic calibration method for the class of cellular automata (CA) characterized by additive transition rules. CA can serve as instruments to support decision-making in spatial systems, since they are in effect dynamic maps representing geographic processes. However, the quality of CA based decision support models depends on the adequacy of the transition rules, which must be complex in realistic models, and these rules typically contain a number of parameters that must be calibrated. At present there is no general method to calibrate the transition rule set other than a manual tuning of the rules. Existing automatic techniques are applicable only to very simple CA. The method presented here draws on several standard optimization and search techniques, adapting them to the CA calibration problem. The procedure is developed first for application to the general class of unconstrained additive transition rules, and is then modified in order to deal with the case of constrained additive rules, where the number of cells in each state at each iteration is determined exogenously to the CA; this latter class is important in urban modeling applications. The calibration procedure is shown to be capable of systematically modifying arbitrary, randomly generated rule sets in order to produce a set of rules that is able to correctly replicate a series of test maps.
Although application of genetic algorithms was a dominant approach to CA identification, some non-genetic techniques are also available. Adamatzky @cite_14 proposed several approaches to extracting rules for different classes of CA. @cite_12 developed a form of hill climbing and backtracking to identify CA rules. In @cite_0 a deterministic sequential floating forward search method was used to select rules of CA. Another approach is based on parameter estimation methods from the field of system identification @cite_4 . A framework for solving the identification problems for both deterministic and probabilistic CA was presented in @cite_5 .