Resumen
Optimization is a discipline that addresses the search for the best possible solution, called the optimal solution, to a problem mathematically modeled. These problems can be classified according to its computational complexity. Problems belonging to the NP-hard class are too complex to be solved with an exact algorithm in a reasonable amount of time. Alternatively, these problems can be approached through approximate techniques that allow finding good quality solutions, although not necessarily optimal, in a reasonable amount of computing time. Among these techniques, heuristic and metaheuristic algorithms stand out, since they have been proven as useful tools in solving high-complexity real problems. In this Doctoral Thesis, heuristic and metaheuristic algorithms are proposed for the resolution of four Graph Layout Problems (GLP). Specifically, the problems studied belong to the NP-hard class and can be framed as combinatorial optimization problems. GLPs aim to find the best possible assignment of the vertices of an input graph to the vertices of a host graph, optimizing a certain objective function. More specifically, this Doctoral Thesis focuses on the study of GLPs in which the embedding is done in circular layouts. This family of problems is of great interest due to the variety of practical applications they have. In this research, a methodology for addressing GLPs is proposed. Specifically, it starts from the study of each problem, and then proposes heuristic and metaheuristic algorithms for tackling the problem. After a preliminary experimentation, the algorithmic proposal is compared to the existing methods in the state of the art. This methodology has been successfully applied to the studied problems, resulting in various scientific publications that compile the main findings of the research carried out.
Sergio Cavero
Doctor en Inteligencia Artificial
Sergio Cavero nació en Madrid (España) el 24 de septiembre de 1997. Se graduó en Ingeniería del Software por la Universidad Politécnica de Madrid en 2019. Durante sus estudios de grado realizó una estancia en la Universidad de Bradford (Reino Unido). Además, fue galardonado en dos ocasiones con la Beca de Excelencia de la Comunidad de Madrid, así como con el premio al Mejor Proyecto Fin de Carrera. Posteriormente, realizó un Máster en Inteligencia Artificial en la misma universidad (UPM) obteniendo los premios al Mejor Expediente Académico (‘Premio José Cuena’) y al Mejor Trabajo Fin de Máster. Sus resultados académicos le permitieron ser beneficiario de una de las ‘Ayudas para la Formación de Profesorado Universitario (FPU)’, financiadas por el Gobierno español. Actualmente realiza su tesis doctoral en la Universidad Rey Juan Carlos, dirigida por los profesores Abraham Duarte y Eduardo G. Pardo. Sus principales intereses de investigación se centran en la interfaz entre las Ciencias de la Computación, la Inteligencia Artificial y la Investigación Operativa. La mayoría de sus publicaciones tratan sobre el desarrollo de procedimientos metaheurísticos para problemas de optimización modelados por grafos.