Studio dell'applicazione di Algoritmi Genetici in problemi di inversione sismica non lineare

UNIVERSITÀ DEGLI STUDI DI PISA

DIPARTIMENTO DI SCIENZE DELLA TERRA

Corso di Laurea Magistrale in Geofisica di Esplorazione ed Applicata

Tesi di Laurea Magistrale

Studio dell'applicazione di Algoritmi Genetici in problemi di inversione

sismica non lineare

Candidato:

Matteo Caporal

Relatore

Prof. Alfredo Mazzotti

Correlatore

Dott. Angelo Sajeva

Controrelatore:

Prof. Francesco Giammanco

Indice

Capitolo 1: Introduzione p.1

Capitolo 2: Il Problema Inverso p.3

2.1 Introduzione p.3

2.2 Problemi inversi non lineari: metodi locali p.11

Capitolo 3: I Metodi Monte Carlo p.17

3.1 Introduzione . p.17

3.2 Metodi Monte Carlo ed ottimizzazione p.19

3.2.1 Algoritmi Genetici p.21

3.2.1.1 Selezione p.23

3.2.1.2 Ricombinazione p.30

3.2.1.3 Mutazione p.32

3.3 Metodi Monte Carlo, inferenza Bayesiana e ricampionamento p. 32 3.3.1 Neighborhood Algorithm per il ricampionamento p.33

Capitolo 4: Ottimizzazione funzionale tramite Algoritmi Genetici p.37

4.1 Introduzione . p.37

4.2 Simulazione . p.40

Capitolo 5: Inversione sismica non lineare tramite Algoritmi Genetici p.54

5.1 Introduzione . p.54

5.2 Influenza dei parametri di controllo sulla convergenza p.59 5.3 Influenza dei parametri di controllo sulla convergenza p.66

Capitolo 6: Conclusioni p.71

Bibliografia . p.73

1

Capitolo 1

Introduzione

L’obiettivo primario che ci prefissiamo nel compiere un’operazione di inversione è la minimizzazione di una funzione d’errore, che spesso dal punto di vista pratico costituisce una qualche misura dello scarto fra i dati sperimentali ottenuti ed i dati da noi predetti. Procedure di ottimizzazione che dipendono da approssimazioni del gradiente, linearizzazioni o da inversioni matriciali possono essere soggette ad instabilità numeriche causate dal mal-condizionamento del problema in esame o da fallimenti nella convergenza, a meno che il modello di riferimento non sia adeguatamente vicino alla soluzione vera. Ci potremmo ad esempio trovare in condizioni sfavorevoli quando la funzione oggetto è particolarmente irregolare, multimodale, non liscia o discontinua.

Nello specifico, il presente lavoro di tesi si pone come obiettivo lo studio dell’applicabilità degli Algoritmi Genetici (AG) all’inversione della forma d’onda sismica, che costituisce uno dei problemi geofisici identificabili come problemi di ottimizzazione multiparametrici non lineari.

Gli Algoritmi Genetici sono metodi di inversione globale che rientrano nella categoria dei metodi Monte Carlo. Essi consistono essenzialmente nelle tre semplici operazioni di selezione, ricombinazione e mutazione, che coinvolgono: la generazione di numeri casuali allo scopo di creare una popolazione di possibili soluzioni, lo scambio di informazioni tra le diverse possibili soluzioni e la parziale modifica casuale delle stesse. Da tali operazioni deriva l’analogia con la genetica.

2 La scelta degli intervalli entro cui generare la popolazione iniziale e la scelta dei parametri che regolano le tre operazioni appena descritte sono di importanza cruciale per un efficiente funzionamento dell’algoritmo.

Si sono studiati in un primo momento gli effetti che tali parametri hanno sulla ricerca del minimo di funzioni analitiche, ed in un secondo momento si è passati all’inversione sismica vera e propria ottenendo dei risultati interessanti, specie se utilizzati come modello di partenza per un algoritmo di inversione locale.

Le funzioni analitiche scelte per sperimentare l’efficienza dell’AG per differenti combinazioni di parametri di controllo, appartengono a tre differenti insiemi emblematici di funzioni:

- Funzioni puramente convesse (paraboloide)

- Funzioni fortemente multimodali (funzione di Rastrigin, funzione di Schwefel) - Funzioni piatte (funzione di Branin)

L’interesse verso lo studio di questi tipi di funzioni, risiede nel fatto che si presume che la funzione oggetto sismica presenti caratteristiche analoghe ad una certa combinazione delle stesse. Da un punto di vista pratico studiare il comportamento della funzione oggetto sismica avvalendosi anche delle analogie con le funzioni analitiche si rivela molto conveniente. Infatti, a livello computazionale, la risoluzione del problema diretto analitico è estremamente meno dispendiosa della risoluzione del corrispettivo sismico. Come vedremo, la funzione oggetto sismica, nei casi studiati, mostra un comportamento intermedio tra quello di una funzione piatta e di una funzione multimodale.

La verifica delle potenzialità e dei limiti della procedura applicata all’inversione della forma d’onda sismica è effettuata utilizzando dati sintetici. Il modello vero di riferimento è una porzione del ben noto modello Marmousi, da cui è generato il dato osservato di riferimento mediante la risoluzione del problema diretto. La funzione oggetto è la norma L2 degli scarti tra dato osservato e dato predetto dalla risoluzione del problema diretto.

Il gran numero di modelli prodotti dall’Algoritmo Genetico ci permette inoltre di operare un ricampionamento per il calcolo della densità di probabilità a posteriori approssimata, seguendo un approccio di tipo Bayesiano. Ciò non richiede ulteriori soluzioni del problema diretto, ma dal nuovo ensemble ricampionato siamo in grado di ottenere un insieme di ulteriori informazioni che il semplice modello migliore non sarebbe in grado di fornirci.

3

Capitolo 2

Il Problema Inverso

2.1 Introduzione

Dall'analisi dei dati sperimentali vengono sviluppate teorie fisiche, così come le teorie fisiche predicono i risultati degli esperimenti. Il confronto fra i risultati predetti ed i dati osservati permette di migliorare o, in presenza di incongruenze inaccettabili, di rigettare una teoria. Il problema legato alla predizione dei risultati delle misure è detto problema diretto, mentre si parla di problema inverso quando, mediante dati sperimentali, ci si propone di dedurre i parametri e le relazioni matematiche mediante cui è possibile esprimere la teoria presa in considerazione.

Da un punto di vista pratico, ciò corrisponde ad ammettere l'esistenza di una funzione, non necessariamente esplicita, che associa i punti m dello spazio dei parametri M (anche detto spazio dei modelli) a i punti d dello spazio dei dati D. Quest'ultima può essere espressa tramite la relazione

4 dove, con d = g(m), si vuole esprimere la relazione di = gi(m1, m2, ...) per i = 1, 2, ... .

L'operatore g() (solitamente non lineare) è detto operatore diretto e costituisce il modello matematico del sistema preso in esame. Ammessa l'invertibilità dell'operatore g(), potremo esprimere il problema inverso associato nella forma:

m = g-1 (d) (Problema Inverso) (2.2)

Figura 2.1

Nella fisica deterministica, il problema diretto ammette un'unica soluzione. In generale però il valore predetto non sarà mai identico al valore osservato sia a causa delle incertezze nelle misure che a causa delle imperfezioni e delle approssimazioni del modello matematico.

Si è scelto pertanto di sviluppare questa breve introduzione ai problemi inversi nella formulazione di Tarantola e Vallette [1,2] ritenendola la più completa ed elegante. Si tratta di una formulazione a stampo Bayesiano: essa si basa sulla convinzione che la forma più generale per descrivere un qualsiasi stato di informazione sia definire una densità di probabilità ad esso associata. La relazione esatta (2.1) è sostituita quindi da una correlazione probabilistica tra i parametri m del modello ed i parametri d delle osservabili (Figura 2.2).

5 Figura 2.2

Vi è una vasta produzione bibliografica sui fondamenti della statistica e sull'interpretazione del concetto di probabilità. Prima di procedere con la trattazione teorica dell'approccio proposto da Tarantola e Vallette, è utile distinguere le differenti interpretazioni ed in particolare l'interpretazione Bayesiana che costituisce il suo punto di partenza. La seguente è una delle classificazioni proposte in letteratura [3,4]:

