ReVEL: Multi-Turn Reflective LLM-Guided Heuristic Evolution via Structured Performance Feedback

O artigo apresenta o ReVEL, um framework híbrido que integra Grandes Modelos de Linguagem (LLMs) em algoritmos evolutivos por meio de feedback estruturado e reflexão multi-turno para gerar heurísticas mais robustas e diversificadas para problemas de otimização combinatória NP-difíceis.

O essencial

Imagine que você precisa organizar uma festa enorme e complexa. Você tem centenas de convidados, uma lista de restrições (quem não pode sentar junto, quem precisa de cadeira especial, quanto espaço sobra na mesa) e o objetivo é criar o melhor arranjo possível. Fazer isso manualmente é exaustivo e propenso a erros.

No mundo da computação, problemas como esse são chamados de problemas de otimização combinatória. Eles são como quebra-cabeças gigantes onde o número de combinações possíveis é infinito.

Aqui está a explicação do paper ReVEL usando uma analogia simples:

O Problema: O "Chef" que Cozinha de Uma Só Vez

Até agora, a inteligência artificial (especificamente os Grandes Modelos de Linguagem, ou LLMs, como o ChatGPT) tentava resolver esses problemas de uma forma muito direta:

1. Você pede ao "Chef IA": "Crie um algoritmo para organizar a festa".
2. O Chef joga uma receita na mesa.
3. Você testa a receita. Se der errado, você pede para ele tentar de novo, do zero.

O problema é que o Chef não aprende muito com o erro anterior. Ele apenas joga outra receita aleatória. É como tentar adivinhar a senha do Wi-Fi chutando números aleatórios sem usar as dicas que você já recebeu.

A Solução: ReVEL (O "Chef" que Reflete e Aprende)

O ReVEL muda completamente a dinâmica. Em vez de pedir uma receita nova a cada vez, ele cria um processo de evolução e reflexão.

Imagine que o ReVEL é como um chef de cozinha com um assistente de controle de qualidade e um grupo de degustadores.

1. O Grupo de Degustadores (Agrupamento Inteligente)

Quando o Chef cria várias receitas (algoritmos), o ReVEL não as trata todas como iguais. Ele as agrupa por estilo:

• O "Grupo da Salada" (receitas que funcionam bem para ingredientes leves).
• O "Grupo do Prato Principal" (receitas para ingredientes pesados).
• O "Grupo da Sobremesa" (receitas para finais delicados).

Isso é importante porque, em vez de dizer ao Chef "essa receita falhou", o sistema diz: "Olhe, todas as receitas do Grupo da Salada falharam porque estavam muito ácidas". Isso dá uma dica estruturada e muito mais útil.

2. A Reflexão em Várias Rodadas (O Diálogo)

Aqui está a mágica. Em vez de apenas pedir "arrume isso", o ReVEL faz o Chef pensar em voz alta várias vezes (multi-turn):

• Rodada 1: O Chef olha para o grupo de receitas falhas e diz: "Hum, percebo que o problema é que estamos usando muito vinagre. Vou tentar reduzir."
• Rodada 2: Ele ajusta a receita e testa novamente.
• Rodada 3: O sistema avisa: "Melhorou, mas ainda falta um toque de sal."
• Rodada 4: O Chef ajusta o sal.

O Chef não está apenas "chutando"; ele está refletindo sobre o que funcionou e o que não funcionou, usando as dicas do grupo para evoluir a receita passo a passo.

3. Explorar vs. Explorar (O Equilíbrio)

O sistema tem um mecanismo inteligente para decidir o que fazer:

• Explorar: Se todas as receitas parecem iguais e não melhoram, o sistema diz: "Esqueça o que sabemos, vamos tentar uma cozinha totalmente nova!" (Talvez usar um forno em vez de uma frigideira).
• Explorar (Aproveitar): Se uma receita está quase perfeita, o sistema diz: "Não mude tudo! Apenas ajuste o tempero final."

Por que isso é incrível?

Os testes mostraram que o ReVEL é muito melhor do que os métodos antigos.

