Tabu search

[irelimax]

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!!!!!

[irelimax]

Questo è il file principale dove ho incluso tutti gli header

#include<stdio.h>          //to use the printf function
#include<conio.h>         //to use the getche function
#include<stdlib.h>
#include<math.h>         //to use the rand function
#include<time.h>
//GA FUNCTION
#include "generatePoint.h"
#include "generateParam.h"
#include "evpop.h"    
#include "calculateFitness.h"
#include "insertion_fit_sort.h"
#include "crossover.h"
#include "mutation.h"
#include "DISTANCE.h"
#include "cp_chrom.h"
#include "deinit.h"

//TABU_LIST FUNCTION
#include "next_tl.h"
#include "init_tl.h"
#include "emptyp.h"
#include "fullp.h"
#include "add_tl.h"
#include "delete_tl.h"
#include "time_zero_TT.h"
#include "time_zero.h"

//ASPIRATION_LIST FUNCTION
#include "next_al.h"
#include "init_al.h"
#include "emptyp_al.h"
#include "fullp_al.h"
#include "add_al.h"
#include "delete_al.h"


#define DIM_POP 100
#define R 0.5               //minimum distance between tabu point and neighbour
#define ELITIST 5      // the number of chromosomes to keep (using the elitism selection concept)
#define PAR_MIN -15.0      // studying the function into established interval [-15, 15]
#define PAR_MAX 15.0
#define RESOLUTION 0.1      // minimum change in the parameter value

typedef enum {FALSE,TRUE} boolean;

typedef struct             // creating the chrom structure
{
   double point[2];  
   double fit;
}chrom;

typedef struct{
   int head;
   int tail;
   int DIM;
   chrom* aspiration_l;   //pointer to the struct aspiration_l
}aspiration_list;


typedef struct{
   chrom ch;
   int tabu_time;
}tabu_el;

typedef struct{
   int head;
   int tail;
   int DIM_LIST;
   tabu_el* tabu_l;
}tabu_list;



int main()                          // the main function
{
   int num;                      // num is the no. of iterations
   int i;
   chrom* FP = (chrom*)malloc(sizeof(chrom)*DIM_POP);
   int TABU_TIME; //is the smallest integer not less than (DIM_POP-2)/50
   int DIM_TL;
   int f=0;
   int k = 0;
   
   int it_FP = DIM_POP-1;
   int aspiration_criteria= ((int)rand()%num)+1;  //aspiration criteria
   int AC = aspiration_criteria; 

   printf("\nMaximum of the function z = -x^2-y^2 + 5 ");                         // introduction to the program
   
   do
   {
      printf("\nPlease enter the no. of iterations:  ");
      scanf("%i",&num);                           // enter the no. of iterations in num
   }while(num<1);

   chrom* population = (chrom*)malloc(sizeof(chrom)*DIM_POP);
   chrom* max = (chrom*)malloc(sizeof(chrom));  //max saved at the first iteration
   TABU_TIME = ((int)ceil(num/50))*36; //is the smallest integer not less than (DIM_POP-2)/50
   DIM_TL = (int)ceil(num/2);

   tabu_list* TL = init_tl(DIM_TL);  //declaration and initialization of TL
   if(TL==NULL){
      exit(0);
   }

   //la dimensione conta poco della AL, non la si riempirà mai, perchè è limitata dal TABU_TIME=0
   aspiration_list* AL = init_al(DIM_TL);
   if(AL==NULL){
      exit(0);
   }
   
   srand(time(NULL));


   evpop(population);                       //initialise pop current

   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
     
   insertion_fit_sort(population);
   
   if(j==0){
            cp_chrom(&(population[0]),max);
   
         }
         if(AC==0){      
            if(population[0].fit > max->fit){
               cp_chrom(&(population[0]),max);
      
            }
            else{
               cp_chrom(max,&(population[0]));
            }
            AC = aspiration_criteria;      //un'altra possibilità è utilizzare un valore random%num
   
         }
   
   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;

      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
               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--;
   
insertion_fit_sort(population);           //sort chromosomes

for(k=0;k<DIM_POP;k++)
          printf("\nSorting:population[%i] fitness=%lf",k,population[k].fit);           //printing the result

         printf("\n");

   printf("\nTHE MAXIMUM OF THE FUNCTION IS:(%lf, %lf)", population[0].point[0], population[0].point[1]);
      printf("\tfitness = %lf", population[0].fit);

   printf("\nPress any key to end ! \n");
   getche();                                        // wait for a character from the keyboard to end

   //return 0;
}
}

ho messo al posto giusto tutte le modifiche che hai apportato?

adesso compilando gli questo file (ovviamente i file header sono stati tutti creati) mi da errore in

#include "evpop.h"

e precisamente non riconosce il tipo chrom nei parametri passati. Ma perchè?

[apatriarca]

[OT] Coma mai hai incluso tutti i file header necessari in un singolo file? È precompilato? Normalmente si preferisce infatti ridurre al minimo le librerie incluse nei diversi file in modo da ridurre i tempi di compilazione. A meno ovviamente di usare header precompilati, ma in tal caso avresti dovuto inserire solo librerie che non dovrebbero cambiare. [/OT]

e precisamente non riconosce il tipo chrom nei parametri passati. Ma perchè?

chrom è stato definito solo più avanti nel file e non è quindi visibile all'interno di "evpop.h".

[irelimax]

non ho mai modularizzato un codice C e per questo pensavo che tutti gli header si richiamassero all'interno del file principale dove metto il main. Allora dove dovrei includerli?

[apatriarca]

Idealmente, all'interno di un file sorgente devi includere solo le librerie che usi (che contengono quindi i prototipi delle funzioni o le dichiarazioni dei tipi che ti servono). Per risolvere il tuo problema, la soluzione solitamente adottata è quella di dichiarare il tipo chrom all'interno di un file header che andrai poi ad includere all'interno di "evpop.h".

[irelimax]

pensavo di aver capito dal tuo ultimo messaggio ma mettendolo in pratica la cosa è sembrata più complicata di quanto non lo fosse. è un casino ed è impossibile spiegartelo. mi servirebbe un tuo indirizzo mail per allegarti tutto il progetto perchè è formato da molti file header (uno per ogni funzione implementata)

[apatriarca]

La divisione di un progetto nei diversi file dovrebbe in generale seguire una qualche "separazione logica" delle funzioni e dei tipi all'interno del design complessivo. In ogni "modulo" (costituito dal file sorgente e dal corrispondente file header) dovrebbero cioè essere presenti funzioni e tipi che sono in qualche modo collegate. Una corretta modularizzazione del codice porta a diversi vantaggi come:
1. Maggiore facilità a muoversi all'interno del codice sorgente del programma.
2. Maggiore velocità di compilazione.
3. Maggiore semplicità nel riutilizzare parte del codice in progetti diversi.
4. ...
Dividendo però il programma in troppi file (uno per funzione) sei però tornata ad una situazione molto simile a quella di partenza con tutto in un singolo file. Ogni funzione e ogni tipo è infatti separato dagli altri ed è molto difficile comprendere le relazioni tra di essi. Non essendo più chiara la relazione tra le diverse funzioni diventa anche difficile riutilizzare il codice (non è chiaro quali file devono essere presi in considerazione per implementare una qualche funzionalità).. Se avessi invece avuto ad esempio un "modulo" per ogni fase del tuo algoritmo sarebbe stato più semplice navigare all'interno del codice e riutilizzare il codice (anche se probabilmente questa seconda cosa non ti interessa). La prima cosa da fare è quindi rivedere il codice e decidere a quale modulo ogni funzione ed ogni tipo appartengono. Una volta fatto questo si vedrà come scrivere meglio i file header.

[apatriarca]

Con questo post inizio a scriverti come dividerei il programma in moduli. Ne seguiranno altri trattandosi di un argomento abbastanza vasto e non avendo molto tempo per scriverlo tutto subito.

