Jugar a EuroMillones con Algoritmos Genéticos
En un artículo anterior hablé del algoritmo genético y en esta ocasión vamos a resolver un problema usando ese algoritmo. El problema que elegí es como generar una combinación de números que sea más probable de ganar EuroMillones.
EuroMillones es una lotería que se juega en varios paises de Europa. El primer sorteo fue en el 2004 y cada semana hay 2 sorteos. Durante el sorteo se extraen 5 bolas de una máquina con 50 bolas númeradas seguido de 2 bolas que se extraen de otra máquina con 12 bolas numeradas. Por lo tanto, se juega con cinco números del 1 al 50 y dos números del 1 al 12 (estrellas de la suerte).
El objetivo de nuestro programa es encontrar una combianción de números que sea lo mas probable de ganar el sorteo usando los datos históricos de EuroMillones. Para lograr esto necesitamos lo siguiente:
- Una forma de representar las posibles soluciones del problema. En este caso la representación esta dada por el problema: un arreglo de 7 números, los primeros cinco deben de estar entre 1 y 50 y no repetirse entre ellos, los últimos dos son números distintos entre el 1 y el 12.
- Un función para evaluar nuestras soluciones. Sabiendo los datos historicos, ¿qué tan probable es que este grupo de números salga en el siguiente sorteo?
- Operadores genéticos que vayamos a utilizar.
El programa lo escribiré en python tratando siempre hacerlo lo más simple posible. Empezamos por escribir el algoritmo genético de una forma semi-abstracta:
Representación de la solución
Representar el juego de la lotería en un algoritmo genético es un problema sencillo, solamente hay que poner atención a 3 cosas:
- Cantidad de números con los que se juegan
- Valores mínimos y máximos
- Números repetidos
En EuroMillones se juega con 7 números:
\[s = [ a, b, c, d, e, x, y ]\]Para \(a,b,c,d,e\) se deben seleccionar cinco números diferentes entre el 1 y el 50. Para \(x,y\) se seleccionan dos números distintos entre 1 y el 12, a estos números se les llama estrellas. Por lo tanto para saber si una solucion es válida podemos escribir una función:
Generar problación inicial
Sabiendo como vamos a representar los boletos del EuroMillones, podemos crear aleatoriamente soluciones que cumplan con los requerimientos explicados en la sección anterior.
Un forma simple de hacerlo es simulando la forma en la que sacan las pelotitas en un sorteo. tenemos un conjunto de 50 números y otro de 12, seleccionamos 5 del primer conjunto aleatoriamente y 2 del segundo conjunto.
Para generar la población completa:
Evaluación de las soluciones
Esta es probablemente la parte más importante del programa. Saber que combinaciónes son más probables de ganar un sorteo es lo que va a guiar la búsqueda. Existen muchas teorías acerca de como ganar la lotería de los cuales se derivan diferentes formas para calcular las probabilidades. Yo no soy tan aficionado a los juegos de azar, pero tuve algunas ideas acerca de que combinaciones pueden ser mas probables de ganar.
- Los números que se han repetido recientemente, probablemente se vuelvan a repetir.
- Hay conjuntos de números que son improbables de salir seleccionados como por ejemplo 1,2,3,4,5,6,7.
- Tomando en cuenta el punto anterior, podriamos decir que hay conjuntos de números que tienen a salir más.
- De igual manera, es muy poco probable, que si ya salio un conjunto de números, este se repita en el corto plazo.
Usando estadistica Bayesiana podemos tratar de calcular la probabilidad de resulte ganador un conjunto de números. El teorema de Bayes propone un forma de calcular la probabilidad que ocurra un evento a partir de los resultados de algun otro evento. A esto se le conoce como probabilidad condicional.
Por lo tanto, la probabilidad de que ocurra un evento \(A\), dado que ocurrió \(B\), esta dado por:
\[P(A|B) = \frac{P(B|A) * P(A)}{P(B)}\]Usando esa formula podriamos calcular cual es la probabilidad de que salga el número 2 despues de que salió el 1 en un sorteo:
\[P(2|1) = \frac{P(1|2) * P(2)}{P(1)}\]Donde:
\[P(1) = P(2) = \frac{1}{50}\] \[P(1|2) = \frac{1}{50} * \frac{1}{49}\]Por lo tanto:
\[P(2|1) = \frac{1}{2,450}\]Pero si tenemos una muestra de los 104 últimos juegos (los juegos de las últimas 52 semanas), podemos calcular todas las probabilidades condicionales usando parejas de números basando las probailidades en los números que más han salido juntos. Los datos históricos de EuroMillones se pueden bajar de su página web en formato CSV. Tomando los cinco números por aparte de las estrellas, hay 10 formas de agrupar esos 5 números en pares. La probabilidad de que salga un par de números seleccionados en un sorteo se puede estimar contando cuantas veces ha salido \(N_1\), cuantas \(N_2\) y cuantas veces han salido juntos:
\[P(N_1,N_2) = \frac{\text{frecuencia}(N_1,N_2)}{\text{frecuencia}(N_2) + \text{frecuencia}(N_1)}\]Y si escogemos 5 números para un boleto de EuroMillones y queremos agrupar las probabilidades de que cada par de números salgan sorteados, podemos calcular el producto de la probabilidades de la siguiente forma:
\[f(\text{Solución}) = \prod^{5}_{i = 1}{\prod^{5}_{j = i + 1}} P(N_i,N_j)\]A su vez, si sabemos que esos 5 números que esocogimos ya ha salido antes en otro sorteo, podemos calcular la probabilidad de que se repita ese escenario asi:
\[P(S_1|S_1) = \frac{1}{2,118,760} \cdot P(S_1)\]Y podemos combinar ambas ecuaciones en una sola:
\[G(s) = \begin{cases} \frac{1}{2,118,760} \cdot \prod\prod P(N_i,N_j),& \text{si } s \in H\\ \prod\prod P(N_i,N_j), & \text{si } s \notin H \end{cases}\]Donde \(H\) es el conjunto de sorteos pasados.
Si transformamos esto a código:
Asumiendo que nuestro historico contiene dos matrices, una con frecuencias de cada número, y otra con las frecuencias por par de números. Podemos calcular las probabilidades de la siguiente forma:
Para encontrar cuales combinaciones de números ya han salido en sorteos anteriores y poder estimar esta probabilidad usamos una lista con el contenido de los últimos sorteos:
Para calcular las matrices de frecuencias, podemos hacer lo siguiente:
Si calculamos la frecuencia con la que salio cada número en el último año y observamos los 10 números más frecuentes:
Número | Frecuencia |
---|---|
5 | 17 |
15 | 17 |
11 | 15 |
14 | 14 |
19 | 14 |
20 | 14 |
46 | 14 |
12 | 13 |
16 | 13 |
27 | 13 |
Y el resultado de la matriz frecuencias_pares
es este:
Cabe mencionar, que todos los números de los sorteos estan ordenados de menor a mayor. Por lo que en los pares, el primer número (eje X) siempre será el menor de ambos, por lo que en la matriz, el triangulo inferior está vacio.
Por último faltaría calcular las probabilidades de las estrellas. Esa parte decidi dejarla fuera de nuestra función objetivo, eso hará que los números de las estrellas sean al azar totalmente. Escoger esos dos digitos de acuerdo a las frecuencias va a hacer que siempre salgan las mismas dos estrellas y es algo que no quiero que suceda en este programa.
Operadores genéticos
Para garantizar que nuestro algoritmo funcione correctamente es necesario elegir operadores que generen soluciones válidas para nuestro problema.
Crossover
Para combinar dos padres en dos hijos, pienso que la mejor opción es usar un Uniform Crossover modificado para lograr mantener las soluciones sin elementos repetidos. El Uniform Crossover trata a cada elemento por separado. Por cada gen se lanza una moneda para decidir si ese gen se hereda del primer padre o del segundo padre.
La modificación para evitar repeticiones es heredar directamente los elementos que esten en ambos padres a los hijos. Y al resto de los genes heredarlos usando Uniform Crossover. Una forma de implementarlo podría ser la siguiente:
- Juntar todos los genes de ambos padres en dos conjuntos, uno para las estrellas y el otro para el resto de los elementos.
- Por cada elemento en el conjunto de los números, elegir un número aleatorio entre 0 y 1.
- Si ese número aleatorio es menor a .5, asignar gen al hijo 1, excepcion que el hijo ya tenga ese gen, en ese caso se asigna al hijo 2. Si es mayor a .5, sucede exactamente lo contrario.
- Si alguno de los hijos ya tiene suficientes elementos, asingar el resto de los elementos al otro hijo.
- Repetir el proceso con el conjunto de estrellas.
Mutación
Para añadir un poco de diversidad a nuestros números de EuroMillones es necesario usar la mutación. Para este fin, vamos a cambiar aleatoriamente dos números en las soluciones, una vez más respetando las condiciones para que sigan siendo válidas.
- Seleccionamos un indice entre 0 y 6 aleatoriamente.
- Seleccionamos un número aleatorio entre 1 y 50 (1 y 12 para las estrellas).
- Si el número generado ya se encuentra en la solucion, generamos otro.
- Reemplazamos el numero en el indicie seleccionado por el número generado.
- Repetir el proceso una vez más.
Selección
La selección que más me gusta a mi es por torneo, y tambien he visto en varios problemas que es de las que mejor desempeño tienen. La selección por torneo funciona de la siguiente forma:
- Aleatoriamente se eligen \(N\) individuos de la población.
- De esos \(N\) individuos seleccionados, se eligen 2 padres, los 2 individuos con la aptitud más alta de de los \(N\) individuos.
En Python:
Notas finales
Ya que tenemos definidas todas las piezas, es cuestión de acomodarlas para que funcionen juntas. Para facilitar la ejecución y la reutilización del código, separé las partes que son exclusivamente de EuroMillones de las funciones del algoritmo génetico.
Para obtener resultados rápidos y evitar que siempre converjan al mismo número, el tamaño de la población la configuré a 50 y el número de generaciones a 150.
Ejemplo de una búsqueda:
Es importante recalcar que la finalidad este programa es explicar como resolver problemas con un algoritmo genético. Es imposible predecir el futuro y la lotería es un juego de azar, por lo tanto no existe un método que nos haga ganar. Y aun que esta idea tenga ciertos fundamentos teóricos, los números que genera el programa tiene exactamente la misma probabilidad de ganar que si compramos un boleto con los números [1,2,3,4,5,6,7]
(o cualquier otra combinación).
Además, los cálculos hechos no reflejan un probabilidad real de ganar la lotería y simplemente creamos una métrica para encontrar combinaciones de números que se lleven bien juntos.
Código
El código fuente lo pueden descargar de github: Algoritmo EuroMillones
Para ejecutar es necesario usar Python 3, y llamar al archivo ejecutar.py
.