06.- Autómata celular

Tabla de contenidos
  1. Introducción

Un autómata celular (AC) es un modelo matemático y computacional que sirve para representar sistemas dinámicos que evolucionen en pasos de tiempo discretos, no de forma continua.

Estos modelos se desarrollan con un conjunto de celdas o células que pueden cambiar de estado o valor.

Introducción

Estos modelos se desarrollan con un conjunto de celdas o células que pueden cambiar de estado o valor. Cada célula es un componente simple conectado a sus vecinos cercanos: hay comunicación limitada, las células sólo pueden comunicarse  directamente con sus vecinos; no hay control central; no hay célula que esté encargada de otra célula.

Hay una amplia clase de modelos llamados «autómatas celulares», quizás el más importante sea el Juego de la Vida. Hay una simulación en NetLogo, Mini-Life, que puede descargarse aquí. (Transcripción en N06.- Mini-Life) En este caso es muy aconsejable utilizar previamente estos modelos para entender mejor el contenido de la unidad. (Las instrucciones en la información NetLogo).

Referencias y lecturas complementarias

1.- Artículo sobre el «Juego de la vida«

2.- Nota biográfica sobre sobre «John von Neumann» en un sitio web muy recomendable con biografías de grandes matemáticos.

6.1.- MODELO DE SISTEMA COMPLEJO

Con los autómatas celulares obtenemos dinámicas bastante complicadas a partir de reglas simples; tienen la capacidad de hacer procesamiento sofisticado de información y pueden evolucionar con algoritmos genéticos. Por todo ello, un AC es un modelo idealizado de un sistema complejo.

Esta sección está dedicada a dos versiones bidimensionales del juego de Conway: además del Mini-Life en NetLogo hay otro modelo más completo, GameOfLife, que permite añadir conjuntos celulares prediseñados cuando se edita el modelo. Puede descargarse aquí. (Transcripción N06.- GameOfLive)

El objetivo de esta sección es familiarizarse con la terminología, con el vecindario, con la creación de patrones y con los efectos de las reglas en el desarrollo del ‘juego’.

6.3.- AUTÓMATAS CELULARES ELEMENTALES

Los autómatas celulares del tipo Juego de la Vida de Conway se desarrollan en una cuadrícula bidimensional. Hay otros tipos que lo hacen en una estructura unidimensional: son los autómatas celulares elementales (ACE)

Sabiendo que hay 8 vecindarios posibles para cada celda (en autómatas de radio 1), se definen sus reglas de evolución. Tales reglas se establecen para la evolución de la celda i-esima en la etapa t-1, para alcanzar un nuevo estado en la etapa t:

Como hay 8 posibles vecindarios en ACE’s de radio 1 y dos posibles estados, esto significa que:

Stephen Wolfram es un matemático y físico británico que ha estudiado autómatas celulares en profundidad, y en particular ha estudiado estos autómatas celulares elementales.

Ha escrito «Un Nuevo Tipo de Ciencia», es una discusión de 1200 páginas sobre cómo la ciencia en sí mismo podría repensarse en términos de sistemas simples como autómatas celulares que producen un comportamiento muy complejo, que se puede consultar libremente desde aquí.

A él se debe la forma de numerar los ACE de radio 1, la llamada «Numeración de Wolfram» para las 256 posibles reglas. El modelo de NetLogo «ElementaryCAs» que puede descargarse aquí, permite editar – seleccionar estas reglas y observar su comportamiento a medida que avanzan las etapas. (Transcripción N06.- ElementaryCAs)

Esta regla es particular en muchos aspectos. Puede consultarse el artículo de la Wikipedia en ingles rule 110 (hay una traducción al español aquí)

6.4.- AUTÓMATAS CELULARES ELEMENTALES: CLASIFICACIÓN DE WOLFRAM

6.5.- DINÁMICA EN LOS ACE

Para establecer el comportamiento dinámico de los autómatas celulares elementales, se puede hacer una comparación con la dinámica del caos en el mapa logístico. El problema surge cuando se quiere encontrar un homólogo al parámetro de control R:

Referencias y lecturas complementarias

1.- Artículo sobre «Christopher Langton«

6.6.- DINÁMICA EN LOS AUTÓMATAS CELULARES NO ELEMENTALES

Los autómatas celulares no elementales  tienen reglas para más de 2 estados y más de 3 vecinos . Se puede experimentar con ellos  con el JavaScript «edge of chaos» en página web o descargar la aplicación edgeofchaosca.jar

Los ajustes para esta aplicación son:

Número de estados, (Number of States): En los que puede estar una celda. Son colores diferentes que pueden aparecer en el mundo; mínimo 2 (vivo, muerto), máximo 32, (en este programa)

