Cruzamento genético

Cruzamento e Mutação

Introdução
Cruzamento e Mutação são os dois operadores básicos de AG. O desempenho do AG depende muito deles. O tipo e a implementação desses operadores dependem da codificação e também do problema
Há diversas maneiras de como fazer o cruzamento e a mutação. Neste capítulo descreveremos brevemente alguns exemplos e sugestões de como fazê-los para diversos tipos de codificação.

Codificação Binária
Cruzamento
Ponto de Cruzamento Único - um ponto de cruzamento é escolhido, a série binária desde o começo do cromossoma até o ponto de cruzamento é copiada do primeiro pais e o resto copiado do outro pai

11001011+11011111 = 11001111
Dois pontos de cruzamento - são definidos dois pontos de cruzamento, a série binária desde o início do cromossoma até o primeiro ponto de cruzamento é copiada do primeiro pai, a parte do primeiro ponto de cruzamento até o segundo ponto é copiada do outro pai e o resto do cromossoma é copiado do primeiro pai novamente

11001011 + 11011111 = 11011111
Cruzamento Uniforme - os bits são copiados aleatóriamento do primeiro ou segundo pai

11001011 + 11011101 = 11011111
Cruzamento Aritmético - é realizada uma operação aritmética para obter a nova geração

11001011 + 11011111 = 11001001 (AND)
Mutação
Inversão de Bit - determinados bits são invertidos

11001001 => 10001001

Codificação por Permutação
Cruzamento
Ponto de Cruzamento Único - um ponto de cruzamento é selecionado e a permutação é copiada atéone crossover point is selected, the permutation is copied do primeiro pai até o ponto de cruzamento, daí o outro pai é rastreado e se o número ainda não estiver na descendência, é adicionado
Nota: há outras maneiras de obter o resto após o ponto de cruzamento
(1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) = (1 2 3 4 5 6 8 9 7)
Mutação
Mudança de Ordem - dois números são escolhidos e trocados entre si
(1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7)

Codificação de Valores
Cruzamento
Todos os cruzamentos de