Code World Models for Parameter Control in Evolutionary Algorithms

Este artigo demonstra que os Modelos de Mundo de Código (CWMs), ao sintetizarem simuladores de dinâmicas de otimizadores a partir de trajetórias subótimas, permitem que um LLM controle efetivamente parâmetros em algoritmos evolutivos, superando métodos adaptativos e de aprendizado por reforço em diversos problemas de otimização combinatória estocástica.

O essencial

Imagine que você está tentando resolver um quebra-cabeça gigante, mas em vez de olhar para a imagem final, você só pode ver uma peça de cada vez e precisa decidir qual peça tentar encaixar a seguir. No mundo da computação, isso é chamado de Algoritmo Evolutivo. O "segredo" para resolver o quebra-cabeça rápido é saber quão agressivo você deve ser ao trocar as peças.

• Se você trocar apenas 1 peça por vez, é lento, mas seguro.
• Se você trocar 50 peças de uma vez, é rápido, mas pode estragar tudo o que já estava bom.

A grande pergunta deste artigo é: Como um computador descobre sozinho a quantidade perfeita de peças para trocar a cada momento, sem que um humano tenha que ensinar a regra?

A Ideia Principal: O "Simulador de Mundo" Feito por IA

Os autores criaram uma técnica chamada Code World Models (CWMs). Pense nisso como se você tivesse um engenheiro de software genial (uma IA) que nunca jogou o jogo, mas leu o manual e assistiu a centenas de pessoas jogando (algumas jogando bem, outras mal).

1. A Observação (Offline): A IA assiste a 200 ou 300 tentativas de alguém tentando resolver o problema. Ela não vê a solução perfeita, apenas tentativas imperfeitas.
2. A Criação (Síntese): Em vez de apenas "adivinhar" a resposta, a IA escreve um programa de computador real (em Python). Esse programa é um "simulador". Ele diz: "Se eu estiver nesta situação e trocar 5 peças, a chance de melhorar é X. Se trocar 10, a chance é Y."
3. A Ação (Online): Agora, quando o algoritmo real precisa jogar, ele consulta esse "simulador" escrito pela IA. O simulador diz: "Neste momento, a melhor jogada é trocar 3 peças". O algoritmo faz isso e avança.

Por que isso é revolucionário? (As Analogias)

O artigo testa essa ideia em quatro cenários diferentes, cada um mais difícil que o outro:

1. A Subida Suave (LeadingOnes e OneMax)

Imagine subir uma montanha com uma estrada reta.

• O problema: Você sabe que, quanto mais perto do topo, mais devagar você deve andar para não escorregar.
• O resultado: A IA aprendeu sozinha a regra: "Quanto mais perto do topo, menor o número de peças para trocar". Ela conseguiu fazer isso tão bem que ficou apenas 6% mais lenta que a solução teórica perfeita, sem nunca ter visto a solução perfeita. Ela deduziu a lógica apenas observando os erros e acertos dos outros.

2. O Vale da Desilusão (Jumpk) - O Grande Trunfo

Aqui está a mágica. Imagine que você está subindo a montanha, mas de repente há um vale profundo (uma armadilha) antes do topo.

• O problema: Para sair do vale, você precisa dar um salto gigante e arriscado (trocar muitas peças de uma vez).
• O erro dos outros: Os métodos tradicionais (como o "Regra de 1/5") veem que você não está subindo e pensam: "Ah, você está preso, então vamos tentar movimentos menores e mais seguros". Isso é fatal! Eles diminuem o salto e ficam presos no fundo do vale para sempre.
• O sucesso da IA: O simulador da IA percebeu, ao analisar os dados, que "nessa situação específica, só um salto grande funciona".
• Resultado: Enquanto todos os outros métodos falharam 100% das vezes, a IA conseguiu 100% de sucesso em atravessar o vale, sem que ninguém lhe dissesse onde o vale estava ou qual era o tamanho do salto necessário.

3. O Terreno Caótico (NK-Landscape)

Imagine um terreno cheio de buracos, picos e vales aleatórios, onde não existe nenhuma fórmula matemática para prever o que acontece.

