Algoritmi genetici per l'inversione di dati sismici a riflessione: attenuazione del genetic drift e analisi preliminari sull'aggiunta di vincoli laterali

DIPARTIMENTO DI SCIENZE DELLA TERRA

Corso di Laurea Magistrale in Geofisica di Esplorazione e Applicata

TESI DI LAUREA MAGISTRALE

Algoritmi genetici per l’inversione di dati sismici a riflessione:

attenuazione del genetic drift e

analisi preliminari sull’aggiunta di vincoli laterali

Laureando:

Silvio Pierini

Matricola 539270

Relatore:

Prof. Alfredo Mazzotti

Correlatore:

Dott. Mattia Aleardi

Controrelatore:

Prof. Stefano Roddaro

DIPARTIMENTO DI SCIENZE DELLA TERRA

Corso di Laurea Magistrale in Geofisica di Esplorazione e Applicata

Tesi di laurea magistrale

Algoritmi genetici per l’inversione di dati sismici a riflessione:

attenuazione del genetic drift e

analisi preliminari sull’aggiunta di vincoli laterali

Laureando:

Silvio Pierini

Matricola 539270

Relatore:

Prof. Alfredo Mazzotti

Correlatore:

Dott. Mattia Aleardi

Controrelatore:

Prof. Stefano Roddaro

Gli algoritmi genetici (GA) sono una classe di algoritmi di ricerca globale ecacemente applicati a problemi di interesse geosico. La strategia otti-mizzativa di un GA, a fronte di una popolazione iniziale (i.e. un insieme di individui, ovvero possibili soluzioni), prevede la generazione iterativa di nuovi individui sempre più promettenti, tramite ricombinazione lineare dei modelli migliori ottenuti all'iterazione precedente, in analogia con i principi biologici di evoluzione della specie. Un problema invalidante dei GA è il genetic drift. Tale fenomeno produce una ridotta variabilità genetica all'interno della po-polazione, determinando la convergenza precoce dell'algoritmo ad un minimo locale. In altri termini tale fenomeno impedisce all'algoritmo di esplorare ef-cacemente lo spazio dei modelli, rimanendo vincolato all'esplorazione di un limitato intorno di tale minimo locale. Si deduce quindi che la riduzione di tale fenomeno è cruciale per garantire una buona adabilità della soluzione. A tal ne in questa tesi viene proposto un algoritmo innovativo: il drift avoidance genetic algorithm (DAGA) che limita fortemente il fenomeno di drift. La soluzione prevede l'ibridazione del GA tramite due operatori che hanno lo scopo di incrementare le capacità esplorative dell'algoritmo in ma-niera adattiva, intervenendo prevalentemente allorquando si vericano condi-zioni tipiche di convergenza precoce. Nello specico il primo operatore mira a limitare la coesistenza di soluzioni topologicamente vicine nella stessa ite-razione, tramite la sostituzione di alcuni di questi individui con altri generati randomicamente con probabilità uniforme su tutto lo spazio dei modelli. La seconda operazione inuisce più drasticamente sul principio di generazione delle nuove soluzioni, simulando un evento catastroco che riduce sensibil-mente il numero degli individui della popolazione, ad una data iterazione. Gli individui eliminanti vengono rimpiazzati nelle iterazioni successive tramite generazione di nuove soluzioni e replicazione degli individui migliori. Data l'incisività di tale operazione è stato deciso di applicarla in modo casuale sulle iterazioni dell'algoritmo, in base ad una probabilità predenita.

st. Inizialmente è stato applicato a diverse funzioni analitiche, evidenziando risultati promettenti: nell'ottimizzazione di problemi multimodali caratteriz-zati da topologie dello spazio dei modelli semplici, l'algoritmo ha ottenuto risultati analoghi a quelli di un normale GA. In casi più complessi, in cui un GA fallisce nella determinazione del minimo globale, il DAGA giunge a convergenza, dimostrando una maggiore stabilità dell'algoritmo in presenza di fenomeni di drift.

Successivamente il DAGA è stato testato su due problemi di interesse geosico di dicile ottimizzazione: le correzioni statiche residuali e la full-waveform inversion. L'analisi dei test, eettuati su dati sintetici, ha eviden-ziato anche in questo caso una maggiore capacità esplorativa dell'algoritmo rispetto ai GA standard, garantendo così un livello di condenza delle solu-zioni trovate maggiore rispetto a quelle individuate dai GA, al prezzo di un aumento marginale del tempo computazionale.

Un ulteriore obiettivo della tesi è stato quello di ricercare strategie atte a limitare la porzione esplorata dello spazio dei modelli, escludendo a priori soluzioni sicamente non signicative, nell'ottica di ridurre sensibilmente i tempi di calcolo dell'inversione full-waveform risolta tramite metodi di ricerca globale. Sono stati esaminati dierenti approcci per direzionare l'esplorazio-ne dello spazio dei modelli in funziol'esplorazio-ne di diversi vincoli a priori. È stata approfondita l'analisi di una strategia che prevede l'inserimento di un vinco-lo sulla semplicità dei modelli, alterando i vavinco-lori della funzione oggetto con un termine di penalizzazione adattivo. I risultati delle inversioni condotte con questo schema evidenziano velocità di convergenza maggiori verso modelli accettabili.

Il lavoro è articolato nei seguenti argomenti: un'analisi dettagliata del fenomeno di genetic drift, una descrizione approfondita della soluzione pro-posta, l'esposizione e il commento dei test eettuati ed inne gli studi ri-guardo le possibili strategie ottimizzative atte a limitare la porzione di spazio eettivamente esplorato dall'algoritmo.

Indice

1 Introduzione 1 1.1 Stato dell'arte . . . 4 2 Genetic Drift 6 2.1 Esempio di drift . . . 7 3 DAGA 11 3.1 Competizione . . . 15 3.2 Catastro . . . 21 3.3 Ripopolamento . . . 25 4 Test 27 4.1 Test su Funzioni Analitiche . . . 28

4.1.1 Denizione e proprietà delle funzioni test . . . 28

4.1.2 Criteri di comparabilità dei risultati . . . 29

4.1.3 Analisi comparata . . . 30

4.1.4 Analisi delle Performances del DAGA su funzioni ana-litiche . . . 43

4.2 Correzioni statiche residuali . . . 54

4.2.1 Denizione del problema . . . 54

4.2.2 Criteri di comparabilità dei risultati . . . 55

4.2.3 Analisi dei risultati . . . 56

4.3 DAGA-FWI . . . 62

4.3.1 Denizione del problema . . . 62

4.3.2 Criteri di comparabilità dei risultati . . . 64 vi

5 Aggiunta di vincoli laterali 77 5.1 Metodi proposti . . . 77 5.1.1 Test . . . 81 6 Conclusioni 94 6.1 Sviluppi futuri . . . 95 A Appendici 98 A.1 Algoritmi Genetici . . . 98

A.1.1 Introduzione . . . 98

A.1.2 Struttura dell'Algoritmo . . . 99

A.1.3 Niched Genetic Algorithm . . . 105

A.2 Funzioni Test . . . 106

A.2.1 Ackley . . . 106 A.2.2 Eggholder . . . 107 A.2.3 Langermann . . . 108 A.2.4 Rastrigin . . . 110 A.2.5 Schwefel . . . 111 Bibliograa 112

Elenco delle gure

1.1 Diagramma schematico del usso di un algoritmo genetico . . 2

2.1 Localizzazione degli individui costituenti la popolazione inizia-le sulla topologia indotta dalla funzione oggetto sullo spazio dei modelli . . . 7

2.2 Analisi dell'inversione: a) Distanza fra l'elitist e il minimo globale e b) Distanza media fra i cromosomi . . . 8

2.3 Minimo individuato dall'inversione GA dopo 100 generazioni . 9 3.1 Diagramma di usso dell'algoritmo . . . 12

4.1 Confronto fra le curve cumulative dei diversi algoritmi . . . 31

4.2 Numero medio di modelli generati dai vari algoritmi . . . 32

4.3 Errore medio degli algoritmi . . . 33

4.4 Confronto fra le curve cumulative dei diversi algoritmi . . . 36

4.5 Numero medio di modelli generati dai vari algoritmi . . . 37

4.6 Errore medio degli algoritmi . . . 37

4.7 Confronto fra le curve cumulative dei diversi algoritmi . . . 40

4.8 Numero medio di modelli generati dai vari algoritmi . . . 41

4.9 Errore medio degli algoritmi . . . 42

4.10 Curve incrementali di convergenza per la funzione di Ackley . 45 4.11 Curve incrementali di convergenza per la funzione eggholder . 47 4.12 Curve incrementali di convergenza per la funzione di Langer-mann . . . 49 4.13 Curve incrementali di convergenza per la funzione di Rastrigin 51 4.14 Curve incrementali di convergenza per la funzione di Schwefel 53

time shift, c), d) risultati delle inversioni DAGA e NGA, e) Confronto fra le energie dei best model delle due inverisoni . . 58 4.16 Test a dimensione 40: a), b) CMP sintetico prima e dopo il