• Mais Robusto: As receitas criadas funcionam bem em diferentes tipos de festas (problemas), não apenas em uma situação específica.
• Mais Diverso: O sistema descobre soluções criativas que humanos ou IAs tradicionais não teriam pensado.
• Mais Eficiente: Embora o processo de "reflexão" leve um pouco mais de tempo de computação, o resultado final é tão superior que vale cada segundo gasto.

Resumo em uma Frase

O ReVEL transforma a Inteligência Artificial de um "alguém que chuta respostas" em um cientista que observa, agrupa seus erros, reflete sobre padrões e melhora sua solução passo a passo, resultando em soluções muito mais inteligentes para problemas complexos do mundo real, como logística, entregas e roteirização.

Resumo técnico

Título: ReVEL: Evolução Heurística Guiada por LLM Reflexiva Multi-turno via Feedback de Performance Estruturado

1. O Problema

O design de heurísticas eficazes para Problemas de Otimização Combinatória (COPs) NP-difíceis (como o Problema do Caixeiro Viajante - TSP, e o Problema de Empacotamento em Lotes - BPP) é tradicionalmente uma tarefa intensiva em expertise e manual.

• Limitações das Abordagens Atuais:
  • Métodos Clássicos e Meta-heurísticos: Dependem de conhecimento humano fixo e têm dificuldade em adaptação a longo prazo.
  • Hyper-heurísticas: Selecionam ou combinam heurísticas de um pool pré-definido, limitando a descoberta de estruturas fundamentalmente novas.
  • Síntese de Código por LLMs (One-shot): Abordagens recentes usam Grandes Modelos de Linguagem (LLMs) para gerar código heurístico em uma única tentativa. Isso resulta em heurísticas frágeis que não aproveitam a capacidade dos modelos para raciocínio iterativo e refinamento profundo.
  • Falta de Feedback Estruturado: Métodos existentes que incorporam reflexão (como ReEvo) frequentemente tratam a crítica como um passo discreto ou baseado em comparações binárias (par a par), fornecendo sinais de feedback grosseiros e atrasados, o que limita a profundidade da melhoria.

2. Metodologia: O Framework ReVEL

O ReVEL propõe um framework híbrido que integra um Algoritmo Evolutivo (EA) com um LLM, transformando a descoberta de heurísticas em um processo de raciocínio reflexivo multi-turno. Em vez de gerar código isolado, o LLM atua como um componente de raciocínio adaptativo dentro de um ciclo evolutivo.

Componentes Principais:

A. Agrupamento e Clusterização Comportamental (Performance-Profile Grouping)
O núcleo da inovação do ReVEL é organizar as heurísticas candidatas em grupos para fornecer feedback mais rico e compacto ao LLM:

• Representação: Cada heurística é representada por um vetor de perfil de performance normalizado, comparando seu desempenho em múltiplas instâncias do problema contra a melhor solução conhecida.
• Grupos Homogêneos (Semelhança): Agrupam heurísticas com comportamentos e estruturas similares. A similaridade é calculada combinando:
  1. Similaridade de Performance: Cosseno entre vetores de performance.
  2. Similaridade Semântica: CodeBLEU (análise sintática e semântica do código).
  • Um processo de duas fases (aglomeração inicial + refinamento guiado por LLM) cria clusters coesos.
• Grupos Heterogêneos (Diversidade): Combinam heurísticas de clusters distintos para estimular a síntese criativa e ampliar o espaço de busca. A seleção é ponderada pela entropia da similaridade interna dos clusters.

B. Refinamento Reflexivo Multi-turno
Dentro de cada grupo, o LLM engaja em um diálogo estruturado seguindo o ciclo: Observar → Raciocinar → Agir.

• Estado e Reflexão: O LLM recebe um estado compacto contendo diagnósticos de desempenho (custos, vetores de melhoria) e histórico. Ele analisa padrões estruturais, modos de falha recorrentes e forças latentes.
• Estratégia Adaptativa (Exploração vs. Exploração):
  • Exploração: Acionada quando há estagnação ou convergência prematura. O LLM propõe novas famílias de algoritmos ou recombinações divergentes.
  • Exploração (Intensificação): Acionada quando candidatos promissores são detectados. O LLM realiza refinamentos direcionados (ajuste de hiperparâmetros, correção de lógica incremental).
