An Analysis of Some Algorithms and Heuristics for Multiobjective Graph Search
Enrique L. Machuca Sánchez · Dialnet (Universidad de la Rioja) · 2012
Muchos problemas reales requieren examinar un numero exponencial de alternativas para encontrar la eleccion optima. A este tipo de problemas se les llama de optimizacion combinatoria. Ademas, en problemas reales normalmente se evaluan multiples magnitudes que presentan conflicto entre ellas. Cuando se optimizan multiples obje-tivos simultaneamente, generalmente no existe un valor optimo que satisfaga al mismo tiempo los requisitos para todos los criterios. Solucionar estos problemas combinatorios multiobjetivo deriva comunmente en un gran conjunto de soluciones Pareto-optimas, que definen los balances optimos entre los objetivos considerados. En esta tesis se considera uno de los problemas multiobjetivo mas recurrentes: la busqueda de caminos mas cortos en un grafo, teniendo en cuenta multiples objetivos al mismo tiempo. Se pueden senalar muchas aplicaciones practicas de la busqueda multiobjetivo en diferentes dominios: enrutamiento en redes multimedia (Climaco et al., 2003), programacion de satelites (Gabrel & Vanderpooten, 2002), problemas de transporte (Pallottino & Scutella, 1998), enrutamiento en redes de ferrocarril (Muller-Hannemann & Weihe, 2006), planificacion de rutas en redes de carreteras (Jozefowiez et al., 2008), vigilancia con robots (delle Fave et al., 2009) o planificacion independiente del dominio (Refanidis & Vlahavas, 2003). La planificacion de rutas multiobjetivo sobre mapas de carretera realistas ha sido considerada como un escenario de aplicacion potencial para los algoritmos y heuristicos multiobjetivo considerados en esta tesis. El transporte de materias peligrosas (Erkut et al., 2007), otro problema de enrutamiento multiobjetivo relacionado, ha sido tambien considerado como un escenario de aplicacion potencial interesante. Los metodos de optimizacion de un solo criterio son bien conocidos y han sido ampliamente estudiados. La Busqueda Heuristica permite la reduccion de los requisitos de espacio y tiempo de estos metodos, explotando el uso de estimaciones de la distancia real al objetivo. Los problemas multiobjetivo son bastante mas complejos que sus equivalentes de un solo objetivo y requieren metodos especificos. Estos, van desde tecnicas de solucion exactas a otras aproximadas, que incluyen los metodos metaheuristicos aproximados comunmente encontrados en la literatura. Esta tesis se ocupa de algoritmos exactos primero-el-mejor y, en particular, del uso de informacion heuristica para mejorar su rendimiento. Esta tesis contribuye analisis tanto formales como empiricos de algoritmos y heuristicos para busqueda multiobjetivo. La caracterizacion formal de estos algoritmos es importante para el campo. Sin embargo, la evaluacion empirica es tambien de gran importancia para la aplicacion real de estos metodos. Se han utilizado diversas clases de problemas bien conocidos para probar su rendimiento, incluyendo escenarios realistas como los descritos mas arriba. Los resultados de esta tesis proporcionan una mejor comprension de que metodos de los disponibles sonmejores en situaciones practicas. Se presentan explicaciones formales y empiricas acerca de su comportamiento. Se muestra que la busqueda heuristica reduce considerablemente los requisitos de espacio y tiempo en la mayoria de las ocasiones. En particular, se presentan los primeros resultados sistematicos mostrando las ventajas de la aplicacion de heuristicos multiobjetivo precalculados. Esta tesis tambien aporta un metodo mejorado para el precalculo de los heuristicos, y explora la conveniencia de heuristicos precalculados mas informados.