A constructive search method using selection based on diversity

Abstract

Este trabajo propone una nueva búsqueda heurística, denominada Búsqueda Diversa (DS), para resolver problemas de optimización combinatoria. Al igual que beam search, este enfoque constructivo expande sólo un subconjunto seleccionado de las soluciones en cada nivel del árbol de búsqueda. Sin embargo, en lugar de seleccionar las soluciones con los mejores valores, DS utiliza un método de selección que promueve la diversidad para elegir un subconjunto diverso de ellas, tras filtrar las que no son interesantes para la búsqueda. En este contexto, la diversidad se entiende como una medida de la distancia entre las soluciones, que permite a la búsqueda evitar la convergencia prematura. Se exploran, proponen y mejoran métodos de selección eficientes que promueven la diversidad. Además, se analiza un método de poda que permite filtrar soluciones innecesarias en el caso particular de los problemas submodulares. DS también detecta las soluciones que no producen mejores descendientes, y utiliza cada una de ellas como punto de partida para un proceso de búsqueda local. La intuición es que la combinación de estas estrategias permite alcanzar más –y más diversos– óptimos locales, aumentando las posibilidades de encontrar el óptimo global. Se desarrolla una descripción formal y general del algoritmo. Esta descripción se valida, en primer lugar, implementando un solver para problemas de localización como el Simple Plant Location Problem (SPLP) y el problema p-median. Estrategias de paralelización para los componentes de DS fueron analizadas e incluídas en esta implementación, que se deja como software de código abierto. En segundo lugar, a través de experimentos sobre benchmarks de la literatura, comparando tanto la calidad de las soluciones obtenidas como los tiempos de ejecución con otros métodos del estado del arte. Estos experimentos también se utilizaron para determinar los componentes y parámetros más eficaces para el algoritmo. Con el uso de un proceso de post-optimización con Path Relinking, DS puede lograr resultados de la misma calidad que el estado del arte en tiempos de CPU similares. Además, DS demostró ser ligeramente mejor en promedio para problemas de gran escala con tamaños de solución pequeños, demostrando ser un algoritmo eficiente que entrega un conjunto de soluciones buenas y diversas