Seleção proporcional de aptidão - Fitness proportionate selection

Exemplo de seleção de um único indivíduo

A seleção proporcional de aptidão , também conhecida como seleção da roda de roleta , é um operador genético usado em algoritmos genéticos para selecionar soluções potencialmente úteis para recombinação.

Na seleção proporcional de aptidão, como em todos os métodos de seleção, a função de aptidão atribui uma aptidão a soluções ou cromossomos possíveis . Este nível de aptidão é usado para associar uma probabilidade de seleção a cada cromossomo individual. Se for a aptidão do indivíduo na população, sua probabilidade de ser selecionado é ${\ displaystyle f_ {i}}$${\ displaystyle i}$

${\ displaystyle p_ {i} = {\ frac {f_ {i}} {\ Sigma _ {j = 1} ^ {N} f_ {j}}},}$

onde está o número de indivíduos na população. ${\ displaystyle N}$

Isso pode ser imaginado como uma roda de roleta em um cassino. Normalmente, uma proporção da roda é atribuída a cada uma das seleções possíveis com base em seu valor de aptidão. Isso poderia ser conseguido dividindo a adequação de uma seleção pela adequação total de todas as seleções, normalizando-as para 1. Em seguida, uma seleção aleatória é feita semelhante à forma como a roda da roleta é girada.

Embora as soluções candidatas com uma adequação mais alta tenham menos probabilidade de serem eliminadas, ainda há uma chance de que sejam eliminadas porque sua probabilidade de seleção é menor que 1 (ou 100%). Compare isso com um algoritmo de seleção menos sofisticado, como seleção de truncamento , que eliminará uma porcentagem fixa dos candidatos mais fracos. Com a seleção proporcional de adequação, há uma chance de algumas soluções mais fracas sobreviverem ao processo de seleção. Isso ocorre porque, embora a probabilidade de que as soluções mais fracas sobrevivam seja baixa, não é zero, o que significa que ainda é possível que sobrevivam; isso é uma vantagem, porque há uma chance de que mesmo soluções fracas possam ter alguns recursos ou características que podem ser úteis após o processo de recombinação.

A analogia com uma roda de roleta pode ser considerada imaginando uma roda de roleta em que cada solução candidata representa um bolso na roda; o tamanho dos bolsos é proporcional à probabilidade de seleção da solução. Selecionar N cromossomos da população é equivalente a jogar N jogos na roleta, já que cada candidato é sorteado independentemente.

Outras técnicas de seleção, como amostragem universal estocástica ou seleção de torneio , são frequentemente utilizadas na prática. Isso porque possuem menos ruído estocástico, ou são rápidos, fáceis de implementar e possuem pressão de seleção constante.

A implementação ingênua é realizada gerando primeiro a distribuição de probabilidade cumulativa (CDF) sobre a lista de indivíduos usando uma probabilidade proporcional à aptidão do indivíduo. Um número aleatório uniforme do intervalo [0,1) é escolhido e o inverso do CDF para esse número dá um indivíduo. Isso corresponde à queda da bola da roleta na lixeira de um indivíduo com uma probabilidade proporcional à sua largura. O "bin" correspondente ao inverso do número aleatório uniforme pode ser encontrado mais rapidamente usando uma pesquisa binária sobre os elementos do CDF. Leva o tempo O (log n) para escolher um indivíduo. Uma alternativa mais rápida que gera indivíduos no tempo O (1) será a utilização do método alias .

Recentemente, foi introduzido um algoritmo muito simples baseado na "aceitação estocástica". O algoritmo seleciona aleatoriamente um indivíduo (digamos ) e aceita a seleção com probabilidade , onde é a aptidão máxima da população. Certas análises indicam que a versão de aceitação estocástica tem um desempenho consideravelmente melhor do que as versões baseadas em pesquisa linear ou binária, especialmente em aplicações onde os valores de aptidão podem mudar durante a execução. Embora o comportamento desse algoritmo seja normalmente rápido, algumas distribuições de aptidão (como distribuições exponenciais) podem exigir iterações no pior caso. Este algoritmo também requer mais números aleatórios do que a pesquisa binária. ${\ displaystyle i}$${\ displaystyle f_ {i} / f_ {M}}$${\ displaystyle f_ {M}}$${\ displaystyle O (n)}$

Pseudo-código

Por exemplo, se você tem uma população com adequações [1, 2, 3, 4], então a soma é (1 + 2 + 3 + 4 = 10). Portanto, você deseja que as probabilidades ou chances sejam [1/10, 2/10, 3/10, 4/10] ou [0,1, 0,2, 0,3, 0,4]. Se você normalizasse visualmente entre 0,0 e 1,0, seria agrupado como abaixo com [vermelho = 1/10, verde = 2/10, azul = 3/10, preto = 4/10]:

0.1 ]

0.2 \
0.3 /

0.4 \
0.5 |
0.6 /

0.7 \
0.8 |
0.9 |
1.0 /

Usando os números de exemplo acima, veja como determinar as probabilidades:

sum_of_fitness = 10
previous_probability = 0.0

[1] = previous_probability + (fitness / sum_of_fitness) = 0.0 + (1 / 10) = 0.1
previous_probability = 0.1

[2] = previous_probability + (fitness / sum_of_fitness) = 0.1 + (2 / 10) = 0.3
previous_probability = 0.3

[3] = previous_probability + (fitness / sum_of_fitness) = 0.3 + (3 / 10) = 0.6
previous_probability = 0.6

[4] = previous_probability + (fitness / sum_of_fitness) = 0.6 + (4 / 10) = 1.0

O último índice deve ser sempre 1,0 ou próximo a ele. Então, veja como selecionar aleatoriamente um indivíduo:

random_number # Between 0.0 and 1.0

if random_number < 0.1
    select 1
else if random_number < 0.3 # 0.3 − 0.1 = 0.2 probability
    select 2
else if random_number < 0.6 # 0.6 − 0.3 = 0.3 probability
    select 3
else if random_number < 1.0 # 1.0 − 0.6 = 0.4 probability
    select 4
end if

Veja também

• Seleção baseada em recompensa
• Amostragem universal estocástica
• Seleção de torneio

Referências

links externos

• Implementação C (.tar.gz; consulte seletor.cxx) WBL
• Exemplo na seleção da roda da Roleta
• Um esboço da implementação da versão O (1)