A2DEPT: Large Language Model-Driven Automated Algorithm Design via Evolutionary Program Trees

1. Definição do Problema

O artigo aborda o desafio do Design Automatizado de Heurísticas (AHD) para Problemas de Otimização Combinatória (COPs).

• Contexto: Os COPs (por exemplo, TSP, Roteamento de Veículos, Programação de Oficinas) são tipicamente NP-difíceis. O design manual tradicional de heurísticas é intensivo em mão de obra, exige profundo conhecimento de domínio e frequentemente falha em generalizar entre variantes de problemas.
• Limitações Atuais: Métodos recentes de AHD baseados em Grandes Modelos de Linguagem (LLMs) (por exemplo, FunSearch, EoH, ReEvo) mostraram promessa, mas sofrem de um gargalo crítico: operam dentro de modelos algorítmicos fixos. Eles otimizam apenas componentes isolados de heurísticas (como funções de pontuação), mantendo a lógica do solucionador circundante (fluxo de controle, retrocesso, estrutura de iteração) rígida.
• A Lacuna: Essa abordagem "limitada por modelos" limita a inovação em nível de sistema. Se o modelo for subótimo para um problema específico, a heurística não pode compensar. Além disso, passar da otimização de um único componente para o design de um solucionador completo (Design Automatizado de Algoritmos Aberto, ou AAD) introduz desafios massivos:
  1. Instabilidade de Executabilidade: A geração de código livre frequentemente leva a erros de compilação, dependências ausentes ou falhas em tempo de execução.
  2. Explosão do Espaço de Busca: O espaço de programas completos válidos e de alto desempenho é vasto e esparsamente distribuído.
  3. Opacidade na Atribuição de Crédito: É difícil atribuir ganhos de desempenho a alterações específicas de código quando todo o algoritmo está evoluindo.

2. Metodologia: Framework A2DEPT

Os autores propõem o A2DEPT (Automated Algorithm Design via Evolutionary Program Trees), um framework que trata LLMs como arquitetos de nível de sistema para evoluir programas de solucionadores completos e executáveis.

Componentes Principais:

1. Busca Evolutiva Estruturada em Árvore:

   • Diferentemente de métodos baseados em população, o A2DEPT mantém uma árvore de busca global onde os nós representam programas executáveis, suas pontuações e metadados de geração.
   • Estratégia Híbrida de Seleção:
     • Seleção Primária por Recozimento Simulado (SA): Utiliza o critério de Metropolis para aceitar pares pai-filho com base na melhoria da pontuação, preservando uma relação de "refinamento pai-filho".
     • Seleção Suplementar de Boltzmann: Para evitar que a busca colapse em uma seleção top-k gananciosa e para preservar a diversidade, o sistema amostra pais adicionais do histórico global da árvore usando probabilidades de Boltzmann. Isso permite que ramos "com desempenho inferior, mas estruturalmente promissores" sobrevivam.
   • Re-resfriamento Dinâmico: Se a busca estagnar (sem melhoria por $N_{stall}$ gerações), a temperatura é aumentada para restaurar a capacidade de exploração.

2. Operadores Hierárquicos com Agendamento Adaptativo:
   Para abordar a atribuição de crédito e permitir mudanças estruturais, o A2DEPT utiliza três níveis de operadores, agendados adaptativamente com base no feedback:

   • Ajuste Fino ($m_1$): Edições locais em funções de estratégia mutáveis (por exemplo, refinar uma fórmula de pontuação) preservando as interfaces.
   • Mutação Macro ($m_2$): Redesenho de cima para baixo do ponto de entrada do solucionador e do fluxo de controle. Permite que o LLM chame funções auxiliares não definidas, que são preenchidas posteriormente.
   • Crossover Semântico ($e_1$): Sintetiza um programa híbrido integrando mecanismos complementares de dois pais.
   • Agendamento Adaptativo: Um vetor de pesos específico por nó é atualizado com base na mudança de desempenho ($\bar{r}$) do filho. Operadores bem-sucedidos são reforçados, enquanto os malsucedidos são penalizados, deslocando dinamicamente o esforço de busca entre o refinamento micro e o reestruturamento macro.

