Resumo Técnico: Evolução Consciente do Professor de Programas Heurísticos a partir de Políticas de Otimização Aprendidas

1. Declaração do Problema

Problemas de otimização combinatória (por exemplo, agendamento, roteamento, otimização de grafos) frequentemente dependem de regras heurísticas compactas e interpretáveis. Embora essas regras sejam rápidas e fáceis de implantar, projetá-las geralmente exige significativa expertise de domínio e ajuste empírico. Métodos recentes de Design Automático de Heurísticas (AHD) baseados em Modelos de Linguagem Grandes (LLM) demonstraram promessa na geração de heurísticas executáveis por meio de busca evolutiva. No entanto, as abordagens existentes dependem principalmente do desempenho no ponto final atrasado (o valor objetivo final após uma execução completa) ou de feedback interno do LLM (reflexões textuais, estatísticas da população) para guiar a evolução.

Essa dependência de feedback no ponto final limita a granularidade do sinal de busca. O artigo postula que Políticas de Otimização Aprendidas (treinadas via Aprendizado por Reforço Profundo ou Otimização Combinatória Neural) contêm informações comportamentais ricas e em nível de ação que são atualmente subutilizadas. Embora essas políticas neurais sejam tipicamente usadas como solucionadores, elas podem servir como "professores comportamentais" que fornecem preferências sobre decisões candidatas em estados específicos. O desafio é aproveitar essas políticas aprendidas para guiar a evolução de programas heurísticos estáticos e executáveis, sem exigir que o programa final imite o professor ou realize inferência neural na implantação.

2. Metodologia

Os autores propõem um Framework Evolutivo Consciente do Professor que integra políticas de otimização de caixa preta treinadas independentemente como professores comportamentais externos no loop de busca heurística baseado em LLM.

Mecanismo Central: Diagnóstico de Professor On-Policy

Em vez de implantar o professor ou usá-lo para imitação direta, o framework consulta o professor nos estados visitados por programas heurísticos candidatos durante sua execução.

• Amostragem de Estados: Para um heurístico candidato $h$, o sistema executa uma simulação para gerar uma trajetória de estados $S_h$.
• Consulta ao Professor: A política do professor $T$ é consultada nesses estados específicos para determinar sua ação preferida $a_T(s)$ ou pontuações de ação $Q_T(s, a)$.
• Sinais de Alinhamento: O sistema computa:
  • Acordo Top-1: A frequência com que a ação do candidato corresponde à ação preferida do professor.
  • Valor Normalizado do Professor: Se pontuações estiverem disponíveis, o valor normalizado da ação escolhida pelo candidato em relação ao conjunto de ações viáveis.
  • Rank Percentil: A classificação da ação do candidato sob a ordenação do professor.

Reflexão e Revisão Guiadas pelo Professor

Esses sinais diagnósticos são convertidos em feedback acionável para o analisador LLM. Um adaptador de interface de tarefa leve garante que o feedback seja contextualmente relevante. O analisador LLM gera resumos de revisão baseados em três operadores guiados pelo professor específicos:

1. Reescrita Estrutural: Modifica componentes de decisão de alto nível quando discordâncias revelam falhas estruturais recorrentes.
2. Calibração de Parâmetros: Ajusta pesos, limiares ou portas quando o programa seleciona ações razoáveis, mas está localmente mal calibrado em relação ao professor.
3. Fusão em Nível de Mecanismo: Combina um mecanismo forte em objetivo com um mecanismo forte em alinhamento para preservar o desempenho enquanto incorpora vieses comportamentais derivados do professor.

Gerenciamento de População

O framework emprega uma estratégia de seleção multiobjetivo usando classificação não dominada estilo Pareto. Cada candidato é avaliado em um vetor $z(h) = (F(h), -Align(h))$, onde $F(h)$ é o objetivo da tarefa (minimizado) e $Align(h)$ é o alinhamento com o professor (minimizado).

• Seleção: O heurístico final é selecionado com base no desempenho da tarefa, não na fidelidade ao professor. Isso garante que a saída permaneça um programa estático e eficiente otimizado para a tarefa específica, em vez de uma versão comprimida do professor.

