Pesquisa tabu

A Pesquisa (ou Busca) Tabu é uma Meta-heurística e um procedimento adaptativo auxiliar, que guia um algoritmo de busca local na exploração contínua dentro de um espaço de busca.

A partir de uma solução inicial, tenta avançar para uma outra solução (melhor que a anterior) na sua vizinhança até que se satisfaça um determinado critério de parada.

O algoritmo de pesquisa tabu foi proposto por Glover [GMN85], na década de 1970 e, é uma técnica muito semelhante à do recozimento simulado.

Origem do nome

A origem da palavra tabu remonta ao Tongan, um idioma da Polinésia. A palavra era utilizada pelos nativos da ilha Tonga para indicar objetos que não podiam ser tocados por serem sagrados.

O nome deste método vem das listas tabu, que consistem em listas com soluções não permitidas. Na sua forma mais básica, contém os $n$ últimos elementos visitados. Outras listas podem conter soluções proibidas devido a, por exemplo, certos atributos da solução ou movimentos ilegais no contexto do problema.

Propriedades

A Busca Tabu não é confundida pela ausência de vizinhos aprimorantes, pois o método é construído de forma a evitar o retorno a um ótimo local previamente visitado. Esta característica faz com que o método seja capaz de superar a otimalidade local e atingir um resultado ótimo ou próximo ao ótimo global.

Métodos Relacionados

• Simulated annealing
• Algoritmos genéticos
• GRASP, ou greedy randomized adaptive search procedure
• Ant colony
• Busca local guiada

Bibliografia

• Glover, F. and M. Laguna, 1997, Tabu Search. Kluwer, Norwell, MA.
• Glover, F. "Tabu Search — Part I", ORSA Journal on Computing, 1989 1: 3, 190-206.
• Glover, F. "Tabu Search — Part II", ORSA Journal on Computing, 1990 2: 1, 4-32.
• Cvijovic, D.; Klinowski, J. "Taboo search - an approach to the multiple minima problem". Science 1995 267, 664-666.

Ligações externas

• ParadisEO é um framework em C++ para meta-heuristicas, incluindo Busca Tabu
• Visualização do algoritmo da Busca Tabu (Applet)