3. Mecanismo de Manutenção de Programas (Aplicação de Executabilidade):
   Para tornar a geração aberta prática, o A2DEPT inclui um loop de reparo leve, orientado por feedback:

   • Representação Estruturada: Os programas são divididos em um "Prefácio" imutável (importações, constantes) e um "Registro de Funções" mutável.
   • Reparo de Dependências: Quando um programa gerado chama funções não definidas (comum na mutação macro), um grafo de dependências é construído. O LLM é solicitado iterativamente a implementar funções ausentes até que o programa esteja "fechado em dependências".
   • Poda: Código inacessível é podado para evitar o acúmulo de lógica morta.

3. Contribuições Principais

1. Mudança de Paradigma: Transita do AHD limitado por modelos (otimização de componentes) para o AAD aberto (evolução de solucionadores completos), desbloqueando um espaço de design mais rico.
2. Framework A2DEPT: Introduz uma busca evolutiva estruturada em árvore com seleção híbrida (SA + Boltzmann) e operadores hierárquicos para navegar no vasto espaço de programas.
3. Mecanismos de Confiabilidade: Propõe um loop de manutenção de programas para reparo automatizado de dependências e uma representação estruturada para garantir a executabilidade durante a evolução.
4. Validação Empírica: Demonstra superioridade consistente em relação a baselines baseadas em LLMs de última geração em diversos benchmarks NP-difíceis.

4. Resultados Experimentais

Os autores avaliaram o A2DEPT em seis problemas NP-difíceis: MIS, CVRP, CFLP, FJSP (benchmarks padrão) e CEVRPTW, MRCPSP (benchmarks de alta restrição).

• Desempenho em Benchmarks Padrão:
  • O A2DEPT superou todas as baselines baseadas em LLMs (FunSearch, EoH, ReEvo, MCTS-AHD) em todas as tarefas.
  • Métrica Chave: Em benchmarks padrão, o A2DEPT reduziu o gap de otimalidade normalizado médio em 9,8% em relação à baseline de AHD concorrente mais forte.
  • Alcançou resultados competitivos contra referências não-LLM (por exemplo, igualando o Gurobi no MIS).
• Problemas de Alta Restrição:
  • No CEVRPTW e MRCPSP, o A2DEPT alcançou a menor Taxa de Inviabilidade (IR) e os melhores gaps de otimalidade, demonstrando robustez em espaços de busca fragmentados onde outros métodos frequentemente falham em encontrar soluções válidas.
• Generalização:
  • O A2DEPT mostrou forte generalização entre diferentes frameworks de design (por exemplo, Busca Local Guiada) e distribuições de instâncias.
  • Estudos de ablação confirmaram que a remoção de qualquer componente (por exemplo, amostragem de Boltzmann, agendamento adaptativo ou o loop de manutenção) degradou significativamente o desempenho.
• Otimização Contínua:
  • O framework também foi aplicado com sucesso a domínios contínuos (resolução de EDOs, busca de raízes, políticas de controle), descobrindo solucionadores numéricos inovadores que superaram baselines industriais especializadas (por exemplo, LSODA) em problemas rígidos.

5. Significado e Impacto

• Inovação em Nível de Sistema: O A2DEPT prova que os LLMs podem atuar como "arquitetos de algoritmos", não apenas geradores de código. Ao evoluir toda a lógica do solucionador, pode descobrir paradigmas estruturais (por exemplo, a transição de uma heurística construtiva gananciosa para um framework de Busca Local Iterada) que o ajuste fino em nível de componente não consegue alcançar.
• Escalabilidade: O framework aborda o gargalo da "executabilidade" da geração de código aberta, tornando viável evoluir programas complexos e multi-módulos sem intervenção humana.
• Direções Futuras: O artigo sugere que, embora os métodos atuais estejam limitados à escala de protótipos de pesquisa, a abordagem abre caminho para a síntese automatizada de solucionadores de nível industrial, desde que trabalhos futuros abordem o gerenciamento modular e a verificação estática de tipos para grandes bases de código.

Em resumo, o A2DEPT representa um salto significativo no design automatizado de algoritmos, avançando além do "preencher lacunas" de um modelo fixo para "escrever o livro inteiro", alcançando assim desempenho superior e robustez na resolução de problemas complexos de otimização combinatória.