Tabu search

Fai una domanda Tutte le categorie
irelimax
irelimax
17 set 2011, 12:39
salve a tutti! qualcuno potrebbe indirizzarmi per l'utilizzo del tabu search per la ricerca di max e min d una funzione? di teoria se ne trova tanta sul web, ma avrei bisogno di qualche esempio per capire come utilizzarlo. Spero qualcuno possa aiutarmi!!!!!
Risposte
hamming_burst
hamming_burst
9 ott 2011, 20:03
"irelimax":

tutto risolto! avevo posizionato nel posto sbagliato le stampe degli elementi. adesso funziona :D


Ottimo :-)

Ora non so che modifiche avete fatto, e se avete migliorato anche l'algoritmo ma questo:

         if(j==0){
            cp_chrom(&(population[0]),mac);
   
         }

si può cancellare, basta inizializzare 
AC=0;

e da lo stesso risultato :-)

visto che usi Dev-C++ :cry:

se usi quel compilatore, fai piangere apatriarca :-D
irelimax
irelimax
10 ott 2011, 10:22
"hamming_burst":


it_FP = DIM_POP-1;

	
		TABU_TIME = (2*ELITIST)+1;
		DIM_TL = 2*TABU_TIME;

		
		mac = malloc(sizeof(chrom));
		
		....


		srand(time(NULL));

		evpop(population);                       //initialise pop current

				
		AC = ((int)rand()%num)+1;

		for(int j=0;j<num;j++)                       // loop num times
		{
			//printf("\ni = %i\n",j);             // print the iteration number

			insertion_fit_sort(population);           //sort chromosomes
			crossover(population);             //cross over to get children chromes
			mutation(population);              //mutate

			//basta cercare il massimo non serve ordinare.
			insertion_fit_sort(population);


			if(j==0){
				cp_chrom(&(population[0]),mac);
	
			}
			if(AC==0){		
				if(population[0].fit > mac->fit){
					cp_chrom(&(population[0]),mac);
		
				}
				else{
					cp_chrom(mac,&(population[0]));
				}
				AC = ((int)rand()%num)+1;
	
			}

			if(num-TABU_TIME>=j){

				add_tl(&(population[0]),TL,TABU_TIME);

				cp_chrom(&(population[it_FP]),&(population[0]));
				it_FP--;
						
			}
			
			if(time_zero(TL)){
				add_al(delete_tl(TL),AL);
			} 


			k=0;

			if(!emptyp(TL)){
				while(k<DIM_POP){

				 
					 f=TL->head;
					 while(f!=TL->tail){


						if(DISTANCE(&(population[k]),&(TL->tabu_l[f].ch))){ //se la distanza è minore di R inserisci elemento in AL
							//printf("distance\n");
							if(emptyp_al(AL)){ //se la AL è vuota

							  cp_chrom(&(population[it_FP]),&(population[k]));
							  it_FP--;
							/*                  sostituire il cromosoma ella popolazione attuale con quello di fitness minore degli antenati */
							/*                  (per ogni iterazione si decresce di indice)*/

							}
							else{
							  cp_chrom(delete_al(AL),&(population[k]));
				
							}

						}
				  


					 f=next_tl(f,TL);
					 }

				 k++;

				}
			}
		

			time_zero_TT(TL);
			it_FP = DIM_POP-1;
			AC--;
		

			srand(time(NULL)+j);
		}



Ritorno un momento a quello che hai scritto in qualche post fa in particolare vorrei commentare la seguente:
if(num-TABU_TIME>=j){
....
}

perchè decidi di limitare l'inserimento di elementi nella tabu list?
inoltre mi accorgo che con un num<= TABU_TIME il programma va in crash...
Un'ultima cosa: quando dobbiamo eliminare un elemento dall'aspiration list (poichè piena) perchè decidiamo di eliminare quello nella posizione tail ovvero il più recente e non quello più vecchio?
credi che i primi punti tabu e dunque i primi punti inseriti nella aspiration list siano quelli più buoni per uscire da probabili cadute nei massimi locali?
hamming_burst
hamming_burst
10 ott 2011, 12:13
Ciao,
"irelimax":

perchè decidi di limitare l'inserimento di elementi nella tabu list?

per queste considerazioni


inoltre mi accorgo che con un num<= TABU_TIME il programma va in crash...

mmm questo non saprei, penso perchè non hai messo dei controlli al posto giusto, io ho provato ma a me non crasha :-)
Ma poi non ha senso fare iterazioni < del tabu_time, che ricerca locale fai? Metti tabu dei punti potenzialmente ottimi per un tempo, ma se le iterazioni sono minori di questo tempo, l'aspiration_list è sempre vuota perchè non scade mai questo tempo...

Le iterazioni (num) deve avere queste caratteristiche non un numero a caso:
- num >= TABU_TIME
- ottimale num>=3*TABU_TIME
- multipli di TABU_TIME, sempre con caratteristica num >= 2*TABU_TIME

è tutto spiegato in quel post linkato, se hai dubbi in merito a questo te lo rispiego ma è valido in questo algoritmo perchè si utilizzano cose particolare non molto standard (aspiration list) :-)


Un'ultima cosa: quando dobbiamo eliminare un elemento dall'aspiration list (poichè piena) perchè decidiamo di eliminare quello nella posizione tail ovvero il più recente e non quello più vecchio?
credi che i primi punti tabu e dunque i primi punti inseriti nella aspiration list siano quelli più buoni per uscire da probabili cadute nei massimi locali?

no. Come ho già scritto l'aspiration_list è meglio considerare di farla come Lista dinamica, e non come vettore finito, o nel caso fare la lunghezza = num, ma così si inseriscono possibili bug non prevedibili da parte dell'utente :-)
irelimax
irelimax
10 ott 2011, 12:54
"hamming_burst":
Ciao,
Come ho già scritto l'aspiration_list è meglio considerare di farla come Lista dinamica, e non come vettore finito


non capisco cosa intendi per lista dinamica. l'aspiration list ha una dim massima pari a DIM_LIST ovvero ha la stessa capienza della tabu list. per quello che dici tu ,allora, anche la tabu list è una lista dinamica...
hamming_burst
hamming_burst
10 ott 2011, 13:17
"irelimax":
non capisco cosa intendi per lista dinamica. l'aspiration list ha una dim massima pari a DIM_LIST ovvero ha la stessa capienza della tabu list.

se ti ricordi ne avevan parlato all'inizio su questa differenza comunque:

- lista dinamica
- vettore circolare

per quello che dici tu ,allora, anche la tabu list è una lista dinamica...


la TL è un vettore circolare, avendo un tabu_time finito si può prevedere quando sarà pieno, percià 2*Tabu-time è un limite superiore, questo vuol dire che non sarà MAI pieno.

la AL non puoi prevedere nulla, perchè dipende dai punti che si valutano e dalla DISTANCE, si può svuotare ad una iterazione od essere sempre piena, se è piena si eliminano punti valuati in precedenza come migliori. Per questo è meglio scirverla come linked-list. Mi pare di non avertela scritta così proprio perchè non conoscevi questa tipologia e per tua semplicità di comprensione :-)
irelimax
irelimax
10 ott 2011, 14:37
:smt023
irelimax
irelimax
12 ott 2011, 08:20
RINGRAZIO pubblicamente hamming_burst per l'enooooorme pazienza che ha avuto nei miei confronti!! e anche apatriarca per l'interessamento! :):) spero adesso d aver capito un po più di programmazione (:D) anche se decisamente questa non sarà la mia strada:) saluto tutti cn affetto e spero un giorno di poter ricambiare, magari sul mio campo però!!:D:D byeeee:):)
hamming_burst
hamming_burst
12 ott 2011, 12:43
:-D E' stato un piacere aiutarti, spero ti sia utile :-)
un bel problema da risolvere con un ibrido molto affascinante :D

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.