Análisis de operadores de recombinación del algoritmo genético aplicado al problema de las n-reinas - Analysis of recombination operators of the genetic algorithm applied to the n-queens problem
Proyecto de tesis para la obtención del grado de Licenciatura en Ciencias de la computación - Thesis Project Implementation for Computer Scientist Bachelor Degree:
El objetivo del proyecto fue analizar cuatro operadores de cruce que utilizan representación basada en permutaciones dentro de un algoritmo genético genérico. El análisis se centró tanto en el tiempo de ejecución computacional como en la calidad de la solución (fitness) alcanzada por el algoritmo genético utilizando cada uno de los cuatro operadores. Para lograr esto, la metodología incluyó un análisis de la complejidad temporal de la implementación en Python, seguido de una comparación de los resultados promedio de cada operador a lo largo de treinta ejecuciones en diferentes tamaños de instancia. Un resultado importante fue la conclusión de que IPMX superó a PMX, así como a mi propuesta de implementación llamada PMX2, la cual mostró tiempos de ejecución competitivos.
The objective of the project was to analyze four crossover operators that use permutation-based representation within a generic genetic algorithm. The analysis focused on both the computational execution time and the solution quality (fitness) achieved by the GA using each of the four operators. To achieve this, the methodology included a time complexity analysis of the Python implementation, followed by a comparison of the average results of each operator across thirty executions on different instance sizes. An important result was the conclusion that IPMX outperformed PMX, as well as my proposed implementation called PMX2, which showed competitive execution times.
- Performance comparison of genetic algorithms with traditional search techniques on the N-Queen Problem
- A Survey and Analysis of Evolutionary Operators for Permutations
- Genetic Algorithms and Their Applications
- Reasoning About Order Crossover in Genetic Algorithms
- Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators