ASrank: un análisis de robustez

Abstract

La resolución de los problemas de optimización en el mundo real es dificultosa no solo por lo que significa la búsqueda de soluciones en espacios de grandes dimensiones sino, también, por el alto grado de incertidumbre que afecta a los datos de entrada al problema. Para ello son necesarios algoritmos que encuentren soluciones de muy buena calidad en poco tiempo y que ademas sean robustos. Los algoritmos metaheurísticos han demostrado una y otra vez que son capaces de lograr el primer objetivo, pero no existen muchas investigaciones que estudien y analicen la robustez de los mismos. En este trabajo se analiza la resistencia al ruido (o robustez) de una variante de los algoritmos de optimización basados en colonias de hormigas, denominado ASrank. Para ello se utiliza el problema del viajante de comercio, ya que modela un amplio espectro de problemas del mundo real. También se propone genTSP, un generador de instancias ruidosas del mencionado problema. El análisis de los resultados obtenidos en la experimentación arroja que el algoritmo estudiado es robusto y no necesita esfuerzo computacional extra para alcanzar este segundo objetivo.