Solución Agente Viajero

Solución al agente viajero por medio de algunos algoritmos y heurísticas, implementadas para al  Traveling Sales Problem.

Resumen.

El Problema del Agente Viajero (PAV) o Traveling Salesman Problem (TSP) es un problema que hay en cualquier empresa u organización, el cual permite calcular la distancia más corta de un punto a otro los que estará entre muchas cosas, ciudades o personas. Y que permite saber cómo será el mejor viaje a realizar, más cercano y menos costo al recorrer las distancia. Para este artículo se presenta una definición de que es TSP, con algunos algoritmo y heurísticas de optimización como son (Algoritmo Constructivo, Algoritmo Voraz Estocástico, Algoritmo voraz, Algoritmo MetaHeurístico) las cuales permitirán dar alguna solución factible a una problemática tratada con el TSP, pero basándose en las características que han propuesto diferentes autores, y la aplicación de TSP como simulación estos problemas reales con. Por último, en la conclusión se aborda el tema de TSP como un paradigma que se puede emplear en situaciones donde se involucran puntos de control (ciudades) y costo entre las ciudades.

Palabras claves: Traveling Salesman Problem, Problema del Agente Viajero, Algoritmo, Heuristica, paradigma.

Problema

El TSP presenta una gran facilidad para formularse y definirse en pocas ciudades, pero a medida que crece el número de ciudades, el tiempo para obtener una solución óptima crece más. Para formular el TSP como un problema de programación Este problema se plantea la siguiente pregunta: Dada una lista de ciudades y las distancias valoraciones entre cada par de ciudades, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una sola vez y vuelve a la ciudad de origen? a este tipo de problemas a las ciudades se les define como punto y a los caminos entre las ciudades se les llama costo. Los costos pueden ser dirigidos y no dirigidos. Donde solo puede ir desde una ciudad inicial hasta una final, es decir que a cada ciudad se le puede asociar una distancia o un costo para poder determinar el mejor recorrido probándolo con los Algoritmos o Heurísticas de optimización.

Soluciones Propuestas:

Usando los algoritmos

Introducción.

Actualmente la optimización combinatoria ocupa un gran interés entre los académicos de diferentes ramas como las matemáticas y la ingeniería. Este tipo de problemas tiene un alcance bastante amplio y su estudio se lleva a cabo desde hace muchos años. Este tipo de temática involucra campos como los de la inteligencia artificial y la lógica computacional, donde por lo general se desea encontrar una solución lo suficientemente buena a un problema bastante genérico pero complejo de analizar. El interés por este tipo de algoritmos radica principalmente en que a pesar de que reciben un gran dominio de soluciones, estos a través de diferentes mecanismos logran acotar dicho espacio explorando en cada paso las mejores soluciones aproximadas al problema planteado de manera eficiente.

Dos de las técnicas fundamentales aplicadas en este curso fueron las heurísticas y meta heurísticas, la primera de estas técnicas logran abordar problemas bastante complejos y a un coste computacional mínimo, además de que la implementación de este tipo de algoritmos es relativamente sencilla de lograr, un ejemplo de algoritmos que trabajan bajo esta técnica pueden ser lo algoritmos genéticos. Por otro lado los algoritmos basados en el uso de estrategias metaheurísticas son algoritmos un más generalizados que no están tan sesgados a un tipo de problema, son algoritmos que ofrecen igualmente muy buenas soluciones, un ejemplo de estos es el algoritmo recocido simulado.

A través de pequeños proyecto de aula se logró abordar una buena cantidad de contenido que facilito ampliar el conocimiento académico de la electiva profesional y sobre todo aprender y conocer el potencial de la programación evolutiva y la optimización combinatoria para la solución de problemas actuales y clásicos de la literatura.

Metodología.

La metodología aplicada para el estudio de estos algoritmos se enfocó sobre todo en primera medida en realizar un análisis de la teoría existente y relacionada a su funcionamiento. Se comenzó por hacer un seguimiento detallado y riguroso al flujo de información y del comportamiento de los algoritmos genéticos sobre un problema de optimización sencillo, donde se estudió las diversas formas de cruce, mutación y generación de nuevas poblaciones por medio de una selección por sorteo en donde la intención de esta estrategia fue la de tratar de seleccionar los individuos más aptos para sobrevivir.

Se propuso entonces realizar una pequeña implementación para que se familiarizara el curso un poco más con la forma lógica de esta heurística y así posteriormente comprender un poco mejor como abordar otro tipo de problemas como el caso del agente viajero. De igual manera se planteó hacer un estudio de otro tipo de algoritmos como el recocido simulado, el algoritmo de fuerza bruta, algoritmo voraz, y algoritmo voraz estocástico.

Por cuestión de tiempo no se pudo realizar una socialización ni conocer a fondo cada uno de estos algoritmos de optimización, pero se dejaron algunas bases para entender su funcionamiento, se dedicó un gran porcentaje del tiempo de clase a la compresión, del problema del agente viajero, TSP por sus siglas en ingles y se implementó parte del problema sobre la estructura de un algoritmo genético.

Marco teórico.

Heurísticas de optimización.

En la actualidad en el campo de la informática existen un cierto tipo de problemas que son complejos de analizar y requieren el uso de diferentes estrategias ya sean de tipo exacto o heurístico para su solución. En el estudio desarrollado desde el análisis de la programación evolutiva se tuvieron en cuenta una serie de procedimientos en los cuales no era tan importante llegar a una respuesta exacta sino más bien a una respuesta aceptable que cumpliera con la mayoría de restricciones, según el autor

D. De Werra y otros, definen este tipo de técnicas como una serie de procesos que permiten alcanzar una aproximación intuitiva haciendo uso inteligente de la estructura del problema para llegar a una solución.

A continuación se presentan algunos casos especiales de esta metodología propuesta.

Algoritmo Constructivo.

Este tipo de algoritmos tienen como característica principal, van agregando con cada iteración un elemento de los posibles a seleccionar hasta completar una solución. Por lo general los elementos que tienden a ser seleccionados son por que cuentan con una buena evaluación, según el problema.

...