Método mejorado para la paralelización de metaheurísticas evolutivas
Autores: Díaz, Diego; Valledor, Pablo; Ena, Borja; Iglesias, Miguel; Menéndez, César
Idioma: Inglés
Editor: MDPI
Año: 2020
Acceso abierto
Artículo científico
2020
Método mejorado para la paralelización de metaheurísticas evolutivas
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Método
Metaheurísticas basadas en población
Instancias
Algoritmos genéticos
Optimización de colonias de hormigas
Problemas del Vendedor Viajero
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 34
Citaciones: Sin citaciones
Este trabajo presenta un método para la distribución de cualquier metaheurística basada en poblaciones. Mejora el enfoque ingenuo de múltiples ejecuciones independientes, al tiempo que agrega una sobrecarga insignificante. Los métodos existentes que coordinan instancias a través de un clúster suelen requerir algún compromiso de un diseño más complejo, cargas de comunicación más altas y una tasa de propagación de soluciones, lo que requiere más trabajo para desarrollar y más recursos para ejecutar. El objetivo del nuevo método no es lograr resultados de vanguardia, sino proporcionar un método base mejor que múltiples ejecuciones independientes. El concepto principal del método es que una de las instancias recibe actualizaciones con la mejor solución actual de todas las demás instancias. Este trabajo describe el enfoque general y su particularización tanto a algoritmos genéticos como a optimización por colonia de hormigas para resolver Problemas del Viajante de Comercio (TSPs). También incluye pruebas extensas en los problemas de referencia de TSPLIB para evaluar la calidad de las soluciones y el rendimiento en cualquier momento (calidad de la solución versus tiempo para alcanzarla). Estas pruebas muestran que el nuevo método produce mejores soluciones para aproximadamente dos tercios de los problemas y soluciones equivalentes en el tercio restante, y muestra consistentemente un mejor rendimiento en cualquier momento.
Descripción
Este trabajo presenta un método para la distribución de cualquier metaheurística basada en poblaciones. Mejora el enfoque ingenuo de múltiples ejecuciones independientes, al tiempo que agrega una sobrecarga insignificante. Los métodos existentes que coordinan instancias a través de un clúster suelen requerir algún compromiso de un diseño más complejo, cargas de comunicación más altas y una tasa de propagación de soluciones, lo que requiere más trabajo para desarrollar y más recursos para ejecutar. El objetivo del nuevo método no es lograr resultados de vanguardia, sino proporcionar un método base mejor que múltiples ejecuciones independientes. El concepto principal del método es que una de las instancias recibe actualizaciones con la mejor solución actual de todas las demás instancias. Este trabajo describe el enfoque general y su particularización tanto a algoritmos genéticos como a optimización por colonia de hormigas para resolver Problemas del Viajante de Comercio (TSPs). También incluye pruebas extensas en los problemas de referencia de TSPLIB para evaluar la calidad de las soluciones y el rendimiento en cualquier momento (calidad de la solución versus tiempo para alcanzarla). Estas pruebas muestran que el nuevo método produce mejores soluciones para aproximadamente dos tercios de los problemas y soluciones equivalentes en el tercio restante, y muestra consistentemente un mejor rendimiento en cualquier momento.