Diseño y desarrollo de un nuevo algoritmo basado en la naturaleza para la resolución del problema del vendedor ambulante

Abstract

El problema del vendedor ambulante, es un problema de optimización combinatoria que trata de encontrar una ruta que pase por una serie de puntos de manera que ésta la menor distancia posible. La resolución de este problema se complica exponencialmente al aumentar el número de puntos por los que la ruta debe pasar. Para la resolución de este problema se utilizan métodos computacionales que realizan cálculos para el avance de la búsqueda de la ruta óptima, algunos de los cuales se basan en procesos biológicos por la capacidad de solución a problemas complejos que brindan. Uno de estos métodos es el llamado optimización por enjambre de partículas que modela conductas sociales como el movimiento de un enjambre de abejas o un banco de peces. Otro de los métodos es conocido como algoritmo genético, el cual basa la generación de soluciones en operadores como la recombinación o mutación de cromosomas. Z.E.R.G. es un algoritmo ideado para la resolución del problema del vendedor ambulante, combinando elementos de los dos métodos mencionados. El algoritmo cuenta con 9 configuraciones distintas que caracterizan el desempeño de su búsqueda de la soluciones. En el presente trabajo, se presenta el diseño y la implementación del algoritmo, además de un análisis de los resultados generados para problemas del vendedor ambulante de variada dificultad.

The Travelling Salesman Problem is a combinatorial optimization problem that aims to find the path that goes through a series of points, with the least possible distance. The resolution of this problem grows exponentially with the number of points that the path must go through. For the resolution of this problem computational methods are used in order to advance in the search of the optimal solution, some of which are based in biological processes because of the capacity to solve complex problems that they bring. One of these methods is the one called Particle Swarm Optimization which models social conducts such as the movement of a bee swarm or a fish school. Another of the methods is known as Genetic Algorithm, which bases the generation of solutions in operators like the crossover or mutation of chromosomes. Z.E.R.G. is an algorithm devised for the resolution of the Travelling Salesman Problem, combining elements of the two mentioned methods. The algorithm has different configurations that characterize the performance of its solution search. In this assignment, the design and development of the algorithm is presented, in addition to an analysis of the results generated for varying difficulty Travelling Salesman Problems.

El problema del viatjant de comerç, és un problema d'optimització combinatòria que tracta de trobar una ruta que passi per una sèrie de punts de manera que aquesta la menor distància possible. La resolució d'aquest problema es complica exponencialment en augmentar el nombre de punts pels quals la ruta ha de passar. Per a la resolució d'aquest problema s'utilitzen mètodes computacionals que realitzen càlculs per a l'avanç de la recerca de la ruta òptima, alguns dels quals es basen en processos biològics per la capacitat de solució a problemes complexos que brinden. Un d'aquests mètodes és l'anomenat optimització per eixam de partícules que modela conductes socials com el moviment d'un eixam d'abelles o un banc de peixos. Un altre dels mètodes és conegut com algorisme genètic, el qual basa la generació de solucions en operadors com la recombinació o mutació de cromosomes. Z.E.R.G. és un algoritme ideat per a la resolució del problema del viatjant de comerç, combinant elements dels dos mètodes esmentats. L'algoritme compta amb 9 configuracions diferents que caracteritzen l'exercici de la seva recerca de la solucions. En el present treball, es presenta el disseny i la implementació de l'algoritme, a més d'una anàlisi dels resultats generats per el problema del viatjant de comerç de variada dificultat.