Resumo Técnico: HMACE – Evolução Colaborativa Multi-Agente Heterogênea para Otimização Combinatória

1. Declaração do Problema

Problemas de Otimização Combinatória (POCs), como o Problema do Caixeiro Viajante (TSP), o Problema de Roteamento de Veículos (VRP) e o Problema de Empacotamento em Caixas (BPP), são fundamentais, porém NP-difíceis, tornando as soluções ótimas computacionalmente proibitivas em grande escala. Embora heurísticas tradicionais dependam de regras custosas e criadas manualmente, abordagens recentes baseadas em Modelos de Linguagem de Grande Escala (LLMs) tentaram automatizar o design de heurísticas. No entanto, os métodos existentes baseados em LLM enfrentam dois gargalos estruturais:

1. Convergência Prematura: Fluxos de trabalho monolíticos frequentemente carecem de mecanismos de exploração estruturada (por exemplo, retrocesso sistemático), levando ao aprisionamento em ótimos locais.
2. Interferência de Papéis: Forçar um único agente a realizar operações cognitivas heterogêneas (planejamento, geração, avaliação, refinamento) cria emaranhamento cognitivo e degrada o desempenho.

Tentativas atuais multi-agente frequentemente sofrem com sobrecarga de comunicação ou falta de foco cognitivo especializado, falhando em superar bases de referência de agentes únicos robustos. O desafio central é projetar uma arquitetura autônoma, especializada em papéis e consciente de memória, que coordene raciocínio e busca de forma eficaz.

2. Metodologia: Framework HMACE

Os autores propõem o HMACE (Evolução Colaborativa Multi-Agente Heterogênea), que reconceptualiza a busca heurística como um problema de design organizacional. Em vez de um processo de geração monolítico, o HMACE decompõe cada geração evolutiva em um loop colaborativo envolvendo quatro agentes especializados comunicando-se por meio de uma memória apoiada em um arquivo:

• Propositor: Rascunha candidatos de estratégia em linguagem natural. Ele condiciona-se à população atual e recupera exemplos diversos do arquivo para garantir que as propostas combinem ou contrastem padrões de busca distintos, em vez de refinar uma única família dominante.
• Gerador: Traduz as estratégias propostas em linguagem natural para código Python executável (heurísticas) que aderem estritamente ao contrato de E/S do problema.
• Avaliador: Executa heurísticas candidatas em instâncias de treinamento para calcular dois sinais:
  • Aptidão ($f_h$): Uma pontuação escalar que mede a qualidade da solução (por exemplo, lacuna de otimalidade).
  • Vetor de Comportamento ($\phi_h$): Um descritor de alta dimensão que caracteriza como a heurística se comporta durante a execução (por exemplo, estatísticas de tempo de execução, características estruturais).
• Refletor: Gerencia a memória compartilhada (arquivo) e guia a busca. Ele realiza:
  • Recuperação Consciente de Comportamento: Seleciona exemplos diversos de nichos comportamentais distintos para condicionar o Propositor.
  • Atualização do Arquivo: Utiliza uma estrutura CVT-MAP-Elites para armazenar o melhor incumbente para cada célula comportamental, garantindo a cobertura do espaço de busca.
  • Filtragem: Antes da avaliação dispendiosa, um filtro determinístico leve remove programas malformados ou quase duplicados para conservar o orçamento de LLM.

Fluxo de Trabalho: O sistema itera através de gerações. O Refletor recupera exemplos diversos; o Propositor rascunha estratégias; o Gerador as codifica; o Avaliador as pontua; e o Refletor atualiza a população e o arquivo. O processo termina quando o orçamento de gerações é esgotado ou nenhuma melhoria é observada por um número definido de gerações.

3. Contribuições Principais

1. Abordagem Organizacional para Design de Heurísticas: O HMACE introduz um framework evolutivo multi-agente heterogêneo que decompõe o processo de busca em papéis especializados (Propositor, Gerador, Avaliador, Refletor), indo além de fluxos de trabalho monolíticos orientados por LLM.
2. Mecanismo de Reflexão de Sinal Duplo: O framework integra um mecanismo de reflexão novel que aproveita trajetórias históricas por meio de recuperação consciente de comportamento e atualizações de arquivo fundamentadas em aptidão. Isso permite que os agentes escapem de ótimos locais explorando nichos comportamentais diversos, mantendo ao mesmo tempo incumbentes de alta qualidade.
3. Compromisso Qualidade-Eficiência: Experimentos extensivos demonstram que o HMACE alcança qualidade de solução superior com custos computacionais significativamente reduzidos (tokens e tempo) em comparação com bases de referência de agentes únicos e multi-agentes mais avançados.

4. Resultados Experimentais

O framework foi avaliado em quatro POCs representativos: TSP, Problema de Empacotamento em Caixas Online (Online BPP), Problema da Mochila Múltipla (MKP) e Programação de Fluxo de Trabalho Permutado (PFSP).

• Desempenho: O HMACE alcançou as menores lacunas de otimalidade médias entre os métodos avaliados pelo GPT-5.4.
  • TSP: Lacuna média de 0,387% (vs. 0,431% para CORAL e 0,467% para EoH).
  • Online BPP: Lacuna média de 0,441% (superando o MoH em 12/15 configurações).
  • PFSP e MKP: O HMACE mostrou compromissos favoráveis de qualidade-eficiência, frequentemente reduzindo o tempo de execução e o uso de tokens significativamente, mantendo valores objetivos competitivos.
• Eficiência: O HMACE demonstrou eficiência excepcional em tokens.
  • Para TSP, exigiu apenas 0,13M de tokens (vs. 0,94M para CORAL).
  • Para Online BPP, exigiu 0,42M de tokens (vs. 5,48M para CORAL).
• Estudos de Ablação: Remover a recuperação consciente de comportamento (substituindo-a por amostragem aleatória) degradou a qualidade da solução, confirmando o valor de priores comportamentais direcionados. Remover a etapa de triagem leve aumentou os custos de tokens sem ganhos proporcionais de qualidade.

5. Significado e Alegações

O artigo alega que o principal gargalo dos solucionadores baseados em LLM atuais não é meramente a capacidade do modelo, mas a falta de uma estrutura organizacional adequada para coordenar raciocínio e busca.

• Além de Agentes Monolíticos: O HMACE demonstra que desacoplar a resolução de problemas em papéis especializados e interativos elimina robustamente a interferência de papéis e permite uma exploração sistemática e diversificada.
• Memória como Mecanismo de Busca: Os autores argumentam que a reflexão no HMACE não é meramente crítica verbal, mas um mecanismo operacional de memória. Ao acoplar a exploração orientada por aptidão com a exploração do espaço comportamental, o framework mitiga a convergência prematura.
• Descoberta Custo-Efetiva: Os resultados sugerem que um fluxo de trabalho evolutivo colaborativo pode descobrir heurísticas reutilizáveis e de alta qualidade de forma mais eficiente do que abordagens de agente único, alcançando um equilíbrio favorável entre qualidade da solução e custos de tokens de API.

Os autores reconhecem limitações, observando que o framework depende de um pipeline pré-definido e em etapas, e que a escalabilidade da memória de longo prazo requer curadoria dinâmica para evitar sobrecarga de informações. Eles posicionam o HMACE como um passo para abordar desafios complexos do mundo real além dos POCs clássicos, como otimização contínua.