Algoritmos Genéticos - Mutação

Introdução à mutação

Em termos simples, a mutação pode ser definida como um pequeno ajuste aleatório no cromossomo, para obter uma nova solução. É usado para manter e introduzir diversidade na população genética e é geralmente aplicado com uma baixa probabilidade -p_m. Se a probabilidade for muito alta, o AG fica reduzido a uma busca aleatória.

Mutação é a parte do GA que está relacionada à “exploração” do espaço de busca. Foi observado que a mutação é essencial para a convergência do GA, enquanto o crossover não é.

Operadores de mutação

Nesta seção, descrevemos alguns dos operadores de mutação mais comumente usados. Como os operadores de crossover, esta não é uma lista exaustiva e o designer do GA pode achar uma combinação dessas abordagens ou um operador de mutação específico para o problema mais útil.

Bit Flip Mutation

Nessa mutação de bit flip, selecionamos um ou mais bits aleatórios e os invertemos. Isso é usado para GAs codificados em binários.

Reinicialização aleatória

Random Resetting é uma extensão do bit flip para a representação inteira. Nesse caso, um valor aleatório do conjunto de valores permitidos é atribuído a um gene escolhido aleatoriamente.

Troca de mutação

Na mutação de troca, selecionamos duas posições no cromossomo aleatoriamente e trocamos os valores. Isso é comum em codificações baseadas em permutação.

Mutação Scramble

A mutação Scramble também é popular com representações de permutação. Neste, de todo o cromossomo, um subconjunto de genes é escolhido e seus valores são embaralhados ou embaralhados aleatoriamente.

Mutação de Inversão

Na mutação de inversão, selecionamos um subconjunto de genes como na mutação de embaralhamento, mas em vez de embaralhar o subconjunto, meramente invertemos a string inteira no subconjunto.