http://www.redcientifica.com/gaia/

http://www.redcientifica.com/gaia/ac/auto_c.htm
Castellano > Vida Artificial > Autómatas...


Autómatas Celulares

Farid Fleifel Tapia - faflta@inf.upv.es
Ricardo Aranguren - ra20914@zurron.upna.es http://www.geocities.com/ResearchTriangle/2262/
Manuel de la Herrán Gascón

Indice:


1.- Autómatas Celulares e Inteligencia Artificial

En la Inteligencia Artificial (IA) podemos observar dos enfoques distintos, según el objetivo perseguido:

El segundo enfoque no pretende obtener programas inteligentes, sino descubrir en qué consiste la inteligencia. Ya que la actividad inteligente surge inicialmente en animales vivos, una parte de los esfuerzos orientados en este sentido pretenden no sólo descubir en qué consiste la inteligencia, sino también en qué consiste la vida.

La Vida Artificial es el intento por parte del hombre, de crear vida, o algo parecido a la vida, mediante la combinación de símbolos (datos) y procesos de símbolos (programas) independientemente del soporte físico de estos símbolos y procesos.

La Vida Artificial, en parte, trata de recrear los procesos propios de la vida, partiendo de la suposición de que la vida o los procesos propios de la vida, si no son imprescindibles para la aparición de la inteligencia, al menos son una buena idea para crear inteligencia, ya que evolutivamente los seres inteligentes siempre han sido seres vivos.

Por otra parte, la Vida Artificial trata de descubrir que es la vida. Fundamentalmente, trata de descubrir si la vida depende de un soporte (físico, energético, metafísico o como se quiera llamar) o se trata de procesos, datos, configuraciones, esquemas, es decir, de objetos lógicos y sus relaciones, independientes del soporte. Este enfoque de la Vida Artificial se aleja tanto de la búsqueda de la inteligencia que parece difícil clasificarlo dentro de la Inteligencia Artificial si no se toman en cuenta las reflexiones anteriores, y perfectamente se podría clasificar como un campo de estudio independiente de la Inteligencia Artificial.

Dentro de la Vida Artificial, los Autómatas Celulares son el más claro ejemplo de este rodeo en la búsqueda de la inteligencia. Es bastante extraño decir que los Autómatas Celulares son inteligentes, no lo parecen en absoluto. En cambio, poseen muchos de los aspectos fundamentales de la vida en cuanto a procesos. Además, esto se intenta conseguir con la máxima simplicidad posible, por lo que podrían ser el fundamento, al menos teórico, de la vida, y por extensión, de la inteligencia.

[ Volver al Indice ]


2.- Los primeros autómatas celulares

Los estudios sobre autómatas finitos, máquinas de Turing, y otros modelos que siguen la misma filosofía configuran lo que se ha denominado Teoría de Autómatas y Máquinas de Turing, o simplemente Teoría de Autómatas, dentro de la Teoría de la Computación.

En la década de los 50, dos neurofisiólogos, Warren S. McCulloch y Walter Pitts diseñaron un modelo matemático para representar el funcionamiento de las células cerebrales que fue el origen de los que hoy se conoce por redes neuronales. El modelo era una aproximación muy sencilla al comportamiento real de las neuronas, pero tenía grandes aplicaciones en otros contextos. En el campo puramente matemático, Kleene redefinió el modelo y dio lugar a los autómatas finitos, especie de máquinas ideales o modelos matemáticos, al modo de la máquina de Turing, con posibilidades bastante más reducidas, pero muy adecuadas para ciertos procesos de cálculo.

Por otra parte el inglés Turing consiguió definir conceptualmente una máquina de cálculo que se considera universal, es decir, el mecanismo de procesar cualquier algoritmo. Turing diseñó un modelo matemático de autómata que siguiendo unas reglas simples conseguía solucionar una gran gama de problemas. En principio, la máquina de Turing constituye el instrumento de cálculo universal, el más general. No es posible dar una demostración rigurosa de esto, aunque sí se tiene una gran cantidad de indicios, agrupados en lo que se conoce como Tesis de Church, que puede plantearse así: "No existen funciones que puedan ser definidas por personas, y cuyo cálculo sea descrito por algún algoritmo, que no puedan computarse con una máquina de Turing". Basándose en la máquina de Turing, Von Neumann trabajó en una máquina autorreproductiva que llamó kinematon y en la idea de autómata celular.

[ Volver al Indice ]


3.- Definición de autómata celular

Los autómatas celulares son redes de autómatas simples conectados localmente. Cada autómata simple produce una salida a partir de varias entradas, modificando en el proceso su estado según una función de transición. Por lo general, en un autómata celular, el estado de una célula en una generación determinada depende única y exclusivamente de los estados de las células vecinas y de su propio estado en la generación anterior.

Los autómatas celulares son herramientas útiles para modelar cualquier sistema en el universo. Pueden considerarse como una buena alternativa a las ecuaciones diferenciales y han sido utilizados para modelar sistemas físicos, como interacciones entre partículas, formación de galaxias, cinética de sistemas moleculares y crecimiento de cristales, así como diversos sistemas biológicos a nivel celular, multicelular y poblacional.

