Pesquisa tabu

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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 arrefecimento simulado.


Origem do nome[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

Bibliografia[editar | editar código-fonte]

  • 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[editar | editar código-fonte]