Skip to content
Voltar aos resultados

Multi-objective Tabu Search (MOTS) — Metaheurística para soluções de Pareto-ótimo

Proposto por
Hansen, M. P.; building on Glover (1989) Tabu Search
Ano
1997
Tipo
Metaheuristic multi-objective optimization
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?

A Multi-objective Tabu Search (MOTS) é um algoritmo meta-heurístico que estende o framework clássico de Tabu Search para otimizar simultaneamente duas ou mais funções objetivo conflitantes.

Em vez de um único ótimo, busca aproximar a fronteira de Pareto — o conjunto de soluções onde nenhum objetivo pode ser melhorado sem piorar outro — tornando-a adequada para problemas complexos de otimização combinatória e contínua em engenharia, logística e pesquisa operacional.

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

Imagine explorar uma paisagem acidentada com muitas colinas e vales, mas você tem vários mapas mostrando diferentes terrenos (um por objetivo) que se contradizem. O MOTS navega neste espaço movendo-se para soluções vizinhas, mantendo uma lista de memória de curto prazo (a lista tabu) de locais recentemente visitados para evitar ciclos, e mantendo um arquivo de soluções não dominadas encontradas até agora. Periodicamente, a diversificação estratégica empurra a busca para regiões inexploradas da fronteira de Pareto, equilibrando a exploração de áreas promissoras com a exploração global.

História

A Multi-objective Tabu Search estende a Tabu Search de objetivo único introduzida por Fred Glover em 1989. A primeira formulação sistemática de MOTS — incluindo arquivamento de Pareto e critérios de aspiração multiobjetivo — foi apresentada por M. P. Hansen na conferência MCDM de 1997. Trabalhos subsequentes de Gandibleux, Teghem e outros formalizaram variantes para problemas combinatórios, e MOTS tem sido desde então aplicada a problemas de escalonamento, logística e projeto de engenharia como uma alternativa competitiva aos algoritmos evolutivos multiobjetivo.

Quando usar

Use MOTS quando você enfrenta um problema de otimização combinatória ou mista inteira com dois ou mais objetivos conflitantes (por exemplo, custo vs. qualidade, tempo vs. risco) e métodos exatos são computacionalmente intratáveis. Ele se destaca em problemas de escalonamento, roteamento de veículos, projeto de redes e seleção de portfólio onde o espaço de busca é muito grande para enumeração exaustiva. Prefira MOTS em vez de busca puramente aleatória quando a estrutura da vizinhança é significativa e os operadores de movimento podem ser definidos claramente. NÃO use MOTS quando: o problema tem um único objetivo (Tabu Search simples é suficiente); quando a fronteira de Pareto pode ser enumerada exatamente; quando a informação de gradiente está disponível e a paisagem é convexa (use programação matemática em vez disso); ou quando decisões em tempo real exigem saídas determinísticas e reproduzíveis sem variação estocástica.

Limitações e considerações

  • O desempenho é altamente sensível ao comprimento da lista tabu, definição da vizinhança e estratégia de diversificação — exigindo ajuste cuidadoso de parâmetros.
  • Nenhuma garantia de convergência para a verdadeira fronteira de Pareto; a qualidade da solução depende do comprimento da execução e da estrutura do problema.
  • Computacionalmente caro por iteração quando as vizinhanças são grandes ou as avaliações de objetivos são custosas.
  • Manter e atualizar o arquivo de Pareto pode se tornar caro à medida que o número de objetivos e o tamanho do arquivo crescem.
  • A implementação paralela não é trivial devido à natureza sequencial baseada em memória do mecanismo tabu.

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

  • Evita revisitar soluções recentes através da lista tabu, reduzindo o risco de ciclos em paisagens complexas.
  • Critérios de aspiração permitem a anulação de restrições tabu quando um movimento leva a uma melhoria excepcional, equilibrando memória com flexibilidade.
  • Não requer informação de gradiente, tornando-o aplicável a funções objetivo não diferenciáveis, discretas ou de caixa preta.
  • Produz uma aproximação de toda a fronteira de Pareto em uma única execução, apoiando a tomada de decisão multicritério.
  • O design flexível de vizinhança e operadores de movimento permite personalização específica do problema.
  • Mecanismos de diversificação permitem escapar de ótimos locais e melhor cobertura da fronteira de Pareto.

Aplicações

  • Roteamento de veículos e escalonamento logístico multiobjetivo (minimizar custo e tempo de entrega simultaneamente)
  • Escalonamento de projetos bi-objetivo: minimizar makespan e custo de recursos sob restrições de precedência
  • Otimização de portfólio: equilibrar retorno esperado contra risco em múltiplas classes de ativos
  • Projeto de rede: minimizar custo de instalação enquanto maximiza confiabilidade ou throughput
  • Planejamento de processo de fabricação: otimizar tempo de ciclo, uso de energia e métricas de qualidade conjuntamente
  • Gestão ambiental: equilibrar produção econômica contra poluição ou impacto ecológico

