Tabu search
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
Ciao,
prova qua
sono slide con degli esempi sulla ricerca locale dove comprende in modo esteso le proibizioni della tabù search.
Se avrai dubbi chiedi pure
prova qua
sono slide con degli esempi sulla ricerca locale dove comprende in modo esteso le proibizioni della tabù search.
Se avrai dubbi chiedi pure

ciao, il pdf che mi hai mandato l'avevo già visto
Il mio problema è implementare un algoritmo ibrido algoritmo genetico + tabu search per trovare il max di una funzione f(x,y). Il GA sono riuscita ad implementarlo ma devo adesso integrarlo con la tabu search.
Io ho trovato una pubblicazione che spiega in teoria come funziona :
Using Tabu search, search space of genetic algorithm is increased. In this problem, after using crossover and mutation operator in each iteration of evolution, the chromosome with best fitness is selected as Tabu and added to Tabu list.
Chromosomes in Tabu list have an aspiration time. In each iteration, aspiration time is decreased. If the value of aspiration time of each chromosome in Tabu list becomes zero, it is deleted from this list and added to aspiration list. After finding Tabu, chromosomes in current population that are similar to Tabu are replaced with the chromosome in aspiration list. If aspiration list was empty this chromosome replaced with chromosomes in last population with smallest fitness value. Using this replace, diversity of population increase.
Vorrei qualche spiegazione più dettagliata magari con qualche linea di codice da cui partire.. Ad es la tabu list la devo riempire tutta prima di iniziare la tabu search? Al primo ciclo, quando ancora l'aspiration list è vuota, con cosa sostituisco i punti simili a quelli tabu? io ho capito che li devo sostituire con quelli cn fitness minore della popolazione precedente, ma se sono ancora alla prima generazione, come faccio?

Io ho trovato una pubblicazione che spiega in teoria come funziona :
Using Tabu search, search space of genetic algorithm is increased. In this problem, after using crossover and mutation operator in each iteration of evolution, the chromosome with best fitness is selected as Tabu and added to Tabu list.
Chromosomes in Tabu list have an aspiration time. In each iteration, aspiration time is decreased. If the value of aspiration time of each chromosome in Tabu list becomes zero, it is deleted from this list and added to aspiration list. After finding Tabu, chromosomes in current population that are similar to Tabu are replaced with the chromosome in aspiration list. If aspiration list was empty this chromosome replaced with chromosomes in last population with smallest fitness value. Using this replace, diversity of population increase.
Vorrei qualche spiegazione più dettagliata magari con qualche linea di codice da cui partire.. Ad es la tabu list la devo riempire tutta prima di iniziare la tabu search? Al primo ciclo, quando ancora l'aspiration list è vuota, con cosa sostituisco i punti simili a quelli tabu? io ho capito che li devo sostituire con quelli cn fitness minore della popolazione precedente, ma se sono ancora alla prima generazione, come faccio?

"irelimax":
ciao, il pdf che mi hai mandato l'avevo già visto![]()
ah sorry

il mio problema è implementare un algoritmo ibrido algoritmo genetico + tabu search per trovare il max di una funzione f(x,y). Il GA sono riuscita ad implementarlo ma devo adesso integrarlo con la tabu search.
ok, problema interessante.
E' pratica parecchio usata mischiare queste tecniche (LS e population) molto potenti, che danno risultati davvero utili per risolvere una varietà di problemi molto vasta

Ma già noto una cosa importante da chiarire: cos'è $f(x,y)$?
se devi scrivere un algoritmo generico in pseudo-codice è una cosa, ti fermi ad un'astrazione molto alto livello; ma se devi scrivere codice vero, devi definire bene cosa è questa funzione.

Rispondi a questo e dopo vediamo

PS: l'immagine che hai allegato la hai presa da qualche libro?
ogni individuo è caratterizzato da due cromosomi $x$ e $y$ e da una fitness $f(x,y)$. Devo trovare l'individuo avente la fitness maggiore ovvero il max della $f(x,y)$. Io devo scrivere il codice che deve perfettamente girare sul compilatore. Ho già implementato la parte del GA (ricerca locale) che funziona. Se vuoi t posso mandare un mess privato per vederlo. Manca adesso la parte della ricerca globale tramite tabu search. L'immagine che t ho allegato l'ho presa da una pubblicazione poco esaustiva...
Dovrei riuscire a tradurre in codice la spiegazione della pubblicazione che ho allegato nel post precedente..
Dovrei riuscire a tradurre in codice la spiegazione della pubblicazione che ho allegato nel post precedente..
con definire f(x,y) intedevo dire del tipo di andamento della funzione. Ma comunque non importa, non avevo letto ieri sera la parte che avevi copiato, pensavo fosse solamente una spiegazione teorica della ricerca tabù e non sel tuo problema.
Domani prendo un po' sul serio la tua questione perchè mi sembra interessante, ma cmq non discosta molto da una normale applicazione di queste tecniche (perciò nulla di anormale
).
PS: il codice puoi anche copiarlo con i tag appositi nel post, ma se vuoi mandarlo ok; non ti prometto nulla che sia collegato con questo, ma gli do un'occhiata volentieri
Domani prendo un po' sul serio la tua questione perchè mi sembra interessante, ma cmq non discosta molto da una normale applicazione di queste tecniche (perciò nulla di anormale

PS: il codice puoi anche copiarlo con i tag appositi nel post, ma se vuoi mandarlo ok; non ti prometto nulla che sia collegato con questo, ma gli do un'occhiata volentieri

