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

Cavero Díaz, Sergio (2019). Búsqueda eficiente de soluciones para el Cyclic Cutwidth Minimization Problem, mediante algoritmos heurísticos. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S.I. de Sistemas Informáticos (UPM), Madrid.

Description

Title: Búsqueda eficiente de soluciones para el Cyclic Cutwidth Minimization Problem, mediante algoritmos heurísticos
Author/s:
  • Cavero Díaz, Sergio
Contributor/s:
  • García Pardo, Eduardo
Item Type: Final Project
Degree: Grado en Ingeniería del Software
Date: July 2019
Subjects:
Freetext Keywords: Algoritmos heurísticos; Búsqueda Tabú
Faculty: E.T.S.I. de Sistemas Informáticos (UPM)
Department: Sistemas Informáticos
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img] PDF - Users in campus UPM only - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (1MB)

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.

More information

Item ID: 56385
DC Identifier: http://oa.upm.es/56385/
OAI Identifier: oai:oa.upm.es:56385
Deposited by: Biblioteca Universitaria Campus Sur
Deposited on: 11 Sep 2019 08:21
Last Modified: 11 Sep 2019 08:21
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM