ENHANCEMENT OF ARTIFICIAL IMMUNE SYSTEMS FOR THE TRAVELING SALESMAN PROBLEM THROUGH HYBRIDIZATION WITH NEIGHBORHOOD IMPROVEMENT AND PARAMETER FINE-TUNING
Peeraya THAPATSUWAN
Department of Computational Science and Digital Technology, Faculty of Liberal Arts and Science, Kasetsart University Kamphaeng Saen Campus (Thailand)
https://orcid.org/0009-0007-4187-124X
Warattapop THAPATSUWAN
warattapop.t@ku.thDepartment of Computational Science and Digital Technology, Faculty of Liberal Arts and Science, Kasetsart University Kamphaeng Saen Campus (Thailand)
https://orcid.org/0000-0001-7740-727X
Chaichana KULWORATIT
Department of Computer Science, School of Science, King Mongkut’s Institute of Technology Ladkrabang (Thailand)
https://orcid.org/0000-0001-9959-4264
Abstract
This research investigates the enhancement of Artificial Immune Systems (AIS) for solving the Traveling Salesman Problem (TSP) through hybridization with Neighborhood Improvement (NI) and parameter fine-tuning. Two main experiments were conducted: Experiment A identified the optimal integration points for NI within AIS, revealing that position 2 (AIS+NIpos2) improved solution quality by an average of 27.78% compared to other positions. Experiment B benchmarked AIS performance with various enhancement techniques. Using symmetric and asymmetric TSP datasets, the results showed that integrating NI at strategic points and fine-tuning parameters boosted AIS performance by up to 46.27% in some cases. The hybrid and fine-tuned version of AIS (AIS-th) consistently provided the best solution quality, with up to a 50.36% improvement, though it required more computational time. These findings emphasize the importance of strategic combinations and fine-tuning for creating effective optimization algorithms.
Keywords:
Artificial Immune Systems, Fine-Tuning, Hybridization, Traveling Salesman ProblemReferences
Adenso-Díaz, B., & Laguna, M. (2006). Fine-Tuning of algorithms using fractional experimental designs and local search. Operations Research, 54(1), 99-114. https://doi.org/10.1287/opre.1050.0243
Google Scholar
Akhand, M. A. H., Akter, S., & Rashid, M. A. (2014). Velocity Tentative Particle Swarm Optimization to solve TSP. 2013 International Conference on Electrical Information and Communication Technology (EICT) (pp. 1-6). IEEE. https://doi.org/10.1109/EICT.2014.6777868
Google Scholar
Akram, M., & Habib, A. (2023). Hybridizing simulated annealing and genetic algorithms with Pythagorean fuzzy uncertainty for Traveling Salesman Problem optimization. Journal of Applied Mathematics and Computing, 69, 4451-4497. https://doi.org/10.1007/s12190-023-01935-y
Google Scholar
Blum, C., & Roli, A. (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys, 35(3), 268-308. https://doi.org/10.1145/937503.937505
Google Scholar
Boryczka, U., & Szwarc, K. (2019). The Harmony Search algorithm with additional improvement of harmony memory for Asymmetric Traveling Salesman Problem. Expert Systems with Applications, 122, 43-53. https://doi.org/10.1016/j.eswa.2018.12.044
Google Scholar
Braun, H. (1991). On solving travelling salesman problems by genetic algorithms. In H.-P. Schwefel & R. Männer (Eds.), Parallel Problem Solving from Nature (Vol. 496, pp. 129-133). Springer-Verlag. https://doi.org/10.1007/BFb0029743
Google Scholar
Burke, E. K., Cowling, P. I., & Keuthen, R. (2001). Effective local and guided variable neighbourhood search methods for the asymmetric travelling salesman problem. In E. J. W. Boers (Ed.), Applications of Evolutionary Computing (Vol. 2037, pp. 203-212). Springer Berlin Heidelberg. https://doi.org/10.1007/3-540-45365-2_21
Google Scholar
Burnet, F. M. (1959). The clonal selection theory of acquired immunity; the Abraham Flexner lectures of Vanderbilt University. Cambridge University Press.
Google Scholar
Campuzano, G., Obreque, C., & Aguayo, M. M. (2020). Accelerating the Miller–Tucker–Zemlin model for the asymmetric Traveling Salesman Problem. Expert Systems with Applications, 148, 113229. https://doi.org/10.1016/j.eswa.2020.113229
Google Scholar
Chandrasekaran, M., Asokan, P., Kumanan, S., Balamurugan, T., & Nickolas, S. (2006). Solving job shop scheduling problems using artificial immune system. International Journal of Advanced Manufacturing Technology, 31, 580-593. https://doi.org/10.1007/s00170-005-0226-3
Google Scholar
Chen, S.-M., & Chien, C.-Y. (2011). Solving the Traveling Salesman Problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques. Expert Systems with Applications, 38(12), 14439-14450. https://doi.org/10.1016/j.eswa.2011.04.163
Google Scholar
De Castro, L., & Timmis, J. (2002). Artificial immune systems: A new computational intelligence approach. Springer.
Google Scholar
De Castro, L., & Von Zuben, F. (2001). The clonal selection algorithm with engineering applications. Workshop Proceedings of GECCO (pp. 36-37).
Google Scholar
Deng, W., Chen, R., He, B., Liu, Y., Yin, L., & Guo, J. (2012). A novel two-stage hybrid swarm intelligence optimization algorithm and application. Soft Computing, 16, 1707-1722. https://doi.org/10.1007/s00500-012-0855-z
Google Scholar
Desrochers, M., & Laporte, G. (1991). Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints. Operations Research Letters, 10(1), 27-36. https://doi.org/10.1016/0167-6377(91)90083-2
Google Scholar
Dorigo, M., & Gambardella, L. M. (1997). Ant colonies for the travelling salesman problem. Biosystems, 43(2), 73-81. https://doi.org/10.1016/S0303-2647(97)01708-5
Google Scholar
Dorigo, M., & Stützle, T. (2004). Ant Colony Optimization. MIT Press.
Google Scholar
Eiben, A. E., & Smit, S. K. (2011). Parameter tuning for configuring and analyzing evolutionary algorithms. Swarm and Evolutionary Computation, 1(1), 19-31. https://doi.org/10.1016/j.swevo.2011.02.001
Google Scholar
Engin, O., & Döyen, A. (2004). Artificial immune systems and applications in industrial problems. Journal of Science, 17(1), 71-84.
Google Scholar
Freitas, A. A., & Timmis, J. (2003). Revisiting the foundations of artificial immune systems: A problem-oriented perspective. In J. Timmis, P. J. Bentley, & E. Hart (Eds.), Artificial Immune Systems (Vol. 2787, pp. 229-241). Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-540-45192-1_22
Google Scholar
Garrett, S. M. (2005). How do we evaluate artificial immune systems? Evolutionary Computation, 13(2), 145-177. https://doi.org/10.1162/1063656054088512
Google Scholar
Glover, F. W. (1989). Tabu Search - Part I. ORSA Journal on Computing, 1(3), 190-206. https://doi.org/10.1287/ijoc.1.3.190
Google Scholar
Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc.
Google Scholar
Gouveia, L., & Pires, J. M. (1999). The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints. European Journal of Operational Research, 112(1), 134-146. https://doi.org/10.1016/S0377-2217(97)00358-5
Google Scholar
Greensmith, J., Whitbrook, A., & Aickelin, U. (2010). Artificial immune systems. In M. Gendreau & J.-Y. Potvin (Eds.), Handbook of Metaheuristics (Vol. 146, pp. 421–448). Springer US. https://doi.org/10.1007/978-1-4419-1665-5_14
Google Scholar
Hart, E., & Timmis, J. (2008). Application areas of AIS: The past, the present and the future. Applied Soft Computing, 8(1), 191-201. https://doi.org/10.1016/j.asoc.2006.12.004
Google Scholar
Huang, C., Li, Y., & Yao, X. (2019). A survey of automatic parameter tuning methods for metaheuristics. IEEE Transactions on Evolutionary Computation, 24(2), 201-216. https://doi.org/10.1109/TEVC.2019.2921598
Google Scholar
Joy, G., Huyck, C., & Yang, X.-S. (2023). Review of parameter tuning methods for nature-inspired algorithms. In X.-S. Yang (Ed.), Benchmarks and Hybrid Algorithms in Optimization and Applications (pp. 33–47). Springer Nature Singapore. https://doi.org/10.1007/978-981-99-3970-1_3
Google Scholar
Kang-Ping, W., Lan, H., Chun-Guang, Z., & Wei, P. (2003). Particle swarm optimization for Traveling Salesman Problem. 2003 International Conference on Machine Learning and Cybernetics (pp. 1583-1585). IEEE. https://doi.org/10.1109/ICMLC.2003.1259748
Google Scholar
Karaboga, D., & Gorkemli, B. (2011). A combinatorial Artificial Bee Colony algorithm for Traveling Salesman Problem. 2011 International Symposium on Innovations in Intelligent Systems and Applications (pp. 50-53). IEEE. https://doi.org/10.1109/INISTA.2011.5946125
Google Scholar
Eberhart, R. C., Shi, Y., & Kennedy, J. (2001). Swarm intelligence. Morgan Kaufmann Publishers Inc.
Google Scholar
Khan, I., & Maiti, M. K. (2019). A swap sequence based Artificial Bee Colony algorithm for Traveling Salesman Problem. Swarm and Evolutionary Computation, 44, 428-438. https://doi.org/10.1016/j.swevo.2018.05.006
Google Scholar
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671-680. https://doi.org/10.1126/science.220.4598.671
Google Scholar
Krishna, M., Panda, N., & Majhi, S. (2021). Solving Traveling Salesman Problem using Hybridization of Rider Optimization and Spotted Hyena Optimization Algorithm. Expert Systems with Applications, 183, 115353. https://doi.org/10.1016/j.eswa.2021.115353
Google Scholar
Laporte, G. (1992). The Traveling Salesman Problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(2), 231-247. https://doi.org/10.1016/0377-2217(92)90138-Y
Google Scholar
Laporte, G., & Nobert, Y. (1980). A Cutting Planes Algorithm for the m-Salesmen Problem. The Journal of the Operational Research Society, 31(11), 1017-1023. https://doi.org/10.2307/2581282
Google Scholar
Larrañaga, P., Kuijpers, C. M. H., Murga, R. H., Inza, I., & Dizdarevic, S. (1999). Genetic algorithms for the Travelling Salesman Problem: A Review of representations and operators. Artificial Intelligence Review, 13, 129-170. https://doi.org/10.1023/A:1006529012972
Google Scholar
Lawler, E. L. (1985). The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization. John Wiley & Sons.
Google Scholar
Li, M., Ma, J., Zhang, Y., Zhou, H., & Liu, J. (2015). Firefly algorithm solving multiple Traveling Salesman Problem. Journal of Computational and Theoretical Nanoscience, 12(7), 1277-1281. https://doi.org/10.1166/jctn.2015.3886
Google Scholar
Miller, C. E., Tucker, A. W., & Zemlin, R. A. (1960). Integer programming formulation of Traveling Salesman Problems. Journal of the ACM, 7(4), 326-329. https://doi.org/10.1145/321043.321046
Google Scholar
Nagata, Y., & Soler, D. (2012). A new genetic algorithm for the asymmetric Traveling Salesman Problem. Expert Systems with Applications, 39(10), 8947-8953. https://doi.org/10.1016/j.eswa.2012.02.029
Google Scholar
Osaba, E., Ser, J. D., Sadollah, A., Bilbao, M. N., & Camacho, D. (2018). A discrete water cycle algorithm for solving the symmetric and asymmetric Traveling Salesman Problem. Applied Soft Computing, 71, 277-290. https://doi.org/10.1016/j.asoc.2018.06.047
Google Scholar
Osaba, E., Yang, X.-S., Diaz, F., Lopez-Garcia, P., & Carballedo, R. (2016). An improved discrete bat algorithm for symmetric and asymmetric Traveling Salesman Problems. Engineering Applications of Artificial Intelligence, 48, 59-71. https://doi.org/10.1016/j.engappai.2015.10.006
Google Scholar
Panwar, K., & Deep, K. (2021). Discrete Grey Wolf Optimizer for symmetric Traveling Salesman Problem. Applied Soft Computing, 105, 107298. https://doi.org/10.1016/j.asoc.2021.107298
Google Scholar
Reinelt, G. (1991). TSPLIB - A Traveling Salesman Problem Library. ORSA Journal on Computing, 3(4), 267-384. https://doi.org/10.1287/ijoc.3.4.376
Google Scholar
Ruan, D. (1997). Intelligent hybrid systems : fuzzy logic, neural networks, and genetic algorithms. Springer.
Google Scholar
Sengupta, S., Basak, S., & Peters, R. A. (2019). Particle swarm optimization: A survey of historical and recent developments with hybridization perspectives. Machine Learning and Knowledge Extraction, 1(1), 157-191. https://doi.org/10.3390/make1010010
Google Scholar
Yang, X.-S. (2023). Nature-Inspired algorithms in optimization: Introduction, hybridization, and insights. In X.-S. Yang (Ed.), Benchmarks and Hybrid Algorithms in Optimization and Applications (pp. 1–17). Springer Nature Singapore. https://doi.org/10.1007/978-981-99-3970-1_1
Google Scholar
Zhang, T., Zhou, Y., Zhou, G., Deng, W., & Luo, Q. (2023). Discrete Mayfly Algorithm for spherical asymmetric Traveling Salesman Problem. Expert Systems with Applications, 221, 119765. https://doi.org/10.1016/j.eswa.2023.119765
Google Scholar
Authors
Peeraya THAPATSUWANDepartment of Computational Science and Digital Technology, Faculty of Liberal Arts and Science, Kasetsart University Kamphaeng Saen Campus Thailand
https://orcid.org/0009-0007-4187-124X
Authors
Warattapop THAPATSUWANwarattapop.t@ku.th
Department of Computational Science and Digital Technology, Faculty of Liberal Arts and Science, Kasetsart University Kamphaeng Saen Campus Thailand
https://orcid.org/0000-0001-7740-727X
Authors
Chaichana KULWORATITDepartment of Computer Science, School of Science, King Mongkut’s Institute of Technology Ladkrabang Thailand
https://orcid.org/0000-0001-9959-4264
Statistics
Abstract views: 66PDF downloads: 21
License
This work is licensed under a Creative Commons Attribution 4.0 International License.
All articles published in Applied Computer Science are open-access and distributed under the terms of the Creative Commons Attribution 4.0 International License.
Similar Articles
- Konrad PIETRYKOWSKI, Tytus TULWIN, THE NONUNIFORMITY OF THE PISTON MOTION OF THE RADIAL ENGINE , Applied Computer Science: Vol. 13 No. 2 (2017)
- Dariusz PLINTA, Martin KRAJČOVIČ, APPLICATION OF THE AUGMENTED REALITY IN PRODUCTION PRACTICE , Applied Computer Science: Vol. 13 No. 2 (2017)
- Janani DEWMINI, W Madushan FERNANDO, Izabela Iwa NIELSEN, Grzegorz BOCEWICZ, Amila THIBBOTUWAWA, Zbigniew BANASZAK, IDENTIFYING THE POTENTIAL OF UNMANNED AERIAL VEHICLE ROUTING FOR BLOOD DISTRIBUTION IN EMERGENCY REQUESTS , Applied Computer Science: Vol. 19 No. 4 (2023)
- Zbigniew CZYŻ, Paweł KARPIŃSKI, Krzysztof SKIBA, Szymon BARTKOWSKI, NUMERICAL CALCULATIONS OF WATER DROP USING A FIREFIGHTING AIRCRAFT , Applied Computer Science: Vol. 19 No. 3 (2023)
- Sahar ZAMANI KHANGHAH, Keivan MAGHOOLI, EMOTION RECOGNITION FROM HEART RATE VARIABILITY WITH A HYBRID SYSTEM COMBINED HIDDEN MARKOV MODEL AND POINCARE PLOT , Applied Computer Science: Vol. 20 No. 1 (2024)
- Anna MACHROWSKA, Robert KARPIŃSKI, Józef JONAK, Jakub SZABELSKI, NUMERICAL PREDICTION OF THE COMPONENT-RATIO-DEPENDENT COMPRESSIVE STRENGTH OF BONE CEMENT , Applied Computer Science: Vol. 16 No. 3 (2020)
- KK Praneeth Tellakula, Saravana Kumar R, Sanjoy Deb, A SURVEY OF AI IMAGING TECHNIQUES FOR COVID-19 DIAGNOSIS AND PROGNOSIS , Applied Computer Science: Vol. 17 No. 2 (2021)
- Łukasz WOJCIECHOWSKI, Tadeusz CISOWSKI, MODEL OF A COMPUTER SYSTEM FOR SELECTION OF OPERATING PARAMETERS FOR TRANSPORT VEHICLES IN THE ASPECT OF THEIR DURABILITY , Applied Computer Science: Vol. 14 No. 4 (2018)
- Mohammed A. Hussein, Ekhlas H. Karam, Rokaia S. Habeeb, CANCER GROWTH TREATMENT USING IMMUNE LINEAR QUADRATIC REGULATOR BASED ON CROW SEARCH OPTIMIZATION ALGORITHM , Applied Computer Science: Vol. 17 No. 2 (2021)
- Nancy WOODS, Gideon BABATUNDE, A ROBUST ENSEMBLE MODEL FOR SPOKEN LANGUAGE RECOGNITION , Applied Computer Science: Vol. 16 No. 3 (2020)
<< < 1 2 3 4 5 6 7 8 9 10 > >>
You may also start an advanced similarity search for this article.
