Algoritmi genetici - Selezione genitore
La selezione dei genitori è il processo di selezione dei genitori che si accoppiano e si ricombinano per creare discendenti per la generazione successiva. La selezione dei genitori è molto cruciale per il tasso di convergenza dell'AG, poiché i buoni genitori guidano le persone verso soluzioni migliori e più adatte.
Tuttavia, è necessario prestare attenzione per evitare che una soluzione estremamente adatta si impossessi dell'intera popolazione in poche generazioni, poiché ciò porta a soluzioni vicine l'una all'altra nello spazio della soluzione, con conseguente perdita di diversità. Maintaining good diversitynella popolazione è estremamente cruciale per il successo di un GA. Questo assorbimento dell'intera popolazione da parte di una soluzione estremamente adatta è noto comepremature convergence ed è una condizione indesiderabile in un GA.
Selezione proporzionata del fitness
La selezione proporzionale del fitness è uno dei modi più popolari di selezione dei genitori. In questo ogni individuo può diventare genitore con una probabilità proporzionale alla sua forma fisica. Pertanto, gli individui più in forma hanno maggiori possibilità di accoppiarsi e propagare le loro caratteristiche alla generazione successiva. Pertanto, una tale strategia di selezione applica una pressione selettiva agli individui più in forma nella popolazione, evolvendo individui migliori nel tempo.
Considera una ruota circolare. La ruota è divisa inn pies, dove n è il numero di individui nella popolazione. Ogni individuo riceve una porzione del cerchio che è proporzionale al suo valore di fitness.
Sono possibili due implementazioni della selezione proporzionale alla forma fisica:
Selezione della ruota della roulette
Nella selezione della ruota della roulette, la ruota circolare è divisa come descritto in precedenza. Si sceglie un punto fisso sulla circonferenza della ruota come mostrato e la ruota viene ruotata. La regione della ruota che si trova davanti al punto fisso viene scelta come genitore. Per il secondo genitore, viene ripetuto lo stesso processo.
È chiaro che un individuo più in forma ha una maggiore torta sulla ruota e quindi una maggiore possibilità di atterrare davanti al punto fisso quando la ruota viene ruotata. Pertanto, la probabilità di scegliere un individuo dipende direttamente dalla sua forma fisica.
Per quanto riguarda l'implementazione, utilizziamo i seguenti passaggi:
Calcola S = la somma di una finezza.
Genera un numero casuale compreso tra 0 e S.
Partendo dalla parte superiore della popolazione, continuare ad aggiungere le finezze alla somma parziale P, fino a P <S.
L'individuo per il quale P supera S è l'individuo scelto.
Campionamento stocastico universale (SUS)
Stochastic Universal Sampling è abbastanza simile alla selezione della ruota della roulette, tuttavia invece di avere un solo punto fisso, abbiamo più punti fissi come mostrato nell'immagine seguente. Pertanto, tutti i genitori vengono scelti in un solo giro della ruota. Inoltre, una tale configurazione incoraggia le persone altamente in forma a essere scelte almeno una volta.
È da notare che i metodi di selezione proporzionati all'idoneità non funzionano nei casi in cui l'idoneità può assumere un valore negativo.
Selezione del torneo
Nella selezione dei tornei K-Way, selezioniamo K individui dalla popolazione a caso e selezioniamo i migliori tra questi per diventare genitori. Lo stesso processo viene ripetuto per la selezione del genitore successivo. La selezione del torneo è anche estremamente popolare nella letteratura in quanto può funzionare anche con valori di fitness negativi.
Selezione del rango
La selezione del grado funziona anche con valori di fitness negativi e viene utilizzata principalmente quando gli individui nella popolazione hanno valori di fitness molto vicini (questo accade di solito alla fine della corsa). Ciò porta ogni individuo ad avere una quota quasi uguale della torta (come nel caso della selezione proporzionata all'idoneità) come mostrato nell'immagine seguente e quindi ogni individuo, indipendentemente da quanto in forma l'uno rispetto all'altro, ha approssimativamente la stessa probabilità di essere selezionato come genitore. Ciò a sua volta porta a una perdita nella pressione di selezione verso individui più in forma, costringendo l'AG a fare scelte povere dei genitori in tali situazioni.
In questo, rimuoviamo il concetto di valore di fitness durante la selezione di un genitore. Tuttavia, ogni individuo nella popolazione è classificato in base alla propria forma fisica. La selezione dei genitori dipende dal grado di ogni individuo e non dalla forma fisica. Gli individui di grado superiore sono preferiti di più rispetto a quelli di grado inferiore.
| Cromosoma | Valore fitness | Rango |
|---|---|---|
| UN | 8.1 | 1 |
| B | 8.0 | 4 |
| C | 8.05 | 2 |
| D | 7.95 | 6 |
| E | 8.02 | 3 |
| F | 7.99 | 5 |
Selezione casuale
In questa strategia selezioniamo casualmente i genitori dalla popolazione esistente. Non vi è alcuna pressione di selezione verso individui più in forma e quindi questa strategia viene solitamente evitata.