Búsqueda de Vecindad Variable secuencial y paralela: una aplicación al problema de la maximización del corte

Resumen

En este trabajo se propone un análisis comparativo de la implementación paralela y secuencial de un algoritmo basado en el es-quema Variable Neighborhood Search. La paralelización se lleva a cabo utilizando NVIDIA CUDA sobre GPU. Para ilustrar el comportamiento de ambas propuestas se utiliza el problema de la maximización del corte (MaxCut Problem -MCP). Dado un grafo G no dirigido, se define un corte como la división del conjunto de vértices de G en dos subconjuntos S y S ′ de forma que S ′ = V S. El MCP consiste entonces en encontrar el corte de máximo valor en G de entre todos los posibles. Para resolver dicho problema se propone un esquema basado en la estrategia Basic VNS. La paralelización se aplica a la búsqueda local, analizando las di-ferencias entre la búsqueda local paralela y la secuencial. Los resultados obtenidos muestran como la paralelización de la búsqueda local en GPU consigue reducir en gran medida el tiempo de ejecución, proporcionando soluciones de mayor calidad. 1. Introducción Se define un grafo G = (V, E), con n = |V | y m = |E|, como un conjunto de vértices V y el conjunto de aristas que los unen E. Siendo w ij el peso asociado con la arista (i, j) ∈ E, se define un corte(S, S ′) como la división de V en dos conjuntos S y S ′ = V S. El valor de dicho corte se calcula mediante la expresión corte(S, S ′) =

Jesús Sánchez-Oro

Profesor Titular de Universidad

Profesor Titular del Departamento de Informática, siendo uno de los investigadores principales del Grupo de Investigación de Algoritmos para la Optimización GRAFO.

Abraham Duarte

Catedrático de Universidad

Mi carrera investigadora se ha centrado en el desarrollo de nuevos algoritmos y técnicas de Inteligencia Computacional (metaheurísticas) y su aplicación a diferentes problemas en Ciencia e Ingeniería desde que me incorporé a la Universidad Rey Juan Carlos (URJC) en el octubre del año 2000.