time shift, c), d) risultati delle inversioni DAGA e NGA, e) Confronto fra le energie dei best model delle due inverisoni . . 59 4.17 Test a dimensione 50: a), b) CMP sintetico prima e dopo il

time shift, c), d) risultati delle inversioni DAGA e NGA, e) Confronto fra le energie dei best model delle due inverisoni . . 60 4.18 Test a dimensione 80: a), b) CMP sintetico prima e dopo il

time shift, c), d) risultati delle inversioni DAGA e NGA, e) Confronto fra le energie dei best model delle due inverisoni . . 61 4.19 Modello di velocità Marmousi in cui è evidenziata la porzione

oggetto delle inversioni . . . 65 4.20 Spettri di frequenza: a) dell'ondina sorgente utilizzata per il

primo test, b) di quella usata per il secondo test. . . 66 4.21 Distribuzione delle sorgenti e dei ricevitori dell'acquisizione . . 67 4.22 Modello di velocità oggetto dell'inversione. Le croci nere

rap-presentano la griglia di inversione coarse. . . 67 4.23 common shot gather del dato sintetico osservato: a)

acquisi-zione della 1o _{sorgente con ondina a 7Hz, b)acquisizione della}

6o _{sorgente con ondina a 7Hz, c) acquisizione della 1}o

sorgen-te con ondina a 15Hz, d) acquisizione della 6o sorgente con

ondina a 15Hz. . . 68 4.24 Curve di errore in funzione delle iterazioni dell'algoritmo . . . 72 4.25 Modelli di velocità dei due test . . . 74 4.26 Confronto fra il dato osservato (in rosso) e quello generato a

partire dalla soluzione del DAGA (in nero): a) Common shot gather relativo alla 1o _{sorgente, generato con ondina a 7Hz,}

b) Common shot gather relativo alla 6o _{sorgente, generato}

con ondina a 7Hz, c) Common shot gather relativo alla 1o

sorgente, generato con ondina a 15Hz, d) Common shot gather relativo alla 6o sorgente, generato con ondina a 15Hz. . . 75

partire dalla soluzione del NGA (in nero): a) Common shot gather relativo alla 1o _{sorgente, generato con ondina a 7Hz,}

b) Common shot gather relativo alla 6o _{sorgente, generato}

con ondina a 7Hz, c) Common shot gather relativo alla 1o

sorgente, generato con ondina a 15Hz, d) Common shot gather relativo alla 6o _{sorgente, generato con ondina a 15Hz. . . 76}

5.1 Confronto fra la curva di peso e una sua formulazione più semplice . . . 79 5.2 Dall'alto: a) Modello di velocità reale, b) modello a priori, c)

modello risultante dall'inversione GA, modelli ottenuti tramite l'imposizione di vincoli d) sulla semplicità e) sui gradienti, f) sulla correlazione. In basso, il confronto fra le curve di errore ottenute dai dierenti algoritmi . . . 83 5.3 In alto: modello reale e in basso: modello a priori utilizzati

per le due inversioni . . . 86 5.4 Risultati della seconda inversione. In alto: a) modello reale,

b) modello a priori, c) best model dell'inversione NGA, d) best model dell'inversione vincolata . . . 88 5.5 Confronto fra il dato osservato (in rosso) e quello generato a

partire dalla soluzione del WGA (in nero): a) Common shot gather relativo alla 1o _{sorgente, generato con ondina a 7Hz,}

b) Common shot gather relativo alla 6o sorgente, generato con

ondina a 7Hz . . . 89 5.6 Risultati della seconda inversione. In alto: a) modello reale,

b) modello a priori, c) best model dell'inversione NGA, d) best model dell'inversione vincolata . . . 91 5.7 Curve di data mist per l'inversione NGa e quella in cui è

partire dalla soluzione del WGA (in nero): a) Common shot gather relativo alla 1o _{sorgente, generato con ondina a 7Hz,}

b) Common shot gather relativo alla 6o _{sorgente, generato con}

ondina a 7Hz . . . 93 A.1 Funzionamento schematico di un algoritmo genetico elementare 99 A.2 Funzione di Ackley . . . 106 A.3 Funzione di eggholder . . . 107 A.4 Funzione di Langermann . . . 108 A.5 Contributo esponenziale della funzione di Langermann . . . . 109 A.6 Funzione di Rastrigin . . . 110 A.7 Funzione di Schwefel . . . 111

Elenco delle tabelle

4.1 Parametri del test . . . 31

4.2 Risultati del test . . . 33

4.3 Parametri del test . . . 35

4.4 Risultati del test . . . 38

4.5 Parametri del test . . . 39

4.6 Risultati del test . . . 42

4.7 Parametri del test . . . 44

4.8 Risultati del test . . . 45

4.9 Parametri del test . . . 46

4.10 Risultati del test . . . 47

4.11 Parametri del test . . . 48

4.12 Risultati del test . . . 49

4.13 Parametri del test . . . 50

4.14 Risultati del test . . . 51

4.15 Parametri del test . . . 52

4.16 Risultati del test . . . 53

4.17 Parametri dei test . . . 56

4.18 Parametri del test . . . 71

5.1 Parametri comuni dei GA testati . . . 82

5.2 Risultati del test . . . 84

5.3 Parametri del test . . . 85

Capitolo 1

Introduzione

In ambito geosico i processi di inversione sono spesso non lineari e caratte-rizzati da funzioni oggetto multimodali. In tali casi il problema viene risolto ricorrendo o ad un metodo di ottimizzazione locale oppure ad un metodo globale.

I metodi di ottimizzazione locale (e.g. Gauss-Newton, gradient based, steepest-descent) sono spesso preferiti a causa della loro elevata velocità di convergenza. Per garantire il successo di questa classe di metodi è necessario fornire un modello di partenza sucientemente accurato. Tale condizione è spesso dicile da soddisfare, soprattutto in casi in cui le informazioni a priori sono di bassa qualità o perno assenti. Inoltre in ogni iterazione degli algoritmi è necessario calcolare le derivate della soluzione in analisi che, per problemi di grande dimensionalità, può essere computazionalmente costoso. In generale questi problemi non garantiscono soluzioni adabili per problemi fortemente multimodali, a meno di una scelta molto accurata del modello iniziale.

I metodi di inversione globale sono invece più adatti a problemi multimo-dali. La velocità di convergenza è generalmente inferiore, ma tali algoritmi esplorano ecacemente l'intero spazio dei modelli, a prescindere dalla sua topologia. Non risentono della scelta del modello iniziale, infatti, general-mente, l'inversione parte su di un set di soluzioni generate randomicamente sullo spazio dei modelli. La natura aleatoria di questi algoritmi non

de che il problema inverso sia lineare, ovvero che possa essere localmente linearizzato, al contrario dei metodi locali.

Gli algoritmi genetici [1] sono una classe di algoritmi euristici di ricerca globale molto ecace nel risolvere problemi di ottimizzazione geosica [2]. L'architettura di questi algoritmi trae spunto dalla teoria dell'evoluzionismo, applicando iterativamente su di una popolazione iniziale, costituita da pos-sibili soluzioni della funzione oggetto in esame, gli operatori evoluzionistici. Nello specico ad ogni individuo si associa un valore di tness in funzione del valore assunto dalla funzione oggetto in quel punto, dunque vengono selezio-nati stocasticamente gli individui, preferendo quelli col maggior tness. A partire dagli individui selezionati si generano delle nuove soluzioni, che, dopo una eventuale fase di mutazione vengono reinserite nella popolazione iniziale dando luogo ad una nuova generazione. In base alla teoria evoluzionistica una popolazione libera di evolvere sviluppa, con il passare delle generazioni, caratteri che rendono gli individui più adattati alle condizioni ambientali. In altri termini col procedere delle iterazioni vengono generati modelli il cui corrispondente valore di funzione oggetto risulta essere sempre minore, no a soddisfare le condizioni di convergenza. In gura 1.1 è schematicamente rappresentato un ow di base di un algoritmo genetico. Per ulteriori dettagli in merito si rimanda all'appendice A.1.

Figura 1.1: Diagramma schematico del usso di un algoritmo genetico Una delle problematiche principali degli algoritmi genetici è la conver-genza precoce verso un minimo locale, denominata genetic drift. Questo

fenomeno si manifesta quando un numero consistente di soluzioni si accumu-la in un intorno di un minimo locale: a causa delle dinamiche dell'algoritmo le soluzioni, generate a partire dagli individui più promettenti della genera-zione precedente, saranno localizzate ancora nell'intorno dello stesso minimo locale, inibendo le capacità esplorative dell'algoritmo.

In questo lavoro si vuole presentare una soluzione innovativa al gene-tic drift, chiamata Drift Avoidance Genegene-tic Algorithm (DAGA), sviluppata ibridando un algoritmo genetico con un algoritmo Monte Carlo [3]. Con ciò si aumentano le potenzialità esplorative dell'algoritmo tramite generazione di nuove soluzioni random con distribuzione uniforme sull'intero spazio dei modelli.

