Tabu search in linguaggio c .
Salve a tutti, devo realizzare un algoritmo ibrido simulated annealing + tabu search per il massimo di una funzione in linguaggio C. Qualcuno sa darmi qualche idea, soprattutto sulla tabu search. grazie in anticipo. è urgente
Risposte
Sostanzialmente devi definire delle mosse per modificare la soluzione. Ad ogni iterazione generi il vicinato come tutte le soluzioni raggiungibili tramite una mossa dalla soluzione corrente, escluse le mosse inverse più recenti (mosse tabù), poi scegli la soluzione migliore nel vicinato e iteri nuovamente.
Per un'introduzione dettagliata c'è A tutorial on tabu search. Prova anche a cercare su Google Scholar "Tabu Search TuoProblema", magari qualcuno ha già affrontato il problema.
Se invece ti servono consigli più concreti dovresti dare più dettagli sul tuo problema.
Per un'introduzione dettagliata c'è A tutorial on tabu search. Prova anche a cercare su Google Scholar "Tabu Search TuoProblema", magari qualcuno ha già affrontato il problema.
Se invece ti servono consigli più concreti dovresti dare più dettagli sul tuo problema.
Ciao,
hai dato un'occhiata a questa discussione: tabu-search-t82565.html
In quel post si è descritto un algoritmo ibrido della specie: Memetic Algorithm (Genetic Algorithm + Tabu Search) per trovare il massimo di una funzione.
vedi se trovi qualcosa di utile, in caso contrario ne discutiamo volentieri.
EDIT: corretto link
hai dato un'occhiata a questa discussione: tabu-search-t82565.html
In quel post si è descritto un algoritmo ibrido della specie: Memetic Algorithm (Genetic Algorithm + Tabu Search) per trovare il massimo di una funzione.
vedi se trovi qualcosa di utile, in caso contrario ne discutiamo volentieri.
EDIT: corretto link
Ho già realizzato il Simulated Annealing trovando una buona approssimazione del massimo di una funzione. Adesso devo migliorarlo passando il valore ottenuto alla Tabu Search. Il mio problema è come generare una nuova configurazione nell' intorno della soluzione corrente e con quale criterio accettare mosse peggiorative
Nessuno sa darmi qualche informazione?? é urgente!!!
Allora l'algoritmo simulated annealing ibrido non lo ho mai visto, sicuro qualcuno (come è stao consigliato) lo ha già strutturato in modo che sia possibile renderlo ibrido, basterebbe cercare...
Prima cosa sarebbe utile vedere lo schema dell'algoritmo che hai pensato (non serve il codice, basta lo schema) così ti si può dire dove effettivamente è utile inserire la Tabu Search. Lo schema classico del simulated annealing ha una parte che si chiama "annealing schedule" penso che qui sia da inserire, visto che si aggiorna la soluzione.
come è strutturata la soluzione parziale nel momento in cui entra in gioco la tabu search?
Nel senso, come hai costruito l'insieme della soluzione parziale ottima? E' un insieme di dati che ha più fasi hai salvato e perciò sono punti di ottimo locali, oppure sono punti dello stesso intorno dove solo uno è un ottimo locale?
se è solo per aggiornare e creare la Tabu-List, un criterio di facile scrittura è utilizzare la distanza euclidea per un $\epsilon$ fissato, dal punto che si tiene in considerazione (es. lo si è utilizzato nella discussione che ti ho linkato nel post sopra, li descrive praticamente l'intero algoritmo, basterebbe solo legarlo al tuo con SA).
Il resto, come il Tabu_Time (se utilizzarlo fisso, dinamico, o reattivo) è legato all'algoritmo di base (SA) che bisognerebbe sapere come lo hai schematizzato.
Prima cosa sarebbe utile vedere lo schema dell'algoritmo che hai pensato (non serve il codice, basta lo schema) così ti si può dire dove effettivamente è utile inserire la Tabu Search. Lo schema classico del simulated annealing ha una parte che si chiama "annealing schedule" penso che qui sia da inserire, visto che si aggiorna la soluzione.
"gessic":
Ho già realizzato il Simulated Annealing trovando una buona approssimazione del massimo di una funzione. Adesso devo migliorarlo passando il valore ottenuto alla Tabu Search.
come è strutturata la soluzione parziale nel momento in cui entra in gioco la tabu search?
Nel senso, come hai costruito l'insieme della soluzione parziale ottima? E' un insieme di dati che ha più fasi hai salvato e perciò sono punti di ottimo locali, oppure sono punti dello stesso intorno dove solo uno è un ottimo locale?
Il mio problema è come generare una nuova configurazione nell' intorno della soluzione corrente e con quale criterio accettare mosse peggiorative
se è solo per aggiornare e creare la Tabu-List, un criterio di facile scrittura è utilizzare la distanza euclidea per un $\epsilon$ fissato, dal punto che si tiene in considerazione (es. lo si è utilizzato nella discussione che ti ho linkato nel post sopra, li descrive praticamente l'intero algoritmo, basterebbe solo legarlo al tuo con SA).
Il resto, come il Tabu_Time (se utilizzarlo fisso, dinamico, o reattivo) è legato all'algoritmo di base (SA) che bisognerebbe sapere come lo hai schematizzato.
Dunque io ho inizializzato la temperatura ho dato un valore alto. Ho generato due numeri random in [a,b] e ho visto se si aveva un miglioramento della funzione o un peggioramento. Se Si ha un miglioramento la configurazione viene accettata se si ha un peggioramento allora calcolo la probabilità di accettazione della soluzione con il criterio che usa il Simulated annealing . Questo lo faccio un numero di volte a temperatura costante. Dopo di che diminuisco la temperatura e inizio un nuovo ciclo iterativo. a questo punto trovo un'approssimazione del massimo globale (lo riesco a trovare sempre perchè ho verificato). Adesso dovrei inserire la Tabu search per migliorare il valore, questo è quello che ho capito dalla spiegazione del mio prof.
"gessic":
Dunque io ho inizializzato la temperatura ho dato un valore alto. Ho generato due numeri random in [a,b] e ho visto se si aveva un miglioramento della funzione o un peggioramento. Se Si ha un miglioramento la configurazione viene accettata se si ha un peggioramento allora calcolo la probabilità di accettazione della soluzione con il criterio che usa il Simulated annealing . Questo lo faccio un numero di volte a temperatura costante. Dopo di che diminuisco la temperatura e inizio un nuovo ciclo iterativo. a questo punto trovo un'approssimazione del massimo globale (lo riesco a trovare sempre perchè ho verificato). Adesso dovrei inserire la Tabu search per migliorare il valore, questo è quello che ho capito dalla spiegazione del mio prof.
ok, dopo ti scrivo qualcosa
con schema comunque non intendevo la descrizione a parole, ma tipo lo pseudo-codice o un diagram. Ma vedo cosa si può fare, appena ho un momento.
Lo schema è supergiù questo:
Inizializzazione di T ed X
While Not (condizione di uscita)
Do Begin
for i:=1 to L
Do Begin
Generazione di Y da X
IF f(Y ) > f(X)
Then X:=Y
Else if e^( f(X) - f(Y))/T) > random(0; 1)
Then X:=Y
End
Riduzione del parametro T
End
Inizializzazione di T ed X
While Not (condizione di uscita)
Do Begin
for i:=1 to L
Do Begin
Generazione di Y da X
IF f(Y ) > f(X)
Then X:=Y
Else if e^( f(X) - f(Y))/T) > random(0; 1)
Then X:=Y
End
Riduzione del parametro T
End
Allora due cose:
- l'algoritmo ibrido deve essere Simulated Annealing base, con ricerca locale come aggiunta.
Oppure può essere un vero ibrido con TS che si amalgama con l'algoritmo SA, per capirci se non funziona la parte di SA rimane funzionante solo TS, perciò rimarrebbe un algoritmo di Tabu_Search.
- il problema è massimizzare una funzione a più variabili spero (X è un vettore)? Ad una variabile è sprecato una algoritmo del genere...
comunque il codice che hai scritto è il classico Simulated Annealing, pensavo altro.
Visto che comuque io non ho mai avuto modo di vedere un ibrido con Simulated Annealing, non conosco le problematiche che possono nascere ad unire due strategie di ricerca, una probabilistica (SA) e un'altra deterministica (TS) [non mi piace molto il termine, ma non mi vengono sinonimi, sarebbe più corretto dire che "ha memoria"].
Cercando su un libro ho trovato un'interessante ibrido, che però non è veramente un SA+TS, ma più il contrario strategia TS (ma non completamente, esiste Tabu-List ma che può essere messa in correlazione con l'Aspiration-list, per capirci si può far quel che si vuole...) con algoritmo SA (come scritto nella domanda sopra).
In pratica: TS framework + SA embedded (cit. libro).
Se ti va bene una cosa del genere vediamo di modificare il tuo algoritmo, in caso contrario si cerca altro (ne esistono tanti, ma ho cercato dove conosco).
questo sarebbe l'algoritmo solo per farti passare l'idea:
while(terminate){
tabu_search{
tabu-step: accept_solution A
move_best
}
simulated annealing{
if prop(A,T)
A' = A
else
T = T*
}
}
Il tuo penso dobrebbe essere:
simultated annealing{
tuo algoritmo.
tabu_search()
}
cioè un qualcosa da inserire alla fine per proibire le soluzione, ma che da problematiche per il motivo prob/determ secondo me. Sarebbe meglio un algoritmo che renda unico il tutto. vedi te e cosa ti abbia detto il docente.
- l'algoritmo ibrido deve essere Simulated Annealing base, con ricerca locale come aggiunta.
Oppure può essere un vero ibrido con TS che si amalgama con l'algoritmo SA, per capirci se non funziona la parte di SA rimane funzionante solo TS, perciò rimarrebbe un algoritmo di Tabu_Search.
- il problema è massimizzare una funzione a più variabili spero (X è un vettore)? Ad una variabile è sprecato una algoritmo del genere...
comunque il codice che hai scritto è il classico Simulated Annealing, pensavo altro.
Visto che comuque io non ho mai avuto modo di vedere un ibrido con Simulated Annealing, non conosco le problematiche che possono nascere ad unire due strategie di ricerca, una probabilistica (SA) e un'altra deterministica (TS) [non mi piace molto il termine, ma non mi vengono sinonimi, sarebbe più corretto dire che "ha memoria"].
Cercando su un libro ho trovato un'interessante ibrido, che però non è veramente un SA+TS, ma più il contrario strategia TS (ma non completamente, esiste Tabu-List ma che può essere messa in correlazione con l'Aspiration-list, per capirci si può far quel che si vuole...) con algoritmo SA (come scritto nella domanda sopra).
In pratica: TS framework + SA embedded (cit. libro).
Se ti va bene una cosa del genere vediamo di modificare il tuo algoritmo, in caso contrario si cerca altro (ne esistono tanti, ma ho cercato dove conosco).
questo sarebbe l'algoritmo solo per farti passare l'idea:
while(terminate){
tabu_search{
tabu-step: accept_solution A
move_best
}
simulated annealing{
if prop(A,T)
A' = A
else
T = T*
}
}
Il tuo penso dobrebbe essere:
simultated annealing{
tuo algoritmo.
tabu_search()
}
cioè un qualcosa da inserire alla fine per proibire le soluzione, ma che da problematiche per il motivo prob/determ secondo me. Sarebbe meglio un algoritmo che renda unico il tutto. vedi te e cosa ti abbia detto il docente.
ok grazie chiederò meglio al mio prof...grazie mille
"gessic":
ok grazie chiederò meglio al mio prof...grazie mille
ok facci sapere, è un algoritmo ibrido interessante
lo consegnerò il prossimo appello. grazie mille comunque. appena avrò notizie vi farò sapere.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo