Recordemos que la meta es diseñar
un autómata celular que
tome una configuración inicial
con una mayoría de blancas y
eventualmente termine con todas en blanco
o, vice versa, todas a negras
Una solución, en la que se podría pensar,
es realizar un conteo local y determinar la mayoría
en cada vecindario de siete células
Así, si la mayoría de las células en
un vecindario son blancas
entonces, la célula central debería cambiar a blanco
y, similarmente, para las blancas
Como sea, si miramos el comportamiento
de un autómata celular
este, de hecho, no realiza esta tarea
Aquí tenemos una rejilla de una dimensión
dispuesta en forma horizontal
el tiempo cero inicia aquí, a la derecha, y
se puede ver la configuración inicial
aleatoria y, muy rápidamente,
las áreas con mayoría negra van al negro
y las áreas con mayoría blanca
van al blanco
pero hay una frontera entre ellas
porque aquí tenemos cuatro negras y
tres blancas junto a tres negras
y cuatro blancas y estas sólo permanecen negras
y una frontera blanca atravesando
el resto del tiempo
Entonces, el problema es que no hay forma de que,
digamos, este segmento mayoritario negro
se comunique con este otro segmento negro
y se procese la información combinada de,
digamos, todos los diferentes segmentos
que juntos lograrían una mayoría
en todala rejilla.
Entonces, nuestro reto es diseñar
un autómata celular que pueda tomar información
de áreas locales y comunicarlas
a través de la rejilla
para tener esa información combinada.
Entonces, conforme toda la rejilla
puede decidir en forma colectiva cuándo
hay mayoría, mayoría absoluta,
de blancas o negras.
Esto se vuelve no trivial.
En vez de diseñar esto nosotros mismos,
lo que vamos a hacer es usar
un algoritmo genético para evolucionar
autómatas celulares para tener el comportamiento deseado
Entonces, esto va a ser familiar
después de haber visto el ejemplo del algoritmo genético
de Robby, el robot, porque
esto tiene mucho en común
Repasemos el algoritmo genético de nuevo
Vamos a crear
una población inicial de posibles reglas
para el autómata celular
La aptitud de cada autómata celular
es la medida de qué tan bien se desempeña
la tarea de clasificar las mayorías
La aptitud del autómata celular le permite reproducirse,
mediante cruza y con mutaciones
Y se continúa este proceso
por muchas generaciones
Entonces, ya hemos visto esto antes
Recuerden que la secuencia de DNA de Robby representaba a su estrategia
De manera similar, la secuencia de DNA de un autómata celular
codifica su tabla de reglas
Entonces, si tenemos una tabla de reglas que luce como esta,
asignamos un cero a cada celda blanca
y un uno a cada celula negra
Y esta lista de 128 unos y ceros
es la secuencia de DNA que vamos a evolucionar
Entonces, creamos una población de cadenas aleatorias
que representan las tablas de reglas del autómata celular.
Entonces, cada una de estas cadenas
es una lista de 128 bits, o unos y ceros.
Aquí tenemos un ciento de candidatos
pero cada quien puede decidir el tamaño de la población
que debería ser usada
Vamos a calcular la aptitudde una regla
y la forma de hacerlo es similar a lo que hicimos con Robby
Creamos varios y diferentes escenarios
y probamos la regla en cada uno de ellos
Los escenarios aquí
van a ser
configuraciones iniciales de la rejilla
y la aptitud de una regla es la proporción
de clasificaciones correctas
Entonces, recordemos que cuando digo regla
en realidad quiero decir tabla de reglas, de tal manera que una regla
se compone de esos 128 estados de actualización
que indican al autómata celular cuál es
estado que debería tener la celda (o célula) central
en cada una de las posibles combinaciones de vecindario
Entonces, aquí está un diagrama que muestra
cómo trabaja esto
Para cada autómata celular en la población
existe una de estas reglas
Se crea la tabla de reglas que corresponde a esto
Aquí está de nuevo, y ahora voy a ejecutar
el autómata celular correspondiente
usando esta regla con muchas
configuraciones iniciales de rejilla
Entonces, aquí está una configuración inicial
y esta es actualizada de acuerdo a la regla
Designamos algún número máximo de
pasos de tiempo para que estas actualizaciones
tengan lugar
y si el comportamiento del autómata celular,
al terminar los pasos de tiempo,
no es la respuesta correcta,
digamos, una mayoría
de celdas negras entonces debería haber puras celdas negras
Pero si no, esta se clasifica como incorrecta
No se da puntuación parcial
para algún número de celdas negras
Sólo puede ser correcto o incorrecto
Este es incorrecto
Este otro es de hecho correcto, después de
una mayoría de celdas blancas y dentro del
número máximo de pasos de tiempo
llega a puras celdas blancas y así.
La aptitud es justamente la fracción que
corresponde a las clasificadas como correctas
Entonces, la aptitud se encuentra entre cero y uno.
Ahora, veamos cómo trabaja el algoritmo
Tenemos una población de
tablas de reglas aleatorias para autómata celular
Ahora, supongamos que la aptitud ha sido
calculada como sigue
¿Qué pasa las reglas más aptas
son seleccionadas para reproducirce entre sí?
Por ejemplo, deberíamos elegir la regla uno
y la regla tres como padres
Crearíamos una nueva generación
Mediante cruza y mutación
cada par de padres se
cruzaría en un punto elegido en forma aleatoria
y el hijo tomaría la primera parte
de un padre
y la segunda parte
del segundo padre
y viceversa
Entonces, aquí estamos creando dos hijos
por cada dos padres
Debemos realizar algunas mutaciones aleatorias
Si este dígito es elejido para mutar
este debería cambiar a cero
Y, ahora, tenemos dos hijos
Y continuamos este proceso
de seleccionar padres y crear hijos
hasta que una nueva generación está completa
Entonces, calculamos la aptitud de
la nueva generación y, así, sucesivamente.
manteniendo la iteración por muchas generaciones.
Cuando el algoritmo genético termina,
realmente estamos en la misma situación
que cuando estábamos en el ejemplo del robot Robby
El algoritmo genético nos ha dado
una cadena de bits, 128 bits
y dice que tiene una aptitud alta
Pero ahora nos quedamos con la tarea
de tratar de entender por qué trabaja