1) Interpretazione classica

L’interpretazione detta “classica” della probabilità fu elaborata da Pierre Simon de Laplace (1749-1827) durante la prima metà del XVIII secolo. Nel quadro di un'impostazione prettamente epistemica, Laplace definisce la probabilità come il rapporto fra il numero dei casi favorevoli di un evento e il numero dei casi possibili. Questa definizione rispecchia la sua idea di probabilità come determinata in parte dalla conoscenza ed in parte dall’ignoranza: se, ad esempio, sappiamo che su tre eventi se ne verificherà uno, ma non siamo a conoscenza di alcun motivo che ci porti a ritenere che uno debba accadere a preferenza degli altri, saremo portati a ritenerli ugualmente possibili. Circa un secolo più tardi i frequentisti rifiutarono il punto di vista epistemico proposto da Laplace per abbracciare una visione empirica della probabilità, in base alla constatazione che in molti casi analizzati dalla scienza è impossibile individuare l'insieme dei casi possibili rispetto all'accadimento di un fenomeno, il che rende inapplicabile la definizione classica.

6 2) Interpretazione frequentista

La meglio conosciuta definizione di probabilità secondo l'interpretazione frequentista è associata al nome di Richard von Mises (1883-1953). Tale teoria ritiene che la probabilità sia una caratteristica dei fenomeni empirici che si esprime attraverso la frequenza con cui i fenomeni favorevoli si presentano all’osservazione. Suo oggetto sono dunque i fenomeni ripetibili. La probabilità di occorrenza di un dato evento A è definita come il limite della frequenza relativa nA / n, per n che tende ad infinito:

P(A) = (2.3)

dove nA è il numero di fenomeni favorevoli A, mentre n è il numero delle prove

effettuate.

Un punto fondamentale ed al contempo critico della teoria è il fatto che per prove si intendono ripetizioni dell'esperimento sotto circostanze identiche. Inoltre, secondo von Mises le successioni probabilistiche devono soddisfare requisiti precisi: devono essere infinite, tendere ad un limite ed essere casuali. Il frequentismo di von Mises solleva quindi problemi di applicabilità, limitando l’uso della probabilità ai collettivi infiniti, nonché casuali e generati in condizioni e circostanze molto rigide.

3) Interpretazione Bayesiana

L'interpretazione Bayesiana deve il suo nome a Thomas Bayes [5], che per primo formulò il principio di probabilità inversa, meglio conosciuta attualmente con il nome di probabilità Bayesiana [6]. Nonostante in linea di principio l'approccio Bayesiano possa essere suddiviso in due classi distinte, un elemento comune ad entrambe è l'interpretazione della probabilità come un grado di credenza, esprimente il supporto (induttivo) a favore di un’ipotesi, assegnato in base all’evidenza disponibile.

