Я пытаюсь решить проблему кроссовера в генетическом алгоритме на моих перестановках. Пусть говорят, что у меня две перестановки из 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
Пусть будет так - как я могу получить детей из этих двух?
То, что вы ищете, это упорядоченный кроссовер. Существует объяснение проблемы Traveling Salesman здесь.
Вот некоторый Java-код, который реализует вариант с частично сопоставленным кроссовером (PMX).
Выбор кроссовера зависит от того, является ли порядок или абсолютная позиция целых чисел важными для фитнеса. В HeuristicLab (С#) мы реализовали несколько популярных в литературе, которые включают в себя: OrderCrossover (2 варианта), OrderBasedCrossover, PartiallyMatchedCrossover, CyclicCrossover (2 варианта), EdgeRecombinationCrossover (ERX), MaximalPreservativeCrossover, PositionBasedCrossover и UniformLikeCrossover. Их реализация может быть найдена вместе со ссылкой на научный источник в плагине HeuristicLab.Encodings.PermutationEncoding. ERX имеет смысл только для проблем с TSP или TSP. CX основан на положении, PMX частично частично упорядочен по порядку, но больше по отношению к позиции. OX основан исключительно на заказе.
Остерегайтесь того, что наши реализации предполагают непрерывную нумерованную перестановку с целыми числами от 0 до N-1. Сначала вам нужно сопоставить их с этим диапазоном.
Согласно моим исследованиям и реализациям генетических операторов. Для кодирования порядка существует множество типов кроссоверных операторов (т.е. Повторение генов не допускается, например, в TSP). В общем, мне нравится думать, что есть две основные семьи:
Список окрестностей используется для хранения соседей каждого node в обоих родителях. Затем, ребенок генерируется с использованием только списка. Известно, что ERX является более уважительным и передающим аллели, что в основном означает, что связи между генами вряд ли будут нарушены.
Примеры ERX-подобных операторов включают в себя: Edge Recombination (ERX), Edge-2, Edge-3, Edge-4 и генерализованный кроссовер разделов (GPX).
Выбраны две точки кроссовера. Затем гены между точками меняются местами между двумя родителями. Поскольку повторения не допускаются, каждый кроссовер предлагает технику, чтобы избежать/исключить повторения. Эти операторы кроссовера более разрушительны, чем ERX.
Пример OX-подобных кроссоверов: порядок кроссовера (OX), максимальный консервативный кроссовер (CX) и неполный кроссовер (PMX).
Первое семейство (ERX) лучше работает в простых генетических алгоритмах. В то время как второе семейство больше подходит в гибридном генетическом алгоритме или меметическом алгоритме (использование локального поиска). Эта статья подробно объясняет это.
В Traveling Salesrep Problem (TSP) вы хотите, чтобы заказ посетил список городов, и вы хотите посетить каждый город ровно один раз. Если вы кодируете города непосредственно в геноме, то наивный кроссовер или мутация часто генерируют неверный маршрут.
Когда-то я придумал новый подход к решению этой проблемы: вместо того, чтобы кодировать решение непосредственно в геноме, я вместо этого закодировал преобразование, которое бы переупорядочило канонический список значений.
Учитывая геном [1, 2, 4, 3, 2, 4, 1, 3], вы начнете со списка городов в произвольном порядке, скажем, в алфавитном порядке:
Тогда вы бы взяли каждую пару значений из генома и поменяли города на этих позициях. Итак, для генома выше вы замените их на 1 и 2, а затем на 4 и 3, а затем на 2 и 4 и, наконец, на 1 и 3. Вы получите:
С помощью этого метода вы можете использовать любой тип кроссовера или мутационной операции и все равно всегда получать действительный тур. Если геном достаточно длинный, то можно изучить все пространство решения.
Я использовал это для TSP и других проблем оптимизации с большим успехом.