Vediamo un po'.
ho letto un po' il problema. Devo dire che ancora non avevo visto implementata una versione del MA nella parte di mutazione con tabu search (c'è sempre la prima volta
)
Prima di tutto, la tabella è piuttosto esaustiva, non sempre c'è adirittura scritto il tipo di ricerca locale da utilizzare per ogni passo delle schema dell'algorimo genetico (di solito in questi casi si utilizzano esperienze sperimentali).
Prendo per buono tutto quello che hai scritto algoritmo genetico + passi di ricerca locale, il codice lo ho letto di sfuggita (non ho il tempo di capire cosa hai fatto) leggendo i nomi delle funzioni utilizzi lo schema standard di implementazione (di solito comunque si preferisce una versione iterativa, ma non cambia).
Ora veniamo solo alla ricerca tabu:
Qua si utilizza la proibizione fissa per iterazioni (o tempo). Sì gli schemi generali per la risoluzione di questi problemi sono molto modellizzabili, devo dire di non aver visto una separazione netta tra insieme delle proibizioni e degli intorni ammessi al valore corrente.
Comunque vediamo di generalizzare questo testo, visto che hai seguito lo schema:
_________
Prima di tutto però ho notato un problema non chiaro, lo stesso che hai domandato, cioè se già all'inizializzazione bisogna inserire la soluzione parziale migliore (della mutation) nella tabù list, cosa abbastanza normale da fare, però c'è anche la aspiration list da tenere in considerazione
si dovrebbe risolvere condizionando il primo passo vedendo che non ci sono mosse tabu, controllo e poi ti dico
_________
continuo 20/09:
allora mettiamo giù sto pseudo-codice di un algoritmo Tabu-Search con proibizione fissa ad iterazione T (utilizzo uno schema standard lo modifichiamo man mano che ti serve
)
questo schema:
tabu_search initialization:
iterator fixed $T$
initial solution $x_1$ := cromosoma C con migior fitness
partial_solution $vecx = x_1$
Tabu_List TL = ${}$
itarator $I = 0$
Using Tabu search, search space of genetic algorithm is increased. In this problem, after using crossover and mutation operator in each iteration of evolution, the chromosome with best fitness is selected as Tabu and added to Tabu list.
Chromosomes in Tabu list have an aspiration time. In each iteration, aspiration time is decreased.
$TL uu vecx$
If the value of aspiration time of each chromosome in Tabu list becomes zero, it is deleted from this list and added to aspiration list.
$if(I - TL_i) = T -> \text{aspirationL} uu TL_i ^^ TL-TL_i$
After finding Tabu, chromosomes in current population that are similar to Tabu are replaced with the chromosome in aspiration list. If aspiration list was empty this chromosome replaced with chromosomes in last population with smallest fitness value. Using this replace, diversity of population increase
$if (TL_i ~~ vecx) -> vecx =\text{aspirationL}(vecx)$
$\ \ \ \ \ \ if(\text{aspirationL} == {}) -> vecx = x_{I-1}$
$I = I+1$
riassumendo:
$TL uu vecx$ cromosoma con miglior fitness
while(I==T)
$\ \ if (I - TL_i) = T -> \text{aspirationL} uu TL_i ^^ TL-TL_i$
$\ \ if (TL_i ~~ vecx) -> vecx = \text{aspirationL}(vecx)$
$\ \ \ \ \ \if(\text{aspirationL} == {}) -> vecx = x_{I-1}$
$\ \ \ I = I+1$
ok, vedi se ti è più chiaro così. Di solito non si utilizza una lista di "aspirazione", ma un procedimento di scelta sui "vicini" penso che questo modo di operare sia per simulare tale comportamento. Non mi piace molto come è stato strutturata questa ricerca, ma così è
Ovviamente ci sono tutte le strutture dati da implementare e studiare al meglio, io sono stato generale apposta.
Se non ti è chiaro ciò che ho scritto (che è direttamente collegato con il testo) chiedi pure, cerco di esser più chiaro ma il testo è fuorviante e non segue uno schema "standard" (come già detto)
due cose da chiarire del testo:
-
serve una misura ed una definizione di "simile". Come è un cromosoma nel tuo algoritmo genetico (non farmi leggere il codice
) e una funzione fitness (cioè la rappresentazione)
-
ti salvi le generazioni antecedenti alla sostituzione con l'elite?
dalle tue risposte dipende la modifica o lo spostamento di un if
EDIT:
parecchie cose.
ho letto un po' il problema. Devo dire che ancora non avevo visto implementata una versione del MA nella parte di mutazione con tabu search (c'è sempre la prima volta

Prima di tutto, la tabella è piuttosto esaustiva, non sempre c'è adirittura scritto il tipo di ricerca locale da utilizzare per ogni passo delle schema dell'algorimo genetico (di solito in questi casi si utilizzano esperienze sperimentali).
Prendo per buono tutto quello che hai scritto algoritmo genetico + passi di ricerca locale, il codice lo ho letto di sfuggita (non ho il tempo di capire cosa hai fatto) leggendo i nomi delle funzioni utilizzi lo schema standard di implementazione (di solito comunque si preferisce una versione iterativa, ma non cambia).
Ora veniamo solo alla ricerca tabu:
Using Tabu search, search space of genetic algorithm is increased. In this problem, after using crossover and mutation operator in each iteration of evolution, the chromosome with best fitness is selected as Tabu and added to Tabu list.
Chromosomes in Tabu list have an aspiration time. In each iteration, aspiration time is decreased. If the value of aspiration time of each chromosome in Tabu list becomes zero, it is deleted from this list and added to aspiration list. After finding Tabu, chromosomes in current population that are similar to Tabu are replaced with the chromosome in aspiration list. If aspiration list was empty this chromosome replaced with chromosomes in last population with smallest fitness value. Using this replace, diversity of population increase.
Qua si utilizza la proibizione fissa per iterazioni (o tempo). Sì gli schemi generali per la risoluzione di questi problemi sono molto modellizzabili, devo dire di non aver visto una separazione netta tra insieme delle proibizioni e degli intorni ammessi al valore corrente.
Comunque vediamo di generalizzare questo testo, visto che hai seguito lo schema:
_________
Prima di tutto però ho notato un problema non chiaro, lo stesso che hai domandato, cioè se già all'inizializzazione bisogna inserire la soluzione parziale migliore (della mutation) nella tabù list, cosa abbastanza normale da fare, però c'è anche la aspiration list da tenere in considerazione
si dovrebbe risolvere condizionando il primo passo vedendo che non ci sono mosse tabu, controllo e poi ti dico

