QUASAR: An Evolutionary Algorithm to Accelerate High-Dimensional Numerical Optimization

Resumo Técnico: QUASAR – Um Algoritmo Evolutivo para Otimização de Alta Dimensionalidade

Definição do Problema
A otimização numérica de alta dimensionalidade permanece um desafio persistente na ciência computacional, particularmente em campos como aprendizado de máquina, engenharia e finanças. O obstáculo primário é a "maldição da dimensionalidade", onde o crescimento exponencial do espaço de busca torna os métodos de busca paramétricos e baseados em gradiente tradicionais ineficazes. Embora as meta-heurísticas, especificamente a Evolução Diferencial (DE), tenham se estabelecido como otimizadores robustos, as variantes padrão de DE frequentemente lutam para manter um equilíbrio eficaz entre exploração global e explotação local em espaços de alta dimensão. Isso frequentemente leva à estagnação ou convergência prematura, necessitando de reinicializações frequentes ou ajustes extensivos de hiperparâmetros, o que limita sua utilidade prática.

Metodologia: O Algoritmo QUASAR
Para abordar essas limitações, o artigo apresenta o Quasi-Adaptive Search with Asymptotic Reinitialization (QUASAR). Conceitualmente inspirado na busca probabilística por estabilidade em núcleos estelares e no comportamento de partículas quânticas, o QUASAR estende o framework de DE através de três mecanismos altamente estocásticos projetados para equilibrar dinamicamente a exploração e a explotação:

1. Estratégias de Mutação Probabilística:
   Em vez de uma estratégia de mutação fixa, o QUASAR emprega uma abordagem de "empurrar e puxar" usando três estratégias distintas selecionadas dinamicamente com base em uma "taxa de emaranhamento" (padrão 0,33):

   • Spooky-Best (Local/Explotação): Semelhante ao DE/best/1, esta estratégia explota o espaço de busca imediato ao redor da melhor solução atual ($X_{best}$) usando um fator de mutação amostrado de uma distribuição normal $N(0, 0,33^2)$:
   • Spooky-Current & Spooky-Random (Global/Exploração): Estas estratégias impulsionam a exploração não local. Elas utilizam uma distribuição bimodal para o fator de mutação, $N(0,5, 0,25^2) + N(-0,5, 0,25^2)$, para encorajar saltos maiores. Notavelmente, a estratégia Spooky-Random utiliza o mesmo vetor aleatório duas vezes em sua formulação.

2. Crossover Baseado em Rank:
   O QUASAR utiliza uma taxa de crossover binomial dinâmica ($CR_i$) inversamente proporcional ao rank de aptidão (fitness) da solução. As melhores soluções (rank 0) recebem uma taxa de crossover mais alta (limitada a um mínimo de 0,33), permitindo que recombinem rapidamente componentes de vetores mutantes. Isso garante que soluções de alta qualidade herdem características benéficas enquanto mantêm a diversidade.

3. Reinicialização de Covariância Assintótica:
   Uma inovação primária do QUASAR é seu mecanismo de reinicialização. Nas gerações iniciais, os 33% piores desempenhos da população são reinicializados. A probabilidade deste evento decai assintoticamente em direção a um alvo de 0,33 conforme as gerações progridem.

   • Mecanismo: Novas soluções são amostradas de uma distribuição normal multivariada definida pela média ($\mu$) e matriz de covariância ($\Sigma$) dos 25% melhores da população.
   • Ruído: Um vetor de ruído é adicionado à distribuição amostrada para promover ainda mais a exploração.
   • Restrição: Este mecanismo é ignorado se o tamanho da população ($N$) for menor que a dimensionalidade ($D$) para evitar matrizes de covariância singulares.

Design Experimental
A eficácia do QUASAR foi rigorosamente avaliada contra o DE padrão (implementação SciPy) e o estado da arte L-SHADE (implementação MealPy) utilizando a suíte de benchmarks CEC2017 completa de 29 funções de teste.

• Parâmetros: Experimentos utilizaram hiperparâmetros padrão para todos os algoritmos para garantir uma comparação justa.
• Variantes: Os ensaios foram conduzidos em diversas dimensões ($D \in [10, 30, 50, 100]$) com um tamanho de população fixo ($N=1000$), e variando os tamanhos de população ($N \in [100, 5000]$) com uma dimensão fixa ($D=100$).
• Métricas: O desempenho foi medido usando som de ranks de Friedman, fatores de redução de erro de média geométrica ($R_{error}$) e razões de tempo de execução de otimização ($R_{time}$). A significância estatística foi verificada usando o teste de postos sinalados de Wilcoxon.

Principais Resultados
O QUASAR demonstrou desempenho superior em todas as métricas comparado ao DE (implementação SciPy) e ao L-SHADE (implementação MealPy):

• Ranking Geral: Usando o teste de Friedman, o QUASAR alcançou o menor som de rank geral (367), superando significativamente o L-SHADE (452) e o DE (735).
• Qualidade da Solução: Comparações de média geométrica revelaram que o QUASAR melhorou a qualidade da solução final em uma média de 3,85× sobre o DE e 2,07× sobre o L-SHADE ($p \ll 0,001$). Os ganhos mais significativos foram observados em dimensões mais altas (ex: 100D) e tamanhos de população maiores.
• Eficiência Computacional: O QUASAR foi 1,40× mais rápido que o DE e 5,16× mais rápido que o L-SHADE em média. O algoritmo escalou linearmente com a dimensionalidade, mantendo a eficiência mesmo conforme a complexidade do problema aumentava.
• Robustez: O algoritmo operou efetivamente utilizando seus parâmetros padrão, sem exigir ajuste manual de hiperparâmetros.

Significância e Alegações
O artigo postula que o QUASAR estabelece um novo padrão para algoritmos evolutivos em problemas de otimização complexos, de alta dimensão e não diferenciáveis. Sua significância reside em:

1. Efetividade: Alcança melhorias estatisticamente significativas na qualidade da solução sem exigir ajustes extensivos de parâmetros.
2. Eficiência: Oferece acelerações substanciais sobre os métodos atuais de estado da arte, tornando-o viável para aplicações do mundo real computacionalmente caras.
3. Facilidade de Uso: A dependência de parâmetros padrão e uma implementação simplificada (disponível como um pacote Python de código aberto, hdim_opt) permite uma integração perfeita em fluxos de trabalho existentes.

Os autores concluem que o QUASAR é uma ferramenta poderosa e pronta para uso para os desafios de otimização de alta dimensão da próxima geração, embora notem que trabalhos futuros podem explorar matrizes de covariância ponderadas (semelhante ao CMA-ES) e verificação em problemas com restrições ou multi-objetivo.