Beyond Numerical Features: CNN-Driven Algorithm Selection via Contour Plots for Continuous Black-Box Optimization

Resumo Técnico: Seleção de Algoritmos Impulsionada por CNNs via Gráficos de Contorno

Declaração do Problema
A otimização de caixa-preta contínua (BBO) envolve a minimização ou maximização de funções objetivo onde informações de gradiente estão indisponíveis, dependendo exclusivamente de avaliações da função. Embora solvers livres de derivadas (por exemplo, variantes do CMA-ES) apresentem bom desempenho, o teorema do No Free Lunch dita que nenhum algoritmo único supera universalmente os outros em todas as instâncias de problemas. Consequentemente, a Seleção Automatizada de Algoritmos (AAS) visa escolher o solver mais adequado de um portfólio fixo para uma instância de problema específica.

As abordagens AAS existentes em BBO contínua dependem predominantemente de Análise Exploratória de Paisagens (ELA), que constrói vetores de características numéricas (por exemplo, curvatura, separabilidade) a partir de avaliações sondadas, ou de Deep-ELA, que utiliza embeddings aprendidos a partir de transformers pré-treinados. Os autores argumentam que esses descritores numéricos podem falhar em capturar a estrutura espacial evidente em paisagens visualizadas. Embora AAS baseada em CNNs tenha sido explorada em domínios discretos com codificações diretas de instâncias, sua aplicação em BBO contínua — onde as representações devem ser construídas via sondagem — é pouco explorada.

Metodologia
O artigo propõe uma abordagem AAS orientada a representação que trata paisagens sondadas como imagens em vez de vetores numéricos.

1. Representação da Instância (Gráficos de Contorno):

   • Objetivo Único (SOO): Cada instância de problema é renderizada como um mapa de contorno em tons de cinza 2D, avaliando a função objetivo em uma grade fixa de $300 \times 300$. Para dimensões $d > 2$, um corte 2D é criado selecionando aleatoriamente duas coordenadas para abranger um subespaço, enquanto as demais são fixadas em zero (aproveitando o domínio simétrico do BBOB).
   • Objetivo Múltiplo (MOO): Para problemas bi-objetivo ($d=2, m=2$), utiliza-se uma estratégia de amostragem de sub-contorno. Cinco janelas retangulares alinhadas aos eixos são amostradas dentro do domínio para cada objetivo, gerando múltiplas visualizações para reduzir a dependência de uma única renderização global.
   • Variantes de Entrada: Para estudar a fidelidade da entrada, os gráficos são redimensionados para resoluções $r \in \{64, 128, 300\}$.

2. Arquiteturas CNN:
   Duas variantes de modelo são propostas para prever o desempenho relativo (Tempo de Execução Esperado para SOO, Hipervolume relativo para MOO) dos algoritmos em um portfólio:

   • Modelo Combinado: As cinco visualizações específicas da instância (ou amostras de janela) são empilhadas ao longo da dimensão do canal e alimentadas diretamente em um codificador CNN.
   • Modelo Separado: Cada visualização é processada individualmente por um codificador de pesos compartilhados, e os vetores de características resultantes são concatenados antes de serem passados para uma cabeça de regressão.
   • Arquitetura SOO: Um codificador CNN de três camadas.
   • Arquitetura MOO: Um codificador ResNet-18 devido a demandas representacionais mais altas.

3. Mecanismo de Seleção:
   O modelo prevê a métrica de desempenho (por exemplo, ERT relativo) para cada algoritmo no portfólio. O solver com o melhor valor previsto (ERT mínimo ou HV máximo) é selecionado.

Principais Contribuições

1. Representação de Imagem Baseada em Sondagem: Os autores introduzem uma formulação AAS inovadora para BBO contínua que utiliza renderizações de mapas de contorno de paisagens sondadas como representações de instância, eliminando a necessidade de características ELA artesanais.
2. Avaliação Empírica: O estudo fornece uma análise abrangente em benchmarks padrão BBOB 2009 de objetivo único e em uma configuração bi-objetivo seguindo o protocolo Deep-ELA. Analisa os efeitos da agregação de visualizações (Combinado vs. Separado) e da resolução de entrada.
3. Benchmarking de Desempenho: O trabalho posiciona a seleção baseada em contorno contra baselines estabelecidas baseadas em características (ELA com MLP/RF e variantes Deep-ELA).

Resultados Experimentais

• Otimização de Objetivo Único (SOO):
  • No benchmark BBOB 2009 (96 configurações), a CNN Combinada com resolução de entrada $300 \times 300$ superou significativamente o Melhor Solver Único (SBS), reduzindo o ERT relativo médio de 30,37 (SBS) para 5,60.
  • A abordagem CNN foi competitiva com as baselines baseadas em características mais fortes (ELA-MLP: 5,72; Deep-ELA Medium-kNN: 6,04).
  • O desempenho geralmente melhorou com maior resolução de entrada ($r=300$), embora isso tenha aumentado os custos de treinamento.
  • O método mostrou ganhos fortes nos grupos de funções F1–F19, enquanto o desempenho no grupo mais difícil (F20–F24) permaneceu misto em comparação com métodos baseados em características.
• Otimização de Objetivo Múltiplo (MOO):
  • Sob a configuração de avaliação Deep-ELA, os seletores baseados em CNN foram competitivos com as baselines Deep-ELA.
  • A CNN Separada alcançou as melhores pontuações médias de HV relativas (0,971–0,974), superando as variantes Deep-ELA (0,904).
  • O método foi particularmente eficaz nas instâncias ZDT (atingindo pontuações quase perfeitas), enquanto os resultados em DTLZ e MMF foram fortes, mas ligeiramente abaixo das melhores configurações Deep-ELA.

Significado e Alegações
O artigo afirma que modelos de visão simples podem explorar a estrutura espacial de paisagens sondadas para seleção de algoritmos sem depender de características ELA artesanais. Os resultados sugerem que visualizações de gráficos de contorno contêm sinal suficiente para impulsionar uma AAS eficaz em BBO contínua, oferecendo uma representação complementar aos descritores numéricos.

Limitações e Escopo
Os autores observam explicitamente várias limitações:

• Orçamento de Sondagem: A abordagem atual requer um orçamento de sondagem substancial (cinco mapas $300 \times 300$ por configuração), tornando-a adequada para análise offline, mas não para implantação online estrita de baixo orçamento.
• Representação de Alta Dimensão: Para $d > 2$, a representação de corte 2D é uma visão parcial da paisagem, o que pode contribuir para um desempenho mais fraco nos grupos de funções mais difíceis.
• Protocolos Fixos: A avaliação está vinculada a portfólios e protocolos específicos (incluindo amostragem de janelas para MOO), e o estudo de MOO é limitado a $d=2, m=2$.

O trabalho é apresentado como uma prova de conceito demonstrando a viabilidade de representações baseadas em imagens, com direções futuras apontando para sondagem sensível a custos, designs de múltiplas visualizações e características híbridas visuais-numéricas.