Resolución de problemas combinatorios con aplicación real en sistemas distribuidos

Abstract

El objetivo de esta tesis es el desarrollo de técnicas metaheurísticas paralelas eficientes para la resolución de problemas con aplicación real, Para ello, inicialmente se ha realizado un estudio sobre el estado del arte actual en el campo de las metaheurísticas, centrándonos principalmente en el dominio de los métodos paralelos. Una vez comprendidas las ventajas y limitaciones de los modelos propuestos en el pasado, y basadas en este conocimiento, se han realizado diferentes propuestas algorítmicas paralelas como extensiones de los modelos más eficientes en la literatura. Estos modelos han sido estudiados en profundidad tanto en un aspecto teórico (estudiando las influencias de los principales parámetros en su convergencia) como en un aspecto experimental, analizando su comportamiento sobre diferentes plataformas paralelas. Basado en el conocimiento adquirido en estas dos últimas fases, se abordó la resolución de diferentes problemas combinatorios con diferentes características pero que comparten como característica diferenciada su gran dificultad y su aplicación real. En concreto se han abordado el diseño de circuitos, el etiquetado léxico del lenguaje natural, el problema de ensamblado de fragmentos de ADN, problemas de planificación y asignación de trabajadores y otros problemas de diferentes campos. Entre las principales aportaciones que se pueden descartar es la mejora en el estado del arte de muchos de los problemas abordas (diseño de circuitos, etiquetado léxico, ...), así como el aumento en el conocimiento sobre diferentes aspectos algorítmicos de los métodos paralelos (estudios sobre la convergencia de los modelos distribuidos, estudio de la influencia del acoplamiento en las técnicas metaheurísticas paralelas, ..)..