El problema de las N-Reinas - Algoritmos Genéticos
Hola Mundo, mi nombre es Luis y les doy la bienvenida a “Mi
Diario Python”.
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.
problema de las N-Reinas”. ¿Te interesa? Entonces sigue leyendo.
El Problema
de las N-Reinas:
de las N-Reinas:
Antes de resolver el problema, debemos enfrentarnos, debemos
conocerlo para luego planear una solución.
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.
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:
solución para este problema:
¿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.
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 reinas.
El problema consistiría en colocar reinas en un tablero de ajedrez de tal manera que ninguna de
las reinas quede atacando a otras.
general como problema de las reinas.
El problema consistiría en colocar 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.
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ón, cruzamiento, mutación y reemplazo.
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ón, cruzamiento, mutació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:
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.
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.
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:
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.
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.
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.
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.
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:
continuación te mostrare una imagen que muestra los pasos del funcionamiento de
un algoritmo genético:
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.
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/).
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.
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.
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.
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.
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.
resultado tuvieron.
Para
mostrar el resultado de manera visual, utilizaremos la librería matplotlib de
la siguiente manera:
mostrar el resultado de manera visual, utilizaremos la librería matplotlib de
la siguiente manera:
Al
ejecutar el script, tendríamos algo como esto:
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.
nombre es Luis, y fue un placer compartir mis conocimientos con todos ustedes
:D.
Unknown 
muy interesante, me interesa todo tipo algoritmos entre estos los genéticos, y claro su aplicación en videojuegos que es mucha