Skip to content
Voltar aos resultados

Agent-Based Tabu Search — Otimização Meta-heurística Distribuída Multiagente

Proposto por
Glover, F. (tabu search); multi-agent extension by various researchers in the 1990s–2000s
Ano
1989–1995
Tipo
Hybrid metaheuristic — agent-based distributed tabu search
Família
Simulation / optimization

Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês

Tamanho da fonte

O que ele faz?

Agent-Based Tabu Search (ABTS) incorpora a meta-heurística tabu search em uma estrutura multiagente, onde agentes autônomos executam threads tabu search independentes ou cooperativas, compartilhando soluções promissoras para escapar de ótimos locais e explorar coletivamente espaços de busca combinatórios ou contínuos de forma mais eficaz do que uma implementação de thread única.

A intuição por trás do método

A tabu search clássica pode ficar presa explorando uma região estreita, mesmo com seu mecanismo de memória de curto prazo. Ao implantar múltiplos agentes autônomos, cada um mantendo sua própria lista tabu e vizinhança, a busca se espalha por diversos pontos de partida. Os agentes periodicamente compartilham soluções de elite (intensificação) e se dispersam deliberadamente para regiões inexploradas (diversificação). Essa estrutura cooperativa, porém independente, espelha o comportamento de enxame biológico — nenhum agente individual tem a visão completa, mas o coletivo encontra soluções de alta qualidade muito mais rapidamente do que qualquer buscador individual.

História

A tabu search foi formalizada por Fred Glover em 1986–1989. Variantes distribuídas e paralelas surgiram no início dos anos 1990, à medida que pesquisadores buscavam explorar arquiteturas multiprocessador. Verhoeven e Aarts (1995) forneceram um estudo sistemático de busca local paralela, incluindo estratégias cooperativas tabu. O enquadramento baseado em agentes tornou-se proeminente nos anos 2000, à medida que o vocabulário de modelagem baseada em agentes entrou na pesquisa operacional.

Quando usar

Use Agent-Based Tabu Search ao resolver problemas difíceis de otimização combinatória ou mista-inteira (agendamento, roteamento, projeto de rede, alocação de recursos) onde a tabu search de thread única estagna e recursos de computação paralela estão disponíveis. É particularmente eficaz quando o cenário de busca tem muitos ótimos locais de qualidade semelhante. Evite-a quando o problema for pequeno o suficiente para resolvedores exatos (MILP, branch-and-bound), quando uma única avaliação for computacionalmente proibitiva (tornando muitas avaliações paralelas inviáveis), ou quando requisitos de reprodutibilidade conflitam com a dinâmica não determinística e de interação entre agentes.

Limitações e considerações

  • O overhead de sincronização e o custo de comunicação entre agentes podem anular os ganhos de paralelismo em sistemas rigidamente acoplados ou redes lentas.
  • Mais hiperparâmetros do que a tabu search de thread única: número de agentes, topologia de comunicação, frequência de sincronização e gatilhos de diversificação exigem ajuste.
  • Garantias teóricas de convergência são mais fracas do que métodos exatos; a qualidade da solução depende fortemente do ajuste e da estrutura do problema.
  • A reprodutibilidade é difícil de alcançar porque as interações dos agentes introduzem estocasticidade adicional além da inicialização aleatória.

As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.

Pontos fortes

  • A exploração paralela reduz significativamente o tempo para solução em grandes problemas combinatórios em comparação com a tabu search de thread única.
  • A estrutura multiagente suporta naturalmente a diversificação, reduzindo o risco de convergência prematura para ótimos locais ruins.
  • A arquitetura flexível permite agentes heterogêneos com diferentes estruturas de vizinhança, estratégias de permanência tabu, ou até mesmo meta-heurísticas mistas.
  • O compartilhamento cooperativo de soluções transfere descobertas entre agentes, acelerando a intensificação em torno de regiões de alta qualidade.
  • Escala bem com os núcleos computacionais disponíveis, tornando-a adequada para ambientes de computação modernos multi-core e distribuídos.

Aplicações

  • Roteamento de veículos e logística: coordenação de múltiplos agentes, cada um otimizando subproblemas de rota.
  • Agendamento de job-shop e fabricação flexível: agentes lidam cooperativamente com subconjuntos de máquinas.
  • Projeto de rede de telecomunicações: atribuição distribuída de canais e otimização de topologia.
  • Planejamento da cadeia de suprimentos: otimização de inventário e distribuição multi-echelon.
  • Previsão de estrutura de proteínas: busca paralela de vizinhança em espaços conformacionais.
  • Agendamento acadêmico e de cursos com agentes distribuídos em nível departamental.

Como funciona

Como funciona

1