Le due classi dell'interpretazione Bayesiana della probabilità si distinguono per l'approccio essenzialmente differente alla teoria: da una parte l'approccio logico-oggettivo, dall'altra un approccio di tipo soggettivo. Secondo l’interpretazione logica, la probabilità ha significato epistemico (si faccia riferimento ad esempio a Keynes [7] per una trattazione più completa dell'argomento), e viene definita come una relazione logica fra gli enunciati esprimenti un’ipotesi e l'insieme di dati sperimentali portati a supporto di tale ipotesi. Esprimendo una relazione logica, la probabilità assume

7 pertanto carattere oggettivo.

Indubbio merito di Keynes nello sviluppo dell'approccio Bayesiano-logico alla probabilità è l’aver posto l’accento sulla questione del peso degli argomenti [8]. Quest’ultimo varia, come la probabilità, a seconda dell’ammontare dell’evidenza disponibile. Mentre però la probabilità dipende dal rapporto fra l’evidenza favorevole e quella contraria, il peso aumenta all’aumentare dell’evidenza rilevante presa nel suo complesso.

Secondo l'interpretazione soggettiva, la probabilità è definita come un grado di credenza soggettivo, si faccia riferimento ad esempio a Ramsey [9] per una trattazione più completa dell'argomento. Ramsey sostituisce le relazioni logiche poste da Keynes alla base della probabilità con le opinioni che il soggetto nutre circa l’accadimento degli eventi. Egli definisce la probabilità dotandola di un fondamento quasi psicologico, anziché logico, e postula che credenze ed opinioni siano misurabili. L'unica restrizione nell'utilizzo delle probabilità è la loro consistenza: gli assiomi della teoria delle probabilità non possono essere violati.

Veniamo dunque alla teoria di Tarantola e Vallette, che, come già accennato si rifà ad un approccio di tipo Bayesiano (logico). Siano M e D rispettivamente lo spazio dei modelli m e lo spazio dei dati d, ad entrambi è associata (inizialmente) una densità di probabilità omogenea, μM (m) e μD (d) (ndr. Bayes usa il termine non-informativa al

posto di omogenea). I punti dei due spazi si presentano nella forma m = (m1, m2, ...) e

d = (d1, d2, ...).

Si indichi con la notazione Θ(d,m) la densità di probabilità congiunta che descrive la correlazione tra parametri e dato sperimentale, tenendo conto delle incertezze intrinseche alla teoria dovute ad una parametrizzazione imperfetta od a lacune nelle informazioni di partenza. In altre parole, Θ(d,m) descrive le informazioni teoriche a nostra disposizione:

Θ(d,m) = θ(d|m) μM(m) (densità di probabilità teorica) (2.4)

dove θ(d|m) rappresenta la densità di probabilità condizionata di d, per ogni possibile modello m. Si noti che l'espressione (2.4) ci assicura che la probabilità marginale per m è omogenea, la probabilità marginale per d può non esserlo.

Esempio: Θ(d,m) = δ(d - g(m)) μM(m)

8 È opportuno a questo punto definire sullo spazio D un'ulteriore densità di probabilità ρD(d) che descrive lo stato delle informazioni acquisite sui parametri d delle osservabili.

Ciò ci permette di tenere conto delle incertezze cui le misure sono soggette. Con un ragionamento analogo è utile definire sullo spazio M, quando possibile, una densità di probabilità ρM(m) che rappresenta le informazioni ottenute indipendentemente dai

risultati delle misure (informazioni a priori).

Le informazioni a disposizione sui parametri dei modelli e sui parametri delle osservabili possono quindi essere descritte, nello spazio DxM, dalla densità di probabilità congiunta:

ρ(d,m ) = ρM(m) ρD(d) (densità di probabilità sperimentale) (2.5)

D'ora in avanti, ci riferiremo a tale densità di probabilità congiunta con il nome di densità di probabilità a priori; al contrario di Θ(d,m), che descrive le informazioni teoriche, ρ(d,m) descrive le informazioni sperimentali in nostro possesso.

I due stati di informazione descritti si combinano a formare lo stato di informazione a posteriori, avremo:

σ = k ρ Θ

μ (2.6)

dove k è una costante di normalizzazione. Una volta definita tale densità di probabilità sullo spazio DxM, le informazioni a posteriori sullo spazio dei modelli e nello spazio delle osservabili (σM e σD) sono ottenute rispettivamente dal calcolo dei seguenti

marginali:

σM(m) = (2.7)

σD(d) = (2.8)

L'equazione (2.6) risolve un problema estremamente generale. I problemi inversi corrispondono al caso particolare in cui gli spazi D ed M hanno significati fisici

9 sostanzialmente differenti ed in cui vi è l'interesse a tradurre le informazioni dallo spazio D delle osservabili allo spazio M dei parametri. Ciò significa che l'informazione di nostro interesse nella risoluzione di un problema inverso, è esattamente quella contenuta nella relazione (2.7). Potremmo scrivere più esplicitamente:

σM(m) = k ρM(m)

ρ

μ (2.9)

da cui è utile definire la funzione di verosimiglianza L(m):

L(m) =

μ (2.10)

che fornisce una misura di quanto un modello m sia adatto alla descrizione del dato sperimentale di riferimento.

L'equazione (2.9) è LA soluzione generale del problema inverso e per definizione ne sono garantite esistenza ed unicità. L'esistenza della soluzione garantisce che la stessa non è identicamente nulla. Se ci trovassimo in tale caso sfavorevole, ciò indicherebbe una evidente e sostanziale incompatibilità tra informazioni teoriche ed informazioni sperimentali. L'unicità della soluzione è diretta conseguenza dell'unicità della coniugazione di diversi stati di informazione. σM può tuttavia presentare diverse

criticità dimostrandosi ad esempio non-normalizzabile o multimodale, ma l'informazione stessa è univocamente definita.

Esprimere la soluzione del problema inverso in forma di densità di probabilità, pur costringendo ad una rappresentazione meno triviale e più macchinosa del sistema, rende il risultato dell'inversione più generale e più ampiamente maneggevole:

- in alcuni casi ad esempio ci sarà utile conoscere quale sia la probabilità che accada un evento con caratteristiche ben determinate, ovvero quale sia la probabilità che un modello m appartenga ad una data regione A ⊆ M, sottoinsieme dello spazio dei modelli. Nella formulazione scelta, ciò si traduce nel calcolo dell'integrale

10

P(A) = (2.11)

Esso può essere calcolato in forma analitica per problemi a poche dimensioni o mediante metodi di campionamento Monte Carlo se il numero di gradi di libertà del sistema è particolarmente alto;

- nel caso in cui M è uno spazio lineare e la densità di probabilità σM è

riconducibile ad una distribuzione Gaussiana, il modello medio <m> potrebbe essere d'interesse:

< m > = (2.12) Allo stesso modo è interessante studiare la matrice di covarianza:

= (2.13)

ed eventualmente confrontarla con la matrice di covarianza a priori per valutare di quanto si sia ridotta l'incertezza iniziale;

- per un numero esiguo di parametri dello spazio dei modelli ed un'espressione di σM non troppo complessa e dispendiosa (a livello di tempo di calcolo), è

possibile definire una griglia sullo spazio dei modelli e calcolare σM ovunque al

suo interno, allo scopo di analizzare e discutere le informazioni così ottenute sui parametri del modello.

Se invece il numero di parametri è grande (indicativamente > 10) e σM è

ragionevolmente semplice da calcolare, l'esplorazione sistematica dello spazio dei modelli può essere vantaggiosamente sostituita da un'esplorazione di tipo random (Monte Carlo) da cui eventualmente ricavare un'approssimazione di σM stessa su tutto lo spazio.

11

2.2 Problemi Inversi non lineari: metodi locali

Si consideri ora, per semplicità, il problema inverso descritto dalle relazioni (2.1) e (2.2). L'operatore g è detto lineare se soddisfa le seguenti proprietà:

g(m1 + m2) = g(m1) + g(m2) (2.14)

g(λm) = λ g(m) (2.15)

Un problema inverso, quindi, è definito come lineare se è lineare l’operatore g(). In tal caso, la relazione (2.1) può essere espressa nella forma compatta:

d = g m

dove g è una matrice n x m, mentre d ed m sono vettori colonna rispettivamente di dimensioni n ed m. Diversamente, un problema inverso si dice non lineare quando è esprimibile come un sistema di equazioni di cui almeno una è non lineare. Il problema quindi non può essere espresso secondo la notazione matriciale compatta sopra descritta, bensì secondo la più generica notazione:

d = g(m)

I problemi inversi trattati in questo lavoro di tesi sono problemi inversi non lineare, come sono non lineari i problemi trattati generalmente in ambito geofisico. In questa sezione l’attenzione sarà rivolta brevemente alla risoluzione di questi ultimi tramite approcci che si contraddistinguono per l'uso di metodi di inversione di tipo locale. Il seguente capitolo sarà invece dedicato alla risoluzione di problemi inversi non lineari mediante approcci di tipo globale, essendo questi ultimi i metodi di inversione scelti per affrontare il presente lavoro di tesi.

12 L'impianto matematico che caratterizza i metodi di inversione di tipo locale si basa essenzialmente sul metodo di Gauss-Newton [10]. Tale metodo è basato su un approccio di tipo iterativo. Come primo passo, viene scelta una soluzione di prova m0 e,

a partire da detta soluzione, viene calcolato il dato predetto:

= g(m0). (2.16)

Ricordiamo che i nostri dati sono l'espressione di un modello vero sommato ad un certo rumore e:

dobs = g(mtrue) + e (2.17)

Nell'ipotesi che g() sia continua e differenziabile, si può sviluppare, in un intorno del punto m0, un'approssimazione lineare di g utilizzando l'espansione in serie di Taylor

troncata al primo ordine:

g(mtrue) ≅ g(m0) + J(m)|m0 δm (2.18)

dove δm = mtrue - m0 e J(m) è la matrice Jacobiana di dimensioni NxM dell'operatore g,

ovvero J(m) = Da (2.17) e (2.18) avremo che dobs = g(m0) + + e (2.19)

13 da cui

= dobs - = δm + e (2.20)

L'obiettivo è quello di ottimizzare l'errore di predizione e, e quindi di trovare il minimo della funzione:

e = = dobs - δm (2.21)

Riconosciamo in quest'ultima espressione un problema lineare. La soluzione ai minimi quadrati di quest'ultimo sarà pertanto data dal sistema delle equazioni normali di Gauss:

δm = ( J(m)T J(m) )-1 J(m)T (2.22)

Tuttavia δm non costituisce la soluzione ma rappresenta unicamente una variazione al

modello di prova m0 che consente di raggiungere un miglior adattamento ai dati

sperimentali. Di conseguenza è necessario reiterare il processo per g(m0 + δm), in tal

modo potremo migliorare ulteriormente il nostro modello di riferimento.

Perciò lo schema di implementazione dell'algoritmo di Gauss-Newton segue i seguenti passi:

1) Sia k = 0;

2) Scegliamo una soluzione di prova mk e calcoliamo il relativo valore = g(mk);

3) Calcoliamo = - ;

14 5) Ricaviamo il valore di δm minimizzando la funzione d'errore;

6) Sia k = k+1, aggiorniamo il modello di prova mk = mk-1 + δm e ripartiamo dal

passo 2 finché la soluzione non è ritenuta accettabile.

Rimangono due punti da chiarire che riguardano: il calcolo della matrice Jacobiana e i criteri in base ai quali troncare la procedura iterativa. Quando è disponibile una formula analitica esplicita per g(m), queste derivate possono essere calcolate analiticamente o mediante un programma di calcolo. Spesso g(m) non ha, tuttavia, una formulazione analitica oppure l'operatore che risolve il problema diretto è implementato in un software di cui non è disponibile il codice sorgente. In questi casi è quindi necessario ricorrere al calcolo delle derivate parziali mediante uno schema alle differenze finite.

Esistono vari metodi alle differenze finite per il calcolo della derivata parziale dell'i-esimo dato predetto rispetto al j-dell'i-esimo parametro del modello. Fra questi:

a) Metodo backward b) Metodo forward

c) Metodo delle differenze centrali

dove hj è l'incremento arbitrario sul j-esimo parametro. Lo schema presentato soffre

15 Una buona regola empirica per la scelta di h è h = , dove α è la precisione con cui è possibile calcolare g(m). I metodi presentati a titolo di esempio si basano su approssimazioni in serie di Taylor arrestate al primo ordine.

L'arresto delle iterazioni si basa essenzialmente su due criteri: le soluzioni smettono di cambiare significativamente o non vi è alcun miglioramento sostanziale nel fit dei dati sperimentali.

Un ulteriore affinamento dello schema di risoluzione del problema inverso non lineare con metodi locali consiste nell'approssimazione lineare di g utilizzando l'espansione in serie di Taylor troncata al secondo ordine. Avremo:

g (m0 + δm) ≈ g (m0 ) + ∇g (m0 )T δm + Hg(m0) m (2.23)

Dove ∇g(m0) rappresenta il vettore gradiente della funzione g() in m0 , mentre Hg(m0)

