Para evolucionar estrategias con un algoritmo genético debemos codificarlas de tal forma que el algoritmo genético pueda usarlas
así que aquí es como esto funciona. Recuerden aquí está nuestro ejemplo de la estrategia con todas las situaciones posibles
representadas y una acción dada para cada situación posible.
Lo que podemos hacer ahora es tomar la lista de acciones y recordar el orden de las 243 situaciones posibles
ahora cortamos la lista de acciones y recuerden que la primer acción corresponde a la primer situación, que es, todo vacío
la segunda acción corresponde a la segunda situación donde todo está vacío excepto la lata en el sitio actual y así..
ahora podemos tomar esa lista de acciones y codificarlas de acuerdo a un código numérico. Voy a darle a cada acción un número
que es su código numérico de 0 a 6. Entonces puedo codificar esta estrategia particular sustituyendo
el código numérico por cada una de las acciones en la lista. Ahora, un cero aquí, en esta primera posición significa que la primera situación que es todo vacío
corresponde a la acción "mover al norte". Un 6 aquí significa que la tercer situación, cualquiera que sea esta en nuestra lista ordenada, corresponde a la acción "Mover aleatoriamente"
y así...Y de esta manera tenemos una lista de números que representa una estrategia específica. Cuando Robby ejecuta una acción
mira alrededor de su situación, recuerda el ordenamiento de las situaciones posibles y piensa por ejemplo " oh estoy en la situación- por ejemplo- 201"
luego busca por la entrada 201 en esta lista, busca a qué corresponde el código en términos de una acción, y ejecuta esa acción
Y vuelve a hacer eso una y otra vez. Así es como codificamos una estrategia
puedes pensar en esta estrategia en un sentido metafórico como el ADN de Robby. Esto es lo que va a evolucionar: esta lista de números
y por supuesto que esta lista de números tiene 243 valores. Si quieres pensar en cada uno de estos números como un gen particular puedes decir
que Robby tiene 243 genes. Por supuesto que la analogía con la genética no tiene que ser exacta, es algo así como una concepción general
ok ahora aquí está una pregunta: ¿Cuántas estrategias posibles hay ahí?
dada esta representación...Queremos encontrar una buena estrategia pero la pregunta es ¿cuántas habrán que pasar para encontrar una buena?
o podemos preguntar ¿cuántas posibles hay? Bueno, si vemos a las 243 diferentes posiciones y cada posición tiene 7 acciones posibles
porque tenemos los números que van de 0 a 6 que podrían ir aquí. Entonces el número total de estrategias posibles es 7x7x7
para cada número posible que podamos poner en cada posición 243 veces.
entonces la respuesta es el gran número 7 elevado a la potencia 23!
el cual es uno de esos números astronómicos que puedes esperar nunca ver en tu vida o en la vida completa del universo completo
este es un número imposible. Nadie podría buscar todas las estrategias posibles dentro de este número
y la meta aquí es tener un algoritmo genético, buscar inteligentemente en este vasto espacio para una buena estrategia
ahora, estamos finalmente listos para averiguar cómo usar un algoritmo genético para evolucionar estrategias
así que lo primero que vamos a hacer, es generar 200 estrategias aleatorias. El número 200 sólo es arbitrario, lo acabo de escoger
..un cierto número de estrategias completamente aleatorias, esa será nuestra población inicial de estrategias
Aquí está una lista que corrí, cuando corrí el AG generé 200 individuos, donde cada individuo es una una estrategia..es una secuencia
de 243 números donde cada número está entre 0 y 6...así que se puede ver que son aleatorios.
ahora vamos a calcular que tan buena o no es cada estrategia, haciendo a Robby usar esa estrategia para llevar a cabo varias acciones en su mundo
el cual está lleno de latas de soda vacías.
y lo que voy a llamar "ambiente" es una configuración particular de latas vacías de soda en su mundo
y para empezar podemos poner latas vacías de soda en lugares de forma aleatoria
luego dejamos a Robby que obedezca una estrategia en particular para cierto número de acciones que pueda ejecutar
calculamos sus recompensas menos las penalidades y hacemos lo mismo para un entorno diferente, una configuración diferente de las latas
hacemos esto muchas veces y la aptitud de una estrategia en particular es el promedio de las recompensas
menos las penalidades, sobre todos los entornos puestos.
Para este punto hemos calculado la aptitud de forma separada para 243 estrategias y ahora viene la parte de los empates
donde se empatan y crean una descendencia...vía "recombinación sexual", por supuesto entre comillas porque
se trata de cadenas y números dentro de una computadora con mutaciones aleatorias
Entre más aptos sean los "padres" más "hijos" o retoños pueden crear. Así que lo que hacemos es escoger dos "padres" aptos
los escogemos probabilísticamente con los más aptos como más probables para ser escogidos
ahora voy a crear un hijo escogiendo un punto aquí, en las cadenas, para separarlos y el retoño o el hijo va a obtener esta primera parte de su padre 1 y esta de su otro padre 2.
ok? Hice al hijo copiando parte del padre 1 otra parte del padre 2...para crear al hijo.
y luego el hijo puede mutar aleatoriamente, escogiendo algunas posiciones aleatorias y cambiándolas por números aleatorios entre el 0 y 6
así que sólo se cambian algunos números aleatoriamente y ahora tenemos a nuestro hijo. Y continuamos haciendo esto una y otra vez
hasta que tengamos una nueva generación de hijos. La vieja generación se muere completamente
Ahora hay que empezar otra vez en el paso 2 con la nueva generación, y hacemos esto por muchas generaciones hasta que estemos a gusto con la estrategia que el AG encontró o hasta que
estemos hartos de correrlo. Quiero puntualizar que el máximo número de estrategias aptas es como de 500.
Eso es porque hay 100 cuadrados en total en el mundo de Robby. Y cada vez que Robby empieza en cada ambiente hay 50 latas.
Eso es alrededor de la mitad de los sitios en los que hay latas.
Algunas veces es menos de 50 otras arriba de 50 por la aleatoriedad pero en promedio son 50
y cada lata vale 10 puntos y entonces el número máximo de puntos que puede obtener en un entorno Robby es de 500.
Antes de correr el AG, diseñé mi propia estrategia a mano la cual fue la estrategia más simple y razonable en la que pude pensar
esta es: si hay una lata en el sitio actual, recógela. De otra forma si hay una lata en los sitios adyacentes
muévete a ese sitio. De otra forma, escoge otra dirección aleatoria para moverte.
Implementé esa estrategia como una cadena de 243 valores, escribí un programa para hacer eso. Luego dejé que Robby usara esa estrategia para
recolectar latas en un número de entornos distintos y tomé su puntuación promedio (de los diferentes ambientes usados) y
el promedio de su aptitud fue 346 de 500 posibles como máximo. OK.. no estuvo tan mal
Pero luego he implementado el AG y lo corrí, así como les expliqué y encontré que el promedio de aptitud (de la estrategia evolucionada) fue 486 ...Casi perfecto!
La pregunta entonces fue ¿Porqué el AG está haciéndolo mejor que yo? ¿Qué hace su estrategia que es mejor que la mía?
Esta es una pregunta no trivial para contestar. Sé la lógica detrás de mi estrategia, pero el AG
al final de su corrida arroja una cadena de 243 números y dice aquí está mi estrategia...esta funciona bien y tiene un alto nivel de aptitud
pero es difícil para nosotros ver cómo funciona...es análogo a lo que pasa en el genoma humano..sabemos que el genoma humano es secuenciado, sabemos
cuál es la secuencia, pero hay un gran salto entre saber qué es la secuencia y saber cómo es que funciona. Cómo es su funcionalidad.
¿Cómo es que los diferentes genes originan diferentes funciones? Así que al ver la estrategia del AG, primero grafiqué la primer corrida del AG...grafiqué la mejor aptitud en la población
como función de generaciones. En tanto el tiempo avanza, veamos cómo la aptitud del mejor individuo en la población mejoran
Esta es la versión que he implementado en el lenguaje de programación C. Ustedes podrán usar la versión que implementé en Net Logo, muy pronto.
Pero esa es relativamente lenta, por eso corrí esta versión de C para obtener estos resultados. Pueden ver que en la primera generación la aptitud es muy baja
está por debajo de cero, es negativa y veremos porqué en un minuto. Pero muy rápido, el mejor individuo en la población empieza a tener más y más aptitud
y ustedes saben que en cada generación, la población total empieza de cero nuevamente, así que estos individuos son distintos en cada generación
La aptitud se mantiene por un tiempo en esta parte
y luego hay un salto agudo, y luego otro salto abrupto hasta que alcanza otra parte plana y hay otro salto y luego otra parte plana
Todas estas pequeñas variaciones ocurren porque la función de aptitud tiene cierta aleatoriedad en ella porque las latas se generan aleatoriamente
las latas siempre son el mismo número (50)...y la disposición de latas varía de entorno en entorno, entonces...
se obtienen diferentes niveles de aptitud incluso para el mismo individuo en diferentes generaciones porque se prueban en diferentes configuraciones de latas