On the Structural (Dis)Agreement of Landscape Representations in Black-Box Optimization

Resumo Técnico: (Des)Acordo Estrutural de Representações de Paisagem em Otimização de Caixa-Preta

Declaração do Problema
A Seleção Automática de Algoritmos (AAS) para otimização de caixa-preta depende fortemente de representações de características de paisagem para mapear instâncias de problemas para o desempenho do algoritmo. Embora existam várias representações — variando de características tradicionais de Análise de Paisagem Exploratória (ELA) a embeddings baseados em aprendizado profundo (por exemplo, DoE2Vec, DeepELA, TransOptAS) —, há um entendimento limitado sobre como essas diferentes representações concordam ou discordam quanto à organização estrutural dos espaços de problemas. A pesquisa atual enfrenta dois desafios principais: a falta de conjuntos de dados de referência suficientemente diversos para testar a generalização e a incerteza sobre se as representações existentes capturam informações complementares ou redundantes sobre as propriedades subjacentes da paisagem. Especificamente, permanece incerto se diferentes representações organizam o mesmo conjunto de problemas de maneiras consistentes ou se enfatizam propriedades geométricas versus semânticas distintas.

Metodologia
Os autores propõem um pipeline de avaliação sistemática e não supervisionada para analisar a consistência estrutural e a complementaridade de quatro representações de paisagem de última geração:

1. ELA: Características estatísticas de baixo nível tradicionais (62 características por instância).
2. DoE2Vec: Um autoencoder variacional que produz vetores latentes de 32 dimensões.
3. TransOptAS: Um codificador baseado em transformer que produz embeddings de 50 dimensões treinados para prever o desempenho do algoritmo.
4. DeepELA: Um transformer auto-supervisionado que produz características de 48 dimensões invariantes a transformações de função.

Geração de Dados:
Para garantir diversidade além dos benchmarks padrão, o estudo utiliza a suíte MA-BBOB. Este conjunto de dados consiste em 8.280 instâncias de problemas transformadas geradas por meio de combinações afins de 552 pares de classes distintas de problemas BBOB. Cada combinação é avaliada usando uma Amostragem de Hipercubo Latino de tamanho $50d$ com dimensão $d=10$.

Procedimento Experimental:

1. Agrupamento (Clustering): Para cada representação, os autores realizaram uma extensa busca em grade sobre cinco algoritmos de agrupamento (Aglomerativo, K-Means, Espectral, Misto Gaussiano, BIRCH) e hiperparâmetros (contagens de clusters $k \in [5, 500]$). A configuração ótima para cada representação foi selecionada com base na Pontuação Silhueta.
2. Análise Dentro da Representação: Os autores construíram matrizes de cobertura para rastrear como as instâncias de problemas se distribuem entre os clusters. Eles avaliaram essas estruturas usando Homogeneidade (H), Completude (C) e Medida-V (V) para avaliar o quão bem os clusters se alinham com as classes de problemas verdadeiras (ground-truth).
3. Análise Entre Representações: Para comparar representações, os autores derivaram descrições baseadas em vetores dos clusters (onde cada entrada do vetor representa a frequência de um problema específico em um cluster) e calcularam a similaridade cosseno entre clusters de diferentes representações. O agrupamento hierárquico foi aplicado a essas pontuações de similaridade para identificar alinhamentos estruturais.
4. Alinhamento de Desempenho: Finalmente, o estudo analisou a relação entre clusters no espaço de características e o desempenho do algoritmo. Usando portfólios de variantes de Evolução Diferencial (DE) e Otimização por Enxame de Partículas (PSO), os autores mediram o quão consistentemente a configuração de algoritmo de melhor desempenho foi selecionada dentro dos clusters definidos por cada representação.

Principais Resultados
O estudo revela que nenhuma representação única domina; em vez disso, cada uma organiza o espaço de problemas de maneira fundamentalmente diferente, capturando aspectos complementares da paisagem:

• Coesão Geométrica (ELA e TransOptAS): Essas representações formam estruturas geométricas compactas e bem separadas. A ELA alcançou a maior Pontuação Silhueta (0,3505), seguida pela TransOptAS (0,2670). No entanto, ambas exibiram baixa Homogeneidade, o que significa que, embora os clusters sejam geometricamente compactos, eles frequentemente contêm tipos de problemas mistos.
• Fidelidade Semântica vs. Fragmentação (DoE2Vec): O DoE2Vec alcançou a maior Homogeneidade (0,5612) e Medida-V (0,5882), indicando forte alinhamento com a semântica real do problema. No entanto, produziu uma paisagem altamente fragmentada com um grande número de clusters (355) e a menor Pontuação Silhueta (0,1722), sugerindo supersegmentação do espaço de características.
• Visão Equilibrada (DeepELA): A DeepELA forneceu uma visão intermediária, equilibrando a separação geométrica e a consistência semântica, embora tenha mostrado similaridade moderada com outras representações.
• Desacordo Estrutural: Mapas de calor de similaridade entre representações mostraram que, enquanto a TransOptAS se alinha estreitamente com a ELA, o DoE2Vec diverge significativamente devido ao seu agrupamento de alta granularidade. As quatro representações organizam os mesmos problemas de maneiras marcadamente diferentes.
• Compensação de Desempenho: Ao analisar o desempenho do algoritmo (DE e PSO), surgiu uma compensação. O DoE2Vec mostrou a maior homogeneidade na seleção de desempenho (problemas no mesmo cluster tendem a compartilhar o melhor algoritmo), mas baixa completude (algoritmos semelhantes foram selecionados em clusters diferentes). Por outro lado, a TransOptAS mostrou alta completude (agrupando problemas de desempenho semelhantes) mas menor pureza. Nenhuma representação única capturou totalmente o comportamento de desempenho do algoritmo.

Significado e Contribuições
A principal contribuição do artigo é a demonstração de que as representações de paisagem não são intercambiáveis; elas impõem visões estruturais distintas sobre o mesmo espaço de problemas.

• Complementaridade: As descobertas destacam que ELA/TransOptAS favorecem a coesão geométrica, enquanto o DoE2Vec prioriza a pureza semântica. Isso sugere que análises de múltiplas visões são essenciais para construir sistemas robustos de meta-aprendizado, pois confiar em uma única representação pode ignorar aspectos críticos da paisagem do problema.
• Orientação para Seleção: Os resultados oferecem orientação para tarefas subsequentes: se o objetivo é agrupar problemas com comportamento algorítmico semelhante, representações com alta completude (como a TransOptAS) podem ser preferíveis, enquanto aquelas com alta homogeneidade (como o DoE2Vec) podem isolar melhor tipos específicos de problemas.
• Limitações: Os autores observam que o estudo está limitado a uma única suíte de benchmarks (MA-BBOB) e famílias específicas de algoritmos (DE e PSO). No entanto, o framework empírico proposto foi projetado para ser extensível a outros benchmarks e domínios de otimização.

Em conclusão, o estudo argumenta contra a existência de uma representação de paisagem "universal". Em vez disso, defende a integração de múltiplas representações para aproveitar suas forças complementares na seleção automática de algoritmos e no meta-aprendizado.