Búsqueda eficiente de soluciones para el Cyclic Cutwidth Minimization Problem, mediante algoritmos heurísticos

Abstract

El desarrollo de este Trabajo Fin de Grado ha tenido lugar en el contexto de una beca de colaboración en el Departamento de Sistemas Informáticos de la Universidad Politécnica de Madrid. En concreto, este trabajo se enmarca en el contexto de la optimización y su objetivo principal ha sido proponer algoritmos heurísticos para abordar un problema de optimización conocido. La optimización es el proceso de búsqueda de la mejor solución posible para un determinado problema. Un problema de optimización consta generalmente de una gran cantidad de soluciones, un criterio para discriminar entre ellas y una función, denominada función objetivo, que determina la calidad de una solución dada. Resolver un problema de optimización de manera exacta puede llegar a ser muy costoso, siendo en ocasiones muy difícil determinar la mejor solución entre todas las soluciones, la óptima. Debido a la dificultad computacional que tienen muchos algoritmos para encontrar la solución óptima a un problema de optimización, cuando el tamaño del problema es grande, aparecen los denominados algoritmos heurísticos y metaheurísticos. Un algoritmo heurístico es un procedimiento simple, basado en el sentido común que, generalmente, encuentra una buena solución (no necesariamente la óptima) a problemas difíciles. Una metaheurística es un procedimiento que guía un algoritmo heurístico en la búsqueda eficiente de soluciones de calidad. En este Trabajo Fin de Grado se ha abordado, mediante técnicas heurísticas y metaheurísticas, el problema de optimización de la minimización del ancho de corte en grafos con disposición circular (CCMP. del inglés Cyclic Cutwidth Minimization Problem). El CCMP consiste en embeber un grafo candidato, dentro de otro grafo con estructura de ciclo (representado en disposición circular) de modo que el máximo número de aristas que cruzan el espacio entre cada dos vértices consecutivos del ciclo, sea minimizado. En la actualidad no se ha reportado un algoritmo que resuelva este problema para grafos genéricos. No obstante, en la literatura sí que se han encontrado procedimientos matemáticos exactos y cotas para grafos específicos. En este TFG se propone un algoritmo basado en la Búsqueda Tabú, cuyos resultados han sido comparados satisfactoriamente con el estado del arte, obteniendo un procedimiento para encontrar soluciones de alta calidad, en tiempos de cómputo reducido, para grafos generales. Abstract: The development of this Final Degree Project has taken place in the context of a collaboration grant in the Departamento de Sistemas Informáticos de la Universidad Politécnica de Madrid. Speciffically, this work is contextualized in the optimization area and its main objective is to propose heuristic algorithms to tackle an optimization problem. Optimization is the process of searching for the best possible solution for a given problem. An optimization problem generally has a large number of solutions, a criteria for discriminating between them and a function, called an objective function, which determines the quality of a given solution. Solving an optimization problem in an exact way can be very complex, being sometimes hard to determine the best solution among all solutions, the optimal one. Due to the computational difficulty that many algorithms have to find the optimal solution to an optimization problem, even more when the size of the problem is large, the so-called heuristic and metaheuristic algorithms get importance. A heuristic algorithm is a simple, common sense procedure that generally finds a good (not necessarily optimal) solution to a hard optimization problem. A metaheuristic is a procedure that guides heuristic algorithms to produce quality and efficient solutions. In this project, the Cyclic Cutwidth Minimization Problem (CCMP) has been tackled through heuristic and metaheuristic techniques. The CCMP consists in embedding a candidate graph in a host graph with cycle structure (represent as a circular arrangement), so that the maximum number of edges crossing the space between each two consecutive vertices a the cycle is minimized. Currently, no algorithm has been reported to solve this problem for generic graphs. However, exact mathematical procedures and bounds for speciffic graphs have been proposed in the literature. In this project an algorithm based on the Tabu Search, whose results have been compared satisfactorily with previous state-of-the-art methods, obtaining an algorithm to find high quality solutions, in reduced computing time and for any graph.