Doctorado de Sociedad de la Información y el Conocimiento
13/03/2015

Autor: Sergio González Martín
Programa: Doctorado de Sociedad de la Información y el Conocimiento
Idioma: inglés
Directores: Dr. Ángel Alejandro Juan Pérez y Dr. Daniel Riera Terrén
Departamento / Instituto: Internet Interdisciplinary Institute (IN3)
Materias: Informática, Teoría general del análisis combinatorio, Teoría de grafos
Palabras clave: Heurísticas aleatorias y sesgadas, Optimización, Aplicaciones reales, Metaheurísticas, Simulación
Área de conocimiento: Ciencia de la Computación e Inteligencia Artificial

+ Enlace al proyecto

Resumen

La mayoría de metaheurísticas tienen un componente aleatorio, que normalmente se basa en aleatorización uniforme –por ejemplo, el uso de la distribución de probabilidad uniforme para efectuar selecciones aleatorias–. Por otro lado, el marco Multi-start biased randomization of classical heuristics with adaptive local search (MIRHA) propone el uso de la aleatorización sesgada (no uniforme) para el diseño de algoritmos metaheurísticos alternativos –por ejemplo, el uso de distribuciones de probabilidad sesgadas como la geométrica o la triangular–. En algunas situaciones, esta aleatorización no uniforme ha obtenido una convergencia más rápida a la solución casi óptima. El marco MIRHA también incluye un paso de búsqueda local para mejorar las soluciones generadas durante el proceso iterativo. Además, permite añadir pasos de búsqueda al problema, como cache (memoria) o splitting (dividir y conquistar), que permiten la generación de soluciones competitivas (casi óptimas).

Los algoritmos diseñados con el marco MIRHA permiten obtener soluciones de alta calidad a problemas realistas en tiempos de computación razonables. Asimismo, tienden a utilizar un número reducido de parámetros, por lo que son simples de implementar y configurar en la mayoría de aplicaciones prácticas. El marco se ha aplicado exitosamente a varios problemas de enrutamiento y planificación. Uno de los principales objetivos de esta tesis es desarrollar nuevos algoritmos, basados en el marco mencionado, para solucionar problemas de optimización combinatoria que pueden ser de interés para la industria de las telecomunicaciones.