_________
continuo 20/09:
allora mettiamo giù sto pseudo-codice di un algoritmo Tabu-Search con proibizione fissa ad iterazione T (utilizzo uno schema standard lo modifichiamo man mano che ti serve

questo schema:
Tabu Search (TS): determine initial candidate solution s While termination criterion is not satisfied: | determine set N of non-tabu neighbours of s | choose a best improving candidate solution s in N | | update tabu attributes based on s | s := s
tabu_search initialization:
iterator fixed $T$
initial solution $x_1$ := cromosoma C con migior fitness
partial_solution $vecx = x_1$
Tabu_List TL = ${}$
itarator $I = 0$
Using Tabu search, search space of genetic algorithm is increased. In this problem, after using crossover and mutation operator in each iteration of evolution, the chromosome with best fitness is selected as Tabu and added to Tabu list.
Chromosomes in Tabu list have an aspiration time. In each iteration, aspiration time is decreased.
$TL uu vecx$
If the value of aspiration time of each chromosome in Tabu list becomes zero, it is deleted from this list and added to aspiration list.
$if(I - TL_i) = T -> \text{aspirationL} uu TL_i ^^ TL-TL_i$
After finding Tabu, chromosomes in current population that are similar to Tabu are replaced with the chromosome in aspiration list. If aspiration list was empty this chromosome replaced with chromosomes in last population with smallest fitness value. Using this replace, diversity of population increase
$if (TL_i ~~ vecx) -> vecx =\text{aspirationL}(vecx)$
$\ \ \ \ \ \ if(\text{aspirationL} == {}) -> vecx = x_{I-1}$
$I = I+1$
riassumendo:
$TL uu vecx$ cromosoma con miglior fitness
while(I==T)
$\ \ if (I - TL_i) = T -> \text{aspirationL} uu TL_i ^^ TL-TL_i$
$\ \ if (TL_i ~~ vecx) -> vecx = \text{aspirationL}(vecx)$
$\ \ \ \ \ \if(\text{aspirationL} == {}) -> vecx = x_{I-1}$
$\ \ \ I = I+1$
ok, vedi se ti è più chiaro così. Di solito non si utilizza una lista di "aspirazione", ma un procedimento di scelta sui "vicini" penso che questo modo di operare sia per simulare tale comportamento. Non mi piace molto come è stato strutturata questa ricerca, ma così è

Ovviamente ci sono tutte le strutture dati da implementare e studiare al meglio, io sono stato generale apposta.
Se non ti è chiaro ciò che ho scritto (che è direttamente collegato con il testo) chiedi pure, cerco di esser più chiaro ma il testo è fuorviante e non segue uno schema "standard" (come già detto)

due cose da chiarire del testo:
-
chromosomes in current population that are similar to Tabu are replaced with the chromosome in aspiration list.
serve una misura ed una definizione di "simile". Come è un cromosoma nel tuo algoritmo genetico (non farmi leggere il codice

-
If aspiration list was empty this chromosome replaced with chromosomes in last population with smallest fitness value.
ti salvi le generazioni antecedenti alla sostituzione con l'elite?
dalle tue risposte dipende la modifica o lo spostamento di un if

EDIT:
parecchie cose.
ok gentilissimo..attendo news

anche questo pseudo codice è ancora un po astratto per me..se ho capito bene, $TL_i$ dovrebbe essere il tempo di aspirazione che caratterizza ogni cromosoma. nel programma che ho implementato io alla funzione tabu search verrebbe passata una popolazione di 100 individui caratterizzati dai cromosomi $(x_i,y_i)$. In base al pseudo codice che m hai scritto, nella tabu list verrebbe inserito l'individuo con la fitness maggiore e quando il suo tempo scade viene trasferito nella aspiration list. Ma in questo modo nella tabu list, resta sempre un solo elemento, o sbaglio?
Forse l'iteratore $I$ che hai messo nel pseudo codice conta il numero di iterazioni che devono essere eseguite dall'intero programma, come riportato nella tabella del post precendete?
Forse l'iteratore $I$ che hai messo nel pseudo codice conta il numero di iterazioni che devono essere eseguite dall'intero programma, come riportato nella tabella del post precendete?
"irelimax":
anche questo pseudo codice è ancora un po astratto per me..
me ne rendo conto, ma dato che questi tipi di algoritmi sono molto concettuali, bisogna astrarre parecchio per non ingolfarsi in strutture dati non adatte al nostro caso, ora comunque appena riusciamo a districarci dall'algoritmo possiamo scegliere cosa fare

se ho capito bene, $TL_i$ dovrebbe essere il tempo di aspirazione che caratterizza ogni cromosoma.
doppio significato $TL_i$ rappresenta quello che il testo chiama "aspiration time" dell'elemento $i$ nella tabu list $TL$ e anche l'elemento stesso, cioè lelemento ${tl_i} in TL$.
Forse se non comprendi il codice così cerco di riscriverlo meglio, introducendo una notazione diversa.
nel programma che ho implementato io alla funzione tabu search verrebbe passata una popolazione di 100 individui caratterizzati dai cromosomi $(x_i,y_i)$.
stampami un'istanza semplice di tutti i dati al momento di utilizzare la Tabu search, così ho chiaro quale è la situazione in input.
In base al pseudo codice che m hai scritto, nella tabu list verrebbe inserito l'individuo con la fitness maggiore e quando il suo tempo scade viene trasferito nella aspiration list. Ma in questo modo nella tabu list, resta sempre un solo elemento, o sbaglio?
qua dipende dai dati input (vedi sopra) all'inizializzazione.
Forse l'iteratore $I$ che hai messo nel pseudo codice conta il numero di iterazioni che devono essere eseguite dall'intero programma, come riportato nella tabella del post precendete?
esatto

aumentare $TL_i$ o sottrarre $I-TL_i$ e controllare se sono zero od uguali al tempo fissato $T$ sono la stessa cosa

vediamo stasera, intanto te prova riportare una print dei dati in input, e se riesci a rispondermi alle due domande del post sopra (riguardanti il testo).

PS: lo compilerei io il tuo codice, ma utilizzi una assurda libreria di MS-DOS (conio.h) che non ho mai sentito in nessuno standard C, posso chiederti dove hai letto di utilizzare questa libreria? dispense, libri?
Allora, ci ho riflettuto ancora un po e i dubbi che rimangono sono:
1) Cosa indica $T$? è una variabile contatore che metterò all'interno della funzione tabu search e che introdurrò da tastiera?
2) Come fisso $TL_i$ per ogni $i$? è una costante oppure varia al variare di $i$?
3) Come viene implementato $TL uu \vec x $ ? Nel senso, come faccio a riempire la tabu list tenendo presente che allo scadere dell'aspiration time alcune posizioni si libereranno? Una semplice coda FIFO eliminerrebbe il piu vecchio elemento della lista già alla prima iterazione senza quindi tener conto dell'apiration time.
4) quando scrivi l'istruzione $\vec x =$ aspiration ($\vec x$) nel caso in cui il cromosoma è simile al tabu, quale sarebbe qst cromosoma nell'aspiration list che sostituirebbe il cromosoma $\vec x$? viene scelto a caso?
5) con l'istruzione if$(TL_i ~~ \vec x) $ confronti i valori tabu ($TL_i$) con il valore migliore ($\vec x$) preso ogni volta dalla popolazione corrente. Dall'affermazione "After finding Tabu, chromosomes in current population that are similar to Tabu are replaced with the chromosome in aspiration list" capisco invece che bisogna confrontare tutti i cromosomi della pop corrente con i tabu e non solo $\vec x$ . Non so se ho capito male io dalla frase precendente.
Ora rispondo alle domande che mi hai fatto:
1) Non salvo nessuna delle generazioni antecedenti alla sostituzione con l'elite perchè non le uso. Il metodo dell'elite lo uso per mantenere i migliori cromosomi della popolazione. Cioè a questi non gli applico crossover e mutation.
2) Per quanto riguarda la domanda sul confronto definirò una funzione "DISTANCE" che calcola la distanza euclidea nel piano tra due punti e che la restituisce come output. Fissata poi una costante raggio $R$ considererò punti simili ai tabu quei punti che distano da essi meno di raggio $R$.
Ti allego come immagine l'outputdel mio algoritmo genetico prima che passo il controllo al tabu search.

