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

Question

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

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

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

Answer 1

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

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

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

Answer 2

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

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

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

Answer 3

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