Implementación de un algoritmo genético, en Python, que genera un sudoku resuelto
La motivación de esta entrada es la poca información en español que hay sobre el tema. Por lo que está dirigida a quienes no tienen idea de cómo implementar un algoritmo genético para generar un sudoku y, obviamente, quieran hacerlo en Python jeje. Así que iremos paso a paso desglosando el problema.
Si bien un algoritmo genético no es la mejor opción para generar un sudoku, el ejemplo resulta muy práctico y explícito para entender la implementación de este tipo de algoritmos.
Muy bien, asumiendo que entendemos la dinámica evolutiva de un algoritmo genético, empecemos.
Un sudoku es un tablero de 9x9, es decir, contiene 81 números, la idea es que los números no se repitan en una misma columna, fila y sector, así un sudoku está resuelto.
Para nuestro caso, la representación de nuestros individuos (sudokus) serán simples listas con los 81 números.
Para implementar nuestro algoritmo genético haremos uso del framework DEAP, el cual ofrece clases, tipos de datos y distintos operadores (funciones) ya implementados que nos facilitarán mucho el trabajo. Más información sobre el framework la pueden encontrar en su documentación.
En líneas generales, seguiremos los siguientes pasos:
De numpy aprovecharemos las funciones mean, std, max y min para generar las estadísticas que nos ayudarán a graficar los resultados obtenidos.
Con matplotlib graficaremos las estadísticas que iremos generando con numpy.
Y finalmente del framework deap importamos base, creator y tools. Más adelante especificaremos mas.
Paso 2. Definir la función Fitness y otras funciones auxiliares:
La función Fitness nos permitirá obtener una medida sobre los distintos individuos (sudokus) que generemos, y así saber si nos acercamos a la solución, ésta función será clave para descartar los peores individuos. Vamos con el código. Nuestra función Fitness recibe como parámetro un sudoku (individuo), que no es más que una lista con los 81 números.
Analicemos la primera función que encontramos dentro: repetidos. Evalúa un individuo y, de repetirse n númeos n veces, retorna la sumatoria de la cantidad de veces que se repitieron esos n números jaja, disculpen el juego de palabras. Veamos la función nuevamente. Recibe el inividuo, esta vez es una lista que representa una columna fila o sector, es decir, tiene 9 elementos (números). Luego compara el tamaño de esa lista (9 también) con el tamaño de la misma lista pero sin los valores repetidos, de ser distintos ambos tamaños (la primera lista es más larga que la segunda) se resta el tamaño de la primera lista (siempre será 9), menos el tamaño de la segunda (que siempre será menor a 9, porque no se toman en cuenta los números repetidos), y se retorna ese valor, se pudiera considerar un fitness local para esa columna, fila o sector. De lo contrario, si el tamaño de la segunda lista es 9 también, quiere decir que no hay valores repetidos (la lista contiene los números del 1 al 9, no necesariamente ordenados) por lo que el valor de fit sería 0. Lo mismo se hará con el resto de las columnas, filas y sectores del sudoku (individuo). Para dejar claro, en total, son 9 filas, 9 columnas y 9 sectores, compuestos por 9 números cada uno.
Una vez que tenemos la función para evaluar las columnas, filas y sectores, pues, nos queda recorrerlos. Para el caso de recorrer las filas y las columnas el procedimiento es el mismo, lo que varía es el desplazamiento para llegar a las casillas adecuadas, con respecto a los sectores la cosa varía un poco. Veamos primero la función evalua_filas_o_columnas.
Esta función recibe tres parámetros: sudoku (individuo), que es la lista con 81 números; fil_col, que es una lista de 9 números que representan las posiciones de la primera fila o columna; y desplazamiento, que es un número entero que nos indicará cuántas posiciones desplazarnos durante la iteración, ya lo detallaremos.
Primero, con el ciclo while nos aseguramos de recorrer todas las filas o columnas, y por cada elemento en fil_col (recordemos que son las posiciones de la fila o columna) añadimos a la lista auxiliar los números del sudoku correspondientes a esas posiciones; actualizamos nuestro valor de Fitness, y nos desplazamos a la siguiente fila o columna, más adelante en la llamada veremos mejor este desplazamiento.
Luego tenemos la función recorre_sectores, recibe dos parámetros, el sudoku o individuo (lista de 81 elementos), y un número entero que representa la posición del primer elemento ubicado en la esquina superior izquierda del sector, como se muestra en la imagen de abajo, la línea roja demarca al primer sector, mientras que la verde al número mencionado.
Pudiera verse como la posición 0 en una lista unidimensional, o la posición 0,0 en una matriz.
Repasemos de nuevo la función.
Muy bien, dado ese primer número nuestra función retorna el sector entero. Viendo la imagen del sudoku, recorramos los rectores imaginariamente de izquierda a derecha y de arriba hacia abajo.
Ahora si, analicemos el resto de la función Fitness. Inicializamos nuestro fitness en 0. y establecemos la primera columna del sudoku de izquierda a derecha (recordemos que nuestro individuo es una lista unidimensional de 81 números, aclaremos que individuo y sudoku es lo mismo), lo mismo hacemos para la primera fila de arriba hacia abajo.
Evaluamos las columnas, nótese que el desplazamiento es 1, es decir, le sumaremos 1 a cada una de las posiciones dadas. Evaluamos las filas, cuyo desplazamiento es 9. Evaluamos los sectores, proporcionando manualmente, los 9 números de la esquina superior izquierda de cada sector. Y por último retornamos el fitness total como una tupla que contiene un número decimal (tiene que ser de esta manera por cuestiones de compatibilidad con el framework).
Seguimos en el paso 2
Digamos que ya estamos en la parte de definir algunas funciones auxiliares.
Aquí entra nuestra función para imprimir un sudoku. Y las funciones que conforman el operador de mutación. Este operador de mutación fue copiado del libro Clinton Sheppard - Genetic Algorithms with Python (2016), por lo que no me detendré a explicarlo. Quiero aclarar que el framework dispone de varios operadores de mutación, mas sin embargo ninguno funcionó para generar un sudoku válido (resuelto).
Ahora ya estamos en el paso 3, configuración del framework. Estos pasos también se pueden encontrar en la documentación del framework, se pudiera decir que son constantes.
Primero instanciamos el objeto FitnessMin, la variable weights toma el valor de -1.0, ¿por qué -1.0? porque queremos minimizar nuestra función Fitness, es decir, decrementarla hasta que sea 0 (que es nuestro valor objetivo). El libro de Sheppard plantea una función de maximización, su Fitness idóneo es 100, en caso de usar esa función, weights tomaría el valor de 1.0 (positivo). Luego instanciamos el objeto Individual especificando el tipo de dato (una lista para este caso).
Ahora vamos con el objeto toolbox el cual contiene el método register que usaremos a continuación.
Registramos la función Fitness. Definimos el tamaño del individuo (sudokus). Especificamos que los individuos contendrán números aleatorios entre 1 y 9. Se registra el método "individual" pasándole como parámetros el objeto que genera enteros aleatorios y el tamaño del individuo; el método "population" lo usaremos para generar la población inicial, completamente aleatoria.
Registramos el operador de cruce, especificándole el tipo de cruce "cxTwoPoint" (cruce en dos puntos); no registramos el método de mutación porque usaremos el del libro que especificamos previamente. Y por último, definimos el operador de selección: "selección por torneo", donde se escogen tres individuos de acuerdo a su fitness.
Paso 4, función principal.
Acá haremos nuestra dinámica evolutiva. Copiada del ejemplo "One Max Problem" de la documentación del framework DEAP. Nuestra función recibe una lista como parámetro, donde iremos insertado nuestras estadísticas generadas en cada iteración.
En la línea 3 definimos la función add_estadisticas que recibe como parámetros la población de cada generación y retorna un diccionario con el número de la iteración (generación), el fitness medio, el estándar, el máximo y el mínimo (aquí es donde hacemos uso de numpy).
En la línea 15 generamos una población inicial de 400 individuos (sudokus aleatorios).
Línea 21: definimos la probabilidad de cruce y mutación: 83% y 75% respectivamente.
Líneas 25, 26, 27 y 28: evalúa/actualiza el fitness de la población.
Línea 33: añade a una lista todos los "fitnesses" calculados previamente para poder hacer la iteración en la línea 39.
Línea 39: mientras nuestro fitness objetivo no sea 0 y no alcancemos un máximo de 300 iteraciones (en la corrida, si alcanzamos las 300 sin hallar solución, se repite todo el proceso con una nueva población aleatoria)...
Líneas 45 y 47: seleccionamos los individuos más aptos (aquí usamos el operador de selección por torneo definido previamente) y hacemos una copia de esta población.
Desde la línea 50 hasta la 66: cruzamos y mutamos los individuos (sudokus).
Desde la línea 69 hasta la 72: evalúa el resto de la población.
Línea 77: reemplaza la vieja población por la nueva. Nótese la sintaxis, porque de hacerlo "pop = offspring" perderíamos el objeto proporcionado por el framework por un simple lista.
De la línea 80 en adelante: las estadísticas.
Muy bien, ya lo que resta es ejecutar nuestro código. Veamos la función main(). Si alcanzó el máximo de iteraciones (300) sin hallar solución, corre de nuevo la dinámica evolutiva, de hallarse una solución la imprime y detiene la ejecución. Todo esto está dentro de un manejo de excepciones porque de ser muy altas las probabilidades de cruce y mutación ocurren excepciones en la ejecución, de ocurrir alguna, se ejecuta de nuevo, de todos modos las probabilidades establecidas son "seguras".
Por último tenemos la función para graficar y la corrida del código. Espero que haya sido de su agrado este brusco y técnico tutorial, es el primero que hago, cualquier duda por favor comenten. El código fuente completo lo pueden encontrar aquí
Si bien un algoritmo genético no es la mejor opción para generar un sudoku, el ejemplo resulta muy práctico y explícito para entender la implementación de este tipo de algoritmos.
Muy bien, asumiendo que entendemos la dinámica evolutiva de un algoritmo genético, empecemos.
Un sudoku es un tablero de 9x9, es decir, contiene 81 números, la idea es que los números no se repitan en una misma columna, fila y sector, así un sudoku está resuelto.
Para nuestro caso, la representación de nuestros individuos (sudokus) serán simples listas con los 81 números.
Para implementar nuestro algoritmo genético haremos uso del framework DEAP, el cual ofrece clases, tipos de datos y distintos operadores (funciones) ya implementados que nos facilitarán mucho el trabajo. Más información sobre el framework la pueden encontrar en su documentación.
En líneas generales, seguiremos los siguientes pasos:
- Definimos las librerías a utilizar.
- Definimos la función Fitness y otras funciones auxiliares.
- Configuramos el framework y le adaptamos nuestra función Fitness.
- Y definimos nuestra función principal.
De numpy aprovecharemos las funciones mean, std, max y min para generar las estadísticas que nos ayudarán a graficar los resultados obtenidos.
Con matplotlib graficaremos las estadísticas que iremos generando con numpy.
Y finalmente del framework deap importamos base, creator y tools. Más adelante especificaremos mas.
Paso 2. Definir la función Fitness y otras funciones auxiliares:
La función Fitness nos permitirá obtener una medida sobre los distintos individuos (sudokus) que generemos, y así saber si nos acercamos a la solución, ésta función será clave para descartar los peores individuos. Vamos con el código. Nuestra función Fitness recibe como parámetro un sudoku (individuo), que no es más que una lista con los 81 números.
Analicemos la primera función que encontramos dentro: repetidos. Evalúa un individuo y, de repetirse n númeos n veces, retorna la sumatoria de la cantidad de veces que se repitieron esos n números jaja, disculpen el juego de palabras. Veamos la función nuevamente. Recibe el inividuo, esta vez es una lista que representa una columna fila o sector, es decir, tiene 9 elementos (números). Luego compara el tamaño de esa lista (9 también) con el tamaño de la misma lista pero sin los valores repetidos, de ser distintos ambos tamaños (la primera lista es más larga que la segunda) se resta el tamaño de la primera lista (siempre será 9), menos el tamaño de la segunda (que siempre será menor a 9, porque no se toman en cuenta los números repetidos), y se retorna ese valor, se pudiera considerar un fitness local para esa columna, fila o sector. De lo contrario, si el tamaño de la segunda lista es 9 también, quiere decir que no hay valores repetidos (la lista contiene los números del 1 al 9, no necesariamente ordenados) por lo que el valor de fit sería 0. Lo mismo se hará con el resto de las columnas, filas y sectores del sudoku (individuo). Para dejar claro, en total, son 9 filas, 9 columnas y 9 sectores, compuestos por 9 números cada uno.
Una vez que tenemos la función para evaluar las columnas, filas y sectores, pues, nos queda recorrerlos. Para el caso de recorrer las filas y las columnas el procedimiento es el mismo, lo que varía es el desplazamiento para llegar a las casillas adecuadas, con respecto a los sectores la cosa varía un poco. Veamos primero la función evalua_filas_o_columnas.
Esta función recibe tres parámetros: sudoku (individuo), que es la lista con 81 números; fil_col, que es una lista de 9 números que representan las posiciones de la primera fila o columna; y desplazamiento, que es un número entero que nos indicará cuántas posiciones desplazarnos durante la iteración, ya lo detallaremos.
Primero, con el ciclo while nos aseguramos de recorrer todas las filas o columnas, y por cada elemento en fil_col (recordemos que son las posiciones de la fila o columna) añadimos a la lista auxiliar los números del sudoku correspondientes a esas posiciones; actualizamos nuestro valor de Fitness, y nos desplazamos a la siguiente fila o columna, más adelante en la llamada veremos mejor este desplazamiento.
Luego tenemos la función recorre_sectores, recibe dos parámetros, el sudoku o individuo (lista de 81 elementos), y un número entero que representa la posición del primer elemento ubicado en la esquina superior izquierda del sector, como se muestra en la imagen de abajo, la línea roja demarca al primer sector, mientras que la verde al número mencionado.
Repasemos de nuevo la función.
Muy bien, dado ese primer número nuestra función retorna el sector entero. Viendo la imagen del sudoku, recorramos los rectores imaginariamente de izquierda a derecha y de arriba hacia abajo.
Ahora si, analicemos el resto de la función Fitness. Inicializamos nuestro fitness en 0. y establecemos la primera columna del sudoku de izquierda a derecha (recordemos que nuestro individuo es una lista unidimensional de 81 números, aclaremos que individuo y sudoku es lo mismo), lo mismo hacemos para la primera fila de arriba hacia abajo.
Evaluamos las columnas, nótese que el desplazamiento es 1, es decir, le sumaremos 1 a cada una de las posiciones dadas. Evaluamos las filas, cuyo desplazamiento es 9. Evaluamos los sectores, proporcionando manualmente, los 9 números de la esquina superior izquierda de cada sector. Y por último retornamos el fitness total como una tupla que contiene un número decimal (tiene que ser de esta manera por cuestiones de compatibilidad con el framework).
Seguimos en el paso 2
Digamos que ya estamos en la parte de definir algunas funciones auxiliares.
Aquí entra nuestra función para imprimir un sudoku. Y las funciones que conforman el operador de mutación. Este operador de mutación fue copiado del libro Clinton Sheppard - Genetic Algorithms with Python (2016), por lo que no me detendré a explicarlo. Quiero aclarar que el framework dispone de varios operadores de mutación, mas sin embargo ninguno funcionó para generar un sudoku válido (resuelto).
Ahora ya estamos en el paso 3, configuración del framework. Estos pasos también se pueden encontrar en la documentación del framework, se pudiera decir que son constantes.
Primero instanciamos el objeto FitnessMin, la variable weights toma el valor de -1.0, ¿por qué -1.0? porque queremos minimizar nuestra función Fitness, es decir, decrementarla hasta que sea 0 (que es nuestro valor objetivo). El libro de Sheppard plantea una función de maximización, su Fitness idóneo es 100, en caso de usar esa función, weights tomaría el valor de 1.0 (positivo). Luego instanciamos el objeto Individual especificando el tipo de dato (una lista para este caso).
Ahora vamos con el objeto toolbox el cual contiene el método register que usaremos a continuación.
Registramos la función Fitness. Definimos el tamaño del individuo (sudokus). Especificamos que los individuos contendrán números aleatorios entre 1 y 9. Se registra el método "individual" pasándole como parámetros el objeto que genera enteros aleatorios y el tamaño del individuo; el método "population" lo usaremos para generar la población inicial, completamente aleatoria.
Registramos el operador de cruce, especificándole el tipo de cruce "cxTwoPoint" (cruce en dos puntos); no registramos el método de mutación porque usaremos el del libro que especificamos previamente. Y por último, definimos el operador de selección: "selección por torneo", donde se escogen tres individuos de acuerdo a su fitness.
Paso 4, función principal.
Acá haremos nuestra dinámica evolutiva. Copiada del ejemplo "One Max Problem" de la documentación del framework DEAP. Nuestra función recibe una lista como parámetro, donde iremos insertado nuestras estadísticas generadas en cada iteración.
En la línea 3 definimos la función add_estadisticas que recibe como parámetros la población de cada generación y retorna un diccionario con el número de la iteración (generación), el fitness medio, el estándar, el máximo y el mínimo (aquí es donde hacemos uso de numpy).
En la línea 15 generamos una población inicial de 400 individuos (sudokus aleatorios).
Línea 21: definimos la probabilidad de cruce y mutación: 83% y 75% respectivamente.
Líneas 25, 26, 27 y 28: evalúa/actualiza el fitness de la población.
Línea 33: añade a una lista todos los "fitnesses" calculados previamente para poder hacer la iteración en la línea 39.
Línea 39: mientras nuestro fitness objetivo no sea 0 y no alcancemos un máximo de 300 iteraciones (en la corrida, si alcanzamos las 300 sin hallar solución, se repite todo el proceso con una nueva población aleatoria)...
Líneas 45 y 47: seleccionamos los individuos más aptos (aquí usamos el operador de selección por torneo definido previamente) y hacemos una copia de esta población.
Desde la línea 50 hasta la 66: cruzamos y mutamos los individuos (sudokus).
Desde la línea 69 hasta la 72: evalúa el resto de la población.
Línea 77: reemplaza la vieja población por la nueva. Nótese la sintaxis, porque de hacerlo "pop = offspring" perderíamos el objeto proporcionado por el framework por un simple lista.
De la línea 80 en adelante: las estadísticas.
Muy bien, ya lo que resta es ejecutar nuestro código. Veamos la función main(). Si alcanzó el máximo de iteraciones (300) sin hallar solución, corre de nuevo la dinámica evolutiva, de hallarse una solución la imprime y detiene la ejecución. Todo esto está dentro de un manejo de excepciones porque de ser muy altas las probabilidades de cruce y mutación ocurren excepciones en la ejecución, de ocurrir alguna, se ejecuta de nuevo, de todos modos las probabilidades establecidas son "seguras".
Por último tenemos la función para graficar y la corrida del código. Espero que haya sido de su agrado este brusco y técnico tutorial, es el primero que hago, cualquier duda por favor comenten. El código fuente completo lo pueden encontrar aquí
Comentarios
Publicar un comentario