Resumo Técnico: PathWise

Declaração do Problema

O Design Heurístico Automatizado (AHD) visa gerar automaticamente algoritmos heurísticos para Problemas de Otimização Combinatória (COPs), reduzindo a dependência de designs manuais elaborados por especialistas. Embora os Modelos de Linguagem de Grande Escala (LLMs) tenham recentemente viabilizado o AHD ao se integrarem a processos de busca evolutiva, os frameworks existentes sofrem com limitações significativas. Métodos baseados em população frequentemente dependem de regras evolutivas fixas e modelos de prompt estáticos, levando a uma geração heurística míope, avaliações redundantes e convergência prematura. Métodos baseados em árvores, como os que utilizam Busca em Árvore Monte Carlo (MCTS), impõem estruturas hierárquicas impulsionadas por estatísticas de desempenho, em vez de uma compreensão semântica da paisagem de busca. Crucialmente, as abordagens atuais carecem de uma representação semântica e com estado de como as heurísticas são derivadas, como as edições se propagam entre gerações ou por que modificações têm sucesso ou falham. Isso resulta em uso ineficiente de chamadas de LLM e na incapacidade de levar adiante decisões passadas de forma eficaz.

Metodologia

Os autores propõem o PathWise (Planejamento através de Modelo de Mundo para Design Heurístico Automatizado via LLMs Autoevolutivos), um novo framework de raciocínio multiagente que formula a geração heurística como um processo de decisão sequencial sobre um grafo de implicação. Este grafo serve como uma memória compacta e com estado da trajetória de busca.

Componentes Principais

1. Grafo de Implicação ($G = (V, E)$):

   • Diferentemente de árvores evolutivas ou populações padrão, o grafo de implicação codifica o histórico de derivação.
   • Nós ($v$): Representam tuplas contendo código heurístico ($h$), uma justificativa de derivação em linguagem natural ($\kappa$), uma descrição algorítmica ($d$), métricas de desempenho ($P(h; D)$) e metadados dos pais ($PM$).
   • Arestas ($E$): Conectam conjuntos de pais a nós filhos, codificando a justificativa específica usada para derivar o filho a partir de seus pais.
   • Esta estrutura permite que o sistema condicione decisões futuras ao histórico de derivação, em vez de tratar etapas como eventos de amostragem isolados.

2. Sistema Multiagente:
   O framework opera por meio de um ciclo coordenado de planejamento, execução e reflexão em duas escalas de tempo (atualizações de população externa e etapas de implicação internas):

   • Agente de Política ($\pi_p$): Atua como um planejador de alto nível. Ele observa o estado atual (a fronteira do grafo de implicação) e propõe ações definidas por uma tupla de nós pais selecionados ($S$) e uma justificativa de derivação em linguagem natural ($\kappa$). Isso permite que a política invente dinamicamente novos tipos de operadores, em vez de depender de modelos fixos.
   • Agente de Modelo de Mundo ($\pi_{wm}$): Atua como um executor de baixo nível. Ele traduz as ações de alto nível da política em código heurístico executável (execuções) condicionado aos pais selecionados e à diretiva.
   • Agentes Críticos:
     • Crítico de Política ($\pi_{p\_critic}$): Analisa os resultados das ações da política (seleções de pais e diretivas) para fornecer reflexões roteadas que orientam estratégias evolutivas futuras.
     • Crítico de Modelo de Mundo ($\pi_{wm\_critic}$): Compara as execuções heurísticas com melhor e pior desempenho para fornecer feedback sobre a qualidade da síntese de código, orientando o modelo de mundo a refinar a estrutura e a eficiência algorítmica.

