Solving scheduling problems with ant colony optimization metaheuristic and high performance computing

Abstract

La resolución de problemas NP-hard presenta un desafío computacional debido al crecimiento exponencial del espacio de búsqueda. La computación de alto rendimiento (HPC) junto con las metaheurísticas se utilizan comúnmente para abordar estos problemas. HPC proporciona un entorno adecuado para trabajar con problemas de optimización combinatoria que presentan gran complejidad, utilizando computación paralela. La computación paralela permite la división del problema entre varias unidades de cómputo utilizando diferentes enfoques de comunicación y sincronización. Las metaheurísticas son procedimientos de alto nivel que generan soluciones casi óptimas a un problema de optimización. Aunque los algoritmos exactos pueden encontrar el máximo global, el tiempo de ejecución de estos métodos crece exponencialmente. Por lo tanto, para trabajar con problemas grandes y complejos, los algoritmos aproximados como las metaheurísticas son usados más frecuentemente. La optimización por colonia de hormigas (ACO) es una metaheurística de población con una naturaleza inherentemente paralela, que ha demostrado buenos resultados de rendimiento y tiempo. Este trabajo tiene como objetivo estudiar la paralelización de ACO mediante la interfaz de paso de mensajes (MPI) y la programación de unidades de procesamiento de gráficos (GPU) utilizando la plataforma CUDA. Basándonos en las implementaciones paralelas existentes de ACO basadas en MPI y CUDA, analizamos los detalles de la paralelización de los dos componentes principales del algoritmo, la construcción de soluciones y el procedimiento de actualización de feromonas. El algoritmo basado en MPI está implementado con un enfoque de grano grueso, y la comunicación entre procesadores se realiza después de un cierto número de iteraciones siguiendo un enfoque maestro-esclavo. La estrategia de intercambio de mensajes está guiada por un nodo raíz que transmite la información requerida a otros nodos y luego recibe las soluciones parciales construidas independientemente por cada nodo. La paralelización de ACO basada en CUDA también sigue un enfoque de grano grueso y divide el trabajo realizado en la construcción de soluciones entre diferentes hilos, uno por cada hormiga. El proceso de actualización de feromonas se realiza de forma atómica para evitar accesos simultáneos a la misma estructura de memoria. Los algoritmos evaluados se implementaron con un proceso incremental, donde técnicas de profiling nos permitieron optimizar los algoritmos. Se utilizaron varias instancias del problema del viajante y el problema de job shop scheduling para evaluar los algoritmos. También un problema de segmentación de imágenes fue evaluado utilizando ACO. Las métricas de speedup, eficiencia y Karp-Flatt se utilizaron para evaluar MPI utilizando hasta 48 procesadores. Además, el tiempo de ejecución, el número de iteraciones y la precisión se utilizaron para evaluar MPI y CUDA utilizando HPC.