Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Giuseppe Bruno » 7.La Tabu Search


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!

xX

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).
  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion