Оператор кроссовера для перестановок

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

Пример:

Parent1: 
 5 12 60 50 42 21 530 999 112 234 15 152 601 750 442 221 30 969 113 134
Parent2: 
 12 750 42 113 530 112 5 23415 60 152 601 999 442 221 50 30 969  134 21

Пусть будет так - как я могу получить детей из этих двух?

Ответы

Ответ 2

Выбор кроссовера зависит от того, является ли порядок или абсолютная позиция целых чисел важными для фитнеса. В HeuristicLab (С#) мы реализовали несколько популярных в литературе, которые включают в себя: OrderCrossover (2 варианта), OrderBasedCrossover, PartiallyMatchedCrossover, CyclicCrossover (2 варианта), EdgeRecombinationCrossover (ERX), MaximalPreservativeCrossover, PositionBasedCrossover и UniformLikeCrossover. Их реализация может быть найдена вместе со ссылкой на научный источник в плагине HeuristicLab.Encodings.PermutationEncoding. ERX имеет смысл только для проблем с TSP или TSP. CX основан на положении, PMX частично частично упорядочен по порядку, но больше по отношению к позиции. OX основан исключительно на заказе.

Остерегайтесь того, что наши реализации предполагают непрерывную нумерованную перестановку с целыми числами от 0 до N-1. Сначала вам нужно сопоставить их с этим диапазоном.

Ответ 3

Согласно моим исследованиям и реализациям генетических операторов. Для кодирования порядка существует множество типов кроссоверных операторов (т.е. Повторение генов не допускается, например, в TSP). В общем, мне нравится думать, что есть две основные семьи:

Семейство ERX

Список окрестностей используется для хранения соседей каждого node в обоих родителях. Затем, ребенок генерируется с использованием только списка. Известно, что ERX является более уважительным и передающим аллели, что в основном означает, что связи между генами вряд ли будут нарушены.

Примеры ERX-подобных операторов включают в себя: Edge Recombination (ERX), Edge-2, Edge-3, Edge-4 и генерализованный кроссовер разделов (GPX).

OX-подобные кроссоверы

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

Пример OX-подобных кроссоверов: порядок кроссовера (OX), максимальный консервативный кроссовер (CX) и неполный кроссовер (PMX).

Первое семейство (ERX) лучше работает в простых генетических алгоритмах. В то время как второе семейство больше подходит в гибридном генетическом алгоритме или меметическом алгоритме (использование локального поиска). Эта статья подробно объясняет это.

Ответ 4

В Traveling Salesrep Problem (TSP) вы хотите, чтобы заказ посетил список городов, и вы хотите посетить каждый город ровно один раз. Если вы кодируете города непосредственно в геноме, то наивный кроссовер или мутация часто генерируют неверный маршрут.

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

Учитывая геном [1, 2, 4, 3, 2, 4, 1, 3], вы начнете со списка городов в произвольном порядке, скажем, в алфавитном порядке:

  • Атланта
  • Boston
  • Чикаго
  • Денвер

Тогда вы бы взяли каждую пару значений из генома и поменяли города на этих позициях. Итак, для генома выше вы замените их на 1 и 2, а затем на 4 и 3, а затем на 2 и 4 и, наконец, на 1 и 3. Вы получите:

  • Денвер
  • Чикаго
  • Boston
  • Атланта

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

Я использовал это для TSP и других проблем оптимизации с большим успехом.