Evaluación de Rendimiento y Precisión de Metaheurísticas Híbridas Paralelas en un Cluster Multicore

Abstract

En los últimos años las tendencias más relevantes para lograr el diseño de metaheurísticas eficientes han estado acompañadas por estrategias de hibridación y paralelismo. Si bien existen diversos tipos de problemas que actualmente son resueltos de forma aceptable mediante la utilización de algoritmos secuenciales. A medida que la complejidad incrementa, dichas implementaciones suelen volverse ineficientes e incluso obsoletas. Siendo necesario utilizar herramientas que permitan ofrecer resultados más eficientes. En este tipo de escenarios, la computación paralela se ha convertido en la forma tradicional de resolver problemas con altas cargas de procesamiento. Desde el punto de vista de exactitud o precisión, cuando trabajamos con problemas del tipo NP-duros, los algoritmos exactos suelen tener tiempos de ejecución que crecen de forma exponencial en relación al tamaño del problema haciéndolos inoperables antes este tipo de escenarios. Para este tipo de problemas, las metaheurísticas suelen ser una buena elección ya que ofrecen resultados de buena calidad en tiempos razonables. En este trabajo se evalúan -en términos de rendimiento y presición- diferentes estrategias de hibridación colaborativa utilizando combinaciones de las siguientes metaheurísticas: Algoritmos Genéticos, Evolución Diferencial, Optimización por Cúmulo de Partículas y Optimización por Colonia de Hormigas. Las implementaciones han sido llevadas a cabo en un cluster multicore utilizando programación paralela basada en MPI y OpenMP.