Какой подход приводит к более короткому обходу в задаче TSP:ближайший сосед или генетические алгоритмы?

Question

За последние несколько дней я отметил несколько паутина Сайты это продемонстрировало решение TS с использованием генетических алгоритмов.

Какой подход приводит к более короткому обходу в задаче TSP:ближайший сосед или генетические алгоритмы?

Answer 1

Поскольку ни один из методов не гарантирует оптимального решения, ваш пробег будет разным.При небольшом везении любая техника может превзойти другую.Оба метода имеют свои плюсы и минусы.

Ближайший сосед:+быстро, +просто, -обычно не оптимально

Генетический алгоритм:-более медленные, -более сложные, + решения со временем стремятся к оптимальным

Большая разница заключается в том, что рандомизированные алгоритмы, такие как имитированный отжиг и генетические алгоритмы могут продолжать совершенствоваться с течением времени - чем дольше вы позволяете им работать, тем больше у вас шансов на оптимальное решение (хотя гарантий нет).

Поскольку NN работает быстро, ничто не мешает вам комбинировать методы.Запустите NN, чтобы найти, возможно, лучшее, чем случайное начальное решение.Затем внесите это решение в свой генетический алгоритм и дайте ему работать столько, сколько вы сочтете нужным.

Если вас интересуют оптимальные решения, ознакомьтесь с Эвристика Лина-Кернигана и Линейное программирование.Оба были использованы для поиска оптимальных решений для крупных туров, включая это решение для экскурсия по городу за 85 900 долларов и a тур по Швеции по 24,978 городам.

В Сайт Georgia Tech TSP это отличный ресурс.