Optimización de un algoritmo de colonia de hormigas mediante CUDA para resolver problemas de ruteo de vehículos

Abstract

En esta tesis se muestra cómo pueden los algoritmos de colonias de hormigas resolver problemas de optimización de gran complejidad que requieren de grandes capacidades de cómputo, los cuales pueden ser combinados con nuevas arquitecturas de programación en paralelo mediante el uso de tarjetas gráficas (GPU´s) para tratar de mejorar su rendimiento. Al inicio se encuentra una introducción, que es una explicación general de los principales elementos que integran el método propuesto, los cuales a través de los diversos capítulos se irán desarrollando de manera más extensa. El capítulo 1 es un marco teórico conformado por la justificación, la hipótesis y los objetivos generales y particulares que se resuelven. Posteriormente, en el capítulo 2 encontraremos una introducción a las técnicas metaheurísticas más conocidas como son los algoritmos genéticos, recocido simulado, colonias de hormigas, entre otras. En el capítulo 3 se expone el tema de complejidad computacional, la dificultad de resolver problemas computacionales y la manera en que algunos problemas consumen grandes cantidades de almacenamiento y capacidad de procesamiento. En el capítulo 4 se encontrará información referente al problema de ruteo de vehículos, en que consiste este problema, su formulación matemática y algunas áreas de aplicación. En el capítulo 5 se explican los algoritmos de optimización basados en colonias de hormigas, la descripción de su estructura y funcionamiento. En el capítulo 6 se habla sobre la arquitectura de programación CUDA, de la cual nos apoyamos para implementar algunas de las funciones para su funcionamiento en paralelo.

This thesis shows how can the ant colony algorithms to solve optimization problems of great complexity that require large computing capabilities, which can be combined with new architectures of parallel programming using graphics cards (GPU’s) to try to improve their performance. At the beginning is an introduction, a general explanation of the main elements that make up the proposed method, which through the various chapters will be developed more extensively. Chapter 1 is a theoretical framework consisting rationale, assumptions and general and specific objectives that are resolved. Later, in chapter 2 we find an introduction to popular metaheuristics such as genetic algorithms, simulated annealing, ant colonies, among other metaheuristic techniques. In chapter 3 the issue of computational complexity, the difficulty of solving computational problems and how some problems consume large amounts of storage and processing capacity is exposed. In chapter 4 will find information about the vehicle routing problem, that is the problem, mathematical formulation and some application areas. In chapter 5 the optimization algorithms based on ant colonies are explained, describing their structure and function. In Chapter 6 we talk about the architecture of CUDA programming, which we rely to implement some functions to operate in parallel. In Chapter 7, the proposed solution algorithm, analysis of the functions that were convenient parallelize and its implementation in the new architecture is explained. Computer equipment used for testing is detailed in chapter 8, as well as the software installed to develop the algorithm in parallel. In Chapter 9 tests with the solution method are explained, the parameters used for factorial testing, and how the results were obtained, finally to be analyzed.