Loading AI tools
Da Wikipédia, a enciclopédia livre
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.
Muitas técnicas de recombinação para organismos existem que usam diferentes estruturas de dados para armazenar elas mesmas.
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:
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:
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.
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.
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[3]
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 idéia. 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 [4]:
Outros métodos possíveis incluem o edge recombination operator.
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.