🤖 machine learning

Heuristic Search as Language-Guided Program Optimization

Este artigo propõe um framework estruturado para o Design Heurístico Automatizado (AHD) guiado por Grandes Modelos de Linguagem, que decompõe o processo de descoberta em etapas modulares de avaliação, feedback analítico e refinamento, demonstrando superioridade sobre métodos existentes em quatro domínios de otimização combinatória do mundo real.

Autores originais: Mingxin Yu, Ruixiao Yang, Chuchu Fan

Publicado 2026-02-19

📖 4 min de leitura☕ Leitura rápida

CC BY 4.0

Autores originais: Mingxin Yu, Ruixiao Yang, Chuchu Fan

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você precisa organizar uma viagem complexa para um grupo de amigos, mas as regras são complicadas: alguns só podem ir de manhã, outros têm orçamento limitado, e o carro tem um espaço máximo. Você precisa encontrar a melhor rota possível.

Antigamente, para resolver isso, os especialistas (humanos) tinham que criar "regras de ouro" (heurísticas) manualmente, testando e ajustando por anos. Depois, surgiram os Modelos de Linguagem (LLMs), como o ChatGPT, que podiam escrever código para tentar resolver esses problemas. Mas havia um problema: esses modelos funcionavam como um "palpite cego". Eles geravam uma solução, viam se era boa ou ruim (um número), e tentavam de novo, muitas vezes sem entender por que falharam. Era como tentar consertar um carro apenas apertando botões aleatórios e torcendo para o motor pegar.

Este artigo apresenta uma nova abordagem chamada LaGO (Otimização Guiada por Linguagem). Vamos usar uma analogia simples para entender como funciona:

A Metáfora da "Equipe de Engenharia de Software"

Em vez de deixar o LLM trabalhar sozinho e de forma bagunçada, os autores organizaram o processo como se fosse uma equipe de desenvolvimento de software estruturada, dividida em três etapas claras:

1. O Teste (A "Passagem à Frente")

Imagine que você tem um protótipo de um novo carro. Você o coloca na pista e o testa.

O que acontece: O sistema executa o código do "algoritmo" (a regra que o LLM criou) em vários problemas reais.
O resultado: Em vez de apenas dizer "o carro foi rápido ou lento", o sistema grava tudo: onde o carro derrapou, onde o motor superaqueceu, e em quais curvas ele foi eficiente. São os "rastros de execução".

2. O Analista (A "Passagem de Volta")

Aqui está a grande inovação. Em vez de apenas olhar para o número final da velocidade, você contrata um engenheiro especialista (um segundo LLM) para analisar os rastros da pista.

O que ele faz: Ele olha os dados e diz: "O carro derrapou na curva 3 porque a suspensão estava muito dura para o tipo de chão. Na reta 5, o motor foi ótimo, mas o freio falhou."
A mágica: Ele transforma o problema em instruções claras e estruturadas (como um relatório técnico), não apenas um número. Ele diz exatamente o que precisa ser consertado e por que. Isso é como dar um "gradiente semântico" (uma direção clara) para o próximo passo.

3. O Gerador (A "Atualização")

Agora, o engenheiro principal (o LLM criador) recebe o relatório do Analista.

O que ele faz: Em vez de tentar adivinhar, ele reescreve o código do carro com base nas dicas específicas. "Ok, vou suavizar a suspensão para curvas de terra e ajustar o freio para a reta."
O resultado: Ele cria uma nova versão do algoritmo que já nasce mais inteligente, aprendendo com os erros específicos do teste anterior.

Por que isso é tão importante?

O artigo mostra que, ao separar essas etapas (Testar -> Analisar -> Corrigir), o sistema aprende muito mais rápido e com mais qualidade do que os métodos antigos.