1) Cosa indica $T$? è una variabile contatore che metterò all'interno della funzione tabu search e che introdurrò da tastiera?
2) Come fisso $TL_i$ per ogni $i$? è una costante oppure varia al variare di $i$?
3) Come viene implementato $TL uu \vec x $ ? Nel senso, come faccio a riempire la tabu list tenendo presente che allo scadere dell'aspiration time alcune posizioni si libereranno? Una semplice coda FIFO eliminerrebbe il piu vecchio elemento della lista già alla prima iterazione senza quindi tener conto dell'apiration time.
4) quando scrivi l'istruzione $\vec x =$ aspiration ($\vec x$) nel caso in cui il cromosoma è simile al tabu, quale sarebbe qst cromosoma nell'aspiration list che sostituirebbe il cromosoma $\vec x$? viene scelto a caso?
5) con l'istruzione if$(TL_i ~~ \vec x) $ confronti i valori tabu ($TL_i$) con il valore migliore ($\vec x$) preso ogni volta dalla popolazione corrente. Dall'affermazione "After finding Tabu, chromosomes in current population that are similar to Tabu are replaced with the chromosome in aspiration list" capisco invece che bisogna confrontare tutti i cromosomi della pop corrente con i tabu e non solo $\vec x$ . Non so se ho capito male io dalla frase precendente.
Ora rispondo alle domande che mi hai fatto:
1) Non salvo nessuna delle generazioni antecedenti alla sostituzione con l'elite perchè non le uso. Il metodo dell'elite lo uso per mantenere i migliori cromosomi della popolazione. Cioè a questi non gli applico crossover e mutation.
2) Per quanto riguarda la domanda sul confronto definirò una funzione "DISTANCE" che calcola la distanza euclidea nel piano tra due punti e che la restituisce come output. Fissata poi una costante raggio $R$ considererò punti simili ai tabu quei punti che distano da essi meno di raggio $R$.
Ti allego come immagine l'outputdel mio algoritmo genetico prima che passo il controllo al tabu search.


Riposta al tuo PS: la funzione getche() per ritornare il controllo al sistema operativo richiede la libreria conio.h

