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

Abstract

Este trabajo trata sobre la aplicación de dos algoritmos de búsqueda a la selección de individuos óptimos en la población inicial de un algoritmo genético, y la consiguiente comparación entre ambos. El primero de ellos es el algoritmo meta-heurístico GRASP, y el segundo es el algoritmo cuántico de Grover. El algoritmo cuántico de Grover forma parte de una nueva generación en las ciencias de la computación: la computación cuántica. Y por tanto hace uso de conceptos matemáticos y físicos completamente distintos a los usados en la programación clásica. En esta tesis se presenta un análisis general de ambos algoritmos, siendo de especial mención el análisis del algoritmo cuántico de Grover, ya que incluye un modelo matemático del funcionamiento del mismo. Este modelo será de suma importancia para simular la ejecución del algoritmo de Grover en una computadora clásica, dada la carencia de una computadora cuántica sobre la cual realizar esto. Luego, se preparan dos procesos experimentales, los cuales se usarán para realizar la comparación de eficacia y eficiencia entre las ejecuciones de los dos algoritmos. Posteriormente, se presenta el diseño e implementación de los algoritmos, ambos aplicados a la selección de individuos de un algoritmo genético genérico. Una vez ambos algoritmos se encuentren correctamente implementados y funcionales, se ejecutarán las pruebas experimentales que permitan realizar la comparación entre ellos. Finalmente se realizan las conclusiones y observaciones del caso en base a los resultados numéricos obtenidos en la fase experimental.