la rispettiva matrice Hessiana. La condizione necessaria affinché un punto x sia un minimo di una generica funzione f(x) che il gradiente di f in tale punto sia nullo. Pertanto, calcolando quest’ultimo in (m0 + δm) per g e trascurando il termine di ordine

superiore, si ottiene:

∇g(m0 + δm) ≈ ∇g(m0) + Hg(m0) δm (2.24)

Imponendo ∇g(m0 + δm) = 0 si arriva al seguente risultato:

∇ g(m0) = − Hg(m0) δm (2.25)

Anche in questo caso il sistema va risolto iterativamente e, come nel caso precedente, ad ogni iterazione si riduce l’approssimazione della soluzione. I due esempi appena descritti, costituiscono la struttura portante su cui si basano i metodi di inversione locali. L’uso di tali metodi nella risoluzione dei problemi inversi non lineari è vantaggiosa dal punto di vista computazionale in quanto, rispetto ai metodi puramente non lineari, richiede tempi di calcolo nettamente minori. La dipendenza da un modello iniziale di prova, invece, è lo svantaggio principale che caratterizza questi metodi, soprattutto quando la funzione oggetto da minimizzare presenta numerosi minimi locali. In queste circostanze, infatti, se il modello iniziale si trova nei pressi di

16 un minimo locale (si osservi Figura 2.3), la soluzione convergerà verso di esso rimanendovi intrappolata. Poiché tali metodi necessitano del valore del gradiente in vari punti della funzione oggetto, la continuità e la derivabilità di quest’ultima costituiscono un vincolo all’applicabilità degli stessi.

Figura 2.3

Queste complicazioni rendono poco affidabili i metodi di inversione locali nella soluzione di problemi inversi in cui le funzioni desiderate presentano numerosi punti critici e/o punti singolari. Inoltre procedure di ottimizzazione che dipendono da approssimazioni del gradiente, linearizzazioni o da inversioni matriciali possono essere soggette ad instabilità numeriche causate dal mal-condizionamento del problema in esame.

17

Capitolo 3

I Metodi Monte Carlo

3.1 Introduzione

Con l'espressione Metodi Monte Carlo, vengono in generale denominate tutte quelle tecniche che fanno uso di tecniche aleatorie artificiali (generate cioè da un calcolatore) per la risoluzione di problemi fisici o matematici.

Apparentemente questo non è un modo molto efficiente per trovare la soluzione di un problema, in quanto la procedura di campionamento simulato porta ad un risultato che è sempre affetto da errore statistico. Nella pratica però ci si trova spesso di fronte a situazioni in cui è particolarmente difficile, se non addirittura impossibile, utilizzare procedimenti numerici od analitici più tradizionali. In tali casi, i metodi Monte Carlo diventano l’unica alternativa disponibile.

L’applicazione di questi metodi non è limitata ai soli problemi di natura statistica, ma include tutti quei casi per cui è possibile riuscire a trovare un collegamento tra il problema in esame ed il comportamento di un particolare sistema aleatorio. Ad

18 esempio, il valore di un integrale definito, pur non essendo di certo una grandezza casuale, può essere calcolato anche mediante la generazione di numeri casuali.

Le basi teoriche del metodo Monte Carlo sono note da lungo tempo. Il primo esempio dell’impiego dei numeri casuali nella risoluzione di integrali definiti risale alla seconda metà del XVIII secolo ed è da attribuirsi a Georges-Luis Leclerc, conte di Buffon, matematico e naturalista francese. Egli delineò un metodo per il calcolo approssimato del valore di π. Tale procedura consiste nel lancio di un ago di lunghezza arbitraria su di un piano su cui sono tracciate linee parallele fra loro equidistanti. Si può dimostrare che la probabilità che l’ago cada intersecando una delle linee è inversamente proporzionale al valore di π.

Per oltre un secolo e mezzo esso fu però usato solo sporadicamente e soprattutto a fini didattici. La sua prima applicazione sistematica si è avuta solo nella prima metà degli anni ’40 a Los Alamos, ad opera dell’équipe di scienziati, guidata da Enrico Fermi, che sviluppò il progetto delle prime bombe atomiche.

Nello stesso periodo viene inoltre introdotto il termine Monte Carlo, che fa riferimento alla città del Principato di Monaco famosa per i suoi casinò ed, in particolare, alla roulette, uno dei mezzi meccanici più semplici per generare variabili aleatorie.

Dopo gli anni ’50 si è avuto un decisivo impulso nell’impiego del metodo mediante l’uso dei calcolatori, grazie ai quali esso è passato in pochi anni dal ruolo di curiosità matematica a quello di strumento indispensabile per la ricerca scientifica. Questo è avvenuto non solo perché i calcolatori permettono la rapida esecuzione dei lunghi calcoli che sono spesso necessari per ottenere un risultato soddisfacente, ma anche per la facilità con cui essi possono generare numeri casuali. Si rimanda al libro di Hammersley e Handscomb [11] per una interessante, seppur non recente, descrizione dei metodi Monte Carlo.

Attualmente si hanno applicazioni dei metodi Monte Carlo nei più svariati campi della ricerca, dalla fisica nucleare all’economia, dall’analisi funzionale alla meccanica quantistica. Le prime applicazioni di tali metodi nella geofisica risalgono alla seconda metà degli anni ’60 e sono da attribuirsi alla scuola sovietica e, pochi anni più tardi, al lavoro di Press [12, 13].

19

3.2 Metodi Monte Carlo ed ottimizzazione

L’obiettivo primario che ci poniamo nel compiere un’operazione di inversione è la minimizzazione di una funzione d’errore, che spesso dal punto di vista pratico costituisce una certa misura dello scarto fra i dati sperimentali ottenuti ed i dati da noi predetti. Procedure di ottimizzazione che dipendono da approssimazioni del gradiente o da inversioni matriciali possono essere soggette ad instabilità numeriche causate dal mal-condizionamento del problema in esame o da fallimenti nella convergenza a meno che il modello di riferimento non sia adeguatamente vicino alla soluzione vera. La funzione oggetto che sottoponiamo al processo di inversione potrebbe essere particolarmente irregolare, multimodale, non liscia o discontinua.

Siccome i metodi Monte Carlo funzionano campionando direttamente uno spazio dei parametri, non è richiesto che la funzione considerata sia liscia o continua né sono coinvolti processi numerici potenzialmente instabili, come ad esempio l’inversione matriciale. In questo senso i metodi Monte Carlo sono intrinsecamente stabili. Se il processo di ricerca casuale è inefficiente, la convergenza ad una soluzione ottima (od anche locale) sarà al più lenta, ma l’inversione comunque procederà.

Press [12] applicò un’inversione con metodi Monte Carlo alla determinazione di modelli terrestri utilizzando come dati: 97 periodi di oscillazioni libere della terra, i traveltimes di onde compressionali e di taglio ed infine la massa ed il momento d'inerzia della terra. L'inversione deriva la distribuzione delle velocità delle onde compressionali (α) e di taglio (β) e la densità (ρ) nella terra. Lo schema dell’algoritmo di Press è mostrata nella in Figura 3.1.

20 Poiché la potenza di calcolo è notevolmente cresciuta durante gli anni ‘80 e più sofisticati metodi di ricerca diretta si sono resi disponibili, le tecniche Monte Carlo sono tornate in voga nelle applicazioni geofisiche. In questa fase la nostra definizione di metodo Monte Carlo necessita di un aggiornamento sostanziale. La definizione più generale descrive questi ultimi come metodi che si avvalgono di un campionamento di tipo pseudocasuale per esplorare uno spazio dei parametri al fine di recuperare informazioni sulle incognite di interesse. L'importante cambiamento consiste nel fatto che la ricerca non deve più essere necessariamente uniforme. Il campionamento casuale a partire da distribuzioni multidimensionali particolarmente non uniformi è pertanto incluso nella definizione di un metodo Monte Carlo.

Ad esempio poniamo che, in un’inversione di tipo Monte Carlo, ad ogni parametro del modello è permesso di variare in un intervallo di ricerca predefinito (determinato a priori). Così per ogni parametro del modello mi, imponiamo mmin < mi < mmax.

