Evaluating Real-World Generalizability of Algorithm Selection Models

Resumo Técnico: Avaliando a Generalização no Mundo Real de Modelos de Seleção de Algoritmos

Definição do Problema
A Seleção de Algoritmos (SA) visa identificar automaticamente o algoritmo de otimização mais adequado para uma instância de problema específica, aproveitando características mensuráveis do problema (características de paisagem) e dados de desempenho histórico. Embora os modelos de SA tenham sido extensivamente desenvolvidos e avaliados em suítes de benchmarks sintéticos controlados (como BBOB e CEC), sua capacidade de generalização para paisagens de otimização do mundo real permanece amplamente não verificada. A literatura existente sugere que os benchmarks sintéticos frequentemente carecem da complexidade estrutural, padrões de ruído e restrições específicas de domínio inerentes aos problemas práticos. Consequentemente, modelos treinados em dados sintéticos podem sofrer overfitting em distribuições de paisagem específicas e falhar quando aplicados a tarefas reais e específicas de domínio. Este estudo aborda a lacuna crítica na compreensão de quão bem os modelos de SA transferem entre benchmarks sintéticos acadêmicos e conjuntos de problemas do mundo real.

Metodologia
O estudo emprega um framework de avaliação sistemática de cross-benchmark envolvendo quatro fontes de problemas distintas:

1. Benchmarks Sintéticos: A suíte Black-Box Optimization Benchmarking (BBOB) e a série de benchmarks de parâmetros reais de objetivo único da IEEE CEC.
2. Benchmarks do Mundo Real: Um conjunto de problemas de otimização de trajetória de robótica (ROB) e problemas de planejamento de trajetória de Veículos Aéreos Não Tripulados (UAV).

A configuração experimental inclui um portfólio de algoritmos de oito métodos de otimização de objetivo único baseados em população (incluindo AGSK, DE, PSO, LSHADE e outros). Os autores avaliam o desempenho através das dimensões 6, 12, 18, 24 e 30.

Extração de Características e Pré-processamento:
O estudo utiliza características de Análise de Paisagem Exploratória (ELA) derivadas do pacote flacco (62 características por instância). Para investigar o impacto da representação de dados na generalização, os autores testam várias estratégias de pré-processamento:

• Escalonamento: Nenhum, escala de y (apenas função objetivo) e escala de x-y (variáveis de decisão e função objetivo).
• Amostragem: Amostra total (10.000 pontos) versus amostragem reduzida (50d pontos).

Modelagem e Avaliação:
Um regressor Random Forest (RF) é treinado para prever o escore de precisão normalizado de cada algoritmo para uma determinada instância de problema. O desempenho da SA é medido pela diferença entre o escore do melhor algoritmo previsto e o escore do verdadeiro melhor algoritmo, comparado contra um baseline "dummy" que prevê o desempenho médio do melhor solver observado no conjunto de treinamento. A avaliação segue um protocolo rigoroso de cross-benchmark: modelos são treinados em um benchmark e testados nos quatro, bem como em um cenário de benchmark mesclado. Adicionalmente, um teste de crossmatch é empregado para quantificar a similaridade estatística das distribuições de características ELA entre pares de benchmarks.

Principais Resultados

• Generalização Limitada: Na maioria dos cenários de cross-benchmark, particularmente em dimensões baixas (6d), modelos de SA treinados em benchmarks sintéticos (BBOB/CEC) falham em superar o baseline dummy quando testados em problemas do mundo real (ROB/UAV), e vice-versa.
• Efeitos da Dimensionalidade: Embora alguma transferência positiva esporádica tenha sido observada (ex: CEC para UAV sem escalonamento em 6d, ou CEC para UAV em 12d), a generalização permaneceu inconsistente. Em dimensões mais altas (24d, 30d), as melhorias sobre o baseline foram modestas (0.1–0.2) e altamente dependentes de pares específicos de origem-destino e escolhas de pré-processamento.
• O Fenômeno de Overfitting do "Único Melhor Solver": A análise das frequências de predição revelou uma causa significativa para a má generalização. Quando um benchmark de treinamento é dominado por um único algoritmo de melhor desempenho (ex: EBOwithCMAR no BBOB ou APGSK_IMODE no UAV), o modelo de SA tende a sofrer overfitting ao prever consistentemente esse mesmo algoritmo. Esse comportamento mimetiza efetivamente o baseline dummy, resultando em nenhum ganho mensurável na precisão de seleção.
• Disparidade no Espaço de Características: As estatísticas do teste de crossmatch confirmaram que os benchmarks sintéticos e do mundo real ocupam regiões amplamente distintas no espaço de características ELA. Embora o BBOB e o CEC apresentem sobreposição substancial, os benchmarks envolvendo problemas de robótica e UAV exibiram similaridade mínima com as suítes sintéticas, especialmente em dimensões mais altas. Etapas de pré-processamento como escalonamento e redução de amostragem aumentaram a sobreposição no espaço de características, mas não se traduziram consistentemente em melhoria no desempenho da SA.

Significância e Alegações
O artigo alega que um forte desempenho em benchmarks sintéticos padrão não garante robustez ou transferibilidade para problemas de otimização do mundo real. O estudo destaca que as diferenças estruturais entre paisagens sintéticas e do mundo real limitam fundamentalmente a generalização entre benchmarks.

Os autores concluem que as abordagens atuais de SA são frequentemente insuficientes para implantação prática sem abordar o deslocamento de distribuição (distributional shift) entre os domínios de treinamento e alvo. Eles sugerem que o desenvolvimento futuro deve migrar para:

1. Enriquecer coleções de benchmarks com instâncias de problemas diversos e realistas.
2. Desenvolver representações de características que capturem melhor as características transferíveis dos problemas.
3. Projetar modelos de SA explicitamente voltados para a generalização entre domínios, em vez de otimizar apenas para o desempenho em um benchmark específico.

O trabalho ressalta a necessidade de ir além dos ambientes sintéticos controlados para avaliar e desenvolver sistemas de SA capazes de lidar com a heterogeneidade e a complexidade das tarefas de otimização do mundo real.