Pengembangan Algoritma Kuantum Terinspirasi untuk Penyelesaian Masalah Optimasi Kompleks dalam Ilmu Komputasi

Yona Eka Pratiwi; Renatalia Fika

doi:10.59031/jnts.v1i2.773

Authors

Yona Eka Pratiwi Universitas Abdurachman Saleh Situbondo
Renatalia Fika Akademi Farmasi Dwi Farma Bukitinggi

DOI:

https://doi.org/10.59031/jnts.v1i2.773

Keywords:

Combinatorial Optimization, Quantum Computing, Quantum-Inspired Algorithms, Solution Accuracy, Time Convergence

Abstract

Quantum-Inspired Algorithms (QIAs) combine principles of quantum computing with classical evolutionary strategies to address complex optimization problems. This research explores the potential of QIAs in improving optimization processes, particularly in combinatorial and multi-objective optimization scenarios. The study focuses on the application of Quantum-Inspired Genetic Algorithms (QIGAs) and Quantum-Inspired Evolutionary Algorithms (QIEAs), assessing their effectiveness in solving classical problems like the Traveling Salesman Problem (TSP) and Minimum Spanning Tree (MST). Through computational simulations, the research compares the time convergence and solution accuracy of QIAs against traditional classical algorithms. The findings demonstrate that QIAs achieve faster convergence rates and higher-quality solutions, with accuracy levels reaching 98-99% of the global optimal solutions, while significantly reducing computational time. These results underline the advantages of QIAs in solving large and complex optimization problems, making them a promising alternative to traditional algorithms. Additionally, QIAs excel in avoiding local minima, a common pitfall of classical methods, due to their ability to explore the solution space more efficiently through quantum principles like superposition and interference. The implications of this study suggest that QIAs can be a valuable tool for tackling real-world optimization challenges, with potential applications in fields such as finance, logistics, telecommunications, and energy management. The research also indicates the necessity for further improvements in quantum-inspired algorithms' scalability and hardware integration, particularly for larger, more intricate optimization problems, to fully realize their potential in practical industrial applications.

References

Awasthi, A., Bär, F., Doetsch, J., Ehm, H., Erdmann, M., Hess, M., Klepsch, J., Limacher, P. A., Luckow, A., Niedermeier, C., Palackal, L., Pfeiffer, R., Ross, P., Safi, H., Schönmeier-Kromer, J., von Sicard, O., Wenger, Y., Wintersperger, K., & Yarkoni, S. (2023). Quantum computing techniques for multi-knapsack problems. Lecture Notes in Networks and Systems, 739 LNNS, 264-284. https://doi.org/10.1007/978-3-031-37963-5_19

Ayodele, M., Allmendinger, R., López-Ibáñez, M., & Parizy, M. (2022). Multi-objective QUBO solver: Bi-objective quadratic assignment problem. GECCO 2022 - Proceedings of the 2022 Genetic and Evolutionary Computation Conference, 467-475. https://doi.org/10.1145/3512290.3528698

Bansal, J. C., & Pal, N. R. (2019). Swarm and evolutionary computation. In Studies in Computational Intelligence, 779 (pp. 1-9). https://doi.org/10.1007/978-3-319-91341-4_1

Campos, R., Casares, P. A. M., & Martin-Delgado, M. A. (2023). Quantum Metropolis Solver: A quantum walks approach to optimization problems. Quantum Machine Intelligence, 5(2), Article 28. https://doi.org/10.1007/s42484-023-00119-y

Cohen, E., & Tamir, B. (2015). Quantum annealing – foundations and frontiers. European Physical Journal: Special Topics, 224(1), 89-110. https://doi.org/10.1140/epjst/e2015-02345-1

da Silveira, L. R., Tanscheit, R., & Vellasco, M. (2012). Quantum-inspired genetic algorithms applied to ordering combinatorial optimization problems. 2012 IEEE Congress on Evolutionary Computation, CEC 2012, art. no. 6256511. https://doi.org/10.1109/CEC.2012.6256511

Gidi, J., Candia, B., Muñoz-Moller, A. D., Rojas, A., Pereira, L., Muñoz, M., Zambrano, L., & Delgado, A. (2023). Stochastic optimization algorithms for quantum applications. Physical Review A, 108(3), 032409. https://doi.org/10.1103/PhysRevA.108.032409

Mandal, P. K. (2023). A review of classical methods and nature-inspired algorithms (NIAs) for optimization problems. Results in Control and Optimization, 13, 100315. https://doi.org/10.1016/j.rico.2023.100315

Pardalos, P. M., Žilinskas, A., & Žilinskas, J. (2017). A brief review of non-convex single-objective optimization. Springer Optimization and Its Applications, 123, 33-42. https://doi.org/10.1007/978-3-319-61007-8_4

Silveira, L. R., Tanscheit, R., & Vellasco, M. (2012). Quantum-inspired genetic algorithms applied to ordering combinatorial optimization problems. 2012 IEEE Congress on Evolutionary Computation, CEC 2012, art. no. 6256511. https://doi.org/10.1109/CEC.2012.6256511

Silveira, L. R., Tanscheit, R., & Vellasco, M. M. B. R. (2017). Quantum inspired evolutionary algorithm for ordering problems. Expert Systems with Applications, 67, 71-83. https://doi.org/10.1016/j.eswa.2016.08.067

Snyman, J. A., & Wilke, D. N. (2018). New gradient-based trajectory and approximation methods. In Springer Optimization and Its Applications, 133 (pp. 197-250). https://doi.org/10.1007/978-3-319-77586-9_6

Tirumala, S. S. (2018). A Quantum-Inspired Evolutionary Algorithm Using Gaussian Distribution-Based Quantization. Arabian Journal for Science and Engineering, 43(2), 471-482. https://doi.org/10.1007/s13369-017-2641-9

Vishwakarma, V. K. (2023). Quantum computing algorithms for nonlinear optimization problems. Communications on Applied Nonlinear Analysis, 30(4), 1-16. https://doi.org/10.52783/cana.v30.i4.279

Jones, R., & Anderson, J. (2024). Advances in computational optimization and their impact on machine learning. Computational Intelligence and Applications, 20(1), 45–67. https://doi.org/10.1016/j.cia.2024.01.006