[JavaScript] Resolver Problema de N Reinas usando algoritmos genéticos

Para empezar tenemos que definir el cromosoma que permita representar las M reinas en el tablero y será de la siguiente manera:

Imagen 1: Representación de un cromosoma de 4 reinas (Fuente propia)

Por cada elemento dentro del arreglo (cromosomas) esta el valor de la fila donde se ubicará la reina, en este caso la imagen 1 se verá de la siguiente manera en un tablero:

Imagen 2: Tablero de 4 reinas (Fuente propia)

Como notaron el cromosoma se representa en un arreglo de M elementos, por lo tanto si deseamos representar una población de cromosomas tendremos como resultado una matriz de NxM, dónde N es el número de individuos (población) y M el número de reinas a representar.

Imagen 3: Población de 7 individuos (cada individuo contiene la representación de 4 reinas)

A priori sabemos que un algoritmo genético hace uso de iteraciones (generaciones) para hacer mutar a los individuos dentro de una población, después se aplica la función fitness a cada individuo con el fin de averiguar si se obtuvo la solución al problema planteado. Para este caso la función fitness que aplicaremos será la siguientes:

Imagen 4: Función Fitness (Fuente propia)

Esto quiere decir que en cada generación vamos a evaluar a cada individuo y aplicarle la función fitness para que nos devuelva el porcentaje de ataque entre reinas. Si la función fitness devuelve 0 % de ataques, quiere decir que hemos encontrado un individuo que nos da la solución al problema de la N reinas.

Programación de la solución

Vamos a empezar por la parte gráfica, como datos de entrada tenemos que solicitar el ingreso del Número de reinas, la población de individuos y el número de máximo de generaciones a realizar.

Imagen 5: Interfaz del usuario. (Fuente propia)

Contenido del archivo index.html:
La información será representa en los divs:

contenido: En este div se dibujará la representación de la población (matriz NxM). Cuando se encuentre un individuo optimo (solución) la fila será marcada con el color rojo.
solución: En este div se dibujará el tablero con la representación de individuo solución (en caso se encuentre)

Contenido del archivo estilos.css:
Contenido del archivo jquery-1.12.2.min.js (por si se les hace dificil encontrarlo en línea):

El archivo algoritmoGenetico.js contiene toda la lógica, así que explicaré el contenido de dicho archivo.

Comenzaré explicando para qué sirven las variables globales:

cantReinas, sirve para almacenar el número de reinas a representar en el problema (M reinas) y el dato será obtenido de la caja de texto txtNumReinas.
poblacion, sirve para almacenar el número de individuos que tendrá la población (N individuos), el dato es obtenido de la caja de texto txtPoblacion.
generaciones, sirve como bandera lógica de tope para las iteraciones realizadas en caso no se llegué a encontrar la solución al problema.
matriz, almacena la representación de NxM (N individuos y sus respectivas M reinas).
matrizTemp, sirve para generar a los individuos de la nueva generación.
indicePintar, por defecto empieza con el valor -1 (porque no se encuentra un individuo solución), si se llega a encontrar un individuo solución se almacena el indice de la fila donde esta ubicado.
listaAtaques, es un arreglo que almacena la cantidad de ataques de las reinas por cada individuo de la población, es decir que si existen 7 individuos el arreglo será de longitud 6 (de 0 a 6).
listaPorcentajes, es un arreglo que almacena el porcentaje de ataques y el indice del individuo, es decir que si existen 7 individuos y existe 1 individuo con 0 ataques y la sumatoria de ataques es 25, tendrá un porcentaje del 0% de ataques lo cuál lo vuelve un individuo solución. Cabe señalar que en cada generación se realiza un ordenamiento para tener siempre a los individuos con menor % de ataques siempre primeros con el fin de que se vuelvan los padres de los individuos de las nuevas generaciones.
numGeneraciones, contador de generaciones que sirve para identificar en qué generaciones nos encontramos. También sirve para compararlo con la variable generaciones en caso lleguemos al límite de generaciones a realizar.
candidatoApto, sirve para identificar si se encontró un individuo solución, si es así se detiene la lógica para construir siguientes generaciones de individuos.

El botón Generar reinicia la bandera que se usa para validar si existe un individuo optimo, por otro lado, valida que las cajas de textos tengan datos y limpia la información de los divs que imprimen la población y la representación del tablero. Además invoca a la función que genera la población inicial, después realiza la selección de los individuos más óptimos, los ordena de forma ascendente (los individuos que tengan menos porcentaje de ataques estarán primeros en la lista de la población) e imprime la representación de la población. A continuación, se evalúa si dicha población generó un individuo óptimo entonces imprime la representación del tablero. En caso no exista un individuo solución lo que se hace es el cruzamiento y mutación de individuos (acción aleatoria, es decir, que no se realiza siempre).

El botón Resolver invoca a la función responsable de realizar la selección de individuos para la próxima generación y evalúa si se encontró un individuo o candidato óptimo. Después se realiza el cruzamiento y mutación de individuos, todo el cálculo se realiza sobre una matriz temporal por lo que se debe actualizar los datos de la variable que contiene la población (línea de referencia 51), por último imprime la población y aumenta el contador de la generación. Esto se realiza X generaciones hasta encontrar un candidato óptimo o hasta llegar al límite de las generaciones a iterar (línea de referencia 58). Si no se halló un candidato apto se indica mediante un mensaje (línea de referencia 59) y se reinicializa las variables.

Contenido total del archivo algoritmoGenetico.js

Repositorio Github: https://github.com/Weyne/AlgoritmoGenetico-N-Reinas