¿Qué es más eficiente para encontrar una solución para el problema del vendedor ambulante, una búsqueda puramente aleatoria o un algoritmo genético? ¿Hay un papel?

Answer 1

Los algoritmos exactos o deterministas no han tenido mucho éxito en alcanzar una solución óptima para el problema del vendedor ambulante, debido a la complejidad temporal poco práctica.

Ahora se sabe que los algoritmos heurísticos (basados ​​en la mejora de la búsqueda local, como el recocido simulado) o incluso mejor, los algoritmos metaheurísticos (basados ​​en la mejora de la búsqueda global, como la optimización de colonias de hormigas) generan una solución casi óptima mucho más rápido.

Ant Colony Optimization, un algoritmo metaheurístico, se basa en simular el esfuerzo de colaboración entre los agentes para resolver un problema, siguiendo el fenómeno de las hormigas que usan niveles de feromona en los caminos recorridos para descubrir un alimento y mantener a otras hormigas en la colonia informado (aunque los niveles de feromona en las pistas) sobre su ubicación. El fenómeno se conoce como Stigmergy.

Puede ver un documento sobre la implementación de Ant Colony Optimization para resolver TSP aquí;

http://www.ef.uns.ac.rs/mis/arch…

Answer 2

La heurística de Lin-Kernighan: [1003.5330] Adaptaciones heurísticas de Lin-Kernighan para el problema generalizado del vendedor ambulante

Puede usarlo en el algoritmo de su deseo, recocido simulado, algoritmo genético, colonia de hormigas, etc.

Además, una búsqueda puramente aleatoria (RS) es una mala idea, debe guiar la búsqueda con algún mecanismo para garantizar una buena solución, y probablemente un algoritmo puramente genético proporcionará una solución mejor que RS.

Algunos viejos, pero es un buen punto de partida para resolver TSP con algoritmos genéticos, tiene un montón de cruces para TSP: Algoritmos genéticos para el problema del vendedor ambulante: una revisión de representaciones y operadores