Como vimos, depois de calculada a qualidade dos indivíduos da população, é necessário decidir quais irão produzir descendentes para a próxima geração, e em que proporção. Em geral, o método de selecção deve permitir que os melhores indivíduos sejam escolhidos mais vezes, na esperança de que os seus descendentes sejam ainda melhores, possibilitando assim que a população evolua até se encontrar uma solução. Existem vários textos, como por exemplo [Bäck, 1994] e [Blickle, 1995], que analisam e comparam métodos de selecção. Não existem, no entanto, técnicas que ajudem a decidir, à priori, qual o melhor método a utilizar num determinado problema. A seguir, iremos descrever brevemente alguns dos métodos de selecção mais utilizados.
Selecção proporcional ao desempenho
Descreveremos dois métodos de selecção proporcional ao desempenho. No método da roleta, a probabilidade de um indivíduo i ser seleccionado é
∑
= N j j i i f f pem que N é o tamanho da população. Pode-se ver este mecanismo de selecção como se a cada indivíduo da população correspondesse uma fatia de uma roleta proporcional ao seu desempenho. A roleta é posta a girar N vezes e em cada uma é seleccionado um indivíduo. Obviamente, é esperado que o número de vezes que um indivíduo é seleccionado seja proporcional ao seu desempenho. No entanto, isto nem sempre acontece, sobretudo em populações pequenas [Mitchell, 1996], podendo suceder que indivíduos fracos são seleccionados bastante mais vezes do que seria esperado.
O método da amostragem universal estocástica procura resolver este problema colocando de uma vez só sobre a roleta N ponteiros igualmente distribuídos. Assim, um indivíduo será seleccionado tantas vezes quantos os ponteiros que estiverem sobre a sua fatia, ou seja, nunca menos que o valor esperado truncado, e nunca mais que o valor esperado truncado e incrementado.
Os métodos de selecção proporcional ao desempenho têm algumas desvantagens relativamente a outros métodos, nomeadamente, porque as probabilidades de selecção dependem fortemente do escalonamento da função de desempenho [Blickle, 1995]. Pode-se tentar resolver este problema utilizando métodos de escalonamento que permitem adaptar os valores da função de desempenho à média da população. Existe ainda outro problema que deriva do facto de o desvio padrão do desempenho dos indivíduos no início da evolução ser, geralmente, alto. Nestas condições, os indivíduos com maior desempenho têm tendência para se multiplicar consideravelmente dominando rapidamente a população (nestes casos diz-se que a pressão selectiva é elevada) e impedindo a exploração de outras regiões do espaço de pesquisa. Por outro lado, quando mais tarde todos indivíduos da população forem muito parecidos, o número de descendentes é quase igual tornando a convergência muito lenta.
Selecção por posição
Na selecção por posição os indivíduos da população são ordenados pelo valor do seu desempenho cabendo ao melhor indivíduo a posição N e ao pior a posição 1. A
probabilidade de selecção é atribuída linearmente ou exponencialmente de acordo com a posição de cada indivíduo. Se, por exemplo, for utilizada uma distribuição linear, a probabilidade de um indivíduo ser seleccionado é dada por
(
)
− − − + = − + − 1 1 1 N i p p p N piem que p− N é a probabilidade do pior indivíduo ser seleccionado e p+ N é a probabilidade de o melhor indivíduo ser seleccionado.
Este método procura reduzir a rápida convergência para um máximo local que ocorre nos métodos de selecção proporcional ao desempenho já descritos. Como a selecção é baseada na posição e não no valor relativo do desempenho dos indivíduos, é possível evitar que um pequeno conjunto de indivíduos com um desempenho muito superior ao do resto da população domine as populações subsequentes. Por outro lado, se o desvio padrão do desempenho dos indivíduos for baixo, a pressão selectiva pode ser mantida.
Selecção por truncamento
Neste método, os indivíduos da população são ordenados pelo seu desempenho e depois, apenas uma fracção T dos melhores indivíduos pode ser seleccionada, tendo estes a mesma probabilidade de serem seleccionados. A pressão selectiva será tanto maior quanto mais pequeno for o valor de T.
Selecção Sôfrega23
Este método é algo parecido com o anterior mas permite que os indivíduos mais fracos possam também ser escolhidos. Para o aplicar é necessário começar por ordenar os indivíduos da população por ordem decrescente do seu desempenho. Depois, divide-se a população em dois grupos: o grupo I, formado pelos melhores indivíduos responsáveis por c% da soma do valor do desempenho de todos os indivíduos da população, e o grupo II, formado pelos restantes. A selecção dos indivíduos é depois realizada da seguinte forma: p% das vezes é escolhido um indivíduo do grupo I e (100 - p)% das vezes é escolhido um indivíduo do grupo II. Dentro de cada grupo os indivíduos são escolhidos com o método de selecção
proporcional ao desempenho. A pressão selectiva deste método será tanto maior quanto maior for o valor de c e p.
Selecção por torneio
O método de selecção por torneio funciona repetindo N vezes o seguinte procedimento: escolhe-se aleatoriamente um número t de indivíduos da população e selecciona-se o melhor deste grupo. É frequente o torneio ser disputado entre dois indivíduos, embora se possa utilizar um valor maior para t, o tamanho do torneio. Quanto maior for este valor, maior será a pressão selectiva.
Este método tem como vantagem o facto de ser computacionalmente mais eficiente que os métodos já descritos pois não necessita de uma comparação centralizada entre todos os indivíduos. Esta característica permite acelerar consideravelmente o processo de evolução, além de que permite paralelizar facilmente o algoritmo [Banzhaf, 1998].