Resumo Técnico: ImprovEvolve: Basin-Hopping Encontra a Busca Evolutiva Guiada por LLM

Declaração do Problema

O artigo aborda o desafio de usar Grandes Modelos de Linguagem (LLMs) para resolver problemas complexos de otimização matemática, particularmente aqueles com paisagens rugosas, não convexas e não suaves (ex: problemas de empacotamento, desigualdades funcionais e códigos esféricos). Trabalhos anteriores como o AlphaEvolve evoluíram programas monolíticos para gerar soluções candidatas diretamente, mas os autores argumentam que essa abordagem impõe uma carga cognitiva excessiva ao LLM. O modelo deve projetar simultaneamente um esquema de inicialização, uma estratégia de busca e critérios de terminação, o que frequentemente leva a programas gerados que dependem de rotinas prontas (como L-BFGS-B), que falham em lidar com as restrições específicas e a não convexidade do problema de forma eficaz. Consequentemente, as soluções geradas por LLM misturam insight matemático com heurísticas em vez de resolver rigorosamente a tarefa de otimização, e têm dificuldade em generalizar para tamanhos de problemas não vistos ou em melhorar soluções construídas por especialistas.

Metodologia: ImprovEvolve

Os autores propõem o ImprovEvolve, uma alternativa algorítmica que decompõe a tarefa de otimização em sub-rotinas especializadas, integrando efetivamente técnicas de otimização global Basin-Hopping com busca evolutiva guiada por LLM.

Decomposição Central

Em vez de evoluir uma função única que retorna uma solução, o ImprovEvolve evolui uma classe Python que implementa três operadores distintos:

1. generate_config(seed): Inicializa uma solução viável a partir de uma semente aleatória.
2. improve(x): Realiza otimização local para refinar uma configuração $x$, retornando uma solução $x'$ com fitness pelo menos tão bom quanto $x$.
3. perturb(x, \sigma): Explora aleatoriamente o espaço de busca em uma intensidade específica $\sigma$.

Esquema de Validação (Basin-Hopping)

A classe evoluída é utilizada dentro de um esquema de validação de dois estágios (Algoritmo 1) que mimetiza o Monotonic Basin-Hopping ($T=0$):

