EMIGO – Metaheurísticas Eficientes para la Optimización en Grafos

Investigador principal: Abraham Duarte y José Manuel Colmenar Verdugo. Entidades financiadoras: Ministerio de Ciencia Innovación y Universidades. (Ref. PGC2018-095322-B-C22). Duración: 01/01/2019 - 31/12/2021.

Resumen:

Los sistemas de información se representan hoy en día comúnmente con un gráfico, lo que facilita su interpretación y comprensión. Un grafo es una estructura de datos abstracta formada por nodos y aristas, donde los nodos, a veces también denominados vértices, representan entidades, y las aristas son enlaces que conectan los nodos representando relaciones entre ellos. Desde un punto de vista teórico, un grafo es un par ordenado G = (V, E), donde V es el conjunto de vértices y E un conjunto de aristas, donde cada arista asocia dos vértices en V. Este tipo de grafos suele denominarse grafos no dirigidos y no ponderados. Los grafos en los que las aristas tienen orientación (es decir, dados los vértices u, v en V existe un arco entre u y v pero no el inverso) se conocen como grafos dirigidos. Por último, los grafos ponderados son aquellos en los que se asigna un número (peso) a cada arista. Estos pesos pueden representar costes, longitudes o capacidades, dependiendo del problema que se trate. Algunos autores llaman a este tipo de grafos “redes”.

Los grafos son la unidad básica de modelado en una gran variedad de áreas dentro de la informática y la informática, como la gestión de proyectos, la programación de la producción, el equilibrio de líneas, los planes de negocio o la visualización de software. La teoría de grafos ofrece una rica fuente de problemas y técnicas de optimización, programación y desarrollo de estructuras de datos. El diseño de una buena heurística o de algoritmos de aproximación para problemas de optimización suele requerir un importante conocimiento especializado y el método de ensayo y error sobre un grafo. En muchas aplicaciones del mundo real, suele ocurrir que el mismo problema de optimización se resuelve una y otra vez de forma periódica, manteniendo la misma estructura del problema pero diferenciando los datos. Esto proporciona una oportunidad para el aprendizaje de algoritmos heurísticos que exploten la estructura de dichos problemas recurrentes. Estudiamos el aprendizaje por refuerzo y la incrustación de grafos para abordar este reto. La política codiciosa aprendida se comporta como un meta-algoritmo que construye incrementalmente una solución, y la acción se determina por la salida de una red de incrustación de grafos que captura el estado actual de la solución.

El objetivo principal de este proyecto es resolver problemas de optimización difíciles, NP-duros en términos científicos, véase Garey y Johnson, (1990), en un grafo que modela una situación real. Un problema de optimización difícil es aquel para el que no es posible garantizar que la solución óptima se encuentre en un tiempo computacional “razonable”. En la práctica, hay muchos problemas difíciles que desencadenan el desarrollo de procedimientos eficientes capaces de encontrar “buenas” soluciones, incluso cuando éstas no pueden ser probadas como óptimas. Estos métodos, para los que la calidad de la solución es tan importante como el tiempo de cálculo necesario para encontrarla, se conocen como heurísticos. En la actualidad, una familia de heurísticas modernas e inteligentes, conocidas normalmente como metaheurísticas (Glover, 1986), son estrategias maestras que guían a los algoritmos subordinados para producir soluciones más allá de las que se obtienen normalmente en la búsqueda de la optimalidad local. Las metaheurísticas se encuentran entre las técnicas más destacadas y exitosas para resolver una gran cantidad de problemas de optimización combinatoria y numérica complejos y computacionalmente difíciles. Ambos grupos de investigación tienen una larga experiencia en el desarrollo y aplicación de estas metodologías. En este proyecto, proponemos la aplicación de las metodologías metaheurísticas para resolver problemas difíciles basados en grafos que surgen en los negocios y la industria.