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

Associate Professor

Miembro fundador del grupo de investigación GRAFO, cuya línea de investigación principal es el desarrollo de algoritmos para abordar problemas de optimización, temática sobre la que versa la Tesis Doctoral del investigador y en la que se enmarcan sus publicaciones más destacadas.