Как я могу улучшить этот генетический алгоритм для TSP?

Question

Это мой генетический алгоритм, шаг за шагом:

1. Создайте две начальные группы случайным образом и выберите наиболее подходящий тур из обоих.

2. Выполните упорядоченный кроссовер, который выбирает случайную часть первого подходящего тура и заполняет остальные со второго по порядку.

3. Мутирует этот тур, меняя местами два города, если этот тур всего в 1,3 раза лучше, чем топ-10% в исходной популяции (что я буквально только что сделал по индукции, выделяя плохие туры, которые производятся) - я бы с удовольствием изменить это, но не могу придумать лучшего пути.

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

4. Возвращает тур производится.

Мутация, однако, почти ВСЕГДА хуже, если не совпадает с кроссовером.

Я был бы очень признателен за помощь. Спасибо!

Answer 1

Проблема в GA - слишком быстрое сужение пространства поиска и поиск решения для локальных максимумов. Вы должны убедиться, что вы не направляете свое решение ни в коем случае, кроме как в функции выбора / пригодности. Итак, когда вы говорите,

почему вы выбрали бы хорошее решение, а затем выполнили функцию, которая, скорее всего, ухудшит его?

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

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

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

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

вы выбираете лучший для мутирования

Это не совсем верно, хорошие люди должны иметь более высокий шанс быть выбранным. Здесь есть небольшая разница в том, что БАДы могут быть выбраны для родителей. Опять же, это помогает снизить вероятность достижения решения локальных максимумов. Это также означает, что лучший человек для поколения может (и часто так) на самом деле становится хуже. Чтобы решить эту проблему, мы обычно реализуем "элитарность", при которой лучший человек всегда копируется в следующее поколение (у него нет операций).

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