IX. Seleção

Introdução

Como você já sabe de AG esboço, os cromossomas são selecionados de uma população para serem pais de um cruzamento. O problema é como selecionar esses cromossomas. De acordo com a teoria da evolução de Darwin, o melhor sobrevive para criar a descendência. Há muitos métodos para selecionar o melhor cromossoma. Exemplos são: seleção por roleta, seleção Boltzman, seleção por campeonato, seleção por classificação, seleção por estado estacionário, e outras.

Algumas delas serão descritas a seguir.

Seleção por Roleta

Os pais são selecionados de acordo com sua adequação. Quanto melhores são os cromossomos, mais chances de serem selecionados. Imagine uma roleta onde são colocados todos os cromossomas da população. O lado de cada secção da roleta é proporcional ao valor da adequação de cada cromossoma: quanto maior for esse valor, mais larga a secção. Veja a imagem a seguir para um exemplo.

Uma bolinha é lançada na roleta e o cromossomo onde ela para é selecionado. Evidentemente os cromossomas com maiores valores de adequação serão selecionados mais vezes.

Este processo pode ser descrito pelo seguinte algoritmo:

[Soma] Calcule a soma dos valores de adequação de todos os cromossomas da população - soma S.
[Seleção] Gere um número aleatório no intervalo (0,S) - r.
[Repetição] Percorra toda a população e some a adequação de 0 - soma s. Quando a soma s for maior que r, pare e retorne o cromossoma atual.

É claro, o passo 1 somente é realizado uma vez para cada população.

Seleção por Classificação

O método anterior de seleção tem problemas quando há grandes diferenças entre os valores de adequação. Por exemplo, se a melhor adequação dos cromossomas é 90% da soma de todas as adequações, então haverá cromossomas com chances muito baixas de serem selecionados.

A Seleção por Classificação primeiro classifica a população e então atribui a cada cromossoma um valor de adequação determinado pela sua classificação. O pior terá adequação igual a 1, o segundo pior 2 etc. de forma que o melhor terá adequação igual a N (número de cromossomas na população).

Você pode ver na figura seguinte como a situação muda depois de mudar a adequação pelos números determinados pela adequação.

Situação antes da Classificação (gráfico da adequação)

Situação depois da Classificação (gráfico dos números de ordem)

Agora todos os cromossomas tem uma chance de serem selecionados. Entretanto, este método pode resultar em menor convergência, porque os melhores cromossomas não se distinguem muito dos outros.

Seleção por Estado Estacionário

Este não é um método particular de seleção de pais. A idéia principal deste tipo de seleção é que a nova população deve ter uma grande parte de cromossomas que sobreviverão para a próxima geração.

A seleção tipo Estado Estacionário dos AG funciona do seguinte modo: Em cada nova geração uns poucos bons cromossomas (com alta adequação) são selecionados para a criação da descendência. A seguir alguns maus cromossomas (com baixa adequação) são removidos e novos descendentes são colocados em seus lugares. Todo o resto da população sobrevive para as próximas gerações.

Elitismo

A idéia básica do elitismo já foi introduzida. Quando criamos uma nova população por cruzamento e mutação, nós temos uma grande chance de perder os melhores cromossomas.

Elitismo é o nome do método que primeiro copia os melhores cromossomas (or os poucos melhores cromossomas) para a nova população. O resto da população é construída das formas descritas acima. Elitismo pode aumentar rapidamente o desempenho do AG, porque previne a perda da melhor solução já encontrada.