Я строю генетический алгоритм для решения проблемы коммивояжера. К сожалению, я ударил пики, которые могут выдержать более тысячи поколений, прежде чем мутировать из них и получить лучшие результаты. В этом случае, как работают кроссоверы и мутации?Предлагаемые операторы GA для проблемы TSP?
ответ
Не могли бы вы уточнить
«К сожалению, я ударил пики, которые могут выдержать в течение более тысяч поколений, прежде чем мутируют из них и получить лучшие результаты»?
Вы можете проверить операторы кроссовера, которые гарантируют, что у вас нет повторяющихся узлов в дочерних хромосомах. Пара этих операторов кроссовера - это операции «Кроссовер заказов» (OX) и пограничный кроссовер.
Мутация может быть простой, простой заменой двух позиций в одной хромосоме.
BTW, поскольку вы отметили «python», посмотрите на Pyevolve, он также имеет пример TSP.
Упорядоченная мутация и заказанный кросс-код (см. this article). Стандартные мутации и кросс-операции обычно приводят к недействительным решениям (т. Е. Дублируют и/или пропускают города на маршруте).
Недавно было similar question.
У меня есть a Java applet that implements the TSP using ordered cross-over and mutation, если вы заинтересованы в сравнении эффективности вашей реализации.
Если ваша проблема в том, что пики остаются в течение более тысячи поколений, проблема может быть не в операторах кроссовера и мутации. Вы не можете вводить или сохранять достаточное количество вариаций для своего населения: я бы рассмотрел пропорции кроссоверов, мутаций и выживших от одного поколения к другому и, возможно, увеличил долю мутаций.
- 1. Метод алгоритма GA для TSP
- 2. TSP/TSPTW с различными семенами
- 3. Данные для простого TSP
- 4. TSP для полного управляемого графика
- 5. Предлагаемые меры для преодоления проблемы с производительностью волны вспышки
- 6. Какой метод пересечения лучше всего дать нам быстрые изменения в лучших значениях для TSP в GA?
- 7. перегрузка операторы проблемы
- 8. Предлагаемые ресурсы для изучения блоков
- 9. Предлагаемые индексы для таблицы MPTT
- 10. Предлагаемые улучшения?
- 11. Предлагаемые значения
- 12. Close-Enough Внедрение TSP
- 13. ga: productCategoryHierarchy vs ga: productCategoryLevelXX
- 14. Имитационная функция отжига для TSP
- 15. Реализация PTAS для евклидова TSP?
- 16. TSP vs. Word Unscrambler
- 17. ga: searchDestinationPage == ga: landingPagePath?
- 18. Проблемы извлечения ключевых слов из GA печенье
- 19. Предлагаемые разрешения для файлов веб-сайта
- 20. Социальная сеть - Предлагаемые друзья
- 21. Алгоритм для генерации решений TSP случайным образом
- 22. операция Кроссовер в генетический алгоритм для TSP
- 23. Лучший способ реализации карты для TSP
- 24. TSP-Вариант, возможный алгоритм?
- 25. Несколько TSP с завихрением
- 26. Panasonic TSP crash
- 27. Simulated Annealing TSP
- 28. Itertools.permutations создает n случайных решений для TSP
- 29. Динамический подход к TSP
- 30. Несколько посещений tsp
http://stackoverflow.com/questions/1544055/rossover-operation-in-genetic-algorithm-for-tsp может помочь. – 2010-02-02 16:31:14