Pesquisa tabu - Tabu search

A pesquisa tabu é um método de pesquisa metaheurística que emprega métodos de pesquisa local usados ​​para otimização matemática . Foi criado por Fred W. Glover em 1986 e formalizado em 1989.

As buscas locais (na vizinhança) pegam uma solução potencial para um problema e verificam seus vizinhos imediatos (ou seja, soluções semelhantes, exceto por poucos detalhes menores) na esperança de encontrar uma solução melhorada. Os métodos de busca local tendem a ficar presos em regiões subótimas ou em planaltos onde muitas soluções são igualmente adequadas.

A pesquisa tabu aprimora o desempenho da pesquisa local relaxando sua regra básica. Em primeiro lugar, a cada passo os movimentos de piora podem ser aceitos se nenhum movimento de melhoria estiver disponível (como quando a busca está paralisada em um mínimo local estrito ). Além disso, proibições (doravante o termo tabu ) são introduzidas para desencorajar a busca de voltar a soluções previamente visitadas.

A implementação da pesquisa tabu usa estruturas de memória que descrevem as soluções visitadas ou conjuntos de regras fornecidos pelo usuário. Se uma solução potencial foi previamente visitada dentro de um determinado período de curto prazo ou se violou uma regra, ela é marcada como " tabu " (proibido) para que o algoritmo não considere essa possibilidade repetidamente.

Fundo

A palavra tabu vem da palavra tonganesa para indicar coisas que não podem ser tocadas porque são sagradas.

A busca tabu (TS) é um algoritmo metaheurístico que pode ser usado para resolver problemas de otimização combinatória (problemas em que se deseja uma ordenação e seleção de opções ótimas).

As aplicações atuais do TS abrangem as áreas de planejamento de recursos , telecomunicações, design VLSI , análise financeira, programação, planejamento de espaço, distribuição de energia, engenharia molecular, logística, classificação de padrões , manufatura flexível, gestão de resíduos, exploração mineral, análise biomédica, conservação ambiental e dezenas de outros. Nos últimos anos, periódicos em uma ampla variedade de campos publicaram artigos tutoriais e estudos computacionais documentando sucessos por busca tabu em estender a fronteira de problemas que podem ser tratados de forma eficaz - produzindo soluções cuja qualidade muitas vezes supera significativamente a obtida por métodos anteriormente aplicados. Uma lista abrangente de aplicativos, incluindo descrições resumidas dos ganhos obtidos com as implementações práticas, pode ser encontrada em Desenvolvimentos e aplicativos recentes de TS também podem ser encontrados em Tabu Search Vignettes .

Descrição básica

A busca tabu usa um procedimento de busca local ou de vizinhança para mover iterativamente de uma solução potencial para uma solução melhorada na vizinhança de , até que algum critério de parada tenha sido satisfeito (geralmente, um limite de tentativa ou um limite de pontuação). Os procedimentos de busca local geralmente ficam presos em áreas de pontuação ruim ou áreas onde as pontuações se estabilizam. Para evitar essas armadilhas e explorar regiões do espaço de busca que seriam deixadas inexploradas por outros procedimentos de busca local, a busca tabu explora cuidadosamente a vizinhança de cada solução conforme a busca avança. As soluções admitidas na nova vizinhança,, são determinadas através do uso de estruturas de memória. Usando essas estruturas de memória, a pesquisa avança movendo-se iterativamente da solução atual para uma solução melhorada em .

A Busca Tabu tem várias semelhanças com o recozimento simulado , pois ambos envolvem possíveis movimentos de declive. Na verdade, o recozimento simulado pode ser visto como uma forma especial de TS, onde usamos "estabilidade graduada", ou seja, um movimento torna-se tabu com uma probabilidade especificada.

