Influenza dei parametri di controllo sulla convergenza

AG e pressione di selezione

Di seguito (Figure 5.4-7) sono confrontati i risultati ottenuti imponendo alternativamente alte e basse pressioni di selezione per ognuno dei metodi di selezione considerati. Nello specifico, viene presentata l'evoluzione, durante le diverse generazioni, del model misfit relativo al modello che presenta il miglior data misfit. I range di variabilità dei parametri dei modelli sono ampi 1200 m/s e sono approssimativamente centrati sui valori di velocità del modello in griglia lasca (8x8) che meglio interpola il modello di riferimento.

60 Figura 5.5

61 Figura 5.7

È evidente che una bassa pressione di selezione è di gran lunga preferibile ad un'alta pressione di selezione per ognuno dei casi proposti. Tale risultato suggerisce che ci troviamo di fronte a problematiche di convergenza prematura verso un minimo locale qualora non siamo in grado di garantire una sufficiente variabilità genetica all'interno della popolazione di modelli-soluzione. Addirittura, nel caso della Truncation Selection riportato in Figura 5.7, la convergenza ad un minimo locale arriva attorno alla decima generazione. L’AG non è in grado di allontanarsi dalla valle di minimo raggiunta.

AG e metodo di selezione

Stabilito che è preferibile imporre una bassa pressione di selezione, è opportuno, al fine di scegliere le migliori impostazioni per una performance ottimale dell'algoritmo, confrontare l'efficienza dei vari metodi di selezione disponibili. Nel seguente grafico (Figura 5.8) è possibile osservare l'evoluzione, durante le diverse generazioni, del model misfit relativo al modello che presenta il miglior data misfit.

62 Figura 5.8

