Procedimiento Sudoku
Procedimiento Sudoku
Procedimiento Sudoku
Implementación
Usé una biblioteca de python llamada DEAP. Lo encontré muy bueno y fácil de
entender / usar La interfaz de esta biblioteca. Permite mucha flexibilidad para
modificar cualquier parámetro. Eso puede existir en un algoritmo genético. La
ventaja de usar esta biblioteca es que ya Viene con muchas cosas básicas y de
uso común en un AG hecho listo. Y cualquier Personalización que quiero hacer,
puedo cambiar la función utilizada dentro del algoritmo a través del
que la documentación llamada del kit de herramientas.
Sin embargo, esta versión tiene un rendimiento que juzgué mal y decidí hacer Una
segunda versión (genetic2.py). En esta versión, la inicialización se realiza de
modo que cada fila de la tabla tenga solo una instancia de cada valor del 1 al
9. Por lo tanto, ya comienzo en un estado que es mejor que un 100% aleatorio.
Con este cambio, la población inicial comenzó con una calificación de la junta
mucho más alta y, en consecuencia, alcanzó el punto de convergencia
comparativamente más rápido (máximo local). Esto también resultó en una Un poco
mejor rendimiento en términos de solución final.
Análisis de parámetros
Empíricamente, puedo decir que un buen valor de mutación para Este problema con
los otros parámetros fijos es del 10%. Quizás esto se deba al hecho de que La
población tiene un tamaño estándar de 50 individuos. Como 50 individuos no
permiten un límite de búsqueda muy amplio, la mutación está a cargo de explorar
ramas más remotas arbol. Lo que nos lleva al segundo parámetro a modificar, el
tamaño de la población.
Cambiando el tablero
Elitismo
Otras variaciones
Usando esta técnica, obtuve una puntuación de 233 de los 243 puntos posibles. Lo
que posiblemente significa que la tabla final tenía 3 cuadrados incorrectos (ya
que en mi función de aptitud cuento los errores por fila, columna y cuadrante,
permitiendo que un cuadrado incorrecto contribuya con hasta 3 errores).
2) Hill Climbing
Introducción
Aun así, Hill Climbing no pudo encontrar ninguna solución. Lo tengo Acércate
mucho, pero no en la solución.
1) Implementación
El algoritmo de escalada fue implementado por mí usando solo numpy como una
biblioteca externa.
2) Cambiando el tablero
Hice los mismos cambios en el tablero con la escalada de colinas para verificar
los cambios. Los resultados fueron consistentes con los del algoritmo genético.
Cuando eliminé las restricciones – y en consecuencia, generó más máximos
locales: la escalada de la colina se atoró al máximo ubicación más a menudo. Y
al agregar restricciones, la escalada de colinas pudo acercarse mucho a la
solución, superando todas mis expectativas para este desempeño.
algoritmo
3) Ejecución
4) Comentarios
Las imágenes se dividen en carpetas con nombres que se explican por sí mismos y
se refieren a experimentos realizados Puede suceder que algunos títulos de
gráficos sean un poco incorrectos (mi error al hacer el gráfico). Sin embargo,
su ubicación en carpetas describe exactamente sus contenidos. Si hay una
divergencia entre el título y la ubicación, la confianza más en la ubicación.