Algoritmos Genéticos - Crossover

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

Introdução ao Crossover

O operador de crossover é análogo à reprodução e ao crossover biológico. Neste, mais de um pai é selecionado e uma ou mais descendentes são produzidos usando o material genético dos pais. O crossover é geralmente aplicado em um GA com alta probabilidade -pc .

Operadores de crossover

Nesta seção, discutiremos alguns dos operadores de crossover mais usados. Deve-se notar que esses operadores de crossover são muito genéricos e o GA Designer pode escolher implementar um operador de crossover específico para o problema também.

Crossover de um ponto

Neste crossover de um ponto, um ponto de crossover aleatório é selecionado e as caudas de seus dois pais são trocadas para obter novas origens.

Crossover multiponto

O crossover multiponto é uma generalização do crossover de um ponto em que segmentos alternados são trocados para obter novas origens.

Crossover uniforme

Em um cruzamento uniforme, não dividimos o cromossomo em segmentos, em vez disso, tratamos cada gene separadamente. Nesse caso, basicamente lançamos uma moeda para cada cromossomo para decidir se ele será ou não incluído na prole. Também podemos enviesar a moeda para um dos pais, para ter mais material genético no filho desse pai.

Recombinação Aritmética Total

Isso é comumente usado para representações inteiras e funciona tirando 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, então os dois filhos serão idênticos, conforme mostrado na imagem a seguir.

Cruzamento da ordem de Davis (OX1)

OX1 é usado para cruzamentos baseados em permutação com a intenção de transmitir informações sobre a ordenação relativa às nascentes. 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 do segundo ponto de cruzamento no segundo pai, copie os números não usados ​​restantes do segundo pai para o primeiro filho, envolvendo a lista.

  • Repita para o segundo filho com o papel do pai invertido.

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