Soft Computing - Testi delle esercitazioni

Esercizio 1

Sia dato il seguente problema di ottimizzazione:

dati tutti i numeri naturali compresi tra 0 e 2¹²-1 (= 4095), trovare quello la cui rappresentazione binaria contiene il maggior numero di cifre uguali a 1.

Si richiede di implementare due metodi per risolvere questo problema tramite l’algoritmo Hill Climbing:

· Nel primo metodo due soluzioni i e j vengono considerate vicine se |i-j| = 1

· Nel secondo metodo due soluzioni i e j vengono considerate vicine se le rappresentazioni binarie di i e j differiscono di un solo bit.

Per ognuno di questi due metodi, si effettuino 50 esecuzioni (run) indipendenti dell’algoritmo Hill Climbing. Ogni run deve essere eseguito per un numero di iterazioni massimo pari a 5000.

Successivamente, per ognuno di questi metodi, si calcolino le fitness media e mediana sui 50 run per ognuna delle iterazioni eseguite. Per semplificare questo calcolo si consiglia, una volta trovata una soluzione ottima (sia essa un ottimo locale o globale), di non interrompere il run, ma di portarlo comunque fino al compimento dell’iterazione 5000, restituendo sempre la soluzione ottima come soluzione corrente in tutte le iterazioni successive alla determinazione di essa (in alternativa, occorre fare attenzione al calcolo della media e della mediana).

Inoltre, per ognuno dei due metodi, si conti quante volte la soluzione ottima globale è stata trovata sui 50 run eseguiti.

In base ai risultati ottenuti, si traggano le opportune conclusioni sulle differenze tra i due metodi implementati.

Esercizio 2

Si generalizzi il problema di ottimizzazione del precedente esercizio in modo tale che lo spazio di ricerca sia composto da tutti i numeri naturali compresi tra 0 e 2^k-1, con k parametro prefissato.

Si implementi un metodo per risolvere questo problema tramite l’algoritmo di Simulated Annealing, considerando due soluzioni i e j come vicine se |i-j| = 1.

Si consideri il caso in cui k = 5. Si cerchi, tramite una serie di esperimenti, un settaggio dei parametri che renda le prestazioni del Simulated Annealing “migliori possibili”.

Successivamente, sempre per il caso di k = 5, si eseguano 50 run indipendenti dell’Hill Climbing (sempre considerando due soluzioni i e j come vicine se |i-j| = 1) e 50 run indipendenti del Simulated Annealing con la stessa struttura di vicinato. Per entrambi gli algoritmi, si esegua ogni run fino all’iterazione 5000. In base ai risultati ottenuti in questi 50 run, si esegua un confronto sperimentale tra i due algoritmi, calcolando media e mediana della fitness per ognuna delle iterazioni eseguite e contando il numero di run in cui è stata trovata la soluzione ottima globale.

Infine, si cerchi di stabilire, sempre tramite una serie di esperimenti, come variano le prestazioni del Simulated Annealing all’aumentare del valore del parametro k.

Esercizio 3

Tentare di migliorare le performance del Simulated Annealing implementato nell’Esercizio 2, tramite l’uso del concetto di memoria, ispirandosi ad uno dei possibili usi del concetto di memoria fatto dal Tabu Search. Si quantifichi il miglioramento ottenuto eseguendo 50 run indipendenti di questo nuovo algoritmo e confrontando i risultati con quelli dell’algoritmo implementato nell’Esercizio 2.

Esercizio 4

Utilizzare gli Algoritmi Genetici per risolvere il seguente problema di ottimizzazione:

Sono date 10 carte, numerate con numeri i naturali da 1 a 10 (e ognuna con un numero diverso dalle altre).

Partizionare queste 10 carte in due mazzi tali che:

· La somma dei numeri delle carte del primo mazzo sia il più possibile vicina a 36.

· Il prodotto dei numeri delle carte del secondo mazzo sia il più possibile vicino a 360.

Una volta implementato l’Algoritmo Genetico, si eseguano alcuni test finalizzati a determinare un settaggio dei parametri “opportuno”. Infine, se ne eseguano 50 run indipendenti e si dica quante volte, su questi 50 run, l’Algoritmo Genetico è stato in grado di trovare una soluzione ottimale per questo problema.

Esercizio 5

Implementare la tecnica del fitness sharing per il problema dell’esercizio 4. Successivamente, effettuare un confronto sperimentale, sul quel problema, tra un Algoritmo Genetico semplice e un Algoritmo Genetico che usa il fitness sharing. Per effettuare questo confronto sperimentale si usino le misure e le metodologie viste a lezione.

Esercizio 6

La funzione di Rastrigin è una funzione che riceve come argomento un vettore n-dimensionale di numeri reali x (dove, per ogni i = 1, 2, ..., n, la componente i-esima x_i del vettore x assume valori all’interno dell’intervallo [-5.12, 5.12]) e restituisce un numero reale scalare.

La formula della funzione di Rastrigin è visualizzabile qui (dove normalmente si usa A = 10).

Trovare (o approssimare) il vettore x (con componenti comprese all’interno dell’intervallo [-5.12, 5.12]) che minimizza il valore della funzione di Rastrigin tramite il Particle Swarm Optimization, per diversi valori della dimensione n, concentrandosi particolarmente sul caso n = 2.

Alcune note sulla funzione di Rastrigin

