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 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[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]