Algoritmos de colonias de hormigas para optimización combinatoria con múltiples objetivos: aplicaciones a los problemas de minimum spanning trees

Abstract

El estudio de soluciones meta-heurísticas basadas en el paradigma del Ant Colony Optimization (ACO) para el Multiple Objective Minimum Spanning Trees y los problemas combinatorios relacionados es la principal preocupación de esta investigación. Es la clasificación comúnmente validada de la complejidad de los problemas, se clasifica el problema de las Multiple Objectiva Minimum Spanning Trees com o NP-completo. Además, como en la generalidad de los problemas de optimización con múltiples objetivos, la solución de un problema Multiple Objective Minimum Spanning Trees es un conjunto de soluciones de compromiso en el sentido que para mejorar uno de los objetivos es necesario por lo menos el empeorar uno los otros, lo que es una preocupación importante en un punto de vista práctico. En la primera parte de la investigación, se hace un análisis teórico del problema para complementar los resultados conocidos. Este análisis corrobora el hecho que en la práctica el uso de métodos exactos de solucionar los problemas Multiple Objective Minimum Spanning se aplica solamente en circunstancias específicas. Esto implica que el uso de métodos de aproximación se deben considerar como alternativa para solucionar el problema. Particularmente, se proponen dos métodos basados en el paradigma del ACO: el Multiple Objective Network optimization base don an ACO (MONACO) y el €-Depth ANT Explorer (€-DANTE). El MONACO utiliza un conjunto de los rastros de feromonas y heurísticas específicas para aproximar el conjunto de Pareto. El €-DANTE es una mejora del MONACO que aplica un procedimiento de búsqueda en profundidad, basado en las mejores soluciones que se obtiene durante el proceso, de modo a mejor explotar el espacio de la búsqueda. Los métodos propuestos son testados con problemas de múltiples objetivos seleccionados, mejorando los resultados obtenidos previamente por otros autores. Para testar los algoritmos MONACO y €-DANTI sobre el problema del Multiple Objective Minimum Spanning se ha propuesto la librería/repositorio de problemas de redes con múltiples objetivos, establecidos sobre de un conjunto sistematizado de generadores para las redes. Los resultados obtenidos con MONACO y €-DANTE son comparados con los resultados obtenidos con los métodos de Fuerza Bruta y de Medidas Ponderadas.