Post on 03-Feb-2020
1
1Vittorio Maniezzo – Università di Bologna
Algoritmi Genetici10
Algoritmi genetici
Un algoritmo genetico è una algoritmo euristico di ricerca che si ispira ai meccanismi della genetica delle popolazioni e della selezione naturale.
Gli algoritmi genetici hanno due componenti principali: la sopravvivenza del meglio adattato e l’ereditarietà dei genotipi (Darwin 1859, Mendel, 1866).
Proposti originariamente da John Holland nel 1975, ripresi con successo da Dave Goldbergnel 1989.
Vittorio Maniezzo – Università di Bologna 2
2
Applicazioni
Applicazioni degli algoritmi genetici:• Ottimizzazione e in generale problemi di Search• Scheduling e Timetabling• Ingegneria Aerospaziale• Astronomia e astrofisica • Chimica• Ingegneria elettrica e elettronica• Analisi dei mercati finanziari• Game playing• Ingegneria dei materiali• Militari e polizia• Biologia molecolare• Pattern recognition e data mining• Robotica• ...
Vittorio Maniezzo – Università di Bologna 3
Biologia, cenni
I processi biologici di riferimento avvengono a livello cellulare.
Il corpo umano è composto da migliaia di miliardi di cellule (37.2 * 10^12‡).
Ogni cellula, eucariota, ha un nucleo che contiene i cromosomi, la specie umana ne ha 23 coppie.
Ogni cromosoma è costituito da lunghe molecole di acido desossiribonucleico (DNA), suddividibili in segmenti detti geni.
Vittorio Maniezzo – Università di Bologna 4
‡ http://www.smithsonianmag.com/smart-news/there-are-372-trillion-cells-in-your-body-4941473/?no-ist
3
Genotipo / fenotipo
Ogni gene è un segmento di DNA che determina specifiche caratteristiche fisiche, es. il colore degli occhi o dei capelli.
La specie umana ha più di 20 000 geni, e ogni gene determina una caratteristica dell’organismo.
• Una collezione di geni è detta genotipo.
• Una collezione di caratteristiche fisiche è detta fenotipo.
Vittorio Maniezzo – Università di Bologna 5
Mutazioni genetiche
Una mutazione genetica è una alterazione del DNA.
Può essere ereditata o acquisita durante la vita, perché le cellule invecchiano, perché sono esposte a sostanze critiche o semplicemente a causa di errori nel processo di replicazione del DNA.
Alcuni di questi cambiamenti danno origine a patologie genetiche.
Vittorio Maniezzo – Università di Bologna 6
4
Riproduzione
La riproduzione comporta la ricombinazione di geni dei genitori, con la possibilità di avere errori nella copiatura dei geni dai genitori ai figli (mutazioni).
Il grado di adattamento di un organismo può essere misurato da quanto si riproduce prima di morire.
Vittorio Maniezzo – Università di Bologna 7
Selezione naturale
Elemento fondamentale della teoria dell’evoluzione di Darwin:
"solo gli organismi meglio adattati al loro ambiente riescono a sopravvivere e riprodursi, quindi a trasmettere le loro caratteristiche genetiche alle generazioni successive".
Gli organismi meno adattati tendono a scomparire, assieme al loro patrimonio genetico.
Vittorio Maniezzo – Università di Bologna 8
5
Algoritmi ad ispirazione naturale
Gli organismi biologici sono in grado di gestire i vincoli e le opportunità offerti dal loro ambiente.
Identificano soluzioni spesso diverse da quelle ottenibili con approcci ingegneristici tradizionali.
Si scambiano, direttamente o indirettamente, informazioni sulle soluzioni scoperte.
Gli algoritmi ad ispirazione naturale cercano di risolvere problemi complessi con metodi computazionali progettati in accordo a processi osservati in natura.
Vittorio Maniezzo – Università di Bologna 9
Trade off
Applicazioni di successo di metodi computazionali tradizionali:• elaborazioni numeriche• supporto alle decisioni• ripetizione di azioni bene identificate
Applicazioni critiche per approcci tradizionali:• pattern recognition• gestione di informazioni vaghe e incomplete• miglioramento con l’esperienza• robustezza ai guasti
Vittorio Maniezzo – Università di Bologna 10
6
Codifica delle soluzioni
Un GA può essere efficace solo quanto lo è la codifica che utilizza.
Come si codifica una soluzione?
Dipende dal problema da risolvere.
I GA lavorano al meglio con stringhe di bit di lunghezza fissa (e.s. 101110, 111111, 000101), considerate come cromosomi
Ogni bit o gruppo di bit rappresenta una caratteristica della soluzione da individuare (è un gene).
Per poter utilizzare un GA è necessario poter valutare ogni soluzione e ottenere una stima della qualità della soluzione: la sua fitness
Vittorio Maniezzo – Università di Bologna 11
Es. 1101 0111 0101
Param. 13 7 5
Fitness
Un modulo di valutazione decodifica ogni cromosoma e gli assegna una misura di fitness.
La fitness misura “quanto buona” è la soluzione, è correlata:• direttamente con la funzione obiettivo in problemi di
massimo;• inversamente in problemi di minimo.
La valutazione è l'unico legame fra il GA e il problema da risolvere.
Vittorio Maniezzo – Università di Bologna 12
7
Codifiche
Le soluzioni sono chiamate “cromosomi”.
I cromosomi possono essere:
• stringhe di bit (0101 ... 1100)
• numeri reali (43.2 -33.1 ... 0.0 89.2)
• Permutazioni di elementi (E11 E3 E7 ... E1 E15)
• Liste di regole (R1 R2 R3 ... R22 R23)
• Istruzioni di programmi (genetic programming)
• ... qualunque struttura dati ...
Vittorio Maniezzo – Università di Bologna 13
Spazio di ricerca
L’insieme di tutte le soluzioni possibili è lo spazio di ricerca (o spazio degli stati). Spesso i GA utilizzano codifiche binarie di numeri, ottenendo stringhe di bit che rappresentano soluzioni.
E’ possibile codificare molti numeri in una stringa, ottenendo funzioni multidimensionali f(x,y,…) .
Vittorio Maniezzo – Università di Bologna 14
Lo spazio di ricerca può essere visualizzato come una superficie in cui la fitness specifica l’altezza, detto fitness landscape.
Ogni possibile genotipo è un punto del dominio di questo spazio.
Il GA cerca di muoversi in punti migliori (di fitness più alta) nello spazio di ricerca.
8
Fitness landscape
Vittorio Maniezzo – Università di Bologna 15
Rosenbrock
Griewank
Kursawe
Riproduzione
I genitori sono selezionati casualmente, con probabilità di selezione influenzata dalla valutazione dei cromosomi.
• solo i selezionati si riprodurranno.
• selezione con ripetizione.
• ogni coppia di genitori genererà due figli.
Vittorio Maniezzo – Università di Bologna 16
9
Selezione dei genitoriSono possibili molti diversi schemi, unica condizione è che gli individui migliori abbiano una maggiore probabilità di riprodursiGli individui "migliori" sono i meglio "adattati" (fit) per cui hanno una maggiore fitness.La selezione più usata è la “Roulette Wheel” selection:
Selezione Montecarlo con ripetizione:1. S = somma della fitness di tutti gli
elementi2. Genera un numero casuale R fra 0 e S3. Scegli il primo individuo che ha fitness
cumulata (somma delle fitness di tutti i cromosomi fino a lui) maggiore o uguale a R
Vittorio Maniezzo – Università di Bologna 17
Modifica dei cromosomi
Le modifiche sono effettuate casualmente
Gli operatori di modifica sono:
• Mutazione
• Crossover (ricombinazione)
Vittorio Maniezzo – Università di Bologna 18
10
CrossoverUn punto di crossover è un punto selezionato a caso fra i geni di due cromosomi omologhi (lo stesso per entrambi).
I figli contengono lo stesso materiale genetico dei genitori, ma scambiato dopo il punto di taglio.
Il crossover si applica non sempre, ma con alta probabilità (pc=0.6 o maggiore)
L'idea è che il crossover preserva i "bit buoni" dei genitori, ricombinandoli per produrre discendenti ancora migliori
Un buono schema di codifica dovrebbe quindi cercare di preservare i "bit buoni" attraverso i crossover.
Vittorio Maniezzo – Università di Bologna 19
Prima: 1) 0 1 1 0 1 1 1 02) 1 1 0 1 1 0 0 1
Dopo: 1) 0 1 1 1 1 0 0 12) 1 1 0 0 1 1 1 0
Single-point corossover
P1 (0 1 1 0 1 0 0 0) (0 1 0 1 1 0 0 0) C1
P2 (1 1 0 1 1 0 1 0) (1 1 1 0 1 0 1 0) C2
Si scelgono a caso due punti di taglio, potrebbero cadere anche prima dell'inizio o dopo la fine.
Si scambia la codifica dei genitori compresa fra i punti di taglio.
In questo modo può capitare che i primi e gli ultimi bit della codifica siano mantenuti assieme anche nei figli. Impossibile con il single point crossover.
Crossover: two points
Vittorio Maniezzo – Università di Bologna 20
11
Mutazione
Applicata in probabilità, tipicamente molto bassa (pm, mutation rate), ad ogni elemento di codifica,
Di solito implementata cambiando il bit da 0 a 1 o viceversa.
Tipiche probabilità di mutazione da 0.1 a 0.001, o spesso 1/n, se n sono il numero di bit del cromosoma.
• Permette spostamenti liberi nello spazio di ricerca
• Permette di recuperare le informazioni altrimenti perse nella popolazione.
Vittorio Maniezzo – Università di Bologna 21
Mutazione: modifica locale
Causa spostamenti nello spazio di ricerca.
Prima: (1 0 1 1 0 1 1 0)
Dopo: (0 1 1 0 0 1 1 0)
Prima: (1.38 -69.4 326.44 0.1)
Dopo: (1.38 -67.5 326.44 0.1)
Vittorio Maniezzo – Università di Bologna 22
12
Varianti
Ci sono molte variazioni dello schema base dei GA:• Molti diversi operatori di selezione (non roulette):
- Rank based- Tournament- Elitism- …
• Molti diversi operatori di ricombinazione- Multi-point crossover - 3 way crossover- …
• Molte diverse codifiche possibili, oltre alle stringhe di bit:- Valori interi- Insiemi ordinate di simboli- …
• Molti diversi tipi di mutazione …
Vittorio Maniezzo – Università di Bologna 23
Esempio, GA base
Pseudocodice:
Genera la popolazione iniziale
while not(termination condition)
valuta la fitness di ogni individuo
selezione
crossover
mutazione
end while
Vittorio Maniezzo – Università di Bologna 24
13
Algoritmi genetici, in generale
Gli algoritmi genetici (GA) [G89] non si basano su costruzione o ricerca locale, ma su un evoluzione parallela di un insieme R di soluzioni.
Questo è ottenuto ricombinando sottinsiemi di 2 elementi in R, i parent set, per ottenere nuove soluzioni.
Per essere efficaci su problemi di CO, vengono spesso ibridati con SA, TS o ricerche locali.
Vittorio Maniezzo – Università di Bologna 25
Algoritmi genetici, pseudocodice generale
1. Inizializza un insieme R di soluzioni.
2. Costruisci un insieme Rs estraendo elementi da R, utilizzando una strategia montecarlo con ripetizione.
3. Costrusci un insieme Rc di soluzioni ricombinando coppie di elementi scelti a caso in Rs.
4. Costruisci il nuovo insieme R di soluzioni modificando elementi scelti a caso in Rc.
5. Se not(end condition) go to step 2.
Vittorio Maniezzo – Università di Bologna 26
14
Componenti di un GA
Un problema da risolvere, e ...
Tecnica di codifica (geni, cromosomi)
Procedura di inizializzazione (creazione)
Funzione di merito (fitness)
Selezione dei genitori (selezione)
Operatori genetici (mutazione, ricombinazione)
Setting dei parametri (esperienza e pratica)
Vittorio Maniezzo – Università di Bologna 27
gergo GA
Procedure GA
{ inizializza la popolazione;
valuta la popolazione;
while not(end_condition)
{ seleziona i genitori per la riproduzione;
esegui ricombinazione e mutazione;
valuta la popolazione;
}
}
Vittorio Maniezzo – Università di Bologna 28
15
Esempio: MAXONE
Il problema MAXONE:
Vogliamo massimizzare il numero di 1 in una stringa di L cifre binarie
Problema banale ma molto utilizzato per determinare le proprietà teoriche del procedimento
Codifica: ovvia, binaria su 10 bit. Se L = 10, ad esempio un individuo può essere 1 = 0000000001 (10 bit)
Vittorio Maniezzo – Università di Bologna 29
Inizializzazione
Si inizia con una popolazione di stringhe casuali, ad es. con L = 10 and n = 6
Generazione random: si generano 60 numeri casuali, ad esempio ottenendo la popolazione:
Vittorio Maniezzo – Università di Bologna 30
Genera la popolazione inizialewhile not(termination condition)
valuta la fitness di ogni individuo
selezionecrossovermutazione
end while
16
Fitness
La funzione di fitness: f(x)
Vittorio Maniezzo – Università di Bologna 31
Genera la popolazione inizialewhile not(termination condition)
valuta la fitness di ogni individuo
selezionecrossovermutazione
end while
Selezione
Selezione con roulette wheel
Si ripete l'estrazione tante volte quanti sono gli individui della popolazione (6 nel nostro caso)
L'area è proporzionale al valore di fitness
Ogni individuo ha probabilità di essere
scelto pari a 𝑝 𝑖 =𝑓(𝑖)
𝑖 𝑓(𝑖)
Vittorio Maniezzo – Università di Bologna 32
Genera la popolazione inizialewhile not(termination condition)
valuta la fitness di ogni individuo
selezionecrossovermutazione
end while
17
Selezione
Esempio, popolazione dopo la selezione:
Vittorio Maniezzo – Università di Bologna 33
Genera la popolazione inizialewhile not(termination condition)
valuta la fitness di ogni individuo
selezionecrossovermutazione
end while
Crossover
Per ogni coppia, si decide in probabilità, es. con prob. 0.6, se applicare il crossover o no.
Ad es., risulta che il crossover debba essere applicato solo alle coppie (s1`, s2`) (s5`, s6`).
Per ogni coppia si genera casualmente un punto di taglio, ad es. 2 per la prima e 5 per la seconda.
Vittorio Maniezzo – Università di Bologna 34
Genera la popolazione inizialewhile not(termination condition)
valuta la fitness di ogni individuo
selezionecrossovermutazione
end while
18
Mutazione
L'ultimo passo è l'applicazione della mutazione
Per ogni bit della popolazione, si decide in probabilità (ad es. pm=0.1) se invertirlo o no.
Vittorio Maniezzo – Università di Bologna 35
Genera la popolazione inizialewhile not(termination condition)
valuta la fitness di ogni individuo
selezionecrossovermutazione
end while
Esempio
Distribuzione degli individui alla generazione 0
Distribuzione degli individui alla generazione n
Fitn
ess
Fitn
ess
Vittorio Maniezzo – Università di Bologna 36
19
TSP: Rappresentazione
Il TSP è un problema innaturale per i GA.
La rappresentazione è (può essere) una lista ordinata di città. Rappresentazione nota come order-based GA.
1) Amsterdam 2) Berlin 3) Bologna 4) London
5) Madrid 6) Paris 7) Prague 8) Vienna
CityList1 (3 5 7 2 1 6 4 8)
CityList2 (2 5 7 6 8 1 3 4)
Vittorio Maniezzo – Università di Bologna 37
TSP - Crossover
Il crossover può essere definito in molti modi (insoddisfacenti) per il TSP.
Esempio:
* *
Parent1 (3 5 7 2 1 6 4 8)
Parent2 (2 5 7 6 8 1 3 4)
Child (8 5 7 2 1 6 3 4)
Questo è chiamato Order1 crossover.
Vittorio Maniezzo – Università di Bologna 38
20
TSP - Mutazione
La mutazione può essere implementata come 2-swap:
* *
Prima: (5 8 7 2 1 6 3 4)
Dopo: (5 8 6 2 1 7 3 4)
Vittorio Maniezzo – Università di Bologna 39
TSP, Ulysses 16
Esempio applicazione GA a Ulysses 16.
Miglior route nella prima popolazione
Miglior route globale al termine di 100000 iterazioni.
Soluzione esportata su GMaps:
(https://www.google.com/maps/@36.8502952,-0.4617461,4z/data=!3m1!4b1!4m2!6m1!1szBBTQIjERGzs.kXbVkXF_HMnw?hl=en)
Vittorio Maniezzo – Università di Bologna 40