All’interno di tale intervallo è tuttavia possibile scegliere di non generare il parametro a partire da una distribuzione uniforme U[0,1], ma di generarlo secondo altri tipi di distribuzioni, ad esempio secondo una distribuzione di tipo gaussiano G(μ, σ), centrata in un punto μ ragionevolmente scelto.

Nell’ambito dei metodi Monte Carlo applicati all’ottimizzazione funzionale, si collocano anche gli Algoritmi Genetici che sono alla base del metodo proposto in questo lavoro di tesi. Nel seguente paragrafo è possibile trovare una descrizione teorica del loro funzionamento.

21

3.2.1 Algoritmi Genetici

Gli Algoritmi Genetici (AAGG) fanno parte dei metodi di ottimizzazione di tipo globale che si propongono come alternativa ai metodi di ottimizzazione locale od a gradiente quando questi ultimi non sono applicabili.

Lo sviluppo originale dell’algoritmo è attribuibile a Holland [14] ed un ulteriore interessante approfondimento è presentato da Goldberg [15]. Analogamente agli altri metodi Monte Carlo, gli Algoritmi Genetici sono metodi non-lineari che sfruttano processi casuali e non richiedono informazioni sulle derivate delle funzioni da ottimizzare. Tuttavia, possono rivelarsi sensibilmente più efficienti di tecniche di inversione puramente casuali o di strategie di Random Walk [16].

La potenza degli Algoritmi Genetici risiede nel fatto che l’ottimizzazione è condotta mediante processi completamente stocastici. Essenzialmente, ciò significa che il meccanismo di esplorazione dello spazio dei modelli non segue un insieme deterministico di regole che forzano l’inversione in una direzione particolare predefinita. È comunque importante sottolineare che l’utilizzo di un processo stocastico non significa che la ricerca è condotta in modo totalmente casuale. Infatti, una delle caratteristiche più interessanti dell’algoritmo risiede nel fatto che procedure relativamente semplici, che fanno uso di sole decisioni casuali, possono produrre un meccanismo di ricerca particolarmente efficiente.

Nonostante le loro promettenti potenzialità, gli algoritmi di questo tipo sono stati applicati in ambito geofisico, ed in particolare nell’inversione delle forme d’onda, solo a partire dall’inizio degli anni ’90 [17,18].

Da un punto di vista pratico, l’algoritmo lavora simultaneamente con una popolazione di N individui che costituiscono un insieme di possibili soluzioni del nostro problema. Generalmente, la popolazione iniziale è creata tramite la generazione di numeri casuali entro un intervallo stabilito arbitrariamente a priori. A seconda del problema specifico in esame, una codifica binaria può essere preferibile rispetto ad una rappresentazione reale delle variabili o viceversa. Per ogni individuo viene calcolato il valore corrispondente della funzione oggetto, risolvendo il problema diretto associato, ed i migliori individui (modelli-soluzione) vengono confrontati e coinvolti nella formazione di una nuova generazione di soluzioni. Ciò avviene tramite le tre operazioni di Selezione, Ricombinazione (o Crossover) e Mutazione, da cui deriva l’analogia con la genetica. Questa procedura è ripetuta per un numero definito dall’utente di iterazioni (generazioni). Maggiori sono il numero N dei modelli ed il numero GM delle generazioni, migliore sarà l’esplorazione dell’algoritmo a discapito però della durata dell’inversione. In Figura 3.2 è presentata uno schema di base di un Algoritmo Genetico standard.

22

Figura 3.2

Recentemente è stata formulata una versione più sofisticata dell'AG che prevede una organizzazione a stampo regionale dell'insieme delle possibili soluzioni. Secondo questo modello regionale, la popolazione iniziale è suddivisa in diverse sottopopolazioni. Tali sottopopolazioni evolvono indipendentemente per un certo numero di generazioni (tempo di isolamento). Dopo il periodo di isolamento un certo numero di individui viene ridistribuito e scambiato tra le sottopopolazioni (migrazione). Secondo quanto riportato in letteratura [19, 20], l'implementazione parallela del modello regionale determina non solo una diminuzione sensibile del tempo di calcolo, ma anche una diminuzione del numero di valutazioni della funzione oggetto necessarie a raggiungere convergenza. Vedremo nei seguenti capitoli che i risultati ottenuti discordano con tali considerazioni.

Al contrario di molte altre tecniche di esplorazione di tipo Monte Carlo (come ad esempio il Simulated Annealing), che lavorano aggiornando continuamente un set di parametri specifico, gli AAGG operano su un insieme di set di parametri, ponendo

23 minor enfasi su ogni membro particolare. Essi sfruttano la struttura e le caratteristiche dei migliori modelli considerati utilizzandoli come base per lo sviluppo di un nuovo insieme di modelli, su cui verranno svolte le medesime operazioni iterativamente. Vale a dire che, pur rimanendo un algoritmo stocastico, un Algoritmo Genetico si avvale delle informazioni raccolte durante le precedenti iterazioni dello stesso, mantenendo così una memoria implicita senza essere proibitivo da un punto di vista computazionale.

Di seguito riportiamo un’analisi delle tre operazioni fondamentali dell’algoritmo, nell’implementazione di Pohlheim [20] utilizzata per il presente lavoro di tesi.

3.2.1.1 Selezione

Il primo passo dell’algoritmo è la selezione. Mediante differenti metodologie, alcuni individui appartenenti alla popolazione di partenza vengono chiamati a formare un nuovo insieme di modelli. A modelli che producono soluzioni più vicine a quella desiderata, verrà assegnata una maggiore probabilità di essere selezionati mentre minore probabilità di essere selezionati è assegnata ai modelli peggiori. Il tasso di selezione (selection rate) è un parametro dal valore arbitrario compreso tra 0 ed 1 che indica la frazione degli N elementi della popolazione presa in considerazione dalle operazioni successive alla selezione.

Una volta calcolato il valore della funzione oggetto per ognuno dei N individui tramite la soluzione del problema diretto, se ne ricavano i valori di fitness, che fungono da indicatori della bontà delle possibili soluzioni. L'operazione di assegnazione del fitness, detta operazione di ranking, avviene una volta ordinate le soluzioni dalla peggiore alla migliore e può essere sia lineare che non lineare, a discrezione dell’utente. Di seguito sono riportate, nei due casi distinti, le relazioni per l’assegnazione del valore di fitness di ciascun individuo, per una popolazione composta da N individui:

- Ranking lineare

fitness(i) = 2 – SP + 2 (SP - 1)

24 - Ranking non lineare

fitness(i) =

dove X è calcolato come la radice del polinomio:

0 = (SP - N) XN-1 + SP XN-2 + … + SP X + SP (3.3)

Un ulteriore parametro da impostare è quindi il parametro SP (pressione di selezione). Ad una maggiore pressione di selezione corrisponde una maggiore tendenza a scartare i peggiori risultati (Figura 3.3). Nel caso di un ranking di tipo lineare, sono ammessi valori di pressione di selezione compresi nell’intervallo [1,2] mentre, per un ranking di tipo non lineare, sono ammessi valori compresi nell’intervallo [1, N-2]. Se SP è impostata uguale a 1, ad ognuno degli individui è associato un valore di fitness identico.

25 Da un punto di vista formale [21], un metodo di selezione Ω è una funzione che trasforma una distribuzione di fitness s in una nuova distribuzione di fitness s’:

s’ = Ω(s, par_list) (3.4)

dove par_list è una lista (in generale opzionale) di parametri associati allo specifico metodo di selezione considerato. Tuttavia, siccome i metodi di selezione sono metodi stocastici, è opportuno parlare di distribuzione di fitness attesa:

s* = Ω*(s, par_list) = E[ Ω(s, par_list)] (3.5)

Si tenga presente che d’ora in avanti indicheremo con la lettera s minuscola le distribuzioni di fitness, con la lettera S maiuscola le rispettive cumulative, mentre le stesse lettere sottolineate indicheranno la natura continua delle medesime.

