Neighborhood Detection Using CA

International Journal of Computer Science (IJCS) Published by SK Research Group of Companies (SKRGC).

Abstract

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 aunified framework for representing the identification problem for both deterministic and probabilistic cellular automata. 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 a Bayesian information criterion. Experimental results show the effectiveness of our algorithm, and that it outperforms other leading CA identification algorithms.

References

[1] A. Ilachinski, Cellular Automata: A Discrete Universe. River Edge, NJ: World Scientific, 2001.

[2] K.-I. Maeda and C. Sakama, ?Identifying cellular automata rules,? J. Cellular Automata, vol. 2, no. 1, pp. 1–20, 2007.

[3] S. Wolfram, Cellular Automata and Complexity: Collected Papers. Boulder, CO: Westview, 2000.

[4] S. Wolfram, A New Kind of Science. Champaign, IL: Wolfram Medi Inc., 2002.

[5] Y. Zhao and S. Billings, ?The identification of cellular automata,? J. Cellular Automata, vol. 2, no. 1, pp. 47–65, 2007.

[6] J. Shan, S. Alkheder, and J.Wang, ?Genetic algorithms for the calibrationof cellular automata urban growth modeling,? Photogramm. Eng. RemoteSens., vol. 74, no. 10, pp. 1267–1277, Oct. 2008.

[7] E. Sapin, L. Bull, and A. Adamatzky, ?Genetic approaches to search for computing patterns in cellular automata,? IEEE Comput. Intell. Mag., vol. 4, no. 3, pp. 20–28, Aug. 2009.

[8] P. L. Rosin, ?Image processing using 3-state cellular automata,? Comput. Vis. Image Understanding, vol. 114, no. 7, pp. 790–802, Jul. 2010.

[9] N. Packard, ?Adaptation toward the edge of chaos,? in Dynamic Patterns in Complex Systems, J. Kelso, A. Mandell, and M. Shlesinger, Eds. Singapore: World Scientific, 1989, pp. 293–301.

[10] F. C. Richards, T. P. Meyer, and N. H. Packard, ?Extracting cellular automaton rules directly from experimental data,? Phys. D, vol. 45, no. 1–3,pp. 189–202, Sep. 1990.

[11] M. Mitchell, J. P. Crutchfield, and R. Das, ?Evolving cellular automata genetic algorithms: A review of recent work,? in Proc. 1st Int. Conf. EvCA, 1996.

[12] Y. Yang and S. Billings, ?Extracting Boolean rules from CA patterns,? IEEE Trans. Syst., Man, Cybern. B, Cybern., vol. 30, no. 4, pp. 573–580,Aug. 2000.

[13] Z. Pan and J. Reggia, ?Artificial evolution of arbitrary self-replicating structures,? J. Cellular Automata, vol. 1, no. 2, pp. 105–123, 2006.

[14] P. Rosin, ?Training cellular automata for image processing,? IEEE Trans. Image Process., vol. 15, no. 7, pp. 2076–2087, Jul. 2006.

[15] A. Adamatzky, Identification of Cellular Automata. London, U.K.: Taylor & Francis, 1994. Identification approach,? Kybernetes: Int. J. Syst. Cybern., vol. 26,no. 2, pp. 126–135, Feb. 1997. , 2002.

Keywords

Cellular automata (CA), neighborhood selection,rule identification.