Autómatas Celulares

Para definir lo que es un autómata celular vamos a empezar por su versión más simple y vamos complicando el modelo. Empezamos por el más simple, un cuadrado que puede tener varios estados y cada estado está asociado a un color. El cambio de estados está regulado por un conjunto de reglas. Por lo que cada autómata queda definido por sus estados y las reglas que los cambian. A los autómatas de les conoce como celdas, individuos o células

Dos dimensiones

Siguiente nivel de dificultad los autómatas con vecinos a ambos lados. Son los autómatas unidimensionales. Se distribuyen en forma de línea. Cada autómata tiene dos vecinos que son otro autómata idéntico situado a la derecha e izquierda. Pero cómo sería muy aburrido tener muchos autómatas que cambien de estado sin interaccionar entre ellos ahora las reglas determinan el cambio según el estado propio y el de los dos vecinos.

El caso más estudiado de este tipo de autómatas celulares es el de celdas de dos estados: blanco y negro o 0 y 1 o muerto y vivo. Las reglas de cambio se expresan como tres celdas. La del centro representa el estado de la celda actual y la de la derecha e izquierda sus dos vecinos. El valor que tomara la celda central se representa debajo. Las reglas toman forma de figura del tetris. Por ejemplo dos formas de expresar la misma regla:

111110101100011010001000
0 1 0 1 1 0 1 0
regla90
Dos formas de expresar la misma regla

Esta regla es conocida como la regla 90. ¿De donde sale ese 90? . Muy sencillo, de la segunda fila de la tabla. En binario 01011010 = 90. Cada regla se denomina así, por el número decimal que se obtiene de poner en decimal los resultados de la regla de transformación. Como solo hay 8 posibles reglas (hay ocho posibles configuraciones de las tres celdas) solo hay 256 reglas.

Los autómatas unidimensionales se representa como una linea. Cada paso en su ejecución se representa como una linea nueva que se pone debajo de la anterior, formando un plano.

Regla 90 tras varios pasos

Tres dimensiones

Aumentamos una la dimensión vamos a los autómatas bidimensionales. En este caso hay 4 u 8 vecinos dependiendo que tipo de vecindad se ese, vecindad de Von Neumann solo tiene en cuenta los vecinos situados arriba, abajo, a la izquierda y a la derecha, mientras que la vecindad de Moore tiene en cuenta también los vecinos de las diagonales. En estos por lo general se tiene en cuenta el número de vecinos en un determinado estado para las reglas de cambio de estado. El ejemplo más famoso de este tipo es el juego de la vida que intenta emular una especie de ecosistema en un autómata muy simple cuyas reglas son:

  • Una célula rodeada de 3 o más vivas está viva al siguiente turno
  • Una célula rodeada de 2 células vivas no cambiara de estado
  • Una célula sin vecinas vivas estará muerta al siguiente turno

Fronteras

Uno de los problemas que tienes al diseñar un autómata es que haces con las celdas que están en los bordes (fronteras) del sistema. No tiene el mismo número de vecinos que las demás. Hay varias soluciones:

  • Valores fijos: se simula que más allá de las fronteras hay otras celdas con valores fijos
  • Mundo infinito: el autómata crece en cada iteración generándose nuevas celdas en los extremos. El problema de esto es que necesitas una cantidad enorme de memoria (idealmente infinita) para que funcione.
  • Mundo circular: se simula que los extremos están en contacto entre ellos, el superior con el inferior y el izquierdo con el derecho, por lo que no hay fronteras y el mundo es cerrado. Es la solución más habitual. Adoptando la forma de un cilindro en los autómatas unidimensionales y de un toro en los bidimensionales

Variaciones

Hemos explicado los ejemplos más sencillos vamos a ver algunas variaciones sobre estos ejemplos:

Más dimensiones. Si hay automatas de una y de dos dimensiones no cuesta mucho imaginar automatas de tres y es cierto que los hay y resultan utiles en cosas como la creacion de espacios en arquitectura, arte e ingenieria. ¿Y de más dimensiones? Alguno hay pero pierde una de las grandes vantajas de los automatas celulares, lo facil que es entender su evolución de forma visual.

Más estados. Es habitual los autómatas celulares con múltiples estados. Para no perder

Reglas estocásticas. Hasta ahora hemos visto reglas que calculan el estado que toma la celda de manera determinista, pero esto no tiene porque ser así, puede ser que la regla determine solo la probabilidad del cambio de estado.

Diferentes vecindarios. Ya hemos visto que hay dos vecindades tradicionales la Moore y la Von Neumann ¿Pero que pasa si queremos aumentar el número de vecinos o su complejidad?. Podríamos aumentar las dimensiones pero ya hemos visto que eso tiene un limite. La solución es ampliar l definición de “vecindad” en lugar de ser solo las celdas en contacto directo podemos usar como vecinos también las de las siguientes hileras. A esto se le denomina el radio de la vecindad.

RadioNº de vecinos
18
224
348
480

Numero de vecinos = ((2*radio+1)^2)-1;

Diferente geometría. Esta relacionado con el punto anterior. En lugar de usar cuadrados se pueden usar hexágonos, triángulos, combinaciones de diversas figuras. En el caso más extremo las relaciones de vecindad se puede representar como un grafo que conecte a los vecinos entre ellos siendo innecesario que tengan una representación geométrica.

Celdas con diferente reglas. Tampoco es necesario tener las mismas reglas para todos los individuos. Puede haber varios grupos de reglas que apliquen a distintos tipos de celdas o incluso que cada celda tenga sus propias reglas generadas como combinación de las suyas propias y de sus vecinos.

Un comentario en “Autómatas Celulares

  1. Pingback: Simular con autómatas celulares la propagación de una enfermedad | Construyendo a Chispas

Los comentarios están cerrados.