Autómatas celulares, aplicación WinCA I

Los autómatas celulares son modelos matemáticos utilizados para estudiar la evolución de sistemas dinámicos complejos, mediante la realización de simulaciones de las interacciones a lo largo del tiempo de un gran número de elementos, llamados células o celdas. En esta serie de artículos voy a presentar la aplicación WinCA, con la que se pueden construir y ejecutar este tipo de objetos.

En este enlace puedes descargar los ejecutables de la aplicación WinCA, y en este otro puedes descargar el código fuente de la solución WinCA, escrita en CSharp con Visual Studio 2015.

Existen muchos otros programas para construir y estudiar los autómatas celulares, uno de los mejores y más completos es DDLAB. Aquí tienes el enlace del website de discrete dynamics lab, donde puedes descargar el programa y documentación.

Aunque normalmente los autómatas celulares se representan utilizando líneas o cuadrículas de celdas regulares, en realidad un autómata celular es una red de celdas interconectadas que puede tener cualquier geometría, incluso geometrías irregulares con un número diferente de conexiones por célula.

Las celdas de un autómata celular pueden estar en un estado de entre un conjunto determinado de ellos, normalmente finito. Estos estados se representan coloreando la celda del color que se hace corresponder con el estado. Para cada uno de los estados, existen una serie de reglas que establecen bajo qué condiciones se pasa de dicho estado a otro cualquiera.

Para cada celda se define una vecindad, consistente en otra serie de celdas con las que está conectada. De este modo, para pasar de un estado a otro se tiene en cuenta tanto el estado de la celda como el de sus vecinas, comprobando las condiciones establecidas por las reglas mencionadas anteriormente.

En función del tipo de evolución del autómata, se pueden clasificar en cuatro tipos:

• Clase I: El sistema evoluciona siempre hacia un estado fijo y permanece en él, partamos de la configuración inicial que partamos.
• Clase II: El sistema evoluciona hacia una dinámica periódica, recorriendo una y otra vez un mismo conjunto de estados.
• Clase III: El sistema evoluciona hacia una dinámica caótica, presentando un aspecto de gran desorden.
• Clase IV: Sistemas con dinámica compleja. Se encuentran en la frontera entre el caos y el orden. Estos son los autómatas más raros, y los más interesantes para modelar el comportamiento de sistemas naturales.

Como introducción al programa WinCA, voy a mostrar algunos ejemplos de diferentes tipos de autómata.

Autómatas celulares lineales de una dimensión

La clase de autómatas más sencilla se construye con una línea de celdas de longitud finita. Cada celda tiene como vecinas la celda de la izquierda y la celda de la derecha y solo existen dos posibles estados. En versiones más complejas se puede establecer un número arbitrario de celdas vecinas y de estados.

Normalmente, estos sistemas se representan en una cuadrícula de dos dimensiones, de manera que podemos ver la evolución del sistema a lo largo del tiempo. En cada línea se representa el estado completo del sistema en uno de los pasos.

Para este tipo simple de autómatas, las reglas se abrevian utilizando un número entre 0 y 255 que se obtiene del conjunto completo de posibles estados de tres células adyacentes y su transición correspondiente. Por ejemplo, la regla 22 se establece de la siguiente manera:

Estado actual: 111 110 101 100 011 010 001 000
Siguiente estado 0 0 0 1 0 1 1 0

Donde el siguiente estado representado es el de la celda central. Podemos ver que esto equivale a las siguientes reglas:

• Una celda en estado 1 pasa a estado 0 si tiene algún vecino en estado 1
• Una celda en estado 0 pasa al estado 1 si tiene un solo vecino en estado 1

El número 22 que da nombre a la regla se obtiene juntando en un solo número binario los estados finales de todas las combinaciones.

Vamos a ver un ejemplo de esa regla en funcionamiento usando la aplicación WinCA. Después de arrancar el programa, usaremos la opción Abrir del menú Archivo y seleccionaremos el tipo de archivo Archivos de autómata (*.cauto). En el subdirectorio Examples de la aplicación seleccionaremos el archivo rule22.cauto:

En la barra de herramientas de la parte superior podemos seleccionar el tipo de autómata. En este caso, como hemos cargado un autómata predefinido, el tipo no se puede cambiar. Cuando estamos diseñando el autómata, como veremos en posteriores artículos, podemos cambiar el tipo para hacer interactuar los estados en diferentes configuraciones de celdas y dimensiones.

El proveedor de celdas es el componente que va a suministrar los tipos de celdas con el que se construye el autómata. De momento solo hay un tipo disponible, que es el proveedor de celdas básico.

El optimizador es un componente que permite acelerar la ejecución del autómata guardando las configuraciones conocidas para evitar tener que evaluar siempre para cada celda las expresiones de cambio de estado. Puede resultar útil si estas expresiones son muy complejas o realizan cálculos pesados. Obviamente, si se utilizan expresiones aleatorias, no podremos usar un optimizador. En posteriores artículos veremos como construir las expresiones de cambio de estado.

El último botón de la barra superior se utiliza para mostrar el editor de estados que corresponde al autómata, que veremos en el siguiente artículo de la serie.

La siguiente barra de herramientas contiene los controles del autómata. De izquierda a derecha son los siguientes:

