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