Metaheurísticas avanzadas para problemas reales en redes de telecomunicaciones

Resumen

Esta tesis doctoral está dedicada a la resolución de problemas reales que aparecen en redes de telecomunicaciones utilizando algoritmos metaheurísticos. Los tres problemas que se han considerado son la planificación de celdas (ACP) y la asignación de frecuencias (AFP), ambos del campo de las redes de telefonía móvil, y el diseño de la estrategia de difusión óptima en redes ad hoc de dispositivos móviles (MANETs), procedente del área de las comunicaciones inalámbricas ad hoc. Nuestro planteamiento ha consistido en utilizar dos técnicas comunes con las que hemos abordado los tres problemas: algoritmos evolutivos con selección por estado estacionario, ssGA, y búsqueda dispersa, SS. La primera extensión avanzada que se ha planteado ha estado motivada por el carácter multiobjetivo de dos de los problemas resueltos (ACP y difusión óptima en MANETs). Como resultado hemos diseñado dos nuevos algoritmos, ssNSGA-II y AbYSS. Además, para cada problema, hemos propuesto un algoritmo específico que se adecua a sus características: estrategias evolutivas paralelas para ACP, colonias de hormigas para AFP y algoritmos genéticos celulares para la difusión óptima en MANETs. En total, hemos abordado cada problema con 3 técnicas distintas. Por último, debido al elevado tiempo de cómputo que requiere la resolución de estos problemas, se han propuesto extensiones de los algoritmos ssGA y ssNSGA-II, llamadas GrEA y assNSGA-II, para realizar las computaciones en un sistema de computación grid compuesto por más de 300 procesadores. Mientras que ssNSGA-II se ha utilizado para ACP y difusión óptima en MANETs, GrEA se ha aplicado al problema de la asignación de frecuencias (AFP). Los resultados han revelado los tres problemas que se han resuelto satisfactoriamente. Además, los algoritmos evolutivos con selección por estado estacionario han sido los más adecuados para resolver este tipo de problemas reales que involucran tareas computacionalmente costosas, no sólo en optimización monoobjetivo, sino también en multiobjetivo (ssNSGA-II siempre ha superado a NSGA-II). Su funcionamiento ha permitido extenderlos de forma eficente para poder ejercutarse en sistemas de computación grid, siendo GrEA y assNSGA-II dos claros ejemplos de este hecho. Los resultados aquí son realmente notables ya GrEA y assNSGA-II no sólo han sido capaces de reducir el tiempo de ejecución de ssGA y ssNSGA-II (sus correspondientes versiones secuenciales) cientos de veces, sino que el modelo de búsqueda subyacente que aparece ha sido más efectivo en algunos casos, es decir, ha sido capaz de alcanzar mejores soluciones utilizando el mismo esfuerzo computacional. Respecto al algoritmo de búsqueda dispersa, ha sido la primera vez que ha aplicado a este tipo de problemas y su comportamiento ha sido muy prometedor, puesto que ha escalado bien con el tamaño de los problemas y no se ha estancado durante la búsqueda.