GeM-EA: A Generative and Meta-learning Enhanced Evolutionary Algorithm for Streaming Data-Driven Optimization

Resumo Técnico: GeM-EA

1. O Problema: Otimização Orientada a Dados em Fluxo (SDDO)

O artigo aborda problemas de Otimização Orientada a Dados em Fluxo (SDDO - Streaming Data-Driven Optimization), comuns em aplicações como gestão de cidades inteligentes e sistemas de transporte. Nestes cenários, os dados chegam continuamente e o ambiente de otimização evolui ao longo do tempo devido ao desvio de conceito (concept drift).

• Desafios Principais:
  • Não-estacionariedade: A paisagem de otimização muda dinamicamente, tornando modelos antigos obsoletos rapidamente.
  • Transferência Negativa: Métodos existentes que reutilizam conhecimento histórico (soluções passadas) frequentemente falham quando ocorrem mudanças bruscas no ambiente. A combinação linear de surrogates (modelos substitutos) ou a injeção direta de soluções antigas pode introduzir viés, desviando a busca de soluções ótimas atuais.
  • Limitações do Meta-Aprendizado Tradicional: Abordagens atuais de meta-aprendizado exigem amostragem ativa de dados (proibida em SDDO) ou assumem distribuições estacionárias, o que conflita com a natureza contínua e imprevisível dos fluxos de dados.

2. Metodologia: GeM-EA

Os autores propõem o GeM-EA, um Algoritmo Evolutivo Aprimorado por Geração e Meta-Aprendizado. A arquitetura unifica a adaptação de surrogates via meta-aprendizado com uma busca evolutiva baseada em replay generativo.

O framework é composto por dois módulos principais:

A. Adaptação de Surrogate Meta-Aprendida (Bi-level)
Utiliza uma Rede de Funções de Base Radial (RBFN) onde os parâmetros são separados em estruturais ($\theta$) e não-estruturais ($w, \sigma$). Para evitar instabilidades de gradiente ao otimizar tudo junto, o método emprega uma estratégia de dois níveis:

1. Identificação de Priori Relevante: Seleciona apenas ambientes históricos altamente relevantes ao atual para construir um conjunto de dados meta ($S_{meta}$), evitando transferência negativa.
2. Adaptação Rápida de Dois Níveis:
   • Nível Estrutural: Os parâmetros topológicos ($\theta$) são atualizados via descida de gradiente para capturar mudanças geométricas complexas.
   • Nível Analítico: As larguras ($\sigma$) e pesos ($w$) são resolvidos analiticamente (Regressão Ridge) ou via heurísticas de vizinhos mais próximos. Isso desacopla a otimização complexa da adaptação rápida, garantindo estabilidade.
3. Estabilização por Resíduo Linear: Adiciona um componente linear residual ($\mathbf{a}^T\mathbf{x} + b$) ao modelo meta-aprendido para capturar tendências globais e corrigir erros de aproximação em dados limitados.

B. Busca Evolutiva Baseada em Replay Generativo (Multi-Ilha)
Para mitigar o risco de ficar preso em ótimos locais ou ser enganado por dados históricos, o algoritmo utiliza uma arquitetura de múltiplas ilhas:

• Ilha de Meta-Adaptação: Explora agressivamente o ambiente atual guiada pelo surrogate meta-aprendido.
• Ilhas de Âncora Histórica: Geradas a partir de resumos estatísticos dos ambientes passados mais similares. Elas atuam como âncoras de estabilidade, acelerando a exploração de regiões promissoras conhecidas.
• Migração Guiada por Confiança: Um mecanismo coordenado permite a troca de soluções entre as ilhas. Soluções históricas migram para a ilha atual, mas soluções da ilha atual só migram para as ilhas históricas se houver uma confiança estatística de que são superiores, prevenindo a contaminação de modelos antigos com dados novos e potencialmente enganosos.

3. Contribuições Principais

1. Framework Unificado: Integra adaptação de surrogate via meta-aprendizado com busca evolutiva baseada em replay generativo, permitindo adaptação rápida sem aquisição ativa de dados.
2. Mecanismo de Adaptação Bi-level: Decopla a adaptação estrutural da adaptação de pesos, resolvendo conflitos de gradiente e garantindo estabilidade em fluxos de dados contínuos.
3. Arquitetura Multi-Ilha Robusta: Utiliza ilhas de âncora histórica e um mecanismo de migração seletivo para equilibrar exploração e exploração, mitigando efetivamente a transferência negativa.
4. Eficiência Computacional: O método mantém complexidade computacional linear $O(N)$ devido às soluções analíticas para os pesos, sendo significativamente mais rápido que métodos baseados em Programação Genética (GP).

4. Resultados Experimentais

O GeM-EA foi avaliado no benchmark SDDObench e comparado com o estado da arte (incluindo TT-DDEA, BDDEA-LDG, MLO, DETO, entre outros).

• Qualidade da Solução: O GeM-EA obteve a melhor classificação média (1.22) em todas as métricas. Em paisagens multimodais complexas (ex: F5-D3), reduziu o erro offline em uma ordem de magnitude em comparação com o segundo melhor método (MLO).
• Comportamento Dinâmico: Após um desvio de conceito, o algoritmo exibe uma convergência "tipo penhasco" (cliff-like), recuperando-se quase verticalmente para um erro baixo, demonstrando alta capacidade de adaptação.
• Eficiência: O tempo de execução é comparável aos baselines mais rápidos e muito superior a métodos baseados em GP, graças à resolução analítica dos parâmetros.
• Significância Estatística: Testes de Kruskal-Wallis e Dunnett confirmaram que o desempenho superior do GeM-EA é estatisticamente significativo na maioria dos casos de teste.

5. Significância e Conclusão

O GeM-EA representa um avanço significativo na otimização orientada a dados em fluxos contínuos. Ao superar as limitações de reutilização rígida de conhecimento e instabilidade de gradientes em meta-aprendizado, o método oferece uma solução robusta para ambientes dinâmicos e imprevisíveis.

A principal contribuição teórica é a demonstração de que é possível realizar meta-aprendizado eficaz sem amostragem ativa, desacoplando a adaptação estrutural da analítica. Isso torna o algoritmo viável para aplicações do mundo real onde o custo de avaliação da função objetivo é alto e os dados são estritamente sequenciais. O código-fonte foi disponibilizado publicamente, facilitando a reprodutibilidade e o avanço futuro na área.