DE-2LS: Differential Evolution with Late-Stage local-search for Unconstrained Single-Objective Numerical Optimization

Resumo Técnico: DE-2LS para Otimização Numérica de Objetivo Único Não Restrita

Definição do Problema
O artigo aborda problemas de otimização numérica de objetivo único não restritos (UCOPs) com limites de variáveis, um cenário comum nas competições IEEE CEC. O desafio central reside em equilibrar a exploração global, a exploração intensiva (exploitation) tardia e a eficiência de avaliação de funções. Especificamente, embora variantes de Evolução Diferencial (DE) como o RDEx (DE reconstruído com ramificação enviesada para explotação) demonstrem um desempenho robusto, elas podem carecer da precisão para "polir" eficientemente soluções incumbentes uma vez que a busca entra em um vale promissor. Essa limitação é crítica sob a métrica de avaliação U-score, que avalia conjuntamente a qualidade da solução final e a velocidade de convergência. O objetivo é melhorar ambos os métricas sem interromper o comportamento de busca evolutiva robusta do algoritmo de base.

Metodologia
O método proposto, DE-2LS, é um aprimoramento conservador do framework RDEx. Em vez de substituir o motor evolutivo central do RDEx, o DE-2LS introduz dois refinamentos de estágio tardio projetados para operar dentro de um orçamento fixo de avaliações de função:

1. Atualização Suavizada da Taxa de Ramificação de Explotação Enviesada (EB):
   No estágio tardio da busca (após 75% do orçamento de avaliação ser consumido), o mecanismo atualiza a probabilidade de selecionar a ramificação enviesada para explotação. Em vez de reagir abruptamente ao desempenho imediato da ramificação, a regra de atualização aplica um suavizamento ponderado (combinação linear da taxa anterior e da estimativa bruta atual). Isso estabiliza a transição para a explotação intensiva, evitando a convergência prematura ou mudanças erráticas na estratégia de busca.

2. Busca Local de Padrão de Coordenadas Guardada (LS):
   Um módulo de busca local leve é ativado apenas quando condições específicas são atendidas: a busca está no estágio tardio (após 82% do orçamento), a melhor solução global estagnou por um número definido de gerações e o limite de chamadas de busca local não foi atingido.

   • Mecanismo: O LS opera na solução global atual utilizando uma abordagem de padrão de coordenadas. Ele explora uma direção de coordenada por vez com um tamanho de passo inicial proporcional aos limites das variáveis.
   • Estratégia: Emprega uma estratégia de "primeira melhoria" (first-improvement); se um ponto melhor for encontrado, o centro é atualizado imediatamente. Se nenhuma melhoria for encontrada, o tamanho do passo é reduzido pela metade.
   • Restrições: O processo é estritamente consciente do orçamento, com uma razão definida de avaliações alocadas por chamada e um número máximo de chamadas. Utiliza aceitação baseada apenas no objetivo (já que o problema é não restrito, exceto pelos limites) e reinjeta as soluções melhoradas na população sem resetar a memória de histórico de sucesso ou a estrutura da população.

Principas Contribuições

• Design do Algoritmo: A proposta do DE-2LS, que aumenta o baseline RDEx com uma atualização de taxa EB suavizada e um módulo de busca local guardado e controlado por orçamento.
• Estudo de Ablação: Uma análise de ablação rigorosa e em estágios foi conduzida para determinar a configuração ideal. Isso incluiu o ajuste do tempo e dos pesos do suavizamento da taxa EB, a taxa EB inicial, a escala de amostragem Gaussiana para a ramificação padrão, parâmetros de pressão de seleção e coeficientes de busca local (tempo, orçamento e tamanho de passo).
• Otimização do U-Score: O design visa explicitamente a métrica U-score, buscando melhorar simultaneamente tanto a precisão (erro final) quanto a velocidade (trajetória de convergência).

Resultos Experimentais
Experimentos foram realizados em 29 funções UCOP (D=30) com um orçamento de 10.000D avaliações de função, utilizando 25 execuções independentes por algoritmo. O desempenho foi avaliado usando o procedimento de U-score pareado.

• Comparação com RDEx: O DE-2LS superou consistentemente o RDEx original. O U-score aumentou de 33.602,0 para 37.448,0, representando uma melhoria de 11,45%. Esse ganho foi impulsionado por uma melhoria de 17,25% no componente de velocidade e uma melhoria de 5,95% no componente de precisão.
• Comparação com Algoritmos Competitivos: Em uma comparação mais ampla contra vários algoritmos competitivos e vencedores do IEEE CEC (incluindo LSRTDE, BlockEA, mLSHADE-RL, jSO e IEACOP), o DE-2LS alcançou o maior U-score geral de 178.966,5. Este resultado superou o segundo melhor algoritmo (RDEx) em 3,17% e a média dos outros competidores em aproximadamente 34,43%.
• Desempenho por Função: O DE-2LS alcançou o melhor U-score em 11 de 29 funções, a contagem mais alta entre todos os algoritmos comparados. Demonstrou uma força particular na velocidade de convergência, atingindo níveis de erro competitivos mais cedo do que seus rivais em muitas funções.

Significância e Alegações
O artigo afirma que o DE-2LS demonstra que uma estratégia de busca local de estágio tardio cuidadosamente projetada pode aumentar significativamente o desempenho de um forte algoritmo de base DE sem comprometer suas capacidades de busca global. Os autores enfatizam que o princípio de design "não causar dano" (do no harm) — preservando o motor original do RDEx enquanto adiciona um mecanismo de polimento leve e consciente do orçamento — é eficaz para melhorar tanto a velocidade de convergência quanto a qualidade final do objetivo. Os resultados sugerem que o controle de taxa EB suavizado e a busca local guardada fornecem um equilíbrio robusto entre exploração e explotação, particularmente sob a estrutura de avaliação U-score, que penaliza a convergência lenta. O código-fonte do DE-2LS é disponibilizado para apoiar a reprodutibilidade.