• O problema: Não há "regra do jogo" escrita. É puro caos.
• A solução: A IA não usou matemática. Ela usou estatísticas empíricas (um resumo de dados: "quando a pontuação está entre 20 e 25, trocar 25 peças funciona melhor").
• Resultado: A IA criou um simulador baseado apenas nesses dados e superou todos os outros métodos, provando que ela pode aprender a "dançar" em terrenos onde não existe mapa.

Comparação com outros "Cérebros" (DQN)

Os autores também compararam sua IA com uma técnica famosa de aprendizado por reforço chamada DQN (como o cérebro de um robô que aprende jogando milhões de vezes).

• O DQN: Precisa de muito tempo de treino (500 episódios), gasta muita energia e, quando o jogo muda um pouco (ex: o tamanho do salto necessário muda), ele falha miseravelmente (0% de sucesso). Ele "decorou" o treino, mas não entendeu o conceito.
• A IA (CWM): Aprendeu com apenas 200 tentativas (menos dados), criou um código que explica por que a jogada funciona e, quando o jogo mudou, ela se adaptou instantaneamente (78% de sucesso).

Conclusão Simples

Este artigo mostra que podemos usar Inteligência Artificial não para "adivinhar" a resposta, mas para escrever o manual de instruções de como jogar.

Em vez de treinar um robô para jogar milhões de vezes até ele acertar por sorte, nós pedimos para a IA ler os dados, entender a lógica do jogo e escrever um pequeno programa que diz exatamente o que fazer. É como se a IA fosse um engenheiro que projeta o melhor motor para o carro, em vez de apenas ser um piloto que tenta acelerar até o motor fundir.

Resumo em uma frase: A IA aprendeu a criar seu próprio "GPS" a partir de mapas imperfeitos, conseguindo navegar por armadilhas mortais onde todos os outros métodos se perderam.

Resumo técnico

Título: Modelos de Mundo em Código para Controle de Parâmetros em Algoritmos Evolutivos

1. O Problema

O controle adaptativo de parâmetros é um desafio fundamental na computação evolutiva. Especificamente, para o algoritmo (1+1)-RLS$_k$ (que inverte exatamente $k$ bits por passo), a questão central é: qual valor de $k$ deve ser utilizado em cada etapa da busca?

• Em paisagens simples (unimodais), como LeadingOnes e OneMax, políticas ótimas são conhecidas, mas em paisagens complexas e enganosas (como Jump$_k$ e NK-Landscape), não existem regras adaptativas fechadas que garantam o sucesso.
• Abordagens existentes (como regras de multiplicação adaptativa ou self-adjusting) tendem a falhar em paisagens enganosas: quando o algoritmo estagna (não há melhoria), essas regras reduzem $k$, o que é contraproducente em vales enganosos onde é necessário um salto grande (aumentar $k$) para escapar.

2. Metodologia: Modelos de Mundo em Código (CWMs)

Os autores estendem o conceito de Code World Models (CWMs) — originalmente desenvolvido para jogos determinísticos — para a otimização combinatória estocástica. A abordagem não usa redes neurais como modelos de mundo, mas sim programas Python sintetizados por um LLM (Large Language Model).

O pipeline funciona em três etapas:

1. Coleta de Trajetórias: O algoritmo (1+1)-RLS$_k$ é executado com diversas políticas de coleta (aleatórias, fixas, decrescentes) para gerar 200-300 trajetórias de otimização. Crucialmente: Nenhuma política de coleta usa conhecimento oráculo (como o valor ótimo de $k$ ou o tamanho do "vazio" em Jump$_k$).
2. Síntese do CWM pelo LLM: Um LLM (Claude Sonnet 4) recebe uma descrição do problema e amostras das trajetórias (transições de estado). O LLM sintetiza uma classe Python (SynthesizedCWM) que atua como um simulador do ambiente.
   • O modelo deve prever a próxima estado e avaliar o valor esperado de diferentes ações ($k$).
   • Para problemas complexos (Jump$_k$, NK), o prompt é enriquecido com tabelas de transição empíricas (probabilidade de melhoria e ganho médio de fitness para cada faixa de fitness e $k$), substituindo a necessidade de um modelo matemático fechado.
3. Planejamento Ganancioso (Greedy Planning): Durante a execução online, em cada passo, o planejador consulta o CWM sintetizado para escolher o $k^*$ que maximiza a melhoria esperada em um único passo de olhar para frente (one-step lookahead). Não é necessário usar MCTS (Monte Carlo Tree Search), pois o ambiente é essencialmente markoviano com horizonte curto.