Não é mais "tentativa e erro" cega: É uma evolução dirigida. O sistema sabe exatamente onde está errando.
Trabalho em equipe: O sistema não cria apenas uma regra. Ele cria duas equipes que trabalham juntas: uma que faz o "trabalho pesado" inicial (criar uma solução básica) e outra que faz o "polimento" (melhorar essa solução). Elas evoluem juntas, como um time de futebol onde o atacante e o goleiro aprendem a jogar melhor um com o outro.
Diversidade: O sistema evita que todos os "alunos" pensem igual. Ele garante que existam diferentes estratégias sendo testadas, evitando que a equipe fique presa em uma solução ruim (o que chamam de "colapso de modo").

Os Resultados

Os autores testaram essa ideia em quatro problemas do mundo real, como:

Entregas com janelas de tempo: Caminhões que precisam pegar e entregar pacotes em horários específicos.
Escalonamento de tripulação de avião: Organizar os pilotos e comissários respeitando regras de segurança e descanso.
Design de chips: Organizar componentes eletrônicos para que o chip seja eficiente.
Processamento de dados: Dividir tarefas de inteligência artificial entre vários computadores.

Em todos esses casos, o método LaGO superou os melhores métodos existentes, encontrando soluções melhores e mais rápidas, especialmente em problemas onde as regras são muito complexas e difíceis de seguir.

Resumo Final

Pense no LaGO como transformar a criação de soluções de um "jogo de adivinhação" em um processo de engenharia de precisão. Ao dar ao computador a capacidade de "ler o relatório de erros" e "entender a lógica do problema" antes de tentar consertar, eles conseguem criar algoritmos muito mais inteligentes e adaptáveis para resolver os desafios mais difíceis do mundo real.

Resumo Técnico: Heuristic Search as Language-Guided Program Optimization (LaGO)

1. Problema e Motivação

O Design Automatizado de Heurísticas (AHD) visa reduzir o esforço manual e a dependência de especialistas de domínio na criação de estratégias para resolver problemas de Otimização Combinatória (CO). Embora os Modelos de Linguagem de Grande Escala (LLMs) tenham revolucionado a descoberta de heurísticas ao gerar código executável diretamente, os pipelines existentes apresentam limitações críticas:

Acoplamento Tightly Coupled: Os processos de avaliação, feedback e atualização estão entrelaçados em um único loop, dificultando a análise isolada de componentes e a melhoria sistemática.
Dependência de Tentativa e Erro: A adaptação a novos problemas complexos ainda depende fortemente de intuição humana e ajustes manuais de prompts.
Feedback Limitado: Métodos anteriores frequentemente utilizam apenas valores de aptidão (fitness) escalares ou reflexões textuais genéricas, perdendo informações estruturais cruciais sobre por que uma heurística falha ou tem sucesso.

O objetivo do trabalho é reformular o AHD como um problema de otimização explícito sobre um espaço de programas, permitindo um refinamento iterativo e modular.

2. Metodologia: Framework LaGO

Os autores propõem o LaGO (Language-Guided Optimization), um framework que decompõe o processo de descoberta de heurísticas em três estágios modulares distintos, análogos ao aprendizado baseado em gradiente:

A. Forward Pass (Passo Adiante - Avaliação)

Função: Avalia heurísticas candidatas injetando-as em um esqueleto de algoritmo pré-definido.
Saída: Gera "traces" de execução (rastros), incluindo soluções geradas, erros de tempo de execução e mensagens intermediárias.
Inovação: Permite a co-evolução de múltiplos componentes, especificamente:
1. Heurística Construtiva ( $\theta_{cons}$ ): Gera soluções iniciais de alta qualidade.
2. Heurística de Refinamento ( $\theta_{ref}$ ): Realiza busca local ou seleção de vizinhança para melhorar a solução.

B. Backward Pass (Passo Retrocedente - Analista)

Função: Analisa os traces de execução para derivar um gradiente semântico ( $\Delta$ ).
Mecanismo: Utiliza um módulo "Analista" (um LLM) que atua como um descobridor de características. Em vez de apenas retornar um número de fitness, o Analista sintetiza funções de características executáveis ( $\Psi$ ) que capturam propriedades estruturais do problema e da solução.
Saída: Um feedback estruturado contendo estatísticas distribucionais (média, faixa, melhores e piores casos) das características, permitindo que o gerador entenda onde e como a heurística falhou.

