Correo Electrónico
DNINFOA - SIA
Bibliotecas
Convocatorias
Identidad U.N.
Publicado
Mining stochastic cellular automata to solve density classification task in two dimensions
Minando autómatas celulares estocásticos para resolver el problema de clasificación de densidad en dos dimensiones
DOI:
https://doi.org/10.15446/dyna.v87n215.83200Palabras clave:
Automated Model Design, Computational Framework, Machine Learning, Genetic Algorithm, Friedman test, Nemenyi’s posthoc test. (en)Diseño Automatizado de Modelos, Marco de Trabajo Computacional, Aprendizaje de Máquina, Algoritmo Genético, Prueba de Friedman, Prueba posthoc de Nemenyi (es)
Descargas
Density Classification Task (DCT) is a well-known problem that researchers have been tackling for more than two decades, where the main goal is to build a cellular automaton whose local rule gives rise to emergent global coordination. We describe the methods used to identify new cellular automata that solve this problem. The design of our cellular automata was carried out by a parallel genetic algorithm, specifically instantiated for this task. Our approach identifies both the neighborhood and its stochastic rule using a dataset of initial configurations that covers in a predefined and balanced way the full range of densities in DCT. We compare our results with some models currently available in the field. In some cases, our models show better performance than the best solution reported in the literature, with efficacy of 0.842 for datasets with uniform distribution around the critical density. The best-known cellular automaton achieves 0.832 in the same datasets. Tests are carried out in datasets of diverse lattice sizes and sampling conditions; we focused the analysis on the performance of our model around critical densities. Finally, by a statistical non-parametric test, we demonstrate that there are no significant differences between our identified cellular automata and the best-known model.
La Tarea de Clasificación de Densidad (TCD) es un problema bien conocido, donde el objetivo principal es construir un autómata celular cuya regla local dé lugar a una coordinación global emergente. Describimos los métodos utilizados para identificar nuevos autómatas celulares que resuelven este problema. Nuestro enfoque identifica tanto la vecindad como su regla estocástica utilizando un conjunto de datos de configuraciones iniciales que cubre de manera predefinida el rango completo de densidades en TCD. Comparamos nuestros resultados con algunos modelos disponibles actualmente en el campo. En algunos casos, nuestros modelos muestran un mejor rendimiento que la mejor solución informada en la literatura, con una eficacia de 0.842 para conjuntos de datos con distribución uniforme alrededor de la densidad crítica. Las pruebas se llevaron a cabo en conjuntos de datos de diversos tamaños de malla y condiciones de muestreo. Finalmente, mediante una prueba estadística no paramétrica demostramos que no hay diferencias significativas entre nuestros autómatas celulares identificados y el modelo más conocido.
Referencias
P. P. B. De Oliveira, “On Density Determination With Cellular Automata : Results, Constructions and Directions,” J. Cell. Autom., vol. 9, no. 5–6, pp. 357–385, 2014.
F. Rohrlich, “Computer Simulation in the Physical Sciences,” PSA 1990, vol. 2, pp. 507–518, 1991.
T. Toffoli and N. Margolus, “Invertible cellular automata: a review,” Physica D., vol. 45, pp. 229–253, 1990.
N. H. Packard, Adaptation Toward the Edge of Chaos. University of Illinois at Urbana-Champaign, Center for Complex Systems Research, 1988.
N. Díaz and I. Tischer, “Generic framework for mining cellular automata models on protein-folding simulations,” Genet. Mol. Res., vol. 15, no. 2, pp. 1–16, 2016.
R. Breukelaar and T. Back, “Evolving Transition Rules for Multi Dimensional Cellular Automata,” Lect. Notes Comput. Sci. Cell. Autom. Proc., vol. 3305, pp. 182–191, 2004.
F. Jiménez Morales, J. P. Crutchfield, and M. Mitchell, “Evolving two-dimensional cellular automata to perform density classification: A report on work in progress,” Parallel Comput., vol. 27, pp. 571–585, 2001.
M. Mitchell, J. P. Crutchfield, and P. T. Hraber, “Evolving cellular automata to perform computations: Mechanisms and impediments,” Physica D., vol. 75, no. 1–3, pp. 361–391, 1994.
D. B. Knoester, H. J. Goldsby, and C. Adami, “Leveraging Evolutionary Search to Discover Self-Adaptive and Self-Organizing Cellular Automata,” arXiv Prepr., p. 10, 2014.
G. M. B. de Oliveira, L. G. A. Martins, and E. Fynn, “Adaptive strategies applied to evolutionary search for 2D DCT cellular automata rules,” Proc. 13th Annu. Conf. Genet. Evol. Comput. - GECCO ’11, vol. 11, no. 07, pp. 1147–1153, 2011.
G. M. B. Oliveira, L. G. A. Martins, L. B. de Carvalho, and E. Fynn, “Some Investigations About Synchronization and Density Classification Tasks in One-dimensional and Two-dimensional Cellular Automata Rule Spaces,” Electron. Notes Theor. Comput. Sci., vol. 252, pp. 121–142, 2009.
D. Wolz and P. P. B. de Oliveira, “Very effective evolutionary techniques for searching cellular automata rule spaces,” J. Cell. Autom., vol. 0, no. 1, pp. 1–24, 2008.
R. Reynaga and E. Amthauer, “Two-dimensional cellular automata of radius one for density classification task p = 1/2,” Pattern Recognit. Lett., vol. 24, pp. 2849–2856, 2003.
H. Fuks, “Solving Two-dimensional Density Classification Problem with Two Probabilistic Cellular Automata,” J. Cell. Autom., vol. 10, no. 1–2, pp. 149–160, 2015.
N. Fatès, “A note on the Density Classification Problem in Two Dimensions,” in Automata 2012 - 18th International Workshop on Cellular Automata and Discrete Complex Systems, 2012, pp. 1–8.
R. Briceño, P. M. De Espanés, A. Osses, and I. Rapaport, “Solving the density classification problem with a large diffusion and small amplification cellular automaton,” Phys. D Nonlinear Phenom., vol. 261, no. 1, pp. 70–80, 2013.
N. Fatès, “Stochastic Cellular Automata Solutions to the Density Classification Problem: When Randomness Helps Computing,” Theory Comput. Syst., vol. 53, no. 2, pp. 223–242, 2013.
B. Wolnik, M. D. B, and W. Bolt, “The density classification problem in the context of continuous cellular automata,” in International Conference on Cellular Automata, 2016, pp. 79–87.
M. Dembowski, B. Wolnik, W. Bołt, J. M. Baetens, and B. de Baets, “Affine continuous cellular automata solving the fixed-length density classification problem,” Nat. Comput., no. 2014, pp. 1–11, 2017.
A. Andreica and C. Chira, “Using a hybrid cellular automata topology and neighborhood in rule discovery,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 8073 LNAI, pp. 669–678, 2013.
F. Simkovic, S. Ovchinnikov, D. Baker, and D. J. Rigden, “Applications of contact predictions to structural biology,” IUCrJ, vol. 4, no. 3, pp. 291–300, 2017.
R. Wirth and J. Hipp, “CRISP-DM: Towards a Standard Process Model for Data Mining,” Proc. 4th Int. Conf. Pract. Appl. Knowl. Discov. Data Min., pp. 29–39, 2000.
L. Bull, I. Lawson, A. Adamatzky, and B. De Lacy Costello, “Towards Predicting Spatial Complexity: A Learning Classifier System Approach to Cellular Automata Identification,” Proc. IEEE Congr. Evol. Comput., pp. 136–141, 2005.
J. Demšar, “Statistical comparisons of classifiers over multiple data sets,” J. Mach. Learn. Res., vol. 7, no. 1, pp. 1–30, 2006.
Cómo citar
IEEE
ACM
ACS
APA
ABNT
Chicago
Harvard
MLA
Turabian
Vancouver
Descargar cita
Licencia
Derechos de autor 2020 DYNA
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-SinDerivadas 4.0.
El autor o autores de un artículo aceptado para publicación en cualquiera de las revistas editadas por la facultad de Minas cederán la totalidad de los derechos patrimoniales a la Universidad Nacional de Colombia de manera gratuita, dentro de los cuáles se incluyen: el derecho a editar, publicar, reproducir y distribuir tanto en medios impresos como digitales, además de incluir en artículo en índices internacionales y/o bases de datos, de igual manera, se faculta a la editorial para utilizar las imágenes, tablas y/o cualquier material gráfico presentado en el artículo para el diseño de carátulas o posters de la misma revista.
