El diseño de técnicas y algoritmos eficientes que resuelvan adecuadamente problemas complejos de optimización es uno de los campos dentro de la investigación en Informática con mayor repercusión en la actualidad. De hecho, debido a que la sociedad actual demanda continuamente más y mayores retos en el campo de la ingeniería, dar una solución adecuada y eficiente a este tipo de problemas cobra cada vez mayor importancia tanto para la industria como para la comunidad científica. Además, es bien sabido que tanto los requisitos temporales como computacionales son un factor crítico a tener en cuenta cuando se trata de resolver problemas de grandes proporciones cuya solución debe ser aplicable en un supuesto real. En estos casos, el uso de heurísticas y metaheurísticas en combinación con estrategias paralelas se presenta como la mejor alternativa de resolución, ya que por una parte, las citadas estrategias no exactas proporcionan una solución de alta calidad en un tiempo razonable, mientras que por otro, es bien sabido que tanto la eficiencia de dichos algoritmos heurísticos como los resultados que éstos obtienen mejoran de manera significativa cuando se aplican estrategias de paralelismo. Éste es el contexto global en el que se incardina esta tesis doctoral. Por tanto, se han estudiado, diseñado y desarrollado un conjunto heterogéneo de metaheurísticas para resolver un importante problema de optimización dentro del dominio de las Telecomunicaciones. Sin embargo, el uso de algoritmos metaheurísticos conlleva un alto coste computacional, ya que por una parte, dichos métodos incluyen una gran cantidad de parámetros que es necesario ajustar mediante numerosos experimentos, mientras que por otra, ciertas partes de dichos algoritmos requieren mucha capacidad de cómputo. Por consiguiente, a la hora de abordar problemas reales de grandes dimensiones, como es el caso del problema manejado en esta tesis, tanto los requisitos técnicos como temporales requeridos por estas técnicas son muy exigentes. Así pues, se hace imprescindible que el uso de las técnicas metaheurísticas esté combinado con estrategias paralelas. De esta forma, se mejora tanto la productividad como el rendimiento de las metaheurísticas, ya que de una parte el paralelismo permite que el ajuste paramétrico de las metaheurísticas se agilice considerablemente, haciendo que este proceso sea más preciso y exhaustivo, mientras que de otra se mejora notablemente la calidad de los resultados en tiempos que serían más elevados si los algoritmos se ejecutaran de manera secuencial. Las estrategias paralelas para mejorar productividad y rendimiento son diferentes, ya que en el primer caso se utilizan paradigmas diseñados para aplicar computación de alta productividad y en el otro se utilizan modelos aplicados a computación de alto rendimiento. En esta tesis se han utilizado ambos modelos, haciendo uso de estrategias paralelas diseñadas para ser ejecutadas tanto en entornos clúster como en entornos grid. En concreto, el problema de optimización con el que se ha trabajado en esta tesis es el de la asignación automática de frecuencias (FAP, del inglés Frequency Assigment Problem), y fue elegido, entre otras razones, tanto por su complejidad (se trata de un problema NP-Completo) como por su relevancia para la industria del sector, ya que es bien conocido que el mundo actual en que vivimos está dominado por las comunicaciones, lo cual provoca que los recursos necesarios para llevar a cabo este proceso sean muy limitados. Este hecho hace que las compañías que ofrecen servicios móviles deban gestionar los citados recursos de manera eficiente para sacar el máximo rendimiento de ellos manteniendo unos niveles altos en la calidad de los servicios que ofrecen.El problema de optimización que surge con el FAP se debe al reducido rango de frecuencias disponible para cada red de telefonía. Debido a este hecho, no es posible asignar a cada comunicación que se establece en la red una frecuencia única, sino que los operadores deben repetir las frecuencias de que disponen múltiples veces para cubrir todas las comunicaciones que se producen entre los usuarios de la red. Sin embargo, este solapamiento de frecuencias causa interferencias que dificultan, e incluso pueden llegar a anular, dichas comunicaciones, por lo que se hace necesario realizar una planificación de frecuencias eficiente con la que se consiga maximizar el número de comunicaciones que se realizan en la red manteniendo a la vez unos mínimos aceptables en la calidad de los servicios ofrecidos.Tras hacer una amplia revisión de los algoritmos heurísticos y metaheurísticos que parecían ajustarse mejor a los requisitos del problema descrito anteriormente, se terminó por desarrollar y ajustar un conjunto de siete metaheurísticas con el que se trató de resolver el problema de la asignación de frecuencias desde varios enfoques. El primero que se implementó fue PBIL (aprendizaje incremental basado en población), el cual se aplicó primero a una versión benchmark del FAP (las instancias Philadelphia), para después ser adaptado a la versión real del problema que ha centrado la investigación del autor de esta tesis. Después se implementó el algoritmo SS (búsqueda dispersa), que ha sido una de las aproximaciones que mejores resultados ha obtenido en la resolución del problema. No se quiso dejar fuera del estudio al clásico algoritmo genético (GA), que tras un exhaustivo ajuste demostró proporcionar planificaciones de frecuencia de muy alta calidad. Finalmente, se incluyó un algoritmo basado en inteligencia colectiva, el ABC (algoritmo basado en colonia de abejas, de reciente aparición), que también ofreció muy buenos resultados. Todos los algoritmos mencionados anteriormente son metaheurísticas basadas en población, ya que utilizan una población de soluciones en su búsqueda del óptimo global, pero no se quisieron dejar fuera del estudio estrategias basadas en trayectoria, ya que presentan características que también resultan interesantes. Así, se desarrollaron los algoritmos ILS (búsqueda local iterativa), VNS (búsqueda de entorno variable) y GRASP (procedimiento de búsqueda adaptativa, avariciosa y aleatoria), con el que además se desarrolló un modelo paralelo maestro-esclavo utilizando una infraestructura grid real.Por tanto, se realizaron múltiples pruebas y experimentos con cada metaheurística, aplicando en algunos casos paradigmas basados en paralelismo. Sin embargo, el estudio presentado en esta tesis concluyó con el diseño e implementación de una novedosa estrategia paralela que hacía uso de todas las metaheurísticas desarrolladas. En concreto, se desarrolló una hiperheurística paralela basada en el heterogéneo conjunto de metaheurísticas que se había desarrollado, y que dio como resultados planificaciones de frecuencia de muy alta calidad que solucionaban el problema de optimización abordado. De hecho, entre las principales contribuciones aportadas por esta tesis se encuentran, por un lado, el desarrollo y evaluación de metaheurísticas que no habían sido aplicadas antes en la resolución del problema FAP, obteniéndose además resultados de muy buena calidad en todas ellas, y por otro, el diseño e implementación de una eficiente estrategia paralela (la hiperheurística basada en metaheurísticas) con la que se ha conseguido mejorar, hasta donde nosotros conocemos, cualquier resultado (tanto en tiempo como en calidad) publicado hasta la fecha en la resolución del problema de la asignación automática de frecuencia en redes reales de telecomunicaciones.
