Búsqueda Dispersa paralela para la resolución del Problema a de la Diversidad Máxima

Abstract

Una gran cantidad de problemas que tienen interés en multitud de campos científicos y tecnológicos pueden enunciarse como problemas de optimización. La optimización constituye una disciplina fundamental en áreas como la Informática, la Inteligencia Artificial o la Investigación Operativa. Existe una colección importante de problemas de optimización para la que no se dispone de algoritmos exactos que permitan encontrar la solución óptima en tiempos razonables. Para resolver estos problemas, una alternativa consiste en diseñar algoritmos aproximados que encuentren soluciones de alta calidad en un tiempo que pueda asumirse. De entre todos los métodos aproximados destacan las metaheurísticas por su eficiencia, efectividad y flexibilidad. Éstas se han aplicado con éxito a una gran variedad de problemas de optimización. Aun teniendo en cuenta la eficiencia de estos algoritmos comparados con los algoritmos exactos, es cierto que requieren una gran capacidad de cómputo para ser ejecutados. Por lo tanto, este PFC surge por la necesidad de aprovechar la potencia de cómputo de las arquitecturas multicore para este tipo de algoritmos, lo que teóricamente debería suponer un salto en la eficiencia. Para eso, se partirá de un algoritmo secuencial bien conocido, y se realizará una versión paralela. Concretamente, se pretende aumentar la eficiencia del algoritmo metaheurístico conocido como Búsqueda Dispersa aplicado al problema de la Diversidad Máxima.