Análisis comparativo entre el algoritmo cuántico de Grover y un algoritmo Grasp, aplicados a la búsqueda de individuos óptimos en la población inicial de un algoritmo genético
Rivera Alejo, José Enríque
Abstract
Este trabajo trata sobre la aplicación de dos algoritmos de búsqueda a la\nselección de individuos óptimos en la población inicial de un algoritmo\ngenético, y la consiguiente comparación entre ambos.\nEl primero de ellos es el algoritmo meta-heurístico GRASP, y el segundo es el\nalgoritmo cuántico de Grover.\nEl algoritmo cuántico de Grover forma parte de una nueva generación en las\nciencias de la computación: la computación cuántica. Y por tanto hace uso de\nconceptos matemáticos y físicos completamente distintos a los usados en la\nprogramación clásica.\nEn esta tesis se presenta un análisis general de ambos algoritmos, siendo de\nespecial mención el análisis del algoritmo cuántico de Grover, ya que incluye\nun modelo matemático del funcionamiento del mismo. Este modelo será de\nsuma importancia para simular la ejecución del algoritmo de Grover en una\ncomputadora clásica, dada la carencia de una computadora cuántica sobre la\ncual realizar esto.\nLuego, se preparan dos procesos experimentales, los cuales se usarán para\nrealizar la comparación de eficacia y eficiencia entre las ejecuciones de los\ndos algoritmos.\nPosteriormente, se presenta el diseño e implementación de los algoritmos,\nambos aplicados a la selección de individuos de un algoritmo genético\ngenérico. Una vez ambos algoritmos se encuentren correctamente\nimplementados y funcionales, se ejecutarán las pruebas experimentales que\npermitan realizar la comparación entre ellos.\nFinalmente se realizan las conclusiones y observaciones del caso en base a\nlos resultados numéricos obtenidos en la fase experimental.