An Evolutionary Framework for Automatic Optimization Benchmark Generation via Large Language Models

Resumo Técnico: Um Framework Evolutivo para Geração Automática de Benchmarks de Otimização via Grandes Modelos de Linguagem

Definição do Problema
Benchmarks de otimização são essenciais para avaliar o desempenho de algoritmos, mas as abordagens existentes enfrentam limitações significativas. Os benchmarks artificiais convencionais (ex: suítes COCO, CEC) baseiam-se em formulações matemáticas predefinidas que frequentemente falham em capturar a heterogeneidade e a irregularidade das estruturas de problemas do mundo real. Por outro lado, os benchmarks derivados de aplicações do mundo real são frequentemente caros para construir, difíceis de reproduzir e restritos por questões de confidencialidade. Embora existam métodos de geração automática de benchmarks, eles tipicamente dependem de geradores paramétricos predefinidos ou representações simbólicas baseadas em árvores (ex: programação genética), o que limita a diversidade e a expressividade dos landscapes de problemas gerados. Há uma necessidade de um framework que possa gerar automaticamente instâncias de benchmarks diversas e reproduzíveis com características estruturais específicas, sem depender de templates rígidos e pré-especificados.

Metodologia: LLM-EBG
Os autores propõem o LLM-driven Evolutionary Benchmark Generator (LLM-EBG), um framework que integra Algoritmos Evolutivos (EAs) com Grandes Modelos de Linguagem (LLMs) para evoluir problemas de benchmark.

• Representação: Problemas de benchmark são representados como expressões matemáticas simbólicas baseadas em texto (código Python) para minimização contínua de objetivo único não restrito.
• Processo Evolutivo: O framework trata os problemas de benchmark como indivíduos de uma população evolutiva. O LLM serve como o operador generativo para inicialização, crossover e mutação, guiado por engenharia de prompt.
  • Inicialização: Uma população inicial é gerada usando uma função semente e prompting de poucos disparos (few-shot prompting), onde o LLM é condicionado a benchmarks existentes para induzir similaridade estrutural enquanto introduz novos componentes.
  • Crossover: Dois benchmarks pais são fornecidos ao LLM como exemplos de contexto (in-context examples), sendo este instruído a gerar um novo problema combinando componentes estruturais de ambos os pais.
  • Mutação: Um único benchmark pai é fornecido, e o LLM é instruído a modificar a expressão estruturalmente (ex: alterando constantes, substituindo funções ou adicionando termos).
• Estratégia de Prompting: O sistema utiliza few-shot prompting com um formato de saída estrito (código Python de linha única) para garantir a validade sintática. O prompt define explicitamente a relação de desempenho alvo (ex: "Crie um problema onde o Algoritmo A1 supere o Algoritmo A2").
• Função de Avaliação: O fitness de um benchmark gerado é determinado pelo desempenho relativo de dois algoritmos alvo (um Algoritmo Genético [GA] e uma Evolução Diferencial [DE]) ao longo de $T$ tentativas. A função de fitness minimiza o ranking normalizado do desempenho do algoritmo alvo em relação ao algoritmo comparativo. Inclui um termo de penalidade para evitar que a solução ótima divirja para o infinito negativo e penaliza benchmarks que produzem valores inválidos (ex: complexos ou infinitos).
• Validação: Uma etapa de pré-validação garante que as expressões geradas produzam saídas de valores reais válidas para amostras aleatórias de variáveis de projeto antes de serem incluídas na população.

Principais Contribuições

1. Framework Inovador: A introdução do LLM-EBG, que utiliza LLMs como operadores evolutivos para buscar diretamente um espaço de expressão simbólica, indo além das restrições de geradores paramétricos predefinidos.
2. Geração de Benchmark Específica para Algoritmos: A demonstração bem-sucedida da geração de benchmarks que induzem disparidades de desempenho significativas entre GA e DE. O framework pode sistematicamente evoluir problemas onde o GA supera consistentemente o DE, e vice-versa.
3. Análise Estrutural: A aplicação de Análise de Landscape Exploratória (ELA) para caracterizar os benchmarks gerados. O estudo revela que os benchmarks que favorecem o GA exibem alta sensibilidade à escala de variáveis (mau condicionamento), enquanto os benchmarks que favorecem o DE mostram disparidades de curvatura mais moderadas.
4. Dinâmica Evolutiva: Uma análise do comportamento do operador do LLM, mostrando que a mutação (particularmente a introdução de novos termos simbólicos) é crucial para escapar de ótimos locais, enquanto o crossover facilita a combinação de estruturas parciais.

Resultos Experimentais
O framework foi testado em dois cenários: buscas "preferência do GA" e "preferência do DE", utilizando 10 tentativas independentes para cada.

• Taxa de Sucesso: O LLM-EBG gerou com sucesso benchmarks onde o algoritmo alvo designado superou o algoritmo comparativo em mais de 80% das tentativas. Especificamente, o fitness mínimo teórico (indicando dominância perfeita) foi alcançado em 8 de 10 tentativas de preferência do GA e 9 de 10 de preferência do DE.
• Características do Landscape:
  • Benchmarks de preferência do GA foram encontrados como altamente sensíveis à escala de variáveis, caracterizados por forte anisotropia e landscapes mal condicionadas (semelhantes a BBOB10 e BBOB11). Esses landscapes favorecem a capacidade do GA de manter a diversidade da população.
  • Benchmarks de preferência do DE exibiram menor sensibilidade à escala de variáveis e landscapes mais suaves, permitindo que o DE explore efetivamente as diferenças posicionais relativas.
• Comportamento de Busca: Nos benchmarks de preferência do GA, o DE tendeu a convergir prematuramente para ótimos locais, enquanto o GA manteve a robustez. Inversamente, nos benchmarks de preferência do DE, o DE convergiu rapidamente para soluções próximas do ótimo, enquanto o GA teve dificuldades com múltiplos ótimos locais.
• Uso de Operadores: A busca de preferência do DE dependeu mais fortemente de operações de mutação (razão de crossover 6,9% menor que a busca de preferência do GA), sugerindo que modificações estruturais locais são mais eficazes para evoluir landscapes que favorecem o DE. A busca de preferência do GA utilizou crossover e mutação em frequências quase iguais.

Significância e Alegações
O artigo afirma que o LLM-EBG estabelece uma metodologia mais fundamentada e confiável para a geração automática de benchmarks em comparação com abordagens existentes. Ao tratar o LLM como um operador evolutivo, o framework pode explorar um espaço de representação flexível e expressivo para gerar problemas com características geométricas distintas que refletem os comportamentos de busca intrínsecos de diferentes algoritmos de otimização.

Os autores afirmam que o framework aborda com sucesso as limitações dos benchmarks artificiais (falta de diversidade) e dos benchmarks do mundo real (custo e reprodutibilidade) ao produzir problemas matematicamente definidos e reproduzíveis que desafiam ou favorecem especificamente certos mecanismos algorítmicos. O estudo conclui que o LLM-EBG pode identificar e amplificar automaticamente propriedades geométricas chave, como anisotropia e mau condicionamento, que diferenciam os comportamentos de busca de algoritmos evolutivos. Um trabalho futuro é proposto para estender o framework para otimização restrita e multiobjetivo, além de uma gama mais ampla de algoritmos.