Resumo Técnico: Busca Heurística Latente (LHS)

Declaração do Problema

O projeto de algoritmos heurísticos de alta qualidade para problemas de otimização combinatória (por exemplo, Problema do Caixeiro Viajante, Roteamento de Veículos, Mochila) é tradicionalmente um processo orientado por especialistas, exigindo refinamento iterativo e profundo conhecimento de domínio. Avanços recentes integraram Modelos de Linguagem de Grande Escala (LLMs) em frameworks evolutivos (por exemplo, FunSearch, EoH, ReEvo) para automatizar essa descoberta. No entanto, esses métodos existentes operam principalmente no espaço discreto da sintaxe de programas. Eles dependem de amostragem estocástica, mutações em nível de token e recombinação para navegar em uma paisagem de otimização altamente não convexa. Essa abordagem frequentemente exige um grande número de avaliações baseadas em execução, que são custosas, para descobrir melhorias consistentes e luta contra a fragilidade dos espaços de busca discretos.

Metodologia

O artigo propõe a Busca Heurística Latente (LHS), um framework que desloca o processo de otimização do espaço de tokens discretos para uma variedade latente contínua aprendida. A metodologia consiste em quatro componentes interconectados:

1. Codificação Latente: Um codificador de código pré-treinado ($E$) mapeia programas heurísticos discretos em embeddings vetoriais contínuos ($z \in \mathbb{R}^d$).
2. Modelagem de Surrogato: Um modelo de surrogato diferenciável ($f_\theta$) é treinado para prever a pontuação de desempenho de uma heurística com base em seu embedding latente. Para garantir robustez contra avaliações ruidosas e variações de escala, o modelo é treinado usando uma função de perda de classificação por pares (RankNet) em vez de regressão pontual, focando na ordenação relativa dos candidatos.
3. Otimização Regularizada via Fluxos Normalizadores: Para abordar a anisotropia e as regiões de baixa densidade frequentemente encontradas nos embeddings de programas brutos, o framework emprega um fluxo normalizador invertível ($F_\phi$). Esse fluxo mapeia o espaço complexo de embeddings de programas para um espaço de prior Gaussiana estruturado e convexo ($u \in \mathbb{R}^d$). A otimização é realizada via ascensão de gradiente dentro desse espaço de prior, garantindo que a trajetória de busca permaneça próxima à variedade de heurísticas plausíveis e válidas.
4. Decodificação via Prompts Suaves: Os vetores latentes otimizados são projetados de volta no espaço de entrada de um LLM congelado apenas de decodificador, usando um mapeador latente-para-prompt aprendido ($\phi_\omega$). Esse mapeador gera "prompts suaves" contínuos (embeddings de condicionamento) que orientam o LLM a sintetizar novo código heurístico executável. O código gerado é validado quanto à sintaxe e avaliado em instâncias de referência para atualizar o conjunto de dados.

O processo geral é iterativo: programas semente são codificados, otimizados no espaço de prior latente, decodificados em novo código, avaliados e adicionados ao pool de treinamento para refinar os modelos de surrogato e fluxo.

Contribuições Principais

• Descoberta Heurística Contínua: O artigo introduz uma mudança de paradigma da busca evolutiva discreta em nível de token para otimização contínua sobre representações de programas aprendidas, permitindo o uso de métodos baseados em gradiente para o projeto de heurísticas.
• Busca Regularizada por Fluxo: Demonstra a necessidade de usar fluxos normalizadores para mapear embeddings de programas para um prior estruturado. Essa regularização impede que a busca se desvie para regiões inválidas do espaço latente, melhorando significativamente a taxa de sucesso do código gerado em comparação com a otimização direta no espaço de embeddings bruto.
• Surrogato Baseado em Classificação: O uso de um modelo de surrogato de classificação por pares fornece um sinal de aprendizado estável para a ascensão de gradiente, evitando a fragilidade associada à regressão de pontuação absoluta em ambientes de avaliação ruidosos.
• Condicionamento por Prompt Suave: O framework utiliza um mapeador aprendível para traduzir vetores latentes em prompts suaves, permitindo o direcionamento de um LLM congelado sem modificar seus parâmetros internos.

Resultados Experimentais

O framework LHS foi avaliado em quatro tarefas de otimização combinatória: TSP, Problema de Roteamento de Veículos com Capacidade (CVRP), Problema da Mochila (KSP) e Empacotamento de Binários Online (OBP).

• Desempenho: Em tarefas de roteamento (TSP e CVRP), o LHS alcançou desempenho de última geração, superando consistentemente as bases evolutivas discretas (FunSearch, EoH, ReEvo) e abordagens baseadas em MCTS. Por exemplo, no TSP-200, o LHS alcançou um objetivo de 12,49, superando o ReEvo (12,58) e o EoH (13,15).
• Eficiência: O LHS demonstrou eficiência de tempo de execução competitiva ou superior. Nos experimentos de TSP, o LHS exigiu significativamente menos tempo (por exemplo, 4,86s para TSP-200) em comparação com o ReEvo (29,61s) enquanto alcançava melhores resultados.
• Estudos de Ablação:
  • Sem-Fluxo: Remover o fluxo normalizador e otimizar diretamente no espaço de embeddings bruto resultou em uma queda significativa na taxa de sucesso do código gerado (61% vs. 74%), confirmando o papel do fluxo na estabilização da busca.
  • Sem-Grad: Substituir a ascensão de gradiente por interpolação simples resultou em alta validade (86%), mas em capacidade de otimização pobre (piores pontuações de objetivo), destacando a necessidade do sinal de gradiente para descobrir heurísticas de alta qualidade.
• Generalização: O método mostrou forte generalização cruzada de tamanho, performando bem em tamanhos de instância (por exemplo, TSP-100, TSP-200) que eram maiores do que aqueles usados durante a fase de busca.

Significado e Alegações

Os autores afirmam que o LHS oferece uma alternativa metodológica complementar às abordagens evolutivas discretas existentes. Ao tratar programas como vetores latentes contínuos, o framework permite a navegação sistemática do espaço de projeto de heurísticas via informação de gradiente, mantendo o rigor da avaliação baseada em execução.

O artigo enfatiza que a otimização contínua é um complemento poderoso à busca discreta, capaz de alcançar objetivos superiores dentro de orçamentos de avaliação fixos. No entanto, os autores permanecem modestos quanto às limitações, observando que a eficácia do LHS está fundamentalmente ligada à qualidade do modelo de surrogato e ao corpus de treinamento inicial. Eles reconhecem que etapas de otimização excessivamente agressivas podem empurrar candidatos para fora da variedade de código executável, sugerindo que trabalhos futuros devem explorar a hibridização do LHS com operadores evolutivos discretos para equilibrar a exploração global com o refinamento local. O framework é apresentado como um passo em direção a um pipeline mais diferenciável para o projeto automatizado de algoritmos, particularmente eficaz em cenários envolvendo buscas repetidas em tarefas relacionadas, onde o custo da geração de dados inicial pode ser amortizado.