¿Qué enfoque produce el recorrido más corto en el problema TSP: vecino más cercano o algoritmos genéticos?

Question

En los últimos días me han señalado algunos sitios que demostraron solución TS usando algoritmos genéticos.

¿Cuál es el enfoque produce el recorrido más corto en el problema TSP:? Vecino más cercano o algoritmos genéticos

Answer 1

Dado que ni técnica garantiza una solución óptima, su kilometraje puede variar. Con un poco de suerte, ya sea técnica puede superar el rendimiento de la otra. Ambas técnicas tienen pros y contras.

Al vecino más próximo: + rápido, + sencilla, no suele ser óptimo

algoritmo genético: -slower, complejo -más, + soluciones tendencia hacia óptima en el tiempo

La gran diferencia es que los algoritmos aleatorios como recocido simulado y algoritmos genéticos pueden seguir mejorando con el tiempo - el tiempo se deje correr, más posibilidades que tiene para una solución óptima (aunque no hay garantías).

Desde NN es rápido, no hay nada que nos impida la combinación de las técnicas. Ejecutar NN para encontrar una solución de partida posiblemente-mejor-que-aleatoria. Entonces, alimentar esa solución en su algoritmo genético y se deja correr todo el tiempo que considere apropiado.

Si está interesado en soluciones óptimas, echa un vistazo a la Lin y Kernighan heurístico y programación lineal . Ambos se utilizaron para encontrar soluciones óptimas para grandes recorridos incluidos rel="nofollow esta solución para un rel="nofollow 85.900 recorrido por la ciudad y una 24978 ciudad Suecia recorrido .

El Georgia Tech TSP sitio es un gran recurso.