seleção roleta-roda em algoritmo genético. População precisa ser resolvido em primeiro lugar?

Question

Em uma algoritmo genético, ao selecionar membros para cruzamento usando o método de seleção de roleta rodas, faz a primeira necessidade população a ser classificados por categoria fitness?

As possibilidades parecem ser:

1. população espécie pela primeira vez por aptidão ascendente
2. população ordenar por descendente de fitness
3. não classificar população e deixar a bola de roleta queda onde for ..

Eu estou pensando que a classificação de qualquer forma pode não ter efeito - um pouso de cascalho de forma aleatória em uma roda contendo fatias diferentes porte (pela forma física) terá exatamente a mesma chance resultado se as fatias maiores são agrupados ou não. Mas eu não estou 100% convencido.

O que você acha?

A necessidade de fazer uma espécie cada geração afeta a velocidade do algoritmo também, então eu prefiro não (eu faria uma espécie se usar elitismo, mas não tenho, neste caso). Graças se você sabe, como eu não consegue encontrar uma resposta definitiva via google etc ..

Answer 1

Não, você não precisa realmente de classificá-los. Você está exatamente correto que ele não terá nenhum efeito se os membros mais elevados do ranking são agrupados ou não (pelo menos com um bom gerador de números aleatórios :)).

Sua intuição está morto aqui - estatisticamente, ele não terá efeito para classificar e como você menciona, você não tem que perder um monte de tempo e esforço classificando coisas

Answer 2

Mesmo se você aplicar elitismo, não há necessidade de classificar a população.

Encontrar os melhores indivíduos N requer apenas uma única iteração através da população.

Answer 3

Você não precisa para classificar a população se você usar tal seleção.

E você também está correto sobre a complexidade, uma espécie é n * log (n), fazendo com que o algoritmo genético significativamente mais lento (mas ainda assim, a complexidade permanece polinomial, uma característica crítica de um algoritmos genéticos).

Aqui está como eu faria isso (e obter pontos extras na escola para isso):

1. implementar uma solução mais genérica usando ganchos - antes de mutação, após a seleção etc etc

2. medir o número de iterações e a velocidade do algoritmo / cada iteração

3. fazer a sua classificação em um gancho. a medida. agora deixe o gancho estar vazio e medir e assim por diante.

Você vai ter alguns dados agradáveis ??e verificar experimentalmente que sua intuição lhe diz.