Tutte le operazioni di inversione, in questo caso, sono condotte a partire dalla medesima popolazione iniziale (l'origine delle curve non coincide per il fatto che sono presentati in figura i risultati a partire dalla seconda generazione). Nell'inversione sismica è stato inoltre introdotto un nuovo metodo di selezione (BOLTZ) basato sulle indicazioni teoriche fornite dalle pubblicazioni di Sen & Stoffa [18,29]. L'introduzione di un ulteriore metodo di selezione è dovuta al fatto che, come è possibile notare in Figura 5.8, a partire circa dalla generazione 35, il model misfit aumenta sensibilmente nonostante il data misfit continui a diminuire. Ciò è riconducibile al fatto che, intorno a tale generazione, data misfit minimo e medio convergono ad un unico valore sottolineando quindi una convergenza molto rapida. La ricerca del minimo si concentra in una zona piuttosto circoscritta, non si notano cambiamenti apprezzabili per il data misfit mentre il modello corrispondente a quella che ci aspettiamo essere la soluzione ottimale si allontana dal risultato desiderato. Il metodo proposto da Sen & Stoffa si rifà alla teoria che sta alla base del metodo Monte Carlo del Simulated Annealing, un algoritmo alternativo all'AG utilizzato nei problemi di ottimizzazione. Il concetto di annealing (ricottura in italiano) deriva dalla scienza dei materiali, dov'è usato per descrivere il processo di eliminazione di difetti reticolari dai cristalli tramite una procedura di riscaldamento seguita da un lento raffreddamento. Questo lento raffreddamento è implementato nell'algoritmo del Simulated Annealing come un lento

63 ridimensionamento della probabilità di accettare le soluzioni ritenute peggiori durante la procedura di inversione. Il concetto di raffreddamento può essere introdotto come supporto all'AG dividendo la funzione di fitness calcolata durante l'operazione di selezione, per un valore di temperatura che decresce durante le generazioni. Durante le prime generazioni è opportuno scegliere una temperatura maggiore di 1 al fine di impedire ai modelli migliori di dominare la popolazione, agevolando un’adeguata diversità genetica. In un secondo momento invece, è utile scegliere una temperatura minore di 1 esagerando quindi le differenze fra i valori di fitness, altrimenti troppo ravvicinati, in modo da guidare l’inversione verso i modelli migliori. Come risultato avremo una convergenza più lenta che produce una soluzione più stabile.

AG, ricombinazione e mutazione

Per quanto riguarda le operazioni di ricombinazione e mutazione, si è scelto di optare per una ricombinazione rettangolare ed un tasso di mutazione pari a 0.1, al fine di mantenere un' adeguata variabilità genetica all'interno della popolazione. Le indicazioni teoriche suggerirebbero un tasso di mutazione più basso ~ 0.05 ma si è deciso di aumentarla leggermente per rendere l'operazione più incisiva. La precisione di mutazione impostata è pari a 4, per una precisione più alta le mutazioni non producono effetti sensibili sul data misfit.

AG e sottopopolazioni

Come mostrato in Figura 5.9, l'utilizzo delle sottopopolazioni non produce effetti vantaggiosi. Ciò conferma quanto riscontrato per il caso delle funzioni analitiche. A colori uguali corrispondono le evoluzioni del model misfit di differenti sottopopolazioni della medesima inversione.

64 AG e ranges delle variabili

Di estremo interesse è la scelta dell'intervallo di variabilità dei parametri dei modelli. Infatti, come constatato per il caso delle funzioni analitiche, le prestazioni dell'AG migliorano notevolmente se la soluzione del Problema Inverso di interesse si trova approssimativamente al centro dell'intervallo di variabilità dei parametri. A tal proposito si sono confrontati i risultati ottenuti al variare dell'intervallo entro cui generare le variabili. Nello specifico sono state effettuate due inversioni distinte. Nel primo caso l'intervallo entro cui generare le variabili è ampio 1200 m/s ed è centrato (a meno di un dislocamento casuale di un massimo di 250 m/s) sul valore vero per ciascuna delle variabili (Figura 5.10). Nel secondo caso l'intervallo entro cui generare le variabili è ampio solamente 400 m/s ma il valore vero, pur essendo contenuto entro i range di variabilità dei parametri, si trova vicino agli estremi degli stessi (Figura 5.11).

65 Figura 5.11

I risultati confermano quanto dedotto dallo studio dell'ottimizzazione funzionale tramite AG presentato nel capitolo precedente: è preferibile aumentare l’ampiezza dei ranges se non siamo particolarmente certi della loro adeguatezza. Di seguito riportiamo un confronto tra l'evoluzione dei rispettivi model misfit (Figura 5.12).

66

5.3 Risultati

Di seguito sono riportati i risultati ottenuti utilizzando il procedimento descritto nell’applicazione del metodo all’inversione dei dati sismici sintetici generati sul modello presentato in Figura 5.1. Nelle Figure 5.13 sono presentati i risultati ottenuti impiegando come ondina sorgente la derivata dell’ondina di Ricker filtrata per ottenere una frequenza centrale di 3 Hz. In Figura 5.14, invece, sono presentati i risultati ottenuti impiegando la medesima ondina filtrata però a 10 Hz.

Per ognuna delle due prove sono riportati:

- l’evoluzione del model misfit rispetto alle generazioni;

- la differenza tra il modello vero ed il modello migliore risultante dall’inversione ed il valore medio di model misfit (in griglia fitta 96x23) calcolato in norma L1;

- il modello migliore risultante dall’inversione.

I risultati sono incoraggianti in entrambi i casi, il model misfit (96x23) medio in norma L1 è pari a circa 50 m/s e raggiunge valori massimi in prossimità dei bordi della piega (Figure 5.13-14(b)). Ciò è riconducibile agli effetti della parametrizzazione che tende a lisciare il modello alle interfacce.

In tabella riportiamo i parametri di controllo utilizzati:

Parametri di controllo dell’AG utilizzati

Num. Individui 300

Num. Generazioni 60

Num. Sottopopolzioni 1

Ranking Lineare

Metodo di selezione BOLTZ

Selection rate 0.8

SP 1.5

Ricombinazione Rettangolare

Mutation rate 0.1

Ranges ∿ centrati, ampiezza 1200m/s

67 Ondina a 3 Hz

Figura 5.13(a)

Figura 5.13(b)

68 Ondina a 10 Hz

Figura 5.14(a)

Figura 5.14(b)

69 Di seguito, in Figura 5.15 ed in Figura 5.16 sono riportati rispettivamente i marginali 1D e 2D della densità di probabilità a posteriori calcolata tramite Neighborhood Algorithm (paragrafo 3.3.1) relativi ad alcune delle 64 variabili in cui è parametrizzato lo spazio dei modelli. Ogni parametro è una cella della griglia 8x8.

La densità di probabilità marginale è riportata nell’asse delle ordinate in funzione del valore assunto dalla variabile, nell’asse delle ascisse. La barra in rosso indica la posizione del valore di riferimento della variabile mentre la barra in nero indica la posizione della migliore soluzione dell’inversione.

Figura 5.16 Figura 5.15

70 Nell’asse delle ascisse e delle ordinate sono riportati i valori assunti dalle due variabili considerate. La densità di probabilità è massima in prossimità delle aree di colore rosso, minima nelle aree di colore blu. Il cerchio bianco indica la posizione del valore di riferimento mentre il cerchio nero indica la posizione della migliore soluzione dell’inversione.

Come possiamo notare vi è un ottimo accordo tra risultati ottenuti, valori di riferimento e densità di probabilità a posteriori. Ciò non fa che rafforzare la nostra confidenza nei risultati. Per tutti i casi mostrati in Figura 5.16 il valore di riferimento è contenuto nelle aree a massima densità di probabilità a posteriori. Fatta eccezione per il parametro (5,3), la migliore soluzione dell’inversione si trova in prossimità del valore i riferimento. Nel caso del suddetto parametro, la soluzione migliore manca il risultato sperato di circa 300 m/s, ciò è riconducibile al bias introdotto dall’interpolazione. La cella corrispondente a tale parametro si trova infatti, lungo la direzione orizzontale, tra due celle a maggiore velocità: variazioni del suo valore non influiscono abbastanza sul data misfit da costringere l’inversione verso la direzione corretta.

71

Capitolo 6

Conclusioni

I risultati ottenuti durante questo lavoro di tesi suggeriscono che gli Algoritmi Genetici hanno il potenziale di risolvere problemi di ottimizzazione fortemente non lineari con un livello di accuratezza promettente. L’AG necessita di informazioni minime sul problema specifico di interesse (il solo calcolo della funzione oggetto) ed è pertanto indipendente dai dettagli del problema diretto. Questa è una caratteristica molto conveniente in quanto esattamente lo stesso algoritmo può essere facilmente applicato ad un ampia gamma di problemi di ottimizzazione. Infatti, lo stesso codice sorgente e le stesse subroutines sono state utilizzate sia nelle applicazioni all’ottimizzazione di funzioni analitica che nelle applicazioni all’inversione sismica non lineari presentate nei capitolo precedenti. L’algoritmo è inoltre indipendente dalla forma della funzione oggetto ed evita l’uso di qualsiasi informazione sulle sue derivate pur sfruttando efficientemente le informazioni accumulate, raggiungendo abbastanza rapidamente una soluzione vicina alla soluzione ottimale.

Attualmente lo studio delle applicazioni degli Algoritmi Genetici alle inversioni Full- Waveform è un terreno di ricerca piuttosto inesplorato, nonostante tale tipo di algoritmi sia stato utilizzato con successo nei più svariati campi scientifici. L’obiettivo di questo lavoro di tesi è di dare un contributo alla verifica della loro applicabilità in questo campo.

72 Il numero di modelli coinvolti durante il processo di inversione sismica è pari a circa 15000 per uno spazio dei parametri a 64 dimensioni. Tale risultato è incoraggiante data la predisposizione intrinseca dell’AG alla parallelizzazione. Tuttavia l’operazione di interpolazione lineare introdotta per mantenere le dimensioni dello spazio dei parametri contenute, introduce un bias che potrebbe non essere sempre gestibile facilmente.

Allo stato attuale si riscontrano alcune difficoltà pratiche che è bene tenere presente. La prima è dovuta alla scarsa copertura dello spazio dei modelli che è inevitabile per dimensioni dello stesso particolarmente elevate. Per casi particolarmente sfavorevoli, modelli non particolarmente vicini al minimo globale della funzione oggetto ma relativamente buoni rispetto al resto della popolazione rischiano di dominare e guidare l’inversione verso minimi locali.

Un ulteriore aspetto in qualche modo insoddisfacente degli Algoritmi Genetici è dovuto al fatto che è necessario sintonizzarli al problema specifico. Infatti, mentre l’algoritmo in sé è agevolmente applicabile in campi scientifici di varia natura, si riscontrano complicazioni non del tutto trascurabili quando si tratta di individuare un insieme di parametri di controllo che si adattino alle caratteristiche particolari del problema in esame. In questo senso se non altro è incoraggiante lo studio condotto sulle funzioni analitiche che ha sottolineato la robustezza del metodo di inversione tramite Algoritmi Genetici per parametri costanti. Robustezza confermata dalle applicazioni in sismica nonostante queste non possano godere della medesima base statistica.

Questo lavoro di tesi lascia aperti numerosi possibili sviluppi futuri su cui sarebbe interessante investigare, ne elenchiamo alcuni di seguito:

- Realizzazione di un codice di inversione ibrido che si avvale degli Algoritmi Genetici supportati da metodi a gradiente tradizionali in due fasi consecutive. Si propone di utilizzare il miglior modello ottenuto dall’inversione globale come modello di partenza per un algoritmo di inversione locale.

- Implementazione di un Algoritmo Genetico meno sensibile alla variazione dei parametri di controllo avvalendosi, ad esempio, di ibridazioni con altri algoritmi appartenenti alla classe dei metodi Monte Carlo (Simulated Annealing, Neighborhood Algorithm, …)

- Ottimizzazione della parallelizzazione dell’algoritmo data la predisposizione intrinseca degli stessi. Il metodo Full-Waveform è infatti particolarmente pesante da un punto di vista computazionale.

- Sperimentazione dell’efficacia del metodo su dati reali (o su sintetici generati da diversi software di forward modeling) e valutazione della robustezza al rumore del metodo proposto.

73

Bibliografia

- [1] A. Tarantola, B. Valette. Inverse Problems – Quest for Information, Journal of Geophysics, 50, 159-170, 1982

-

- [3] M.C. Gavallotti. Interpretazioni della Probabilità, SWIF, 2006

- [4] A. Duijndam. Detailed Bayesian inversion of seismic data (thesis dissertation), Delft Geophysical, 1987

- [5] T. Bayes. An Essay Towards Solving a Problem in the Doctrine of Chances, Philosophical Transactions of the Royal Society of London, 53, 370-418, 1763 (data stesura)

- [6] Fienberg. When Did Bayesian Inference Become “Bayesian”?, Bayesian Analysis, 1, 1-40, 2006

- [7] J.M. Keynes. A Treatise on Probability, MacMillan & Co., 1921

- [8] I. Good. Probability and the Weighing Evidence, Charles Griffin, 1950 - [9] F. P. Ramsey. Foundations of Mathematics and Other Logical Essays, 1931 - [10] R. Aster, B. Borchers, C. Thurber. Parameter Estimation and Inverse

Problems, Elsevier, 2005.

- [11] J. M. Hammersley, D.C. Handscomb. Monte Carlo Methods, Methuen, 1964

- [12] F. Press, Earth Models Obtained by Monte Carlo Inversion, Journal of Geophysical Research, 73(16), 5223-5234, 1968

74 - [13] M. Sambridge, K. Mosegaard. Monte Carlo Methods in Geophysical

Inverse Problems, Reviews of Geophysics, 40(3), 1-29, 2002

- [14] J.H. Holland. Adaptation in Natural and Artificial System, University of Michigan Press, 1975

- [15] D.E. Goldberg. Genetic Algorithm in Search Optimization and Machine Learning, Kluwer Academy Publisher s, 1989

- [16] G.H. Weiss. Aspects and Applications of the Random Walk, North Holland, 1994

- [17] M. Sambridge, G. Drijkoningen. Genetic Algorithm in Seismic Waveform Inversion, Geophysical Journal International, 109, 323-342, 1992

- [18] P.L. Stoffa, M. Sen. Nonlinear Multiparameter Optimization using Genetic Algorithms: Inversion of Plane-Wave Seismograms, Geophysics, 56(11), 1794- 1810, 1991

- [19] J. Horn. Finite Markov Chain Analysis of Genetic Algorithm with Niching, Proceedings of the 5th international conference on genetic algorithms, 1993 - [20] H. Pohlheim. Genetic and Evolutionary Algorithm Toolbox for use with

Matlab – Documentation, http://www.geatbx.com/, 1994-1999

- [21] T. Blicke, L. Thiele. A Comparison of Selection Schemes used in Genetic Algorithms, TIK Report N. 11,1995

- [22] H. Mühlenbein, D. Schlierkamp-Voosen. Predictive Models for the Breeder Genetic Algorithm: I. Continuous Parameter Optimization, Evolutionary Computation, 1(1), 25-49,1993

- [23] T. Blicke, L. Thiele. A mathematical Analysis of Tournament Selection, Proceedings of the 6th international conference on genetic algorithms, 1995 - [24] J. Crow, M. Kimura. An Introduction to Population Genetics Theory, Harper

and Row, 1970

- [25] H. Mühlenbein. The Breeder Algorithm – a provable optimal search algorithm and its application. IEE Colloquium on Applications of Genetic Algorithms,1994

- [26] M. Sambridge. Geophysical Inversion with Neighborhood Algorithm – II. Appraising the Ensemble, Geophysical Journal International, 138, 727-746, 1999

- [27] M. G. Voronoi. Nouvelles Applications des paramètres continus a la théorie des forms quadratiques, J. reine Angew. Math., 134, 198-287, 1908

75 - [28] S. Geman, D. Geman. Stochastic Relaxation, Gibbs Distributions and the Bayesian Restoration of Images, IEEE Transaction on Pattern Analysis and Machine Intelligence, 6(6), 721-741

- [29] A. Ostermeier, A. Gawelczyk, N. Hansen. Step Size Adaptation based on non-local use of Selection Information, Parallel Problem Solving from Nature, 189-198, 1994

- [30] M. Sen, P.L. Stoffa, Global Optimization Methods in Geophysical Inversion, ELSEVIER, 1995

- [31] A. Fichtner. Full Seismic Waveform Modeling and Inversion, Springer, 2011 - [32] J. Virieux, S. Operto. An Overview of Full-Waveform Inversion in