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

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

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

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

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

    • The mutation is selected from a population of several mutations.

  4. Возвращает произведенный тур.

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

Буду очень признателен за помощь. Спасибо!


python mutation traveling-salesman genetic-algorithm crossover
person sam price    schedule 06.12.2017    source источник
comment
Не делайте кроссовер. Это необязательно.   -  person Ray    schedule 06.12.2017
comment
Кроссовер на самом деле улучшает то, что выбрано из исходной популяции (родителей), но не дает наилучшего возможного тура.   -  person sam price    schedule 06.12.2017
comment
Скрещивание и мутация не улучшают гены; они делают разные гены. Выбор делает вещи лучше. А кроссовер - ненужное усложнение.   -  person Ray    schedule 06.12.2017
comment
Это то, что я тоже, но уберите кроссовер и мутацию, и все, что у вас есть, это грубая сила. Мне нужно разработать генетический алгоритм.   -  person sam price    schedule 06.12.2017
comment
Вы все еще делаете мутацию. Случайным образом выберите один из лучших генов и мутируйте его. Это не грубая сила, это стохастический. И это генетическое, потому что ваши мутирующие гены.   -  person Ray    schedule 07.12.2017
comment
Итак, вы говорите, что ваш алгоритм состоит в том, чтобы перебрать приличное решение, а затем случайным образом изменить его и надеяться, что оно улучшится? Я не понимаю, как это когда-нибудь сработает. Тем не менее, я ценю комментарии.   -  person sam price    schedule 07.12.2017
comment
Вы не надеетесь, что это улучшится; вы буквально выбираете лучших для мутации. Выбор – самая важная часть. Так работает эволюция. И снова, как и в естественной эволюции, кроссовер необязателен.   -  person Ray    schedule 08.12.2017
comment
Я знаю, что вы выбираете лучшее для мутации, но если вы мутируете лучшее так, как это сделал я, то есть просто случайным образом меняете местами города, то вы всегда получите худшее решение. Я до сих пор не понимаю, почему вы берете хорошее решение, а затем выполняете функцию, которая, скорее всего, сделает его худшим решением.   -  person sam price    schedule 08.12.2017
comment
Мутация не всегда дает худшее решение. Опять же, кроссовер НЕ создает лучшие решения, он также делает худшие решения, как и мутация.   -  person Ray    schedule 08.12.2017
comment
Кроме того, другие генетические алгоритмы, решающие TSP, просто используют мутацию. Вы можете посмотреть их на YouTube.   -  person Ray    schedule 08.12.2017

Ответы (1)


arrow_upward
0
arrow_downward

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

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

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

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

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

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

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

Это не совсем верно, у хороших людей должен быть более высокий ШАНС быть выбранным. Здесь есть тонкая разница в том, что ПЛОХИЕ люди также могут быть выбраны в качестве родителей. Опять же, это помогает уменьшить вероятность достижения решения с локальным максимумом. Это также означает, что лучший человек в своем поколении может (и часто так и происходит) стать еще хуже. Чтобы решить эту проблему, мы обычно реализуем «элитизм», при котором лучший индивидуум всегда копируется в следующее поколение (при этом он не подвергается никаким операциям).

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

person M. Mansell    schedule 16.01.2018