Argomenti della lezione
- Introduzione
- Caratteristiche della procedura
- I passi della procedura
- Considerazioni generali
Tabu Search: Introduzione
In termini generali un problema di ottimizzazione può essere formulato come
z = f (x) Max!
x∈X
con
- X di insieme di soluzioni ammissibili
- z=f(x) funzione obiettivo z=f(x) da massimizzare
Una soluzione x*∈X è un massimo locale se f(x*)≥f(x) per ogni x ∈Iε(x);
Una soluzione x*∈X è un massimo globale se f(x*)≥f(x) per ogni x ∈X.
Tabu Search: Introduzione (segue)
Problema e metodo di risoluzione
Una volta formalizzato un problema di ottimizzazione si pone il problema di individuarne le soluzioni (ottimi globali o locali).
Un metodo di risoluzione è una tecnica che consente di trovare soluzioni del problema.
Un metodo di risoluzione può essere:
- esatto se individua un ottimo globale ammissibile
- euristico se è orientato alla ricerca di una buona soluzione (ma non necessariamente ottima).
Tabu Search: Introduzione (segue)
In presenza di problemi complessi dal punto di vista computazionale (NP-hard) nelle applicazioni è necessario ricorrere a tecniche euristiche di risoluzione.
Le tecniche costruttive sono orientate alla individuazione (costruzione) di una soluzione ammissibile.
Le tecniche migliorative o di ricerca locale partono da una soluzione ammissibile e puntano a migliorarla attraverso la applicazione iterativa di una mossa. Esse convergono in un ottimo locale.
Per migliorare la qualità delle soluzioni individuabili con queste tecniche è possibile ricorrere a tecniche cosiddette metaeuristiche.
Tabu Search: Introduzione (segue)
Tabu Search: Introduzione (segue)
Tabu Search: Introduzione (segue)
La qualità della soluzione ottenibile da una tecnica di ricerca locale dipende dalla soluzione di innesto e dalla tipologia di mossa.
Per superare la “trappola” della convergenza in un minimo locale, in corrispondenza di esso, bisognerebbe individuare una procedura che consenta di accettare soluzioni peggiorative.
Tuttavia, in corrispondenza di un minimo locale, scegliendo una soluzione peggiorativa, al passo successivo si ritornerebbe ad esaminare il minimo locale e la procedura entrerebbe in loop.
Tabu Search: Introduzione (segue)
Tabu Search: Introduzione (segue)
Per superare la “trappola” della convergenza in un minimo locale, in corrispondenza di esso, bisognerebbe individuare una procedura che
- consenta di accettare soluzioni peggiorative;
- eviti il passaggio per soluzioni già esaminate.
Tabu Search: caratteristiche della procedura
La Tabu Search è una procedura metaeuristica che migliora l’efficienza di un classico algoritmo di ricerca locale memorizzando informazioni che riguardano il processo di ricerca in modo da uscire da situazioni di stallo in corrispondenza del raggiungimento di punti di minimo locale.
Ad ogni iterazione k si considera un intorno N(S,k)⊂N(S) dove, rispetto ad N(S), sono state rimosse alcune soluzioni definite tabu, sulla base di una memoria del processo di ricerca effettuato fino all’iterazione k.
Le soluzioni tabu non sono raggiungibili all’iterazione successiva.
Tabu Search: caratteristiche della procedura (segue)
Per avere memoria del processo di ricerca si considera un insieme di informazioni sintetiche dette attributi che sono memorizzati in una o più liste tabu. Ad ogni iterazione, alle liste tabu vanno aggiunti nuovi attributi.
Le liste tabu sono di dimensioni limitate del tipo FIFO (First In First Out). In questo modo, se TL è la lunghezza della lista tabu, un attributo che entra in lista all’iterazione k vi esce all’iterazione k+TL rendendo così nuovamente ammissibile l’attributo.
Tabu Search: caratteristiche della procedura (segue)
In pratica gli attributi sono informazioni sintetiche che devono consentire di evitare il passaggio per soluzioni già esaminate. In questo modo l’intorno della soluzione corrente si riduce eliminando tutte quelle soluzioni che presentano attributi tabu.
Per illustrare questo concetto si consideri un problema di TSP di 8 città, e si ipotizzi di utilizzare una mossa di scambio nell’ordine di visita di due città i e j (swap(i,j)). Si supponga che a partire dalla soluzione S riportata, la migliore soluzione dell’intorno S’ sia individuata dallo scambio di posizione del nodo 3 con il nodo 7 swap(3,7).
Tabu Search: caratteristiche della procedura (segue)
Per impedire che al passo successivo si esegua la mossa inversa (swap(7,3)) che riporterebbe l’algoritmo nella soluzione precedente, si inserisce qualche “attributo” della mossa nella lista tabu.
Possibili scelte di attributi sono, ad esempio,
- (A1) la posizione del primo nodo dello swap;
- (A2) la posizione del secondo nodo dello swap;
- (A3) la coppia ((A1)or(A2));
- (A4) la coppia ((A1)and(A2));
Secondo la scelta che si adotta cambiano le mosse considerate tabu e, quindi, la dimensione dell’intorno N(S,k).
Tabu Search: caratteristiche della procedura (segue)
Per definire la lunghezza TL della lista tabu si può ricorrere a regole statiche o regole dinamiche
Le regole statiche fissano un valore della lunghezza della lista che resta invariato per tutto l’algoritmo. Valori tipici di TL sono compresi tra 5 e 20; un’altra regola suggerisce di scegliere il valore √n se n è la dimensione del problema.
Le regole dinamiche prevedono, invece, un’attribuzione variabile della dimensione delle liste durante l’esecuzione. Una regola dinamica spesso utilizzata prevede che, ad ogni iterazione, fissati a priori due valori minimi e massimi per TL, si assegna all’attributo che deve entrare nella lista tabu, un periodo di permanenza in lista casuale compreso tra TLmin e TLmax.
Tabu Search: i passi della procedura
1. Inizializzazione
Si individua una soluzione S di innesco dell’algoritmo.
2. Definizione intorno soluzione corrente e scelta nuova soluzione
All’iterazione generica k, si definisce un intorno N(S,k) della soluzione corrente S; si individua la soluzione S‘ di N(S,k) migliore sulla base di uno stimatore E[N(S,k)] e si sostituisce S con S‘.
3. Criterio di arresto
Se un certo criterio di arresto è soddisfatto l’algoritmo si interrompe; altrimenti si pone k=k+1 e si torna al passo 2. Come soluzione finale si adotta la migliore soluzione individuata durante l’intero processo di ricerca.
Tabu Search: i passi della procedura (segue)
La soluzione di innesco dell’algoritmo può esser individuata casualmente o attraverso un algoritmo costruttivo.
Lo stimatore E[N(S,k)] viene di solito assunto coincidente con la funzione obiettivo ma può anche essere diverso.
La procedura non converge naturalmente. Per chiuderla è necessario definire un criterio di arresto. Esempi di criteri di arresto sono:
- numero massimo di iterazioni;
- numero massimo iterazioni non migliorative.
Tabu Search: i passi della procedura (segue)
Per migliorare la qualità della soluzione ottenuta si possono introdurre le fasi di intensificazione e diversificazione.
L’intensificazione dirige la ricerca nell’intorno di soluzioni buone già individuate.
La diversificazione consiste nello spostare la ricerca verso nuove regioni che non sono state ancora esplorate. Per diversificare è necessario modificare sensibilmente la soluzione corrente o la migliore soluzione ottenuta.
Le fasi di intensificazione e/o diversificazione vanno introdotte nel corso del processo di ricerca quando le strutture di memoria a breve termine non risultano più efficaci. Si possono avviare dopo un certo numero di iterazioni consecutive non migliorative (es: dopo 100 iterazioni dall’individuazione della soluzione migliore) o dopo un certo numero prefissato di iterazioni totali (es: ogni 1000 iterazioni).
Tabu Search: i passi della procedura (segue)
Tabu Search: considerazioni generali
La qualità della soluzione ottenibile dipende dai diversi parametri di calibrazione della procedura ovvero:
- Tipo di mossa;
- Organizzazione lista tabu (attributi, lunghezza lista);
- Criteri di innesto delle fasi di diversificazione ed intensificazione;
- Criterio di arresto.
Tabu Search: considerazioni generali
Caratteristiche generali della procedura
- Produce soluzioni molto buone;
- Presenta una discreta flessibilità intesa come capacità di adattamento per la risoluzione di problemi diversi;
- L’implementazione non risulta particolarmente complessa;
- Risulta piuttosto sensibile alla scelta dei parametri di calibrazione;
- I tempi di calcolo dipendono dal criterio di arresto (in generale si eseguono migliaia di iterazioni).
Le lezioni del Corso
1. Introduzione al corso di Ricerca operativa II
2. Generalità e classificazione dei sistemi di produzione
3. La logistica dei sistemi di produzione
4. Introduzione all'ottimizzazione combinatoria
5. Fondamenti di teoria della complessità computazionale
6. Algoritmi euristici costruttivi e migliorativi
10. Problemi di Localizzazione
12. Introduzione alla gestione delle scorte
13. Modelli stocastici per la gestione delle scorte
14. Modelli discreti per la gestione delle scorte
15. Introduzione allo scheduling
16. Scheduling su macchina singola
17. Problemi di scheduling su macchina singola e su macchine parall...
