Вопрос о детали при применении генетического алгоритма для коммивояжера
Я считал различный материал на этом и понимаю принцип и включенные понятия, однако, ни одна из бумаги не упоминает детали того, как вычислить фитнес хромосомы (который представляет маршрут) вовлечение смежных городов (в хромосоме), которые непосредственно не соединены краем (в графике).
Например, учитывая хромосому 1|3|2|8|4|5|6|7, в котором каждый ген представляет индекс города на графике/карте, как мы вычисляем его физическую форму (т.е. полная сумма расстояний переместился), если, скажем, нет никакого прямого края/ссылки между городом 2 и 8. Мы следуем своего рода жадному алгоритму, чтобы разработать маршрут между 2 и 8 и добавить расстояние этого маршрута к общему количеству?
Эта проблема кажется довольно распространенной при применении GA к TSP. Любой, кто сделал это прежде, обменивается Вашим опытом.Спасибо.
2 ответа
Если на вашем графе нет связи между 2 и 8, то любая хромосома с 2|8 или 8|2 в ней недействительна для классической задачи о путешествующем продавце. Если вы найдете какой-то другой маршрут между 2 и 8, вы, вероятно, нарушите требование "посетить каждое место один раз".
Одно из действительно сомнительных, но прагматичных решений - включить ребра между этими узлами с невероятно большими расстояниями, или даже +INF, если ваш язык поддерживает это. Таким образом, ваша стандартная минимизирующая фитнес-функция будет естественным образом отсекать их.
Я думаю, что оригинальная формулировка проблемы включает ребра между всеми узлами, так что это не проблема.
Это точный вид проблемы, специальные методы кроссовера и мутации были применены для основанных на ГА решений проблем TSP. См. Этот вопрос .