Tabu search is a mathematical optimization method, belonging to the class of local search techniques. Tabu search enhances the performance of a local search method by using memory structures. Tabu search is generally attributed to Fred Glover. Tabu search uses a local or neighbourhood search procedure to iteratively move from a solution x to a solution x' in the neighbourhood of x, until some stopping criterion has been satisfied. To explore regions of the search space that would be left unexplored by the local search procedure and---by doing this---escape local optimality, tabu search modifies the neighbourhood structure of each solution as the search progresses. The solutions admitted to N * (x), the new neighbourhood, are determined through the use of special memory structures. The search now progresses by iteratively moving from a solution x to a solution x' in N * (x). Perhaps the most important type of short-term memory to determine the solutions in N * (x), also the one that gives its name to tabu search, is the use of a tabu list. In its simplest form, a tabu list contains the solutions that have been visited in the recent past (less than n moves ago, where n is the tabu tenure). Solutions in the tabu list are excluded from N * (x). Other tabu list structures prohibit solutions that have certain attributes (e.g. traveling salesman problem (TSP) solutions that include certain arcs) or prevent certain moves (e.g. an arc that was added to a TSP tour cannot be removed in the next n moves). Selected attributes in solutions recently visited are labelled tabu-active. Solutions that contain tabu-active elements are tabu. This type of short-term memory is also called recency-based memory. Tabu lists containing attributes are much more effective, although they raise a new problem. With forbidding an attribute as tabu, typically more than one solution is declared as tabu. Some of these solutions that must now be avoided might be of excellent quality and have not yet been visited. To overcome this problem, aspiration criteria are introduced which allow to override the tabu state of a solution and thus include it in the allowed set. A commonly used aspiration criterion is to allow solutions which are better than the currently best known solution. Related Methods Simulated Annealing (SA) is a related global optimization technique which traverses the search space by generating neighbouring solutions of the current solution. A superior neighbour is always accepted. An inferior neighbour is accepted probabilistically based on the difference in quality and a temperature parameter. The temperature parameter is modified as the algorithm progresses to alter the nature of the search. Genetic Algorithms (GA) maintain a pool of solutions rather than just one. The process of finding superior solutions mimics that of evolution, with solutions being combined or mutated to alter the pool of solutions, with solutions of inferior quality being discarded. Ant Colony Optimization (ACO) uses many animals (or agents) to traverse the solution space and find locally productive areas. While usually inferior to tabu search and other forms of local search, it is able to produce results in problems where no global or up-to-date perspective can be obtained, and thus the other methods cannot be applied. |
TESTO PARALLELO INCASELLATO |
|
Tabu search is a mathematical optimization method, belonging to the class of local search techniques. |
La Tabu search è un metodo matematico di ottimizzazione, appartenente alla classe delle tecniche di ricerca locale. |
|
Tabu search enhances the performance of a local search method by using memory structures. |
La tabu search migliora le prestazioni di un metodo di ricerca locale usando strutture di memoria. |
|
Tabu search is generally attributed to Fred Glover. |
La tabu search è usualmente attribuita a Fred Glover. |
|
Tabu search uses a local or neighbourhood search procedure to iteratively move from a solution x to a solution x' in the neighbourhood of x, until some stopping criterion has been satisfied. |
La tabu search usa una procedura di ricerca locale o di contiguità per muoversi iterativamente da una soluzione x verso una soluzione x' nell'intorno di x, fino a che non sia soddisfatto qualche criterio d'arresto. |
|
To explore regions of the search space that would be left unexplored by the local search procedure and---by doing this---escape local optimality, tabu search modifies the neighbourhood structure of each solution as the search progresses. |
Per esplorare regioni dello spazio della ricerca che sarebbero lasciate inesplorate dalla procedura locale di ricerca e, così facendo, sottrarsi all'ottimalizzazione locale, la tabu search modifica la struttura dell'intorno di ogni soluzione al progredire della ricerca. |
|
The solutions admitted to N * (x), the new neighbourhood, are determined through the use of special memory structures. |
Le soluzioni ammesse in N * (x), il nuovo intorno, sono determinate usando speciali strutture di memoria. |
|
The search now progresses by iteratively moving from a solution x to a solution x' in N * (x). |
La ricerca ora progredisce iterativamente muovendosi da una soluzione x verso una soluzione x' nella N * (x). |
|
Perhaps the most important type of short-term memory to determine the solutions in N * (x), also the one that gives its name to tabu search, is the use of a tabu list. |
Forse il tipo più importante di memoria a breve termine usato per determinare le soluzioni in N *(x), anche quello che dà il suo nome alla tabu search, è l'uso di una lista di tabu. |
|
In its simplest form, a tabu list contains the solutions that have been visited in the recent past (less than n moves ago, where n is the tabu tenure). |
Nella sua forma più semplice una tabu list contiene le soluzioni che sono state visitate nel recente passato (meno di n mosse fa, dove n è la durata del tabu). |
|
Solutions in the tabu list are excluded from N * (x). |
Le soluzioni della tabu list sono escluse da N *(x). |
|
Other tabu list structures prohibit solutions that have certain attributes (e.g. traveling salesman problem (TSP) solutions that include certain arcs) or prevent certain moves (e.g. an arc that was added to a TSP tour cannot be removed in the next n moves). |
Altre strutture di tabu list proibiscono le soluzioni che hanno certi attributi (per es. le soluzioni del problema del commesso viaggiatore [TSP- Traveling Salesman Problem] che includono determinati archi) o impediscono certe mosse (per es. un arco che è stato aggiunto in una visita del TSP non può essere rimosso nelle successive n mosse). |
|
Selected attributes in solutions recently visited are labelled tabu-active. |
Gli attributi selezionati nelle soluzioni recentemente visitate sono identificati tabu-attivi. |
|
Solutions that contain tabu-active elements are tabu. |
Le soluzioni che contengono gli elementi tabu-attivi sono tabu. |
|
This type of short-term memory is also called recency-based memory. |
Questo tipo di memoria a breve termine è anche detta memoria recency-based cioè basata sull'attualità. |
|
Tabu lists containing attributes are much more effective, although they raise a new problem. |
Le tabu list che contengono gli attributi sono molto più efficaci, anche se sollevano un nuovo problema. |
|
With forbidding an attribute as tabu, typically more than one solution is declared as tabu. |
Proibendo un attributo come tabu, in genere più di una soluzione è dichiarata tabu. |
|
Some of these solutions that must now be avoided might be of excellent quality and have not yet been visited. |
Alcune di queste soluzioni che devono ora essere evitate potrebbero essere di qualità eccellente e non essere state ancora visitate. |
|
To overcome this problem, aspiration criteria are introduced which allow to override the tabu state of a solution and thus include it in the allowed set. |
Per superare questo problema sono introdotti i criteri di aspirazione che consentono di escludere lo stato di tabu di una soluzione e così la includono nell'insieme ammissibile. |
|
A commonly used aspiration criterion is to allow solutions which are better than the currently best known solution. |
Un criterio di aspirazione comunemente usato è quello di permettere soluzioni che sono migliori della migliore soluzione attualmente conosciuta. |
|
Related Methods |
Metodi Correlati |
|
Simulated Annealing (SA) is a related global optimization technique which traverses the search space by generating neighbouring solutions of the current solution. |
La Simulated Annealing (SA) è una tecnica di ottimizzazione globale correlata che attraversa lo spazio di ricerca generando soluzioni nell'intorno di quella corrente. |
|
A superior neighbour is always accepted. |
Un vicino migliore (cioè che migliora la funzione obiettivo), è accettato sempre. |
|
An inferior neighbour is accepted probabilistically based on the difference in quality and a temperature parameter. |
Un vicino peggiore (cioè che peggiora la funzione obiettivo) è accettato con un criterio probabilistico basato sulla differenza nella qualità ed in un parametro di temperatura. |
|
The temperature parameter is modified as the algorithm progresses to alter the nature of the search. |
Il parametro di temperatura è modificato con il procedere dell'algoritmo per alterarne la natura della ricerca. |
|
Genetic Algorithms (GA) maintain a pool of solutions rather than just one. |
Gli Algoritmi Genetici usano un gruppo di soluzioni piuttosto che una sola. |
|
The process of finding superior solutions mimics that of evolution, with solutions being combined or mutated to alter the pool of solutions, with solutions of inferior quality being discarded. |
Il processo di ricerca delle soluzioni migliori imita quello dell'evoluzione naturale, con combinazioni o mutazioni che ne cambiano l'insieme, scartando inoltre quelle di qualità inferiore. |
|
Ant Colony Optimization (ACO) uses many animals (or agents) to traverse the solution space and find locally productive areas. |
La Ant Colony Optimization (ACO) [letteralmente ottimizzazione del formicaio] usa molti animali (o agenti) per attraversare lo spazio delle soluzioni e trovare aree localmente produttive. |
|
While usually inferior to tabu search and other forms of local search, it is able to produce results in problems where no global or up-to-date perspective can be obtained, and thus the other methods cannot be applied. |
Mentre di solito è meno efficiente rispetto alla tabu search e ad altre forme di ricerca locale, è in grado di fornire risultati nei problemi dove non si può ottenere nessuna euristica globale o aggiornata e quindi gli altri metodi non possono essere applicati. |
|