Ci sono per prima cosa due tipi usati in praticamente tutte le funzioni: chrom e boolean. Ha quindi probabilmente senso racchiunderli in un unico file header che verrà incluso in praticamente qualsiasi file sorgente del programma. In questo header avrà anche senso inserire cp_chrom che è anch'essa comunemente usata. Il tipo boolean non è in realtà forse così necessario, si può infatti usare semplicemente un qualche tipo intero o fare uso del tipo booleano presente nel poco supportato standard C99. In effetti, usando i commenti che iniziano con // nel tuo codice stai già facendo riferimento ad una qualche funzionalità del C99 per cui potrebbe aver senso usarne anche altre. Nel C99 il tipo booleano si chiama _Bool e accetta come valori solo 0 e 1, ma è possibile, includendo , usare anche i nomi bool, true e false comuni nel C++. Anche cp_chrom è forse poco utile. cp_chrom(A, B) è infatti del tutto equivalente a *B = *A. L'operazione di assegnamento tra strutture corrisponde infatti alla copia di tutti i campi di una nei corrispondenti campi dell'altra. Usando l'operatore di assegnamento si risolve inoltre il problema di capire qual'è il puntatore all'elemento copiato e quale a quello di destinazione. L'unico modo per stabilirlo nel tuo codice è quello di leggere l'implementazione della funzione. Se ti troverai in futuro a dover scrivere funzioni di questo tipo ti consiglio di rendere costante il puntatore al valore copiato in modo da rendere evidente questa distinzione (preferisco inserire il const dopo il tipo..) e di usare nomi più utili:

void cp_chrom(chrom const * source, chrom* dest);

A questo punto non rimane però molto nel nostro file header. Potrebbe però convenire cercare altre funzionalità comuni a buona parte del codice o riguardanti il tipo chrom. Non mi viene però niente in mente se non, forse, ad una implementazione generica di una lista. Fai infatti uso di due liste nel tuo codice. Ma tale implementazione avrebbe senso inserirla in un "modulo" diverso. Facendo allora uso del tipo booleano del C99 (per usare il tuo tipo basta cambiare una riga), il nostro primo header (che chiamo common.h) diventerebbe:

#ifndef COMMON_H
#define COMMON_H

#include <stdbool.h> // per il tipo bool..

// preferisco dividere il typedef e la dichiarazione in due fasi distinte
typedef struct chrom chrom;
struct chrom {
   double point[2];
   double fit;
};

#endif // not defined COMMON_H

Le righe dell'header che iniziano con # prendono il nome di include guards. Sono sfortunatamente necessarie per impedire che un file header sia inserito più volte. Questo sistema dei file header e file sorgente è tutt'altro che perfetto..

E' a questo punto possibile dividere logicamente il programma nei due algoritmi principali usati, l'algoritmo genetico e la tabu search. Siccome c'è tanto da dire e si è fatto tardi riprenderò i commenti domani. In generale, credo che l'algoritmo genetico vada bene e che in generale possa essere implementato in una sola coppia header/sorgente. La tabu search è secondo me migliorabile: non è a mio parere allo stesso livello di astrazione dell'algoritmo genetico all'interno del main e la maggior parte delle funzioni potrebbe forse essere implementata in modo più generico riducendo il numero totale delle funzioni. Anche questa parte potrebbe forse essere inserita in una singola coppia header/sorgente. A questo punto rimarrebbe poi solo il main che se ne starebbe in un file a parte.

[irelimax]

Buongiorno,

DOMANDA N°1: se nel file header che hai creato tu volessi inserire la funzione cp_chrom, basterebbe mettere al suo interno solo il prototipo della stessa?

DOMANDA N°2: come hai notato, la funzione cp_chrom non viene usata da tutte le funzioni. Se aggiungessi nel file header che hai creato tu tale funzione, e includessi tale libreria nel file sorgente delle funzioni che usano chrom e boolean, ma non cp_chrom, il compilatore mi restituirebbe errore?

Per quanto riguarda la modularizzazione del probramma, comincio a capire come si deve ragionare, per tanto ho notato che molte funzioni hanno in comune il tipo tabu_list, quindi vedo se riesco a creare una libreria che comprende questo e qualche altro tipo e funzione.

