Google+ Seguidores

sábado, 5 de mayo de 2018

El problema de las N-Reinas - Algoritmos Genéticos


Hola Mundo, mi nombre es Luis y les doy la bienvenida a “Mi Diario Python”.
En el día de hoy, nos propondremos a resolver un problema. “El problema de las N-Reinas”. ¿Te interesa? Entonces sigue leyendo.

El Problema de las N-Reinas:

Antes de resolver el problema, debemos enfrentarnos, debemos conocerlo para luego planear una solución.
En el juego de ajedrez la reina amenaza a aquellas piezas que se encuentren en su misma fila, columna o diagonal. El problema de las 8 reinas (o n-reinas ya que dependen del numero asignado) consiste en poner sobre un tablero de ajedrez ocho reinas sin que estas se amenacen entre ellas.

En la siguiente imagen se muestra un ejemplo sobre una posible solución para este problema:

Resultado de imagen para el problema de las n-reinas


¿Cómo resolverías este problema? Podrías buscar un tablero de ajedrez y tratar de hacerlo a mano. O podríamos utilizar nuestros conocimientos de programadores y resolver el problema.

El problema de las ocho reinas se puede plantear de modo general como problema de las {\displaystyle n} reinas. El problema consistiría en colocar {\displaystyle n} reinas en un tablero de ajedrez de tal manera que ninguna de las reinas quede atacando a otras.

Hay muchas maneras de resolver este problema, pero en el día de hoy utilizaremos una herramienta la cual nos va a permitir resolver el problema de manera eficiente. Utilizaremos Algoritmos Genéticos. ¿No sabes que son los Algoritmos Genéticos? No te preocupes, lo explicaremos paso a paso.


 Algoritmos Genéticos:

Los algoritmos genéticos (AG) funcionan entre el conjunto de soluciones de un problema llamado fenotipo, y el conjunto de individuos de una población natural, codificando la información de cada solución en una cadena, generalmente binaria, llamada cromosoma. Los símbolos que forman la cadena son llamados genes. Cuando la representación de los cromosomas se hace con cadenas de dígitos binarios se le conoce como genotipo. Los cromosomas evolucionan a través de iteraciones, llamadas generaciones. En cada generación, los cromosomas son evaluados usando alguna medida de aptitud. Las siguientes generaciones (nuevos cromosomas), son generadas aplicando los operadores genéticos repetidamente, siendo estos los operadores de seleccióncruzamientomutación y reemplazo.

Un algoritmo genético puede presentar diversas variaciones, dependiendo de cómo se aplican los operadores genéticos (cruzamiento, mutación), de cómo se realiza la selección y de cómo se decide el reemplazo de los individuos para formar la nueva población. En general, el pseudocódigo consiste de los siguientes pasos:

·         Inicialización: Se genera aleatoriamente la población inicial, que está constituida por un conjunto de cromosomas los cuales representan las posibles soluciones del problema. En caso de no hacerlo aleatoriamente, es importante garantizar que dentro de la población inicial, se tenga la diversidad estructural de estas soluciones para tener una representación de la mayor parte de la población posible o al menos evitar la convergencia prematura.

·         Evaluación: A cada uno de los cromosomas de esta población se aplicará la función de aptitud para saber cómo de "buena" es la solución que se está codificando.

·         Condición de término: El AG se deberá detener cuando se alcance la solución óptima, pero esta generalmente se desconoce, por lo que se deben utilizar otros criterios de detención. Normalmente se usan dos criterios: correr el AG un número máximo de iteraciones (generaciones) o detenerlo cuando no haya cambios en la población. Mientras no se cumpla la condición de término se hace lo siguiente:

·         Selección: Después de saber la aptitud de cada cromosoma se procede a elegir los cromosomas que serán cruzados en la siguiente generación. Los cromosomas con mejor aptitud tienen mayor probabilidad de ser seleccionados.

·         Recombinación o cruzamiento: La recombinación es el principal operador genético, representa la reproducción sexual, opera sobre dos cromosomas a la vez para generar dos descendientes donde se combinan las características de ambos cromosomas padres.

·         Mutación: Modifica al azar parte del cromosoma de los individuos, y permite alcanzar zonas del espacio de búsqueda que no estaban cubiertas por los individuos de la población actual.

·         Reemplazo: Una vez aplicados los operadores genéticos, se seleccionan los mejores individuos para conformar la población de la generación siguiente.

A continuación te mostrare una imagen que muestra los pasos del funcionamiento de un algoritmo genético:

Resultado de imagen para algoritmos geneticos
Algoritmo genético i: inicialización, f(X): evaluación, ?: condición de término, Se: selección, Cr: cruzamiento, Mu: mutación, Re: reemplazo, X*: mejor solución.

Solución del Problema:
Perfecto, ya conocemos el problema y sabemos que herramienta utilizar para la solución. Ahora nos hace falta implementar solución. Esto lo haremos en el lenguaje de programación Python y haremos uso del módulo Deap (https://pypi.org/project/deap/).

Una vez que dispongamos del módulo Deap, podemos proseguir a programar la solución.





Comenzamos importando las librerías necesarias. Como pueden observar, la variable NB_QUEENS contiene el número de reinas que irán en el tablero, como mencione anteriormente, el número de reinas depende del programador, yo utilizare 8 ya que es el típico.





La función de evaluación calcula el número de reinas R que hay en cada diagonal. El número de ataques que hay en cada diagonal se puede calcular como R-1.





Lo que se hace ahora es crear las poblaciones y los individuos, para que luego obtengamos como resultado la posible solución.




La función main nos devolverá la población y los individuos que mejor resultado tuvieron.

Para mostrar el resultado de manera visual, utilizaremos la librería matplotlib de la siguiente manera:




Al ejecutar el script, tendríamos algo como esto:





Como pueden observar, el algoritmo a resuelto el problema de manera rápida.

Puedes conseguir el script en mi repositorio de github: https://github.com/LuisAlejandroSalcedo/Problema-de-las-N-Reinas.

¿Qué te pareció? Si tienes dudas no dudes en dejar tu comentario.

¿Quieras más artículos referentes a este tema? Déjanoslo saber.

Mi nombre es Luis, y fue un placer compartir mis conocimientos con todos ustedes :D. 

1 comentario :
Write comentarios
  1. muy interesante, me interesa todo tipo algoritmos entre estos los genéticos, y claro su aplicación en videojuegos que es mucha

    ResponderEliminar

Tu comentario es importante y nos motiva a seguir escribiendo...

Powered by Blogger .