Apprendimento Automatico:
Algoritmi Genetici e Programmazione Genetica
Roberto Navigli
Algoritmi genetici e programmazione genetica
Roberto Navigli
Cap. 9 [Mitchell]
Cap. 4.3 [Russel & Norvig]
Algoritmi Genetici
• Algoritmi motivati dall’analogia con l’evoluzione
biologica
– Lamarck: le specie “trasmutano” nel tempo sulla base di come
usano le parti del loro corpo (es. giraffa allunga il collo per
mangiare foglie)
– Darwin e Wallace: variazioni consistenti ereditabili si osservano
negli individui di una popolazione; selezione naturale dei più sani
(esistono giraffe con collo più o meno alto: solo alcune
sopravvivono)
– Mendel e la genetica: esiste un meccanismo per ereditare tratti
genetici
• A partire da un insieme di ipotesi (popolazione),
generano successori delle ipotesi producendo
perturbazioni su di esse che si spera producano
risultati migliori
Algoritmi genetici e programmazione genetica
Roberto Navigli
Caratteristiche degli AG
• Gli AG possono effettuare ricerche nello spazio di
ipotesi i cui elementi interagiscono in modo complesso
(ovvero laddove è difficile valutare l’impatto di un
singolo elemento)
• Gli AG sono ottimizzatori, non sono veri “apprendisti”
• Gli AG sono facilmente parallelizzabili (si avvantaggiano
del basso costo dell’hardware)
Algoritmi genetici e programmazione genetica
Roberto Navigli
Algoritmi Genetici
• Una Funzione Fitness che assegna un valore di
“benessere” a ogni ipotesi h
• Una Soglia di Fitness che specifica un criterio di
terminazione
• p numero di ipotesi da includere nella popolazione
• r la frazione della popolazione che deve essere
rimpiazzata dall’operatore di incrocio (crossover)
• m il tasso di mutazione
Algoritmi genetici e programmazione genetica
Roberto Navigli
Algoritmo Tipo
GA(Fitness, Soglia-Fitness, p, r, m)
• Inizializza: P = insieme di p ipotesi
– generate a caso o specificate a mano
• Valuta: per ogni h in P, calcola Fitness(h)
• While maxh Fitness(h) < Soglia-Fitness
– Seleziona: seleziona (1-r)·p membri di P da aggiungere a una
nuova generazione PS
– Crossover: Seleziona r·p/2 coppie di ipotesi da P
• Per ogni coppia (h1, h2) produci due successori (offspring) applicando
l’operatore di crossover
– Muta: Inverti un bit a caso di m% individui di PS scelti a caso
– Aggiorna: P = PS
– Valuta: per ogni h in P, calcola Fitness(h)
• Return argmaxh  P Fitness(h)
Algoritmi genetici e programmazione genetica
Roberto Navigli
Rappresentazione delle Ipotesi (1)
• La rappresentazione di base in GA è la stringa binaria
(cromosoma)
– La mappatura dipende dal dominio e dal progetto
• La stringa di bit rappresenta una ipotesi
• Elementi dell’ipotesi (es. clausole di una regola,
caratteristiche, ecc.) sono rappresentati ciascuno da una
sottostringa che si trova in una posizione specifica (se la
stringa ha lunghezza fissa)
Algoritmi genetici e programmazione genetica
Roberto Navigli
Rappresentazione delle Ipotesi (2)
• Esempio 1: rappresentiamo l’ipotesi
(Outlook = Overcast  Rain)  (Wind = Strong)
con:
Outlook
011
Wind
10
• Esempio 2: rappresentiamo l’ipotesi
IF Wind = Strong THEN PlayTennis = yes
con:
Outlook
111
Wind
10
PlayTennis
10
• Esempio 3: rappresentiamo un’architettura di rete neurale definita da
un grafo codificato mediante una stringa binaria
Algoritmi genetici e programmazione genetica
Roberto Navigli
Operatori per gli Algoritmi Genetici
Stringhe iniziali
Maschera di
crossover
Successori
(offspring)
Single-point
crossover
11101001000
00001010101
11111000000
11101010101
00001001000
Two-point
crossover
11101001000
00001010101
00111110000
00101000101
11001011000
Uniform crossover
11101001000
00001010101
10011010011
10001000100
01101011001
Point mutation
11101001000
•
•
•
11101011000
Gli operatori di crossover creano dei discendenti di una coppia di ipotesi “mescolando” le
caratteristiche dei due genitori
L’operatore di mutazione crea un discendente da un’ipotesi invertendo un bit scelto a caso
Altri operatori specializzati possono essere definiti sulla base del problema specifico
Algoritmi genetici e programmazione genetica
Roberto Navigli
Selezione delle ipotesi migliori (fittest hypotheses)
• La selezione degli (1-r)·p membri avviene sulla base della
probabilità:
Pr( hi ) 
Fitness( hi )
p
 Fitness( h j )