Una proprietà di questa operazione preliminare dell'AG, che ci permette di analizzare il comportamento dei diversi metodi di selezione al variare degli specifici parametri è l’intensità di selezione [22]. Tale misura descrive ragionevolmente la variazione del fitness medio della popolazione dovuta all’operazione di selezione. Nell’ambito della genetica delle popolazioni, il concetto di intensità di selezione è stato introdotto al fine di ottenere una misura normalizzata ed adimensionale che descrivesse il grado di esplorazione dello spazio dei modelli. L'idea è quella di misurare i progressi dovuti all’operazione di selezione a partire dal cosiddetto differenziale di selezione, ovvero la differenza tra il fitness medio della popolazione dopo e prima della selezione. L’intensità di selezione è definita dividendo il differenziale di selezione per la deviazione standard del fitness della popolazione, tale operazione garantisce l’adimensionalità desiderata.

Formalmente avremo che l’intensità di selezione I di un metodo di selezione Ω per la distribuzione (continua) di fitness s(f) è definita come segue:

I = (M* - M) / σ (3.6)

dove M è il fitness medio (atteso) della popolazione prima dell'operazione di selezione mentre M* è il fitness medio (atteso) dopo l'operazione di selezione:

26

M = (3.7)

M* = (3.8)

mentre con σ si denota la deviazione standard della distribuzione di fitness s(f) prima dell'operazione di selezione, definita come:

σ = (3.9)

È perciò evidente che l'intensità di selezione dipende ampiamente dalla distribuzione di fitness della popolazione iniziale. Allo scopo di confrontare gli effetti dei diversi metodi di selezione, è necessario restringere le prove ad una sola specifica distribuzione iniziale. Di seguito è presentata la trattazione teorica formulata da Blickle e Thiele [22] che propongono come distribuzione di fitness iniziale una distribuzione Gaussiana normalizzata. E' quindi possibile definire una nuova intensità di selezione, che chiameremo standardizzata, allo scopo di semplificarne lo studio.

L’intensità di selezione standardizzata I è il valore del fitness medio (atteso) della popolazione dopo l'applicazione del metodo di selezione Ω ad una distribuzione Gaussiana normalizzata G(0,1)(f) = 1/ * exp( - f2 / 2) :

IΩ = (3.10)

Si noti che questa definizione, così come quella adottata per l’intensità di selezione non standardizzata, può essere applicata se il metodo di selezione studiato è invariante per traslazione e gode inoltre della proprietà di invarianza di scala. Allo stesso modo tale definizione non ha corrispettivo nel caso di distribuzioni di fitness discrete, ma, per un numero abbastanza elevato di campioni, i risultati reali mostrano una coerenza soddisfacente con le conclusioni teoriche.

Segue una breve descrizione dei vari metodi di selezione implementati nell’algoritmo di Pohlheim, tra cui è possibile scegliere quale utilizzare in base al contesto specifico ed al problema in esame.

27 - Roulette Wheel Selection (RWS)

Ad ogni individuo è associata una porzione, proporzionale al proprio fitness, di una linea di lunghezza unitaria. Generato un numero casuale (RND) compreso tra 0 ed 1, viene selezionato l'individuo cui corrisponde il segmento che contiene il valore RND stesso (Figura 3.4). L'operazione è ripetuta ogni qual volta è necessario selezionare un individuo.

Figura 3.4

 Sia s(f) una distribuzione di fitness continua della popolazione. La distribuzione di fitness attesa dopo l’applicazione del metodo RWS (Ωr*) con assegnazione lineare del ranking, scelto il parametro SP, e l’intensità di selezione associata (per s(f) = G(0,1) ) sono: ΩR*(s, SP)(f) = s*(f) = (2 - SP) s(f) + S(f) s(f) (3.11)

I

 Sia s(f) una distribuzione di fitness continua della popolazione. La distribuzione di fitness attesa dopo l’applicazione del metodo RWS (Ωr*) con assegnazione non-lineare del ranking, scelto il parametro SP, e ricavatone il valore di X (relazione (3.3)), e l’intensità di selezione associata (per s(f) = G(0,1) ) sono:

Ωex*(s, X)(f) = s*(f) = N

s(f) X

S(f)

28

I

π

(3.14)

Si rimanda a [20] per tutte le dimostrazioni matematiche.

- Stochastic Universal Sampling (SUS)

Ad ogni individuo è associata una porzione, proporzionale al proprio fitness, di una linea di lunghezza unitaria. Sia Ns il numero totale degli individui da selezionare, un numero casuale (RND) compreso tra 0 ed 1/Ns è generato. Ns puntatori equispaziati (con spaziatura pari a 1/Ns) sono posizionati sulla linea a partire da RND. Gli individui cui corrispondono i segmenti che contengono i puntatori vengono selezionati (Figura 3.5). Rispetto alla RWS il presente metodo di selezione garantisce un'esplorazione più uniforme dello spazio delle soluzioni.

Figura 3.5

Da un punto di vista formale, i valori di intensità di selezione associati al metodo SUS, scelto il metodo di assegnazione del ranking ed il valore di SP sono analoghi a quelli ottenuti per il metodo RWS, nonostante l’applicazione del vincolo dovuto all’introduzione della barra rigida dei puntatori. Invece, è plausibile che la deviazione standard della distribuzione di fitness attesa diminuisca sensibilmente. Nel caso reale discreto potremmo al più aspettarci per SUS una intensità di selezione leggermente inferiore a quella associata a RWS per parametri identici.

29 - Tournament Selection (TOUR)

Sia Ns il numero totale degli individui da selezionare. Ogni individuo selezionato è il migliore tra t individui sorteggiati casualmente. Il parametro t (1 <= t <= Ns) è posto di default pari a SP, arrotondato per eccesso.

 Sia s(f) una distribuzione di fitness continua della popolazione. La distribuzione di fitness attesa dopo l’applicazione del metodo TOUR, scelto il parametro SP, e l’intensità di selezione associata ( per s(f) = G(0,1) ) sono:

ΩT*(s, t) = s*(f) = t s(f) +

(3.15)

I

Si rimanda a [22] per tutte le dimostrazioni matematiche e le derivazioni teoriche.

- Truncation Selection (TRUNC)

Sia Ns il numero totale degli individui da selezionare. Un numero Nt (= T*Ns) di individui (scelti in base al loro ranking) viene replicato fino a coprire l'intero insieme da selezionare. N * (1-T) individui vengono clonati dai migliori Nt. Il parametro T (0 <= T <= 1) è posto pari a 1/SP di default.

 Sia s(f) una distribuzione di fitness continua della popolazione. La distribuzione di fitness attesa dopo l’applicazione del metodo TRUNC, scelto il parametro SP, e l’intensità di selezione associata (per s(f) = G(0,1) ) sono:

Ω *(s, T) =

30

I

Si rimanda a [24] per tutte le dimostrazioni matematiche e le derivazioni teoriche.

3.2.1.2 Ricombinazione

Attraverso l’operazione di ricombinazione, l’algoritmo produce nuovi individui combinando le informazioni genetiche degli individui genitore scelti dall’operazione di selezione. In questo caso sono proposti due diversi schemi di ricombinazione, tra cui l'utente può scegliere quello desiderato. I metodi descritti di seguito possono essere applicati ad individui a variabili reali.

- Ricombinazione lineare (LR)

I valori delle variabili degli individui-prole sono scelti sulla linea definita dalle variabili dei genitori (P1 e P2) (Figura 3.6):

(3.19)

con i = 1, 2, …, Nvar (Nvar numero di dimensioni dello spazio dei modelli) ed [-d,1+d] scelto in maniera casuale e costante per ogni valore di i.

Il valore di d definisce la lunghezza della linea entro cui vengono generate le variabili dei nuovi individui. Per d = 0, tale linea coincide con la distanza euclidea fra le variabili genitore. Siccome la maggior parte delle variabili non sono generate agli estremi della linea definita dai genitori, la zona di possibile esistenza delle nuove variabili tende a restringersi durante le generazioni. Di default si pone quindi d = 0.25 per prevenire, almeno in parte, effetti di questo genere.

31 Figura 3.6

- Ricombinazione rettangolare (RR)

I valori delle variabili degli individui-prole sono scelti all’interno del rettangolo definito dalle variabili dei genitori (Figura 3.7):

(3.20)