L'algoritmo è stato implementato in linguaggio Matlab, sfruttando mas-sicciamente GEATbx [4], un toolbox di Matlab riguardante gli algoritmi genetici ed evolutivi.

Questo algoritmo è stato testato su un campione signicativo di fun-zioni analitiche, per analizzarne il comportamento in presenza di dicoltà ottimizzative dierenti. Successivamente è stato testato su problemi di ca-rattere geosico di interesse: le correzioni statiche residuali e la full-waveform inversion.

Data la natura computazionalmente esosa della full-waveform inversion è stato inoltre arontato uno studio preliminare atto a limitare il numero di modelli valutati, ovvero a direzionare la fase di esplorazione dello spazio dei modelli verso quelli più sicamente probabili e promettenti. Sono sta-te esaminasta-te diverse soluzioni possibili, sfruttando dei modelli semplici che hanno permesso di selezionare la soluzione apparentemente più prometten-te. Questa soluzione è stata testata in un caso di inversione full-waveform, dimostrando performances promettenti per futuri approfondimenti.

Nel paragrafo successivo si presenta una breve discussione sullo stato della ricerca sul genetic drift.

Nel capitolo 2 si fornisce una descrizione accurata del fenomeno di genetic drift indicando le strategie ottimizzative studiate.

Successivamente, nel capitolo 3, viene descritta nel dettaglio la strategia di ibridazione adottata e le funzioni che caratterizzano il funzionamento del DAGA.

Il capitolo 4 raccoglie i test eettuati per dimostrare la validità e l'appli-cabilità del metodo, e per valutarne le performances.

Nel capitolo 5 vengono presentai i risultati dei test preliminari sulla strategia di limitazione dell'esplorazione dello spazio dei modelli.

Inne nel capitolo 6 conclusivo sono raccolte le considerazioni nali sul lavoro svolto e le ipotesi su possibili sviluppi futuri relativi all'applicabilità del metodo per casi reali e ad altri innovativi meccanismi di ottimizzazione. Il lavoro è completato da 2 appendici. La prima riguarda gli approfon-dimenti relativi alla struttura degli algoritmi getici (appendice A.1), mentre la seconda il dettaglio delle funzioni analitiche di test utilizzate (appendice A.2).

1.1 Stato dell'arte

L'adozione degli algoritmi genetici per la soluzione di problemi geosici pone problematiche principalmente legate a:

• l'onerosità dei tempi di calcolo e • l'adabilità delle soluzioni raggiunte.

Nel primo caso esiste un'ampia letteratura riguardo la limitazione della por-zione dello spazio dei modelli esplorato tramite l'applicapor-zione di vincoli ana-litici. A quanto ci è dato sapere non sono state applicate con successo stra-tegie atte a limitare o direzionare l'esplorazione tramite vincoli basati su informazioni a priori caratterizzate da una limitata adabilità.

Nel secondo caso una delle problematiche principali è costituita dal gene-tic drift, che rappresenta una fra le principali cause di errore nell'ottimizza-zione tramite algoritmi genetici. Di conseguenza sono state ideate dierenti strategie per limitarlo.

J.Horn [5] propone l'uso di Algoritmi genetici in cui la popolazione sia suddivisa in più sottoinsiemi (sottopopolazioni) liberi di evolvere in maniera

indipendente. Tale metodo, il Niched Genetic Algorithm (NGA) è piuttosto ecace ed è stato spesso preso come base di partenza per sviluppare soluzioni più promettenti ed elaborate.

T.Eldos [6, 7] ha sviluppato un metodo che trae spunto da un evento naturale che inuenza l'evoluzione di una popolazione biologica: le cata-stro. L'operatore catastroco agisce su di un NGA in maniera discontinua sulle generazioni, eliminando casualmente una porzione signicativa di una sottopopolazione selezionata.

Il crowding [8, 9] sviluppato per la prima volta da De Jong si sviluppa in due fasi: aancamento e rimpiazzo. Nella prima fase gli ospring vengono accoppiati con gli individui della popolazione corrente a loro più vicini, nella seconda fase per ogni coppia si seleziona e sostituisce uno dei due individui. Ciò mira a preservare la diversità e limita la convergenza precoce.

Capitolo 2

Genetic Drift

Nella genetica delle popolazioni per Genetic Drift si intende un fenomeno che tende ad accrescere o a ridurre la frequenza di un allele (i.e. una forma di un gene che denisce uno specico carattere di un individuo) con il passare delle generazioni [10]. Dopo un numero suciente di generazioni tale allele sarà comune a tutti gli individui, oppure a nessuno di essi.

Trasponendo tale denizione agli algoritmi genetici (per ulteriori dettagli si faccia riferimento all'appendice A.1) risulta che il genetic drift è legato alla convergenza prematura dell'algoritmo in un minimo locale. Formalmente il teorema fondamentale degli algoritmi genetici [1] garantisce la convergenza dell'algoritmo per popolazioni innite. Tale teorema non risulta più valido se l'ipotesi di innitezza della popolazione iniziale viene meno. Da ciò segue il genetic drift.

Una descrizione euristica del fenomeno può essere fornita in termini di comportamento degli individui: se almeno un individuo dovesse essere ge-nerato all'interno di un intorno convesso (e dunque connesso) di un minimo locale, e risultasse avere un valore di tness migliore degli altri individui della stessa popolazione, allora la popolazione tenderebbe, nelle generazioni future, a convergere a tale minimo, riducendo la variabilità genetica ai va-lori dell'insieme connesso. Ciò implica che gli ospring (ovvero gli individui generati nell'iterazione successiva come combinazione lineare degli individui migliori della generazione corrente), a meno di una mutazione di grande

tità, saranno localizzati tutti e soli all'interno dell'insieme connesso. Una mutazione ecace deve essere tale da ricollocare un ospring al di fuori del più grande insieme connesso contenente il minimo locale ed in un punto con tness migliore dell'elitist della popolazione (i.e. l'individuo il cui valore del-la funzione oggetto è minimo neldel-la popodel-lazione in esame); quest'ultimo è un evento potenzialmente raro, fortemente legato alla topologia indotta dalla funzione oggetto del problema considerato.

Ne consegue che risulta necessario implementare una correzione all'algo-ritmo di base per evitare, o quantomeno limitare, la convergenza prematu-ra ad un minimo locale, che determinerebbe il fallimento della ricerca del minimo globale.

2.1 Esempio di drift

Per maggiore chiarezza si fornisce un esempio pratico di drift, che evidenzia l'incapacità dei GA di individuare il minimo globale della funzione oggetto in esame a partire da un set di soluzioni iniziali generate randomicamente.

Figura 2.1: Localizzazione degli individui costituenti la popolazione iniziale sulla topologia indotta dalla funzione oggetto sullo spazio dei modelli

Si vuole ottimizzare una funzione di Schwefel (per ulteriori dettagli si faccia riferimento all'appendice A.2) con un algoritmo genetico. Si sceglie una popolazione di 10 individui ed una selective pressure dell'80% (ossia per ogni generazione viene rimpiazzato l'80% degli individui della popolazione). In gura 2.1 sono stati evidenziati in nero i punti corrispondenti ai cromosomi della prima generazione, sovrapposti alla topologia indotta dalla funzione oggetto sullo spazio dei modelli. Risulta evidente la grande distanza fra i minimi locali, inoltre nessun individuo della popolazione iniziale è prossimo al minimo globale, evidenziato dalla freccia rossa.

In gura 2.2 sono mostrate:

• la distanza del cromosoma migliore (nel senso del valor minimo della funzione oggetto) di una data generazione rispetto al minimo globale, in funzione delle generazioni (iterazioni) dell'algoritmo,

• la distanza media fra i cromosomi componenti una data generazione, in funzione delle generazioni.

a) b)

Figura 2.2: Analisi dell'inversione: a) Distanza fra l'elitist e il minimo globale e b) Distanza media fra i cromosomi

Si nota che, a partire dalla popolazione iniziale, i cromosomi si sono al-lontanati dal minimo globale (per convergere verso dei minimi locali), quindi, già dopo 10 iterazioni, la distanza non varia più con le generazioni no alla

generazione 40. Durante la generazione 40 c'è stato un grosso incremento della distanza rispetto al minimo globale, dovuto alla scoperta di un minimo locale con valori della funzione oggetto ben minori del precedente. Successi-vamente si ripete l'assenza di variazioni della distanza del best model rispetto al target dell'ottimizzazione. Tale fatto è dovuto alla grossa dicoltà che in-contra l'algoritmo nel generare nuovi individui molto distanti dal minimo locale in cui l'intera popolazione è precocemente conversa, poiché i minimi limitro assumono valori molto meno signicativi, ovvero gli individui gli che possono trovarvisi avrebbero un valore di tness estremamente depresso rispetto ai genitori, e dunque verrebbero scartati nelle generazioni successi-ve. Si può anche notare come, dopo poche generazioni dall'individuazione del minimo locale, tutti gli individui componenti la generazione convergono verso quel minimo locale, assumendo valori sostanzialmente uguali.

