BITácora de Software

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)

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.

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

El algoritmo de ordenamiento por mezcla (merge sort en inglés) es un algoritmo de ordenamiento externo estable basado en la técnica divide y vencerás. Es de complejidad O(n log n), fue desarrollado en 1945 por John Von Neumann

In computer science, merge sort (also commonly spelled mergesort) is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Mergesort is a divide and conquer algorithm that was invented by John von Neumann in 1945. A detailed description and analysis of bottom-up mergesort appeared in a report by Goldstine and Neumann as early as 1948.

Podemos plantearnos también diseñar un algoritmo de búsqueda “ternaria”, que primero compara con el elemento en posición n/3 del vector, si éste es menor que el elemento x a buscar entonces compara con el elemento en posición 2n/3, y si no coincide con x busca recursivamente en el correspondiente subvector de tamaño 1/3 del original. ¿Conseguimos así un algoritmo mejor que el de búsqueda binaria?
We may also consider designing a "ternary" search algorithm, which First compared to the element in position n / 3 of the vector, if this is less The element x to look for and compare with the element in position 2n / 3, and if not Match recursively searching for the corresponding 1/3 size subvector From the original. Did we get a better algorithm than binary search?

Se tienen dos vacas greedys que deben alimentarse,dichas vacas se alimentan de bloques de pasto colocados en fila, a su turno cada vaca come el bloque mas grande entre los extremos ¿cuánto comió cada vaca?

La búsqueda binaria funciona en arreglos ordenados. La búsqueda binaria comienza por comparar el elemento del medio del arreglo con el valor buscado. Si el valor buscado es igual al elemento del medio, su posición en el arreglo es retornada. Si el valor buscado es menor o mayor que el elemento del medio, la búsqueda continua en la primera o segunda mitad, respectivamente, dejando la otra mitad fuera de consideración.

Binary search works in ordered arrays. The binary search begins by comparing the middle element of the array with the searched value. If the searched value is equal to the middle element, its position in the array is returned. If the searched value is less than or greater than the middle element, the search continues in the first or second half, respectively, leaving the other half out of consideration.