PDA

Visualizza la versione completa : Algoritmo ibrido GA+TS


mbistato
05-08-2011, 08:14
Salve a tutti!
Mi sono appena registrato in questo forum visto che mi diletto a programmare in C++ e vorrei ricevere utili consigli su quello che sto per dirvi. Mi sto occupando di realizzare un codice ibrido che consiste nell'assemblare 2 algoritmi euristici molto importanti per trovare il massimo di una funzione a 2 variabili: Algoritmo Genetico (GA) e Tabu Search (TS). Visto che sono argomenti particolari volevo sapere se qualcuno di voi ci ha mai lavorato con questa roba e se potrebbe darmi degli spunti per portare avanti il mio lavoro. Allego in questo messagio il flow-chart che sto seguendo in modo da farvi capire di che si tratta.

Ciao e grazie in anticipo!

alka
05-08-2011, 15:59
Originariamente inviato da mbistato
volevo sapere se qualcuno di voi ci ha mai lavorato con questa roba e se potrebbe darmi degli spunti per portare avanti il mio lavoro.

Non è chiaro che spunti cerchi, né quale sia il problema, né quale sia la domanda o il dubbio specifico.

Leggi il Regolamento (http://forum.html.it/forum/showthread.php?s=&threadid=973887).

mbistato
05-08-2011, 22:08
Ciao!
Ok entro nei dettagli. Devo realizzare un codice ibrido usando l'algoritmo genetico e il Tabu Search per trovare il massimo della funzione t=-x^2-y^2+5. Il codice, in una prima parte, consiste nel generare una popolazione random fatta di individui chiamati cromosomi, ordinarli in base alla fitness (ovvero il valore della funzione calcolata nel punto) e applicarvi le operazioni di crossover e mutation in modo da generare ad ogni passo una nuova popolazione che si avvicini sempre più al massimo ottimale (questo è il GA= Genetic Algorithm). La seconda parte del codice consiste invece nell'implementare il Tabu Search cioè quella parte di programma che evita di far convergere la ricerca in un massimo locale e fa in modo di espanderla considerando pure altri punti del piano. Esso non deve far altro che conservare (in una Tabu list appunto) tutti i migliori valori trovati ad ogni iterazione e mantenerli memorizzati fino alla scadenza di un certo tempo chiamato TENURE. Un punto viene dichiarato tabu (cioè viene inserito nella tabu list) se è sostanzialmente distante da tutti i punti già presenti nella tabu list (nel programma ho imposto che la distanza minima tra i candidati ad essere tabu e i punti già presenti nella tabu list deve essere almeno S. Se le distanze sono minori di S i punti candidati non vengono inseriti nella tabu list perchè considerati troppo vicini ai punti già visitati.
Non so se ho reso l'idea ma questa che ho presentato è una panoramica generale di quello che ho implementato. Purtroppo non posso scriverti qui il codice perchè lo visualizza senza andare a capo avendo cosi una pessima visualizzazione dello stesso. Posso inviarti una mail con il codice sorgente scritto in DEV C++.

Il mio indirizzo e-mail è mbistato@hotmail.it


Il problema è che il programma si imballa quando tento di eseguirlo e non so da dove realmente deriva la causa. Mi potresti dare qualche dritta?

alka
08-08-2011, 15:54
Non è possibile affrontare la questione in questi termini, con una problematica così generale, un problema così specifico, le risposte via email e il codice da analizzare completamente.

Se hai un problema che riguarda una parte specifica del codice, sviluppata con un determinato linguaggio, riporta i dettagli dell'errore e la parte di codice interessata aprendo una discussione seguendo le indicazioni del Regolamento (http://forum.html.it/forum/showthread.php?s=&threadid=973887).

In caso contrario, non è possibile fornirti un aiuto adeguato.

Loading