IMPLEMENTATION OF GENETIC ALGORITHM ACCELERATOR ON FPGA FOR TRAVELING SALESMAN PROBLEM AND PERFORMING COMPARATIVE PERFORMANCE ANALYSIS

Yıl 2026, Cilt: 10 Sayı: 1 , 176 - 191 , 30.04.2026

Cem Deniz Kumral

https://doi.org/10.46519/ij3dptdi.1856787

https://izlik.org/JA25CE63NG

Öz

The primary objective of this study is to perform a comprehensive comparative performance analysis between traditional processor-based systems and hardware-oriented architectures for solving the Traveling Salesman Problem (TSP). On this way, a high-performance and scalable Genetic Algorithm (GA) accelerator was designed and implemented on a Xilinx Artix-7 Field-Programmable Gate Array (FPGA) using VHSIC Hardware Description Language (VHDL). The proposed architecture employs a Dual-Port Block RAM (BRAM) structure and a 4-stage parallel pipeline to overcome the computational bottlenecks and memory access latencies inherent in serial Central Processing Units (CPU) execution. The performance of the developed system was benchmarked against a Python-based CPU implementation using TSPLIB datasets. Experimental results reveal that the FPGA-based accelerator provides a big advantage, achieving a speedup ratio of up to 121.24x on used datasets. This comparative analysis demonstrates that the proposed hardware-based approach offers a superior, cost-effective, and deterministic alternative to software-based solutions for real-time optimization and Edge AI applications.

Anahtar Kelimeler

Genetic Algorithm , FPGA , VHDL , TSP , Hardware Acceleration , Performance Analysis.

Kaynakça

