Подробный вопрос при применении генетического алгоритма для путешествующего продавца

StackOverflow https://stackoverflow.com/questions/2542174

Вопрос

Я читаю различные вещи по этому поводу и понимаю принцип и концепции, однако, ни одна из бумаг не упоминает детали того, как рассчитать пригодность хромосомы (которая представляет путь) с участием соседних городов (в хромосоме), которые не напрямую связаны по краю (на графике).

Например, учитывая хромосому 1 | 3 | 2 | 8 | 4 | 5 | 6 | 7, в котором каждый ген представляет индекс города на графике/карте, как мы рассчитаем его пригодность (то есть общая сумма Расстояния пройдены) Если, скажем, нет прямых преимуществ/связи между городом 2 и 8. Следуем ли мы каким -то жадным алгоритмом для выработки маршрута между 2 и 8 и добавлять расстояние от этого маршрута к общему?

Эта проблема кажется довольно распространенной при применении GA к TSP. Любой, кто сделал это раньше, пожалуйста, поделитесь своим опытом. Спасибо.

Это было полезно?

Решение

Если на вашем графике нет связи между 2 и 8 Для классической проблемы продавца -путешественника. Анкет Если вы найдете какой -то другой маршрут между 2 и 8, вы, вероятно, будете нарушать требование «посетить каждое место» один раз ».

Одним из действительно хитрых, но прагматичных решений является включение краев между этими узлами с невероятно высокими расстояниями, или даже +Inf, если ваш язык поддерживает его. Таким образом, ваша стандартная функция минимизации фитнеса будет естественным образом обрезать их.

Я думаю, что первоначальная формулировка проблемы включает в себя края между всеми узлами, так что это не проблема.

Другие советы

Это точная проблема, специализированные методы кроссовера и мутации были применены для решений на основе GA для задач TSP. Посмотри это вопрос.

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

(Или наоборот, назначьте ему пригодность, если более высокая пригодность означает, что хромозон более подходит для работы)

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top