Evolucionando autómatas celeulares
con algoritmos genéticos
En esta sub-unidad, voy a hablar acerca de un proyecto
en el que trabajé durante varios años
con Jim Crutchfield
de quien ya han oido hablar antes, y
Rajanhi Das quien está en el Centro de Investigaciones de IBM
Este fue un proyecto sobre evolución
de autómatas celulares con algoritmos genéticos
para realizar "computación colectiva"
He colocado el enlace a este artículo,
con una revisión reciente del trabajo,
en la página de materiales para el curso
Se trata de una tarea computacional particular para autómatas celeulares
Una que fue originalmente propuesto
por Norman Packard
La tarea es diseñar un autómata celular
que decide cuando si o cuando no
la configuración inicial de las células
presenta mayoría de células negras
Entonces, aquí en la imagen
Aquí está una configuración inicial para
un autómata celular de una dimensión
donde hay uno, dos, tres, cuatro, cinco, seis,
siete, ocho, nueve, diez, once celdas
y seis de ellas son negras
Entonces, hay una mayoría de celdas negras
El comportamiento deseado sería que,
despuésde un número de pasos de tiempo,
toda la rejilla se volviera negra
De manera similar, si se inicia con mayoría de
celdas blancas, lo que se desea es que la rejilla
se volviera blanca en los siguientes pasos de tiempo
Esta es una tarea computacional
simple de describir, pero variantes de la misma
tienen importantes aplicaciones en la computación
particularmente en el campo de la computación distribuida
Entonces, la pregunta es
¿Cómo diseñamos un autómata celular
para hacer esto? Bueno, un punto por realizar es que
si se tiene una computadora estándar o tradicional,
que tiene una unidad central de procesamiento
y memoria de acceso aleatorio
no es difícil diseñar un programa para
definir si se tiene una mayoría negra
o una mayoría blanca almacenada en las celdas,
en algún lugar en la memoria
Todo lo que se tendría que hacer es escribir un programa que
vaya a esas localidades de memoria,
cuente el número de celdas negras,
mediante un contador centralizado
y memoria central para guardar
la cuenta, y definir qué proporción es mayor
Pero, recordemos que los autómatas celulares
no tienen ningún control central
ni tampoco ninguna memoria de acceso aleatorio
Todo lo que tiene son celdas o "células" individuales
que se encuentran conectadas a sus vecinas
Entonces, no está del todo claro
cómo diseñar un autómata celular
para realizar esta tarea
Como ya se discutió antes,
hay 256 autómatas celulares elementales
Sabemos lo que todos ellos hacen,
cómo es que se comportan y sabemos
que ninguno de ellos hace estas tareas
Como resultado, los autómatas celulares
donde cada célula tiene cuatro vecinos,
con los dos vecinos más cercanos de cada lado
tampoco realizan esta tarea
Entonces, vemos un autómata celular
en el que cada célula tiene seis vecinos:
los tres vecinos más cercanos de cada lado
La tabla con la regla para este tipo
de autómata celular nos da todas
las posibles configuraciones de vecinos
de siete celdas y especifica,
para cada configuración, cuál es el estado siguiente
que debería tener la célula o celda central en
el siguiente paso de tiempo
Ahora, un rápido cuestionario,
Nuestro cuestionario tiene dos preguntas
Ámbas son preguntas nunéricas y espero
que estén listos para esto
La primera pregunta es
para un autómata celular como este
con vecindario de siete células
¿cuántas posibles configuraciones
de vecindarios existen?
Y, la segunda pregunta es
¿cuántas tablas diferentes de reglas
para el autómata celular existen con
vecindarios de siete células?