A genetic algorithm for the
classification of natural
corks
Introduzione
Sughero naturale
-Il sughero è un prodotto naturale ben conosciuto nell’industria del
vino pregiato. Il maggior vantaggio del sughero naturale è di
permettere una buona diffusione gassosa che si adatta alla
maturazione del vino.
-Il processo di produzione dei tappi di sughero è
composto di differenti fasi.
Nella prima fase il sughero viene stoccato e
lasciato stagionare.
Nella seconda fase il sughero viene bollito nell’acqua e classificato.
Nell’ultima fase il sughero viene tagliato a strisce verticali, di
dimensioni proporzionali alla lunghezza del tipo di tappo che si dovrà
produrre.
2
Introduzione
Classificazione dei tappi di sughero:
In questo studio ci interesseremo alla fase di classificazione.
Per classificare il sughero vengono considerate dall’uomo esperto
diverse caratteristiche: i fori, le crepe, i colori,..
La qualità del sughero dipende dalla natura, la quantità, la misura,
e dalla posizione dei difetti.
In questo studio i tappi di sughero vengono classificati in base
all’aspetto delle due teste del tappo.
Questa operazione permette di separare i tappi di sughero in
3 categorie.
3
Introduzione
Per ottenere informazioni necessarie per la classificazione vengono
usate fotocamere CCD che ci danno delle figure per ogni testa del
tappo di sughero.
Da queste figure otteniamo dei valori numerici.
Un programma di classificazione è allora usato per determinare le
classi di ogni tappo.
La classificazione viene fatta confrontando valori numerici ottenuti
dalla fotocamera con parametri interni del programma di
classificazione.
L’obiettivo di questo studio è di analizzare come l’algoritmo
genetico riesce a determinare questi parametri che vengono utilizzati
dal programma di classificazione.
4
Introduzione
Affrontiamo nell’ordine i seguenti problemi:
-nella prima sezione introduciamo il problema della classificazione
-nella seconda sezione viene affrontato il punto di vista matematico
-nella terza sezione viene presentato GA
-nella quarta sezione vengono mostrati i risultati sperimentali
5
1° sezione
4 CCD fotocamere permettono di ottenere 2 figure per ognuna delle
due teste del tappo.
-Ogni figura è stata analizzata per estrarre 15 parametri che
registreremo CAMij
In questo studio non viene analizzato il metodo usato per estrarre
questi parametri, né la natura dei parametri selezionati.
-Un programma di classificazione analizza i 15 parametri dati da
ognuna delle 4 camere. Per semplificare diremo che il programma di
classificazione (AUTOCLASS) usa 30 parametri interni chiamati
(P1i, P2i), i [1;15].
CLASSIFICAZIONE DEI TAPPI DI SUGHERO
6
1° sezione
CLASSIFICAZIONE DEI TAPPI DI DI SUGHERO
7
-L’algoritmo usato dal programma di classificazione confronta i
valori numerici ottenuti dalle figure CAMij con i valori del
programma di classificazione (P1i, P2i).
-Una buona impostazione di questi parametri (P1i, P2i) i [1;15]
permetterà di classificare i tappi di sughero nella maniera più
giusta secondo le informazioni date dalla fotocamera.
ALGORITMO DI CLASSIFICAZIONE
8
2°sezione
Formule matematiche:
Vengono identificate un insieme di variabili V, un insieme di domini
per le variabili, un insieme di costrizioni per le variabili e una
funzione costo da essere ottimizzata.
•Variabili:
l’insieme di variabili è composto dai parametri P1i e P2i che sono
rinominati Vi
FORMULE MATEMATICHE
9
2°sezione
•Domini:
ogni variabile Vi deve avere un valore positivo e intero.
•Costrizioni:
questa costrizione è usata per evitare che un tappo di sughero che
non può essere accettato nella classe 2 venga accettato nella classe
1 (classe 1 è di più alta qualità).
Questa costrizione è dovuta all’algoritmo di classificazione detto
prima.
FORMULE MATEMATICHE
10
2°sezione
Infatti senza questa costrizione avremmo:
k [1,15]
Vk+15<CAMik<Vk
CONSEGUENTI
IMPLICAZIONI
ANTECEDENTI
Un tappo di sughero allora può essere messo nella classe 1 (CAMik<Vk)
mentre viene escluso dalla classe 2 (Vk+15<CAMik).
•Funzione costo è la somma dei tappi di sughero che sono
FUZZIFICAZIONE
classificati in modo corretto.
Questi tappi di sughero classificati
sono quelli per cui la classe
REGOLE
determinata dall’algoritmo IMPLICAZIONE
di classificazione è la stessa di quella
data dall’uomo.
DEFUZZIFICAZIONE
L’obiettivo è di massimizzare questa funzione.
PROVE PER LA
VALIDAZIONE
FORMULE MATEMATICHE
11
L’algoritmo genetico parte da un certo numero di possibili soluzioni
(individui) che evolvono durante un numero di interazioni
(generazioni).
Il meccanismo di evoluzione è basato su alcuni operatori genetici
come il crossover e mutazioni.
Il crossover prende 2 individui per produrre 2 nuove individui.
La mutazione consiste nella modificazione casuale di un gene di
un individuo.
Finita la fase di evoluzione ad ogni soluzione viene assegnato un
valore di fitness. I migliori individui sopravviveranno e potranno
produrre nuovi individui.
La fine dell’algoritmo può avvenire:
-dopo un numero predefinito di generazioni o valore di fitness
-dopo un numero di generazioni senza miglioramenti
DEFINIZIONE DI ALGORITMO GENETICO
12
3°sezione
Dobbiamo determinare i parametri per la classficazione con GA.
Ogni individuo è definito da un vettore: Vi=Pi1,..Pi10,..Pi30
Ogni gene corrisponde ad uno dei 30 parametri e prendo il suo valore
dal valore del suo dominio. Viene usata una popolazione di 40
individui.
CROSSOVER E MUTAZIONE:
Il crossover è generato per creare nuovi individui.
Supponiamo che noi decidiamo di mutare il Kth gene Vik di un
individuo.
La selezione viene effettuata sull’intera popolazione e metà dei migliori
individui sono conservati.
Il miglior individuo è sempre registrato in una variabile V* ed è
aggiornato ogni volta che una soluzione migliore è trovata.
L’algoritmo si ferma dopo un numero di generazioni senza
miglioramento (fissato a 50 generazioni).
NOSTRO ALGORITMO GENETICO
13
3°sezione
Per valutare il fitness di un individuo scorriamo il programma di
classificazione AUTOCLASS con valori parametrici di individui
presenti in un database conosciuto.
Questo database è costituito da un insieme di tappi di sughero
classificati.
Secondo il numero di tappi correttamente classificati viene assegnato
un punteggio ai singoli individui che sono stati valutati.
Di qui viene usato un programma esterno per la valutazione del
fitness ( la valutazione costituisce il tempo maggiore dell’algoritmo )
L’algoritmo usa una funzione di diversificazione.
Se i migliori individui della popolazione non evolvono durante 10
generazioni allora l’intera popolazione subisce una mutazione (ogni
individuo è mutato) per evitare il problema della prematura convergenza
della popolazione.
NOSTRO ALGORITMO GENETICO
14
MOTORE
INFERENZIALE
INTERFACCI
UTENTE
INTERFACCIA
SVILUPPATORE
AGGOIRNAMENTO
DELLA CONOSCENZA
3°sezione
NOSTRO ALGORITMO GENETICO
15
4°sezione
Risultati sperimentali su dati artificiali:
Consideriamo un insieme di dati artificiali e casuali dove è conosciuta
la soluzione ottimale che è, per ogni tappo, la sua classe.
CONSOLIDATO
Usando tale data set possiamo paragonare i risultati dell’GA con le
EVOLUTO
soluzioni ottimali.
Questi dati sono ottenuti creando una tabella di dimensioni
NxM
FLESSIBILE
dove N=5000 (numero di tappi teorici) e M=61 (60 valori
numerici
OTTIMIZZATO
simulati che di solito sono dati dalle 4 camere più la classe del tappo)
In dettaglio la prima linea è calcolata casualmente e le informazioni
successive sono calcolate da una funzione che prende il valore della
cella della prima linea e un valore casuale.
Per ognuna delle N linee ci sono 15 parametri dati dalle 4 camere per
ogni tappo.
Poi per assegnare a ogni tappo la classe procediamo nel seguente modo.
RISULTATI SPERIMENTALI SU DATI ARTIFICIALI
16
4°sezione
Viene presa casualmente una combinazione di 30 parametri da usare
con AutoClass.
Scorriamo AutoClass con questi parametri per classificare tutti i 5000
tappi.
Quindi conosciamo la classe di ogni tappo e anche i parametri necessari
per trovare questa classificazione ( questi parametri possono essere
considerati essere ottimali per la classificazione di questi tappi ).
Ora possiamo scorrere il nostro algoritmo genetico su questi dati per
vedere se è capace di trovare questi parametri ottimali per classificare
correttamente tutti i tappi.
Noi testiamo il programma su data sets con differenti misure (50, 100,
200, 500, 1000 e 5000 tappi).
Scorriamo 10 volte l’algoritmo su ogni data set. I tests erano realizzati
su un Pentium II con 200 MHz e 64 MB di RAM.
RISULTATI SPERIMENTALI SU DATI ARTIFICIALI
17
4°sezione
CONSEGUENTI
DEDUZIONI
BASE DEI FATTI
BASE DEI DATI
IMPLICAZIONI
ANTECEDENTI
Avremo i seguenti risultati:
RISULTATI SPERIMENTALI SU DATI ARTIFICIALI
18
4°sezione
Dalla tabella si osserva, per esempio che con 200 tappi di sughero
l’algoritmo dà una giusta classificazione per 162 tappi su 200 (81%).
L’ultima colonna indica il tempo medio per ogni corsa.
Si vede che il tempo di risoluzione incrementa secondo la misura del
data set. Questo è dovuto alla fase di valutazione che usa un programma
di classificazione esterna (AutoClass).
Conclusione:
Questo esperimento è molto soddisfacente da un punto di vista pratico.
Mostra che l’algoritmo è capace di trovare la migliore soluzione
ottimale.
Si può parlare di soluzione ottimale perché è conosciuta e sappiamo che
possiamo cercarla.
RISULTATI SPERIMENTALI SU DATI ARTIFICIALI
19
4°sezione
Risultati sperimentali su dati reali:
Da una selezione visuale realizzata da uomini esperti 173 tappi erano
classificati secondo le loro teste. Avremo i seguenti risultati:
APPRENDIMENTO
RAPPRESENTAZIONE
DELLA CONOSCENZA
Analizziamo
i tappi di ogni classe con
le 4 fotocamere
in modo da
MEMORIZZAZIONE
CAPACITÀ
DECISIONALI
estrarre i 60 parametri da ogni tappo.
I dati sono registrati in una tabella con 61 colonne.
La classe
VALUTAZIONE
RIUTILIZZAZIONE
determinata dall’occhio esperto è indicata nella
61st colonna
DELL’OTTIMO
RISULTATI SPERIMENTALI SU DATI REALI
20
4°sezione
Scorriamo il nostro algoritmo per determinare i 30 parametri di
classificazione Vi i [1,30] tale che la classificazione è la stessa che è
stata determinata dall’uomo esperto.
Scorriamo l’algoritmo 20 volte prima di selezionare la soluzione
migliore.
RISULTATI SPERIMENTALI SU DATI REALI
21
4°sezione
RISULTATI SPERIMENTALI SU DATI REALI
22
4°sezione
RISULTATI SPERIMENTALI SU DATI REALI
23
4°sezione
La prossima figura mostra la tipica evoluzione della funzione di fitness
degli individui migliori con il numero di generazioni.
Si vede che il fitness dei migliori individui aumenta rapidamente per
le prime 60 generazioni. Poi l’evoluzione rallenta e si ferma intorno
a 181 con un migliore fitness di 130.
RSULTATI SPERIMENTALI SU DATI REALI
24
4°sezione
Da questi risultati noi sappiamo che i parametri di classificazione
determinati dall’algoritmo genetico permettono di classificare 130 su
173 tappi di sughero come ha indicato l’uomo esperto.
Noi ora vogliamo sapere esattamente la classificazione per ogni tappo.
Per questo scopo prendiamo uno dei migliori individui con fmax=130.
Ora riscorriamo il programma di classificazione con i parametri di
classificazione dati dall’individuo scelto. Applicato ai nostri 173 tappi
di sughero otteniamo i seguenti risultati:
RISULTATI SPERIMENTALI SU DATI REALI
25
4°sezione
Dalla tabella si può vedere che su 70 tappi che sono classificati dagli
esperti nella classe 1, 61 di loro sono classificati dal sistema di
classificazione in classe 1, 8 in classe 2, e 1 in classe 3.
Circa il 75% dei tappi di sughero viene classificato nello stesso modo
sia dall’algoritmo che dall’uomo esperto.
RISULTATI SPERIMENTALI SU DATI REALI
26
4°sezione
Se noi paragoniamo questi risultati con quelli ottenuti su tappi teorici
possiamo concludere che i risultati su dati reali sono meno buoni.
Due fattori possono spiegare la differenza tra questi due esperimenti.
-il primo è dovuto alla classificazione fatta da umani esperti
-il secondo fattore è più preoccupante ed è relativo all’algoritmo di
classificazione usato (AutoClass). I dati stessi che noi usiamo non
possono permettere di classificare correttamente il set dei tappi.
LIMITI
27
Conclusione:
La classificazione dei tappi di sughero naturali è molto importante
nell’industria del vino.
Ci siamo soffermati sul problema dell’ottimizzazione dei parametri per
un sistema di classificazione automatico.
Il problema riguarda 30 variabili con un enorme numero (sopra i 10 000)
di possibili valori per questi parametri.
Per risolvere il problema abbiamo sviluppato un approccio basato
sull’algoritmo genetico per cercare una buona combinazione per i 30
parametri.
L’approccio proposto è stato valutato su entrambi i dati reali ed artificiali
e i risultati ottenuti sono stati più che soddisfacenti.
Le analisi dei risultati hanno dimostrato che sarebbe possibile migliorare
il sistema di classificazione modificando altre fasi del processo di
classificazione (incluso il programma di classificazione).
CONCLUSIONE
28