• Ação: O LLM gera artefatos acionáveis (patches, novos códigos, entradas de DSL) com justificativa.
• Feedback Contínuo: Observações de performance são injetadas a cada turno, permitindo que o LLM ajuste sua estratégia dinamicamente, evitando a estagnação em ótimos locais.

C. Controle Meta-Evolutivo
Um controlador baseado em EA gerencia a população, selecionando e integrando as heurísticas refinadas pelo LLM, equilibrando a diversidade e a qualidade ao longo das gerações.

3. Contribuições Chave

1. Framework Reflexivo LLM-EA: Introduz um paradigma onde a descoberta de heurísticas é um processo de refinamento coerente, não gerações independentes. O LLM acumula feedback evolutivo para raciocinar multi-turno.
2. Mecanismo de Agrupamento Consciente de Performance: Estrutura o feedback em torno de clusters comportamentais coesos, permitindo análises mais informativas e refinamentos generalizáveis, superando as limitações de comparações par a par.
3. Estratégia de Prompting Guiada por Feedback: Integra um ciclo de geração-avaliação-seleção com prompts adaptativos que controlam o trade-off exploração-exploração de forma principial.
4. Validação Empírica Robusta: Demonstra que o ReVEL produz heurísticas mais robustas e diversas, superando baselines fortes em benchmarks padrão.

4. Resultados Experimentais

Os experimentos foram conduzidos em benchmarks clássicos: TSP (10 a 200 nós) e BPP Online (capacidades de 100 a 500, até 10k itens).

• Desempenho Quantitativo:
  • BPP: O ReVEL reduziu consistentemente a fração de excesso de bins. Em capacidades apertadas (C=100), alcançou 2-3% de excesso, superando First Fit/Best Fit (4-5%) e métodos adaptativos como ReEvo.
  • TSP: Alcançou gaps de otimalidade menores que os métodos baseados em LLM (EoH, ReEvo) em todas as escalas de instância (n=10 a 200).
• Robustez do Backbone: O desempenho superior foi mantido ao testar com diversos modelos LLM (DeepSeek V3, Kimi, Qwen, GLM), indicando que a melhoria vem do workflow estruturado do ReVEL e não apenas da potência bruta do modelo base.
• Estudo de Ablação:
  • A remoção de qualquer componente (refinamento multi-turno ou agrupamento) degradou severamente o desempenho (ex: gap de 9.20% no ReVEL completo vs. 17.18% sem multi-turno).
  • Ajuste de coeficientes de similaridade (α) mostrou que o equilíbrio entre similaridade comportamental e semântica é crucial (α=0.5 foi o ideal).
• Análise de Comportamento: O LLM naturalmente segue uma trajetória "explorar-então-explorar", com mudanças de paradigma ocorrendo no início/fim e refinamentos granulares no meio, guiados pelo feedback estruturado.
• Validação Adicional: Resultados positivos em instâncias reais do TSPLib e no Problema de Roteamento de Veículos com Capacidade (CVRP) confirmam a generalização do método.

5. Significado e Conclusão

O ReVEL representa uma mudança de paradigma no design automatizado de heurísticas. Ao tratar o LLM não como um gerador estático de código, mas como um agente de raciocínio adaptativo que reflete sobre falhas coletivas e padrões estruturais, o método supera as limitações da síntese "one-shot".

A principal implicação é que a estruturação do feedback (via agrupamento comportamental) é tão crítica quanto a capacidade do modelo de linguagem. O ReVEL oferece um caminho escalável e eficiente em termos de amostras para automatizar o design de heurísticas em domínios complexos de otimização, demonstrando que a reflexão iterativa guiada por dados pode superar métodos evolutivos tradicionais e abordagens de IA generativa convencionais.