Una Introducción a los Autómatas Celulares
Resumen
En este artículo se introducen los Autómatas Celulares
como una de las herramientas de la inteligencia artificial, utilizada para
la representación directa y discreta de comportamientos complejos
de algunos sistemas físicos, mecánicos, biológicos
y químicos. Se define la estructura básica de un Autómata
Celular, se introducen sus conceptos asociados y se plantean las mínimas
consideraciones que deben tenerse en cuenta para solucionar problemas por
medio de esta técnica. Finalmente, se enuncian algunos ejemplos
representativos y se presenta la descripción detallada y una ejecución,
en Applets de Java, de dos de los Autómatas clásicos:
el "Juego de la Vida" y "Mayoría
Alineada".
Abstract
In this article the basic concepts are introduced associate to the Cellular
Automata, like tool of the used artificial intelligence for the construction
of discreet models of some physical, biological and chemical systems. The
basic structure of a Cellular Automata is defined and the basic
considerations to solve problems by means of this technique. Finally, some
classic examples are enunciated and the detailed description appears and
an execution, in Java Applets, for two Automata: the "Life"
and "Aligned Majority". Not english
version avaliable.
1. Introducción
El modelamiento de la mayoría de sistemas físicos, eléctricos
y mecánicos, está basada en métodos y expresiones
matemáticas, las cuales representan teóricamente el comportamiento
de dichos sistemas. Generalmente, para modelar sistemas de naturaleza
contínua, son utilizadas las ecuaciones diferenciales, las integrales
funcionales y las variables de estado, entre otras. Algunos procedimientos
de discretización y digitalización de sistemas, permiten
realizar análisis numéricos sobre modelos aproximados.
Una técnica matemática compleja utilizada para modelar
algunos sistemas físicos y mecánicos es el Método
de los Elementos Finitos (FEM), cuya finalidad es discretizar
espacios de naturaleza contínua, sobre los cuales es posible realizar
análisis numéricos para comprender, por medio de un modelo
discreto, el comportamiento de sistemas analógicos. No obstante,
la complejidad de aplicar FEM sobre algunos sistemas es tal, que resulta
difícil lograr modelos que describan con precisión sus comportamientos.
FEM es de amplia utilización en análisis de sistemas y espacios
físico-mecánicos donde el objetivo sea comprender la resistencia
de materiales, la dinámica de partículas y en general el
comportamiento y la interacción de los elementos base del sistema
en el espacio; pero quedan aún muchos sistemas complejos y de diversa
naturaleza en los cuales no es convencional aplicar esta técnica,
por ejemplo, sistemas químicos, biológicos, evolutivos, genéticos,
eléctricos, computacionales e inclusive otros físicos y mecánicos.
Para el modelamiento de este tipo de sistemas quedan aún tres opciones:
Lograr un modelo de naturaleza contínua (en aquellos sistemas analógicos),
en el cual se requiere expresiones de funciones contínuas; utilizar
métodos aproximativos de discretización (sin embargo, se
tienen problemas de digitalización del modelo) o modelar con un
Autómata
Celular.
Los Autómatas Celulares son estructuras ideales para construir
modelos digitales aproximativos de algunos sistemas complejos de naturaleza
contínua, sin pasar por modelos analógicos. Es posible,
por ejemplo, lograr sencillos modelos digitales que representen con suma
fidelidad algunas leyes de la física.
2. Estructura de un Autómata Celular
Un Autómata Celular es una herramienta computacional que
hace parte de la Inteligencia Artificial basada en modelos biológicos,
el cual está básicamente compuesto por una estructura estática
de datos y un conjunto finito de reglas que son aplicadas a cada nodo o
elemento de la estructura. El interés que ha despertado esta
técnica radica en la sencillez y en la simplicidad que caracteriza
la construcción de los modelos; además, en la particularidad
de los patrones de comportamiento presentados por el Autómata
en tiempo de ejecución.
Basados en el planteamiento que presenta Muñoz6
acerca de la estructura de un Autómata Celular, se definen
como sus componentes básicos:
-
Un plano bidimensional o un espacio n-dimensional dividido en un número
de subespacios homogéneos, conocidos como celdas. A todo esto
se le denomina Teselación Homogénea.
-
Cada celda puede estar en uno de un conjunto finito o numerable S
de estados.
-
Una Configuración C, la que consiste en asignarle un estado
a cada celda del autómata.
-
Una Vecindad definida para cada celda, la que consiste en un conjunto
contíguo de celdas, indicando sus posiciones relativas respecto
a la celda misma.
-
Una Regla de Evolución, la cual define cómo debe cada
celda cambiar de estado, dependiendo del estado inmediatamente anterior
de su vecindad.
-
Un Reloj Virtual de Cómputo conectado a cada celda del autómata,
el cual generará "tics" o pulsos simultáneos a todas
las celdas indicando que debe aplicarse la regla de evolución y
de esta forma cada celda cambiará de estado.
Según Toffoli y Margolus7, se define
un Autómata Celular sólo si se tiene que todas las
celdas:
-
Tienen el mismo Conjunto S de
Estados posibles.
-
Tienen la misma forma de Vecindad.
-
Tienen la misma Regla de Evolución.
2.1 Consideraciones adicionales
Un Autómata Celular puede ser construido definiendo alguna
especificación para cada uno de sus componentes, es decir, de alguna
forma se definirá su teselación, los posibles estados,
las vecindades y la regla de evolución; no obstante,
se tienen unas consideraciones y posibilidades con estos componentes, las
que permitirán cierta flexibilidad en el momento de construir el
autómata.
-
El autómata puede ser de 1, 2, 3, ..., n dimensiones.
-
La teselación puede ser finita o infinita, con condiciones
de frontera abiertas o periódicas.
-
El conjunto de estados S no
necesita tener ninguna estrutura algebraica adicional.
-
La vecindad puede ser simétrica o no y puede incluir o no
a la propia celda.
-
La regla de evolución es una tabla o unas reglas.
3. Algunos ejemplos y aplicaciones
Tal vez, lo más llamativo e interesante de los Autómatas
Celulares es el comportamiento presentado por el modelo en tiempo de
ejecución y la similitud de éste con la complejidad de la
naturaleza contínua. "Life" o "El Juego de la Vida",
por ejemplo, simula la existencia de diferentes "formas de vida" sobre
un espacio bidimensional, las cuales presentan singular comportamiento
a través del tiempo; "Evolución" es un autómata
que simula cómo un conjunto de microbios sobreviven comiendo bacterias;
y "Mayoría Alineada" muestra cómo es el comportamiento
de la tensión superficial entre líquidos no permeables.
A continuación, algunos ejemplos de Autómatas Celulares
(tomados de Muñoz6).
-
"Life" o "El Juego de la Vida", de John Hourton Conway.
-
"Mayoría Alineada". Modelo Celular de Dedwdney2.
-
"Evolución". Modelo Celular de Dewdney3.
-
"Reacción Química de Belousov-Zhabotinski".
Modelo Celular de Dewdney2.
-
"HPP-GAS" (modelo de dinámica de fluidos), de Hardy, de Pazzis
y Pomeau5.
El modelar un sistema del mundo real por medio de un Autómata
Celular, requiere que se conozca al menos su comportamiento global.
Si conocido este comportamiento se quiere deducir un conjunto de reglas
de evolución local que lo genere, entonces se desea desarrollar
el autómata por el Problema Inverso. De lo contrario,
si se desea primero experimentar y ajustar una Regla de Evulución
pseudo-aleatoria hasta lograr un comportamiento similar al del sistema
real, entonces se desea desarrollar el autómata por el Problema
Directo. No obstante, se puede lograr algo intermedio, a partir
de comportamientos locales del sistema real construir una regla de evolución
local y ponerla a prueba para determinar si se logra un autómata
que modele el comportamiento del sistema global, a esto se el denomina
el Problema Intermedio.
Dependiendo de la naturaleza compleja de un sistema y de la posibilidad
de identificar estados locales y reglas generales de evolución,
se podrían simular comportamientos por medio de Autómatas
Celulares; por ejemplo, los mundos y sistemas enunciados a continuación
son susceptibles a un modelamiento por esta técnica: Simulación
de tráfico automotor, virus, glóbulos, epidemias, bacterias,
contaminación, ecosistemas, evolución galáctica, flujo
de electrones, acción & reacción, medios granulares y
gases de Fermi entre otros.
4. Dos autómatas implementados
"El Juego de la Vida"
| Teselación: |
Cuadrícula homogénea. |
| Estados: |
Cuatro estados:
Vivo (negro)
Muerto (blanco)
"Recién" Vivo (gris oscuro)
"Recién" Muerto (gris claro)
|
| Estado Inicial: |
Configuración aleatoria. |
| Vecindad: |
Cuadrícula de 3x3 centrado en una celda. Incluye la celda
del centro. |
| Regla de Evolución: |
Una celda viva permanece viva sólo si en la vecindad hay 2 ó
3 celdas vivas, de lo contrario se muere.
Una celda muerta cambia a viva sólo si en la vecindad hay exactamente
3 celdas vivas, de lo contrario sigue muerta.
|
|
"Life"
John Hourton Conway
Modelo celular de Berchelamp, Conway y Guy1;
Gardner4.
|
"Mayoría Alineada"
| Teselación: |
Cuadrícula homogénea. |
| Estados: |
Cuatro estados:
Vivo (negro)
Muerto (blanco)
"Recién" Vivo (gris oscuro)
"Recién" Muerto (gris claro)
|
| Estado Inicial: |
Configuración aleatoria. |
| Vecindad: |
Cuadrícula de 3x3 centrado en una celda. Incluye la celda
del centro. |
Regla de
Evolución: |
Si en una vecindad la mayoría de celdas están vivas, entonces
la celda del centro deberá estar viva; excepto para exactamente
5 celdas vivas, si es así, entonces deberá estar muerta.
Si en una vecindad la mayoría de celdas están muertas, entonces
la celda del centro deberá estar muerta; excepto para 4 celdas muertas,
si es así, entonces deberá estar viva.
|
|
"Mayoría Alineada"
Modelo celular de Dedwdney2.
|
5. Conclusiones
Es típico de un Autómata Celular generar comportamientos
complejos a partir de reglas muy sencillas. En conclusión,
un Autómata Celular está compuesto por:
-
Una Teselación Homogénea.
-
Un conjunto finito de Estados para cada celda.
-
Una Vecindad para cada celda.
-
Una Regla de Evolución.
Son útiles en la construcción de modelos donde los elementos
base o componentes (actores) son de similar naturaleza y comportamiento;
donde éstos se rigen por reglas parecidas y donde, en el mismo sistema
real, se identifican componentes diferenciables, independientes, aislables
y/o discretos.
Como propuesta de proyecto, se plantea desarrollar un programa computacional
que permita la creación, edición y ejecución de Autómatas
Celulares. Este programa, como entorno integrado de desarrollo,
deberá permitir: definir la dimensión de la teselación,
la vecindad, los estados, la regla de evolución y el estado inicial,
entre otros. Se podrá visualizar paso a paso la evolución
del autómata como también la configuración luego de
haber ejecutado n pasos de evolución. Además,
como cualquier programa, deberá permitir la manipulación
de los autómatas en archivos, la edición de los mismos, el
manejo de gráficas y los correspondientes menús de ayuda
y documentación.
6. Palabras Clave
Autómata(s) Celular(es), Celda(s), Discretizar, Ecuación(es)
Diferencial(es), Elementos Finitos (FEM), Estado Local, Estado Global,
Estados, Estructura(s) Estática(s) de Dato(s), Integral(es) Funcional(es),
Inteligencia Artificial (IA), Modelo(s), Modelos Biológicos, Problema
Directo, Problema Intermedio, Problema Inverso, Regla de Evolución,
Regla(s) Local(es), Reloj Virtual de Cómputo, Sistema(s), Sistema(s)
Análogo(s), Sistema(s) Complejo(s), Sistema(s) Discreto(s), Teselación,
Variables de Estado, Vecindad.
7. Referencias en Línea
8. Referencias Bibliográficas
| [1] |
BERCHELAMP, Elwyn; CONWAY, John y GUY, Richard.
Winning Ways. Academic Press, 1982. |
| [2] |
DEWDNEY, A. K. Artículo: JUEGOS DE ORDENADOR,
en: Investigación y Ciencia. No. 145, 1988. |
| [3] |
DEWDNEY, A. K. Artículo: JUEGOS DE ORDENADOR,
en: Investigación y Ciencia. No. 154, 1989. |
| [4] |
GARDNER, Martin. Wheels: Life and other Mathematical
Amazements. W. H. Freeman and Company, 1983. |
| [5] |
HARDY, J.; DE PAZZIS, O. y POMEAU, Y. Molecular
Dynamics of a Classical Lattice Gas: Transport Properties and Time
Correlation Functions. Physical Review, No. 5, 1976. |
| [6] |
MUÑOZ CASTAÑO, José Daniel. Artículo:
AUTÓMATAS
CELULARES Y FÍSICA DIGITAL, en: Memorias del Primer
Congreso Colombiano de NeuroComputación. Santafé
de Bogotá, D. C.: Academia Colombiana de Ciencias Exactas,
Físicas y Naturales, 1996. 28 p. ISBN 958-9205-17-8. |
| [7] |
TOFFOLI, Tommaso y MARGOLUS, Norman. Cellular
Automata Machines: A New Environment for Modeling. The
MIT Press, Cambridge MA, 1987. |
Editado el 15 de Marzo de 1999.
Primera Versión.