3. Principais Contribuições

1. Extensão para Otimização Estocástica: Adaptação dos CWMs de jogos determinísticos para otimização combinatória estocástica, demonstrando que o planejamento ganancioso é suficiente (eliminando a sobrecarga do MCTS).
2. Desempenho em Paisagens Enganosas: No benchmark Jump$_k$, onde todas as bases adaptativas falham (0% de sucesso), o CWM-greedy atinge 100% de taxa de sucesso, sem nunca ter visto trajetórias ótimas ou o parâmetro do vazio ($k_{jump}$) durante o treinamento.
3. Substituição de Modelos Fechados: No NK-Landscape (onde não existe modelo matemático fechado), o uso de estatísticas de transição empíricas no prompt permite que o CWM supere todas as bases, demonstrando que resumos estruturados de dados podem substituir modelos analíticos.
4. Eficiência de Amostra e Generalização: O CWM supera o DQN (Deep Q-Network) em eficiência de amostra (200 trajetórias offline vs. 500 episódios online), taxa de sucesso e capacidade de generalização para valores de $k$ não vistos durante o treinamento.

4. Resultados Experimentais

Os experimentos foram realizados com $n=50$ (e testes de generalização até $n=200$) em quatro benchmarks:

• LeadingOnes e OneMax (Paisagens Unimodais):

  • O CWM-greedy opera dentro de 6% da política ótima teórica em LeadingOnes e 2% em OneMax.
  • Supera significativamente todas as bases adaptativas (p < 0.0001).
  • O LLM consegue inferir a política correta (rampa suave ou "cliff" abrupto) apenas a partir da estrutura do problema e trajetórias subótimas.

• Jump$_k$ (Paisagem Enganosa):

  • Resultado Chave: O CWM atinge 100% de sucesso, enquanto todas as bases adaptativas (EA$\alpha$, self-adjusting) falham completamente (0% de sucesso) porque reduzem $k$ durante a estagnação no vale.
  • O CWM aprende a aumentar $k$ especificamente na borda do vale para realizar o salto necessário.
  • Comparação com DQN: O DQN atinge apenas 58% de sucesso e sofre de overfitting ao ruído de exploração ($\epsilon$-greedy), falhando ao avaliar de forma gananciosa. O CWM, ao codificar a estrutura do problema em código, é imune a essa falha.

• NK-Landscape (Sem Modelo Matemático):

  • O CWM supera todas as bases (incluindo heurísticas estáticas e adaptativas) em 15 instâncias independentes (36.94 vs 36.32 de fitness médio).
  • A generalização para $K=3$ e $K=4$ (sem re-síntese) também foi bem-sucedida.

• Generalização para $k$ não vistos:

  • Treinado em Jump$_k$ com $k=2$, o CWM generaliza para $k=3$ com 78% de sucesso, enquanto o DQN e as bases adaptativas caem para 0%. Isso ocorre porque o CWM codifica o modelo probabilístico (hipergeométrico) e não apenas uma tabela de lookup.

5. Significado e Conclusão

O artigo demonstra que Modelos de Mundo em Código oferecem uma ponte poderosa entre a inteligência artificial generativa e a teoria de algoritmos evolutivos:

• Interpretabilidade: Ao invés de pesos de rede neural opacos, o LLM gera código Python auditable que encapsula a lógica de controle.
• Complemento à Teoria: O método não substitui a análise formal, mas complementa-a, permitindo o planejamento analítico mesmo em paisagens onde modelos fechados não existem.
• Eficiência: É extremamente eficiente em termos de dados, superando métodos de Aprendizado por Reforço (RL) tradicionais que exigem milhares de episódios online.
• Robustez: A síntese é estável em múltiplas execuções independentes, capturando comportamentos críticos (como a travessia de vales) de forma consistente.

Em suma, o trabalho prova que um LLM, guiado por trajetórias subótimas e estatísticas empíricas, pode "descobrir" e codificar políticas de controle de parâmetros ótimas ou próximas do ótimo, superando as limitações das regras adaptativas clássicas em problemas complexos e enganosos.