C. Update Step (Passo de Atualização - Gerador)

Função: Atua como um operador evolutivo semântico.
Mecanismo: Utiliza um LLM para sintetizar a próxima geração de heurísticas ( $P_{t+1}$ ) combinando a população atual com o feedback estruturado ( $\Delta$ ).
Gestão de População: Implementa uma estratégia consciente da diversidade. Para evitar o colapso de modo (convergência prematura para um mínimo local), o gerador seleciona pais baseados não apenas na aptidão média, mas na diversidade comportamental (distância euclidiana entre vetores de desempenho em diferentes instâncias).

3. Contribuições Principais

Formalização Modular: O LaGO formaliza o AHD como um problema de otimização guiada por linguagem, decompondo o ciclo em Forward, Backward e Update. Isso permite a análise sistemática e a melhoria "plug-and-play" de componentes individuais.
Feedback Executável (Analista): Introduz um módulo analista que gera características estruturadas e executáveis, superando a limitação de feedbacks puramente escalares ou textuais.
Co-evolução de Componentes: Demonstra que otimizar conjuntamente heurísticas construtivas e de refinamento gera sinergias que métodos que otimizam apenas uma parte não conseguem alcançar.
Generalização de Métodos Existentes: Mostra que métodos populares (como EoH, ReEvo, LLM-LNS) são instâncias restritas do framework LaGO. Ao aplicar as melhorias modulares do LaGO a esses métodos, o desempenho é significativamente elevado.

4. Resultados Experimentais

O framework foi validado em quatro domínios reais de otimização combinatória do benchmark HeuriGym:

PDPTW (Problema de Coleta e Entrega com Janelas de Tempo).
Airline Crew Pairing (Atribuição de Tripulação Aérea).
Technology Mapping (Mapeamento Tecnológico em EDA).
Intra-Operator Parallelism (Escalonamento de Paralelismo em Compiladores).

Principais Achados:

Desempenho Superior: O LaGO superou consistentemente todas as linhas de base (HeuriGen, EoH, ReEvo, LLM-LNS) em todos os domínios.
Melhoria no QYI: Obteve melhorias de até 0,17 no Índice de Qualidade e Rendimento (QYI) em conjuntos de teste não vistos (ex: PDPTW).
Generalização: O framework manteve uma lacuna de generalização (diferença entre treino e teste) muito menor (0,07) comparado às linhas de base (0,24), indicando que as heurísticas aprendidas são mais robustas e menos propensas a overfitting.
Análise de Componentes:
- A co-evolução (Variante A) foi crucial para resolver o problema de "início frio" em métodos evolutivos.
- O Analista de Código (Variante B) melhorou drasticamente métodos que dependiam apenas de feedback escalar.
- A gestão de diversidade (Variante C) preveniu o colapso de modo, permitindo exploração sustentada.
Robustez: Os resultados foram consistentes ao usar diferentes modelos de linguagem (Gemini-3-Flash e GPT-4.1-mini), provando que o ganho vem da estrutura do framework e não de peculiaridades de um modelo específico.

5. Significado e Impacto

Este trabalho representa uma mudança de paradigma na descoberta automatizada de algoritmos:

De Evolução Estocástica para Otimização Dirigida: Transforma a busca de heurísticas de um processo de mutação aleatória para uma otimização dirigida por feedback semântico estruturado.
Abstração Comum: Oferece uma base unificada para comparar, analisar e estender métodos de AHD baseados em LLMs.
Aplicabilidade em Problemas Complexos: É particularmente eficaz em domínios onde heurísticas manuais são difíceis de projetar e onde as restrições são complexas e não convexas (como logística e design de chips), superando a limitação de métodos anteriores que funcionam bem apenas em problemas bem estudados (como TSP clássico).

Em suma, o LaGO demonstra que a decomposição explícita do ciclo de descoberta de heurísticas, combinada com feedback analítico rico e gestão de diversidade, é a chave para escalar a capacidade dos LLMs na criação de algoritmos de otimização competitivos para problemas do mundo real.