Un ejemplo práctico de un algoritmo genético
Una de las mejores cosas sobre el aprendizaje automático es que existen muchos enfoques diferentes para resolver problemas. Las redes neuronales son excelentes para encontrar patrones en los datos, lo que resulta en capacidades predictivas que son realmente impresionantes. El aprendizaje por refuerzo utiliza conceptos basados en recompensas, que mejoran con el tiempo. Y luego está el enfoque llamado algoritmo genético .
Un algoritmo genético (AG) usa principios de la evolución para resolver problemas. Funciona utilizando una población de soluciones potenciales a un problema, seleccionando y seleccionando repetidamente los candidatos más exitosos hasta que la solución definitiva emerge después de varias generaciones.
Para demostrar cuán efectivo es este enfoque, lo utilizaremos para resolver un problema. problema complejo: la creación de una estrategia para el juego de casino Blackjack (también conocido como “21”).
El término “estrategia” en este caso significa una guía para las acciones de los jugadores que cubre todas las situaciones . El objetivo es encontrar una estrategia que sea lo mejor posible, dando como resultado ganancias maximizadas a lo largo del tiempo.
Acerca de esta Estrategia “Ganadora”
Por supuesto, en realidad no existe una estrategia ganadora para Blackjack: el Se establecen reglas para que la casa siempre tenga una ventaja. Si juegas el tiempo suficiente, perderás dinero .
Sabiendo que la mejor estrategia posible es la que minimiza las pérdidas. El uso de tal estrategia permite a un jugador estirar un bankroll lo más posible mientras espera una buena racha de buena suerte a corto plazo. Esa es realmente la única forma de obtener ganancias en Blackjack.
Como puedes imaginar, Blackjack ha sido estudiado por matemáticos e informáticos durante mucho, mucho tiempo. En la década de 1960, un matemático llamado Edward O. Thorp escribió un libro llamado Beat the Dealer que incluía gráficos que mostraban la estrategia “básica” óptima.
La estrategia óptima parece algo como esto:
Las tres tablas representan una estrategia completa para jugar Blackjack.
La mesa alta de la izquierda es para manos duras la de arriba la derecha es para manos suaves y la tabla en la parte inferior derecha es para pares .
Si no está familiarizado con el Blackjack, una mano suave es una mano con un As que puede contar como 1 u 11, sin que el valor total de la mano exceda a 21. Un par se explica por sí mismo, y una mano dura es básicamente todo lo demás, reducida a un valor total de la mano.
Las columnas a lo largo de la parte superior de las tres Las mesas son para el revendedor, lo que influye en la estrategia. Tenga en cuenta que los rangos de las cartas superiores no incluyen a Jack, Queen o King. Esto se debe a que todas las cartas cuentan como 10, por lo que todas se agrupan junto con las Diez (“T”) para simplificar las tablas.
Para usar las tablas, un jugador primero debe determinar si tiene un par, mano suave o mano dura, luego mire en la tabla correspondiente usando la fila correspondiente a su posición de la mano y la columna correspondiente a la carta ascendente del distribuidor.
La celda en la tabla será “H” cuando la estrategia correcta es golpear, “S “Cuando la estrategia correcta es pararse,” D “para doblar, y (solo en la tabla de pares)” P “para dividir.
Conocer la solución óptima para un problema como este es realmente muy útil. La comparación de los resultados de una AG con la solución conocida demostrará cuán efectiva es la técnica.
Finalmente, hay otra cosa que evitar antes de continuar, y esa es la idea de no determinismo . Eso significa que si el mismo código GA se ejecuta dos veces seguidas, se devolverán dos resultados diferentes. Eso es algo que sucede con los algoritmos genéticos debido a su aleatoriedad inherente. Es inusual que el software actúe de esta manera, pero en este caso es solo una parte del enfoque.
Cómo funciona un algoritmo genético
Los algoritmos genéticos son divertidos de usar porque son muy fáciles de entender: comience con una población de (inicialmente, completamente aleatorias) soluciones potenciales, y luego deje que la evolución haga su trabajo para encontrar una solución.
Ese proceso evolutivo se basa en la comparación de soluciones candidatas. Cada candidato tiene un puntaje de condición física que indica lo bueno que es. Ese puntaje se calcula una vez por generación para todos los candidatos y se puede usar para compararlos.
En el caso de una estrategia de Blackjack, el puntaje de condición física es bastante sencillo: si juegas N manos de Blackjack con la estrategia , cuanto dinero tienes cuando termines? (Debido a la ventaja de la casa, todas las estrategias perderán dinero, lo que significa que todas las puntuaciones de condición física serán negativas. Una puntuación más alta de condición física para una estrategia simplemente significa que perdió menos dinero que otras.)
Una vez que una función de condición física efectiva es creada, la siguiente decisión cuando se usa una AG es cómo hacer la selección.
Hay varias técnicas de selección diferentes para controlar cuánto se maneja una selección según el puntaje de condición física frente a la aleatoriedad. Un enfoque simple se llama Selección de torneos y funciona seleccionando N candidatos aleatorios de la población y utilizando el que tiene el mejor puntaje de condición física. Es simple y efectivo.
Una vez que se seleccionan dos padres, se cruzan para formar un niño. Esto funciona igual que la reproducción sexual regular: el material genético de ambos padres se combina. Dado que los padres fueron seleccionados teniendo en cuenta la aptitud física, el objetivo es transmitir los elementos exitosos de ambos padres.
Naturalmente, en este caso, el “material genético” es simplemente 340 células de las tres tablas que tiene cada estrategia. Una celda en el niño se llena al elegir la celda correspondiente de uno de los dos padres. A menudo, el cruce se realiza de manera proporcional a las puntuaciones relativas de condición física, por lo que uno de los padres podría terminar aportando muchas más celdas de la tabla que el otro si tuviera una puntuación de aptitud física significativamente mejor.
Finalmente, al igual que en la naturaleza, es importante tener diversidad en una poblacion Las poblaciones que son demasiado pequeñas o demasiado homogéneas siempre tienen un desempeño peor que las poblaciones más grandes y más diversas.
La diversidad genética es importante, porque si no tienes lo suficiente, es fácil quedar atrapado en algo llamado mínimo local que es básicamente una solución que funciona mejor que cualquier otra alternativa similar, pero es inferior a otras soluciones que son significativamente diferentes a ella.
Para evitar ese problema, los algoritmos genéticos a veces usan mutación (la introducción de material genético completamente nuevo) ) para mejorar la diversidad genética, aunque las poblaciones iniciales más grandes también ayudan.
Resultados utilizando una AG
Una de las cosas interesantes de las AG es simplemente observar cómo evolucionan una solución. La primera generación está poblada con soluciones completamente aleatorias. Esta es la mejor solución (basada en el puntaje de condición física) de 750 candidatos en la generación 0 (la primera generación aleatoria):
Como puede ver, es completamente aleatorio. Para la generación 12, algunas cosas están comenzando a tomar forma:
Con solo 12 generaciones de experiencia, las estrategias más exitosas son aquellas que soportan 20, 19, 18 y posiblemente 17. Esa parte de la estrategia se desarrolla primero porque Sucede tan a menudo y tiene un resultado bastante claro. Los conceptos básicos se desarrollan primero con los AG, con los detalles que vienen en generaciones posteriores.
Los otros indicios de calidad en la estrategia son las tenencias de 11 duro y 10 duro. De acuerdo con la estrategia óptima, deberían ser en su mayoría Double-Down, por lo que es alentador ver tanto amarillo allí.
Las parejas y las mesas de manos suaves se desarrollan al final porque esas manos ocurren con poca frecuencia. A un jugador se le reparte un par solo el 6% del tiempo, por ejemplo.
En la generación 33, las cosas comienzan a aclararse:
En la generación 100, la mesa de mano dura de la izquierda está completamente estabilizada, no es así. No cambies de generación en generación. Las tablas de mano suave y de pares se están volviendo más refinadas:
Y luego se usan las generaciones finales para refinar las estrategias. Los cambios de generación a generación son mucho más pequeños en esta etapa, ya que es realmente el proceso de resolver los detalles más pequeños.
Finalmente, la mejor solución encontrada en 237 generaciones:
Como puede ver, el resultado final no es exactamente lo mismo que la solución óptima, pero es muy, muy cerca. Las manos duras en particular (la tabla de la izquierda) son casi exactamente correctas. Las mesas de manos blandas y parejas tienen algunas celdas más que no coinciden, pero eso es probable porque esos tipos de manos ocurren mucho menos que las manos duras.
En términos de resultados, jugar la estrategia óptima para 500,000 manos a $ 5 por mano daría como resultado una pérdida de $ 176,040. Usar la estrategia generada por computadora resultaría en una pérdida de $ 176,538, una diferencia de $ 498 en más de medio millón de manos.
Hay un GIF animado que muestra la evolución de esta estrategia en 237 generaciones, pero consciente de que tiene 19 MB de tamaño, por lo que es posible que no desee verlo por teléfono.
El código fuente del software que produjo estas imágenes es de código abierto . Es una aplicación de escritorio para Windows escrita en C # con WPF.
Implicaciones combinatorias
A pesar de lo impresionante que es la estrategia resultante, debemos ponerla en contexto pensando en el alcance del problema. Una estrategia óptima para Blackjack se expresa al rellenar cada una de las 340 celdas de la mesa (repartidas en las tres mesas) con la mejor opción para cada combinación de cartas con cartas de crupier / repartidor, ya sea de pie, golpe, doble hacia abajo o dividida. En cuanto a combinaciones, hay 4¹⁰⁰ posibles estrategias de par, 3⁸⁰ posibles estrategias de mano suave y 3¹⁶⁰ posibles estrategias de mano dura, para un total de 5 x 10¹⁷⁴ posibles estrategias para Blackjack:
4¹⁰⁰ x 3⁸⁰ x 3¹⁶⁰ = 5 x 10¹⁷⁴ posible Estrategias de blackjack
En este caso, el algoritmo genético encontró una solución casi óptima en un espacio de solución de 5 x 10¹⁷⁴ respuestas posibles. Ejecutándose en una computadora de escritorio estándar, tardó unos 75 minutos. Durante esa ejecución, se evaluaron aproximadamente 178,000 estrategias.
Pruebas de aptitud física
Los algoritmos genéticos son esencialmente impulsados por funciones de aptitud física. Sin una buena manera de comparar candidatos entre sí, no hay manera de que el proceso evolutivo pueda funcionar.
La idea de una función de aptitud es simple. Si bien es posible que no sepamos la solución óptima a un problema, sí tenemos una manera de medir las posibles soluciones entre sí. La función de condición física refleja los niveles de condición física relativos de los candidatos que se le pasaron, por lo que los puntajes se pueden usar efectivamente para la selección.
A los efectos de encontrar una estrategia de Blackjack, una función de condición física es sencilla: es una función que devuelve lo esperado ganancias finales después de usar la estrategia en un cierto número de manos.
¿Pero cuántas manos son suficientes?
Resulta que es necesario jugar muchas manos con una estrategia para determinar su calidad. Debido a la aleatoriedad innata de un mazo de cartas, es necesario jugar muchas manos para que la aleatoriedad se iguale entre los candidatos.
Esto es especialmente importante cuando nuestra AG se acerca a una solución final. En las primeras generaciones, no es un problema si los puntajes de condición física no son exactos, porque la diferencia entre un mal candidato y un buen candidato suele ser bastante grande y la convergencia a la solución final continúa sin problemas.
Sin embargo, una vez que GA se adentra en las generaciones posteriores, las estrategias candidatas que se comparan tendrán solo pequeñas diferencias, por lo que es importante obtener las ganancias esperadas y precisas de una función de aptitud.
Por suerte, es bastante sencillo encontrar el número correcto de manos necesarias. Usando una única estrategia, se ejecutan múltiples pruebas, lo que resulta en un conjunto de puntuaciones de condición física. Las variaciones de una carrera a otra para la misma estrategia revelarán cuánta variabilidad existe, que se debe en parte a la cantidad de manos probadas. Cuanto más manos se jueguen, más pequeñas serán las variaciones.
Al medir la desviación estándar del conjunto de puntajes, obtenemos una idea de cuánta variabilidad tenemos a través del conjunto para una prueba de N. manos. Pero a medida que experimentamos con diferentes números de manos jugadas por prueba, no podemos comparar las desviaciones estándar, por la siguiente razón:
La desviación estándar se escala a los datos subyacentes. No podemos comparar las puntuaciones de condición física (o las desviaciones estándar de las mismas) de las pruebas que usan diferentes números de manos porque una mayor cantidad de manos jugadas da como resultado un aumento correspondiente en la puntuación de condición física.
Dicho de otra manera: digamos que una estrategia gana 34 % del tiempo. Si lo ejecutas para 25,000 manos contra 50,000 manos, tendrás diferentes totales al final. Es por eso que no puede simplemente comparar las puntuaciones de condición física que resultan de diferentes condiciones de prueba. Y si no puede comparar los valores sin procesar, no puede comparar las desviaciones estándar.
Resolvemos esto dividiendo la desviación estándar por el puntaje promedio de condición física para cada uno de los valores de prueba (el número de manos jugadas, que es). Eso nos da algo llamado coeficiente de variación que puede compararse con otros valores de prueba, independientemente del número de manos jugadas.
La tabla aquí muestra cómo la variabilidad se reduce a medida que jugamos más manos. :
Hay un par de observaciones de la tabla. Primero, las pruebas con solo 5,000 o 10,000 manos no son suficientes. Habrá grandes cambios en los puntajes de condición física informados para la misma estrategia en estos niveles. De hecho, parece que un mínimo de 100,000 manos es probablemente razonable, porque ese es el punto en el que la variabilidad comienza a aplanarse.
¿Podríamos correr con 500,000 o más manos por prueba? Por supuesto. Reduce la variabilidad y aumenta la precisión de la función de fitness. De hecho, el coeficiente de variación para 500,000 manos es 0.0229, que es significativamente mejor que 0.0494 para 100,000 manos. Pero esa mejora es definitivamente un caso de rendimientos decrecientes: el número de pruebas tuvo que aumentarse 5 veces solo para obtener la mitad de la variabilidad.
Dados esos hallazgos, la función de aptitud para una estrategia tendrá que jugar al menos 100,000 manos de Blackjack , usando las siguientes reglas (comunes en los casinos del mundo real):
- Usando 4 barajas de cartas barajadas juntas
- Se requiere que el crupier golpee hasta que tenga 17 (blando o duro)
- Puedes doblar una mano que se divide
- No hay seguro
- Blackjack paga 3: 2
Configuraciones de algoritmo genético
Uno de los aspectos inusuales para trabajar con una AG es que tiene tantas configuraciones que deben configurarse . Los siguientes elementos pueden configurarse para una ejecución:
- Tamaño de la población
- Método de selección
- Tasa de mutación e impacto
- Condiciones de terminación
La variación de cada uno de estos da diferentes resultados. La mejor manera de establecer los valores para estos ajustes es simplemente experimentar.
Tamaño de la población
Aquí hay una tabla de la idoneidad del candidato promedio por generación para los diferentes tamaños de población:
El eje de esta tabla es el número de generación (con un máximo de 200), y el eje Y es el puntaje promedio de aptitud por generación. No se muestra que las primeras generaciones enfaticen las diferencias a medida que llegamos a las generaciones posteriores.
La línea blanca plana en la parte superior de la tabla es la puntuación de aptitud para la estrategia de línea de base óptima y conocida.
Lo primero es de notar que las dos poblaciones más pequeñas (que tienen solo 100 y 250 candidatos respectivamente, mostradas en azul y naranja) tuvieron el peor de todos los tamaños.
La falta de diversidad genética en esas poblaciones pequeñas da como resultado puntuaciones de aptitud final deficientes, junto con Con un proceso más lento de encontrar una solución. Claramente, tener una población lo suficientemente grande como para asegurar la diversidad genética es importante.
Por otro lado, no hay demasiadas diferencias entre las poblaciones de 400, 550, 700, 850 y 1000.
Esta es una situación similar para elegir el número de manos con las que realizar la prueba: si elige un valor demasiado pequeño, la prueba no es precisa, pero una vez que supera un cierto nivel, las diferencias son menores.
Métodos de selección
El proceso de encontrar buenos candidatos para el cruce se llama selección, y hay varias formas de hacerlo. La selección de torneos ya ha sido cubierta. Aquí hay otros dos enfoques:
Selección de rueda de ruleta selecciona candidatos proporcionales a sus puntuaciones de condición física. Imagine un gráfico circular con tres cuñas de tamaño 1, 2 y 5. La cuña con el valor 5 se seleccionará 5/8 del tiempo, la cuña con el valor 2 se seleccionará 2/8 del tiempo, y la cuña con valor 1 se seleccionará 1/8 del tiempo. Esa es la idea básica detrás de la selección de la ruleta. El tamaño de la cuña de cada candidato es proporcional a su puntuación de condición física en comparación con la puntuación total de todos los candidatos.
Uno de los problemas con ese método de selección es que a veces ciertos candidatos tendrán una puntuación de aptitud física tan pequeña que nunca serán seleccionados. Si, por suerte, hay un par de candidatos que tienen puntajes de aptitud física mucho más altos que los demás, pueden ser seleccionados de manera desproporcionada, lo que reduce la diversidad genética.
La solución es utilizar Selección Clasificado que trabaja clasificando a los candidatos por condición física, luego le da al peor candidato una puntuación, el siguiente peor puntuación, y así sucesivamente, hasta el mejor candidato, que recibe una puntuación igual al tamaño de la población. Una vez que se completa este ajuste de puntaje de condición física, se utiliza la selección de la rueda de la ruleta.
Aquí hay un gráfico que compara la condición física promedio por generación utilizando una variedad de métodos de selección:
Como puede ver, la selección de torneos converge en una solución óptima. Rápido: de hecho, cuanto mayor sea el tamaño del torneo, más rápido mejorará el puntaje de condición física promedio. Eso tiene sentido, porque si eliges 7 candidatos aleatorios y usas el mejor, la calidad va a ser mucho más alta que si haces lo mismo mientras eliges solo 2.
A pesar de que tuvo la mejoría inicial más rápida, el Tourney 7 termina produciendo los peores resultados. Eso tiene sentido, porque aunque el tamaño de un gran torneo resulta en una mejora rápida, también limita el conjunto genético a lo mejor. La diversidad genética necesaria se pierde y, a la larga, no se desempeña tan bien.
Las personas con mejor desempeño parecen ser el Torneo 2, el Torneo 3 y el Torneo 4. Dada una población de 700, estas cifras son buenas por mucho tiempo.
Elitismo
Hay otro concepto en los algoritmos genéticos llamado elitismo . Es la idea de que cuando se construye una nueva generación, primero se clasifica a la población por aptitud física, y luego se pasa un cierto porcentaje de los mejores candidatos directamente a la siguiente generación sin alteración. Una vez hecho esto, comienza el cruce normal.
Este cuadro muestra los efectos de cuatro tasas de elitismo diferentes (solo generaciones posteriores, para mostrar los detalles). Claramente, el elitismo o el 15% son razonables, aunque el 0% se ve un poco mejor.
Hay algo que sorprende de este cuadro: cuanto más alto era el elitismo, más lenta era la convergencia para la solución. Podría pensar que incluir deliberadamente lo mejor de cada generación aceleraría las cosas, pero en realidad parece que usar solo candidatos cruzados brinda los mejores resultados, y también es el más rápido.
Mutaciones
Mantener alta la diversidad genética es importante, y la mutación es una forma fácil de introducir eso.
Hay dos factores relacionados con la mutación: ¿con qué frecuencia ocurre y cuánto impacto tiene cuando ocurre?
A la tasa de mutación controla la frecuencia con la que se muta a un candidato de nueva creación. La mutación se realiza inmediatamente después de la creación a través de un cruce.
El impacto de la mutación controla cuánto se muta un candidato, en términos del porcentaje de sus células que se cambiarán al azar. Las tres tablas (manos duras, manos suaves y pares) se mutan en el mismo porcentaje.
Comenzando con una tasa de impacto fija del 10%, aquí están los efectos de diferentes tasas de mutación:
Está claro que la mutación no lo hace Ayuda para este problema: cuantos más candidatos se vean afectados por la mutación, peores serán los resultados. De ello se deduce que no es necesario probar diferentes valores de impacto de mutación: la tasa de mutación del 0% es claramente la mejor para este problema.
Condiciones de terminación
Saber cuándo abandonar un algoritmo genético puede ser complicado. Algunas situaciones requieren un número fijo de generaciones, pero para este problema, la solución fue buscar el estancamiento; en otras palabras, el algoritmo genético se detiene cuando detecta que los candidatos ya no mejoran.
La condición utilizada para esta prueba fue que si no hubo mejoras en la mejor estrategia general (o en el puntaje promedio de una generación) durante 25 generaciones seguidas, el proceso termina y el mejor resultado encontrado hasta ese momento se usa como la solución final.
Los algoritmos genéticos son una poderosa técnica para resolver problemas complejos, y tienen la ventaja de ser fáciles de entender. Para problemas con grandes espacios de solución debido a factores combinatorios, son extremadamente efectivos.
Para más información sobre GA, comience con este Artículo de Wikipedia o el Curso de PluralSight (pagado) Escribí que cubre el tema con mucho mayor detalle.
Ganar Blackjack usando Machine Learning se publicó originalmente en Hacia la ciencia de datos en Medio, donde las personas continúan la conversación resaltando y respondiendo a esto. historia