Mejora de las soluciones del problema del viajante múltiple mediante técnicas de aprendizaje automático y optimización de Harris Hawks

Abstract

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.

Keywords

• problemas de optimización combinatoria
• inicialización
• metaheurísticas
• ajuste de parámetros
• aprendizaje por refuerzo