(c) Marek Obitko, 1998
Probabilidade de Cruzamento e de Mutação
Há dois parâmetros básicos dos AG - Probabilidade de Cruzamento e de Mutação.
Probabilidade de Cruzamento: com qual freqüência o cruzamento é realizado. Se não não houver cruzamento, a descendência é uma cópia exata dos pais. Se ocorre o cruzamento a descendência é constituída de partes dos cromossomas de ambos os pais. Se a probabilidade de cruzamento é 100%, então toda a descendência é produzida por cruzamento. Se a probabilidade é 0%, toda a nova geração é formada por cópia exata dos cromossomas da população antiga (mas isso não significa que a nova geração é a mesma!).
Os cruzamentos são realizados na esperança de que os novos cromossomas contenham partes boas dos cromossomas antigos e que portanto os novos cromossomas serão melhores. Entretanto, é bom deixar uma parte da antiga população sobreviver para a próxima geração.
Probabilidade de Mutação: com qual freqüência as partes dos cromossomas sofrerão mutação. Se não houver mutação, a descendência é gerada imediatamente após o cruzamento (ou copiada diretamente) sem nenhuma alteração. Se ocorreu a mutação, uma ou mais partes do cromossoma é alterada. Se a probabilidade de mutação é 100%, todos os cromossomas são alterados, se é 0%, nenhum é alterado.
A mutação em geral evita que o AG caia num extremo (mínimo ou máximo) local. A mutação não deve ocorrer com muita freqüência porque senão o AG tornar-se-á de fato uma busca aleatória.
Outros Parâmetros
Temos também alguns outros parâmetros nos AG. Um particularmente importante é o tamanho da população.
Tamanho da População: quantos cromossomas existem na população (em uma geração). Se houver poucos cromossomas, o AG terá poucas possibilidade de realizar cruzamentos e somente uma parte pequena do espaço de soluções será explorada. Por outro lado, se houver muitos cromossomas, os AG tornar-se-ão lentos. Pesquisas mostram que após determinado limite (que depende principalmente da codificação e do problema), não é conveniente aumentar a população porque isso não resolve o problema mais rapidamente do que com tamanhos moderados de população.
Algumas recomendações para os parâmetros podem ser encontradas nos capítulos seguintes.
Exemplo
Aqui você pode ver um exemplo similar ao anterior. Porém aqui você pode mudar a probabilidade de cruzamento e de mutação. É possível também controlar o elitismo.
No gráfico abaixo você pode ver o desempenho do AG. A vermelha é a melhor solução, a azul é o valor médio (adequação) de toda a população.
Mude os parâmetros e veja como o AG se comporta.
Questão: Se você aumenta a probabilidade da mutação até 100%, o AG começará a se comportar de maneira muito estranha, de uma forma parecida como se a probabilidade de mutação fosse 0%. Você sabe por que? Você pode ver uma dica e se mesmo assim você não conseguir descobrir, veja a resposta em: solução!