Algoritmos Genéticos - Seleção de Pais
Seleção de pais é o processo de seleção de pais que se acasalam e se recombinam para criar descendentes para a próxima geração. A seleção dos pais é crucial para a taxa de convergência do AG, pois bons pais conduzem os indivíduos a soluções melhores e mais adequadas.
No entanto, deve-se ter cuidado para evitar que uma solução extremamente adequada ocupe toda a população em algumas gerações, pois isso faz com que as soluções fiquem próximas umas das outras no espaço de solução, levando a uma perda de diversidade. Maintaining good diversityna população é extremamente crucial para o sucesso de um AG. Essa ocupação de toda a população por uma solução extremamente adequada é conhecida comopremature convergence e é uma condição indesejável em um GA.
Seleção Proporcional de Fitness
A seleção proporcional de condicionamento físico é uma das formas mais populares de seleção dos pais. Nisso, todo indivíduo pode se tornar um pai com uma probabilidade proporcional à sua aptidão. Portanto, indivíduos mais aptos têm uma chance maior de acasalar e propagar suas características para a próxima geração. Portanto, tal estratégia de seleção aplica uma pressão de seleção aos indivíduos mais aptos da população, evoluindo os indivíduos melhores ao longo do tempo.
Considere uma roda circular. A roda é dividida emn pies, onde n é o número de indivíduos na população. Cada indivíduo recebe uma parte do círculo que é proporcional ao seu valor de aptidão.
Duas implementações de seleção proporcional de aptidão são possíveis -
Seleção de Roleta
Em uma seleção de roda de roleta, a roda circular é dividida conforme descrito anteriormente. Um ponto fixo é escolhido na circunferência da roda conforme mostrado e a roda é girada. A região da roda que fica na frente do ponto fixo é escolhida como pai. Para o segundo pai, o mesmo processo é repetido.
É claro que um indivíduo mais apto tem uma torta maior na roda e, portanto, uma chance maior de pousar na frente do ponto fixo quando a roda é girada. Portanto, a probabilidade de escolher um indivíduo depende diretamente de sua aptidão.
Em termos de implementação, usamos as seguintes etapas -
Calcule S = a soma das sutilezas.
Gere um número aleatório entre 0 e S.
Começando do topo da população, continue adicionando as sutilezas à soma parcial P, até P <S.
O indivíduo para o qual P excede S é o indivíduo escolhido.
Amostragem Estocástica Universal (SUS)
A Amostragem Universal Estocástica é bastante semelhante à seleção da roda da Roleta, entretanto, em vez de ter apenas um ponto fixo, temos vários pontos fixos, como mostrado na imagem a seguir. Portanto, todos os pais são escolhidos em apenas um giro da roda. Além disso, tal configuração incentiva os indivíduos altamente aptos a serem escolhidos pelo menos uma vez.
É de notar que os métodos de seleção proporcionais de aptidão não funcionam para casos em que a aptidão pode assumir um valor negativo.
Seleção de torneio
Na seleção do torneio K-Way, selecionamos K indivíduos da população aleatoriamente e selecionamos o melhor deles para se tornar um pai. O mesmo processo é repetido para selecionar o próximo pai. A seleção de torneio também é extremamente popular na literatura, pois pode até funcionar com valores de condicionamento físico negativos.
Seleção de Classificação
A Seleção de Classificação também funciona com valores de aptidão negativos e é usada principalmente quando os indivíduos na população têm valores de aptidão muito próximos (isso geralmente acontece no final da corrida). Isso leva a cada indivíduo tendo uma parte quase igual do bolo (como no caso de seleção proporcional de adequação), conforme mostrado na imagem a seguir e, portanto, cada indivíduo, independentemente de quão adequado em relação ao outro, tem aproximadamente a mesma probabilidade de ser selecionado como um pai. Isso, por sua vez, leva a uma perda na pressão de seleção em relação aos indivíduos mais aptos, fazendo com que o AG faça seleções de pais ruins em tais situações.
Com isso, removemos o conceito de um valor de adequação ao selecionar um pai. No entanto, cada indivíduo na população é classificado de acordo com sua aptidão. A seleção dos pais depende da classificação de cada indivíduo e não da aptidão. Os indivíduos de classificação mais alta são mais preferidos do que os de classificação inferior.
| Cromossoma | Valor de aptidão | Classificação |
|---|---|---|
| UMA | 8,1 | 1 |
| B | 8,0 | 4 |
| C | 8,05 | 2 |
| D | 7,95 | 6 |
| E | 8.02 | 3 |
| F | 7,99 | 5 |
Seleção aleatória
Nesta estratégia, selecionamos aleatoriamente os pais da população existente. Não há pressão de seleção para indivíduos mais aptos e, portanto, essa estratégia geralmente é evitada.