logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-11052014-010331


Tipo di tesi
Tesi di laurea magistrale
Autore
BONADIO, RAFFAELE
URN
etd-11052014-010331
Titolo
SVILUPPO DI ALGORITMI GENETICI IN LINGUAGGIO C CON APPLICAZIONI A PROBLEMI DI FULL WAVEFORM INVERSION
Dipartimento
SCIENZE DELLA TERRA
Corso di studi
GEOFISICA DI ESPLORAZIONE E APPLICATA
Relatori
correlatore Prof. Mazzotti, Alfredo
relatore Prof. Stucchi, Eusebio Maria
Parole chiave
  • algoritmi genetici
  • C
  • full waveform inversion
  • FWI
Data inizio appello
19/12/2014
Consultabilità
Completa
Riassunto
Un problema geofisico inverso consiste nell’ottenere il modello per il quale i dati predetti meglio si adattino a quelli osservati. Il problema sismico di full waveform inversion mira a calcolare modelli di velocità ad alta risoluzione minimizzando la differenza tra le forme d’onda sismiche sintetiche e quelle osservate. Attualmente esistono diversi strumenti che possono essere utilizzati allo scopo, la maggior parte dei quali sono però distribuiti con licenza di tipo commerciale.
Per risolvere il problema di FWI possono essere utilizzati diversi metodi quali metodi di ottimizzazione locale, come ad esempio il metodo Gauss-Newton, che però producono spesso soluzioni intrappolate in minimi locali o metodi di ottimizzazione globale, quali i metodi simulated annealing, neighborhood algorithm o gli algoritmi genetici.
Gli algoritmi genetici in informatica (Holland 1992, Holland 1995) sono metodi di ricerca stocastici basati sull’imitazione del processo naturale di evoluzione biologica introdotto da Darwin in “L’origine delle Specie” (Darwin 1859).
Facendo riferimento ad alcuni recenti lavori sviluppati sull’argomento (Sajeva et al. 2014) e a librerie Matlab esistenti (Pohlheim 2006) si è voluto sviluppare un software in linguaggio C allo scopo di risolvere il problema sismico di FWI elastica monodimensionale tramite l’utilizzo di algoritmi genetici.
Gli obiettivi principali di questo lavoro sono la possibilità di svincolarsi da software proprietario, ottenere prestazioni computazionali migliori, assicurarsi maggiore portabilità e condivisione, ottenere l’opportunità di adeguare gli algoritmi esistenti ad uno specifico uso personale implementando nuove soluzioni non già previste.
Il metodo di lavoro affrontato per lo sviluppo di questo codice ha previsto una prima parte di studio teorico degli algoritmi seguita da uno studio approfondito più tecnico delle librerie Matlab esistenti, allo scopo di selezionare quali funzioni fossero necessarie e come integrare le stesse con nuovi metodi per rispettare le nostre specifiche.
La parte di sviluppo ha previsto lo studio e la codifica delle funzioni fondamentali degli algoritmi genetici (quali ad esempio la selezione, la ricombinazione, la mutazione, la migrazione) adeguando ogni funzione alle nostre necessità; successivamente a questa fase la codifica è stata estesa ad uno studio delle funzioni oggetto di tipo analitico da utilizzare per una preliminare fase di test.
Il software è stato testato su problemi di minimo utilizzando funzioni oggetto analitiche quali le funzioni di De Jong e di Rastrigin e quelle più “complesse” di Schwefel e di Michalewicz e successiva mente è stata effettuata una comparazione del software elaborato con l’algoritmo Matlab esistente, eseguendo una statistica per confrontare l’efficienza dell’algoritmo nei due diversi ambienti al variare dei parametri fondamentali quali la dimensione dello spazio dei modelli, il numero di iterazioni, l’accuratezza. Si è verificato che il software codificato in C permette di ottenere identici risultati con un tempo di elaborazione di quasi 2 ordini di grandezza inferiore.
In questa fase di test preliminare si è anche verificato la congruenza dei risultati nei due diversi ambienti, proponendo un metodo di verifica valido caso per caso: impostando per entrambi gli algoritmi la stessa generazione di numeri pseudo-casuali i risultati ottenuti indipendentemente dai due algoritmi risultano identici (alla precisione richiesta di 64-bit, la codifica standard utilizzata durante tutta l’elaborazione).
Alla fase di test è seguita una fase di ulteriore sviluppo riguardante l’algoritmo da utilizzare nel caso geofisico di FWI. Si è considerato un modello geologico mono-dimensionale; supponendo di conoscere lo spessore degli strati e le proprietà della colonna d’acqua si è invertito per le velocità P e S e per la densità relative ad 8 strati, quindi con un totale di 21 parametri da invertire. In questa fase si è introdotto l’uso del software OASES (Schmidt 1987) per la soluzione del problema diretto, unendo l’utilizzo dei due programmi tramite linguaggio di Bash Scripting.
Durante l’elaborazione ci si è imbattuti in un problema fondamentale di tipo computazionale, problema che si verifica anche in ambiente Matlab; la soluzione del problema diretto richiede la più grossa percentuale di risorse computazionali, rendendo quasi trascurabile il miglioramento dell’efficienza temporale ottenuta con la conversione da Matlab a C. Si è allora introdotta nell’algoritmo una procedura di parallelizzazione. Anziché generare un singolo modello a iterazione vengono generati più modelli contemporanemante indirizzando il calcolo di ogni modello su un processore diverso. La procedura permette una riduzione effettiva del tempo di calcolo che aumenta all’aumentare del numero dei processori.
Si è infine utilizzato il codice elaborato per indagare lo spazio dei parametri nel caso geofisico specifico. Sono stati prodotti diversi test, introducendo del rumore per rendere il dato più simile al caso reale e mettendo l’algoritmo in condizioni di ricerca difficili, ad esempio allargando i range di ricerca o modificando la centratura della soluzione rispetto ai limiti di ricerca. I test hanno dimostrato che alcune condizioni rendono l’indagine meno efficiente ma intervenendo con la modifica opportuna di alcuni parametri, quale ad esempio la pressione di selezione, si può affinare la ricerca.
Il programma sviluppato presenta i seguenti vantaggi rispetto a software analogo esistente:
- è possibile risolvere il problema geofisico di FWI per dati sintetici con prestazioni computazionali migliori
- il codice non utilizza nessun tipo di software esterno (a meno del software OASES, che però è distribuito liberamente) e ciò permette di non dover sostenere elevati costi di acquisto di programmi proprietari
- la codifica del programma, indipendente dallo sviluppo di altri programmatori, permette di adeguare le funzioni alle nostre ricerche specifiche senza dover richiedere modifiche e integrazioni a terze parti.
File