Resumo Técnico: MO-ELA

Definição do Problema

A Seleção Automática de Algoritmos (AAS) é um campo maduro para otimização de objetivo único (SO), onde modelos de aprendizado de máquina predizem o algoritmo de melhor desempenho para uma instância de problema específica com base em características de "análise de paisagem exploratória" (ELA). No entanto, no domínio da otimização multi-objetivo (MO) contínua, o panorama de características disponíveis é escasso. As abordagens existentes frequentemente dependem do cálculo de características SO para cada objetivo individualmente, o que falha em capturar interações complexas entre objetivos, ou em características MO restritas que não são diretamente aplicáveis a problemas contínuos não restritos (com restrições de caixa). Há uma necessidade de um conjunto de características rigoroso e complementar, projetado especificamente para caracterizar a paisagem de problemas de otimização multi-objetiva contínua com restrições de caixa (MOPs) para melhorar o desempenho da AAS.

Metodologia

Os autores propõem o MO-ELA, um novo conjunto de 226 características para problemas bi-objetivo e 233 características para problemas tri-objetivo. Essas características são derivadas de uma amostra aleatória de pontos tanto no espaço de decisão quanto no espaço de objetivos, utilizando relações de dominância e várias análises estruturais. As características são categorizadas em cinco grupos distintos:

1. Características Baseadas em Ordenação Não-Dominada (NDS):

   • Utiliza o procedimento de ordenação não-dominada (inspirado no NSGA-II) para particionar a amostra em camadas ($L_1, L_2, \dots$).
   • Calcula métricas como o número de pontos não-dominados, o número de camadas e a média de pontos por camada.
   • Computa medidas de Hipervolume (HV) e Solow-Polasky (SP) para as primeiras cinco camadas.
   • Ajusta regressões polinomiais (graus 1–4) aos valores de HV através das camadas para capturar a não-linearidade da distribuição da fronteira de Pareto, usando $R^2$ como uma característica.

2. Estatísticas Descritivas de Pontos Não-Dominados:

   • Aplica medidas estatísticas (mínimo, máximo, média, desvio padrão) aos vetores de objetivos da primeira camada não-dominada ($L_1$).
   • Inclui correlações de Spearman pareadas entre objetivos e a diferença absoluta nos desvios padrões para casos bi-objetivo.

3. Características Baseadas em PCA:

   • Realiza a Análise de Componentes Principais (PCA) em três conjuntos: os pontos do espaço de decisão ($X$), os pontos do espaço de objetivos ($Y$) e o conjunto concatenado ($XY$) da camada não-dominada.
   • Extrai o mínimo, o máximo e a média da variância explicada dos componentes principais desses conjuntos.

4. Características Baseadas em Grafos:

   • Constrói grafos baseados na camada não-dominada $L_1$ tanto nos espaços de decisão quanto de objetivos.
   • Grafos MST e kNN: Constrói Árvores Geradoras Mínimas (MST) e grafos de k-Vizinhos Mais Próximos (kNN) ($k=1$) no espaço de decisão ($G_D$) e no espaço de objetivos ($G_O$).
   • Transferência de Arestas: Transfere a estrutura de arestas de um grafo para o outro (ex: arestas da MST do espaço de decisão aplicadas aos pontos de objetivo, denotado como $G_{D \to O}$).
   • Métricas: Calcula pesos de arestas (distâncias), centralidade de proximidade de nós, ângulos entre nós conectados e propriedades de componentes conectados (número de componentes, nós por componente, caminho mais longo).
   • Inclui razões de características entre os grafos dos espaços de decisão e de objetivos para capturar a distorção entre os espaços.

5. Características Baseadas em Gradiente:

   • Computa inclinações absolutas por variável entre nós conectados na MST do espaço de objetivos ($G^O_{ST}$).
   • Agrega essas inclinações através de todos os objetivos e arestas para formar um vetor de gradiente multi-objetivo, do qual os valores de mínimo, máximo, desvio padrão e média são extraídos.

