Предлагаемые операторы GA для проблемы TSP?

Question

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

Answer 1

Упорядоченная мутация и упорядоченный переход (см. в этой статье ). Стандартные операции мутации и перекрестного перехода обычно приводят к неверным решениям (т. Е. Дублирующимся и / или отсутствующим городам в маршруте).

Недавно был похожий вопрос .

У меня есть Java-апплет, который реализует TSP с использованием упорядоченного перехода и мутации , если вы хотите сравнить производительность вашей реализации.

Answer 2

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

Answer 3

Не могли бы вы уточнить

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

Вы можете проверить операторы кроссовера, чтобы убедиться, что у вас нет повторяющихся узлов в дочерних хромосомах.Пара таких операторов кроссовера - операторы Order Crossover (OX) и Edge Crossover.

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

Кстати, так как вы пометили "python", взгляните на Pyevolve также есть пример TSP.