Una implementación de la meta-heurística “Optimización en Mallas Variables” en la arquitectura CUDA

Resumen

En el campo de la optimización, tanto académico como industrial los problemas que se presentan a diario son a menudo complicados y NP-difícil. La solución computacional de los mismos no puede llevarse a cabo de una manera exacta en un plazo de tiempo razonable, y el uso de recursos de hardware de cómputo para esta solución aumenta considerablemente. Para lidiar con tal asunto, el diseño de los métodos de solución debe estar basado en el uso conjunto de los enfoques avanzados de la optimización combinatoria y los métodos de paralelismo a gran escala. En las últimas décadas, en la rama de la Inteligencia Artificial las meta-heurísticas basadas en poblaciones representan una poderosa herramienta para la solución de problemas complejos. El objetivo de este trabajo es exponer los resultados obtenidos a partir de la aplicación de técnicas paralelas utilizando la arquitectura CUDA a la meta-heurística “Optimización en Mallas Variables”, con el propósito de lograr una mejora en el costo temporal. Las etapas más costosas del algoritmo en el proceso de expansión y contracción de la malla para la obtención de la nueva población inicial son implementadas en paralelo. Los resultados obtenidos fueron validados utilizando una versión secuencial de la meta-heurística. Los tiempos de ejecución de ambos algoritmos se comparan, mostrándose mejoras sustanciales en la versión paralela con el uso de CUDA.