Tamaño del vecindario, (Neighborhood Size): Número de vecinos, incluida la propia celda, que se consideran. Siempre impar pues la celda central es la que evoluciona. Cuanto mayor sea el número de estados y mayor el tamaño del vecindario, se necesitan más reglas para el autómata. Para limitar el número de reglas, existe un tamaño máximo de vecindario y el tamaño máximo depende del número de estados. Si el número de estados es 16 o más, el único tamaño de vecindario posible es 3.

Isotropía, (Isotropic): La vecindad de una celda tiene un determinado patrón de colores, y este patrón determina el color de la celda en la próxima generación. Suponga que el patrón de colores en el vecindario se invierte de izquierda a derecha. ¿Puede esto afectar el color de la célula en la próxima generación? Si no afecta, se dice que las reglas son «isotrópicas». Si afecta, son «anisotrópicos». Las reglas isotrópicas tienden a dar resultados más simétricos, por lo que las reglas son isotrópicas por defecto en este programa. Sin embargo, puede desactivar la isotropía si lo desea.

NOTA: Puede que una configuración inicial produzca diferentes comportamientos para un mismo autómata celular, pero lo que importa es el comportamiento promedio. La cuestión es si el comportamiento caótico tiene una dependencia significativa  de las condiciones iniciales.

6.7.- COMPUTACIÓN UNIVERSAL CON AUTÓMATAS CELULARES

Mientras la computación universal en AC es bien interesante, incluso sorprendente, con lo sencillos que son, (en especial los ACE), no son la manera más práctica de hacer un cómputo.

Es demasiado lento simular un Computador Universal en un Autómata Celular. También son muy difíciles de programar. En realidad nadie hace cómputos con propósitos prácticos usando las habilidades de computación universal de los AC:

6.8.- EVOLUCIÓN DE AUTÓMATAS CELULARES CON ALGORITMOS GENÉTICOS

Veamos la capacidad de un algoritmo genético para diseñar autómatas celulares que realicen cálculos. Las estrategias computacionales de los autómatas celulares resultantes pueden entenderse utilizando un marco en el que las «partículas» incrustadas en configuraciones de espacio-tiempo transportan información e interacciones entre partículas efecto del procesamiento de la información.

Se puede usar un algoritmo genético para evolucionar autómatas celulares para tener el comportamiento deseado de forma que el fitness de cada autómata celular sea la medida de cómo desempeña la tarea de clasificar las mayorías

El fitness del autómata celular le permitirá reproducirse mediante cruces y tener mutaciones:

El proceso evolutivo es el mismo que se usó para el robot virtual:

El resultado que se busca es el:

6.9.- PROCESAMIENTO DE INFORMACIÓN EN LOS SISTEMAS COMPLEJOS

La cuestión es ¿Cómo describimos el procesamiento de información en los sistemas complejos? O más concretamente: ¿Cómo procesan información estos sistemas, con componentes simples, que están descentralizados y sin control central? 

Referencias y lecturas complementarias

Hay muchos artículos y trabajo relacionados con los autómatas celulares. La selección que he hecho son los que me parecen más sencillos de leer:

1.- Artículo «Autómata celular«

2.- En la web, (muy aconsejable) de Fernando Sancho Caparrini la página «Autómatas Celulares«

3.- Una descripción que presenta un formalismo próximo al que se ha expuesto antes, pero algo más riguroso, en «Autómatas Celulares y su Aplicación en Computación» en una conferencia presentada por Santiago Fernández Fraga, Santiago Miguel y Rangel Mondragón Jaime, en el VIII Congreso Internacional de Ingeniería Mecánica y Mecatrónica. MÉXICO

4.- El artículo de David Alejandro Reyes Gómez, de la UNAM, «Descripción y Aplicaciones de los Autómatas Celulares» presenta aplicaciones en arquitectura, bioinformática, control de incendios forestales y criptografía.

5.- En la misma línea, «Autómatas celulares y aplicaciones» de Alberto Cano Rojas y Ángela Rojas Matas.

6.- En «Evolución de autómatas celulares utilizando algoritmos genéticos» los autores, Juan Ignacio Vázquez y Javier Oliver, de la universidad de Deusto resumen así su artículo: «Las capacidades computacionales de los autómatas celulares son elevadas. sin embargo, su naturaleza paralela dificulta su programación mediante métodos convencionales. Entra las alternativas para esta programación se encuentra la aplicación de algoritmos genéticos con el fin de obtener el autómata celular óptimo que lleve a cabo una tarea concreta…»

Anterior
Siguiente