В этой главе мы обсудим, что такое оператор кроссовера, а также другие его модули, их использование и преимущества.
Введение в кроссовер
Оператор кроссовера аналогичен воспроизведению и биологическому кроссоверу. При этом выбирается более одного родителя, и один или несколько потомков производятся с использованием генетического материала родителей. Кроссовер обычно применяется в GA с высокой вероятностью — p c .
Операторы кроссовера
В этом разделе мы обсудим некоторые из наиболее популярных операторов кроссовера. Следует отметить, что эти операторы кроссовера являются очень общими, и GA Designer может также решить реализовать оператор кроссовера для конкретной задачи.
One Point Crossover
В этом одноточечном пересечении выбирается случайная точка пересечения, и хвосты двух ее родителей меняются местами, чтобы получить новые исходные элементы.
Многоточечный кроссовер
Многоточечный кроссовер — это обобщение одноточечного кроссовера, в котором чередующиеся сегменты меняются местами для получения новых выходных пружин.
Единый кроссовер
В равномерном кроссовере мы не делим хромосому на сегменты, мы рассматриваем каждый ген отдельно. В этом мы по существу подбрасываем монету для каждой хромосомы, чтобы решить, будет ли она включена в потомство. Мы также можем привязать монету к одному из родителей, чтобы у ребенка было больше генетического материала от этого родителя.
Целая арифметическая рекомбинация
Это обычно используется для целочисленных представлений и работает, взяв средневзвешенное значение двух родителей, используя следующие формулы:
- Child1 = α.x + (1-α) .y
- Child2 = α.x + (1-α) .y
Очевидно, что если α = 0,5, то оба потомка будут идентичны, как показано на следующем рисунке.
Кроссовер Ордена Дэвиса (OX1)
OX1 используется для кроссоверов на основе перестановок с целью передачи информации об относительном упорядочении выходным источникам. Это работает следующим образом —
-
Создайте две случайные точки пересечения в родительском элементе и скопируйте сегмент между ними от первого родительского элемента к первому потомству.
-
Теперь, начиная со второй точки пересечения во втором родительском элементе, скопируйте оставшиеся неиспользуемые числа от второго родительского элемента к первому дочернему элементу, оборачивая список.
-
Повторите эти действия для второго ребенка с перевернутой ролью родителя.
Создайте две случайные точки пересечения в родительском элементе и скопируйте сегмент между ними от первого родительского элемента к первому потомству.
Теперь, начиная со второй точки пересечения во втором родительском элементе, скопируйте оставшиеся неиспользуемые числа от второго родительского элемента к первому дочернему элементу, оборачивая список.
Повторите эти действия для второго ребенка с перевернутой ролью родителя.
Существует множество других кроссоверов, таких как кроссинговер с частичным отображением (PMX), кроссовер на основе заказов (OX2), кроссовер с перемешиванием, кольцевой кроссовер и т. Д.