Per il valore di d, è applicabile quanto detto a proposito del valore dello stesso nel caso di una ricombinazione di tipo lineare. Il valore di cambia per ogni i differente.

32 3.2.1.3 Mutazione

Dopo un buon numero di iterazioni dell’algoritmo, vi è la possibilità che l’intera popolazione delle possibili soluzioni tenda a convergere nell’intorno di un minimo senza garanzie sul fatto che si tratti del minimo globale. Per tale motivo, tramite l'operazione di mutazione, gli individui sono alterati casualmente allo scopo di mantenere un buon grado di diversità genetica all’interno della popolazione. Un efficiente metodo di mutazione è quello proposto da Mühlenbein [26] e largamente utilizzato in tutti i campi di applicazione degli AAGG. Per Mühlenbein, nello specifico, ogni variabile di ciascun individuo è alterata con probabilità pari al tasso di mutazione (mutation rate) di un incremento pari a:

Incr = 0.2 RANGE (3.21)

con αi = rand(MutPrec,1) < 1/MutPrec, dove MutPrec è la precisione di mutazione, si

consiglia compresa tra 4 e 24.

Il segno dell'incremento è scelto in maniera casuale. La mutazione non coinvolge gli individui che presentano i migliori risultati: il 5% degli elementi totali non è modificato per costruzione. In letteratura, il valore del tasso di mutazione consigliato è pari a 1/Nvar, dove Nvar è pari al numero di gradi di libertà del sistema.

3.3

Metodi Monte Carlo, inferenza Bayesiana e ricampionamento

Il rinnovato interesse per le tecniche Monte Carlo per l'ottimizzazione globale e per l'esplorazione dello spazio dei modelli ha sollevato un interessante interrogativo, cioè come fare uso del campionamento prodotto per valutare trade-offs, vincoli e risoluzione nell’ambito di problemi non lineari multimodali. In altre parole, come si può utilizzare l'insieme dei modelli generati in un’inversione di tipo Monte Carlo per produrre più di una semplice stima di un set di parametri associati al modello migliore. Una interessante risposta a tale quesito, suggerita dalla seconda generazione di utenti dei metodi descritti, propone un approccio di tipo Bayesiano al problema. Tale tipo di trattazione statistica dei problemi inversi è ben noto ai geofisici attraverso l'opera di Tarantola e Valette (capitolo 2) ed è stato applicato ampiamente ai problemi linearizzati. Le tecniche Monte Carlo facilitano un'estensione della filosofia Bayesiano ai problemi non lineari.

33 In questa formulazione di un problema inverso tutte le informazioni sono rappresentate in termini probabilistici (gradi di credenza). In breve, una procedura di tale tipo combina le informazioni preliminari note del modello con i dati osservati e produce la funzione di densità di probabilità a posteriori (PPD) sullo spazio dei modelli, che rappresenta la soluzione completa del problema inverso.

Per problemi altamente non lineari la densità di probabilità a posteriori può avere una forma multimodale piuttosto irregolare, derivante dalla natura del fit dei dati (funzione di verosimiglianza) od anche dalla inclusione di informazioni a priori piuttosto complesse. In questo caso, sono necessarie tecniche di ottimizzazione globale per identificare il massimo della densità di probabilità a posteriori. Tuttavia, come la complessità della PPD aumenta, scegliere come soluzione del problema il singolo modello più probabile, se presente, è poco significativo.

Con date premesse, sono necessarie informazioni sulla forma completa della PPD per produrre le misure Bayesiane di incertezza e risoluzione. È qui che i metodi Monte Carlo presentano maggiori vantaggi rispetto metodi di linearizzazione (locali) dal momento che il campionamento prodotto può essere utilizzato per calcolare gli integrali Bayesiani. È posta quindi maggiore enfasi sul campionamento dello spazio dei parametri che sulla semplice ottimizzazione. Tale processo è noto come importance sampling.

L'essenza del presente approccio risiede nell’utilizzo delle informazioni a disposizione (la distribuzione dei modelli generati durante l’inversione) per guidare un ricampionamento dello spazio dei parametri. Questo non richiede ulteriori soluzioni del problema diretto, ma dal nuovo ensemble ricampionato siamo in grado di ottenere un insieme di informazioni che il semplice modello migliore non sarebbe in grado di fornirci.

Nell’ambito dei metodi Monte Carlo applicati al ricampionamento, si colloca il Neighbourhood Algorithm che è quello utilizzato, nella formulazione di Malcolm Sambridge [27], per il calcolo della densità di probabilità a posteriori approssimata in questo lavoro di tesi. Nel seguente paragrafo è possibile trovare una breve descrizione teorica del funzionamento dello stesso.

3.3.1 Neighbourhood Algorithm per il ricampionamento

La ricostruzione della densità di probabilità a posteriori (PPD) da un insieme finito di campioni è effettivamente un problema di interpolazione in uno spazio multidimensionale e, per spazi ad alte dimensioni, la maggior parte dei metodi possono diventare improponibili a livello computazionale. L’algoritmo proposto da

34 Sambridge (Neighbourhood Algorithm) propone un metodo di interpolazione multidimensionale basato sull’utilizzo delle celle di Voronoi []. Le celle di Voronoi costituiscono semplicemente le regioni di maggiore vicinanza ad ogni campione dello spazio dei modelli considerato. Nello specifico, la cella associata ad un generico punto P dello spazio dei modelli, è quella regione dello spazio contenente tutti i punti che distano dal punto P meno che da qualsiasi altro punto dell’insieme considerato (Figura 3.8). Tale distanza è misurata in norma L-Nvar, con Nvar uguale al numero di gradi di libertà del sistema. Esse si rivelano particolarmente utili per le proprietà geometriche di cui godono. Infatti, qualunque sia la distribuzione (regolare od irregolare) di punti e qualunque sia il numero di gradi di libertà del sistema considerato, le celle di Voronoi sono poliedri convessi univocamente definiti e space-filling, la loro dimensione e la loro forma si adattano automaticamente all’insieme dei punti considerati. L’approssimazione della PPD proposta da Sambridge, che chiameremo PNA(m), associa

ai punti all’interno di ogni cella di Voronoi le medesime caratteristiche del campione di cui sono i vicini più prossimi. Ogni cella costituisce cioè “l’area d’influenza” di ogni campione. Avremo:

PNA(m) = P(pi) (3.22)

dove pi è il campione dell’insieme di partenza più vicino al punto m.

Il metodo di ricampionamento proposto si fonda su di un’importante assunzione: essendo essa l’unica informazione in nostro possesso sulla PPD, faremo uso della PPD approssimata (PNA) al posto di quella reale (P). Avremo:

PNA(m) ~ P(m) (3.23)

Gli integrali Bayesiani possono dunque essere calcolati (tramite integrazioni di tipo Monte Carlo) generando un nuovo insieme di Nr punti dello spazio dei modelli, sk(k =

1, …, Nr), la cui distribuzione tende asintoticamente a PNA(m). Chiameremo tale set di

punti insieme ricampionato ed il procedimento prende il nome, come già accennato in precedenza, di importance sampling. Pertanto, se il campionamento è effettuato correttamente, per la densità di campionamento, hR(m), dovrebbe essere soddisfatta

la relazione

35

da cui avremo che gli integrali Bayesiani si ridurranno a semplici medie sull’insieme ricampionato:

(3.25)

Si è utilizzato il pedice NA per enfatizzare il fatto che si è utilizzata la PPD approssimata. L'insieme ricampionato può essere generato con un approccio standard conosciuto con il nome di campionamento di Gibbs [29]. Con questo metodo è possibile generare una passeggiata aleatoria (random walk) nello spazio dei modelli, la cui distribuzione tenda a qualsiasi distribuzione desiderata. Nel caso in esame, il campionamento di Gibbs è utilizzato allo scopo di generare punti distribuiti secondo la distribuzione PNA(m). La passeggiata aleatoria inizia nel punto B, che chiameremo mB. Da questo

punto la passeggiata compie, a turno, una serie di passi di ampiezza casuale nella direzione di ciascuno degli assi dello spazio dei parametri. Ad ogni passo un elemento di mB viene aggiornato (Figura 3.8).