[ Volver al Indice ]


4.- Ejemplos de Autómatas Celulares

Estos tres ejemplos de autómatas se pueden descargar de la página download.

[ Volver al Indice ]


4.1.- El juego de la vida de Conway

Uno de los autómatas celulares más conocidos es el que John Horton Conway llamó el juego VIDA (Life Game). El juego VIDA es un autómata celular bidimensional en cuadrícula con dos estados por celda. Cada celda o célula puede estar viva o muerta y en cada generación se aplica un algoritmo que sigue estas tres reglas:

1.- Cada célula viva con dos o tres células vecinas vivas sobrevive a la siguiente generación.

2.- Cada célula viva con ninguna, una, o más de tres células vivas a su alrededor pasa a estar muerta.

3.- Cada célula muerta con tres células vecinas vivas resucita en la siguiente generación.

El juego VIDA presenta configuraciones finales estables, periódicas o no. Langton defiende que presenta propiedades de catálisis (acciones de construcción arbitrarias), de transporte (borrando estructuras y reconstruyéndolas en otro lugar del espacio celular), estructurales (como elementos estáticos, barreras, etc.), de regulación, defensa e incluso informativas, y que por tanto estos autómatas virtuales tienen capacidades computacionales suficientes para cumplir los papeles funcionales que juegan las macromoléculas en la lógica molecular de la vida. En definitiva, que funcionalmente, los autómatas son equiparables a los componentes básicos de la vida en nuestro planeta.

[ Volver al Indice ]


4.2.- El programa "Células" de Peter Donnelly

El programa "células" es en esencia una curiosidad científica propuesta por primera vez por Peter Donnelly del University College de Swansea, Gales, y Dominic Welsh, de la universidad de Oxford. El programa fue descrito en detalle por A. K. Dewdney en su artículo "Cinco piezas sencillas" para Scientific American. En este artículo se bautiza al programa con el nombre de "votación", ya que según el autor pretende simular una votación política algo particular. Citando textualmente:

"Las casillas de un cuadriculado rectangular están coloreadas de blanco o negro, aleatoriamente. Se supone que cada color refleja la opinión política de una persona residente en esa casilla. Un color podría representar 'demócrata' y el otro 'republicano'.
[...]
A cada señal de reloj, se selecciona al azar uno de los votantes y su opinión política se somete a cambio: se selecciona al azar uno de sus ocho vecinos y la convicción política del elector se transforma en la de este vecino, independientemente de cuál fuera su opinión anterior.
[...]
Al hacer funcionar este modelo, confesadamente simplista, del proceso político, ocurren cosas llamativas y extrañas. Primero se desarrollan grandes bloques de voto homogéneo. Estos bloques son zonas geográficas donde todo el mundo es de la misma opinión política. Seguidamente tales bloques van migrando en torno al cuadriculado y, durante cierto tiempo luchan, como buscando su predominancia. Finalmente, el sistema bipartidista se viene abajo, por acabar todo el mundo votando de igual manera".

Además de esta interpretación de la ejecución del programa, hay otra más aproximada, y mucho más sugerente para los interesados en la vida artificial y temas afines. Podemos llegar a apreciar comportamientos "cuasi-biológicos" si observamos la evolución de los votantes como un ejemplo de la coexistencia-competitividad de dos especies similares en un mismo medio con abundancia de alimento, como podría ser el caso de dos especies de bacterias en un fluido rico en nutrientes.

La interpertación es la siguiente: Cada posición de la matriz representa una célula de una especie determinada. En cada ciclo se elige aleatoriamente una de las células de la matriz. Esa célula muere, dejando un espacio libre. Ese espacio es ocupado inmediatamente de la siguiente forma: Se elige a una de las ocho células contiguas a ese espacio vacío para reproducirse, y el lugar dejado por la célula muerta lo ocupa una nueva célula, hija de la escogida, y por lo tanto de su misma especie.

A partir de este comportamiento tan simple podremos observar como el caos inicial, en el que las células de ambas especies se hallan mezcladas, da paso a una forma de organización en la que las células de una misma especie forman amplios grupos. que se desplazan, se estiran y se contraen mientras tratan de sobrevivir.

Si se deja el programa funcionando durante un tiempo una de las especies pasa a ser dominante, pudiendo llegar a hacer desaparecer a la otra especie.

Finalmente, y como curiosidad, podríamos pensar en realizar en cada ciclo la reproducción de las células de un modo algo más inusual...

¿Qué ocurriría si al reproducirse una célula para ocupar el espacio vacío dejado por otra célula muerta, tuviera una hija de la otra especie, y no de la suya propia? ¿Seguiría produciéndose la homogeneidad, o el caos inicial se extendería hasta el infinito? A partir del código fuente del programa, y realizando una pequeña modificación se puede resolver esta trascendental duda.

[ Volver al Indice ]


4.3.- Hormigas y Plantas

Hormigas y Plantas es un programa que requiere de una cierta justificación para considerarse como autómata. Para ello se distinguirán varios tipos de autómtas en función de su objetivo. Esta discusión continúa en la sección Discretización del tiempo en los autómatas del documento "Autómatas como analogías de nuestro Universo"