Allora ti ringrazio dello screen, mi hai chiarito alcune cose.
Tipo che alla popolazione dai una funzionde d'ordine per fitness migliore. Cosa che cambia il codice.
Per le tue domande, scendi di un livello di astrazione, il mio "codice" è la trattazione del testo. L'implementazione è tutt'altra cosa. Molto bene che mi parli di "distanza" euclidea.
Ascolta, a me non piace questa implementazione della tabu search non c'è una definizione di vicinato e come hai già notato la tabu list rimarrà sempre di un elemento, e la funzione rimarrà sempre in un punto stagnante.
Ora non ho la concentrazione per analizzare i tuoi punti non chiari ($T$ come scritto è un valore fissato all'inizio ed è costante per le iterazioni) ma mi è venuto in mente dato che hai una funzione d'ordine sulla popolazione, si può pensare a costruire un insieme di "vicini" ai cromosomi per fitness o seconda possibilità analizzare ogni cromosoma per DISTANCE e cotruire un insieme di vicini di raggio R, così la tabu search avrebbe più significato che dal testo non ne ha (la aspiration list è una simulazione non un'implementazione).
Tutto questo lo vediamo domani, se non hai troppa fretta
Tipo che alla popolazione dai una funzionde d'ordine per fitness migliore. Cosa che cambia il codice.
Per le tue domande, scendi di un livello di astrazione, il mio "codice" è la trattazione del testo. L'implementazione è tutt'altra cosa. Molto bene che mi parli di "distanza" euclidea.
Ascolta, a me non piace questa implementazione della tabu search non c'è una definizione di vicinato e come hai già notato la tabu list rimarrà sempre di un elemento, e la funzione rimarrà sempre in un punto stagnante.
Ora non ho la concentrazione per analizzare i tuoi punti non chiari ($T$ come scritto è un valore fissato all'inizio ed è costante per le iterazioni) ma mi è venuto in mente dato che hai una funzione d'ordine sulla popolazione, si può pensare a costruire un insieme di "vicini" ai cromosomi per fitness o seconda possibilità analizzare ogni cromosoma per DISTANCE e cotruire un insieme di vicini di raggio R, così la tabu search avrebbe più significato che dal testo non ne ha (la aspiration list è una simulazione non un'implementazione).
Tutto questo lo vediamo domani, se non hai troppa fretta

Vediamo un po' di risolvere sto problema 
Come detto non mi piace sta implementazione con "aspiration list"; cerchiamo di semplificarci la vita, utilizziamo la TS standard e in un secondo momento, se funzionerà questa implementazione modificare l'algoritmo con il modello che hai utilizzato non penso sia complicato (la local search è obbligata nei MA qualunque essa sia).
Allora:
utilizziamo la proprietà di neighbour perciò dobbiamo costruirci un sotto-insieme della soluzione attuale. In questo problema siamo in un bellissimo caso, che non dobbiamo andare troppo lonati per definire la proprietà di "vicino" utilizziamo la distanza euclidea DISTANCE come la hai già definita per un $R$ fissato.
$C(x,y)$ cromosoma
$P$ insieme popolazione
$TL$ Tabù List
${}$ Insieme vuoto
$T$ iterator fissato
$I$ iterator
s = $C(x,y)$ con fitness migliore
Ora questo codice, è ovviamente da sistemare, ma mi sembra molto più semplice da comprendere ed implementare
C'è da considerare il tabu-time e l'aspiration criteria non è difficile.
La cosa che mi fa dubitare è se la Tabu list deve essere una lista globale e non che si azzeri ad ogni popolazione nuova (od iterazione fissata). Penso l'aspiration list sia un modo per ovviare a questo mantendendo solo i cromosomi migliori.
Vedi se riesci a capire ora, a me sembra più che ok; come prima il livello di implementazione è tutto da vedere, chiedi pure cosa non ti è chiaro e cerchiamo di sistemare
EDIT:
in questa versione ho introdotto un problema ancora più ostico da risolvere, i vicini sono infiniti...
Io ho ragionato in modo discreto, ma il problema che vuoi risolvere è di su una funzione continua cosa che in questo caso la TS standard non può risolvere. Bisognerebbe introdurre altre strutture e definizioni di vicinato prese dall'analisi matematica.
In questo caso meglio non complicare ancora, ritorniamo sui nostri passi con la tua traccia, visto penso di aver capito come strtutturare il tutto, ti scrivo definitivamente il codice e finimo

Come detto non mi piace sta implementazione con "aspiration list"; cerchiamo di semplificarci la vita, utilizziamo la TS standard e in un secondo momento, se funzionerà questa implementazione modificare l'algoritmo con il modello che hai utilizzato non penso sia complicato (la local search è obbligata nei MA qualunque essa sia).
Allora:
utilizziamo la proprietà di neighbour perciò dobbiamo costruirci un sotto-insieme della soluzione attuale. In questo problema siamo in un bellissimo caso, che non dobbiamo andare troppo lonati per definire la proprietà di "vicino" utilizziamo la distanza euclidea DISTANCE come la hai già definita per un $R$ fissato.
$C(x,y)$ cromosoma
$P$ insieme popolazione
$TL$ Tabù List
${}$ Insieme vuoto
$T$ iterator fissato
$I$ iterator
s = $C(x,y)$ con fitness migliore
Tabu Search($s in P$):
Tabu List $TL = {}$
soluzione migliore $s^{\prime} = s$
while(Terminte Criteria)
qua io metterei $I==T$ ma certi testi costruiscono due cicli while ed utilizzano un terminatore differente.
______
trovare i vicini migliori $s^{\prime}_1 in \text{DISTANCE}(s,s_n), s^{\prime}_1 !in TL$
NOTA: "migliori" si intende con fitness maggiore (non considerando s). quando si controlla che $s^{'}_1$ non appartiene a TL, possiamo controllare anche che il tabu-time sia a zero (equivalentemente a T) e togliere questa soluzione dalla lista per non essere più tabu.
$TL = TL uu {s}$
$s=s^{\prime}_1$
if$(f(s) > f(s^{\prime}))$
$\ \ \ \ \ s^{\prime} = s $
I = I+1;
_____
return $s'$
Ora questo codice, è ovviamente da sistemare, ma mi sembra molto più semplice da comprendere ed implementare

C'è da considerare il tabu-time e l'aspiration criteria non è difficile.
La cosa che mi fa dubitare è se la Tabu list deve essere una lista globale e non che si azzeri ad ogni popolazione nuova (od iterazione fissata). Penso l'aspiration list sia un modo per ovviare a questo mantendendo solo i cromosomi migliori.
Vedi se riesci a capire ora, a me sembra più che ok; come prima il livello di implementazione è tutto da vedere, chiedi pure cosa non ti è chiaro e cerchiamo di sistemare

EDIT:
in questa versione ho introdotto un problema ancora più ostico da risolvere, i vicini sono infiniti...
Io ho ragionato in modo discreto, ma il problema che vuoi risolvere è di su una funzione continua cosa che in questo caso la TS standard non può risolvere. Bisognerebbe introdurre altre strutture e definizioni di vicinato prese dall'analisi matematica.
In questo caso meglio non complicare ancora, ritorniamo sui nostri passi con la tua traccia, visto penso di aver capito come strtutturare il tutto, ti scrivo definitivamente il codice e finimo

Riproviamo 
Sono valide tutte le considerazioni fattefino al penultimo post (anche se, a dire il vero, gli algoritmi sono quasi equivalenti, ma lasciamo stare).
che ne dici?
Penso sia più comprensibile adesso
nota che ho seguito il testo con qualche mia interpretazione. Ora basta implementare, per ogni lista c'è da fare i controlli sugli indici per non "sbordare".
Spero che funzioni così, il ruolo della AL è proprio come avevo pensato all'inizio, simula il ruolo del vicinato.
Da considerare che questa implementazione funziona se fai più iterazioni dell'algoritmo principale, se no è come hai segnalato te qualche post sopra, avrai sempre gli stessi elementi (o uno solo) nella TL.
Se hai domande chiedi pure
EDIT:
rileggendo un attimo il testo mi rimane il dubbio che "last population" si riferisca davvero agli antenati o invece all'ultima popolazione, cioè quella corrente...

Sono valide tutte le considerazioni fattefino al penultimo post (anche se, a dire il vero, gli algoritmi sono quasi equivalenti, ma lasciamo stare).
Population P[] Antenati FP[] bisogna salavarsi la generazione (UNA) precedente, da eliminare dopo ogni ricerca tabù. tempo fissato tabu: F cromosoma: C cromosoma in input: c' Tabu List TL[] TL[i]=C(x,y) Tabu Time TT[] TT[i]=F notare che c'è corrispondenza tra indici TL[i]~~TT[i], questo perchè il tabu time deve corrispondere alla tabu list. Aspiration List AL[] AL[j]=C(x,y) Tabu_Search(c' in P) TL.add(c') TT(c')=F; while(I<F){ if(TT[i]==0){ AL[j]=TL[i] TL.delete(i) TT.delete(i) } if(DISTANCE((P[k]-c'),TL)){ valutare se sono simili con gli elementi in tabu list con la popolazione (senza quello con fitness migliore) if(AL=={}){ P[k]=FP[f()<) sostituire il cromosoma ella popolazione attuale con quello di fitness minore degli antenati (per ogni iterazione si decresce di indice) } else{ P[k]=AL[j] } } foreach(tt in TT){ tt = tt - 1; } si diminuisce il tabu time per ogni elemento I=I+1; } }
che ne dici?
Penso sia più comprensibile adesso

nota che ho seguito il testo con qualche mia interpretazione. Ora basta implementare, per ogni lista c'è da fare i controlli sugli indici per non "sbordare".
Spero che funzioni così, il ruolo della AL è proprio come avevo pensato all'inizio, simula il ruolo del vicinato.
Da considerare che questa implementazione funziona se fai più iterazioni dell'algoritmo principale, se no è come hai segnalato te qualche post sopra, avrai sempre gli stessi elementi (o uno solo) nella TL.
Se hai domande chiedi pure

EDIT:
rileggendo un attimo il testo mi rimane il dubbio che "last population" si riferisca davvero agli antenati o invece all'ultima popolazione, cioè quella corrente...
Finalmente entriamo nel concreto. Ho dato una
lettura al tuo codice ed è un pò più
comprensibile dei precedenti anche se ho
ancora alcune domande da porti.
Non conviene inserire i campi Tabu List TL[]
e Tabu Time TT[] in una struttura di dati?
Penso che cosi verrebbe più ordinato e
comprensibile... Ed inoltre che dimensione
devono avere la tabu list e l'aspiration list
tenuto conto che la popolazione è formata da
100 elementi?
Una volta chiarito questo incomincerò a
scrivere il codice vero e proprio e cercheremo di chiarire altri dubbi durante
l'implementazione.
P.S.: Ma gli antenati e ultima popolazione non rappresentano la stessa cosa?
lettura al tuo codice ed è un pò più
comprensibile dei precedenti anche se ho
ancora alcune domande da porti.
Non conviene inserire i campi Tabu List TL[]
e Tabu Time TT[] in una struttura di dati?
Penso che cosi verrebbe più ordinato e
comprensibile... Ed inoltre che dimensione
devono avere la tabu list e l'aspiration list
tenuto conto che la popolazione è formata da
100 elementi?
Una volta chiarito questo incomincerò a
scrivere il codice vero e proprio e cercheremo di chiarire altri dubbi durante
l'implementazione.
P.S.: Ma gli antenati e ultima popolazione non rappresentano la stessa cosa?
"irelimax":
Non conviene inserire i campi Tabu List TL[]
e Tabu Time TT[] in una struttura di dati?
Penso che cosi verrebbe più ordinato e
comprensibile...
esattamente, adesso ci si deve pensare.
Non hai mai seguito un corso di algoritmi?
Ci sono varie fasi, una si progetta in un pseudo-codice, poi si pensa alle cose secondarie come strutture dati ecc...
Forse non è intuitivo fare così, ma io lo vedo più facile

Comunque dipende un po' dalla tua "sensibilità".
Si può implementare in vari modi, una è scrivere tipo:
struct tabu_el{ chrome c int tabu_time };
e utilizzare poi un array di questo cioè "tabu_el tabu[]"
così hai anche un'indicizzazione da utilizzare nei cicli. Ci sono da implementare funzioni per l'add o il delete, se fai un delete tipo pui utilizzare il valore NULL come dire che è cancellata o un qualsiasi valore particolare... come detto dipende da cosa sai fare, non è complicato e anche nel web ci sono mille esempi

Ed inoltre che dimensione
devono avere la tabu list e l'aspiration list
tenuto conto che la popolazione è formata da
100 elementi?
per la dimensione dipende se utilizzi vettori o strutture a liste. Se usi vettori se ricordo bene una buona dimensione per la tabu list è $3n$, cioè 3 volte il valore del sottoinsieme composto dai vicini o delle soluzioni parziali (in questo caso della popolazione). In questo caso devi considerare che può diventare piena la lista, ma dubito avvenga, basta imporre il tempo fissato di iterazioni a $3$ o massimo $4$ sono buoni numeri. O se usi le liste non hai questi problemi, hai solo qualche scocciatura in più da programmare.
P.S.: Ma gli antenati e ultima popolazione non rappresentano la stessa cosa?
eeh è questo il mio dubbio, last population non capisco a cosa si riferisca, in italiano la tradurrei come antenati, anche perchè se fosse la popolazione corrente c'è il rischio di sostituire in loop sempre gli stessi elementi. Lascia al momento FP[] è subito fatto cambiare

PS:
io lo ho dato per scontato, ma te conosci le strutture dati a liste (LIFO, FIFO, double linked list, ecc..)?
La struttura che deve gestire la Tabu List non deve essere una FIFO, ma deve evere queste proprietà insieme a quelle di una double linked list, cioè:
- limitare la dimensione della lista con un fattore limite (3n)
- avere un ordine di inserimento FIFO
- eliminare elementi in qualunque punto, proprietà delle DLL
- navigare negli elementi utili della lista con un "for"
come vedi dovresti unire due mondi per implementare bene la TS, se dici cosa conosci e cosa no ti si da una mano anche in questo

mmm... pensavo si potesse fare esclusivamente usando array di strutture. Il problema è che non ho molta esperienza nell'uso delle liste quindi la mia difficoltà sarebbe nel gestire la tabu list ( aggiungere o eliminare elementi). sono ben accette le tue dritte. Ho cominciato a scrivere qualcosa basandomi su quello che mi hai scritto ieri. adesso ti mostro cosa ho scritto.
procedo bene? cambieresti qualcosa del mio codice? Ad esempio come vedi ho ancora ben chiaro come definire l'aspiration list. Ho usato una matrice DIM_ALx2 per questa ma non so se è una buona idea
#define DIM_TABU 3n #define DIM_AL //aspiration list dimension #define F //tabu tenure #define R //minimum distance between neighbor and tabu point typedef struct{ //creating a structure for tabu list float c[2]; int tabu_time; }tabu tabu tabu_el[DIM_TABU]; float al[DIM_AL][2]; //creating aspiration list chrom FP[DIM_POP]; pickchrom(population) //sorting population for(int i=0;i<DIM_POP;i++) { FP[i]=population[i]; } //after sort the population the best on and the worst one are in the first //and last position respectively chrom best=FP[0]; chrom worst=FP[DIM_POP]; void tabu_search(chrom FP[DIM_POP], best, worst) { int I=0; int i,k,j,t; add(best); //call to function to add element in tabu list for(i=0;i<DIM_TABU;i++) tabu_el.tabu_time[i]=F; while(I<F) { for(i=0;i<DIM_TABU;i++) if(tabu_el[i].tabu_time==0) { al[j][0]=tabu_el[i].c[0]; //indice j da chiarire per asp. list al[j][1]=tabu_el[i].c[1]; delete(i); //call to function to delete element from tabu list } for(j=1;j<DIM_POP;j++) for(k=0;k<DIM_TABU;k++) { if(distance(FP[j].point,tabu_el.c)<R) if(al[][]==NULL) { FP[j]=worst; } else { FP[j]=al[][]; } } for(t=0;t<DIM_TABU;t++) tabu_el[t].tabu_time--; I++; }
procedo bene? cambieresti qualcosa del mio codice? Ad esempio come vedi ho ancora ben chiaro come definire l'aspiration list. Ho usato una matrice DIM_ALx2 per questa ma non so se è una buona idea
a pensarci bene, si può utilizzare una coda FIFO con vettori, l'unico accorgimento è navigare la lista, il resto si può gestire tutto con enqueue() e dequeue(). Questo perchè il tabu-time corrisponde al tempo di inserimento nella FIFO, perciò il codice non viene complicato, scusa se ho parlato di double linked list e cose varie non avevo considerato il tempo di inserimento 
naaa il tuo codice, non può funzionare... Ci sono troppe condizioni (sia del testo originale, sia delle proprietà della TL) che non mantieni... alcune sono corrette invece. Appena ho un attimo guardo meglio il tutto. Se riesci cerca di scrivere la TL basandoto sulla proprietà FIFO, così si sitema tutto da se, ma cmq pian piano sistemiamo tutto

naaa il tuo codice, non può funzionare... Ci sono troppe condizioni (sia del testo originale, sia delle proprietà della TL) che non mantieni... alcune sono corrette invece. Appena ho un attimo guardo meglio il tutto. Se riesci cerca di scrivere la TL basandoto sulla proprietà FIFO, così si sitema tutto da se, ma cmq pian piano sistemiamo tutto

Visto che ho un po' di voglia sto guardando come sistemarti il codice inserendoti le proprietà FIFO.
Qualche post sopra me ne hai parlato pure te
perciò penso tu conosca e non serve ti spieghi il codice, te lo copio qui appena finisco se no tiriamo il discorso ancora per una settimana e giriamo con pseudo-codice che da quanto ho visto non comprendi a pieno...
Ora ci sono alcune cose extra da chiarire, oltre la questione liste che serve per far funzionare l'algoritmo ibrido:
- quante iterazioni fai fare all'algoritmo genetico, cioè quante popolazioni crei?
- per scrivere pickchroms() la funzione che ordina per fitness, hai seguito qualche schema di algoritmi di ordinamento conosciuti? ad occhio mi sembra utilizzi un algoritmo naive parecchio inefficiente, visto che dal numero di iterazioni dell'algoritmo genetico, ti renderà il tutto "appesantito" da questo ordinamento (se conosci le classi di complessità, avrai una limitazione asintotica superiore dell'ordinamente che sovrasta tutto il resto).
Qui il codice Tabu_search + code AL e TL in modalità FIFO:
da tenere in considerazione che si può scrivere e modulare in parecchi modi, io lo ho scritto in una pagina, ma puoi benissimo modoularizzare il codice (consigliato) in vari file con i vari header.
Ci sono alcune funzioni ridondanti (next(),fullp,emptyp) si possono togliere e generalizzare... fai come credi per te più comodo (non avevo voglia di scrivere altro)
In un altro momento te lo commento in modo più specifico, ma se conosci le FIFO è esattamento lo stesso utilizzo, ho solo specializzate le fuzioni al nostro caso con Tabu_search e le sue condizioni. Ci dovrebbero essere alcuni punti ancora da sistemare come la dimensione della TL, il TABU_TIME dipende da cosa mi rispondi alle domande sopra, io ho usato un parametro standard, cioè usare 3/4 della dimensione dei vicini, e le iterazioni. Infine c'è da scrivere la funzione DISTANCE, cosa che la lascio a te
Qualche post sopra me ne hai parlato pure te
Una semplice coda FIFO eliminerrebbe il piu vecchio elemento della lista già alla prima iterazione senza quindi tener conto dell'apiration time.
perciò penso tu conosca e non serve ti spieghi il codice, te lo copio qui appena finisco se no tiriamo il discorso ancora per una settimana e giriamo con pseudo-codice che da quanto ho visto non comprendi a pieno...

