Aplicación de aprendizaje de máquinas para la clasificación de autómatas celulares

Abstract

Los autómatas celulares son una familia muy amplia de sistemas dinámicos discretos, con comportamientos altamente diversos. Se trata de sistemas distribuidos (por lo general, en una grilla regular de dimensión 1, 2 o a veces superior), en los que a cada celda se le asocia una máquina de estados finitos, que es actualizada en cada iteración dependiendo de los estados de las celdas que le son vecinas. De esta forma, un autómata celular dado, queda determinado por: su topología, el conjunto de estados, la vecindad considerada y la función de transición. A partir de su dinámica evolutiva, Stephen Wolfram plantea una clasificación en la cual distribuye 255 reglas de autómatas celulares en 1D denominadas elementales, separándolos en 4 clases según su convergencia: estado homogéneo, estructuras estables o periódicas, comportamiento caótico y estructuras complejas[Wolfram, 1984]. Dentro de este contexto, se propone comparar el desempeño de clasificaciones automáticas realizadas por diversos tipos de algoritmos, basados en aprendizaje supervisado y no supervisado, con el fin de obtener un mayor entendimiento sobre estas y lo que representan. A partir de los experimentos realizados, se concluye que modelos basados en VGG 16 obtienen una alta exactitud realizando la clasificación de Wolfram, mientras que para el caso de no supervisado es posible obtener al menos 3 clústeres donde uno posee bastante similitud a la clasificación propuesta por Wolfram.

Cellular automata are a very large family of discrete dynamical systems, with highly diverse behaviors. They are distributed systems (usually in a regular grid of dimensión 1, 2 or sometimes higher), in which a finite state machine is associated to each cell, which is updated at each iteration depending on the states of its neighboring cells. Thus, a given celular automaton is determined by: its topology, the set of states, the considered neighborhood and the transition function. From its evolutionary dynamics, Stephen Wolfram proposes a classification in which he distributes 255 cellular automata rules in 1D called elementary, separating them into 4 classes according to their convergence: homogeneous state, stable or periodic structures, chaotic behavior and complex structures[Wolfram, 1984]. Within this context, it is proposed to compare the performance of automatic classifications performed by different types of algorithms, based on supervised and unsupervised learning, in order to obtain a better understanding of them and what they represent. From the experiments performed, it is concluded that models based on VGG 16 obtain a high accuracy performing Wolfram’s classification, while for the case of unsupervised it is possible to obtain at least 3 clusters where one has enough similarity to the classification proposed by Wolfram.