La corsa dell’algoritmo genetico - Applicazione degli algoritmi genetici nella selezione di var

9.6 Applicazione degli algoritmi genetici nella selezione di variabili spettrali

9.6.1 La corsa dell’algoritmo genetico

Prima di descrivere i passaggi degli algoritmi, è necessario definire come viene effettuata la codifica delle variabili spettrali: ogni spettro è descritto da un cromosoma composto da un numero di geni pari al numero di lunghezze d’onda dello spettro. Ogni gene è formato da un solo bit codificato 1 o 0 a seconda che quella variabile sia presa in considerazione o meno [Leardi, 1992]. Per esempio, per un insieme di 10 variabili, l’utilizzo delle variabili 1, 5, 8 e 9 produrrà il codice binario 1000100110.

Il primo passaggio effettuato dagli algoritmi genetici è dato dalla creazione di una popolazione iniziale che consiste nel 1) decidere il numero n di individui che ne faranno

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.

parte; 2) creare un numero di cromosomi uguale al numero n di individui decisi per la popolazione; 3) valutare la risposta di tutti i cromosomi creati.

Negli algoritmi genetici semplici, i cromosomi iniziali vengono determinati in modo casuale, con un probabilità del 50% che una variabile sia selezionata o meno, e che quindi ogni gene del cromosoma sia codificato con 1 o con 0. Questo metodo ha però due svantaggi principali: 1) se il modello contiene numerose variabili, i tempi di computazione sono molto elevati; 2) è molto probabile che la selezione di circa metà delle lunghezza d’onda inglobi alcune variabili buone per la predizione; il risultato ottenuto sarà buono grazie alle poche variabili buone presenti, ma le risposte di diversi cromosomi saranno molto simili e sarà quindi molto difficile determinare quali variabili non sono buone per la predizione ed eliminarle dal modello finale.

Negli algoritmi genetici adattati alla selezione delle lunghezze d’onda di uno spettro, i cromosomi iniziali vengono determinati fissando un valore di probabilità di selezione p = xc/v con xc numero medio di variabili che si è deciso si vogliono considerare in un

cromosoma e v numero di variabili spettrali totali, ottenendo cromosomi contenenti un numero limitato di geni codificati 1 (variabili selezionate). Quindi, in ogni cromosoma costituito da v geni, esistono mediamente xc geni codificati 1 e v-xc geni codificati 0. Il

valore di default di xc nel software è 5.

In questo modo si otterranno cromosomi con piccoli blocchi di variabili molto diversi tra un cromosoma e l’altro, permettendo tempi di elaborazione molto ridotti e la possibilità di rilevare facilmente quali siano le variabili rilevanti per la predizione. Le variabili non buone saranno facilmente eliminate e le variabili informative, divise in piccoli blocchi, inizieranno a crescere di numero con il progredire dell’elaborazione.

Una volta creato un numero prefissato di cromosomi, ne viene calcolata la risposta (la percentuale di varianza spiegata) tramite regressione PLS in cross-validazione. La qualità di un sottoinsieme di variabili è valutata sia in base alla risposta che in base al numero di variabili considerate. È quindi importante sapere qual è il cromosoma con la risposta migliore, ottenuto da un dato numero di variabili. I cromosomi con queste caratteristiche sono altamente informativi, perciò vengono bloccati ed entrano a far parte della popolazione dalla quale non possono essere eliminati finché un altro cromosoma, che utilizza al massimo lo stesso numero di variabili, non produce una risposta migliore.

Una volta creata la popolazione, si passa alla fase di riproduzione e mutazione. La fase di riproduzione utilizza il metodo “crossover uniforme” descritto nel paragrafo 9.3.2, in modo da poter evitare qualsiasi influenza dovuta all’ordine delle variabili, basando la scelta dei

cromosomi genitori in base al metodo di probabilità descritto nello stesso paragrafo e visualizzato in Figura 9.1.

Figura 9.3 – Schema di una corsa dell’algoritmo genetico [Ferrand, 2011].

Una volta generati i cromosomi figli, l’algoritmo produce in loro una mutazione. Il valore di probabilità di default nel software è 0,01 per gene. Le risposte dei cromosomi figli vengono valutate e, se risultano essere migliori di quelli di altri cromosomi presenti nella popolazione, i loro cromosomi verranno conservati a discapito dei cromosomi della

popolazione con le risposte peggiori. È anche possibile che un cromosoma figlio produca una risposta migliore di un cromosoma bloccato, utilizzando al massimo lo stesso numero di variabili. In questo caso il cromosoma figlio viene bloccato e l’altro cromosoma viene invece sbloccato.

Esiste la probabilità che un gruppo di variabili considerate in un cromosoma sia un sottoinsieme di un gruppo di variabili considerate da un altro cromosoma. Se la risposta del primo è migliore della risposta del secondo, allora le variabili in più contenute nel secondo cromosoma non sono informative ma rappresentano semplicemente rumore, perciò questo cromosoma verrà eliminato.

Per poter incrementare le performance di un algoritmo genetico, esso viene alternato con cicli di selezione di variabili ottenuti col metodo della backward elimination (paragrafo 8.4.2), ottenendo così un cosiddetto algoritmo ibrido. Il metodo viene applicato al miglior cromosoma, con una frequenza di un ciclo ogni 100 valutazioni ed un ciclo alla fine del processo (se il numero di valutazioni non è un multiplo di 100) e, se la risposta ottenuta dal cromosoma generato è migliore della risposta precedente, il nuovo cromosoma rimpiazzerà l’originale.

La fase evolutiva procede fino a quando non viene soddisfatto un criterio di arresto che viene a decretare la fine di una corsa dell’algoritmo. In Figura 9.3 è mostrato lo schema di una corsa dell’algoritmo.

9.6.2 Implementazioni dell’algoritmo per ridurre il rischio di overfitting e

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 171-174)