Passaggi degli algoritmi genetici - Messa a punto e validazione di metodi analitici aspecifici

Gli algoritmi genetici seguono tre passi fondamentali: 1. creazione di una popolazione originaria; 2. riproduzione;

3. mutazione.

9.3.1 Creazione di una popolazione originaria

Il primo passaggio consiste nella decisione del numero n di individui di una popolazione. Ogni individuo possiede un cromosoma che viene determinato in maniera casuale. In questo modo ogni bit di ogni cromosoma assume un valore casuale che può essere 0 o 1. Se il cromosoma formato corrisponde ad una condizione sperimentale possibile, viene calcolato il suo fitness [Leardi, 2009].

Marco Caredda. Messa a punto e validazione di metodi analitici aspecifici online impieganti strumentazione a Trasformata di Fourier per la determinazione di macro e microanaliti in latte ovino. Tesi di dottorato in Scienze chimiche, Ciclo XXVI, Università degli studi di Sassari.

9.3.2 Riproduzione

Nella fase di riproduzione si ha la ricombinazione dei cromosomi della popolazione creata nel primo passaggio. In natura, la probabilità che i migliori individui si riproducano è maggiore di quella degli individui peggiori. I genotipi migliori saranno ricombinati per generare nuovi genotipi mentre i genotipi peggiori andranno pian piano ad estinguersi. Gli algoritmi genetici utilizzano lo stesso principio riuscendo ad attribuire una valore di probabilità di riproduzione ad ogni cromosoma in funzione della loro risposta. La funzione utilizzata calcola la probabilità di riproduzione di ogni cromosoma (pi) come il rapporto tra

la risposta di quel cromosoma e la somma delle risposte della popolazione:

Il valore di probabilità di ogni cromosoma è compreso tra zero ed uno.

La fase iniziale della riproduzione consiste nella copia dei cromosomi della popolazione iniziale N, a seconda della loro probabilità. Ordinando i cromosomi rispetto alla probabilità decrescente otterremo che i valori di pi (con i=1,2…n) saranno ordinati in modo tale che p1

corrisponda alla probabilità maggiore, p2 alla seconda probabilità maggiore e così via. A

questo punto vengono scelti n numeri casuali compresi tra 0,000 ed 1,000, che sceglieranno quali cromosomi verranno copiati a seconda dell’intervallo di probabilità in cui cadranno all’interno del range tra zero ed uno (Figura 9.1).

Figura 9.1 – Schema della selezione dei cromosomi più probabili.

Essendo l’intervallo di una probabilità maggiore più ampio dell’intervallo di una probabilità minore, è più probabile che i numeri random scelti rientrino nell’intervallo con probabilità maggiore. In Figura 9.1 si vede come i numeri casuali scelti (le frecce blu), siano presenti maggiormente negli intervalli di probabilità più ampi. Quando un numero cade all’interno di un intervallo, il cromosoma associato verrà copiato nella generazione successiva, dove è quindi più probabile trovare i cromosomi con un valore di p alto rispetto

ai cromosomi con un valore di p basso. I migliori individui verranno copiati più di una volta mentre i peggiori scompariranno. In questo modo la risposta media della generazione N+1 sarà statisticamente migliore della risposta media della generazione N.

A questo punto viene simulata la riproduzione. Gli n individui vengono fatti accoppiare formando n/2 coppie. Da ogni coppia vengono prodotti due nuovi individui (la prole) i cui cromosomi sono ottenuti tramite le tecniche di “crossover” a partire dai cromosomi genitori. Le tecniche di “crossover” più frequentemente applicate sono il “crossover singolo” ed il “crossover uniforme”. Nel “crossover singolo” viene selezionato in maniera casuale un punto di rottura dei cromosomi genitori, dividendoli in due parti: la parte a sinistra del punto di rottura contenente un numero x di geni, e la parte a destra del punto di rottura, contenente un numero y di geni, tali che x+y=g con g numero totale di geni del cromosoma. Il primo cromosoma figlio sarà dato dall’unione dei geni x del primo genitore con i geni y del secondo genitore. Il secondo cromosoma figlio sarà dato dall’unione dei geni x del secondo genitore con i geni y del primo genitore (Figura 9.2).

Figura 9.2 – Crossover singolo

Il limite di questo metodo è che l’ordine delle variabili all’interno del cromosoma risulta essere molto importante; la probabilità che due geni contigui nel cromosoma siano trasmessi ognuno ad un figlio diverso sarà bassa ed è data da 1/(g–1). Al contrario, il primo e l’ultimo gene saranno sempre trasmessi a figli diversi.

Nel “crossover uniforme”, ad ogni gene viene assegnato un numero casuale compreso tra zero ed uno. Il numero può rientrare o nell’intervallo tra 0,000 e 0,500 o nell’intervallo tra 0,500 ed 1,000. Nel primo caso, il gene del genitore A viene trasferito al primo figlio ed il

gene del genitore B viene trasferito al secondo figlio. Nel secondo caso avviene l’inverso, ovvero il gene del genitore B viene trasferito al primo figlio mentre il gene del genitore A viene trasferito al secondo figlio. In questo modo ogni gene di ogni genitore ha la stessa probabilità di essere trasferito ad un figlio o ad un altro [Leardi, 2009].

9.3.3 Mutazione

La mutazione sopperisce ad uno dei problemi derivanti dalle tecniche di crossover. Se i cromosomi genitori possiedono un gene identico, i cromosomi figli otterranno entrambi quello stesso gene e gli altri valori (alleli) di quel gene non saranno mai trasmessi alle generazioni successive, eliminando di fatto delle possibili condizioni sperimentali nei cromosomi figli.

Così, mentre il “crossover” agisce sui geni, lasciando i bit invariati, la mutazione fa variare i singoli bit di un gene, rendendo possibile la comparsa, nei cromosomi figli, di geni con una sequenza di bit non presente nei cromosomi genitori.

In natura, la mutazione avviene con una bassissima probabilità, mentre negli algoritmi genetici la probabilità di mutazione è dell'ordine dell'1-2%. Quindi, su una popolazione di n individui, se un cromosoma è formato da z bit (totale dei bit di tutti i geni) ed ha il 2% di probabilità che uno dei zi bit venga mutato, il numero di mutazioni medio per generazione

sarà dato da:

Alla conclusione dei tre passaggi base degli algoritmi genetici (creazione di una popolazione originaria, riproduzione e mutazione) si ottiene la seconda generazione, con un numero di individui identico a quello della prima generazione e con una risposta media superiore a quella della prima generazione. L’intero processo viene ripetuto più volte, con l’ottenimento di successive generazioni di risposta sempre migliore, fino a quando viene soddisfatto un criterio di arresto che può essere dato da un numero prefissato di generazioni, da un tempo di elaborazione predefinito o dall’ottenimento di un valore di risposta prefissato [Leardi, 2009].

Nel documento Messa a punto e validazione di metodi analitici aspecifici online impieganti strumentazione a Trasformata di Fourier per la determinazione di macro e microanaliti in latte ovino (pagine 165-169)