Configuração Experimental:

• Benchmarks: Um conjunto abrangente de 1.165 instâncias de problemas derivados de BiObjBBOB, ZDT, DTLZ e MPM2, cobrindo 2 e 3 objetivos e dimensões $d \in \{2, 5, 10, 20\}$.
• Algoritmos: Três solvers (NSGA-II, SMS-EMOA, MOEA/D) foram executados 20 vezes por instância.
• Framework de AAS: Modelos de aprendizado de máquina (SVM, XGBoost, Random Forest) foram treinados para prever o melhor solver. A seleção de características foi realizada por meio de uma busca exaustiva de ida e volta (forward-backward) para identificar o subconjunto mais influente.
• Métricas: O desempenho foi avaliado usando o Hipervolume Normalizado (HVN) e a Melhoria Relativa (RI) no fechamento da lacuna entre o Único Melhor Solver (SBS) e o Melhor Solver Virtual (VBS).

Principais Resultados

• Desempenho da Seleção de Algoritmos: As características propostas melhoraram significamente o desempenho da AAS. Para problemas bi-objetivo, o melhor seletor (XGBoost com seleção de características) alcançou uma RI de 0,963, fechando efetivamente a lacuna para o VBS. Para problemas tri-objetivo, uma RI de 0,272 foi alcançada.
• Contribuição das Características: Após a seleção de características, as novas características propostas pelo MO-ELA foram frequentemente as principais contribuintes.
  • Para problemas bi-objetivo, 14 das 32 características selecionadas eram novas (dominadas por características de NDS).
  • Para problemas tri-objetivo, 17 das 36 características selecionadas eram novas (dominadas por características de grafo kNN).
• Estabilidade das Características: As características demonstraram alta estabilidade entre diferentes amostras aleatórias e tamanhos de amostra, com correlações pareadas médias de ~0,8 para todas as características e quase 1,0 para o subconjunto selecionado.
• Expressividade das Características: As características selecionadas mostraram baixa correlação mútua (média de ~0,30 para bi, ~0,23 para tri), indicando que capturam aspectos distintos da paisagem do problema.
• Sensibilidade ao Tamanho da Amostra: Um tamanho de amostra de 500 gerou os melhores resultados para as dimensões 5, 10 e 20. Para a dimensão 2, um tamanho de amostra de 200 foi o ideal. Notavelmente, tamanhos de amostra maiores melhoraram o desempenho mesmo quando o orçamento restante para execuções do solver foi reduzido, sugerindo que a expressividade das características é crítica.

Significância e Alegações

O artigo afirma que o MO-EDA fornece uma expansão rigorosa das características de paisagem exploratória para otimização multi-objetiva contínua. Sua principal significância reside em:

1. Preencher a Lacuna: Ele aborda a escassez de características para problemas MO ao introduzir um conjunto abrangente que captura interações entre objetivos e a geometria de ambos os espaços de decisão e de objetivos.
2. Utilidade Comprovada: As características não são meramente teóricas; elas permitem empiricamente que modelos de aprendizado de máquina distingam entre instâncias de problemas e selecionem algoritmos com precisão quase ótima (aproximando-se do VBS para casos bi-objetivo).
3. Complementaridade: As novas características complementam as características MO-ELA existentes (de Liefooghe et al., 2021), com a seleção de características consistentemente retendo uma mistura de ambas, sugerindo que diferentes grupos de características capturam diferentes propriedades necessárias da paisagem.
4. Praticidade: As características são estáveis e eficazes mesmo com tamanhos de amostra relativamente pequenos (ex: 200–500 pontos), tornando-as viáveis para aplicação prática onde os orçamentos computacionais são limitados.

Os autores concluem que, embora a pesquisa esteja em estágio inicial, estas características fornecem insights significativos sobre a estrutura do problema e melhoram significativamente o estado da arte na seleção automática de algoritmos para otimização multi-objetiva contínua.