Defina uma população de agentes autônomos. Cada agente recebe uma função: alguns focam na intensificação (busca local profunda em torno de regiões promissoras), outros na diversificação (escapando para áreas inexploradas). Cada agente mantém sua própria lista tabu de movimentos proibidos, uma solução atual e uma estrutura de vizinhança adaptada ao tipo de problema (por exemplo, movimentos de troca, inserção ou 2-opt para problemas combinatórios).

2

Inicialize os agentes com soluções de partida distintas, geradas aleatoriamente ou semeadas por uma heurística construtiva (por exemplo, vizinho mais próximo para roteamento). A diversidade entre as soluções de partida é crucial — inícios idênticos levam a buscas paralelas redundantes. Avalie a função objetivo para cada solução inicial e registre a melhor solução global entre todos os agentes.

3

Cada agente executa seu próprio loop tabu search: gera a vizinhança da solução atual, avalia todas (ou um subconjunto de) soluções vizinhas, seleciona o melhor vizinho não-tabu como próximo movimento (o critério de aspiração permite sobrepor a lista tabu se o candidato superar o melhor global) e atualiza a lista tabu adicionando o movimento reverso com uma permanência extraída de um intervalo fixo ou adaptativo.

4

Os agentes se comunicam em intervalos de sincronização definidos ou gatilhos de eventos. Estratégias comuns incluem transmitir o melhor global atual para todos os agentes (que podem reiniciar a partir dele), injetar a solução de elite em um pool compartilhado que os agentes consultam periodicamente, ou troca ponto a ponto de soluções entre agentes vizinhos em uma topologia (anel, totalmente conectado ou aleatório). Controles de diversidade evitam convergência prematura penalizando agentes com soluções idênticas.

5

Termine quando um orçamento máximo de iterações, limite de tempo de relógio ou critério de estagnação for atingido (por exemplo, nenhuma melhoria no melhor global por um número determinado de iterações). Selecione a melhor solução global encontrada entre todos os agentes em todas as iterações como saída final. Opcionalmente, relate uma frente de Pareto se múltiplos objetivos forem rastreados.

Erros comuns

  • Definir todos os agentes com soluções de partida idênticas desperdiça capacidade paralela — garanta inicialização diversificada.
  • Comunicação excessivamente frequente força os agentes para a mesma bacia de solução, eliminando os benefícios da diversificação e reduzindo efetivamente a busca a um único thread.
  • Ignorar o critério de aspiração no projeto da lista tabu pode fazer com que os agentes percam soluções obviamente melhores, particularmente na fase inicial da busca.
  • Aplicar ABTS a problemas onde a avaliação da vizinhança é extremamente custosa sem um modelo substituto resultará em tempos de execução proibitivos.

Perguntas frequentes

Como o Agent-Based Tabu Search difere de simplesmente executar múltiplas threads tabu search?

A principal diferença é a cooperação. Em execuções paralelas independentes, as threads nunca compartilham informações. Em ABTS, os agentes trocam ativamente soluções, atualizam um pool de elite compartilhado ou adotam gatilhos de diversificação com base no estado coletivo — produzindo um comportamento de busca emergente ausente em execuções independentes.

Quantos agentes devo usar?

Um ponto de partida comum é um agente por núcleo de CPU disponível. Pesquisas sugerem retornos decrescentes além de 8–16 agentes para a maioria dos problemas combinatórios, à medida que o overhead de comunicação aumenta. Experimentos piloto com 4, 8 e 16 agentes ajudam a identificar o ponto ideal para um determinado problema.

O ABTS pode lidar com problemas multi-objetivo?

Sim. Os agentes podem manter aproximações locais de uma frente de Pareto e compartilhar soluções não dominadas através de um arquivo compartilhado. Isso é às vezes chamado de Multi-Objective Agent-Based Tabu Search e é distinto do ABTS padrão de objetivo único.

Qual topologia de comunicação é melhor?

Topologias totalmente conectadas espalham as boas soluções mais rapidamente, mas criam alto custo de comunicação. Topologias de anel ou de mundo pequeno equilibram a difusão de informações com a autonomia. Para a maioria dos problemas práticos, um anel ou uma topologia esparsa aleatória funcionam bem como padrão.

Quando devo preferir um algoritmo genético ou particle swarm em vez de ABTS?

Prefira métodos baseados em população (GA, PSO) quando o problema tem um cenário contínuo e suave ou quando operadores de cruzamento/recombinação são bem definidos. ABTS se destaca em problemas discretos e combinatórios com operadores de vizinhança bem definidos, onde a memória tabu fornece uma forte vantagem de busca.

Métodos relacionados

Fontes

  1. Glover, F. (1989). Tabu search — Part I. ORSA Journal on Computing, 1(3), 190–206.

    Abrir referência DOI
    Copiado.
  2. Verhoeven, M. G. A., Aarts, E. H. L. (1995). Parallel local search. Journal of Heuristics, 1(1), 43–65.

    Abrir referência DOI
    Copiado.