Почему добавление кроссовера в мой генетический алгоритм дает мне худшие результаты?

Question

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

Вот другие параметры, которые я использую:

Мутация : Мутация с одним свопом или инвертированная мутация подпоследовательности (, как описано здесь Tiendil ) с тестированием мутаций от 1 до 25%.

Выбор : Выбор колеса рулетки

Фитнес-функция : 1 / дистанция тура

Численность населения : протестировано 100, 200, 500, я также запускаю GA 5 раз, чтобы у меня было множество начальных популяций.

Условие остановки : 2500 поколений

При том же наборе данных в 26 баллов я обычно получаю результаты на расстоянии 500-600, используя чисто мутацию с высокой частотой мутаций. При добавлении кроссовера мои результаты обычно находятся в диапазоне 800 дистанций. Другая сбивающая с толку вещь заключается в том, что я также реализовал очень простой алгоритм Hill-Climbing, чтобы решить проблему, и когда я бегу 1000 раз (быстрее, чем 5 раз GA), я получаю результаты на расстоянии 410-450, и я ожидаю чтобы получить лучшие результаты, используя GA.

Есть идеи, почему моя GA работает хуже, когда я добавляю кроссовер? И почему он работает намного хуже, чем простой алгоритм Hill-Climb, который должен застрять на локальных максимумах, поскольку у него нет возможности исследовать его, когда он находит локальный максимум?

Answer 1

С помощью выбора колеса рулетки вы вводите в смесь плохих родителей. Если вы хотите как-то взвесить колесо, чтобы выбрать лучших родителей, это может помочь.

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

Answer 2

Похоже, ваш оператор кроссовера вносит слишком много случайности в новые поколения, поэтому вы теряете свои вычислительные усилия, пытаясь улучшить плохие решения. Представьте, что алгоритм Hill-Climb может улучшить данное решение в лучшую сторону, но ваш Генетический алгоритм может вносить ограниченные улучшения только в почти случайную совокупность (решения).

Стоит также сказать, что GA - не лучший инструмент для решения TSP. В любом случае, вы должны посмотреть на некоторые примеры того, как это реализовать. например http://www.lalena.com/AI/Tsp/

Answer 3

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

Answer 4

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

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

Стоит подчеркнуть, что без этого нарушения симметрии кроссовер генетические алгоритмы не смогли бы заполнить эволюционные «ниши» (где зачастую не хватает симметрии) - и поэтому кроссовер (во всех его вариантах) существенно важен в Подавляющее большинство случаев.

Answer 5

Одна из причин того, что ваши результаты ухудшаются при добавлении кроссовера, может заключаться в том, что он не делает то, что должен - объединяет лучшие качества двух людей. Попробовать с низкой вероятностью кроссовера можно? Разнообразие населения может быть проблемой здесь. Моррисон и Де Йонг в своей работе Измерение разнообразия населения предлагают новую меру разнообразия. Используя эту меру, вы можете увидеть, как разнообразие вашего населения меняется от поколения к поколению. Посмотрите, какая разница, когда вы используете кроссовер или не используете кроссовер.

Кроме того, в вашей реализации OX или PMX могут быть незначительные ошибки / упущенные детали. Может быть, вы что-то упустили? Кстати, может быть, вы хотите попробовать кроссовер Edge Recombination? ( Pyevolve имеет реализацию).