Review of Swarm Intelligence for Solving Symmetric Traveling Salesman Problem
DOI:
https://doi.org/10.48161/qaj.v3n2a141Keywords:
Swarm Intelligence, NP-Hard problem, Travels Salesman Problem (TSP), Particle Swarm Optimization (PSO), Artificial Bee Colony (ABC), Bat algorithm (BA), Ant Colony Algorithm (ACO)Abstract
Swarm Intelligence algorithms are computational intelligence algorithms inspired from the collective behavior of real swarms such as ant colony, fish school, bee colony, bat swarm, and other swarms in the nature. Swarm Intelligence algorithms are used to obtain the optimal solution for NP-Hard problems that are strongly believed that their optimal solution cannot be found in an optimal bounded time. Travels Salesman Problem (TSP) is an NP-Hard problem in which a salesman wants to visit all cities and return to the start city in an optimal time. In this article we are applying most efficient heuristic based Swarm Intelligence algorithms which are Particle Swarm Optimization (PSO), Artificial Bee Colony (ABC), Bat algorithm (BA), and Ant Colony Optimization (ACO) algorithm to find a best solution for TSP which is one of the most well-known NP-Hard problems in computational optimization. Results are given for different TSP problems comparing the best tours founds by BA, ABC, PSO and ACO.
Downloads
References
S. M. Almufti, “Historical survey on metaheuristics algorithms,” International Journal of Scientific World, vol. 7, no. 1, p. 1, Nov. 2019, doi: 10.14419/ijsw.v7i1.29497.
S. M. Almufti, A. Ahmad Shaban, R. Ismael Ali, and J. A. Dela Fuente, “Overview of Metaheuristic Algorithms,” Polaris Global Journal of Scholarly Research and Trends, vol. 2, no. 2, pp. 10–32, Apr. 2023, doi: 10.58429/pgjsrt.v2n2a144.
Asaad, R. R., Abdurahman, S. M., & Hani, A. A. (2017). Partial Image Encryption using RC4 Stream Cipher Approach and Embedded in an Image. Academic Journal of Nawroz University, 6(3), 40–45. https://doi.org/10.25007/ajnu.v6n3a76
S. M. Almufti, R. B. Marqas, P. S. Othman, and A. B. Sallow, “Single-based and population-based metaheuristics for solving np-hard problems,” Iraqi Journal of Science, vol. 62, no. 5, pp. 1710–1720, May 2021, doi: 10.24996/ijs.2021.62.5.34.
Rajab Asaad, R., & Masoud Abdulhakim, R. (2021). The Concept of Data Mining and Knowledge Extraction Techniques. Qubahan Academic Journal, 1(2), 17–20. https://doi.org/10.48161/qaj.v1n2a43
A. Acan and A. Unveren, “A shared-memory ACO+GA hybrid for combinatorial optimization,” in 2007 IEEE Congress on Evolutionary Computation, IEEE, Sep. 2007, pp. 2078–2085. doi: 10.1109/CEC.2007.4424729.
Asaad, R. R., Ahmad, H. B., & Ali, R. I. (2020). A Review: Big Data Technologies with Hadoop Distributed Filesystem and Implementing M/R. Academic Journal of Nawroz University, 9(1), 25–33. https://doi.org/10.25007/ajnu.v9n1a530
T. Dokeroglu, E. Sevinc, T. Kucukyilmaz, and A. Cosar, “A survey on new generation metaheuristic algorithms,” Comput Ind Eng, vol. 137, p. 106040, Nov. 2019, doi: 10.1016/j.cie.2019.106040.
Asaad, R. R. (2019). Güler and Linaro et al Model in an Investigation of the Neuronal Dynamics using noise Comparative Study. Academic Journal of Nawroz University, 8(3), 10–16. https://doi.org/10.25007/ajnu.v8n3a360
A. W. Marashdih, Z. F. Zaaba, S. M. Almufti, and Z. Fitri Zaaba, “The Problems and Challenges of Infeasible Paths in Static Analysis Bat Algorithm (BA): Literature Review various types and its Applications View project Hybrid Metaheuristic in solving NP-Hard Problem View project The Problems and Challenges of Infeasible Paths in Static Analysis,” International Journal of Engineering & Technology, pp. 412–417, 2018, doi: 10.14419/ijet.v7i4.19.23175.
Asaad, R. R. (2021). Penetration Testing: Wireless Network Attacks Method on Kali Linux OS. Academic Journal of Nawroz University, 10(1), 7–12. https://doi.org/10.25007/ajnu.v10n1a998
A. Yahya Zebari, S. M. Almufti, and C. Mohammed Abdulrahman, “Bat algorithm (BA): review, applications and modifications,” International Journal of Scientific World, vol. 8, no. 1, p. 1, Jan. 2020, doi: 10.14419/ijsw.v8i1.30120.
Asaad, R. R., & Abdulnabi, N. L. (2018). Using Local Searches Algorithms with Ant Colony Optimization for the Solution of TSP Problems. Academic Journal of Nawroz University, 7(3), 1–6. https://doi.org/10.25007/ajnu.v7n3a193
F. S. Abu-Mouti and M. E. El-Hawary, “Overview of Artificial Bee Colony (ABC) algorithm and its applications,” in 2012 IEEE International Systems Conference SysCon 2012, IEEE, Mar. 2012, pp. 1–6. doi: 10.1109/SysCon.2012.6189539.
Asaad, R. R., & Ali, R. I. (2019). Back Propagation Neural Network(BPNN) and Sigmoid Activation Function in Multi-Layer Networks. Academic Journal of Nawroz University, 8(4), 216–221. https://doi.org/10.25007/ajnu.v8n4a464
S. Almufti, “Using Swarm Intelligence for solving NPHard Problems,” Academic Journal of Nawroz University, vol. 6, no. 3, pp. 46–50, 2017, doi: 10.25007/ajnu.v6n3a78.
Rajab Asaad, R. (2021). Review on Deep Learning and Neural Network Implementation for Emotions Recognition . Qubahan Academic Journal, 1(1), 1–4. https://doi.org/10.48161/qaj.v1n1a25
J. Kennedy and R. Eberhart, “Particle swarm optimization,” in Proceedings of ICNN’95 - International Conference on Neural Networks, IEEE, pp. 1942–1948. doi: 10.1109/ICNN.1995.488968.
Asaad, R. R., Abdulrahman, S. M., & Hani, A. A. (2017). Advanced Encryption Standard Enhancement with Output Feedback Block Mode Operation. Academic Journal of Nawroz University, 6(3), 1–10. https://doi.org/10.25007/ajnu.v6n3a70
Ridwan B. Marqas, Saman M. Almufti, Pawan Shivan Othman, and Chyavan Mohammed Abdulrahman, “Evaluation of EHO, U-TACO and TS Metaheuristics algorithms in Solving TSP,” JOURNAL OF XI’AN UNIVERSITY OF ARCHITECTURE & TECHNOLOGY, vol. XII, no. IV, Apr. 2020, doi: 10.37896/jxat12.04/1062.
Abdulfattah, G. M., Ahmad, M. N., & Asaad, R. R. (2018). A reliable binarization method for offline signature system based on unique signer’s profile. INTERNATIONAL JOURNAL OF INNOVATIVE COMPUTING INFORMATION AND CONTROL, 14(2), 573-586.
R. Asaad and N. Abdulnabi, “Using Local Searches Algorithms with Ant Colony Optimization for the Solution of TSP Problems,” Academic Journal of Nawroz University, vol. 7, no. 3, pp. 1–6, 2018, doi: 10.25007/ajnu.v7n3a193.
Asaad, R. R., Sulaiman, Z. A., & Abdulmajeed, S. S. (2019). Proposed System for Education Augmented Reality Self English Learning. Academic Journal of Nawroz University, 8(3), 27–32. https://doi.org/10.25007/ajnu.v8n3a366
S. M. Almufti, “U-Turning Ant Colony Algorithm powered by Great Deluge Algorithm for the solution of TSP Problem.”
Asaad, R. R. (2020). Implementation of a Virus with Treatment and Protection Methods. ICONTECH INTERNATIONAL JOURNAL, 4(2), 28-34. https://doi.org/10.46291/ICONTECHvol4iss2pp28-34
S. M. Almufti, “U-Turning Ant Colony Algorithm powered by Great Deluge Algorithm for the solution of TSP Problem.”
Boya Marqas, R., M. Almufti, S., & Rajab Asaad, R. (2022). FIREBASE EFFICIENCY IN CSV DATA EXCHANGE THROUGH PHP-BASED WEBSITES. Academic Journal of Nawroz University, 11(3), 410–414. https://doi.org/10.25007/ajnu.v11n3a1480
S. M. Almufti, R. B. Marqas, P. S. Othman, and A. B. Sallow, “Single-based and population-based metaheuristics for solving np-hard problems,” Iraqi Journal of Science, vol. 62, no. 5, 2021, doi: 10.24996/ijs.2021.62.5.34.
Ihsan, R. R., Almufti, S. M., Ormani, B. M., Asaad, R. R., & Marqas, R. B. (2021). A survey on Cat Swarm Optimization algorithm. Asian J. Res. Comput. Sci, 10, 22-32.
A. Gogna and A. Tayal, “Metaheuristics: review and application,” Journal of Experimental & Theoretical Artificial Intelligence, vol. 25, no. 4, pp. 503–526, Dec. 2013, doi: 10.1080/0952813X.2013.782347.
Rajab Asaad, R., & Luqman Abdulnabi, N. (2022). A Review on Big Data Analytics between Security and Privacy Issue. Academic Journal of Nawroz University, 11(3), 178–184. https://doi.org/10.25007/ajnu.v11n3a1446
S. M. Almufti, R. Boya Marqas, and V. Ashqi Saeed, “Taxonomy of bio-inspired optimization algorithms,” Journal of Advanced Computer Science & Technology, vol. 8, no. 2, p. 23, Aug. 2019, doi: 10.14419/jacst.v8i2.29402.
Yahya Hussien , A., & Rajab Asaad, R. (2022). Review on Social Media and Digital Security. Qubahan Academic Journal, 2(2), 1–4. https://doi.org/10.48161/qaj.v2n2a119
S. M. Almufti and A. A. Shaban, “U-Turning Ant Colony Algorithm for Solving Symmetric Traveling Salesman Problem,” Academic Journal of Nawroz University, vol. 7, no. 4, p. 45, Dec. 2018, doi: 10.25007/ajnu.v7n4a270.
Asaad, R. R. (2022). Keras Deep Learning for Pupil Detection Method . Academic Journal of Nawroz University, 10(4), 240–250. https://doi.org/10.25007/ajnu.v10n4a1328
S. M. Almufti, A. Yahya Zebari, and H. Khalid Omer, “A comparative study of particle swarm optimization and genetic algorithm,” Journal of Advanced Computer Science & Technology, vol. 8, no. 2, p. 40, Oct. 2019, doi: 10.14419/jacst.v8i2.29401.
Asaad, R. R., & Segerey, R. I. (2018). School Management Application Using iOS. Academic Journal of Nawroz University, 7(4), 38–44. https://doi.org/10.25007/ajnu.v7n4a269
S. M. Almufti, “Hybridizing Ant Colony Optimization Algorithm for Optimizing Edge-Detector Techniques,” Academic Journal of Nawroz University, vol. 11, no. 2, pp. 135–145, May 2022, doi: 10.25007/ajnu.v11n2a1320.
Asaad, R. R., Saeed, V. A., & Abdulhakim, R. M. (2021). Smart Agent and it’s effect on Artificial Intelligence: A Review Study. ICONTECH INTERNATIONAL JOURNAL, 5(4), 1-9.
M. T. Adham and P. J. Bentley, “An artificial ecosystem algorithm applied to the travelling salesman problem,” in GECCO 2014 - Companion Publication of the 2014 Genetic and Evolutionary Computation Conference, Association for Computing Machinery, 2014, pp. 155–156. doi: 10.1145/2598394.2598438.
Asaad, R. R., & Saeed, V. A. (2022). A Cyber Security Threats, Vulnerability, Challenges and Proposed Solution. Applied Computing Journal, 2(4), 227-244. https://doi.org/10.52098/acj.202260
S. M. Almufti, R. Boya Marqas, and R. R. Asaad, “Comparative study between elephant herding optimization (EHO) and U-turning ant colony optimization (U-TACO) in solving symmetric traveling salesman problem (STSP),” Journal of Advanced Computer Science & Technology, vol. 8, no. 2, p. 32, Aug. 2019, doi: 10.14419/jacst.v8i2.29403.
Renas Rajab Asaad. (2022). Support vector machine classification learning algorithm for diabetes prediction. International Research Journal of Science, Technology, Education, and Management, 2(2), 26–34. https://doi.org/10.5281/zenodo.6975670
D. A. Zebari, S. S. Sadiq and D. M. Sulaiman, "Knee Osteoarthritis Detection Using Deep Feature Based on Convolutional Neural Network," 2022 International Conference on Computer Science and Software Engineering (CSASE), Duhok, Iraq, 2022, pp. 259-264, doi: 10.1109/CSASE51777.2022.9759799.
J. Luis and C. Sequera, “7 Tune Up of a Genetic Algorithm to Group Documentary Collections.” [Online]. Available: www.intechopen.com
Ibrahim, D. A., Zebari, D. A., Mohammed, H. J., & Mohammed, M. A. (2022). Effective hybrid deep learning model for COVID-19 patterns identification using CT images. Expert Systems, 39( 10), e13010. https://doi.org/10.1111/exsy.13010
D. A. Zebari, D. M. Sulaiman, S. S. Sadiq, N. A. Zebari and M. S. Salih, "Automated Detection of Covid-19 from X-ray Using SVM," 2022 4th International Conference on Advanced Science and Engineering (ICOASE), Zakho, Iraq, 2022, pp. 130-135, doi: 10.1109/ICOASE56293.2022.10075586.
A. Acan, H. Altincay, Y. Tekol, and A. Unveren, “A genetic algorithm with multiple crossover operators for optimal frequency assignment problem,” in The 2003 Congress on Evolutionary Computation, 2003. CEC ’03., IEEE, pp. 256–263. doi: 10.1109/CEC.2003.1299583.
D. A. Zebari, H. Haron, D. M. Sulaiman, Y. Yusoff and M. N. Mohd Othman, "CNN-based Deep Transfer Learning Approach for Detecting Breast Cancer in Mammogram Images," 2022 IEEE 10th Conference on Systems, Process & Control (ICSPC), Malacca, Malaysia, 2022, pp. 256-261, doi: 10.1109/ICSPC55597.2022.10001781.
“Genetic Algorithm based Feature Selection Technique for Writer Verification: A case study with Handwritten Bangla Document ARTICLE TYPE Genetic Algorithm based Feature Selection Technique for Writer Verification: A case study with Handwritten Bangla Document.”
D. A. Zebari, A. R. Abrahim, D. A. Ibrahim, G. M. Othman and F. Y. H. Ahmed, "Analysis of Dense Descriptors in 3D Face Recognition," 2021 IEEE 11th International Conference on System Engineering and Technology (ICSET), Shah Alam, Malaysia, 2021, pp. 171-176, doi: 10.1109/ICSET53708.2021.9612430.
Sadeeq, H. T., Abdulazeez, A. M., Kako, N. A., Zebari, D. A., & Zeebaree, D. Q. (2021). A New Hybrid Method for Global Optimization Based on the Bird Mating Optimizer and the Differential Evolution. 2021 7th International Engineering Conference “Research & Innovation amid Global Pandemic" (IEC), 54–60. https://doi.org/10.1109/IEC52205.2021.9476147
S. M. Almufti, R. R. Asaad, and B. W. Salim, “Review on Elephant Herding Optimization Algorithm Performance in Solving Optimization Problems,” Article in International Journal of Engineering and Technology, vol. 7, no. 4, pp. 6109–6114, 2018, doi: 10.14419/ijet.v7i4.23127.
D. A. Zebari, D. A. Ibrahim and A. Al-Zebari, "Suspicious Region Segmentation Using Deep Features in Breast Cancer Mammogram Images," 2022 International Conference on Computer Science and Software Engineering (CSASE), Duhok, Iraq, 2022, pp. 253-258, doi: 10.1109/CSASE51777.2022.9759633.
S. M. Almufti, R. R. Asaad, and B. W. Salim, “Review on Elephant Herding Optimization Algorithm Performance in Solving Optimization Problems,” Article in International Journal of Engineering and Technology, vol. 7, no. 4, pp. 6109–6114, 2018, doi: 10.14419/ijet.v7i4.23127.
I. Fister, X.-S. Yang, D. Fister, and I. Fister, “Cuckoo Search: A Brief Literature Review,” 2014, pp. 49–62. doi: 10.1007/978-3-319-02141-6_3.
Mustafa Zebari, G. ., Assad Zebari, D. . ., & Al-zebari, A. . (2021). FUNDAMENTALS OF 5G CELLULAR NETWORKS: A REVIEW. Journal of Information Technology and Informatics, 1(1), 1–5. https://doi.org/10.6084
I. Fister, X.-S. Yang, D. Fister, and I. Fister, “Cuckoo Search: A Brief Literature Review,” 2014, pp. 49–62. doi: 10.1007/978-3-319-02141-6_3.
D. A. Zebari, D. M. Sulaiman, S. S. Sadiq, N. A. Zebari and M. S. Salih, "Automated Detection of Covid-19 from X-ray Using SVM," 2022 4th International Conference on Advanced Science and Engineering (ICOASE), Zakho, Iraq, 2022, pp. 130-135, doi: 10.1109/ICOASE56293.2022.10075586.
S. Almufti, “The novel Social Spider Optimization Algorithm: Overview, Modifications, and Applications,” ICONTECH INTERNATIONAL JOURNAL, vol. 5, no. 2, pp. 32–51, Jun. 2021, doi: 10.46291/icontechvol5iss2pp32-51.
D. A. Zebari, H. Haron, D. M. Sulaiman, Y. Yusoff and M. N. Mohd Othman, "CNN-based Deep Transfer Learning Approach for Detecting Breast Cancer in Mammogram Images," 2022 IEEE 10th Conference on Systems, Process & Control (ICSPC), Malacca, Malaysia, 2022, pp. 256-261, doi: 10.1109/ICSPC55597.2022.10001781.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Qubahan Academic Journal
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