j 1
• Può causare crowding (alcuni individui tendono a
prendere il sopravvento, riducendo drasticamente la
diversità della popolazione)
Algoritmi genetici e programmazione genetica
Roberto Navigli
Ricerca nello spazio delle ipotesi
• Gli AG effettuano ricerche randomizzate sullo spazio
delle ipotesi
– Differente rispetto agli altri metodi di apprendimento (es.
BackPropagation si muove molto più lentamente da un’ipotesi
all’altra)
• E’ meno probabile che gli AG cadano in un minimo locale
• Il crowding è una difficoltà reale: alcuni individui con buon
fitness si riproducono velocemente e copie simili a queste
prendono il sopravvento sulla popolazione, riducendone la
diversità
– Soluzione: creare perturbazioni o alterazioni della funzione di
selezione
• Tempi di apprendimento lunghi (necessario hw “ad hoc”)
• Prestazioni paragonabili a C4.5
Algoritmi genetici e programmazione genetica
Roberto Navigli
Risolvere il problema del crowding
• Tournament selection (selezione per torneo):
– Scegli h1 e h2 casualmente con probabilità uniforme
– Con probabilità p, seleziona l’ipotesi migliore delle due (la peggiore
con probabilità 1-p)
– Procede con altri gruppi di 2 (o, più in generale, di k elementi)
sottoposti a selezione per “torneo”
• Rank selection (selezione per grado):
– Ordina tutte le ipotesi per fitness
– La probabilità di selezione è proporzionale al rank
Algoritmi genetici e programmazione genetica
Roberto Navigli
GABIL (De Jong et al., 1993)
• Un sistema per apprendere insiemi di regole proposizionali
• Ogni ipotesi corrisponde a un insieme di regole
• La rappresentazione a stringhe di ciascuna regola viene
concatenata alle altre
– La lunghezza complessiva della stringa cresce con l’aumentare delle
regole
• IF a1 = T  a2 = F THEN c = T; IF a2 = T THEN c = F
a 1 a2 c
10 01 1
– Fitness(h) = correct(h)2
a 1 a2 c
11 10 0
• Correct(h) è il numero di esempi di addestramento correttamente classificati da h
– Point mutation standard e operatore crossover che preservi la ben
formatezza dell’ipotesi
Algoritmi genetici e programmazione genetica
Roberto Navigli
GABIL: operatore di crossover
• L’operatore di crossover è un’estensione del two-point crossover
• Date due ipotesi h1 e h2 si seleziona per h1 un intervallo di bit (m1, m2)
• Si calcola la distanza d1 (d2) di m1 (m2) dal confine della regola
immediatamente alla sua sinistra
• Per h2 si sceglie un intervallo di bit tale che preservi le stesse distanze
d 1 e d2
• Esempio:
a1 a2 c
a 1 a2
[ 01 1
] 10
h1:
10
11
h2:
01
10 01
[ 11
] 0
ottenendo come offspring:
h3:
11 10 0
h4:
00 01 1
11 11
c
a 1 a2 c
0d1 = 1, d2 = 3
0 d1 = 1, d2 = 3
0
10 01 0
Algoritmi genetici e programmazione genetica
Roberto Navigli
GABIL: estensioni
• Aggiungiamo due operatori specializzati da applicare con
una certa probabilità:
– AggiungiAlternativa (AA)
• Generalizza il vincolo su un attributo cambiando uno 0 in 1 nella
sottostringa corrispondente all’attributo
– EliminaCondizione (EC)
• Generalizzazione ancora più drastica: rimpiazza tutti i bit di un
attributo con 1
• Possiamo anche aggiungere due bit alla fine di ogni
ipotesi, AA e EC, per indicare se su quell’individuo si
potranno applicare i due operatori oppure no
– Questi bit possono essere modificati da una
generazione all’altra come tutti gli altri mediante
crossover e mutazione
– Anche la strategia di apprendimento evolve!
-> Meta-Programmazione Genetica!
Algoritmi genetici e programmazione genetica
Roberto Navigli
Esempio: problema del commesso viaggiatore
• Il commesso viaggiatore deve visitare ogni città nella
sua zona esattamente una volta e quindi ritornare al
punto di partenza. Dato il costo di viaggio tra le città,
quale itinerario dovrebbe seguire per minimizzare il
costo del tour?
• TSP  NP-Complete
Algoritmi genetici e programmazione genetica
Roberto Navigli
TSP: Rappresentazione, inizializzazione, valutazione
• Un vettore v = (i1 i2… in) rappresenta un tour (v è una
permutazione di {1,2,…,n})
• Inizializzazione: campione casuale di permutazioni di
{1,2,…,n}
• Il fitness f di una soluzione è l’inverso del costo del tour
corrispondente
Algoritmi genetici e programmazione genetica
Roberto Navigli
Using Genetic Programming To Evolve Soccer Teams
(da Gamasutra.com)
Algoritmi genetici e programmazione genetica
Roberto Navigli
Applicazioni
• Nei campi più svariati:
–
–
–
–
–
–
–
–
–
–
–
Chimica: trovare molecole simile ad altre già note
Astronomia: calcolare la curva di rotazione di una galassia
Biologia molecolare: identificare sequenze di aminoacidi
Ingegneria aerospaziale: quale forma per l’ala di un aereo
supersonico?
Finanza: predire le prestazioni di prodotti finanziari nel tempo
Videogiochi: apprendere un giocatore
Matematica: trovare la soluzione di un’equazione
Algoritmi: trovare algoritmi efficienti che risolvono un dato
problema (-> programmazione genetica)
Crittografia: trovare la soluzione di un problema crittografico
Robotica: es. RoboCup, apprendere un robot che vinca in una
competizione
Pattern recognition/Data mining: sistemi che apprendono
grammatiche, conoscenza lessicale e semantica, ecc.
Algoritmi genetici e programmazione genetica
Roberto Navigli
Altre tecniche di ottimizzazione
• Hill climbing
– Simile a GA, ma più sistematico e meno casuale: inizia con una
soluzione casuale, quindi muta la stringa e mantiene quella
delle due che ha il fitness più altro. L’algoritmo termina quando
non si trova alcuna mutazione che può migliorare il fitness della
soluzione attuale.
• Simulated annealing
– L’idea proviene dal processo industriale di fusione in cui il
materiale viene riscaldato fino a un punto critico per
ammorbidirlo, quindi gradualmente raffreddato per eliminare
difetti nella sua struttura cristallina, producendo
un’organizzazione degli atomi più stabile e regolare
Algoritmi genetici e programmazione genetica
Roberto Navigli
"It occurred to me that perhaps you could combine
genetic algorithms with the basic thrust of AI, which
was to get computers to do things automatically that perhaps you could evolve a population of
programs."
- John Koza (1998)
Algoritmi genetici e programmazione genetica
Roberto Navigli
Programmazione Genetica
• Metodologia di programmazione evolutiva in cui gli
individui nella popolazione in evoluzione sono programmi
informatici
• La PG utilizza la stessa struttura algoritmica degli AG
• I programmi manipolati dalla PG sono rappresentati da
alberi che corrispondono agli alberi sintattici (parse tree)
dei programmi
Algoritmi genetici e programmazione genetica
Roberto Navigli
PG: un esempio
• Supponiamo che il nostro programma calcoli la funzione:
sen( x )  x 2  y
• Il suo albero sintattico è il seguente:
• Simboli terminali: x, y e costanti (es. 2)
• Funzioni: sen, +, radice, quadrato
Algoritmi genetici e programmazione genetica
Roberto Navigli
Crossover nella PG
Algoritmi genetici e programmazione genetica
Roberto Navigli
Passi preparatori per la PG
• Determinare l’insieme dei terminali ammessi
• Determinare l’insieme delle funzioni
• Determinare la misura di fitness:
– Il fitness di un singolo programma (individuo) è determinato
dall’accuratezza del programma eseguito su un insieme di
addestramento
• Determinare i parametri per il run
• Determinare il criterio per terminare un run
Algoritmi genetici e programmazione genetica
Roberto Navigli
Esempio: Il problema dei blocchi (Koza, 1992)
• Vogliamo sviluppare un algoritmo che prenda in input qualsiasi
configurazione iniziale di blocchi distribuiti a caso tra una pila e il
tavolo e li inserisca correttamente nella pila nell’ordine corretto (per
leggere: UNIVERSAL)
• Azioni permesse:
– Il blocco in cima alla pila può essere spostato sul tavolo
– Un blocco sul tavolo può essere spostato in cima alla pila
Algoritmi genetici e programmazione genetica
Roberto Navigli
Il problema dei blocchi (Koza, 1992)
• La scelta della rappresentazione può influenzare
la facilità di risolvere il problema
• Simboli terminali:
– CS (“current stack”) = denota il blocco in cima alla pila
o F se non c’è nulla
– TB (“top correct block”) = nome del blocco in cima alla
pila tale che tutti i blocchi sulla pila sono nell’ordine
corretto
– NN (“next necessary”) = nome del prossimo blocco
richiesto sopra TB sulla pila per poter leggere
“universal” o F se abbiamo finito
Algoritmi genetici e programmazione genetica
Roberto Navigli
Il problema dei blocchi (Koza, 1992)
• Funzioni:
– (MS x): (“move to stack”), se il blocco x è sul tavolo, sposta x in
cima alla pila e restituisce il valore T. Altrimenti non fa niente e
restituisce il valore F
– (MT x): (“move to table”), se il blocco x è da qualche parte nello
stack, sposta il blocco che è in cima allo stack sul tavolo e
restituisce il valore T. Altrimenti restituisce F.
– (EQ x y): (“equal”), restituisce T se x è uguale a y e restituisce F
altrimenti
– (NOT x): restituisce T se x = F, altrimenti restituisce F
– (DU x y): (“do until”) esegue l’espressione x ripetutamente finché
l’espressione y restituisce il valore T
Algoritmi genetici e programmazione genetica
Roberto Navigli
Il programma appreso
• Allenato su 166 configurazioni iniziali di blocchi
• Il fitness di qualsiasi programma è dato dal numero di
esempi risolti dallo stesso
• Usando una popolazione di 300 programmi, si trova il
seguente programma dopo 10 generazioni che risolvono i
166 problemi:
(EQ (DU (MT CS)(NOT CS)) (DU (MS NN)(NOT NN)) )
Per approfondire:
• Koza, John R. 1992. Genetic Programming: On the
Programming of Computers by Means of Natural
Selection. Cambridge, Massachusetts: The MIT Press.
Algoritmi genetici e programmazione genetica
Roberto Navigli
Learning Monna Lisa (!)
0) Inizializza una stringa di DNA casuale per la
renderizzazione di poligoni (50 poligoni massimo)
1) Copia la sequenza attuale e mutala leggermente
2) Usa il nuovo DNA per renderizzare i poligoni su tela
3) Confronta la tela con l’immagine sorgente
4) Se la nuova immagine sembra più somigliante
all’immagine sorgente rispetto alla precedente,
sovrascrivi il nuovo DNA con il precedente
5) Ripeti dal passo 1
Algoritmi genetici e programmazione genetica
Roberto Navigli
Algoritmi genetici e programmazione genetica
Roberto Navigli
Algoritmi genetici e programmazione genetica
Roberto Navigli
Algoritmi genetici e programmazione genetica
Roberto Navigli
Algoritmi genetici e programmazione genetica
Roberto Navigli
Algoritmi genetici e programmazione genetica
Roberto Navigli
Apprendere un programma per giocare a Snake
• Obiettivo: Trova un programma che mangi il maggior
numero possibile di pezzi di cibo
• Terminali: (avanti), (sinistra), (destra)
• Funzioni: seCiboAvanti, sePericoloAvanti,
sePericoloSinistra, sePericoloDestra, eseguiEntrambe
• Fitness: numero di pezzi di cibo mangiati
Algoritmi genetici e programmazione genetica
Roberto Navigli
Esempio di programma appreso
(seCiboAvanti (sePericoloSinistra (right)(sePericoloDestra
(avanti)(sePericoloAvanti (sinistra)(avanti))))
(sePericoloAvanti (sePericoloSinistra (destra)(sinistra))
(sePericoloSinistra (sePericoloDestra (avanti)(destra))
(eseguiPrimaUnaPoiLaltro (sinistra)(destra)))))
Algoritmi genetici e programmazione genetica
Roberto Navigli
Programmazione Genetica per i Videogiochi
• Snake: http://www.gamedev.net/reference/articles/article1175.asp
• Mancala: http://www.corngolem.com/john/gp/project.html
• Vari giochi: Sipper et al.Attaining Human-Competitive Game
Playing with Genetic Programming, IEEE Transactions on Systems,
Man and Cybernetics -- Part C, 2005
Algoritmi genetici e programmazione genetica
Roberto Navigli