Я строю генетический алгоритм для решения проблемы коммивояжера. К сожалению, я ударил пики, которые могут выдержать более тысячи поколений, прежде чем мутировать из них и получить лучшие результаты. В этом случае, как работают кроссоверы и мутации?Предлагаемые операторы GA для проблемы TSP?
Не могли бы вы уточнить
«К сожалению, я ударил пики, которые могут выдержать в течение более тысяч поколений, прежде чем мутируют из них и получить лучшие результаты»?
Вы можете проверить операторы кроссовера, которые гарантируют, что у вас нет повторяющихся узлов в дочерних хромосомах. Пара этих операторов кроссовера - это операции «Кроссовер заказов» (OX) и пограничный кроссовер.
Мутация может быть простой, простой заменой двух позиций в одной хромосоме.
BTW, поскольку вы отметили «python», посмотрите на Pyevolve, он также имеет пример TSP.
Упорядоченная мутация и заказанный кросс-код (см. this article). Стандартные мутации и кросс-операции обычно приводят к недействительным решениям (т. Е. Дублируют и/или пропускают города на маршруте).
Недавно было similar question.
У меня есть a Java applet that implements the TSP using ordered cross-over and mutation, если вы заинтересованы в сравнении эффективности вашей реализации.
Если ваша проблема в том, что пики остаются в течение более тысячи поколений, проблема может быть не в операторах кроссовера и мутации. Вы не можете вводить или сохранять достаточное количество вариаций для своего населения: я бы рассмотрел пропорции кроссоверов, мутаций и выживших от одного поколения к другому и, возможно, увеличил долю мутаций.
http://stackoverflow.com/questions/1544055/rossover-operation-in-genetic-algorithm-for-tsp может помочь. – 2010-02-02 16:31:14