Altra domanda: in uno stesso file header posso inserire 2 prototipi di funzione?

[apatriarca]

"irelimax":DOMANDA N°1: se nel file header che hai creato tu volessi inserire la funzione cp_chrom, basterebbe mettere al suo interno solo il prototipo della stessa?

All'interno del file header dovresti inserire solo il prototipo della funzione. Ovviamente, dovresti inserire anche l'implementazione da qualche parte. Normalmente l'implementazione delle funzioni il cui prototipo è inserito in un qualche header si inseriscono in un file sorgente con lo stesso nome ed estensione .c. Per cui in questo caso dovresti crearti un file chiamato "common.c" e inserirci all'interno l'implementazione della funzione. Come ho però già detto, credo che sia meglio usare semplicemente l'assegnamento invece di una funzione in questo caso.

DOMANDA N°2: come hai notato, la funzione cp_chrom non viene usata da tutte le funzioni. Se aggiungessi nel file header che hai creato tu tale funzione, e includessi tale libreria nel file sorgente delle funzioni che usano chrom e boolean, ma non cp_chrom, il compilatore mi restituirebbe errore?

È in realtà decisamente normale non usare tutti i tipi e le funzioni di un file header. Pensa ad esempio alle librerie standard, quante funzioni credi di usare normalmente tra tutte quelle fornite? Per cui puoi inserire una libreria anche senza usarla.

[code]Per quanto riguarda la modularizzazione del probramma, comincio a capire come si deve ragionare, per tanto ho notato che molte funzioni hanno in comune il tipo tabu_list, quindi vedo se riesco a creare una libreria che comprende questo e qualche altro tipo e funzione.[/quote]
Il mio prossimo post che sarà sulla parte dell'algoritmo genetico potrebbe essere maggiormente utile per comprendere come scrivere un file header e il corrispondente file sorgente.

Altra domanda: in uno stesso file header posso inserire 2 prototipi di funzione?

Puoi inserirne quante ne vuoi, non ci sono limiti.

P.S. Il concetto di modulo non esiste in C, è solo un termine che sto usando per semplicità io. Di fatto in C esistono in un certo senso solo i file sorgenti e i file header vengono inclusi (nel senso copiati) al loro interno durante la prima fase di compilazione.Quello che chiamo modulo si potrebbe quindi più o meno chiamare unità di compilazione, ma direi che i due termini non sono proprio corrispondenti e mi riferisco più che altro ad una divisione logica del programma.

[hamming_burst]

Ho dato un'occhiata all'algoritmo, mancano dei controlli e TABU_TIME e DIM_TL non hanno senso inizializzai in quel modo...quelli che hai usato sono esempi che feci all'inizio per permetterti di usare l'algoritmo.
Tutto il discorso con ELITIST non ha senso in questo modo, e ti sleghi completamente da una definizione di TABU_SEARCH che ha una definizione del tempo, se si utilizza la proibizione fissa.

Da aggiungere sono i controlli se la lista TL diventa vuota con emptyp(), in time_zero(), time_zero_TT() e in un'altra.
Poi è da valutare di sostituire l'aspiration_list scritta con vettore, con strutturazione a Lista dinamica, così facendo si evita di perdere informazione quando la coda diventa piena.

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);
		}

così dovrebbe essere ok
da aggiungere come detto i controlli se la coda TL è vuota in time_zero ...
Alla fine del codice se si vuole si può valutare il massimo tra mac - AL - Population anche se dovrebbe essere sempre in Population
vedi se ti è chiaro, ho messo aspiration_criteria in modo random così si ha più possibilità di reindirizzare la ricerca al massimo
E poi ho messo le condizione in modo corretto, non ho aggiunto NULLA di nuovo sono solo le cose dette per tutti i post

"apatriarca":cp_chrom(A, B) è infatti del tutto equivalente a *B = *A.