36 In questo modo il metodo di Gibbs può essere impiegato per generare un insieme ricampionato di qualsiasi dimensione, Nr. È inoltre preferibile fare uso di diversi

random walks indipendenti a partire da altrettanti punti distinti dello spazio.

A partire dal nuovo insieme di Nr elementi è possibile inoltre derivare le distribuzioni

di densità marginali relative a ciascun grado di libertà. Queste possono significativamente migliorare il grado di conoscenza del problema considerato.

È importante, tuttavia, tenere presente che tecniche di ottimizzazione complesse come gli Algoritmi Genetici od il Simulated Annealing campionano preferenzialmente zone dello spazio dei modelli ad alta PPD, non è quindi garantito un buon accordo tra PPD approssimata e PPD reale in casi particolarmente sfavorevoli (ad esempio in caso di convergenza prematura verso minimi locali o di sottocampionamento marcato). Sicuramente sono un'utile conclusione da affiancare al risultato ottenuto.

37

Capitolo 4

Ottimizzazione funzionale tramite

Algoritmi Genetici

4.1 Introduzione

Allo scopo di mostrare da un punto di vista pratico il comportamento di un'inversione tramite Algoritmi Genetici, nel presente capitolo saranno presentati tre diversi esempi di ottimizzazione funzionale che si avvalgono di tale algoritmo. Per un'introduzione teorica sugli Algoritmi Genetici si rimanda al paragrafo 3.2.1. Le funzioni analitiche scelte per sperimentare l’efficienza dell’AG appartengono a tre differenti insiemi emblematici di funzioni:

38 - Funzioni convesse (paraboloide o funzione di De Jong)

Figura 4.1

Definizione: f(x,y) = x2 + y2 Dominio di ricerca: -100 ≤ x,y ≤ 100

Descrizione: la funzione è puramente convessa, il punto di minimo globale è l’unico punto singolare.

Minimo globale: f(0,0) = 0

- Funzioni marcatamente multimodali (funzione di Schwefel e funzione di Rastrigin)

39 Definizione: f(x,y) =

Dominio di ricerca: -100 ≤ x,y ≤ 100

Descrizione: la funzione è multimodale, il punto di minimo globale è si trova in prossimità dei limiti del dominio di ricerca. I minimi locali sono molteplici e distribuiti irregolarmente.

Minimo globale: f(420.9687,420.9687) = -837.9658

Figura 4.3

Definizione: f(x,y) = – π – π Dominio di ricerca: -5 ≤ x,y ≤ 5

Descrizione: la funzione è multimodale, il punto di minimo globale è si trova al centro del dominio di ricerca. I minimi locali sono molteplici e distribuiti regolarmente.

Minimo globale: f(0,0) = 0

- Funzioni piatte (funzione di Branin)

40 Definizione: f(x,y) =

Dominio di ricerca: -2.048 ≤ x,y ≤ 2.048

Descrizione: la funzione è particolarmente piatta in un’area estesa intorno al minimo globale, che è l’unico punto singolare.

Minimo globale: f(1,1) = 0

L’interesse verso lo studio dei minimi di questi tipi di funzioni, risiede nel fatto che si presume che la funzione oggetto sismica presenti caratteristiche analoghe ad una certa combinazione delle stesse. Nello specifico la funzione di Schwefel, la funzione di Rastrigin e la funzione di Branin rappresentano tre casi estremi particolarmente sfavorevoli. A meno che il modello di partenza non sia adeguatamente vicino alla soluzione vera, metodi di ottimizzazione locali mostrano gravi lacune nel raggiungere una convergenza adeguata al risultato sperato. Vedremo come, in tale frangente, è utile sfruttare le potenzialità dell'AG. Ci avvarremo inoltre dei risultati ottenuti per definire una linea da seguire, come supporto teorico, per le inversioni geofisiche che verranno affrontate nel seguente capitolo, pur tenendo ben presente le cruciali differenze riscontrabili fra le due problematiche.

Da un punto di vista pratico studiare il comportamento della funzione oggetto sismica avvalendosi anche delle analogie con le funzioni analitiche si rivela molto conveniente. Infatti, a livello computazionale, la risoluzione del problema diretto analitico è estremamente meno dispendiosa della risoluzione del corrispettivo sismico. Il relativamente ridotto tempo di calcolo necessario alla convergenza al minimo delle funzioni sopra elencate, ci consente pertanto di fornire delle discrete basi statistiche da cui trarre vantaggio per poter applicare al meglio il medesimo procedimento al fine di ottenere adeguati modelli di sottosuolo.

4.2 Simulazione

Nelle seguenti pagine è mostrata l'evoluzione della distribuzione della popolazione in funzione delle generazioni per ciascuno dei tre insiemi di funzioni sopra elencati. Fra le due funzioni multimodali descritte si è scelta la funzione di Schwefel a titolo di esempio. Tali simulazioni sono presentate allo scopo di fare maggiore chiarezza sul funzionamento dell'algoritmo utilizzato e sono pertanto eseguite su spazi dei modelli a due dimensioni per facilitarne la rappresentazione grafica. Come vedremo in seguito, è possibile estendere le considerazioni ricavate a spazi a dimensione maggiore. Nella seguente tabella sono riportati i valori dei parametri di controllo dell'AG, mantenuti costanti per ognuna delle tre simulazioni.

41 Figura 4.5

42 Figura 4.6

43 Figura 4.7

44

Parametri di controllo dell’AG utilizzati Num. Individui 50 Num. Generazioni 50 Ranking Lineare SP 1.5 Selection rate 0.8 Ricombinazione Rettangolare Mutation rate 0.5

Metodo selezione SUS

La prima simulazione (Figura 4.5) riguarda la ricerca del minimo applicata al semplice caso di una funzione oggetto parabolica bidimensionale. La funzione è puramente convessa e simmetrica rispetto all'origine degli assi. Il campo di variazione di ciascuna delle due variabili è compreso tra -100 e 100. Nella scala di colori descritta dalla barra riportata ai lati delle Figure 4.5(a-f) sono presentati i valori della funzione al variare delle due variabili x ed y. Il cerchio verde rappresenta il punto di minimo assoluto mentre gli asterischi magenta rappresentano gli individui della popolazione relativi alla i-esima generazione, per i = 0, 3, 5, 10, 15, 20, 30. Infine, in figura 4.5(g), è possibile osservare, in scala semilogaritmica, l'evoluzione rispetto alle generazioni dello scarto medio e dello scarto minimo fra la soluzione vera, che è nota, e le soluzioni predette. In questo caso la convergenza ad un valore prossimo alla soluzione vera è piuttosto rapida, si noti che, già a partire dalle decima generazione, il miglior modello predetto assicura un'accuratezza dell'ordine di 1e-4. Alla cinquantesima generazione si arriva ad un'accuratezza dell'ordine di 1e-8. Da un punto di vista statistico, il metodo di inversione risulta essere piuttosto robusto in quanto l'accuratezza massima alla cinquantesima generazione per 100 tentativi nelle medesime condizioni oscilla approssimativamente tra 1e-8 e 1e-7. È bene tuttavia tenere presente che ci troviamo in condizioni estremamente favorevoli, non potremmo infatti sperare in risultati altrettanto ottimali nel caso di funzioni multimodali, piatte, asimmetriche rispetto al centro dell'intervallo di variazione e/o per dimensioni particolarmente alte.

La seconda simulazione (Figura 4.6) riguarda la ricerca del minimo applicata alla funzione di Schwefel in due dimensioni. La funzione è multimodale e presenta diversi minimi locali distribuiti in maniera irregolare nello spazio. Il campo di variazione di ciascuna delle due variabili è compreso tra -100 e 100. La convergenza ad un valore prossimo al minimo assoluto della funzione è raggiunta con un'accuratezza dell'ordine di 1e-4. In questo caso, su 100 tentativi nelle medesime condizioni, l'accuratezza massima oscilla in media tra 1e-4 ed 1e-3. Tuttavia si riscontrano all'incirca un 10% di fallimenti nella convergenza al minimo assoluto. In tali casi nessuno dei modelli della popolazione iniziale cade nell'intorno del minimo globale e la mutazione non risulta