[ Volver al Indice ]


4.3.1.- Introducción a los tipos de autómatas

Inspirados en los primeros autómatas (como el juego de la vida de Conway), en los últimos años han surgido multitud de modelos, por lo general implementados en programas software, que intentan o bien resolver un determinado tipo de problemas, o bien representar lo más fielmente algún aspecto concreto de nuestro universo real o de cierto universo imaginario.

En cuanto a los autómatas que tratan de resolver un problema determinado, probablemente los más numerosos sean los compiladores, analizadores léxicos, sintácticos o semánticos, en definitiva, traductores de algún tipo. Estos autómatas son capaces de leer una secuencia de símbolos escrita de acuerdo a una norma o gramática, generando como salida otra secuencia ajustada a otra gramática diferente. La entrada puede ser un texto en castellano, un programa escrito en lenguaje C o un fichero de datos con una determinada estructura (por ejemplo, cierta cabecera, cuerpo y pie). La salida correspondiente podría ser entonces el texto en holandés, el programa de ordenador en lenguaje Lisp u otro fichero de datos con una composición diferente. Otro tipo de autómatas que están siendo muy utilizados son las Redes Neuronales Artificiales, sobre todo en aplicaciones de clasificación (reconocimiento) y predicción.

Dentro del segundo grupo de autómatas, más orientados hacia la representación y la simulación que hacia la resolución, hay un gran subgrupo de autómatas que pretenden nada menos que la simulación de los procesos de la vida. Entre ellos se encuentra el programa "Hormigas y Plantas".

[ Volver al Indice ]


4.3.2.- Hormigas y Plantas como autómata

En el programa "Hormigas y Plantas", cada una de las celdas de la rejilla en 2 dimensiones es un autómata simple con los siguientes estados posibles:

- Vacío
- Ocupado por una hormiga
- Ocupado por una planta
- Ocupado por un obstáculo

Cada celda cambia de estado en función del estado de las celdas vecinas. Por ejemplo, una celda en estado "planta" pasa a estado "vacío" si hay una hormiga próxima a la planta: la hormiga se come la planta. Otros cambios de estado están supeditados además al resultado de una función pseudoaleatoria uniforme, y se producen, si se cumplen las otras condiciones, según una cierta probabilidad. Por ejemplo, una celda en estado "vacío" pasa a estado "hormiga" sólo si hay una hormiga próxima a la planta y además con una cierta probabilidad (solo si la hormiga "decide" tomar esa dirección).

El estado de cada celda puede estar definido por distintas variables: las hormigas, así como las plantas, poseen una cierta cantidad de energía. Pero además, las hormigas poseen una inercia en cuanto a la dirección del movimiento, que provoca una tendencia a moverse en la misma dirección, y un "tipo", ya que hay hormigas "rojas", "rosas", "naranjas", "amarillas" y "verdes" que corresponden con distintas probabilidades de moverse, regar, pelearse o reproducirse.

En este autómata, los cambios de estado están dirigidos únicamente por las "hormigas", de forma que la "ejecución" de una hormiga provoca un cambio de estado en sí misma y en otras posibles celdas de tipo "planta". Este último punto lleva a la posibilidad de contemplar el programa desde otro punto de vista: como un conjunto de autómatas simples móviles cuyo estado se define, entre otros, por su posición en los ejes X e Y. Es decir, en vez de ver una rejilla cuyas celdas cambian de estado, vemos un conjunto de hormigas que se mueven por unos ejes cartesianos. Efectivamente, el autómata no se ha programado como un conjunto de celdas con distintas propiedades, sino como varios conjuntos (o varios autómatas superpuestos): un conjunto de hormigas, otro de plantas y otro de obstáculos, controlando que cualquiera de ellos no exista en la misma posición que otro.

[ Volver al Indice ]


4.4.- Los mundos de Pixel

Los mundos de Pixel son un conjuto de autómatas celulares desarrollados en JavaScript. La mayoría de ellos utilizan las reglas de replicación RS y SR de René Reynaga rene@umsanet.edu.bo y B. Sandi.

[ Volver al Indice ]


5.- Bajar código fuente

En estas páginas se ofrece:

Estos programas y sus ficheros fuente son gratis y de libre distribución. El código fuente está disponible y puede ser modificado, distribuido, o utilizado en otros programas citando al autor o autores.

Se ven mejor con Netscape

Programa

Descripción

Imágenes

accl2.html

Autómata Celular Circular Lineal (1 Dimensión)
RS y SR de 2 estados, 2 vecinos mediante Html autogenerado

X X X

accl3.html

Autómata Celular Circular Lineal (1 Dimensión)
RS y SR de 3 estados, 2 vecinos mediante Html autogenerado

accm2.html

Autómata Celular Circular Matricial (2 Dimensiones)
RS y SR de 2 estados, 8 vecinos mediante Html autogenerado

X X X

Pulse aquí para bajar el código fuente.

[ Volver al Indice ]

[ Home Page Castellano | Home Page English ]
Traduccion