# Recombinação (computação evolutiva)

Em algoritmos genéticos a recombinação ou crossover é um operador genético usado para variar a programação de um cromossomo ou cromossomas de uma geração para a próxima. É análogo à reprodução e recombinação genética, sobre as quais os algoritmos genéticos são baseados. Uma recombinação é um processo de se pegar mais de uma solução progenitora e produzir uma solução descendente a partir deles. Existem métodos para a seleção dos cromossomos. Alguns deles são fornecidos abaixo.

## Métodos de seleção de cromossomos para o cruzamento

* Amostragem estocástica uniforme (Stochastic universal sampling) O indivíduo é selecionado com base em sua aptidão. A probabilidade de um indivíduo ser selecionado aumenta proporcionalmente à medida de sua aptidão em relação aos demais candidatos a progenitor. Os indivíduos são mapeados em segmentos contíguos de uma reta proporcionais à sua aptidão.
* Método da Roleta (Roulette wheel selection) (SCX) Também é conhecido como seleção proporcional à aptidão (Fitness-Proportionate Selection). O indivíduo é selecionado com base em sua aptidão. A probabilidade de um indivíduo ser selecionado aumenta proporcionalmente à medida de sua aptidão em relação aos demais candidatos a progenitor. Difere da amostragem estocástica uniforme simplesmente por ser em uma roleta viciada ao invés de uma reta.
* Seleção Boltzmann (Boltzmann selection) Estabelece uma pressão de seleção variável de acordo com o tempo da pesquisa de solução. Inicialmente, permite a reprodução de indivíduos com baixa aptidão de modo a manter a diversidade da população e evitar convergências prematuras. Com o tempo, vai aumentando a pressão seletiva de modo a favorecer cada vez mais os indivíduos com aptidão mais alta.
* Método do Torneio (Tournament selection) Consiste em selecionar uma série de indivíduos da população e estabelecer entre eles uma competição pelo direito de ser um dos progenitores.
* Seleção por ranking (Rank selection)
* Seleção Truncada (Truncation selection)
* Steady state selection
* Seleção local (Local selection)

## Técnicas de recombinação

Muitas técnicas de recombinação para organismos existem que usam diferentes estruturas de dados para armazenar elas mesmas.

### Recombinação em um ponto

Um único ponto para recombinação é selecionado em ambos os organismos progenitores. Todos os dados além do ponto selecionados são trocados entre os progenitores. Os organismos resultantes são os filhos:

### Recombinação em dois pontos

A recombinação em dois pontos necessita que dois pontos sejam selecionados nas cadeias dos organismos progenitores. Tudo que está entre estes dois pontos é trocado entre os progenitores resultando nos filhos:

### "Corte e emenda"

Outra variação de recombinação, a abordagem "corte e emenda", resulta na troca de comprimento entre os filhos. A razão para esta diferença é que se escolhe o ponto de corte de cada progenitor separadamente.

### Recombinação uniforme e recombinação metade uniforme

Em ambos estes esquemas os progenitores se combinam para formar seus descendentes.
No esquema da recombinação uniforme (UX do inglês Uniform Crossover), os bits do vetor são comparados individualmente entre ambos progenitores. Os bites se intercambiam com uma probabilidade fixada, usualmente 0.5.
No esquema da recombinação metade uniforme (HUX do inglês Half Uniform Crossover), exatamente a metade dos bits que são diferentes são trocados. Por isto se faz necessário se calcular a distância de Hamming (número de bits diferentes). Este número se divide por dois, e o número resultante é a quantidade de bits diferentes que tem que ser intercambiados entre os progenitores.

### Recombinação com três progenitores

Nesta técnica, o descendente é derivado a partir de três pais. Eles são escolhidos aleatoriamente. Cada bit do primeiro pai é verificado com o bit do segundo pai se eles são os mesmos. Se são os mesmos então o bit é levado para a prole de outro modo o bit do terceiro pai é levado para a prole. Por exemplo, os seguintes três pais:
pai1 1 1 0 1 0 0 0 1 0
pai2 0 1 1 0 0 1 0 0 1
pai3 1 1 0 1 1 0 1 0 1 produzem a seguinte prole:
prole 1 1 0 1 0 0 0 0 1

### Recombinação para cromossomos ordenados

Dependendo de como o cromossoma representa a solução, uma troca direta não pode ser possível. Um desses casos é quando o cromossomo é uma lista ordenada, como uma lista ordenada das cidades a ser percorrida para o problema do caixeiro viajante. Existem muitos métodos de recombinação para cromossomos ordenados. A já mencionada recombinação de N-pontos pode ser aplicada para cromossomas ordenados também, mas isto sempre necessita de um reparo correspondente, na realidade, alguns métodos de recombinação ordenados derivam desta ideia. Contudo, algumas vezes uma recombinação de cromossomos produz recombinações que violam a restrição de ordenamento e portanto necessitam de ser reparados. Vários exemplos de operadores de recombinação (também operadores de mutação) são dados em:
* partially matched crossover (PMX): Neste método, dois pontos de recombinação são selecionados aleatoriamente e o PMX atua posicionando trocas sábias. Os dois pontos de recombinação fornecem a seleção correspondente. Ela afeta o cruzamento pelas operações de troca, posição por posição. Neste método os pais são mapeados para o outro, portanto, também se pode chamar partially mapped crossover.
* cycle crossover (CX): Começando em qualquer gene $i$ no progenitor 1, o $i$-ésimo gene no progenitor 2 torna-se substituído por ele. O mesmo é repetido para o gene deslocado até que o gene que é igual ao primeiro gene inserido fica substituído (ciclo).
* order crossover operator (OX1 ou OX): Uma parte de um dos progenitores é mapeada para uma porção do outro progenitor. A partir da porção substituída, o resto é preenchido pelos genes remanescentes, onde genes já presentes são omitidos e a ordem é preservada.
* order-based crossover operator (OX2 ou OBX)
* position-based crossover operator (POS)
* voting recombination crossover operator (VR)
* alternating-position crossover operator (AP)
* sequential constrictive crossover operator (SCX)
Outros métodos possíveis incluem o edge recombination operator.

## Recombinações tendenciosas

Para os operadores de cruzamento que trocam seções contíguas dos cromossomos (por exemplo, k-ponto) a ordenação das variáveis ​​pode tornar-se importante. Isto é particularmente verdadeiro quando boas soluções contêm blocos de construção que podem ser perturbados por um operador de crossover que não respeite esta ordem.