Essas estruturas de memória formam o que se conhece como lista tabu, um conjunto de regras e soluções proibidas que serve para filtrar quais soluções serão admitidas na vizinhança para serem exploradas pela busca. Em sua forma mais simples, uma lista tabu é um conjunto de curto prazo das soluções que foram visitadas no passado recente (menos de iterações atrás, onde está o número de soluções anteriores a serem armazenadas - também é chamado de posse tabu). Mais comumente, uma lista tabu consiste em soluções que mudaram pelo processo de mudança de uma solução para outra. É conveniente, para facilitar a descrição, entender uma “solução” a ser codificada e representada por tais atributos.

Tipos de memória

As estruturas de memória usadas na pesquisa tabu podem ser divididas em três categorias:

  • Curto prazo: A lista de soluções recentemente consideradas. Se uma solução potencial aparecer na lista tabu, ela não pode ser revisada até que atinja o ponto de expiração.
  • Termo intermediário: regras de intensificação destinadas a direcionar a busca para áreas promissoras do espaço de busca.
  • Longo prazo: regras de diversificação que conduzem a busca em novas regiões (isto é, em relação a reinicializações quando a busca fica presa em um platô ou um beco sem saída subótimo).

As memórias de curto, médio e longo prazo podem se sobrepor na prática. Dentro dessas categorias, a memória pode ainda ser diferenciada por medidas como frequência e impacto das mudanças feitas. Um exemplo de uma estrutura de memória de termo intermediário é aquela que proíbe ou encoraja soluções que contêm certos atributos (por exemplo, soluções que incluem valores indesejáveis ​​ou desejáveis ​​para certas variáveis) ou uma estrutura de memória que impede ou induz certos movimentos (por exemplo, com base na memória de frequência aplicado a soluções que compartilham recursos em comum com soluções não atraentes ou atraentes encontradas no passado). Na memória de curto prazo, os atributos selecionados em soluções visitadas recentemente são rotulados como "tabu-ativo". Soluções que contêm elementos tabu-ativos são banidas. Os critérios de aspiração são empregados que substituem o estado tabu de uma solução, incluindo assim a solução excluída de outra forma no conjunto permitido (desde que a solução seja “boa o suficiente” de acordo com uma medida de qualidade ou diversidade). Um critério de aspiração simples e comumente usado é permitir soluções que são melhores do que a melhor solução atualmente conhecida.


A memória de curto prazo por si só pode ser suficiente para alcançar soluções superiores às encontradas pelos métodos convencionais de busca local, mas as estruturas de médio e longo prazo são freqüentemente necessárias para resolver problemas mais difíceis. A pesquisa tabu é frequentemente comparada com outros métodos metaheurísticos - como recozimento simulado , algoritmos genéticos , algoritmos de otimização de colônia de formigas , otimização de pesquisa reativa, pesquisa local guiada ou pesquisa adaptativa aleatória gananciosa . Além disso, a pesquisa tabu às vezes é combinada com outras metaheurísticas para criar métodos híbridos. O híbrido de busca tabu mais comum surge juntando-se TS com Busca Scatter, uma classe de procedimentos baseados em população que tem raízes em comum com busca tabu, e é freqüentemente empregado na solução de grandes problemas de otimização não linear.

Pseudo-código

O pseudocódigo a seguir apresenta uma versão simplificada do algoritmo de pesquisa tabu conforme descrito acima. Essa implementação tem uma memória de curto prazo rudimentar, mas não contém estruturas de memória de longo ou intermediário. O termo "aptidão" refere-se a uma avaliação da solução candidata, incorporada em uma função objetivo para otimização matemática.

sBest  s0
bestCandidate  s0
tabuList  []
tabuList.push(s0)
while (not stoppingCondition())
    sNeighborhood  getNeighbors(bestCandidate)
    bestCandidate  sNeighborhood[0]
    for (sCandidate in sNeighborhood)
        if ( (not tabuList.contains(sCandidate)) and (fitness(sCandidate) > fitness(bestCandidate)) )
            bestCandidate  sCandidate
        end
    end
    if (fitness(bestCandidate) > fitness(sBest))
        sBest  bestCandidate
    end
    tabuList.push(bestCandidate)
    if (tabuList.size > maxTabuSize)
        tabuList.removeFirst()
    end