• Estágio A (Inicialização): Múltiplas configurações iniciais são geradas e refinadas via improve. O melhor resultado é selecionado como o ponto de partida $x^*$.
• Estágio B (Busca Iterativa): O algoritmo realiza $R$ rodadas de perturbação e melhoria. Em cada rodada, a intensidade de perturbação $\sigma$ decai geometricamente de $\sigma_{max}$ para $\sigma_{min}$. O processo envolve:
  1. Perturbar a solução atual de melhor desempenho: $x' = \text{perturb}(x^*, \sigma)$.
  2. Refinar a solução perturbada: $x'' = \text{improve}(x')$.
  3. Aceitação Monotônica: $x^*$ é atualizado para $x''$ apenas se o fitness melhorar estritamente.

Esta decomposição desloca a tarefa do LLM de projetar um otimizador de ponta a ponta para codificar heurísticas específicas do domínio para inicialização, busca local e exploração, que são então orquestradas pelo framework clássico de Basin-Hopping.

Framework Evolutivo

O sistema utiliza o framework GigaEvo com um loop MAP-Elites. O fitness de um programa candidato é determinado executando o esquema de validação de dois estágios completo sobre ele. O LLM (Gemini 3 Pro para inicialização, Gemini 3 Flash para evolução) muta o código da classe Improv, guiado por feedback de fitness e insights de linhagem.

Contribuições Principais e Resultados

1. Empacotamento Hexagonal (HEX $n$)

• Tarefa: Empacotar $n$ hexágonos regulares unitários no menor hexágono regular envolvente.
• Resultados:
  • Para $n=11$, o ImprovEvolve descobriu um novo estado da arte (SOTA) de empacotamento com lado $L=3.9245$, superando o $3.9301$ do AlphaEvolve e o recorde humano anterior de $3.9434$.
  • O programa evoluído generalizou para tamanhos de problemas não vistos ($11 \le n \le 24$) sem re-evolução, encontrando novos empacotamentos SOTA para $n=12, 15, 16$.
  • ImprovEvolve+E: Com edições humanas mínimas (trocando otimizadores, ajustando pesos de penalidade), o sistema encontrou novos empacotamentos SOTA para $n=14, 17, 23$ e forneceu empacotamentos estruturados para $n=25-30$ onde não existiam resultados prévios.
  • Comparação: O ImprovEvolve superou significativamente o baseline GigaEvo (abordagem monolítica), que falhou em generalizar para $n > 11$ devido a erros de sobreposição.

2. Segunda Desigualdade de Autocorrelação (ACI 2)

• Tarefa: Encontrar uma função não negativa $f$ que maximize a constante $C_2$ na desigualdade $\|f * f\|_2^2 \le C_2 \|f * f\|_1 \|f * f\|_\infty$.
• Resultados:
  • O programa base do ImprovEvolve alcançou $C(f) = 0.9512$, superando baselines de código aberto, mas ficando aquém do $0.96102$ do AlphaEvolve.
  • ImprovEvolve+E: Ao retomar a otimização a partir da solução do AlphaEvolve e aplicar edições guiadas por humanos (escala de resolução progressiva até 1.6M de passos, removendo o clipping inferior), o sistema alcançou um novo limite inferior SOTA de $C(f) = 0.96258$.
  • Significância: Isso demonstra a capacidade do framework de refinar soluções de alta qualidade já existentes fornecidas por especialistas ou outros modelos, uma capacidade que abordagens de LLM monolíticas têm dificuldade em realizar.

3. Códigos Esféricos

• Tarefa: Organizar $N$ pontos em uma esfera unitária $S^{d-1}$ para minimizar o produto interno máximo (coerência).
• Resultados:
  • Avaliado em 90 configurações diversas do catálogo Cohn ($d \in [8, 16]$).
  • ImprovEvolve++ (um melhorador geral calibrado evoluído através de múltiplas dimensões) reduziu estritamente o cosseno máximo para 53 das 9 de 90 configurações, alcançando uma melhoria relativa média de 0.1765%.
  • Isso representa uma melhoria de 2.35$\times$ sobre o melhor programa anterior (ImprovEvolve).
  • Diagnósticos (UMAP e distribuições de produto interno) mostraram que o ImprovEvolve++ realizou rearranjos estruturais globais, movendo pontos para regiões distintas do espaço de busca, enquanto outras variantes apenas faziam ajustes locais.

Robustez Estatística

Estudos de múltiplas execuções confirmaram que as melhorias do ImprovEvolve são estatisticamente significativas ($p < 0.05$) em comparação com o baseline GigaEvo, validando que a decomposição modular oferece uma vantagem reproduzível sobre o aprendizado de um otimizador monolítico.

Significância e Alegações

O artigo afirma que decompor tarefas de otimização em subproblemas modulares é um princípio crítico para a descoberta guiada por LLM.

• Redução da Carga Cognitiva: Ao separar inicialização, melhoria local e perturbação, o LLM foca em codificar a estrutura matemática e heurísticas, em vez de orquestrar todo o processo de busca.
• Colaboração Humano-LLM: A interface modular permite que especialistas no domínio apliquem edições direcionadas e mínimas (ex: mudar otimizadores, ajustar cronogramas de resolução) para aumentar significativamente o desempenho, preenchendo a lacuna entre o código gerado por LLM e o ajuste de nível especialista.
• Generalização: A interface improve/perturb permite que programas evoluídos generalizem para tamanhos de problemas não vistos e possam retomar a otimização a partir de soluções fornecidas por especialistas, superando a fragilidade de programas de ponta a ponta monolíticos.

Os autores posicionam este trabalho como um passo em direção à escala da descoberta matemática impulsionada por LLM, sugerindo que sistemas futuros devem combinar tais decomposições personalizadas com fluxos de trabalho agentes que decidam autonomamente quais módulos refinar. O artigo permanece modesto quanto à generalização mais ampla, observando que a avaliação quantitiva é atualmente limitada a estes três domínios específicos de otimização.