Algoritmo Genetico Con El Juego De Las N Reinas

Algoritmo Genético
Problema de las N Reinas
El problema de las n-Reinas (n-Queens Problem) es muy antiguo y consiste en
encontrar una asignación a n reinas en un tablero de ajedrez de n x n sin que éstas se
amenacen, por tanto dos reinas no pueden estar en la misma fila, columna o diagonal.
Es importante mencionar que la investigación sobre el problema de las n reinas no
ha parado hasta hoy, queel numero de soluciones crece en forma exponencial para valores
de n más grandes, que para n=1 (una reina) el problema tiene una solución, que para n=2 y
n=3 no tiene solución, es decir, no se pueden ubicar las 2 y 3 reinas en un tablero de ajedrez
de 2x2 y 3x3 respectivamente sin que se ataquen y que se tienen 2 soluciones para n=4.

A continuación se muestra el número total de solucionesválidas para cada valor de
n, donde 4 < n < 20
n
Total de Soluciones
4
2
5
10

6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

4
40
92
352
724
2.680
14.200
73.712
365.596
2.279.184
14.772.512
95.815.104
666.090.624
4.968.057.848
39.029.188.884

En el presente trabajo se tratará dicho problema y consistirá en encontrar
exactamente una solución válida mediante Algoritmo Genético para 8 reinas (n=8) puestoque, como se observó en la tabla anterior para n=8 existen 92 soluciones validas.
Si aplicamos la búsqueda por fuerza bruta para solucionar el problema de las 8
reinas, se tendría que examinar todas las combinaciones de posición; un total de
178.462.987.637.760 (64!/56!) posiciones diferentes, comprobando en cada una de ellas
que las 8 reinas no se ataquen mutuamente.
La búsqueda por fuerza bruta essencilla de implementar y se usa habitualmente
cuando el número de soluciones candidatas no es elevado, siempre que exista, encuentra
una solución. Sin embargo, su coste de ejecución es proporcional al número de soluciones
candidatas, el cual es exponencialmente proporcional al tamaño del problema.
Es aquí donde los Algoritmos Genéticos juegan un importante papel a la hora de
encontrar lasolución válida al Problema de las 8 Reinas con un esfuerzo insignificante si
los comparamos con lo descrito anteriormente.
Los Algoritmos Genéticos son métodos adaptativos, generalmente usados en
problemas de búsqueda y optimización de parámetros, basados en la reproducción sexual y
en el principio de supervivencia del más apto. Están basados en el proceso genético de los
organismos vivos. A lo largode las generaciones, las poblaciones evolucionan en la
naturaleza acorde con los principios de la selección natural y la supervivencia de los más
fuertes, postulados por Darwin (1859).
En la naturaleza los individuos de una población compiten entre sí en la búsqueda
de recursos tales como comida, agua y refugio. Incluso los miembros de una misma especie
compiten a menudo en la búsqueda de uncompañero. Aquellos individuos que tienen más

éxito en sobrevivir y en atraer compañeros tienen mayor probabilidad de generar un gran
número de descendientes. Por el contrario individuos poco dotados producirán un menor
número de descendientes. Esto significa que los genes de los individuos mejor adaptados se
propagaran en sucesivas generaciones hacia un número de individuos creciente. La
combinaciónde buenas características provenientes de diferentes ancestros, puede a veces
producir descendientes “superindividuos", cuya adaptación es mucho mayor que la de
cualquiera de sus ancestros. De esta manera, las especies evolucionan logrando unas
características cada vez mejor adaptadas al entorno en el que viven.
Los Algoritmos Genéticos usan una analogía directa con el comportamiento natural.Trabajan con una población de individuos, cada uno de los cuales representa una solución
factible a un problema dado. Cuanto mayor sea la adaptación de un individuo al problema,
mayor será la probabilidad de que el mismo sea seleccionado para reproducirse, cruzando
su material genético con otro individuo seleccionado de igual forma. Este cruce producirá
nuevos individuos (descendientes de los...