Algoritmos de búsqueda con retroceso para problemas multicriterio

Abstract

La búsqueda en grafos, con multitud de aplicaciones en el mundo real, ha propiciado el diseño de una gran cantidad de algoritmos centrados en el procesamiento de un único objetivo, magnitud representativa del coste. Sin embargo, un tratamiento realista de estos problemas requiere en muchas ocasiones contemplar diferentes objetivos de modo simultáneo. Además, es habitual que estos objetivos sean antagónicos, de tal modo que la optimización de uno de ellos se traduzca en el empeoramiento de uno o varios de los objetivos restantes. Esto hace que el coste óptimo no sea único, sino que generalmente existe un conjunto de soluciones óptimas cuyas componentes de coste están compensadas entre sí.

Esta naturaleza multiobjetivo de los problemas provoca que el rendimiento de los algoritmos empeore de modo considerable, ya que al procesamiento habitual de los nodos generados durante el proceso de búsqueda hay que añadir el tratamiento de vectores de coste (de dimensión igual al número de objetivos considerado) y el manejo de un conjunto de soluciones óptimas (cuyo tamaño en el peor de los casos será exponencial), siendo este tipo de operaciones muy costosas desde el punto de vista de tiempo y memoria.

De las dos principales clases de algoritmos exactos multiobjetivo, la correspondiente a un enfoque "best-first" ha sido ampliamente estudiada, dando lugar a una gran cantidad de algoritmos que persiguen reducir la complejidad espacial y temporal del proceso de búsqueda. Asimismo existen numerosas y detalladas comparativas de rendimiento entre estos algoritmos. Sin embargo la clase de algoritmos "depth-first", aún siendo de gran utilidad en la resolución de problemas con grafo de búsqueda en forma de árbol, presentaba un reducido número de propuestas, careciendo además de análisis comparativos entre las mismas.

Esta tesis pretende cubrir dicho hueco, realizando un estudio sistemático de algoritmos exactos multiobjetivo de tipo "depth-first. Para ello, por un lado se realiza una caracterización detallada de dichos algoritmos, contribuyendo con nuevos diseños multiobjetivo, variantes de algoritmos para un objetivo que aplican los conceptos de "Frontera de Pareto" y "Punto Ideal" a la cota de expansión empleada en la búsqueda "depth-first". De todos estos nuevos algoritmos se aporta su correspondiente análisis formal. Asimismo se realizan adaptaciones de algoritmos multiobjetivo ya existentes, de tal modo que sean aplicables a árboles infinitos, el principal tipo de problemas usado en el análisis de rendimiento realizado en este trabajo.

Por otro lado, en esta tesis se realiza un análisis empírico detallado de los algoritmos mencionados. Para ello en primer lugar se determinan los principales parámetros de rendimiento a tener en cuenta en función de la naturaleza multiobjetivo de los problemas considerados. Concretamente el tiempo de ejecución, en combinación con el tamaño de la cota de expansión, se perfilan como los factores clave de rendimiento. Los resultados obtenidos en las pruebas realizadas presentan a la variante multiobjetivo del algoritmo Branch & Bound como la opción más eficiente para árboles de búsqueda tanto finitos como infinitos, precisando de una cota adicional en este último caso.