То, почему добавление Перекрестно соединяет к моему Генетическому алгоритму, дает мне худшие результаты?
Я реализовал Генетический алгоритм для решения Проблемы коммивояжера (TSP). Когда я использую только мутацию, я нахожу лучшие решения чем тогда, когда я добавляю в перекрестном соединении. Я знаю, что нормальные перекрестные методы не работают на TSP, таким образом, я реализовал и Заказанное Перекрестное соединение и методы Перекрестного соединения PMX, и оба страдают от плохих результатов.
Вот другие параметры, которые я использую:
Мутация: Единственная Мутация Подкачки или Инвертированная Мутация Подпоследовательности (как описано Tiendil здесь) с уровнями мутации, протестированными между 1% и 25%.
Выбор: выбор колеса рулетки
Функция фитнеса: 1 / расстояние тура
Численность населения: Протестированный 100, 200, 500, я также выполняю GA 5 раз так, чтобы у меня было множество стартового населения.
Условие остановки: 2 500 поколений
С тем же набором данных 26 точек я обычно получаю результаты приблизительно расстояния 500-600, использующего просто мутацию с высокими уровнями мутации. При добавлении перекрестного соединения мои результаты обычно находятся в 800 диапазонах расстояния. Другая запутывающая вещь состоит в том, что я также реализовал очень простой алгоритм Преодоления подъема для решения проблемы и когда я выполняю это 1000 раз (быстрее, чем выполнение GA 5 раз), я получаю результаты вокруг расстояния 410-450, и я ожидал бы получать лучшие результаты с помощью GA.
Какие-либо идеи, относительно почему мое выполнение GA хуже, когда я добавляю перекрестное соединение? И почему это работает намного хуже, чем простой алгоритм Восхождения на вершину, который должен застрять на локальных максимумах, поскольку это не имеет никакого способа исследовать, после того как это находит локальное макс.?
5 ответов
Одна из причин, по которой ваши результаты ухудшаются при добавлении кроссовера, потому что, возможно, он не делает то, что должен - сочетает лучшие черты двух людей. Попробовать с низкой вероятностью кроссовера может быть? Разнообразие населения может быть проблемой здесь. Моррисон и Де Йонг в своей работе Измерение разнообразия населения предлагают новую меру разнообразия. Используя эту меру, вы можете увидеть, как меняется разнообразие вашего населения на протяжении поколений. Посмотрите, какая разница, когда вы используете кроссовер или не используете кроссовер.
Кроме того, в вашей реализации OX или PMX могут быть некоторые незначительные ошибки / упущенные детали. Может быть, вы что-то упустили из виду? Кстати, может быть, вы хотите попробовать оператор кроссовера Edge Recombination? (Pyevolve имеет реализацию).
Похоже, ваш оператор кроссовера привносит слишком много случайности в новые поколения, поэтому вы теряете вычислительные усилия, пытаясь улучшить плохие решения. Представьте, что алгоритм Hill-Climb может улучшить данное решение до лучшего из его окружения, но ваш генетический алгоритм может только ограниченно улучшать почти случайную популяцию (решения).
Также стоит сказать, что GA - не лучший инструмент для решения TSP. В любом случае, вам стоит посмотреть на несколько примеров того, как это реализовать. например http://www.lalena.com/AI/Tsp/
Чтобы придумать «инновационные» стратегии генетического алгоритмы обычно используют кроссовер , чтобы комбинировать возможности различных возможных решений, чтобы очень быстро исследовать пространство поиска и находить новые стратегии более высокой пригодности - совсем не в отличие от внутренней работы человеческого интеллекта (вот почему это спорно, что мы на самом деле ничего не «изобретаем», а просто смешиваем то, что уже знаем).
Таким образом (случайное объединение разных особей) кроссовер не сохраняет симметрию или порядок, и когда проблема сильно зависит от какой-либо симметрии или порядка генов в хромосоме (как в вашем конкретном случае), она действительно вероятно, что переход на кроссовер приведет к худшим результатам. Как вы сами упомянули, хорошо известно, что кроссовер не подходит для коммивояжера.
Стоит подчеркнуть, что без этого подвига нарушения симметрии генетических алгоритмов кроссовера не удалось бы заполнить эволюционные «ниши» (где часто необходимо отсутствие симметрии) - и поэтому кроссовер (во всех его вариантах) чрезвычайно важен в подавляющее большинство случаев.
Выбирая колесо рулетки, вы добавляете в смесь плохих родителей. Если вы хотите как-то утяжелить колесо, чтобы выбрать лучших родителей, это может помочь.
Помните, большая часть вашего населения может быть неподходящими родителями. Если вы вообще не взвешиваете родительский отбор, есть большая вероятность, что вы будете постоянно разводить плохие решения, которые выходят за пределы пула. Взвесьте свой выбор, чтобы чаще выбирать лучших родителей, и используйте мутацию, чтобы исправить слишком похожий пул, добавив случайности.
Вы можете попробовать ввести элитизм в процесс отбора. Элитизм означает, что две особи с наивысшей приспособленностью в популяции сохраняются и копируются в новую популяцию до проведения отбора. После завершения элитизма отбор продолжается в обычном режиме. Это означает, что независимо от того, какие родители выбраны колесом рулетки или что они производят во время кроссинговера, две лучшие особи всегда будут сохранены. Это предотвращает потерю пригодности новой популяции, поскольку два лучших решения в ней не могут быть хуже, чем в предыдущем поколении.