3. Processo de Busca:

   • Laço Externo: Mantém uma população de nós raiz.
   • Laço Interno: Constrói incrementalmente um grafo de implicação enraizado na população atual. Em cada etapa, o sistema amostra múltiplas ações e execuções, seleciona o nó resultante mais adequado e atualiza o grafo.
   • Mecanismos de Diversidade: Para prevenir saídas de baixa diversidade, o PathWise emprega Diversidade em Nível de Prompt (perturbando prompts com frases exploratórias) e Embaralhamento de Estado (randomizando a ordem dos nós para mitigar viés posicional).

Contribuições Principais

1. Formulação Híbrida Grafo-População: Os autores introduzem uma formulação onde um grafo de implicação codifica a justificativa de derivação e o histórico de desempenho, servindo como um estado compartilhado para a interação entre política e modelo de mundo.
2. Framework Multiagente Coordenado: Um sistema onde um agente de política controla a estratégia evolutiva, um modelo de mundo executa a geração de código e agentes críticos fornecem reflexões roteadas, permitindo a geração heurística autoevolutiva e consciente do estado sem atualizar parâmetros de LLM.
3. Diversidade em Nível de Prompt: Mecanismos para garantir variedade na seleção de pais e em execuções heurísticas, permitindo uma exploração mais ampla sobre o grafo de implicação.
4. Validação Empírica: Experimentos extensivos demonstrando que o PathWise descobre heurísticas mais fortes com menos avaliações, alcança convergência mais rápida e escala efetivamente para tamanhos de problema maiores em diversos COPs.

Resultados Experimentais

O PathWise foi avaliado em múltiplos COPs NP-difíceis, incluindo o Problema do Caixeiro Viajante (TSP), Problema da Mochila (KP), Problema de Roteamento de Veículos com Capacidade (CVRP), Problema da Mochila Múltipla (MKP), Problema de Orientação (OP) e Problema de Empacotamento em Binários (BPP). O framework foi testado em três paradigmas de busca: Construção Passo a Passo, Otimização por Colônia de Formigas (ACO) e Busca Local Guiada (GLS).

• Desempenho: O PathWise superou consistentemente as bases de referência AHD baseadas em LLMs mais avançadas (FunSearch, EoH, ReEvo, HSEvo, MCTS-AHD) e heurísticas projetadas manualmente. Ele alcançou lacunas de otimalidade menores em conjuntos de teste tanto dentro do domínio quanto fora do domínio.
• Eficiência: O PathWise convergiu mais rápido para heurísticas melhores. Em vários experimentos, o PathWise alcançou desempenho superior com apenas 500 avaliações, enquanto as bases de referência tiveram permissão para 1000 avaliações.
• Escalabilidade: O método demonstrou forte generalização para tamanhos de problema maiores (por exemplo, TSP com $N=200$, KP com $N=500$) e diferentes backbones de LLM (GPT-4o-mini, GPT-5-nano com níveis de raciocínio variados).
• Estudos de Ablação: A remoção de agentes críticos ou mecanismos de diversidade degradou significativamente o desempenho, confirmando a necessidade de feedback consciente do estado e exploração.

Significado e Alegações

O artigo alega que o PathWise representa uma mudança da "evolução por tentativa e erro" para o "planejamento consciente do estado através do raciocínio". Ao tratar a descoberta heurística como um processo de decisão sequencial sobre um grafo de implicação, o sistema pode levar adiante decisões passadas e reutilizar ou evitar informações de derivação entre gerações.

Os autores enfatizam que o PathWise é livre de treinamento no sentido de que não atualiza parâmetros de LLM; em vez disso, ele aproveita o conhecimento pré-treinado dos LLMs reforçado por meio de reflexões em linguagem natural. O significado reside em sua capacidade de superar a miopia dos métodos AHD existentes ao fornecer uma memória estruturada do processo de busca, reduzindo assim avaliações redundantes e permitindo uma descoberta mais eficaz de heurísticas de alta qualidade para problemas combinatórios complexos. O trabalho sugere que o raciocínio estruturado sobre o histórico de derivação é um componente crítico para escalar o design automatizado de algoritmos baseado em LLM.