Figura 2.3: Minimo individuato dall'inversio-ne GA dopo 100 gedall'inversio-nerazioni

In gura 2.3 è mostrata la posizione del minimo indi-viduato dall'algoritmo dopo 100 iterazioni (con la stella rossa). È opportuno sotto-lineare che il fallimento nel-l'individuazione del minimo globale (in basso a destra) è fortemente dipendente dal-la scelta dei modelli inizia-li. Tale dipendenza è in net-to contrasnet-to con la strategia dei metodi di ricerca globa-le, che vorrebbero garantire

la localizzazione del risultato ottimo a prescindere dalle condizioni iniziali. In questo lavoro si presenta una soluzione innovativa, che trae spunto da [6, 8, 9], per attenuare il fenomeno ibridando l'algoritmo con un altro me-todo di ottimizzazione globale che non sore aatto di convergenza precoce: l'algoritmo Monte-Carlo.

ottenuto combinando alcuni principi del niched genetic algorithm (NGA) [5] (per ulteriori dettagli si faccia riferimento all'appendice A.1) e del Monte Carlo (MCA) [3, 12]. Nello specico sono state aggiunte tre funzioni al nor-male ow del NGA: competizione, catastro e ripopolamento. Il principio comune alle diverse funzioni è quello di aumentare le capacità esplorative dell'algoritmo, generando durante le iterazioni nuove soluzioni in maniera casuale. Il risultato ottenuto è stato quello di garantire all'algoritmo una buona esplorazione dello spazio dei modelli anche nel caso di topologie estre-mamente complesse, garantendo il raggiungimento del minimo globale nella quasi totalità dei test. Come drawback il tempo di calcolo è risultato mag-giore rispetto ad un normale NGA a causa del maggior numero di soluzioni esplorate.

Capitolo 3

DAGA

Il DAGA è un algoritmo genetico modicato per ridurre il fenomeno di drift: è stata potenziata sensibilmente la capacità esplorativa sfruttando due dif-ferenti metodi di ibridazione con un algoritmo Monte Carlo. Ciò è stato ottenuto generando, durante le iterazioni, delle soluzioni random uniforme-mente distribuite su tutto lo spazio dei modelli, a discapito di individui poco promettenti. Ciò garantisce un aumento di variabilità genetica e, di conse-guenza, una limitazione del fenomeno di drift. Una scelta randomica potreb-be, nei problemi pratici presi in esame, comportare la valutazione di modelli di scarso interesse sico, e di conseguenza imporrebbe il calcolo di problemi diretti relativi a modelli non verosimili e poco promettenti. Si osserva però che gli ospring ottenuti come ricombinazione fra questi individui e individui con alti valori di tness sarebbero localizzati in porzioni nuove dello spazio dei modelli, ereditando le caratteristiche dei genitori migliori.

Sono stati sviluppati due operatori, competition e catastrophe and repo-pulation, aggiunti in coda al normale usso di un algoritmo genetico, che con metodi dierenti rimpiazzano alcuni cromosomi con altri generati random, come illustrato in gura 3.1 (per una descrizione dettagliata degli algorit-mi genetici e dei relativi operatori citati nel diagramma di usso si faccia riferimento all'appendice A.1).

Lo scopo specico dei due metodi è quello di disincentivare stagnazioni in minimi locali delle singole sottopopolazioni, favorendone l'esplorazione dello

Figura 3.1: Diagramma di usso dell'algoritmo spazio dei modelli.

Il primo operatore Competizione è una funzione che riduce il numero di individui simili di ogni sottopopolazione, sviluppando in maniera innovativa l'idea alla base del crowding [8]. Con il procedere delle generazioni, soprat-tutto in presenza di fenomeni di drift, è probabile che sempre più individui assumano valori simili. Ciò comporta una stagnazione della popolazione in analisi e una grossa spesa computazionale per calcolare forward modeling di modelli sostanzialmente uguali fra loro.

Il crowding è un algoritmo che mira a ridurre il genetic drift riducendo il numero di individui vicini. Per farlo gli ospring vengono aancati ai genitori più prossimi, quindi fra questi ne viene selezionato e reinserito uno per ogni coppia.

L'algoritmo proposto invece, in ogni generazione, sceglie una o più coppie di individui simili per ogni sottopopolazione, a prescindere che questi siano o meno ospring presenti nella neighbourhood del genitore più prossimo, quindi per ogni coppia viene selezionato un individuo, in base ai valori della funzione oggetto degli individui della coppia, che verrà rimpiazzato con un nuovo cromosoma generato casualmente con probabilità uniforme su tutto lo spazio dei modelli.

Ciò comporta un ricambio sistematico degli individui della popolazione, e conseguentemente un'esplorazione dello spazio dei modelli più ecace. Que-sto metodo da solo non è suciente a garantire una buona soluzione per il drift, in quanto:

• per preservare una buna velocità di convergenza dell'algoritmo, è ne-cessario che una porzione sostanziale di individui rimanga collocata in un intorno quanto più limitato possibile del minimo individuato. • per limitare il costo computazionale è necessario che il numero di

indi-vidui rimpiazzati sia sucientemente esiguo.

• per limitare il fenomeno di drift è necessario che un numero su-cientemente elevato di modelli sia generato al di fuori di un minimo potenzialmente locale.

Queste condizioni sono chiaramente in conitto fra loro, pertanto risulta necessario individuare un valido compromesso fra l'aumento del costo com-putazionale e il rapporto fra esplorazione e convergenza dell'algoritmo. Nel-l'elaborazione dei test presentati in questo lavoro tale scelta è state eettuata tramite ranamenti successivi con una strategia try and error.

Il secondo operatore è composto da due funzioni: catastro e ripopola-mento. Un NGA ha una ridotta variabilità genetica rispetto ad un GA a singola popolazione, infatti, a parità di individui totali, nell'NGA essi sono suddivisi in più sottopopolazioni, ciascuna delle quali contiene solo una por-zione degli individui di partenza. Ciò implica una ridotta variabilità genetica della singola sottopopolazione, e, per topologie piuttosto complesse, potreb-be portare alcune sottopopolazioni a stagnazione prematura potreb-ben prima della generazione in cui un GA a popolazione singola con parametri equivalenti giungerebbe a drift. Non sempre la sola funzione di migrazione è suciente ad impedire tale fenomeno.

La soluzione proposta segue il principio esposto da T.Eldos [6] secondo cui gli algoritmi genetici orono migliori soluzioni quando evolvono in modo più simile alla realtà. Nello specico viene introdotto un evento casuale

che colpisce saltuariamente una sottopopolazione scelta in maniera random, e ne elimina un numero importante di individui. Gli individui eliminati vengono rimpiazzati nelle generazioni successive con la seconda funzione, alcuni tramite migrazione e altri tramite generazione di individui random con probabilità uniforme su tutto lo spazio dei modelli.

Questa funzione garantisce un ricambio saltuario molto signicativo degli individui di una sottopopolazione.

3.1 Competizione

La competizione è la prima delle funzioni caratterizzanti il DAGA. Garantisce all'algoritmo una lenta ma costante esplorazione dello spazio dei modelli. La funzione apporta delle modiche alla popolazione in ogni generazione, dun-que ne consegue che il numero di chiamate alla funzione (e alle sottofunzioni richiamate nel codice) è molto elevato. Tale osservazione, insieme alla neces-sità di eseguire il forward modeling per i cromosomi generati dalla funzio-ne, aumenta il costo computazionale complessivo dell'algoritmo. Per ridurre tale problematica è stata necessaria un'ottimizzazione del codice piuttosto accurata.

Di seguito viene analizzato il codice nel dettaglio, descrivendo anche le scelte e le ottimizzazioni legate all'implementazione.

Descrizione della funzione

La funzione Competition è così denita:

function [chrome, randIx]=competition(chrome, OBJ, CN, ... FieldDR, k, SUBPOP) I parametri in input della funzione sono:

• chrome la matrice dei cromosomi della generazione in analisi, in cui ogni riga rappresenta un individuo della popolazione, ovvero una solu-zione del problema,

• OBJ i rispettivi valori della funzione oggetto,

• CN il numero di trials, ovvero il numero di individui da rimpiazzare per ogni sottopopolazione,

• FieldDR i valori massimi e minimi dello spazio dei modelli,

• k un parametro di controllo sulla distanza a partire dalla quale eet-tuare le sostituzioni,

• SUBPOP (opzionale) un vettore contenente l'informazione relativa alla sottopopolazione cui appartengono i singoli cromosomi.

La funzione opera ricorsivamente su ciascuna sottopopolazione denita tra i parametri in input.

Dunque, supponendo di operare sui cromosomi di una singola sottopopo-lazione, l'algoritmo può essere schematizzato come:

• calcolo della distanza di ogni coppia di cromosomi,

• esclusione degli individui migliori dalle operazioni successive,

• test sulla distanza media degli individui: se è troppo grande l'algoritmo si interrompe senza eseguire rimpiazzi

• individuazione delle CN coppie di cromosomi più vicine • selezione di un cromosoma per ogni coppia scelta

• rimpiazzo dei cromosomi selezionati con nuove soluzioni generate su tutto lo spazio dei modelli.

La prima operazione eseguita nel codice è il calcolo della distanza euclidea fra tutte le coppie di cromosomi, al ne di individuare gli individui simili da rimpiazzare.

Per ridurre il tempo di calcolo l'operazione è stata vettorializzata. Inoltre si è scelto di operare con il quadrato della distanza euclidea, per evitare il co-sto dell'estrazione di radice. Ciò è lecito in quanto l'estrazione di radice è una funzione strettamente crescente in [0, +∞), e dunque biettiva sull'intervallo considerato.

Il calcolo del quadrato della distanza euclidea fra due generici punti α e β è dato da:

||α − β||2 = ||α||2+ ||β||2 − 2 < α, β >

in cui < ·, · > rappresenta il prodotto scalare. Dovendo calcolare le distanze fra cromosomi posizionati sulle righe di una matrice, è possibile esprimere la distanza in forma matriciale. Siano:

• ˜C il vettore colonna avente per elementi la norma L2 dei corrispondenti cromosomi,

• I la matrice identità di dimensione pari al numero di cromosomi, allora:

Dist= ˜C · It+ I · ˜Ct− 2C · Ct

indicando con ·t l'operatore di trasposizione.

Questa forma permette un notevole risparmio di tempo, in quanto si evi-tano strutture iterative, sfruttando le ottimizzazioni di Matlab per il calcolo matriciale.

Il vettore risultante sarà della forma

Dist=                  dist(chrome1, chrome2) ...

dist(chrome1, chromeend)

dist(chrome2, chrome3)

...

dist(chrome2, chromeend)

...

dist(chromeend−1, chromeend)

                

dunque, supponendo di avere Nind individui, il vettore Dist avrà lunghezza N ind ·(N ind − 1)/2.

Per popolazioni piuttosto grandi il vettore di distanze occupa quantità consistenti di memoria. Di conseguenza operare con questo vettore è com-putazionalmente costoso. Risulta però necessario eseguire determinate ope-razioni sul vettore, ad esempio escludere dall'elenco quelle distanze calcolate rispetto agli individui migliori e, in un secondo momento, quelle relative ad un individuo sostituito, anché non venga selezionato per una sostituzione successiva.

Per queste ragioni, sfruttando le potenzialità di Matlab, piuttosto che lavorare direttamente sul vettore Dist, si è scelto di lavorare sul corrispon-dente vettore di indici booleano boolean_index, ovvero un vettore di pari

lunghezza di dist che assume il valore false per escludere le coppie su cui non devono essere eettuate le operazioni di rimpiazzamento, e true per tutte le altre.

L'operazione successiva consiste nell'escludere gli individui migliori della generazione corrente dalle operazioni di rimpiazzamento. È stato scelto di operare questa esclusione per non rischiare di perdere soluzioni promettenti che richiederebbero uno sforzo computazionale per essere ritrovate. Dunque vengono determinati gli indici di tutte le distanze calcolate rispetto ad uno di questi valori e viene posto uguale a false il corrispondente valore del vettore di indici booleano.

Successivamente si valuta se la distanza media fra i cromosomi è su-cientemente grande, ovvero se

mean(dist(boolean_Index)) < (mean_dist/k)2_{· dim}

in cui dist(boolean_Index) è il vettore di distanze lecite (ovvero quelle cor-rispondenti ai true del vettore boolean_index), mean_dist la media sulle dimensioni della lunghezza dello spazio dei modelli e dim la dimensione dello spazio dei modelli.

Nel caso in cui la disuguaglianza sia vericata si eseguono le sostituzioni, iterando su CN.

Innanzitutto si trova la coppia di individui più vicini con una scansione degli elementi validi del vettore di distanza.

Tale operazione fornisce l'indice del vettore di distanze corrispondente alla coppia scelta. Per determinare gli indici dei due cromosomi è neces-sario sfruttare un'altra funzione che risale ai due vettori con un'operazione analitica, descritta nel seguito.

Detti α e β gli indici dei due cromosomi, tali che β > α, h l'indice del vettore di distanza corrispondente alla distanza fra α e β e n il numero totale di cromosomi, allora vale

Allora

h= (2n − α) · (α − 1)

2 + (β − α) =

−α2_{+ (2n − 1) · α}

2 + (β − n) Ricordando che β > α allora vale

h > −α

2_{+ (2n + 1) · α}

2 − n

e dunque vale la disuguaglianza α2

2 −

2n + 1

2 · α + h + n > 0 Le radici dell'equazione associata sono

α1/2=

2n + 1 ±p(2n + 1)2_{− 8(h + n)}

2

entrambe positive, in quanto l'argomento della radice è sempre positivo e minore di (2n + 1)2_{. Risulta facile dimostrare che delle due radici una è}

sempre minore di n e una sempre maggiore. Inoltre si osserva che per ogni valore di β compreso fra α + 1 ed n l'equazione deve portare allo stesso valore intero di α. Dunque, avendo imposto per le soluzioni dell'equazione associata, che β = α, deve risultare che α sia uguale al primo valore intero maggiore della più piccola radice dell'equazione associata, ovvero:

α = [(2n + 1 −p(2n + 1)2_{− 8(h + n))/2] + 1}

indicando con le parentesi quadre l'operatore parte intera di. Di conseguen-za, noto α si può calcolare dall'equazione precedente:

β = h − n · (α − 1) + α · α+ 1 2

Tale operazione è analitica, e dunque richiede un tempo di calcolo sostan-zialmente nullo nell'economia del costo computazionale dell'algoritmo.

metodo simile al roulette wheel (descritto nel paragrafo dell'appendice A.1 relativo alla selezione):

• si divide un segmento unitario in due parti di lunghezza proporziona-le al valore della funzione oggetto corrispondente a ciascuno dei due individui (individui migliori occuperanno spazi minori).

• Si genera un numero random nell'intervallo [0, 1],

• se tale numero ricade nell'intervallo corrispondente al primo cromosoma questo verrà scelto, altrimenti sarà scelto l'altro.

L'elemento selezionato verrà rimpiazzato da un nuovo cromosoma genera-to sull'intero spazio dei modelli con probabilità uniforme, in maniera analoga al sistema di generazione delle soluzioni di un MCA.

Al termine delle iterazioni su CN, si fornisce in output l'elenco dei cromo-somi aggiornato con i rimpiazzi eettuati e un vettore di indici dei cromocromo-somi sostituiti, per poterne calcolare i nuovi valori della funzione oggetto.

3.2 Catastro

In natura una catastrofe è un evento sporadico che riduce drasticamente il numero di individui di una popolazione. Tale dinamica può essere sfruttata per sviluppare un operatore composto da due funzioni: una prima fase di eliminazione casuale di grande entità ed una successiva di ripopolamento su più generazioni che riporti il numero di individui alla numerosità originaria [6].

Descrizione della funzione

function [chrome, SUBPOP, OBJ]=

destroy(chrome, SUBPOP, subpop0, prob_destroy,... OBJ, intensity_level,gen, gen_max)

I parametri caratterizzanti della funzione sono:

• chrome la matrice dei cromosomi della generazione in analisi, in cui ogni riga rappresenta un individuo della popolazione, ovvero una solu-zione del problema,

• SUBPOP un vettore contenente l'informazione relativa alla sottopo-polazione cui appartengono i singoli cromosomi,

• subpop0 la divisione iniziale di cromosomi in sottopopolazioni, • prob_ destroy la probabilità con cui avviene una catastrofe in una

data generazione,

• OBJ i rispettivi valori della funzione oggetto,

• intensity_ level il livello d'intensità della catastrofe, ovvero un nu-mero compreso fra 0 ed 1 che determina il nunu-mero di individui eliminati durante una catastrofe (valori maggiori determinano più rimozioni), • gen la generazione attuale,

Anche in questo caso si è scelto di escludere dalle operazioni gli individui migliori di ogni sottopopolazione, per non perdere soluzioni promettenti.

Il numero di individui da salvare è stato ssato in 3, ed allo stesso modo sono stati deniti staticamente il raggio medio di propagazione della cata-strofe, la sua varianza, ed un parametro necessario per la funzione adattiva sulle generazioni che determina il numero di eliminazioni.

È stato scelto di non rendere modicabili questi parametri per semplicità: sarebbe altrimenti stato necessario denire un grande numero di parametri aggiuntivi per il corretto funzionamento del DAGA. I valori scelti risultano essere un buon compromesso per la maggior parte dei test eseguiti.

La prima operazione della funzione consiste nel valutare se la catastrofe viene innescata o meno nella generazione corrente: si genera un numero ran-dom nell'intervallo [0, 1] e viene confrontato con la probabilità che avvenga la catastrofe, in caso di risultato positivo si procede con la funzione, altri-menti non succede nulla e la funzione termina senza aver eseguito nessuna operazione sui cromosomi. Ciò permette di avere un eetto discontinuo nelle generazioni.

Nel caso in cui la catastrofe venga innescata, si procederà con dei passaggi preliminari:

• si calcola il valore medio dei valori della funzione oggetto per ogni sottopopolazione,

• si esegue un ranking con i valori medi di tness ottenuti nel passaggio precedente,

• si seleziona il centro della catastrofe (la sottopopolazione colpita) con un metodo analogo al roulette wheel: si genera un numero random nell'intervallo [0, 1], quindi si confronta con il ranking delle sottopopo-lazioni, dando maggiore probabilità di essere sorteggiate alle sottopo-polazioni con valori minori di ranking,

• si calcola il raggio di eetto con un metodo stocastico a distribuzione gaussiana che, con i parametri impostati, ha una buona probabilità che sia pari a 1, ovvero che la catastrofe colpisca con minore intensità le

sottopopolazioni a distanza 1. Ad esempio se il centro della catastrofe è la 3a _{sottopopolazione ed il raggio è 1, verranno colpite con eetti}

minori la 2a _{e la 4}a _{sottopopolazione,}

• si valuta l'intensità, ovvero il numero di individui eliminati dalla cata-strofe, con una funzione stocastica a distribuzione gaussiana adattiva sulle generazioni [7]:

 si calcola la media della distribuzione normale adattivamente sulle generazioni

Nd= e−a

gen genmax · N₀

in cui a è un numero inferiore di 1 che determina la decrescita del numero di individui eliminati al crescere delle generazioni, gen la generazione corrente, genmax la generazione massima e N0 il

nu-mero di individui originariamente costituenti la sottopopolazione selezionata,

 si calcola la varianza adattivamente sulle generazioni σd = (N0− Nd) · intensity_level

in cui N0 ed Ndsono stati deniti in precedenza e intensity_level

è un parametro fornito in input alla funzione,  si calcola il numero di individui da eliminare come

Ndel = ranksubpop(centre) · (Nd+ σd· randn)

in cui ranksubpop(centre) è un valore compreso fra 0 e 1

calcola-to in precedenza per selezionare il centro della catastrofe. Tan-to è maggiore quanTan-to peggiore è il tness medio degli individui della sottopopolazione. centre è la sottopopolazione centro del-la catastrofe, e randn è un numero random selezionato da una distribuzione gaussiana a media 0 e varianza 1.

Terminate queste operazioni si selezionano gli individui della sottopopo-lazione centrale da eliminare. Anche in questo caso si è scelto di lavorare con un vettore di indici, così da poter gestire le operazioni accuratamente e con un onere computazionale piuttosto limitato.

Innanzitutto si escludono dal vettore degli indici quelli relativi agli indivi-dui migliori, quindi si procede alla selezione degli indici relativi agli indiviindivi-dui da eliminare tramite una subroutine che richiama la funzione di selezione de-gli algoritmi genetici, privilegiando de-gli individui con tness peggiore. Inne si eliminano gli individui e i corrispondenti valori della funzione oggetto usan-do un vettore logico opportunamente costruito, inoltre si aggiorna il vettore contenente le informazioni relative alle sottopopolazioni, essendo cambiato il numero di individui della sottopopolazione in analisi.

Con lo stesso metodo si procede sulle popolazioni laterali, con la dierenza che il numero di individui da eliminare sarà minore tanto maggiore sarà la distanza dal centro della catastrofe.

La funzione restituisce in output:

• la matrice avente per righe i cromosomi della popolazione,

• il vettore contenente i corrispondenti valori della funzione oggetto, • il vettore contenente il numero di individui appartenenti a ciascuna

3.3 Ripopolamento

La funzione di ripopolamento completa la gestione degli eventi catastroci nel DAGA. Lo scopo della funzione è reintrodurre degli individui in una po-polazione colpita da una catastrofe nelle generazioni successive all'evento. La fase di ripopolamento è distribuita su più iterazioni, così da ridurre il numero di forward modeling per generazione, e per massimizzare l'eetto ottenuto dall'introduzione di nuovi individui nella sottopopolazione. Per limitare il costo computazionale della funzione, e per incrementare lo scambio di infor-mazioni fra le sottopopolazioni, è stato scelto di reintegrare gli individui in due modi:

• migrazione degli individui migliori delle altre sottopopolazioni,

• generazione di individui random uniformemente distribuiti su tutto lo spazio dei modelli.

function [chrome, SUBPOP, OBJ]=

repop(chrome, SUBPOP, subpop0, OBJ, FieldDR)

La funzione non richiede la scelta di parametri che ne regolino il funziona-mento. Gli unici parametri richiesti sono quelli caratterizzanti la popolazione e la generazione corrente:

• chrome la matrice dei cromosomi della generazione in analisi, in cui ogni riga rappresenta un individuo della popolazione, ovvero una solu-zione del problema,

• SUBPOP un vettore contenente l'informazione relativa alla sottopo-polazione cui appartengono i singoli cromosomi,

• subpop0 la divisione iniziale di cromosomi in sottopopolazioni, • OBJ i rispettivi valori della funzione oggetto,

Sono stati deniti dei parametri costanti all'interno della funzione, aventi lo scopo di limitare il numero massimo di individui reintrodotti e quello di individui generati random. Nello specico è stato scelto:

• di reintrodurre un numero di individui inferiore ad 1/3 rispetto al numero iniziale dei componenti la sottopopolazione,

• di generare un numero di individui random non superiore ad 1/10 del totale di individui reintrodotti.

Per ogni popolazione si determina il numero di individui da reintrodurre, garantendo il rispetto delle condizioni iniziali e che non venga mai superato il numero di individui della popolazione iniziale.

Gli individui da migrare vengono scelti tramite selezione su tutta la popolazione (senza ripetizioni).

I nuovi individui vengono generati con probabilità uniforme sullo spazio dei modelli.

La fase di introduzione dei nuovi individui prevede l'inserimento degli elementi migrati con i corrispondenti valori della funzione oggetto a partire dal primo elemento della sottopopolazione di appartenenza, ed a seguire i nuovi cromosomi. I valori corrispondenti della funzione oggetto vengono posti a NaN, per poter essere facilmente individuati e sostituiti con i valori di tness all'interno del ow principale del DAGA.

Vengono aggiornati di conseguenza anche i vettori con le informazioni sulle sottopopolazioni. In output vengono quindi restituiti la matrice aggior-nata dei cromosomi, il vettore aggiornato contenete le informazioni riguardo le sottopopolazioni e il vettore dei valori della funzione oggetto.

Capitolo 4

Test

Lo scopo dei test presentati è quello analizzare le performances del DAGA in dierenti contesti ottimizzativi, al ne di valutarne l'ecacia.

I test presentati in questo capitolo sono suddivisi in:

• test su funzioni analitiche (sezione 4.1), in cui il DAGA viene testa-to su diverse funzioni che simulano dicoltà tipiche di problemi di ottimizzazione.

• Correzioni statiche residuali (sezione 4.2), in cui viene arontato un problema geosico fortemente non lineare caratterizzato da una funzio-ne oggetto multimodale di dicile ottimizzaziofunzio-ne.

• Full-waveform inversion (sezione 4.3), complesso problema di interesse geosico, approcciato ecacemente con algoritmi genetici [2].

La scelta di queste funzioni per testare il DAGA è nalizzata a garantirne un analisi accurata delle performances in contesti dierenti e quanto più generale possibile.

4.1 Test su Funzioni Analitiche

Per testare l'ecacia dell'algoritmo sono state usate dierenti funzioni ana-litiche, atte a simulare topologie tipiche di problemi di ottimizzazione.

4.1.1 Denizione e proprietà delle funzioni test

Le funzioni test sono spesso utilizzate per testare limiti e performances degli algoritmi di ottimizzazione. Sono generalmente caratterizzate da topolo-gie complesse per poter valutare le caratteristiche speciche dell'algoritmo analizzato (robustezza, tasso di convergenza, precisione).

Sia data una generica funzione test

f _{: D ⊂ R}n _{−→ R} Allora deve valere:

1. f è analitica,

2. D è un sottoinsieme proprio compatto di Rn_,

3. f ha un numero limitato di minimi.

Da tali condizioni seguono delle proprietà che rendono le funzioni test particolarmente ecaci nel testare le prestazioni di un'ottimizzazione. conseguenze

• Il calcolo del problema diretto risulta essere rapido ed ecace.

Per la condizione 1 le operazioni di calcolo sono limitate alla valuta-zione della f nel punto considerato, e dunque il tempo macchina sarà proporzionale al numero di operazioni analitiche da eseguire.

• il dominio delle funzioni oggetto è chiuso e limitato.

• le funzioni oggetto sono continue con le proprie derivate. Tale fatto segue direttamente dalla condizione 1.

• le funzioni oggetto hanno almeno un minimo globale ben denito all'in-terno del codominio della funzione.

Tale osservazione è garantita dal teorema di Weierstrass [13] e dalle condizioni 1 e 2.

Tale teorema insieme alla condizione 3 garantisce l'esistenza e la nitez-za dell'insieme delle soluzioni {x ∈ D : f(x) ≤ f(y) ∀ y ∈ D}. Nello specico le funzioni scelte hanno un unico punto di minimo globale, ciò garantisce l'unicità della soluzione del problema di ottimizzazione in analisi.

Le funzioni su cui sono tate eettuate le inversioni sono: • Akley

• Eggholder • Langermann • Rastrigin • Schwefel

Per maggiori dettagli si faccia riferimento alle appendici A.2.

4.1.2 Criteri di comparabilità dei risultati

Per una corretta valutazione delle proprietà stocastiche degli algoritmi in ana-lisi è stato scelto di ripetere più volte i vari test, imponendo come condizione di uscita il raggiungimento di una iterazione pressata oppure l'individua-zione di un modello avente una distanza rispetto al minimo globale (pesata sulle dimensioni del problema) minore o uguale ad un epsilon pressato [14]:

s Pdim

i=1(Centrei− modeli)2

detti centre il valore del minimo globale, model il modello migliore di una data generazione, dim la dimensione del problema ed ε un valore preimpo-stato.

Data la natura stocastica degli algoritmi di ottimizzazione globale, la ripetizione successiva di un test fornirà risultati dierenti. Una adeguata analisi dei risultati può essere eseguita a partire da una statistica delle per-formance ottenute nelle diverse ripetizioni. Per un'adeguata visualizzazione dei risultati è stato scelto di collezionare i dati in curve cumulative, ovvero ad ogni generazione è stato associato un valore che rappresenta il numero di volte che l'algoritmo ha trovato una soluzione che soddisfacesse il criterio di convergenza impiegando un numero di generazioni minore o uguale alla generazione corrente.

Per garantire un confronto bilanciato è stato valutato lo stesso numero di modelli per tutte le funzioni prese in esame, a meno degli individui generati random dalle nuove funzioni introdotte in questo lavoro.

Tutti i test sono stati eettuati con un codice seriale Matlab compilato su di una CPU intel i3@1.7GHz

4.1.3 Analisi comparata

I primi tre test eettuati hanno lo scopo di provare come le funzioni imple-mentate in questo lavoro comportino un miglioramento sostanziale al NGA, inoltre si vuole evidenziare come i contributi delle due funzioni (Competition e Catastrophy and Repopulation) prese singolarmente siano meno ecaci della combinazione delle due. Pertanto si è scelto di confrontare il DAGA con il NGA integrato con una sola delle due funzioni componenti il DAGA (la competizione per CompGA e catastro e ripopolamento per CataGA). Inoltre per analizzare l'eettivo miglioramento oerto dalle nuove funzioni, si è scelto di aggiungere al confronto anche i risultati delle inversioni ottenute con un NGA e con un GA standard.

Per i tre test presentati sono state eseguite 100 ottimizzazioni generando ogni volta una popolazione iniziale dierente.

Rastrigin 2d

Per questa ottimizzazione sono stati scelti dei parametri piuttosto limitati, così da rendere la ricerca quanto più dicile possibile per l'algoritmo.

Parametri valori Dimensione del problema 2 # Popolazione iniziale 6 # Sottopopolazioni 2 # Massimo di generazioni 200 Tasso di selezione 0.8 Parametri DAGA # Rimpiazzi 1 probabilità catastrofe 0.2

Tabella 4.1: Parametri del test

Figura 4.2: Numero medio di modelli generati dai vari algoritmi Risulta evidente dal graco 4.1 come l'ottimizzazione non presenti parti-colari ostacoli, tanto che gli algoritmi classici hanno un rateo di convergenza analogo a quello degli algoritmi ottimizzati.

Ciò è dovuto alla topologia indotta dalla funzione oggetto sullo spazio dei modelli, ottenuto dalla combinazione di un'armonica con un iperboloide. La morfologia risultante è costituita da un insieme di picchi e valli di valore decrescente all'avvicinarsi del minimo globale. Ciò comporta che i minimi locali prossimi a quello globale corrispondono a valori della funzione oggetto migliori rispetto a regioni più distanti. Tale fatto comporta un'esplorazione direzionata verso il minimo globale, rendendo superua un'esplorazione più vasta dello spazio dei modelli.

In gura 4.2 si può notare come il numero di modelli valutati per i diversi algoritmi sia sostanzialmente uguale, a causa dell'esiguo numero di individui della popolazione iniziale, e, di conseguenza, l'ancora più ridotto numero di individui generati random.

La curva corrispondente a CataGA risulta depressa rispetto alle altre a causa di un leggero aumento di velocità di convergenza fra la generazione 60 e la 80. Ciò ha determinato un numero totale di individui generati inferiore

agli altri algoritmi.

Figura 4.3: Errore medio degli algoritmi

La gura 4.3 rappresenta l'errore medio degli individui migliori ad una data generazione. L'andamento è anche in questo caso simile per tutti gli algoritmi. Si può notare come il GA abbia un'exploitation migliore, ovvero una maggiore capacità di convergere verso il valore del minimo globale, una volta individuato un intorno convesso di tale minimo.

# di test a convergenza per GA 96 # di test a convergenza per NGA 96 # di test a convergenza per CompGA 99 # di test a convergenza per CataGA 97 # di test a convergenza per DAGA 99 # di medio di modelli generati per GA 518 # di medio di modelli generati per NGA 526 # di medio di modelli generati per CompGA 521 # di medio di modelli generati per CataGA 438 # di medio di modelli generati per DAGA 528

I risultati riportati in tabella 4.2 confermano quanto detto in precedenza. Il numero di successi è pressoché lo stesso per tutti gli algoritmi, come già evidenziato dalla gura 4.1.

Schwefel 2d

La funzione di Schwefel è stata scelta per esaminare le performances degli algoritmi in un contesto molto più dicile, a causa della topologia fortemente multimodale, con grandi valli di minimo isolate e localizzate ai bordi dello spazio dei modelli. La posizione al bordo del minimo globale costituisce un'ulteriore dicoltà per i GA.

Parametri valori Dimensione del problema 2 # Popolazione iniziale 7 # Sottopopolazioni 2 # Massimo di generazioni 300 Tasso di selezione 0.8 Parametri DAGA # Rimpiazzi 1 probabilità catastrofe 0.2

Tabella 4.3: Parametri del test

È stato scelto di usare un insieme di parametri piuttosto ridotto per evidenziare eetti di drift comunque presenti con probabilità crescente con l'aumentare della dimensionalità del problema.

Dalla gura 4.4 si nota una forte discrepanza fra i risultati dei vari test: • GA è fortemente depressa, a causa del drift genetico.

• NGA è l'algoritmo che va a convergenza più spesso nelle prime genera-zioni. La scelta del modello iniziale inuenza il successo dell'ottimizza-zione, sebbene in maniera più limitata del GA. Ciò determina la forte depressione della curva nelle ultime generazioni.

• CompGA, CataGA Le curve, sebbene con uno scarto signicativo fra il numero di test giunti a convergenza ad una data generazione, ma-nifestano comportamenti simili. Entrambe mostrano una grande capa-cità esplorativa della funzione, ma di contro risentono di una limitata capacità di convergenza.

Figura 4.4: Confronto fra le curve cumulative dei diversi algoritmi • DAGA il daga risulta essere una combinazione degli aspetti

miglio-ri delle due curve precedenti: ha un'elevata capacità esplorativa senza però deprimere eccessivamente la velocità di convergenza. Ciò è evi-denziato dal fatto che non risente di drift e giunge a convergenza nella quasi totalità dei casi.

Le nuove funzioni generano nuove soluzioni uniformemente distribuite sul-lo spazio dei modelli. Ciò comporta che il numero di modelli totale valutato, mostrato in gura 4.5, sia maggiore rispetto al numero di modelli valutato da un GA lanciato con gli stessi parametri. Ciononostante le curve CompGA e DAGA mostrano un numero medio (mediato sul numero di test) di modelli generati inferiore rispetto alle altre curve, a causa della maggiore velocità di convergenza. In altri termini, la maggiore quantità di tentativi a convergen-za in un numero limitato di generazioni ha fatto sì che il numero totale di individui generati sia notevolmente inferiore, a causa dell'uscita anticipata dalle iterazioni dell'algoritmo.

Figura 4.5: Numero medio di modelli generati dai vari algoritmi

Figura 4.6: Errore medio degli algoritmi

La gura 4.6 è conseguenza dei dati della gura 4.4: il maggiore numero di test falliti per le curve GA, ed in misura minore NGA e CataGA, inuiscono sui valori medi del valore della funzione oggetto del cromosoma migliore della popolazione in una data generazione. Pertanto le curve corrispondenti alle

funzioni sopracitate hanno valori peggiori.

# di test a convergenza per GA 32 # di test a convergenza per NGA 61 # di test a convergenza per CompGA 93 # di test a convergenza per CataGA 75 # di test a convergenza per DAGA 99 # di medio di modelli generati per GA 2467 # di medio di modelli generati per NGA 1669 # di medio di modelli generati per CompGA 1384 # di medio di modelli generati per CataGA 1665 # di medio di modelli generati per DAGA 1399

Schwefel 4d

Nell'ottica di analizzare in maniera approfondita gli algoritmi in esame è stato eseguito un ulteriore test su una funzione Schwefel a 4 dimensioni. L'aumento della dimensione aumenta la complessità dell'inversione in maniera più che lineare, rendendo più evidenti le dinamiche ed i comportamenti propri di ogni algoritmo.

Parametri valori Dimensione del problema 4 # Popolazione iniziale 76 # Sottopopolazioni 2 # Massimo di generazioni 700 Tasso di selezione 0.8 Parametri DAGA # Rimpiazzi 5 probabilità catastrofe 0.2

Tabella 4.5: Parametri del test

Anche in questo caso i parametri scelti sono estremamente ridotti per il problema in esame. Si può notare in tabella 4.5 come rispetto al caso 2d (tabella 4.3) i parametri siano stati incrementati di un fattore ben maggiore a 2.

La gura 4.7 evidenzia le dierenti proprietà delle funzioni esaminate: • GA In 31 casi su 100 si osserva una convergenza verso il minimo

glo-bale dell'algoritmo estremamente rapida. Ciò probabilmente è dovuto ad una scelta favorevole dei modelli costituenti la popolazione iniziale, ovvero alla generazione di un modello nella valle del minimo globale durante le prime generazioni dell'algoritmo. In tutti gli altri casi si as-siste ad un fenomeno di drift che inibisce totalmente le sue potenzialità esplorative.

• NGA Anche in questo caso si osserva una dinamica sostanzialmen-te uguale alla curva corrispondensostanzialmen-te al GA. Si nota un miglioramento marginale dovuto ad una limitata capacità di far fronte al drift genetico.

Figura 4.7: Confronto fra le curve cumulative dei diversi algoritmi • CompGA Ha una velocità di convergenza estremamente limitata, ma

la grande capacità esplorativa garantisce una crescita costante della curva soprattutto sulle ultime generazioni. L'algoritmo non risente di drift genetico, ma impiegherebbe un numero di generazioni molto grande per giungere a convergenza su tutti i test.

• CataGA La curva ha una buona velocità di convergenza sulle prime generazioni. Nelle generazioni successive ha zone a derivata nulla per periodi prolungati. Ciò probabilmente è dovuto a generazioni in cui non avvengono catastro. In questi intervalli l'algoritmo si comporta in maniera analoga ad un NGA, e pertanto è soggetto a forti rallentamenti. • DAGA il daga risulta essere una combinazione degli aspetti migliori delle due curve precedenti: ha un'elevata capacità esplorativa (come CompGA) senza però deprimere eccessivamente la velocità di conver-genza (come CataGA).

Figura 4.8: Numero medio di modelli generati dai vari algoritmi Come nel caso 2d è ben evidenziata la capacità del DAGA di giungere a convergenza: tale fatto permette all'algoritmo di terminare dopo poche iterazioni, valutando quindi pochi modelli.

CompGA ha un comportamento analogo a DAGA nelle prime iterazioni, discostandosi da questo quasi subito a causa della sua incapacità di giungere a convergenza.

Figura 4.9: Errore medio degli algoritmi

Come nel caso precedente il DAGA ha una maggiore capacità esplorativa, che comporta un miglior tness medio dei cromosomi migliori.

# di test a convergenza per GA 31 # di test a convergenza per NGA 38 # di test a convergenza per CompGA 36 # di test a convergenza per CataGA 51 # di test a convergenza per DAGA 98 # di medio di modelli generati per GA 3000 # di medio di modelli generati per NGA 2836 # di medio di modelli generati per CompGA 4448 # di medio di modelli generati per CataGA 2609 # di medio di modelli generati per DAGA 2125

4.1.4 Analisi delle Performances del DAGA su funzioni

analitiche

Appurata la maggiore ecienza del DAGA rispetto alle singole funzioni che lo compongono, si è scelto di testare l'algoritmo su dierenti funzioni oggetto, per valutarne l'ecienza su topologie con dierenti specicità.

Le ottimizzazioni sono state confrontate con un NGA, avente gli stessi parametri del DAGA, e con un MCA, essendo il DAGA generato a partire da questi due approcci metaeuristici.

L'algoritmo MCA non sarebbe confrontabile con gli altri algoritmi scelti, non avendo una struttura algoritmica iterativa. Per ovviare a questo pro-blema è stato usato un algoritmo iterativo che, ad ogni ciclo, opera come un MCA con un numero di soluzioni generate pari al numero di cromosomi generato dal DAGA nella generazione corrispondente.

Ackley

La funzione di Ackley è una funzione multimodale ben ottimizzabile tramite GA. La topologia indotta dalla funzione sullo spazio dei modelli è costitui-ta da un insieme di minimi di valore decrescente con la discostitui-tanza dal minimo globale. Inoltre gli intorni convessi del minimo globale assumono valori forte-mente decrescenti verso il centro. Tali fatti rendono l'esplorazione dei modelli estremamente direzionata verso il minimo globale. A causa di ciò è stato scel-to un insieme di parametri molscel-to limitascel-to per le ottimizzazioni. In tabella 4.7 sono riportati i parametri dei test.

Parametri 2d 3d 4d 10d Dimensione del problema 2 3 4 10 # Popolazione iniziale 8 10 12 21 # Sottopopolazioni 2 2 2 3 # Massimo di generazioni 100 100 100 150 Tasso di selezione 0.8 0.8 0.8 0.8 Parametri DAGA # Rimpiazzi 1 1 1 1 probabilità catastrofe 0.2 0.2 0.2 0.2

Tabella 4.7: Parametri del test

Le curve cumulative in gura 4.10 evidenziano un risultato atteso: la maggiore capacità esplorativa del DAGA permette in molti test di giungere a convergenza più rapidamente, anche a causa del grande bacino di attrazione del minimo globale. Ciò comporta una maggiore velocità di convergenza del DAGA rispetto al NGA. Il NGA giunge a convergenza in quasi tutti i casi. Il MCA ha trovato il minimo globale in un solo caso su 50 in dim = 2. Ciò è dovuto alla mancanza di memoria nella fase di esplorazione dell'algoritmo. I risultati dell'inversione sono riportati in tabella 4.8.

2d 3d

4d 10d

Figura 4.10: Curve incrementali di convergenza per la funzione di Ackley

Risultati 2d 3d 4d 10d

# di test a convergenza per DAGA 50 50 50 50 # di test a convergenza per NGA 49 49 49 49 # di test a convergenza per MC 1 0 0 0 Tempo medio di convergenza per DAGA 201 ms 267 ms 322 689 ms Tempo medio di convergenza per NGA 198 ms 260 ms 232 457 ms Tempo medio di convergenza per MC 7 ms 9 ms 8 ms 31 ms

Eggholder

La funzione Eggholder è denita solo per dimensione 2, pertanto l'analisi è stata limitata solo all'ottimizzazione 2d. L'ottimizzazione è complicata da diversi fattori:

• la grande estensione del dominio della funzione, che rende più complessa l'esplorazione dello spazio dei modelli,

• il posizionamento al bordo del minimo globale: gli algoritmo genetici individuano più facilmente soluzioni localizzate all'interno dell'insieme di denizione,

• i grandi valori di gradiente assunti dalla funzione in prossimità del mini-mo globale: il bacino di attrazione (ovvero il più grande intorno conves-so contenente il minimo globale) è piuttosto ridotto, e di conseguenza di dicile localizzazione.

A seguito di tali osservazioni sono stati scelti dei parametri molto maggiori rispetto a quelli usati per la funzione di Ackley, come evidenziato dalla tabella 4.9.

Parametri valori Dimensione del problema 2 # Popolazione iniziale 20 # Sottopopolazioni 2 # Massimo di generazioni 300 Tasso di selezione 0.8 Parametri DAGA # Rimpiazzi 2 probabilità catastrofe 0.2

Tabella 4.9: Parametri del test

I risultati mostrati in gura 4.11 evidenziano la complessità della topo-logia su cui è stata eseguita l'inversione. La velocità di convergenza del DAGA risulta essere molto elevata, a causa della buona capacità esplorativa dell'algoritmo, che giunge a convergenza in ogni test eettuato.

Figura 4.11: Curve incrementali di convergenza per la funzione eggholder Il NGA fallisce l'ottimizzazione in 43 casi su 50, a causa di fenomeni di drift genetico, causati dai fattori analizzati in precedenza, come evidenziato dalla tabella 4.10, in cui sono riportati i risultati dell'inversione.

Anche in questo caso il MCA non raggiunge mai il minimo globale. # di test a convergenza per DAGA 50

# di test a convergenza per NGA 7 # di test a convergenza per MC 0 Tempo medio di convergenza per DAGA 542 ms Tempo medio di convergenza per NGA 643 ms Tempo medio di convergenza per MC 16 ms