%0 Thesis
%A Vargas Paredes, Jhonny
%A Penit Granado, Víctor
%T Estudio y aplicación de metaheurísticas y comparación con métodos exhaustivos
%D 2016
%U https://hdl.handle.net/20.500.14352/66086
%X Cuando nos enfrentamos a problemas reales haciendo uso de recursos computacionales, hemos de tener en cuenta que el número de posibles soluciones candidatas a tener en cuenta puede llegar a ser tan inmenso que abordarlas mediante técnicas algorítmicas clásicas, en la mayoría de los casos, pueden llegar a convertirse en un problema en sí mismo debido al gran coste en recursos que pueden llegar a generar. En este contexto, aspectos como el tiempo utilizado en la búsqueda de una solución mediante algoritmos de búsqueda exhaustiva tales como fuerza bruta, vuelta atrás, ramificación y poda, etc., puede llegar a ser prohibitivo en la práctica. Ante este problema que se nos plantea, podemos hacer un estudio sobre otros métodos, tales como los metaheurísticos, que, aunque no siempre aseguran la optimalidad de las soluciones producidas; tienen un tiempo de ejecución mucho menor que los métodos exhaustivos. En el presente trabajo hemos seleccionado dos problemas NP-completos de entre los más famosos de la literatura y hemos realizado un estudio de ambos. Concretamente, los problemas seleccionados han sido el TSP (Traveling Salesman Problem) y el problema de la Mochila 0-1. Por otro lado, hemos llevado a cabo un estudio sobre distintas metaheurísticas para poder resolver los problemas mencionados. Entre estas metaheurísticas, hemos seleccionado cuatro: metaheurísticas evolutivas, metaheurísticas inspiradas en colonias de hormigas, metaheurísticas simulated annealing (enfriamiento simulado) y metaheurísticas GRASP (Greedy Randomized Adaptive Search Procedure). Después de esto, cada problema ha sido resuelto aplicando tanto algoritmos de búsqueda exhaustiva como metaheurísticas. Una vez adaptados los algoritmos a la resolución de los problemas concretos, hemos realizado un estudio experimental, donde se realizaron comparativas de rendimiento. Finalmente, todo este trabajo ha sido plasmado en el desarrollo de una aplicación software, la cual consta de dos partes: una que contiene la implementación los algoritmos adaptados para la resolución de los problemas y que son ofrecidos a modo de servicios web y otra parte donde se ha implementado un cliente web que puede consumir estos servicios y realizar una presentación más vistosa de la ejecución de los algoritmos y los resultados obtenidos. Esta arquitectura podrá servir como base para futuras ampliaciones de este estudio.
%X When we face real problems using computational resources, we must take into account that the number of possible candidate solutions to consider can become so huge that address this through classic algorithmic techniques, in most of cases can become a problem itself due to the high cost in of generated resources. In this context, aspects such as the time spent in the search for a solution by exhaustive search algorithms such as backtracking, branch and bound, dynamic programming, etc., can become prohibitive in practice. To face this problem, we can make a study of other methods, such as metaheuristics, which, although it not always ensure the optimality of the solutions produced, have a runtime much smaller than the exhaustive methods. In this work we have selected two NP-complete problems among the most famous in literature, and we have studied both. Specifically, the selected problems were the TSP (Traveling Salesman Problem) and 0-1 Knapsack problem. On the other hand, we have carried out a study on different metaheuristics to solve the above problems. We have selected four of these techniques: evolutionary metaheuristics, metaheuristics inspired in ant colonies, simulated annealing metaheuristics and GRASP (Greedy Randomized Adaptive Search Procedure) metaheuristics. After this, each problem has been solved by applying exhaustive search algorithms and metaheuristics. Once the algorithms have been adapted to solving the specific problems, we have performed an experimental study where we have made comparatives of performance. Finally, all this work has led to the development of a software application, which is composed of two parts: one containing the implementation of the algorithms adapted to solve the problems offered as web services, and another part where a web client has been implemented to consume these services, and present in a more attractive manner the results obtained by the algorithms. This architecture will serve as a basis for future extensions of this study.
%~