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 ú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)
