 .dsy:it. ~ nous's journal ~ Riassunto... |
|
|
|
» |
Visto che va di moda esporsi...ecco il mio riassuntino :
Questa tesi si svolge nell'ambito dei modelli genetici realizzati da algoritmi adattivi e stocastici analizzati col metodo di Vose (dal nome del matematico della Michigan University che lo ha ideato). Si studia il particolare modello genetico BCCG (ideato dai professori Bertoni, Campadelli, Carpentieri e Grossi) e si applicano i risultati a problemi di ottimizzzazione.
Dopo una introduzione in cui si analizzano gli AG mediante la tecnica di Holland e i suoi limiti, si illustrano le motivazioni all' approccio di tipo matematico di Vose, che condensando in operatori matematici tutti i dettagli degli AG permette, una volta costruito il modello, di dimostrare teoremi riguardanti le proprietà di tali operatori. Successivamente si presentano le basi per la comprensione della teoria completa di Vose, ossia i lavori da lui compiuti con i professori Liepins e Nix, e finalmente si fornisce un sunto della teoria di Vose per RHS (Random Heuristic Search) e i teoremi più importanti da lui dimostrati.
Un limite computazionale del modello di Vose nel caso di popolazioni infinite, è il numero degli stati, che sono rappresentati da vettori in R^2^l, dove l è la lunghezza del cromosoma. Il modello BCCG utilizza un particolare operatore di ricombinazione che permette la riduzione degli stati, che vengono rappresentati da vettori in R^l.
Questo metodo riesce a conservare tutti gli elementi del SGA (Simple Genetic Algorithm) di Vose risultando al contempo computazionalmente eseguibile. L'applicazione di questo metodo ai problemi di ottimizzazione è non vincolata, in quanto vengono esplorate tutte le regioni dell'ipercubo delle possibili soluzioni al problema.
Allo scopo di avere una esecuzione dell'algoritmo vincolata al tipo di problema di studio è stato infine introdotto un polinomio caratteristicoad estendere il metodo BCCG permettendo l'esplorazione delle sole zone dell'ipercubo in cui è lecito attendersi siano le soluzioni del problema. Questo polinomio deve essere definito in funzione del problema trattato rendendo l'esecuzione dell'AG modellabile sul problema.
La correttezza del metodo presentato è stata testata su alcuni problemi NP-Completi su grafi ed i risultati sono stati confrontati con quelli ottenibili tramite metodi greedy.
Gli algoritmi sono stati scritti in ANSI C e testati su un Celeron 800 con OS Red Hat Linux 9.0
|
|
|
 mood:
(none) |  now playing: (none) |
| Commento di 0m4r |
20-01-2004 14:40 |
|
|
» |
secondo me la tua tesi spacca! |
|
| Commento di nous |
20-01-2004 14:40 |
|
|
» |
Secondo me fa cagare, sarà che c'è poco sviluppo e troppa teoria :) |
|
| Commento di 0m4r |
20-01-2004 14:40 |
|
|
» |
>>Secondo me fa cagare, sarà che c'è poco sviluppo e troppa teoria
ah..ok scusa:
secondo me la tua tesi fa cagare, poco sviluppo e troppa teoria ;P |
|
|
|
|
.dsy:it. ~ nous's journal ~ Riassunto...
mood:
(none) | 
now playing: (none)