• 1. Pop, P.C., Cosma, O., Sabo, C. and Sitar, C.P., “A comprehensive survey on the generalized traveling salesman problem”, European Journal of Operational Research, Vol. 314, Issue 3, Pages 819-835, 2024.
• 2. Alam, T., Qamar, S., Dixit, A. and Benaida, M., “Genetic algorithm: Reviews, implementations, and applications”, arXiv preprint arXiv:2007.12673, 2020.
• 3. Katoch, S., Chauhan, S.S. and Kumar, V., “A review on genetic algorithm: past, present, and future”, Multimedia Tools and Applications, Vol. 80, Issue 5, Pages 8091-8126, 2021.
• 4. Harada, T. and Alba, E., “Parallel genetic algorithms: a useful survey”, ACM Computing Surveys (CSUR), Vol. 53, Issue 4, Pages 1-39, 2020.
• 5. Zhou, P., “Study on CPU and FPGA in Artificial Intelligence and Machine Learning”, 2024 13th International Conference of Information and Communication Technology (ICTech), Pages 1-5, Wuhan, 2024.
• 6. Seng, K.P., Lee, P.J. and Ang, L.M., “Embedded Intelligence on FPGA: Survey, Applications and Challenges”, Electronics, Vol. 10, Issue 8, Pages 895, 2021.
• 7. Kumral, C.D., Topal, A., Ersoy, M., Çolak, R. and Yiğit, T., “Performing Performance Analysis by Implementing Random Forest Algorithm on FPGA”, El-Cezeri, Vol. 9, Issue 4, Pages 1315-1327, 2022.
• 8. Koyuncu, İ., Taşdemir, M.F., Alçın, M., Tuna, M. and Coşgun, E., “Real time realization of image processing algorithms on FPGA”, Journal of Balikesir University Institute of Science and Technology, Vol. 24, Issue 1, Pages 125-137, 2022.
• 9. Doan, N.A.V., Manuel, M., Conrady, S., Kreddig, A. and Stechele, W., “Parameter Optimization of Approximate Image Processing Algorithms in FPGAs”, 2020 Eighth International Symposium on Computing and Networking Workshops (CANDARW), Pages 74-80, Naha, 2020.
• 10. Grubeša, S., Stamać, J., Suhanek, M. and Petošić, A., “Use of Genetic Algorithms for Design an FPGA-Integrated Acoustic Camera”, Sensors, Vol. 22, Issue 8, Pages 2851, 2022.
• 11. Chakraborty, A., Dutta, S., Chakrabarti, I. and Banerjee, A., “VLSI architecture of stochastic genetic algorithm for real-time training of deep neural network”, Sādhanā, Vol. 49, Issue 175, Pages 1-7, 2024.
• 12. Kaziha, O., Bonny, T. and Jarndal, A., “Genetic Algorithm Augmented Inception-Net based Image Classifier Accelerated on FPGA”, Multimedia Tools and Applications, Vol. 82, Pages 45097–45125, 2023.
• 13. Alqudah, E. and Jarrah, A., “Parallel implementation of genetic algorithm on FPGA using Vivado high level synthesis”, Int. J. Bio-Inspired Computation, Vol. 15, Issue 2, Pages 90-99, 2020.
• 14. Noordin, N.H., Eu, P.S. and Ibrahim, Z., “FPGA Implementation of Metaheuristic Optimization Algorithm”, e-Prime - Advances in Electrical Engineering, Electronics and Energy, Vol. 6, Pages 100377, 2023.
• 15. Zermani, M.A., Manita, G., Chhabra, A., Feki, E. and Mami, A., “FPGA-based hardware implementation of chaotic opposition-based arithmetic optimization algorithm”, Applied Soft Computing, Vol. 154, Pages 111352, 2024.
• 16. Jiang, Q., Xu, J. and Chen, Y., “A Genetic Algorithm for Scheduling in Heterogeneous Multicore System Integrated with FPGA”, 2021 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Pages 1-8, New York, 2021.
• 17. Yiu, Y.F. and Mahapatra, R., “Heuristic Function Evolution for Pathfinding Algorithm in FPGA Accelerator”, 2020 IEEE Third International Conference on Artificial Intelligence and Knowledge Engineering (AIKE), Pages 1-6, Laguna Hills, 2020.
• 18. Malhotra, G., Duraiswamy, P. and Kishore, J.K., “FPGA Accelerated Parallel HsClone GA for Digital Circuit Configuration in CGP Format”, J. Inst. Eng. India Ser. B, Vol. 104, Issue 5, Pages 1079–1089, 2023.
• 19. Garcia, L.H., Alkamil, A., Mohsin, M.A., Menzel, J. and Perera, D.G., “FPGA-Based Hardware Architecture for Sequence Alignment by Genetic Algorithm”, 2025 IEEE International Symposium on Circuits and Systems (ISCAS), Pages 1-5, London, 2025.
• 20. Wu, C., Zhang, K. and Zhang, X., “FPGA-Based Speed Control Strategy of PMSM Using Improved Beetle Antennae Search Algorithm”, Energies, Vol. 17, Issue 8, Pages 1870, 2024.
• 21. Doroshenko, A., Shymkovych, V., Yatsenko, O. and Mamedov, T., “Automated Software Design for FPGAs on an Example of Developing a Genetic Algorithm”, Proceedings of the 11th International Conference on DESSERT, Pages 1-12, Kyiv, 2021.
• 22. Barbareschi, M., Barone, S., Bosio, A., Han, J. and Traiola, M., “A Genetic-algorithm-based Approach to the Design of DCT Hardware Accelerators”, ACM Journal on Emerging Technologies in Computing Systems, Vol. 18, Issue 3, Pages 1-22, 2022.
• 23. Danilova, E.Y. and Kovylyaev, D.A., “Advanced Genetic Algorithm for the Embedded FPGA Logic Diagnostic”, 2021 International Conference on Information and Digital Technologies (IDT), Pages 93-97, Zilina, 2021.
• 24. Guo, S., Stern, R., Zhang, H. and Pang, L., “Speedy light focusing through scattering media by a cooperatively FPGA-parameterized genetic algorithm”, Optics Express, Vol. 30, Issue 20, Pages 36414-36423, 2022.
• 25. Lotfy, A., Kaveh, M., Mosavi, M.R. and Rahmati, A.R., “An enhanced fuzzy controller based on improved genetic algorithm for speed control of DC motors”, Analog Integrated Circuits and Signal Processing, Vol. 105, Issue 1, Pages 141–155, 2020.
• 26. Holland, J.H., “Genetic Algorithms”, Scientific American, Vol. 267, Issue 1, Pages 66-73, 1992
• 27. Whitley, D., “A genetic algorithm tutorial”, Statistics and Computing, Vol. 4, Issue 2, Pages 65-85, 1994.
• 28. Rose, J., El Gamal, A. and Sangiovanni-Vincentelli, A., “Architecture of field-programmable gate arrays”, Proceedings of the IEEE, Vol. 81, Issue 7, Pages 1013-1029, 1993.
• 29. Monmasson, E. and Cirstea, M.N., “FPGA Design Methodology for Industrial Control Systems—A Review”, IEEE Transactions on Industrial Electronics, Vol. 54, Issue 4, Pages 1824-1842, 2007.
• 30. Reinelt, G., “TSPLIB—A Traveling Salesman Problem Library”, ORSA Journal on Computing, Vol. 3, Issue 4, Pages 376-384, 1991.