Enhancement of artificial immune systems for the traveling salesman problem through hybridization with neighborhood improvement and parameter fine-tuning

• Autorzy: Thapatsuwan Peeraya , Thapatsuwan Warattapop , Kulworatit Chaichana

Identyfikatory

DOI

10.35784/acs-2024-43

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

artificial immune systems; fine-tuning; hybridization; traveling salesman problem

• Wydawca: Polskie Towarzystwo Promocji Wiedzy ; Lublin University of Technology
• Czasopismo: Applied Computer Science
• Rocznik: 2024
• Tom: Vol. 20, no. 4
• Strony: 117--137
• Opis fizyczny: Bibliogr. 49 poz., fig., tab.

Twórcy

autor

Thapatsuwan Peeraya

• Kasetsart University Kamphaeng Saen Campus, Faculty of Liberal Arts and Science, Department of Computational Science and Digital Technology

• https://orcid.org/0009-0007-4187-124X

autor

Thapatsuwan Warattapop

• Kasetsart University Kamphaeng Saen Campus, Faculty of Liberal Arts and Science, Department of Computational Science and Digital Technology

• https://orcid.org/0000-0001-7740-727X

autor

Kulworatit Chaichana

• IPB University, Faculty of Fisheries and Marine Sciences, Department of Marine Sciences and Technology, Indonesia

• https://orcid.org/0000-0001-9959-4264

Bibliografia

• [1] 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
• [2] 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
• [3] 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
• [4] 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
• [5] 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
• [6] 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
• [7] 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
• [8] Burnet, F. M. (1959). The clonal selection theory of acquired immunity; the Abraham Flexner lectures of Vanderbilt University. Cambridge University Press.
• [9] 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
• [10] 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
• [11] 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
• [12] De Castro, L., & Timmis, J. (2002). Artificial immune systems: A new computational intelligence approach. Springer.
• [13] De Castro, L., & Von Zuben, F. (2001). The clonal selection algorithm with engineering applications. Workshop Proceedings of GECCO (pp. 36-37).
• [14] 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
• [15] 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
• [16] 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
• [17] Dorigo, M., & Stützle, T. (2004). Ant Colony Optimization. MIT Press.
• [18] 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
• [19] Engin, O., & Döyen, A. (2004). Artificial immune systems and applications in industrial problems. Journal of Science, 17(1), 71-84.
• [20] 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
• [21] Garrett, S. M. (2005). How do we evaluate artificial immune systems? Evolutionary Computation, 13(2), 145-177. https://doi.org/10.1162/1063656054088512
• [22] 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
• [23] Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc.
• [24] 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
• [25] 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
• [26] 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
• [27] 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
• [28] 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
• [29] 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
• [30] 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
• [31] Eberhart, R. C., Shi, Y., & Kennedy, J. (2001). Swarm intelligence. Morgan Kaufmann Publishers Inc.
• [32] 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
• [33] 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
• [34] 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
• [35] 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
• [36] 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
• [37] 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
• [38] Lawler, E. L. (1985). The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization. John Wiley & Sons.
• [39] 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
• [40] 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
• [41] 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
• [42] 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
• [43] 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
• [44] 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
• [45] 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
• [46] Ruan, D. (1997). Intelligent hybrid systems : fuzzy logic, neural networks, and genetic algorithms. Springer.
• [47] 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
• [48] 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
• [49] 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

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025).