Como funciona

Como funciona

1

Inicializar a busca com uma ou mais soluções iniciais (geradas aleatoriamente ou construídas heuristicamente). Definir uma lista tabu vazia de comprimento fixo L e inicializar o arquivo de Pareto com soluções não dominadas da população inicial.

2

Gerar a vizinhança N(s) da solução atual s aplicando operadores de movimento (trocas, inserções, perturbações). Avaliar todas as soluções vizinhas em cada função objetivo para identificar candidatos à progressão.

3

Aplicar o filtro tabu: excluir vizinhos cujos movimentos definidores aparecem na lista tabu, a menos que satisfaçam um critério de aspiração — tipicamente que o vizinho domine todos os membros atuais do arquivo ou melhore o melhor valor conhecido em pelo menos um objetivo. Isso evita ciclos e força a exploração.

4

Selecionar o melhor vizinho não tabu (ou vencedor do critério de aspiração) como a próxima solução atual. Atualizar o arquivo de Pareto adicionando a nova solução se ela não for dominada; remover quaisquer membros do arquivo que sejam dominados pela nova entrada.

5

Aplicar estratégias de diversificação quando a busca estagnar: a memória de frequência de longo prazo identifica regiões raramente visitadas; reiniciar de soluções de elite do arquivo ou de soluções perturbadas aleatoriamente para estender a cobertura da fronteira de Pareto.

6

Repetir os passos de vizinhança, filtro e arquivo até que um critério de parada seja atendido — tipicamente um número máximo de iterações, avaliações de função ou tempo de CPU decorrido. Retornar o arquivo de Pareto como a fronteira de Pareto-ótimo aproximada.

Erros comuns

  • Definir a lista tabu muito curta causa ciclos; defini-la muito longa restringe excessivamente a busca e perde boas soluções — a calibração empírica é essencial.
  • Negligenciar a diversificação leva à convergência prematura em uma região da fronteira de Pareto, produzindo uma aproximação pobre.
  • Aplicar MOTS com mais de três objetivos degrada o desempenho porque o gerenciamento do arquivo e a manutenção da diversidade se tornam computacionalmente onerosos; considere métodos baseados em decomposição para problemas com muitos objetivos.
  • Usar operadores de movimento genéricos sem design específico do problema limita severamente a qualidade da solução em comparação com implementações personalizadas.
  • Relatar apenas o arquivo final sem examinar o histórico de convergência pode mascarar estagnação prematura.

Perguntas frequentes

Como o MOTS lida com a lista tabu quando há múltiplos objetivos?

A lista tabu armazena movimentos (não soluções), portanto, opera da mesma forma que na Tabu Search de objetivo único. A principal diferença é que a seleção entre vizinhos não tabu usa dominância multiobjetivo ou uma função de escalonamento, e o critério de aspiração é redefinido para permitir um movimento tabu se a solução resultante não for dominada por todos os membros atuais do arquivo.

O que é o arquivo de Pareto e qual deve ser o seu tamanho?

O arquivo de Pareto armazena todas as soluções não dominadas encontradas durante a busca. Seu tamanho máximo é geralmente limitado (por exemplo, 100–500 soluções) para manter o custo de memória e atualização gerenciável. Quando o arquivo está cheio, a poda por distância de agrupamento ou baseada em grade remove soluções de regiões superlotadas para manter a diversidade.

Como o MOTS se compara ao NSGA-II para problemas multiobjetivo?

O NSGA-II usa uma abordagem evolutiva baseada em população com crossover e mutação, tornando-o melhor na exploração global no início da busca. O MOTS depende de movimentos de vizinhança e memória, o que muitas vezes resulta em melhor qualidade de busca local. Na prática, o MOTS tende a ter melhor desempenho em problemas combinatórios com forte estrutura de vizinhança, enquanto o NSGA-II é mais amplamente utilizado para problemas contínuos.

Quantas iterações são tipicamente necessárias?

Não há regra universal. A prática comum é orçar avaliações de função em vez de iterações — tipicamente 10.000 a 100.000 avaliações dependendo do tamanho do problema — e realizar múltiplas execuções independentes para avaliar a qualidade da solução e a estabilidade da fronteira de Pareto.

O MOTS pode lidar com mais de dois objetivos?

Sim, mas a eficácia degrada à medida que o número de objetivos cresce além de três (a 'maldição da dimensionalidade' no espaço de objetivos). Para quatro ou mais objetivos, o tamanho do arquivo explode e a manutenção da diversidade se torna difícil; abordagens baseadas em decomposição ou baseadas em indicadores são frequentemente preferidas.

Métodos relacionados

Fontes

  1. Hansen, M. P. (1997). Tabu search for multiobjective optimization: MOTS. Presented at the 13th International Conference on Multiple Criteria Decision Making (MCDM), Cape Town, South Africa.

    Abrir referência da publicação
    Copiado.
  2. Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206.

    Abrir referência DOI
    Copiado.