Un enfoque multi-objetivo para el problema de la máxima diversidad

Abstract

El problema de la maxima diversidad ha sido ampliamente estudiado desde diferentes perspectivas, haciendo uso de tecnicas exactas y heur ısticas. En este artıculo, nos enfrentamos a una variante multi-objetivo del problema, la cual intenta optimizar simultaneamente las cinco m etricas de diversidad cuyo uso esta m as extendido en la literatura. Para lograrlo, proponemos una novedosa adaptacion del ya conocido Greedy Randomized Adaptive Search Procedure, que ha sido usado tradicionalmente para optimizacion mono-objetivo. Con este nuevo enfoque, un conjunto de soluciones eficientes es generado siguiendo dos estrategias constructivas diferentes, analizando el rendimiento de ambas. La fase de mejora del algoritmo propuesto consiste en un procedimiento de busqueda local basado en una estructura de intercambios siguiendo un enfoque first improvement. Ademas, se propone una exploraci on inteligente de la vecindad que permita limitar el espacio de busqueda. Los experimentos computacionales muestran la calidad del algoritmo propuesto, comparado con los resultados obtenidos con el mejor metodo previo de la literatura. Las diferencias encontradas han sido respaldadas por pruebas estadısticas no parametricas.

Alejandra Casado

Artificial Intelligence Phd Student

My research interests include metaheuristics and combinatorial optimization.

Jesús Sánchez-Oro

Associate Professor

Associate Professor at the Computer Science Department, being one of the senior researchers of the Group for Research on Algorithms For Optimization GRAFO.

Eduardo García Pardo

Full Professor

One of the founders of the investigation group GRAFO, whose main line of research is the development of algorithms to tackle optimization problems, the topic of the researcher’s Doctoral Thesis and which their most notable publications are framed.