end
return sBest

As linhas 1-4 representam alguma configuração inicial, respectivamente criando uma solução inicial (possivelmente escolhida ao acaso), definindo essa solução inicial como a melhor vista até agora e inicializando uma lista tabu com esta solução inicial. Neste exemplo, a lista tabu é simplesmente uma estrutura de memória de curto prazo que conterá um registro dos elementos dos estados visitados.

O loop algorítmico central começa na linha 5. Este loop continuará procurando por uma solução ideal até que uma condição de parada especificada pelo usuário seja atendida (dois exemplos de tais condições são um limite de tempo simples ou um limite na pontuação de aptidão). As soluções vizinhas são verificadas quanto a elementos tabu na linha 9. Além disso, o algoritmo rastreia a melhor solução na vizinhança, que não é tabu.

A função de aptidão é geralmente uma função matemática, que retorna uma pontuação ou os critérios de aspiração são satisfeitos - por exemplo, um critério de aspiração pode ser considerado quando um novo espaço de busca é encontrado). Se o melhor candidato local tiver um valor de aptidão superior ao melhor atual (linha 13), ele será definido como o novo melhor (linha 14). O melhor candidato local é sempre adicionado à lista tabu (linha 16) e se a lista tabu estiver cheia (linha 17), alguns elementos poderão expirar (linha 18). Geralmente, os elementos expiram da lista na mesma ordem em que são adicionados. O procedimento selecionará o melhor candidato local (embora tenha pior aptidão do que o sBest) para escapar do ótimo local.

Este processo continua até que o critério de parada especificado pelo usuário seja atendido, momento em que a melhor solução vista durante o processo de busca é retornada (linha 21).

Exemplo: o problema do caixeiro viajante

O problema do caixeiro viajante (TSP) às vezes é usado para mostrar a funcionalidade da pesquisa tabu. Esse problema levanta uma questão direta - dada uma lista de cidades, qual é o caminho mais curto que visita todas as cidades? Por exemplo, se a cidade A e a cidade B estão próximas uma da outra, enquanto a cidade C está mais longe, a distância total percorrida será menor se as cidades A e B forem visitadas uma após a outra antes de visitar a cidade C. Como encontrar uma solução ideal é NP-hard , métodos de aproximação baseados em heurística (como pesquisas locais) são úteis para conceber soluções quase ótimas. Para obter boas soluções de TSP, é essencial explorar a estrutura do gráfico. O valor de explorar a estrutura do problema é um tema recorrente em métodos metaheurísticos, e a pesquisa tabu é bem adequada para isso. Uma classe de estratégias associadas à pesquisa tabu chamada métodos de cadeia de ejeção tornou possível obter soluções de TSP de alta qualidade de forma eficiente

Por outro lado, uma simples busca tabu pode ser usada para encontrar uma solução satisfatória para o problema do caixeiro viajante (ou seja, uma solução que satisfaça um critério de adequação, embora não com a alta qualidade obtida pela exploração da estrutura do grafo). A busca começa com uma solução inicial, que pode ser gerada aleatoriamente ou de acordo com algum tipo de algoritmo de vizinho mais próximo . Para criar novas soluções, a ordem em que duas cidades são visitadas em uma solução potencial é trocada. A distância total de viagem entre todas as cidades é usada para julgar o quão ideal uma solução é comparada a outra. Para evitar ciclos - isto é, visitar repetidamente um determinado conjunto de soluções - e para evitar ficar preso em ótimos locais , uma solução é adicionada à lista de tabu se for aceita na vizinhança da solução ,.

Novas soluções são criadas até que algum critério de parada, como um número arbitrário de iterações, seja atendido. Uma vez que a busca tabu simples para, ela retorna a melhor solução encontrada durante sua execução.

Referências

links externos