TY - GEN
T1 - Hybrid-Computing for Finding Solutions to NP-Complete Problems in Graphs Using Ant Colony Optimization
AU - Villarruel-Mosquera, Valery A.
AU - Gabriela Zumarraga, Maria
AU - Ospina, Alejandra
AU - Riofrio, Daniel
AU - Benitez, Diego
AU - Perez, Noel
AU - Grijalva, Felipe
AU - Moyano, Ricardo Flores
AU - Baldeon-Calisto, Maria
N1 - Publisher Copyright:
© 2023 IEEE.
PY - 2023
Y1 - 2023
N2 - Finding solutions to NP-Complete problems is colloquially related to finding a needle in a haystack because of its complexity, which, in consequence, yields exponential time algorithms. In particular, one strategy to find "good solutions"to these problems is to evaluate potential solutions generated at random and measure the quality of each in every attempt. However, true randomness cannot be implemented on classical computers. Hence it is emulated through algorithms that create pseudo-random numbers. This paper analyzes two NP-complete problems in graphs: the Traveling Salesman and the Hamiltonian path problems. The Ant Colony Optimization algorithm was used to find solutions to these with different random number generators: pseudo-random and quantum-random. The convergence time and overall cost of varying graph setups (different complexity levels, i.e. 50, 100, 150, and 200 nodes) were compared under both random number generators. The results indicate that, generally, when quantum random number generators are used, faster convergence is achieved and better results are obtained.
AB - Finding solutions to NP-Complete problems is colloquially related to finding a needle in a haystack because of its complexity, which, in consequence, yields exponential time algorithms. In particular, one strategy to find "good solutions"to these problems is to evaluate potential solutions generated at random and measure the quality of each in every attempt. However, true randomness cannot be implemented on classical computers. Hence it is emulated through algorithms that create pseudo-random numbers. This paper analyzes two NP-complete problems in graphs: the Traveling Salesman and the Hamiltonian path problems. The Ant Colony Optimization algorithm was used to find solutions to these with different random number generators: pseudo-random and quantum-random. The convergence time and overall cost of varying graph setups (different complexity levels, i.e. 50, 100, 150, and 200 nodes) were compared under both random number generators. The results indicate that, generally, when quantum random number generators are used, faster convergence is achieved and better results are obtained.
KW - ACO
KW - HPP
KW - Pseudo random numbers
KW - Quantum computing
KW - Random numbers
KW - TSP
UR - https://www.scopus.com/pages/publications/85186142733
U2 - 10.1109/ROPEC58757.2023.10409466
DO - 10.1109/ROPEC58757.2023.10409466
M3 - Contribución a la conferencia
AN - SCOPUS:85186142733
T3 - Proceedings of the 25th Autumn Meeting on Power, Electronics and Computing, ROPEC 2023
BT - Proceedings of the 25th Autumn Meeting on Power, Electronics and Computing, ROPEC 2023
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 25th Autumn Meeting on Power, Electronics and Computing, ROPEC 2023
Y2 - 18 October 2023 through 20 October 2023
ER -