• Mostrar / ocultar editor de vecindario: Con este botón controlamos la visualización del editor que aparece debajo de la barra de herramientas, que comentaré más adelante.
• Botones de zoom: Se utilizan para decrementar o aumentar el tamaño de la imagen del autómata.
• Botones de control de velocidad: Se usan para frenar o acelerar la ejecución del autómata cuando la lanzamos en modo automático.
• Botón de lanzamiento: Hace avanzar el autómata paso a paso de forma automática.
• Botón de pausa: Con este botón podemos detener el avance automático, sin perder la posición.
• Botón de avance paso a paso: Para avanzar un solo paso.
• Botón de reinicio: Para volver al estado inicial del autómata, el paso 0.

El resto de controles son dependientes del tipo de autómata. En el caso del autómata lineal son los siguientes:

• Editor de anchura: Donde podemos cambiar el número de celdas del autómata, escribiendo un nuevo valor y pulsando el botón que hay a la derecha del editor.
• Editor de historia: Donde podemos configurar la memoria que vamos a guardar de los estados pasados del autómata. Esto hará que veamos la ejecución como una cuadrícula de Ancho x Historia elementos.
• Botón de inicialización: Con este botón abriremos un cuadro de diálogo para establecer el estado inicial del autómata.
• Tipo de celda: Para seleccionar el tipo de las celdas del autómata. De momento solo está disponible el tipo de celda básico.
• Definición de contorno: Con este botón indicaremos si el autómata termina en los bordes izquierdo y derecho o si se pasa del borde izquierdo al derecho de forma circular.

El editor de estado inicial tiene el siguiente aspecto:

En la barra de herramientas, de izquierda a derecha tenemos los siguientes controles:

• Botones de zoom: Para disminuir o aumentar el tamaño de la imagen inicial del autómata.
• Botón de selección de patrones: Con este botón podemos seleccionar una serie de archivos de imagen que se utilizarán para crear patrones de estados. Estos archivos aparecerán en la parte inferior (en negro) del cuadro de diálogo.
• Botón de selección de modo patrón: Cuando esta opción esté seleccionada, se podrá elegir uno de los patrones previamente cargados en la parte inferior de la ventana (pulsando sobre el con el ratón) y crear sobre la imagen del autómata un patrón de estados determinado por el patrón seleccionado al pulsar sobre ella con el botón izquierdo del ratón. Los píxeles de la imagen que no sean de color negro, se convertirán en celdas con el estado seleccionado en el desplegable.
• Botón de selección de modo celda: Al pulsar con el botón izquierdo del ratón sobre una de las celdas del autómata, se le asignará el estado seleccionado en el desplegable.
• Botón de asignación de estado aleatoria: Con este botón, se asignará el estado seleccionado en el desplegable al número de celdas indicado en el cuadro de texto, de manera aleatoria.
• Desplegable de selección de estado: Para seleccionar el estado que se asignará con las diferentes opciones.
• Botón de relleno: Al pulsar este botón, todas las celdas del autómata se inicializarán con el estado seleccionado en el desplegable.
• Botón para guardar: Una vez inicializado el autómata, este botón permite guardar los cambios.
• Botón para cancelar: Para cancelar todos los cambios realizados.

En la parte central de la ventana se puede ver el estado inicial del autómata en forma de imagen, y en la parte inferior, con fondo negro, los patrones de estados que hayamos seleccionado.

Volviendo al formulario del autómata, debajo de las barras de herramientas se encuentra el editor de vecindario del autómata. En color negro se representa el cuadro que representa la célula actual, para marcar una célula como vecina, se debe pulsar sobre ella con el botón izquierdo del ratón, y su color cambiará a amarillo. Se puede eliminar un vecino pulsando sobre la celda con el botón derecho del ratón.

Sobre la celda aparece el número que corresponde a ese vecino, que se puede referenciar con ese índice en las expresiones de cambio de estado. Todas las celdas del autómata se inicializarán con la estructura de vecindario que se establezca de esta manera.

Al ejecutar el autómata, se puede ver su evolución en el tiempo. Este es un ejemplo en el que partimos de una única celda inicial en estado activo en el centro del autómata, después de unos cuantos pasos:

Autómatas celulares de dos dimensiones

Si ahora abrimos el archivo life-game.cauto podemos ver un autómata de dos dimensiones, el conocido juego de la vida de Conway. Esta es una muestra del autómata inicializado con alguna de las estructuras típicas del juego:

La única diferencia en los controles es que ahora un cuadro de texto para el alto de la cuadrícula sustituye al de la historia. También se puede ver que el editor de vecindad es diferente, permitiendo definir vecinos en dos dimensiones.

Aunque en estos autómatas parece que los elementos se desplazan sobre el espacio disponible, hay que tener en cuenta que no existe ningún tipo de movimiento. Cada celda cambia de estado según sus vecinas, no de lugar. El movimiento es solo aparente. Este es el aspecto del autómata después de unos cuantos pasos:

Por último, podemos abrir el autómata Excitation.cauto para ver la ejecución de un autómata con más de dos estados. Se trata de un autómata con una función aleatoria de cambio de estado que simula una especie de ondas de excitación / relajación de estados.

Eso es todo por el momento. En el próximo artículo mostraré como utilizar los editores de estados y propiedades de la aplicación WinCA.