logo móvil
Contáctanos

Un algoritmo de aprendizaje profundo basado en una red de punteros de gráficos para resolver el problema del vendedor viajero

Autores: Perera, Jeewaka; Liu, Shih-Hsi; Mernik, Marjan; repinek, Matej; Ravber, Miha

Idioma: Inglés

Editor: MDPI

Año: 2023

Descargar PDF

Acceso abierto

Artículo científico
2023

Un algoritmo de aprendizaje profundo basado en una red de punteros de gráficos para resolver el problema del vendedor viajero


Categoría

Matemáticas

Subcategoría

Matemáticas generales

Palabras clave

Problemas del vendedor viajero
Multiobjetivo
Red de punteros de grafo profundo
Aprendizaje por refuerzo
Algoritmos evolutivos
Indicador de hipervolumen

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 30

Citaciones: Sin citaciones


Descripción
Los Problemas del Viajante de Comercio (TSPs) han sido un desafío interesante y duradero para los investigadores en diferentes áreas. La dificultad de tales problemas aumenta aún más cuando se consideran múltiples objetivos de manera simultánea. Se ha introducido mucho trabajo en algoritmos evolutivos para resolver TSPs multi-objetivo con resultados prometedores, y el trabajo en aprendizaje profundo y aprendizaje por refuerzo ha estado en aumento. Este artículo introduce un algoritmo de aprendizaje por refuerzo basado en redes de punteros gráficos profundos multi-objetivo (MODGRL) para TSPs multi-objetivo. El MODGRL mejora un algoritmo previo de aprendizaje por refuerzo profundo multi-objetivo, llamado DRL-MOA, al utilizar una red de punteros gráficos para aprender las estructuras gráficas de los TSPs. Tales mejoras permiten que MODGRL sea entrenado en un TSP a pequeña escala, pero pueda encontrar soluciones óptimas para TSPs a gran escala. NSGA-II, MOEA/D y SPEA2 son seleccionados para comparar con MODGRL y DRL-MOA. Los indicadores de calidad hipervolumen, dispersión y cobertura sobre el frente de Pareto (CPF) fueron seleccionados para evaluar el rendimiento de los algoritmos. En términos del indicador de hipervolumen que representa la convergencia y diversidad de los frentes de Pareto, MODGRL superó a todos los competidores en los tres problemas de referencia bien conocidos. Tales hallazgos demostraron que MODGRL, con la red de punteros gráficos mejorada, efectivamente tuvo un mejor desempeño, medido por el indicador de hipervolumen, que DRL-MOA y los otros tres algoritmos evolutivos. MODGRL y DRL-MOA fueron comparables en el grupo líder, medido por el indicador de dispersión. Aunque MODGRL tuvo un mejor desempeño que DRL-MOA, ambos fueron solo promedio en cuanto a la uniformidad y diversidad medida por el indicador CPF. Tales hallazgos recuerdan que diferentes indicadores de rendimiento miden los frentes de Pareto desde diferentes perspectivas. Elegir un indicador de rendimiento bien aceptado y adecuado para el diseño experimental es muy crítico, y puede afectar las conclusiones. También se experimentaron tres algoritmos evolutivos con iteraciones adicionales, para validar si las iteraciones adicionales afectaban el rendimiento. Los resultados muestran que NSGA-II y SPEA2 mejoraron considerablemente, medidos por los indicadores de dispersión y CPF. Tales hallazgos plantean preocupaciones de equidad sobre las comparaciones de algoritmos utilizando diferentes criterios de detención fijos para diferentes algoritmos, lo que apareció en el trabajo de DRL-MOA y muchos otros. A través de estas lecciones, concluimos que MODGRL efectivamente tuvo un mejor desempeño que DRL-MOA en términos de hipervolumen, y también instamos a los investigadores a realizar diseños experimentales y comparaciones justas, con el fin de obtener conclusiones científicamente sólidas.

Otros recursos que podrían interesarte

Temas Virtualpro