Algoritmi genetici e programmazione genetica Roberto Navigli Apprendimento Automatico: Algoritmi...

Algoritmi genetici e programmazione geneticaRoberto Navigli

Roberto Navigli

Apprendimento Automatico:Algoritmi Genetici e Programmazione Genetica


• 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


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)


• 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


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)


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)


Rappresentazione delle Ipotesi (2)

• Esempio 1: rappresentiamo l’ipotesi

(Outlook = Overcast Rain) (Wind = Strong)

con: Outlook Wind 011 10

• Esempio 2: rappresentiamo l’ipotesi

IF Wind = Strong THEN PlayTennis = yes

con: Outlook Wind PlayTennis 111 10 10

• Esempio 3: rappresentiamo un’architettura di rete neurale definita da un grafo codificato mediante una stringa binaria


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

Operatori per gli Algoritmi Genetici

• 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


Selezione delle ipotesi migliori (fittest hypotheses)

• La selezione degli (1-r)·p membri avviene sulla base della probabilità:

• Può causare crowding (alcuni individui tendono a prendere il sopravvento, riducendo drasticamente la diversità della popolazione)

p

jj

ii

hFitness

hFitnessh

1)(

)()Pr(


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

a1 a2 c a1 a2 c 10 01 1 11 10 0– Fitness(h) = correct(h)2

• 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


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

d1 e d2

• Esempio: a1 a2 c a1 a2 c a1 a2 c

h1: 10 01 1 11 10 0

h2: 01 11 0 10 01 0

ottenendo come offspring:

h3: 11 10 0

h4: 00 01 1 11 11 0 10 01 0

[ ] d1 = 1, d2 = 3[ ] d1 = 1, d2 = 3


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!


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


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


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


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


Using Genetic Programming To Evolve Soccer Teams (da Gamasutra.com)


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.


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


"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)


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


PG: un esempio

• Supponiamo che il nostro programma calcoli la funzione:

• Il suo albero sintattico è il seguente:

• Simboli terminali: x, y e costanti (es. 2)• Funzioni: sen, +, radice, quadrato

yxxsen 2)(


Crossover nella PG


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


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


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


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


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.


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


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


Esempio di programma appreso

(seCiboAvanti (sePericoloSinistra (right)(sePericoloDestra (avanti)(sePericoloAvanti (sinistra)(avanti))))

(sePericoloAvanti (sePericoloSinistra (destra)(sinistra))

(sePericoloSinistra (sePericoloDestra (avanti)(destra))

(eseguiPrimaUnaPoiLaltro (sinistra)(destra)))))


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 Apprendimento Automatico: Algoritmi...

Documents

Transcript of Algoritmi genetici e programmazione genetica Roberto Navigli Apprendimento Automatico: Algoritmi...