Ora ci sono alcune cose extra da chiarire, oltre la questione liste che serve per far funzionare l'algoritmo ibrido:
- quante iterazioni fai fare all'algoritmo genetico, cioè quante popolazioni crei?
- per scrivere pickchroms() la funzione che ordina per fitness, hai seguito qualche schema di algoritmi di ordinamento conosciuti? ad occhio mi sembra utilizzi un algoritmo naive parecchio inefficiente, visto che dal numero di iterazioni dell'algoritmo genetico, ti renderà il tutto "appesantito" da questo ordinamento (se conosci le classi di complessità, avrai una limitazione asintotica superiore dell'ordinamente che sovrasta tutto il resto).
Qui il codice Tabu_search + code AL e TL in modalità FIFO:
#define DIM_POP 100 struct chrom; struct aspiration_list; struct tabu_el; struct tabu_list; typedef enum {FALSE,TRUE} boolean; typedef struct{ float point[2]; float fit; }chrom; typedef struct{ int head; int tail; int DIM; chrom* 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; void cp_chrom(chrom*,chrom*); //funzione da scrivere boolean DISTANCE(chrom*,chrom*); //TABU_LIST FUN int next_tl(int,tabu_list*); tabu_list* init_tl(int); boolean emptyp(tabu_list*); boolean fullp(tabu_list*); void add_tl(chrom*,tabu_list*,int); chrom* delete_tl(tabu_list*); void time_zero_TT(tabu_list*); boolean time_zero(tabu_list*); //ASPIRATION_LIST FUN int next_al(int,aspiration_list*); aspiration_list* init_al(int); boolean emptyp_al(aspiration_list*); boolean fullp_al(aspiration_list*); void add_al (chrom*,aspiration_list*); chrom* delete_al(aspiration_list*); void Tabu_Search(chrom*,chrom*); void cp_chrom(chrom* a,chrom* f){ a->point[0]=f->point[0]; a->point[1]=f->point[1]; a->fit = f->fit; } //TABU LIST FUN int next_tl(int index, tabu_list* tl){ return (index+1)%tl->DIM_LIST; } tabu_list* init_tl(int dim_tl){ tabu_list* tl = malloc(sizeof(tabu_list)); if(tl==NULL){ return NULL; } tl->tabu_l = malloc(sizeof(tabu_el)*dim_tl); if(tl->tabu_l==NULL){ return NULL; } tl->DIM_LIST=dim_tl; tl->tail=tl->head=0; return tl; } boolean emptyp(tabu_list* tl){ return (boolean)(tl->tail==tl->head); } boolean fullp(tabu_list* tl){ return (boolean)(next_tl(tl->tail,tl)==tl->head); } void add_tl(chrom* n,tabu_list* tl,int TABU_TIME){ //se la tabu_list è piena si elimina l'elemento più vecchio e distante dal cromosoma migliore if (fullp(tl)){ delete_tl(tl); } cp_chrom(n,&(tl->tabu_l[tl->tail].ch)); tl->tabu_l[tl->tail].tabu_time = TABU_TIME; tl->tail = next_tl(tl->tail,tl); } chrom* delete_tl(tabu_list* tl){ chrom* c; if (emptyp(tl)){ c = NULL; } else { c = &tl->tabu_l[tl->head].ch; tl->head = next_tl(tl->head,tl); } return c; } void time_zero_TT(tabu_list* tl){ int j=tl->head; while(j!=tl->tail){ tl->tabu_l[j].tabu_time--; j=next_tl(j,tl); } } boolean time_zero(tabu_list* tl){ return (boolean)(tl->tabu_l[tl->head].tabu_time==0); } //ASPIRATION LIST FUN int next_al(int index,aspiration_list* al) { return (index+1)%al->DIM; } aspiration_list* init_al(int DIM){ aspiration_list* al = malloc(sizeof(aspiration_list)); if(al==NULL){ return NULL; } al->aspiration_l = malloc(sizeof(chrom)*DIM); if(al->aspiration_l==NULL){ return NULL; } al->DIM=DIM; al->tail=al->head=0; return al; } boolean emptyp_al(aspiration_list* al) { return (boolean) (al->tail==al->head); } boolean fullp_al(aspiration_list* al) { return (boolean)(next_al(al->tail,al)==al->head); } void add_al (chrom* a,aspiration_list* al){ if (fullp_al(al)){ delete_al(al); } cp_chrom(a,&al->aspiration_l[al->tail]); al->tail = next_al(al->tail,al); } chrom* delete_al(aspiration_list* al) { chrom* c; if (emptyp_al(al)){ c=NULL; } else { c = &(al->aspiration_l[al->tail]); al->head = next_al(al->head,al); } return c; } void Tabu_Search(chrom* P,chrom* FP){ int TABU_TIME = ceil((DIM_POP-2)/50)*36; int ITERATION = 4*DIM_POP; int DIM_TL = 3*DIM_POP; int k = 0; int I = 0; int f = 0; int it_FP = DIM_POP-1; tabu_list* TL = init_tl(DIM_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); } add_tl(&(P[0]),TL,TABU_TIME); while(I<ITERATION){ //gli elementi a TIME_TABU=0 possono essere solo singoli elementi per iterazione, cioè può essere UNO solo. //perciò basta controllare solo l'elemento da più tempo in lista, corrispondente all'elemento in testa if(time_zero(TL)){ add_al(delete_tl(TL),AL); } k=1; /* interatore sulla popolazione P, */ /* inizializzato ad 1 per non analizzare il cromosoma con fitness migliore corrispondente all'elemento 0 */ while(k<DIM_POP){ //navigazione in TABU_LIST in ordine di inserimento decrescente f=TL->head; while(f!=TL->tail){ //scrivere la funzione boolean DISTANCE(chrom*,chrom*) if(DISTANCE(&(P[k]),&(TL->tabu_l[f].ch))){ if(emptyp_al(AL)){ //se la AL è vuota P[k]=FP[it_FP]; 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),&(P[k])); } } f=next_tl(f,TL); } k++; } //si diminuisce il tabu time per ogni elemento time_zero_TT(TL); I++; } }
da tenere in considerazione che si può scrivere e modulare in parecchi modi, io lo ho scritto in una pagina, ma puoi benissimo modoularizzare il codice (consigliato) in vari file con i vari header.
Ci sono alcune funzioni ridondanti (next(),fullp,emptyp) si possono togliere e generalizzare... fai come credi per te più comodo (non avevo voglia di scrivere altro)

