selezione roulette ruota algoritmo genetico. Popolazione deve essere risolto prima?

Question

In un algoritmo genetico, quando si selezionano i membri per l'incrocio con il metodo di selezione roulette ruote, non la popolazione prima bisogno di essere ordinati per rango di forma fisica?

Le possibilità sembrano essere:

1. popolazione sorta prima salendo forma fisica
2. sorta popolazione scendendo forma fisica
3. Non in ordine di popolazione e lasciò cadere pallina della roulette dove può ..

sto pensando che l'ordinamento in entrambi i casi potrebbe non avere effetto - un atterraggio di ciottoli a caso su una ruota che contiene diverse dimensioni (da fitness) fette avranno esattamente la stessa probabilità esito se le fette più grandi sono raggruppati insieme o no. Ma io non sono convinto al 100%.

Cosa ne pensi?

La necessità di fare una sorta ogni generazione influisce sulla velocità dell'algoritmo troppo, quindi preferisco non (vorrei fare una specie se si utilizza elitarismo, ma io non sono in questo caso). Grazie se si sa, come non riesco a trovare una risposta definitiva tramite google etc ..

Answer 1

No, in realtà non c'è bisogno di ordinarli. Lei è esattamente corretto che essa non avrà alcun effetto se i membri di alto-ordinati sono raggruppati insieme oppure no (almeno con un buon generatore di numeri casuali :)).

La tua intuizione è morto qui - statisticamente, non avrà alcun effetto per ordinare, e come si parla, non c'è bisogno di sprecare un sacco di tempo e fatica risolvere le cose

Answer 2

Anche se si applica elitarismo, non c'è bisogno di ordinare la popolazione.

Trovare i migliori N individui richiede solo una singola iterazione tra la popolazione.

Answer 3

Non è necessario ordinare la popolazione se si utilizza un tale selezione.

E sei anche una corretta informazione circa la complessità, è una sorta n * log (n), rendendo l'algoritmo genetico molto più lento (ma ancora, la complessità rimane polinomiale, una caratteristica fondamentale di un algoritmi genetici).

Ecco come vorrei farlo (e ottenere punti extra a scuola per questo):

1. implementare una soluzione più generica con ganci - prima mutazione, dopo la selezione ecc ecc

2. misurare il numero di iterazioni e la velocità dell'algoritmo / ogni iterazione

3. fare il vostro ordinamento in un gancio. misurare. ora lasciare che il gancio sia vuoto e misura e così via.

Si otterrà alcuni dati curato e sperimentalmente verificare ciò che il vostro intuito vi dice.