3. Contribuições Principais

O artigo afirma quatro contribuições primárias:

1. Formulação: Introduz o conceito de usar políticas de otimização de caixa preta treinadas independentemente como professores comportamentais externos para a evolução de heurísticas baseada em LLM.
2. Alinhamento de Professor On-Policy Amostrado: Um método para consultar professores em estados induzidos por candidatos e converter suas preferências em sinais de busca comportamental local, distinto da aprendizagem por imitação padrão.
3. Evolução Reflexiva Consciente do Professor: Um framework que utiliza resumos de alinhamento com o professor e casos de discordância para guiar revisões estruturais e paramétricas de programas heurísticos.
4. Validação Empírica: Demonstração em quatro domínios de otimização combinatória sequenciais (JSSP, TSP, CVRP, MaxCut) de que políticas aprendidas podem guiar efetivamente a descoberta de heurísticas estáticas, interpretáveis e eficientes.

4. Resultados Experimentais

O método foi avaliado em quatro benchmarks: Agendamento de Oficinas (JSSP), Problema do Caixeiro Viajante (TSP), Problema de Roteamento de Veículos com Capacidade (CVRP) e MaxCut.

• Desempenho: O método proposto superou consistentemente as linhas de base de LLM orientadas a desempenho (EoH, ReEvo) e regras de despacho clássicas em configurações dentro da distribuição e fora da distribuição (OOD).
  • JSSP: Alcançou o melhor makespan em instâncias 10x10, 15x15 e 20x20, e demonstrou generalização superior para instâncias aleatórias maiores e benchmarks Taillard.
  • Roteamento (TSP/CVRP): Produziu a melhor qualidade de solução entre heurísticas evoluídas por LLM, estreitando a lacuna para solucionadores especializados (como LKH) enquanto mantinha a velocidade de programas estáticos.
  • MaxCut: Mostrou desempenho competitivo em distribuições de treinamento e forte transferibilidade para diferentes distribuições de grafos (por exemplo, de Barabási–Albert para Erdős–Rényi) e escalas.
• Eficiência: As heurísticas resultantes são programas executáveis estáticos, não exigindo inferência neural na implantação. Elas são substancialmente mais rápidas do que as políticas neurais aprendidas (professores) usadas para orientação.
• Estudos de Ablação: A remoção do feedback derivado do professor ("Apenas Desempenho") degradou consistentemente os resultados, confirmando o valor dos sinais comportamentais. A remoção de componentes específicos (orientação do analisador, operadores guiados pelo professor ou atualizações Pareto) também levou a quedas de desempenho, particularmente na generalização OOD.

5. Significado e Afirmações

O artigo argumenta que políticas de otimização aprendidas podem ser reaproveitadas como fontes de feedback comportamental para a descoberta automática de heurísticas. O significado reside em mudar o papel das políticas neurais de serem o solucionador final para serem uma fonte de feedback local em nível de decisão.

• Complementaridade: As preferências do professor fornecem um sinal complementar ao fitness no ponto final, guiando a busca em direção a heurísticas que preservam vieses aprendidos úteis enquanto corrigem fraquezas específicas.
• Estático vs. Neural: O framework conecta com sucesso a lacuna entre o alto desempenho das políticas neurais aprendidas e a interpretabilidade/eficiência das heurísticas estáticas.
• Modéstia: Os autores reconhecem limitações, observando que o método requer um professor aprendido alinhável, adaptadores de interface específicos para a tarefa e chamadas do analisador. Eles não afirmam substituir todos os solucionadores, mas sim melhorar o processo de descoberta de heurísticas estáticas.

Em resumo, o trabalho demonstra que, ao tratar políticas aprendidas como "professores comportamentais" em vez de "solucionadores a serem imitados", é possível evoluir heurísticas estáticas que são tanto de alto desempenho quanto eficientes, aproveitando os ricos sinais de decisão local do aprendizado profundo sem herdar sua sobrecarga computacional.