Algoritmos Genéticos - Crossover

Neste capítulo, discutiremos sobre o que é um Operador Crossover, juntamente com seus outros módulos, seus usos e benefícios.

Introdução ao Crossover

O operador de cruzamento é análogo à reprodução e cruzamento biológico. Nisto, mais de um pai é selecionado e uma ou mais nascentes são produzidas usando o material genético dos pais. O crossover é geralmente aplicado em um GA com uma alta probabilidade - p c .

Operadores de crossover

Nesta seção, discutiremos alguns dos operadores de crossover mais populares. É importante observar que esses operadores de crossover são muito genéricos e o GA Designer também pode optar por implementar um operador de crossover específico ao problema.

One Point Crossover

Nesse cruzamento de um ponto, um ponto de cruzamento aleatório é selecionado e as caudas de seus dois pais são trocadas para obter novas fontes.

One Point Crossover

Multi Point Crossover

Crossover de múltiplos pontos é uma generalização do crossover de um ponto em que segmentos alternados são trocados para obter novas fontes.

Multi Point Crossover

Passagem uniforme

Em um cruzamento uniforme, não dividimos o cromossomo em segmentos, mas tratamos cada gene separadamente. Nesse sentido, basicamente jogamos uma moeda para cada cromossomo para decidir se ela será ou não incluída na primavera. Também podemos influenciar a moeda para um dos pais, para ter mais material genético na criança desse pai.

Passagem uniforme

Recombinação Aritmética Inteira

Isso geralmente é usado para representações inteiras e funciona calculando a média ponderada dos dois pais usando as seguintes fórmulas -

  • Criança1 = α.x + (1-α) .y
  • Criança2 = α.x + (1-α) .y

Obviamente, se α = 0,5, as duas crianças serão idênticas, como mostrado na imagem a seguir.

Recombinação Aritmética Inteira

Passagem de pedidos de Davis (OX1)

OX1 é usado para cruzamentos baseados em permutações com a intenção de transmitir informações sobre pedidos relativos às fontes externas. Funciona da seguinte maneira -

  • Crie dois pontos de cruzamento aleatórios no pai e copie o segmento entre eles do primeiro pai para o primeiro filho.

  • Agora, começando no segundo ponto de cruzamento no segundo pai, copie os números restantes não utilizados do segundo pai para o primeiro filho, agrupando a lista.

  • Repita o procedimento para o segundo filho com a função dos pais invertida.

Existem muitos outros crossovers como Crossover parcialmente mapeado (PMX), crossover baseado em ordem (OX2), crossover aleatório, crossover de anel, etc.