Путешественник - Ближайший сосед и генетический DEATHMATCH

Question

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

Я ищу ваше мнение, которое лучше подходит для этой конкретной проблемы.

Эвристика против генетики.

К счастью, я имею в виду, что будет иметь более короткий/более дешевый путь.

Объясните, почему вы чувствуете, как вы себя чувствуете.

Примеры и ссылки на другие сайты приветствуются.

Answer 1

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

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

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

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

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

Если вас интересуют оптимальные решения, ознакомьтесь с Lin-Kernighan heuristic и Linear Programming. Оба были использованы для поиска оптимальных решений для крупных туров, включая this solution для 85,900 city tour и 24,978 city Sweden tour.

Georgia Tech TSP site - отличный ресурс.