I primi tre test eettuati hanno lo scopo di provare come le funzioni imple- mentate in questo lavoro comportino un miglioramento sostanziale al NGA, inoltre si vuole evidenziare come i contributi delle due funzioni (Competition e Catastrophy and Repopulation) prese singolarmente siano meno e caci della combinazione delle due. Pertanto si è scelto di confrontare il DAGA con il NGA integrato con una sola delle due funzioni componenti il DAGA (la competizione per CompGA e catastro e ripopolamento per CataGA). Inoltre per analizzare l'eettivo miglioramento oerto dalle nuove funzioni, si è scelto di aggiungere al confronto anche i risultati delle inversioni ottenute con un NGA e con un GA standard.
Per i tre test presentati sono state eseguite 100 ottimizzazioni generando ogni volta una popolazione iniziale dierente.
Rastrigin 2d
Per questa ottimizzazione sono stati scelti dei parametri piuttosto limitati, così da rendere la ricerca quanto più di cile possibile per l'algoritmo.
Parametri valori Dimensione del problema 2 # Popolazione iniziale 6 # Sottopopolazioni 2 # Massimo di generazioni 200 Tasso di selezione 0.8 Parametri DAGA # Rimpiazzi 1 probabilità catastrofe 0.2
Tabella 4.1: Parametri del test
Figura 4.2: Numero medio di modelli generati dai vari algoritmi Risulta evidente dal gra co 4.1 come l'ottimizzazione non presenti parti- colari ostacoli, tanto che gli algoritmi classici hanno un rateo di convergenza analogo a quello degli algoritmi ottimizzati.
Ciò è dovuto alla topologia indotta dalla funzione oggetto sullo spazio dei modelli, ottenuto dalla combinazione di un'armonica con un iperboloide. La morfologia risultante è costituita da un insieme di picchi e valli di valore decrescente all'avvicinarsi del minimo globale. Ciò comporta che i minimi locali prossimi a quello globale corrispondono a valori della funzione oggetto migliori rispetto a regioni più distanti. Tale fatto comporta un'esplorazione direzionata verso il minimo globale, rendendo super ua un'esplorazione più vasta dello spazio dei modelli.
In gura 4.2 si può notare come il numero di modelli valutati per i diversi algoritmi sia sostanzialmente uguale, a causa dell'esiguo numero di individui della popolazione iniziale, e, di conseguenza, l'ancora più ridotto numero di individui generati random.
La curva corrispondente a CataGA risulta depressa rispetto alle altre a causa di un leggero aumento di velocità di convergenza fra la generazione 60 e la 80. Ciò ha determinato un numero totale di individui generati inferiore
agli altri algoritmi.
Figura 4.3: Errore medio degli algoritmi
La gura 4.3 rappresenta l'errore medio degli individui migliori ad una data generazione. L'andamento è anche in questo caso simile per tutti gli algoritmi. Si può notare come il GA abbia un'exploitation migliore, ovvero una maggiore capacità di convergere verso il valore del minimo globale, una volta individuato un intorno convesso di tale minimo.
# di test a convergenza per GA 96 # di test a convergenza per NGA 96 # di test a convergenza per CompGA 99 # di test a convergenza per CataGA 97 # di test a convergenza per DAGA 99 # di medio di modelli generati per GA 518 # di medio di modelli generati per NGA 526 # di medio di modelli generati per CompGA 521 # di medio di modelli generati per CataGA 438 # di medio di modelli generati per DAGA 528
I risultati riportati in tabella 4.2 confermano quanto detto in precedenza. Il numero di successi è pressoché lo stesso per tutti gli algoritmi, come già evidenziato dalla gura 4.1.
Schwefel 2d
La funzione di Schwefel è stata scelta per esaminare le performances degli algoritmi in un contesto molto più di cile, a causa della topologia fortemente multimodale, con grandi valli di minimo isolate e localizzate ai bordi dello spazio dei modelli. La posizione al bordo del minimo globale costituisce un'ulteriore di coltà per i GA.
Parametri valori Dimensione del problema 2 # Popolazione iniziale 7 # Sottopopolazioni 2 # Massimo di generazioni 300 Tasso di selezione 0.8 Parametri DAGA # Rimpiazzi 1 probabilità catastrofe 0.2
Tabella 4.3: Parametri del test
È stato scelto di usare un insieme di parametri piuttosto ridotto per evidenziare eetti di drift comunque presenti con probabilità crescente con l'aumentare della dimensionalità del problema.
Dalla gura 4.4 si nota una forte discrepanza fra i risultati dei vari test: • GA è fortemente depressa, a causa del drift genetico.
• NGA è l'algoritmo che va a convergenza più spesso nelle prime genera- zioni. La scelta del modello iniziale in uenza il successo dell'ottimizza- zione, sebbene in maniera più limitata del GA. Ciò determina la forte depressione della curva nelle ultime generazioni.
• CompGA, CataGA Le curve, sebbene con uno scarto signi cativo fra il numero di test giunti a convergenza ad una data generazione, ma- nifestano comportamenti simili. Entrambe mostrano una grande capa- cità esplorativa della funzione, ma di contro risentono di una limitata capacità di convergenza.
Figura 4.4: Confronto fra le curve cumulative dei diversi algoritmi • DAGA il daga risulta essere una combinazione degli aspetti miglio-
ri delle due curve precedenti: ha un'elevata capacità esplorativa senza però deprimere eccessivamente la velocità di convergenza. Ciò è evi- denziato dal fatto che non risente di drift e giunge a convergenza nella quasi totalità dei casi.
Le nuove funzioni generano nuove soluzioni uniformemente distribuite sul- lo spazio dei modelli. Ciò comporta che il numero di modelli totale valutato, mostrato in gura 4.5, sia maggiore rispetto al numero di modelli valutato da un GA lanciato con gli stessi parametri. Ciononostante le curve CompGA e DAGA mostrano un numero medio (mediato sul numero di test) di modelli generati inferiore rispetto alle altre curve, a causa della maggiore velocità di convergenza. In altri termini, la maggiore quantità di tentativi a convergen- za in un numero limitato di generazioni ha fatto sì che il numero totale di individui generati sia notevolmente inferiore, a causa dell'uscita anticipata dalle iterazioni dell'algoritmo.
Figura 4.5: Numero medio di modelli generati dai vari algoritmi
Figura 4.6: Errore medio degli algoritmi
La gura 4.6 è conseguenza dei dati della gura 4.4: il maggiore numero di test falliti per le curve GA, ed in misura minore NGA e CataGA, in uiscono sui valori medi del valore della funzione oggetto del cromosoma migliore della popolazione in una data generazione. Pertanto le curve corrispondenti alle
funzioni sopracitate hanno valori peggiori.
# di test a convergenza per GA 32 # di test a convergenza per NGA 61 # di test a convergenza per CompGA 93 # di test a convergenza per CataGA 75 # di test a convergenza per DAGA 99 # di medio di modelli generati per GA 2467 # di medio di modelli generati per NGA 1669 # di medio di modelli generati per CompGA 1384 # di medio di modelli generati per CataGA 1665 # di medio di modelli generati per DAGA 1399
Schwefel 4d
Nell'ottica di analizzare in maniera approfondita gli algoritmi in esame è stato eseguito un ulteriore test su una funzione Schwefel a 4 dimensioni. L'aumento della dimensione aumenta la complessità dell'inversione in maniera più che lineare, rendendo più evidenti le dinamiche ed i comportamenti propri di ogni algoritmo.
Parametri valori Dimensione del problema 4 # Popolazione iniziale 76 # Sottopopolazioni 2 # Massimo di generazioni 700 Tasso di selezione 0.8 Parametri DAGA # Rimpiazzi 5 probabilità catastrofe 0.2
Tabella 4.5: Parametri del test
Anche in questo caso i parametri scelti sono estremamente ridotti per il problema in esame. Si può notare in tabella 4.5 come rispetto al caso 2d (tabella 4.3) i parametri siano stati incrementati di un fattore ben maggiore a 2.
La gura 4.7 evidenzia le dierenti proprietà delle funzioni esaminate: • GA In 31 casi su 100 si osserva una convergenza verso il minimo glo-
bale dell'algoritmo estremamente rapida. Ciò probabilmente è dovuto ad una scelta favorevole dei modelli costituenti la popolazione iniziale, ovvero alla generazione di un modello nella valle del minimo globale durante le prime generazioni dell'algoritmo. In tutti gli altri casi si as- siste ad un fenomeno di drift che inibisce totalmente le sue potenzialità esplorative.
• NGA Anche in questo caso si osserva una dinamica sostanzialmen- te uguale alla curva corrispondente al GA. Si nota un miglioramento marginale dovuto ad una limitata capacità di far fronte al drift genetico.
Figura 4.7: Confronto fra le curve cumulative dei diversi algoritmi • CompGA Ha una velocità di convergenza estremamente limitata, ma
la grande capacità esplorativa garantisce una crescita costante della curva soprattutto sulle ultime generazioni. L'algoritmo non risente di drift genetico, ma impiegherebbe un numero di generazioni molto grande per giungere a convergenza su tutti i test.
• CataGA La curva ha una buona velocità di convergenza sulle prime generazioni. Nelle generazioni successive ha zone a derivata nulla per periodi prolungati. Ciò probabilmente è dovuto a generazioni in cui non avvengono catastro . In questi intervalli l'algoritmo si comporta in maniera analoga ad un NGA, e pertanto è soggetto a forti rallentamenti. • DAGA il daga risulta essere una combinazione degli aspetti migliori delle due curve precedenti: ha un'elevata capacità esplorativa (come CompGA) senza però deprimere eccessivamente la velocità di conver- genza (come CataGA).
Figura 4.8: Numero medio di modelli generati dai vari algoritmi Come nel caso 2d è ben evidenziata la capacità del DAGA di giungere a convergenza: tale fatto permette all'algoritmo di terminare dopo poche iterazioni, valutando quindi pochi modelli.
CompGA ha un comportamento analogo a DAGA nelle prime iterazioni, discostandosi da questo quasi subito a causa della sua incapacità di giungere a convergenza.
Figura 4.9: Errore medio degli algoritmi
Come nel caso precedente il DAGA ha una maggiore capacità esplorativa, che comporta un miglior tness medio dei cromosomi migliori.
# di test a convergenza per GA 31 # di test a convergenza per NGA 38 # di test a convergenza per CompGA 36 # di test a convergenza per CataGA 51 # di test a convergenza per DAGA 98 # di medio di modelli generati per GA 3000 # di medio di modelli generati per NGA 2836 # di medio di modelli generati per CompGA 4448 # di medio di modelli generati per CataGA 2609 # di medio di modelli generati per DAGA 2125