In un altro momento te lo commento in modo più specifico, ma se conosci le FIFO è esattamento lo stesso utilizzo, ho solo specializzate le fuzioni al nostro caso con Tabu_search e le sue condizioni. Ci dovrebbero essere alcuni punti ancora da sistemare come la dimensione della TL, il TABU_TIME dipende da cosa mi rispondi alle domande sopra, io ho usato un parametro standard, cioè usare 3/4 della dimensione dei vicini, e le iterazioni. Infine c'è da scrivere la funzione DISTANCE, cosa che la lascio a te

grazie il codice è molto chiaro. volevo chiederti 2 cose:
1) cos'è ceil((DIM_POP-2)/50)*36 quando definisci la TABU_TIME? non l'hai definita da nessuna parte nel codice
2)nella funzione add_tl non capisco se è stato un tuo errore o una mia incomprensione. alla funzione cp_chrom passi i parametri a ed f ma penso che li hai inseriti nell'ordine sbagliato. infatti nel caso in cui scrivi cp_chrom(n,&(tl->tabu_l[tl->tail].ch)) nella funzione add_tl copi il valore nella tabu list in P[0] il che deve essere al contrario. inoltre quando richiami cp_chrom(delete_al(AL),&(P[k])) copi P[k] nell'aspiration list il che deve essere il contrario come da teoria. se non sbaglio dovrei scrivere void cp_chrom(chrom* f,chrom* a)
1) cos'è ceil((DIM_POP-2)/50)*36 quando definisci la TABU_TIME? non l'hai definita da nessuna parte nel codice
2)nella funzione add_tl non capisco se è stato un tuo errore o una mia incomprensione. alla funzione cp_chrom passi i parametri a ed f ma penso che li hai inseriti nell'ordine sbagliato. infatti nel caso in cui scrivi cp_chrom(n,&(tl->tabu_l[tl->tail].ch)) nella funzione add_tl copi il valore nella tabu list in P[0] il che deve essere al contrario. inoltre quando richiami cp_chrom(delete_al(AL),&(P[k])) copi P[k] nell'aspiration list il che deve essere il contrario come da teoria. se non sbaglio dovrei scrivere void cp_chrom(chrom* f,chrom* a)