questa funzione la ho scritta io (un po' di fretta?), è dovuta al fatto che TL è un vettore di chrom e non un array di puntatori
Quello che dici te non funziona solo se le strutture sono allocate staticamente?

[apatriarca]

Come ti ho già detto, il tuo programma può essere diviso a livello logico nei due algoritmi da te usati: l'algoritmo genetico e la tabu search. I due algoritmi sono indipendenti uno dall'altro e l'unica costante tra i due algoritmi è la struttura chrom usata da entrambi. E' quindi una buona idea quella di dividere questi due algoritmi in files distinti.

In questo post discuterò dell'algoritmo genetico. Questo modulo è composto dalle funzioni evpop, insertion_fit_sort, crossover e mutation che definiscono le fasi principali dell'algoritmo genetico e le funzioni generatePoint, generateParam e calculateFitness che invece determinano come generare casualmente o calcolare le variabili membro della struttura chrom. Di queste funzioni solo il primo blocco viene usato al di fuori del modulo mentre le altre vengono solo richiamate dalle funzioni del modulo stesso. Diciamo quindi che il primo blocco rappresenta l'interfaccia esterna del modulo, mentre le altre solo le funzioni statiche locali all'unità di compilazione. Solo l'interfaccia esterna deve essere inclusa nell'header, le altre funzioni è meglio inserirle solo nel file sorgente. Siccome il numero delle funzioni è ridotto e non vedo alcuna divisione interna che abbia senso, inserirei tutto l'algoritmo genetico in una singola coppia header/sorgente chiamati ga.h e ga.c. I due file dovrebbero apparire più o meno come i seguenti:

// ga.h
#ifndef GA_H
#define GA_H

#include "common.h" // per chrom..

// costanti
#define ELITIST 5 
#define DIM_POP 100

void evpop(chrom* popcurrent);
void insertion_fit_sort(chrom* popcurrent);
void crossover(chrom* popnext);
void mutation(chrom* popnext);

#endif // not defined GA_H

// ga.c
#include "ga.h"

// prototipi delle funzioni locali (nota l'uso di static)
static void generatePoint(double point[2]);
static double generateParam();
static double calculateFitness(double x, double y);

void evpop(chrom* popcurrent)
{
    for (int i = 0; i < DIM_POP; i++) {
        generatePoint(popcurrent[i].point);
        popcurrent[i].fit = calculateFitness(popcurrent[i].point[0], popcurrent[i].point[1]);
      
        printf("\npopcurrent[%i]=(%lf, %lf)", i, popcurrent[i].point[0],popcurrent[i].point[1]);
        printf("\tfitness = %lf",popcurrent[i].fit);
    }
}

void insertion_fit_sort(chrom* popcurrent)
{
    // non c'è alcun bisogno di allocarlo dinamicamente..
    //chrom* temp = (chrom*)malloc(sizeof(chrom));
    //if(temp==NULL) exit(0);
    chrom temp;

    // puoi inizializzare le variabili direttamente quando le dichiari
    int i = 1, j = 0, k;
    while (i < DIM_POP) {
        temp = popcurrent[i];
        j = i;
        while (j >= 1 && popcurrent[j-1].fit < temp.fit) {
          popcurrent[j] = popcurrent[j-1];
          j = j-1;
        }
        popcurrent[j] = temp;
        i++;
    }

    // e quindi neanche di deallocarlo..
    //free(temp);

    //for(k=0;k<DIM_POP;k++)
    //printf("\nSorting:popnext[%i] fitness=%lf",k,popcurrent[k].fit); //printing the result

    //printf("\n");
}


void crossover(chrom* popnext) // crossover function takes a pointer to array of chromes
{
    int i,j;
    for(i = ELITIST; i < DIM_POP; i++) {
        if(rand() % 2 == 0) popnext[i].point[0] = popnext[rand()%DIM_POP].point[0];
        else popnext[i].point[1] = popnext[rand()%DIM_POP].point[1];
        
        popnext[i].fit = calculateFitness(popnext[i].point[0], popnext[i].point[1]);
    }

    // Print the population
    for(j=0; j < DIM_POP; j++) {
        printf("\nCrossOver popnext[%i]=(%lf, %lf)", j, popnext[j].point[0], popnext[j].point[1]);
        printf("\tfitness = %lf", popnext[j].fit);
    }
}

void mutation(chrom* popnext)   // mutation funtion given a pointer to array of chromes
{
    for(int i = ELITIST; i < DIM_POP; i++) {
        for(int j = 0; j < 2; j++) {
            if ((rand()%100) < 20) {    // Suppusiong Probability of mutation is 20 %
                popnext[i].point[j] = generateParam();
                popnext[i].fit = calculateFitness(popnext[i].point[0], popnext[i].point[1]);   // calculate the fitness for the mutated chrome

                // print the mutated chromosome
                // printf("\nMutation occured in popnext[%i] gene[%i]:=(%lf, %lf)",i,j,popnext[i].point[0],popnext[i].point[1]);
                //printf("\tfitness = %lf",popnext[i].fit);
            }
        }
    }
}

static void generatePoint(double point[2])
{
    point[0] = generateParam();
    point[1] = generateParam();
}

static double generateParam()
{
    double param = ((double)rand()/RAND_MAX)*(PAR_MAX-PAR_MIN) + PAR_MIN;

    double roundedParam = PAR_MIN;
    int counter = 1;
    while(roundedParam < param) {
        roundedParam = PAR_MIN + counter * RESOLUTION;
        counter++;
    }

    return roundedParam;
}

static double calculateFitness(double x, double y)          // the function that we look for it's maximum value takes (x,y) value
{
    // puoi scrivere tutto in una singola riga..
    return x + y;            // the function is z= - ( x^ 2 ) - (y^ 2) +5
}

Ho eliminato cp_chrom sostituendolo con le assegnazioni tra strutture per mostrarti quanto possa aiutare nella comprensione del codice. Ho fatto anche qualche altra leggera modifica al tuo codice (a parte la formattazione) che ti ho commentato.

La libreria così com'è non è comunque perfetta. Si da infatti sempre per scontato che la popolazione abbia una certa dimensione, nonostante non sia stata creata all'interno del codice del modulo. La funzione del quale si vuole calcolare il massimo è inoltre parte integrante del codice. Volendo implementarne una forma più generica si sarebbe dovuto passare calculateFitness come argomento delle funzioni. Volendolo ancora più generico si sarebbe dovuto lavorare con funzioni a puntatori a void tipo la funzione qsort standard del C. Ma complicava forse inutilmente tutto e la genericità del codice non credo che sia tra i tuoi interessi per questo progetto.

Per quanto riguarda a questo punto la tabu search ti direi di provarci da sola. Potrebbe essere alla fin fine comodo inserire tutto nella stessa unità di compilazione. Ci sono certamente più funzioni e a prima vista potrebbe essere comodo separare tabu_list e aspiration_list, ma hai però anche funzioni che lavorano su entrambe.

[apatriarca]

"hamming_burst":
[quote="apatriarca"]cp_chrom(A, B) è infatti del tutto equivalente a *B = *A.

questa funzione la ho scritta io (un po' di fretta?), è dovuta al fatto che TL è un vettore di chrom e non un array di puntatori
Quello che dici te non funziona solo se le strutture sono allocate staticamente?[/quote]
Non vedo perché dovrebbe essere limitato a strutture allocate staticamente, ma puoi sempre provare a scrivere un programma di test come il seguente per provarlo:

#include <stdio.h>
#include <stdlib.h>

struct A {
    double punto[2];
    double fit;
};

int main(void) {
    struct A a = {.punto = {1.0, 0.0}, .fit = 2.3};

    struct A *b = malloc(sizeof(struct A));
    *b = a;

    struct A *c = malloc(sizeof(struct A));
    *c = *b;

    printf("a = {(%lf, %lf), %lf}\n", a.punto[0], a.punto[1], a.fit);
    printf("b = {(%lf, %lf), %lf}\n", b->punto[0], b->punto[1], b->fit);
    printf("c = {(%lf, %lf), %lf}\n", c->punto[0], c->punto[1], c->fit);

    free(b);
    free(c);

    return 0;
}

[hamming_burst]

"apatriarca":
Non vedo perché dovrebbe essere limitato a strutture allocate staticamente, ma puoi sempre provare a scrivere un programma di test come il seguente per provarlo:

interessante, sapevo questa differenza sbagliata, si impara sempre qualcosa

[irelimax]

"apatriarca":

Per quanto riguarda a questo punto la tabu search ti direi di provarci da sola. Potrebbe essere alla fin fine comodo inserire tutto nella stessa unità di compilazione. Ci sono certamente più funzioni e a prima vista potrebbe essere comodo separare tabu_list e aspiration_list, ma hai però anche funzioni che lavorano su entrambe.

ti ho risposto mandandoti una mail

[apatriarca]

- Per prima cosa TL-AL_H non può essere usato in #ifndef. Devi quindi scrivere TL_AL_H. Ti consiglio di leggerti un manuale per comprenderne il motivo (il - non può essere usato all'interno di un identificativo del preprocessore).
- Per altre cose è necessario compilare il codice usando lo standard c99, per cui devi inserire l'opzione "-std=c99" (senza virgolette). Ma forse l'hai già fatto perché il tuo codice già usava alcune delle funzionalità che richiedevano tale riga (almeno nella mia versione del compilatore che potrebbe essere diversa dalla tua visto che usi Dev-C++
- In ga.c mi ero dimenticato di includere e . Non avendo provato a compilarlo non l'avevo notato. Alla riga 76 di ga.c mancano inoltre le // per il commento. manca anche in TL-AL.c.
- In TL-AL.c, devi mettere static anche nell'implementazione di fullp e non solo nel prototipo.
- Se cp_chrom non è poi più definito devi eliminarlo da tutte le parti in cui lo usi..
- Devi inserire il prototipo di DISTANCE prima del main.
- Manca una parentesi alla fine del main.
Tutto ciò dovrebbe permetterti di compilare il progetto, ma non mi funziona (è andato in crash appena ho cercato di farlo partire percui non ti inserisco il codice).

[irelimax]

tutti gli errori dovrebbero essere risolti ma ho ancora qualche problema con la cp_chrom. l'ho cancellata come tu hai detto ma ho errori di tipi incompatibili. ad esempio ho sostitutito l'istruzione

cp_chrom(max,&(population[0]));

con la seguente:

&(population[0]) = max;

e mi da errore.

mentre se sostituisco

cp_chrom(&(population[0]),max);

con questo

max = &(population[0]);

è corretto

Probabilmente è qualcosa di teorico che non so...

[apatriarca]

A cp_chrom passi dei puntatori, degli indirizzi, mentre quando fai l'assegnazione devi lavorare direttamente con le strutture e quindi deferenziare i puntatori. Avevo infatti scritto che cp_chrom(A, B) corrisponde a *B = *A. Nel tuo caso

cp_chrom(max,&(population[0]));

diventa

population[0] = *max;

nota che * e & sono operatori uno l'inverso dell'altro.

[hamming_burst]

"apatriarca":(è andato in crash appena ho cercato di farlo partire percui non ti inserisco il codice).

possibili motivazioni del crash qui
o perchè ritorna NULL in una delete_*() ...

[irelimax]

il crash di cui state parlando non si verifica più ma, nel run, mi sono accorta di un malfunzionamento. Praticamente quando viene eliminato un elemento dalla tabu list, nella aspiration list viene aggiunto l'elemento (0,0) con fitness 0. non penso sia errore di stampa bensi di codice.

a entrambi vi mando via e mail il progetto completo.

penso che un boccone adesso me lo sono meritata perciò vado a cenare e ci si sente tra un pò sempre che voi ci siate. spero di si . buona cena!

[irelimax]

"irelimax":il crash di cui state parlando non si verifica più ma, nel run, mi sono accorta di un malfunzionamento. Praticamente quando viene eliminato un elemento dalla tabu list, nella aspiration list viene aggiunto l'elemento (0,0) con fitness 0. non penso sia errore di stampa bensi di codice.

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