Scopriamo come funziona il codice di un algoritmo genetico: la selezione

da | Feb 15, 2021 | Tutorial | 0 commenti

Continua lo studio degli algoritmi genetici. In questo articolo scopriremo come selezionare gli individui della popolazione di oggetti appena creata. Occorrerà valutare quale dei membri ha un “fit” migliore per essere selezionato come genitori della prossima generazione. Il processo di selezione può essere diviso in due parti.

La valutazione della funzione fitness.

Perché il nostro algoritmo funzioni correttamente avremo bisogno di progettare una funzione fitness. La funzione produrrà un numero pr descrivere il fitness di un datomembro della popolazione. Questo ovviamente non è quanto accade nella realtà. Gli esseri viventi non hanno un indicatore di riproducibilità. semplicemente sopravvivono o meno. Ma nel caso di questo nostro algoritmo genetico classico, noi stiamo solo cercando di progettare una soluzione a un problema. Per far questo abbiamo bisogno di indicare numericamente il grado di successo di ogni possibnile soluzione.

Tornando al nostro esempio delle scimmie. Noi abbiamo tre membri della popolaione: “hut”, “car”, e “box”. Car ovviamente ha un fit superiore a tutti gli altri. Vi ricordiamo infatti che la notra frase target è “cat”. Hut ha solo 1 carattere corretto e box, nessuno.

Creazione del mating pool.

Una volta che il fitness è stato calcolato per tutti i membri della popolazione, abbiamo selezionato quale tra i membri ha un fit per essere un genitore, e li abbiamo inseirti in un mating pool. Ci sono molti approcci diversi che potremmo utilizzare. Per esempio potremmo utilizzare il metodo elitario, ossia: Quale dei deu membri della popolazione ha un fit piu alto? Ecco che questi due membri sarebbero scelti per creare tutti i figli della generazione successiva. 

Questo probabilmente è uno dei metodi più facili da programmare, tuttavia anche il meno variabile. Se due membri della popolazione infatti  sono i soli disponibili alla riproduzione, la nuova generazione avrà un tasso di variabilità molto basso rispetto alla precedente. Potremmo invece creare un mating pool con un numero più grande di genitori, ad esempio usare il 50% della popolazione. Anche questo secondo metodo è semplice da programmare, tuttavia come per il precedente, non produrrà buoni risultati. In questo caso infatti, il valore più alto avrà le stese possibilità di essere selezionato del valore medio dei 500 membri della popolazione selezionata. Ma anche perché dovremmo dare una chace al membro 50° enon al membro 501°?

Una soluzione migliore per il mating pool, è usare un metodo probabilistico, la roulette wheel. Per illustrare questo metodo, consideriamo un semplice esempio dove abbiamo una popolazione di 5 elementi, ognuno dei quali con un valore di fitness.

 

Il primo passa sarà normalizare tutti i valori, riconducendili ad un range che va da 0 a 1.

total fitness = 3+4+0.5+1.5+1=10

Ora occorre dividere ogni valore per il fitness totale come indicato nell’immagine sotto.

Ora capiremo perche parliamo di wheel of fortune (ruota della fortuna).

 

Ruotanto l’asticella, noterete che l’elemento B ha maggiori probabilità di essere selezionato. Seguono A, D, E ed infine C. Questo metodo probabilistico è molto performante. 1. grarantisce che l’ellemnto con valore più alto avrà maggiori probabilità di essere selezionato. 2. non elimina totalmente le altre variazioni dalla popolazione, come accadeva nell’elist method. E’ molto probabile che anche  l’elemento con score più basso abbia un valore utile al raggiungimento dell’obiettivo. Si veda il caso seguente.

Come si può vedere anche se C ha un valorre di fit più basso rispetto ad A e B, è l’unico membro con i geni necessari al raggiugeimento dell’obiettivo. Grazie al metodo probabilistico, anche C avrà una chance per partecipare alla riproduzione della specie, e così tramandare il gene necessario al completamento della frase To be or not to be.