XI. 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 codificação binária podem ser usados

Mutação

Adicionando um número pequeno (para codificação de valores reais) - um número pequeno é adicionado a (ou subtraído de) valores selecionados

(1.29  5.68  2.86  4.11  5.55) => (1.29  5.68  2.73  4.22  5.55)




Codificação em Árvore

Cruzamento

Cruzamento de Árvores - um ponto de cruzamento é escolhido em ambos os pais, os pais são divididos nesse ponto e as partes abaixos do ponto de cruzamento são trocadas para produzir a descendência

Mutação

Mudando o operador - os nós escolhidos são mudados


           
(c) Marek Obitko, 1998