Ottimizzazione funzionale tramite Algoritmi Genetic
4.3 Influenza dei parametri di controllo sulla convergenza dell’AG
In questo paragrafo valuteremo l'influenza che i parametri di controllo hanno sull'efficienza delle inversioni condotte con Algoritmi Genetici. In un primo momento valuteremo l'efficacia del metodo al variare delle dimensioni dello spazio dei modelli per poi passare allo studio dei parametri dell'AG relativi alle tre operazioni fondamentali descritte nel Capitolo 3. Ognuno dei test è effettuato su tre funzioni analitiche appartenenti ai tre differenti insiemi riportati nel paragrafo precedente. Nello specifico le funzioni scelte sono: la funzione di De Jong, la funzione di Rastrigin e la funzione di Branin.
AG e dimensioni dello spazio dei modelli
Le simulazioni relative alla ricerca del minimo delle funzioni di De Jong e di Rastrigin sono state condotte usando i medesimi parametri di controllo, riportati in tabella, indipendentemente dalle dimensioni dello spazio dei modelli. I campi di variazione delle variabili delle due funzioni sono rispettivamente [-100,100] per la funzione di De Jong, e [-10,10] per la funzione di Rastrigin.
46 In Figura 4.8 è riportato il numero di modelli calcolati raggiungere convergenza con un'accuratezza minima di 1e-3 in funzione delle dimensioni dello spazio dei parametri.
Figura 4.8
Si deduce che, per entrambi i funzionali di riferimento, il numero di modelli calcolati cresce in regime approssimativamente esponenziale all'aumentare delle dimensioni. Si tratta di un'informazione molto utile per quando ci troveremo a scegliere quale tipo di parametrizzazione dei modelli di sottosuolo adottare per l'inversione sismica che tratteremo nel prossimo capitolo. La deviazione standard sul numero medio dei modelli calcolati oscilla tra il 3% ed il 9% del valore riportato in Figura 8, indipendentemente dalle dimensioni per entrambe le funzioni di riferimento. In tal senso l'AG, in queste circostanze, è da considerarsi piuttosto stabile e robusto.
Per quanto riguarda il caso della funzione di Branin, i risultati ottenuti per raggiungere la medesima accuratezza minima di convergenza non sono altrettanto promettenti (Figura 4.9). L'operazione di ricombinazione, per quanto riguarda questa applicazione specifica, non è sufficiente a garantire una convergenza adeguata in un numero ragionevole di iterazioni dell'algoritmo. Inoltre un metodo di mutazione più efficace è il metodo di mutazione adattativo proposto da Ostermeier et al [30]. Il metodo, ad ogni generazione, adatta passo e direzione di mutazione tenendo conto di successi e fallimenti dei passi scelti nelle iterazioni precedenti. Questa caratteristica lo rende particolarmente adatto all'ottimizzazione di funzioni particolarmente piatte. D'altra
Parametri di controllo dell’AG utilizzati Num. Individui 100 Ranking Lineare SP 1.5 Selection rate 0.8 Ricombinazione Rettangolare Mutation rate 0.5
47 parte, le operazioni di aggiornamento del passo di mutazione implicano un costo computazionale aggiuntivo. Per questo motivo, nonostante il numero relativamente ragionevole di modelli calcolati anche per dimensioni maggiori a quelle presentate in Figura 4.9 il metodo necessita di tempi di calcolo elevati. Tuttavia l'AG standard richiede la soluzione del problema diretto per un numero proibitivo dei modelli (> 1e6). La deviazione standard sul numero medio dei modelli calcolati oscilla intorno al 5% del valore riportato in Figura 4.9.
Figura 4.9
AG e parametri di controllo
Una proprietà di estrema importanza per l'operazione di selezione è l'intensità di selezione (si rimanda al paragrafo 3.2.1.1 per i dettagli teorici). Ricordiamo che può essere definita come la tendenza a scegliere i modelli migliori a discapito dei modelli peggiori. All'aumentare dell'intensità di selezione aumenta la probabilità di accettare i modelli che producono un risultato più vicino a quello desiderato.
In Figura 4.10 sono riportati il numero medio di modelli necessari a raggiungere convergenza con un'accuratezza minore di 1e-3 in funzione dell'intensità di selezione calcolata, per ognuno dei metodi di selezione considerati (Roulette Wheel Selection, Stochastic Universal Sampling, Truncation Selection, Tournament Selection). Lo spazio dei modelli è a 10 dimensioni, 3 per la funzione di Branin, ed ogni dato è mediato su 50 simulazioni. I parametri di controllo utilizzati sono riportati in tabella. Si ricorda che i valori di intensità di selezione calcolati per RWS e per SUS sono i medesimi.
Parametri di controllo dell’AG utilizzati
Num. Individui 15
Ranking Lineare
SP 1.5
Selection rate 1
Ricombinazione Non prevista Mutazione Ostermeier [29]
48 Figura 4.10(a)
Figura 4.10(b)
Figura 4.10(c)
Parametri di controllo dell’AG utilizzati Num. Individui 50 Ranking Lineare SP 1.5 Selection rate 0.8 Ricombinazione bka Rettangolare Mutatione rate 0.5 Metodo selezione
49 I risultati confermano quanto avremmo potuto supporre conoscendo le funzioni di riferimento. Rigettare i peggiori risultati nel caso di una funzione puramente convessa (Figura 4.10(a)) guida l'inversione verso una convergenza più rapida. Sebbene la tendenza sia meno accentuata, considerazioni analoghe si possono trarre per la funzione di Rastrigin (Figura 4.10(b)). Al contrario, la funzione di Branin è ottimizzata più rapidamente per un'intensità di selezione minore (Figura 10(c)). Date le caratteristiche della funzione, qualora l'area attorno al minimo non fosse campionata adeguatamente, rischieremmo una convergenza più lenta se non tenessimo in considerazione eventuali modelli peggiori per dirigere, tramite la ricombinazione, la ricerca verso il risultato sperato.
Per quanto riguarda l'operazione di ricombinazione, si è preferita una ricombinazione di tipo rettangolare (paragrafo 3.2.1.2) per massimizzare l'area entro cui è possibile generare nuove soluzioni e, di conseguenza, la variabilità genetica.
In materia di mutazione, si è raggiunto un buon accordo fra risultati sperimentali ed indicazioni teoriche ottenute dalla letteratura [20, 26, 31]. Le pubblicazioni scientifiche riguardanti l'argomento, infatti, consigliano un tasso di mutazione pari o leggermente superiore ad 1/Nvar, con Nvar pari al numero di gradi di libertà del sistema. Nel seguente grafico (Figura 4.11) sono presentati il numero di successi, normalizzati sul numero totale dei tentativi (pari a 100), al variare del tasso di mutazione per le funzioni di De Jong, Schwefel e Branin. L'indagine è condotta per un numero di dimensioni pari a 2, il tasso di mutazione di riferimento è pertanto pari a 0.5. Di fianco sono elencati i rimanenti parametri di controllo, mantenuti costanti in ciascuna delle prove. Mentre per una funzione puramente convessa il risultato non cambia sostanzialmente, si riscontrano sensibili variazioni nel caso di
funzioni più
complesse. In
entrambi gli altri due casi, un tasso di mutazione troppo basso peggiora l'inversione in quanto, tramite la sola operazione di ricombinazione, non è garantita la stessa variabilità genetica Figura 4.11
50 che il supporto della mutazione poteva
assicurare. D'altra parte, un tasso di mutazione esageratamente alto vanifica i benefici della ricombinazione impedendo all'AG di sfruttare a pieno le informazioni accumulate nelle varie generazioni: nel caso della funzione di Branin il risultato peggiora mentre nel caso della funzione di Schwefel rimane approssimativamente costante.
Invece, nel valutare i vantaggi dell'utilizzo delle sottopopolazioni per diminuire il numero di modelli calcolati per raggiungere convergenza, ci troviamo in disaccordo con quanto affermato da Pohlheim ed altri studi [19, 20] se ci concentriamo sul caso di funzioni multimodali. Come mostrato in Figura 4.12, a parità di individui totali all'interno della popolazione, il numero di modelli calcolati per raggiungere convergenza con accuratezza minore di 1e-3 aumenta o, al più, rimane pressoché invariato all'aumentare delle sottopopolazioni. L'esperimento è stato condotto sulla funzione di Rastrigin e reiterato per un numero di dimensioni dello spazio dei modelli variabile pari a 10, 20, 30, 40 e 50. Risultati analoghi si sono ottenuti nelle inversioni sismiche, come vedremo nel prossimo capitolo. Ogni risultato è ricavato dalla media su 25 tentativi; nei grafici sono riportate le deviazioni standard relative ai dati. I parametri di controllo sono i medesimi utilizzati nell’ultimo esperimento descritto (tabella riportata nella presente pagina). Ovviamente non è stato stabilito a priori un numero massimo di generazioni ed il numero di individui è variabile.
Figura 4.12(a)
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
51 Figura 4.12(b)
Figura 4.12(c)
52 Figura 4.12(e)
AG e intervallo di variabilità delle variabili
Una peculiarità di importanza cruciale degli AAGG implementati nello schema presentato, è la loro risposta alle variazioni dell'intervallo di variabilità dei parametri dei modelli. Infatti, per costruzione, l'operazione di ricombinazione, sia lineare che rettangolare, comporta un campionamento preferenziale del centro di tale intervallo (si faccia riferimento al paragrafo 3.2.1.2, ed in particolare alle Figure 3.6 e 3.7). A titolo esemplificativo si è scelto di generare 50 punti dello spazio R2 in maniera del tutto casuale con entrambe le 2 variabili libere di assumere qualsiasi valore all'interno dell'intervallo chiuso [0,1]. Da ogni punto sono state tracciate linee rette in modo da connettere ciascun elemento ai restanti 49 (Figura 4.13).
53 Figura 4.13
È evidente, osservando Figura 4.13, che la densità delle linee è nettamente maggiore al centro dell'intervallo di variabilità dei parametri. Quindi, essendo l'individuo figlio generato lungo una di tali linee, od al più all'interno del rettangolo definito dai genitori, la convergenza è facilitata se la soluzione giace in un intorno del punto medio dell'intervallo di esistenza dei parametri. Un esempio pratico consiste nel confronto tra l'ottimizzazione delle funzioni di Rastrigin e di Schwefel. I parametri di controllo utilizzati per l'ottimizzazione di entrambe le funzioni sono quelli riportati nella tabella a pagina 44. I fallimenti nella convergenza al minimo della funzione di Schwefel, su 50 tentativi nelle medesime condizioni, ammontano all'incirca al 10% del totale mentre non vi sono fallimenti nell'ottimizzazione della funzione di Rastrigin. Ciò avviene nonostante la valle del minimo della funzione di Rastrigin sia, in proporzione, notevolmente più ristretta della valle del minimo della funzione di Schwefel. Queste considerazioni si riveleranno fondamentali per la scelta dell’intervallo entro cui generare i modelli di sottosuolo per l'inversione in sismica.
54