Mejora de las soluciones del problema del viajante múltiple mediante técnicas de aprendizaje automático y optimización de Harris Hawks
DOI:
https://doi.org/10.51252/rcsi.v4i2.745Palabras clave:
problemas de optimización combinatoria, inicialización, metaheurísticas, ajuste de parámetros, aprendizaje por refuerzoResumen
Este trabajo presenta un enfoque para resolver el Problema del Viajante Múltiple (mTSP) mediante la integración de algoritmos metaheurísticos (MHs) con técnicas de aprendizaje automático (ML). En particular, se desarrolló el algoritmo de Optimización Discreta de Halcones de Harris (DHHO) para manejar la naturaleza discreta del mTSP, ya que el algoritmo original de Optimización de Halcones de Harris (HHO) fue diseñado para problemas continuos. El algoritmo DHHO, mejorado con mecanismos de aprendizaje basados en SARSA para la inicialización de soluciones y ajuste de parámetros, mejora significativamente la eficiencia de las soluciones del mTSP. Al aprovechar la adaptabilidad del ML dentro del robusto marco de MH, este estudio ofrece una nueva perspectiva sobre los problemas de optimización combinatoria, superando las mejores soluciones conocidas (BKS) en varias instancias del mTSP. Los resultados se probaron utilizando instancias de referencia de TSPLIB, incluyendo Att48, Berlin52, Bier127, Pr76 y Rat99, para dos, tres y cuatro vendedores, logrando resultados óptimos en 12 de las 15 instancias. El rendimiento del DHHO se validó por la calidad de las soluciones y la consistencia a lo largo de múltiples ejecuciones, obteniendo resultados óptimos en 5 de 5 instancias para dos vendedores, 3 de 5 para tres vendedores y 4 de 5 para cuatro vendedores. La validación estadística mediante la prueba de rango con signo de Wilcoxon confirmó la significancia de estas mejoras (p < 0.05). Este trabajo destaca el impacto de integrar MHs y ML, contribuyendo de manera sustancial a la literatura actual.
Descargas
Citas
Belhor, M., El-Amraoui, A., Jemai, A., & Delmotte, F. (2023). Learning-Based Metaheuristic Approach for Home Healthcare Optimization Problem. Comput. Syst. Sci. Eng., 45(1), 1–19. https://doi.org/10.32604/csse.2023.029058 DOI: https://doi.org/10.32604/csse.2023.029058
Cheikhrouhou, O., & Khoufi, I. (2021). A comprehensive survey on the Multiple Traveling Salesman Problem: Applications, approaches and taxonomy. Computer Science Review, 40, 100369. https://doi.org/10.1016/j.cosrev.2021.100369 DOI: https://doi.org/10.1016/j.cosrev.2021.100369
de Castro Pereira, S., Solteiro Pires, E. J., & de Moura Oliveira, P. B. (2023). Ant-Balanced Multiple Traveling Salesmen: ACO-BmTSP. Algorithms, 16(1), 37. https://doi.org/10.3390/a16010037 DOI: https://doi.org/10.3390/a16010037
Ghani, J. A., Choudhury, I. A., & Hassan, H. H. (2004). Application of Taguchi method in the optimization of end milling parameters. Journal of Materials Processing Technology, 145(1), 84–92. https://doi.org/10.1016/S0924-0136(03)00865-3 DOI: https://doi.org/10.1016/S0924-0136(03)00865-3
Gulcu, S. D., & Ornek, H. K. (2019). Solution of multiple travelling salesman problem using particle swarm optimization based algorithms. International Journal of Intelligent Systems and Applications in Engineering, 7(2), 72–82. https://doi.org/10.18201//ijisae.2019252784 DOI: https://doi.org/10.18201/ijisae.2019252784
Guo, Y., Wang, Y., Yang, I.-H., & Sycara, K. (2023). Reinforcement learning methods for network-based transfer parameter selection. Intelligence & Robotics, 3(3), 402–419. https://doi.org/10.20517/ir.2023.23 DOI: https://doi.org/10.20517/ir.2023.23
Hamza, A., Darwish, A. H., & Rihawi, O. (2023). A new local search for the bees algorithm to optimize multiple traveling salesman problem. Intelligent Systems with Applications, 200242. https://doi.org/10.1016/j.iswa.2023.200242 DOI: https://doi.org/10.1016/j.iswa.2023.200242
He, P., Hao, J.-K., & Xia, J. (2024). Learning-guided iterated local search for the minmax multiple traveling salesman problem. ArXiv Preprint ArXiv:2403.12389. https://doi.org/10.48550/arXiv.2403.12389
Heidari, A. A., Mirjalili, S., Faris, H., Aljarah, I., Mafarja, M., & Chen, H. (2019). Harris hawks optimization: Algorithm and applications. Future Generation Computer Systems, 97, 849–872. https://doi.org/10.1016/j.future.2019.02.028 DOI: https://doi.org/10.1016/j.future.2019.02.028
Hildebrandt, F. D., Thomas, B. W., & Ulmer, M. W. (2023). Opportunities for reinforcement learning in stochastic dynamic vehicle routing. Computers & Operations Research, 150, 106071. https://doi.org/10.1016/j.cor.2022.106071 DOI: https://doi.org/10.1016/j.cor.2022.106071
Hussein, A. A., Yassen, E. T., & Rashid, A. N. (2023). Grey Wolf Optimizer for Green Vehicle Routing Problem. International Journal of Intelligent Engineering & Systems, 16(5). https://doi.org/10.22266/ijies2023.1031.53 DOI: https://doi.org/10.22266/ijies2023.1031.53
Kusumahardhini, N., Hertono, G. F., & Handari, B. D. (2020). Implementation of K-Means and crossover ant colony optimization algorithm on multiple traveling salesman problem. Journal of Physics: Conference Series, 1442(1), 012035. https://doi.org/10.1088/1742-6596/1442/1/012035 DOI: https://doi.org/10.1088/1742-6596/1442/1/012035
Latah, M. (2016). Solving multiple TSP problem by K-means and crossover based modified ACO algorithm. International Journal of Engineering Research and Technology, 5(02). https://doi.org/10.17577/IJERTV5IS020474
Liu, Y., & Cao, B. (2020). A novel ant colony optimization algorithm with Levy flight. Ieee Access, 8, 67205–67213. https://doi.org/10.1109/ACCESS.2020.2985498 DOI: https://doi.org/10.1109/ACCESS.2020.2985498
Mzili, I., Mzili, T., & Riffi, M. E. (2023). Efficient routing optimization with discrete penguins search algorithm for MTSP. Decision Making: Applications in Management and Engineering, 6(1), 730–743. https://doi.org/10.31181/dmame04092023m DOI: https://doi.org/10.31181/dmame04092023m
Nand, R., Chaudhary, K., & Sharma, B. (2024). Single Depot Multiple Travelling Salesman Problem Solved With Preference-Based Stepping Ahead Firefly Algorithm. IEEE Access, 12, 26655–26666. https://doi.org/10.1109/ACCESS.2024.3366183 DOI: https://doi.org/10.1109/ACCESS.2024.3366183
Pop, P. C., Cosma, O., Sabo, C., & Sitar, C. P. (2023). A Comprehensive Survey on the Generalized Traveling Salesman Problem. European Journal of Operational Research. https://doi.org/10.1016/j.ejor.2023.07.022 DOI: https://doi.org/10.1016/j.ejor.2023.07.022
Ramanathan, T., Suresh, S., & Rao, T. S. (2023). Multiple Depot MTSP using Genetic Algorithm and Reinforcement Learning. 2023 Second International Conference on Augmented Intelligence and Sustainable Systems (ICAISS), 440–446. https://doi.org/10.1109/ICAISS58487.2023.10250669 DOI: https://doi.org/10.1109/ICAISS58487.2023.10250669
Reinelt, G. (1991). TSPLIB—A traveling salesman problem library. ORSA Journal on Computing, 3(4), 376–384. https://doi.org/10.1287/ijoc.3.4.376 DOI: https://doi.org/10.1287/ijoc.3.4.376
Singh, A. (2016). A review on algorithms used to solve multiple travelling salesman problem. International Research Journal of Engineering and Technology (IRJET), 3(4), 598–603. https://www.irjet.net/archives/V3/i4/IRJET-V3I4120.pdf
Sui, J., Ding, S., Liu, R., Xu, L., & Bu, D. (2021). Learning 3-opt heuristics for traveling salesman problem via deep reinforcement learning. Asian Conference on Machine Learning, 1301–1316. https://proceedings.mlr.press/v157/sui21a
Taguchi, G., & Phadke, M. S. (1984). Quality engineering through design optimization. Quality Control, Robust Design, and the Taguchi Method, 77–96. https://doi.org/10.1007/978-1-4684-1472-1_5 DOI: https://doi.org/10.1007/978-1-4684-1472-1_5
Zhang, K., Yang, Z., & Başar, T. (2021). Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, 321–384. https://doi.org/10.1007/978-3-030-60990-0_12 DOI: https://doi.org/10.1007/978-3-030-60990-0_12
Descargas
Publicado
Cómo citar
Número
Sección
Licencia
Derechos de autor 2024 Ahmed Abdulmunem Hussein, Musa A. Hameed, Saddam Hamdan Ahmed
Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.
Los autores retienen sus derechos:
a. Los autores retienen sus derechos de marca y patente, y tambien sobre cualquier proceso o procedimiento descrito en el artículo.
b. Los autores retienen el derecho de compartir, copiar, distribuir, ejecutar y comunicar públicamente el articulo publicado en la Revista Científica de Sistemas e Informática (RCSI) (por ejemplo, colocarlo en un repositorio institucional o publicarlo en un libro), con un reconocimiento de su publicación inicial en la RCSI.
c. Los autores retienen el derecho a hacer una posterior publicación de su trabajo, de utilizar el artículo o cualquier parte de aquel (por ejemplo: una compilación de sus trabajos, notas para conferencias, tesis, o para un libro), siempre que indiquen la fuente de publicación (autores del trabajo, revista, volumen, número y fecha).