Esistono alcune proprietà note della funzione di Rastrigin. In particolare:

· L’ottimo globale è x = [0, 0, ..., 0] e la fitness ottima (cioè minima) è f(x) = 0.

· La funzione contiene svariati ottimi locali uniformemente distribuiti all’interno dell’ipercubo che ne costituisce lo spazio di ricerca (si ricorda che lo spazio di ricerca è formato tutti i vettori x dove, per ogni i = 1, 2, ..., n, la componente i-esima x_i del vettore x assume valori all’interno dell’intervallo [-5.12, 5.12]).

Inoltre, esistono vari siti web che forniscono una documentazione, e in alcuni casi anche un’implementazione, della funzione di Rastrigin. Ad esempio:

· Alla pagina http://www-optima.amp.i.kyoto-u.ac.jp/member/student/hedar/Hedar_files/TestGO_files/Page2607.htm si trova una rappresentazione grafica della funzione per n = 2 e un’implementazione per MatLab.

· All’indirizzo http://www.google.it/url?sa=t&source=web&cd=6&ved=0CEEQFjAF&url=http%3A%2F%2Fcs.gettysburg.edu%2F~tneller%2Fresources%2Fsls%2Fcode%2FRastrigin.java&rct=j&q=rastrigin%20function%20implementation&ei=4JLjTImCF9C7hAeF5cSTDQ&usg=AFQjCNG4R_DH_bZ_L0dQ1VOczGncslHZNA&cad=rja si trova un’implementazione in Java.

· Alla pagina http://www.math.ntu.edu.tw/~wwang/cola_lab/test_problems/multiple_opt/multiopt_prob/Rastrigin/Rastrigin.htm si trova sia un’implementazione per MatLab che un’implementazione in C.

· La pagina http://tracer.lcc.uma.es/problems/rastrigin/rastrigin.html contiene una breve documentazione della funzione, con la citazione di due riferimenti bibliografici per eventuali approfondimenti.

· La pagina di YouTube http://www.youtube.com/watch?v=Xb9KmhASYT4 contiene un video in cui si vede la rappresentazione in 3D della funzione (quindi nel caso n=2) che viene fatta ruotare, in modo da poterne osservare alcune proprietà.

Esercizio 7

Si considerino i seguenti pacchetti public domain di Programmazione Genetica:

· ECJ, implementato in Java: http://cs.gmu.edu/~eclab/projects/ecj/

· GPC++, implementato in C++: http://www.cs.ucl.ac.uk/staff/W.Langdon//ftp/weinbenner/gp.html

· GPLab, implementato in MatLab: http://gplab.sourceforge.net/

Per chi non disponesse di un ambiente Linux, e quindi fosse impossibilitato all’utilizzo di GPC++, si consiglia di considerare uno dei seguenti tools, anch’essi implementati in C++:

· LIL-GP: http://garage.cse.msu.edu/software/lil-gp/

· EO: http://eodev.sourceforge.net/

Oppure si può anche considerare il tool (la cui ultima versione è implementata in Java):

· Tiny GP: http://cswww.essex.ac.uk/staff/rpoli/TinyGP/

Per tutti (o se non è possibile, almeno per due a vostra scelta tra) questi pacchetti, si tenti di capirne il funzionamento a livello utente. Successivamente, si tenti di eseguire qualche run di Programmazione Genetica:

· Per il problema Artificial Ant on the Santa Fe trail (che dovrebbe essere implementato in tutti e tre i pacchetti).

· Per la regressione simbolica, con la semplice funzione target monodimensionale x⁴+x³+x²+x, usando come fitness cases i 100 numeri naturali compresi tra 0 e 99 e come fitness l’errore quadratico medio tra valori calcolati e valori target (anche questo problema, o altrimenti un problema molto simile, dovrebbe essere già implementato in tutti e tre i pacchetti).

· Per la regressione simbolica con la stessa funzione target e gli stessi fitness cases del punto precedente, ma usando come funzione di fitness il coefficiente di correlazione di Pearson tra valori calcolati e valori target (per un’introduzione estremamente banale del coefficiente di correlazione di Pearson, si veda ad esempio: http://www.childrens-mercy.org/stats/definitions/correlation.htm).

Una volta effettuati questi test, si tenti di fare un confronto critico tra i pacchetti ECJ, GPC++ e GPLab (o tra i pacchetti studiati), cercando di rispondere, in maniera informale, alle seguenti domande:

· Quale di questi pacchetti è il più facile/veloce da imparare a usare?

· Quale di questi pacchetti consente di apportare delle modifiche alla versione base in modo più facile/veloce (supponendo ad esempio di voler modificare un operatore o la funzione di fitness)?

· Quale di questi pacchetti è computazionalmente più efficiente?

· Quale di questi pacchetti consente di modificare i parametri fondamentali dell’algoritmo nel modo più facile, veloce e intuitivo?

· Quale di questi pacchetti restituisce i risultati dei run in forma più chiara, leggibile e facilmente interpretabile?

· Quale di questi pacchetti consente di fare il numero più elevato di operazioni (come modifiche, calcolo di statistiche sui risultati dei run, etc.)?

Infine, rispondete in maniera generale alla seguente domanda, cercando di motivare:

· Quale di questi pacchetti è il vostro preferito rispetto agli altri?

Nel rispondere alle domande precedenti, naturalmente, potete farvi guidare dai vostri personali gusti di programmazione.