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

Resumen

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

Estudiante de Doctorado en Inteligencia Artificial

Mi investigación se centra en el uso de metaheuristicas y la resolución de problemas de optimización combinatoria.

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.

Eduardo García Pardo

Catedrático de Universidad

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.