Appurata la maggiore e cienza del DAGA rispetto alle singole funzioni che lo compongono, si è scelto di testare l'algoritmo su dierenti funzioni oggetto, per valutarne l'e cienza su topologie con dierenti speci cità.
Le ottimizzazioni sono state confrontate con un NGA, avente gli stessi parametri del DAGA, e con un MCA, essendo il DAGA generato a partire da questi due approcci metaeuristici.
L'algoritmo MCA non sarebbe confrontabile con gli altri algoritmi scelti, non avendo una struttura algoritmica iterativa. Per ovviare a questo pro- blema è stato usato un algoritmo iterativo che, ad ogni ciclo, opera come un MCA con un numero di soluzioni generate pari al numero di cromosomi generato dal DAGA nella generazione corrispondente.
Ackley
La funzione di Ackley è una funzione multimodale ben ottimizzabile tramite GA. La topologia indotta dalla funzione sullo spazio dei modelli è costitui- ta da un insieme di minimi di valore decrescente con la distanza dal minimo globale. Inoltre gli intorni convessi del minimo globale assumono valori forte- mente decrescenti verso il centro. Tali fatti rendono l'esplorazione dei modelli estremamente direzionata verso il minimo globale. A causa di ciò è stato scel- to un insieme di parametri molto limitato per le ottimizzazioni. In tabella 4.7 sono riportati i parametri dei test.
Parametri 2d 3d 4d 10d Dimensione del problema 2 3 4 10 # Popolazione iniziale 8 10 12 21 # Sottopopolazioni 2 2 2 3 # Massimo di generazioni 100 100 100 150 Tasso di selezione 0.8 0.8 0.8 0.8 Parametri DAGA # Rimpiazzi 1 1 1 1 probabilità catastrofe 0.2 0.2 0.2 0.2
Tabella 4.7: Parametri del test
Le curve cumulative in gura 4.10 evidenziano un risultato atteso: la maggiore capacità esplorativa del DAGA permette in molti test di giungere a convergenza più rapidamente, anche a causa del grande bacino di attrazione del minimo globale. Ciò comporta una maggiore velocità di convergenza del DAGA rispetto al NGA. Il NGA giunge a convergenza in quasi tutti i casi. Il MCA ha trovato il minimo globale in un solo caso su 50 in dim = 2. Ciò è dovuto alla mancanza di memoria nella fase di esplorazione dell'algoritmo. I risultati dell'inversione sono riportati in tabella 4.8.
2d 3d
4d 10d
Figura 4.10: Curve incrementali di convergenza per la funzione di Ackley
Risultati 2d 3d 4d 10d
# di test a convergenza per DAGA 50 50 50 50 # di test a convergenza per NGA 49 49 49 49 # di test a convergenza per MC 1 0 0 0 Tempo medio di convergenza per DAGA 201 ms 267 ms 322 689 ms Tempo medio di convergenza per NGA 198 ms 260 ms 232 457 ms Tempo medio di convergenza per MC 7 ms 9 ms 8 ms 31 ms
Eggholder
La funzione Eggholder è de nita solo per dimensione 2, pertanto l'analisi è stata limitata solo all'ottimizzazione 2d. L'ottimizzazione è complicata da diversi fattori:
• la grande estensione del dominio della funzione, che rende più complessa l'esplorazione dello spazio dei modelli,
• il posizionamento al bordo del minimo globale: gli algoritmo genetici individuano più facilmente soluzioni localizzate all'interno dell'insieme di de nizione,
• i grandi valori di gradiente assunti dalla funzione in prossimità del mini- mo globale: il bacino di attrazione (ovvero il più grande intorno conves- so contenente il minimo globale) è piuttosto ridotto, e di conseguenza di di cile localizzazione.
A seguito di tali osservazioni sono stati scelti dei parametri molto maggiori rispetto a quelli usati per la funzione di Ackley, come evidenziato dalla tabella 4.9.
Parametri valori Dimensione del problema 2 # Popolazione iniziale 20 # Sottopopolazioni 2 # Massimo di generazioni 300 Tasso di selezione 0.8 Parametri DAGA # Rimpiazzi 2 probabilità catastrofe 0.2
Tabella 4.9: Parametri del test
I risultati mostrati in gura 4.11 evidenziano la complessità della topo- logia su cui è stata eseguita l'inversione. La velocità di convergenza del DAGA risulta essere molto elevata, a causa della buona capacità esplorativa dell'algoritmo, che giunge a convergenza in ogni test eettuato.
Figura 4.11: Curve incrementali di convergenza per la funzione eggholder Il NGA fallisce l'ottimizzazione in 43 casi su 50, a causa di fenomeni di drift genetico, causati dai fattori analizzati in precedenza, come evidenziato dalla tabella 4.10, in cui sono riportati i risultati dell'inversione.
Anche in questo caso il MCA non raggiunge mai il minimo globale. # di test a convergenza per DAGA 50
# di test a convergenza per NGA 7 # di test a convergenza per MC 0 Tempo medio di convergenza per DAGA 542 ms Tempo medio di convergenza per NGA 643 ms Tempo medio di convergenza per MC 16 ms
Langerman
La funzione di Langermann è caratterizzata da un ristretto numero di minimi locali molto distanti fra loro aventi valori prossimi al minimo globale. Ciò, come già visto per alcune funzioni test precedenti, genera fenomeni di drift. I test sono stati eettuati in dimensione 2, 3, 4, con parametri su cientemente grandi da garantire un buon successo per ottimizzazioni di coltose, in ma- niera analoga all'ottimizzazione della funzione eggholder, come evidenziato dalla tabella 4.11.
Parametri 2d 3d 4d Dimensione del problema 2 3 4 # Popolazione iniziale 10 20 60 # Sottopopolazioni 2 2 3 # Massimo di generazioni 200 200 500 Tasso di selezione 0.8 0.8 0.8 Parametri DAGA # Rimpiazzi 1 2 5 probabilità catastrofe 0.2 0.2 0.2
Tabella 4.11: Parametri del test
Dall'analisi della gura 4.12 si può osservare che in dimensione 2, an- che a causa della limitata estensione del dominio della funzione, il MCA evidenzia una seppur limitata capacità di convergenza. Col crescere della dimensionalità del problema la funzione non riesce ad identi care il minimo globale a causa del grande aumento di complessità derivante dall'aumento della dimensione della funzione considerata.
L'NGA, come già visto in precedenza, ha un'ottima velocità di conver- genza iniziale, che si riduce drasticamente dopo poche generazioni. Anche in questo caso diversi tentativi non sono giunti a convergenza, probabilmente a causa di convergenze precoci in minimi locali.
Dai test risulta evidente che il DAGA riesce ad individuare il minimo globale in quasi tutti i casi.
2d 3d
4d
Figura 4.12: Curve incrementali di convergenza per la funzione di Langermann
Risultati 2d 3d 4d
# di test a convergenza per DAGA 50 49 48 # di test a convergenza per NGA 30 31 31 # di test a convergenza per MC 10 0 0
Tempo medio di convergenza per DAGA 214 ms 442 ms 1720 ms Tempo medio di convergenza per NGA 354 ms 409 ms 864 ms Tempo medio di convergenza per MC 12 ms 30 ms 106 ms
Rastrigin
Come già visto nell'analisi comparata la funzione di Rastrigin non ore particolari impedimenti nell'ottimizzazione.
La scelta dei parametri, mostrata in tabella 4.13, è conseguente all'os- servazione di forti somiglianze fra la topologia indotta da questa funzione e quella della Ackley, sebbene il valore del minimo di quest'ultima, e il suo bacino di attrazione (ovvero il più grande intorno convesso contenente il minimo globale) fossero ben più signi cativi dei corrispettivi della Rastrigin.
Parametri 2d 3d 4d 10d Dimensione del problema 2 3 4 10 # Popolazione iniziale 10 15 18 72 # Sottopopolazioni 2 3 3 3 # Massimo di generazioni 200 150 200 450 Tasso di selezione 0.8 0.8 0.8 0.8 Parametri DAGA # Rimpiazzi 1 1 1 3 probabilità catastrofe 0.2 0.2 0.2 0.2
Tabella 4.13: Parametri del test
Dalla gura 4.13 si può osservare come anche in questo caso, a causa del- la ristrettezza de dominio considerato, il MCA identi ca, in dimensione 2, il minimo globale in un numero signi cativo di casi. NGA e DAGA mostrano performances analoghe, così come sono simili le velocità di convergenza evi- denziate dalle due curve. I risultati delle inversioni sono riportate in tabella 4.14.
2d 3d
4d 10d
Figura 4.13: Curve incrementali di convergenza per la funzione di Rastrigin
Risultati 2d 3d 4d 10d
# di test a convergenza per DAGA 50 49 48 49 # di test a convergenza per NGA 50 43 44 49 # di test a convergenza per MC 24 0 0 1
Tempo medio di convergenza per DAGA 295 ms 474 ms 923 ms 2761 ms Tempo medio di convergenza per NGA 218 ms 350 ms 467 ms 1206 ms Tempo medio di convergenza per MC 4 ms 15 ms 21 ms 117 ms
Schwefel
La funzione di Schwefel presenta diverse criticità legate all'ottimizzazione tra- mite algoritmi genetici [14]. Conseguentemente la scelta dei parametri iniziali per le inversioni tiene conto di tali problematiche. Rispetto alle funzioni pre- cedenti i valori scelti sono molto maggiori (eccezion fatta per la eggholder, per certi versi analoga a questa funzione). I parametri dell'inversione sono riportati in tabella 4.15.
Parametri 2d 3d 4d 10d Dimensione del problema 2 3 4 10 # Popolazione iniziale 10 24 60 300 # Sottopopolazioni 2 2 2 4 # Massimo di generazioni 300 300 450 1000 Tasso di selezione 0.8 0.8 0.8 0.8 Parametri DAGA # Rimpiazzi 1 3 5 12 probabilità catastrofe 0.2 0.2 0.2 0.2
Tabella 4.15: Parametri del test
Dalla gura 4.14 risulta ben evidente il successo del DAGA rispetto al NGA, che, col crescere della dimensionalità del problema, incontra sempre più di coltà nell'identi cazione del minimo globale. Ad alte generazioni è ben evidente il fenomeno di drift genetico del NGA, non riscontrabile nell'evoluzione del DAGA.
Il MCA non giunge mai a convergenza, anche a causa della grande esten- sione dello spazio dei modelli. I risultati delle inversioni sono riportate in tabella 4.16.
2d 3d
4d 10d
Figura 4.14: Curve incrementali di convergenza per la funzione di Schwefel
Risultati 2d 3d 4d 10d
# di test a convergenza per DAGA 50 49 50 47 # di test a convergenza per NGA 32 29 23 19 # di test a convergenza per MC 0 0 0 0
Tempo medio di convergenza per DAGA 365 ms 1030 ms 1042 ms 28338 ms Tempo medio di convergenza per NGA 396 ms 430 ms 860 ms 9893 ms Tempo medio di convergenza per MC 16 ms 27 ms 42 ms 374 ms