Descripción:
RESUMEN: En este trabajo de investigación se presentan dos propuestas novedosas para resolver el problema de la mochila, un Algoritmo Genético Cuántico Híbrido (AGCH) y un Algoritmo Genético Cuántico Híbrido con Angulo de Rotación Adaptativa (AGCHA- RA). Ambas propuestas están basadas en ciertos principios de la mecánica cuántica aplicadas a la computación cuántica, tales como, superposición, entrelazamiento cuántico, y paralelismo cuántico. Además, utilizan un circuito cuántico de Deutsch-Jozsa para generar a su población cuántica, el cual trabaja de manera sinérgica como un operador de recombinación haploide y mutación tomando ventajas de las propiedades cuánticas antes mencionadas, generando nuevos individuos a partir de la explotación y exploración del espacio de búsqueda. Para el AGCHARA, se añadió un operador de ángulo de rotación adaptativo que ayuda a refinar a los nuevos individuos y disminuir los tiempos de convergencia hacía la solución óptima. Para probar el desempeño de ambas propuestas, se realizaron comparaciones con diferentes tipos de algoritmos. El AGCH se comparó con un Algoritmo Genético Cuántico Híbrido con qubits (AGCH-Q), un Algoritmo Evolutivo de Inspiración Cuántica con qubits (AEIC-Q), y un Algoritmo Genético Clásico (AG). El AGCHARA se comparó con un Algoritmo Evolutivo de Inspiración Cuántica con Ángulo de Rotación Adaptativa con operador de migración local (AEICARA-local), un Algoritmo Evolutivo de Inspiración Cuántica con Angulo de Rotación Adaptativa con operador de migración global (AEICARA-global), y un Algoritmo Genético Clásico (AG). Cabe mencionar que es tos algoritmos también son considerados como contribución, ya que fueron modificados para poder ser implementados en el simulador cuántico. Todos los algoritmos fueron implementados en el simulador Qiskit de IBM. El desempeño del AGCH se evaluó en tres conjuntos de datos fuertemente correlacionados; los resultados experimentales demostraron que el AGCH obtuvo las mejores soluciones en los tres conjuntos de datos comparado con sus similares cuánticos. Para el AGCHARA se realizaron tres pruebas estadísticas para verificar el desempeño general, tiempos de convergencia, precisión y exactitud. Los resultados demostraron que los algoritmos cuánticos se desempeñaron de manera similar pero mejor que el algoritmo clásico respecto a precisión y exactitud. Además, las pruebas estadísticas demostraron que nuestra propuesta cuántica es más rápida que sus similares cuánticos.
ABSTRACT: In this research work, two novel proposals are presented to solve the knapsack problem, a Hybrid Quantum Genetic Algorithm (HQGA) and a Hybrid Quantum Genetic Algorithm with Adaptative Rotation Angle (HQGAARA). Both proposals are based on quantum mechanics principles applied to quantum computing, such as, superposition, quantum entanglement, and quantum parallelism. In addition, they use a Deutsch-Jozsa quantum circuit to generate their quantum population, which works synergistically as a haploid recombination and mutation operator, taking advantage of the aforementioned quantum properties, generating new individuals from exploitation and exploration of the search space. For HQGAARA, an adaptive rotation angle operator was added to help refine new individuals and decrease convergence times to the optimal solution. To test the performance of both proposals, comparisons were made with different types of algorithms. The HQGA was compared with a Hybrid Quantum Genetic Algorithm with qubits (HQGA-Q), a Quantum-inspired Evolutionary Algorithm with qubits (QIEA-Q), and a Classical Genetic Algorithm (GA). The HQGAARA was compared with a Quantum Inspired Evolutionary Algorithm with a Adaptive Rotation Angle with local migration operator (QIEAARA-local), a Quantum Inspired Evolutionary Algorithm with a Adaptive Rotation Angle with global migration operator (QIEAARA-global), and a Classical Genetic Algorithm (GA). It is worth mentioning that these algorithms are also considered as a contribution, since they were modified to be implemented in the quantum simulator. All algorithms were implemented in the IBM Qiskit simulator. The performance of the HQGA was evaluated on three strongly correlated data sets; the experimental results indicated that the HQGA obtained the best solutions in the three data sets compared to its quantum peers. For the HQGAARA, three statistical tests were carried out to verify the general performance, convergence times, precision and accuracy. The results showed that the quantum algorithms performed similar but better than the classical algorithm regarding precision and accuracy. Furthermore, statistical tests showed that our quantum proposal is faster than its quantum counterparts.