DE-2LS: Differential Evolution with Lightweight Late Local Search for Constrained Numerical Optimization

Resumo Técnico: DE-2LS para Otimização Numérica com Restrições

Definição do Problema
A otimização numérica de objetivo único com restrições exige o equilíbrio de três fatores concorrentes: viabilidade (satisfazer as restrições), convergência do objetivo e eficiência computacional, tudo dentro de um orçamento fixo de avaliações de função. Embora a Evolução Diferencial (DE) seja um algoritmo robusto baseado em população, variantes padrão frequentemente enfrentam dificuldades nas etapas finais de otimização. Especificamente, após a descoberta de uma região viável, o orçamento de busca restante pode ser gasto gerando vetores de tentativa que são muito grosseiros ou estocásticos para refinar eficientemente a solução atual. Essa limitação é crítica em ambientes de pontuação pareada (como as competições IEEE CEC), onde pequenos incrementos na qualidade ou velocidade da solução final podem impactar decisivamente a classificação geral.

Metodologia
O artigo propõe o DE-2LS (Differential Evolution with Lightweight Late Local Search), uma variante do framework RDEx projetada para otimização com restrições. A filosofia central de design é "não causar danos": os componentes originais do RDEx permanecem inteiramente inalterados, preservando suas forças estabelecidas em busca global, descoberta de viabilidade e velocidade.

Em vez de modificar o motor evolutivo, o DE-2LS introduz uma busca local de padrão de coordenadas leve (LS) como um mecanismo de "polimento guardado". As principais características metodológicas incluem:

• Ativação em Estágio Tardio: A busca local não está ativa durante os estágios iniciais ou intermediários da execução para evitar exploração prematura ou o consumo de avaliações em bacias não promissoras. Ela é acionada apenas quando condições específicas são atendidas:
  1. A busca progrediu além de um limite (ex: 85% do orçamento), o melhor global estagnou por um número definido de gerações e o incumbente é viável ou quase viável.
  2. Um gatilho de contingência de "estágio muito tardio" (ex: 95% do orçamento) garante uma tentativa final de polimento mesmo se os critérios de estagnação não forem estritamente atendidos.
• Busca de Padrão de Coordenadas: O LS opera em torno da melhor solução atual ($x_b$). Ele examina movimentos candidatos ao longo de cada dimensão de coordenada ($x_d \pm \Delta$). Se um candidato melhora a solução, o centro é atualizado imediatamente (regra de primeira melhoria). Se nenhuma melhoria for encontrada em todas as coordenadas, o tamanho do passo $\Delta$ é reduzido pela metade.
• Aceitação Consciente de Viabilidade: Os candidatos são aceitos com base na mesma lógica usada pelo RDEx: uma solução é preferida se for viável com um valor de objetivo menor, ou se reduzir a violação de restrição quando ambas as soluções são inviáveis.
• Injeção de População: Se o LS encontrar uma solução melhor, ela é injetada de volta na população do RDEx. Crucialmente, toda a população não é substituída e a memória de histórico de sucesso não é resetada, garantindo que a dinâmica adaptativa do RDEx seja preservada.
• Restrições de Orçamento: O LS é estritamente limitado pelo orçamento (ex: 0,5% do orçamento total por chamada, com no máximo duas chamadas), garantindo que atue como uma ferramenta de refinamento em vez de uma estratégia de busca dominante.

Principais Contribuições

1. Proposta Algorítmica: A introdução do DE-2LS, um algoritmo de otimização com restrições que aprimora o RDEx via uma busca local controlada em estágio tardio sem alterar os operadores evolutivos principais.
2. Princípio de Design: Uma abordagem conservadora que separa a descoberta de viabilidade global (tratada pelo RDEx) da exploração final (tratada pelo LS), evitando a interrupção das vantagens de velocidade do RDEx.
3. Especificidades do Mecanismo: A implementação de uma regra de aceitação consciente de viabilidade dentro da busca local e uma lógica de gatilho específica que evita a exploração prematura.
4. Validação Empírica: Estudos de ablação abrangentes e experimentos comparativos demonstrando que o refinamento controlado em estágio tardio é superior às estratégias de busca local agressivas ou prematuras.

Resultados
O artigo avalia o DE-2LS em 28 problemas de objetivo único com restrições do conjunto de benchmarks CEC (dimensão $D=30$, MaxFEs = $20000 \times D$). O desempenho é medido usando o U-score, uma métrica combinada de precisão e velocidade derivada de comparações pareadas.

• Estudo de Ablação: Entre várias configurações (diferentes orçamentos, tempos de início e tamanhos de passo), a configuração finalizada do DE-2LS alcançou o maior U-score (178.749), superando variantes com orçamentos maiores ou ativação mais precoce. Isso confirma que um pequeno orçamento em estágio tardio é ideal.
• Comparação Direta vs. RDEx: O DE-2LS melhorou o U-score do RDEx base em 5,58% (de 33.369,5 para 35.230,5). Esse ganho foi impulsionado por melhorias tanto em precisão (+6,17%) quanto em velocidade (+4,99%), indicando que a busca local refinou a solução sem sacrificar a velocidade de convergência do algoritmo.
• Comparação de Quatro Algoritmos: Comparado ao RDEx, CL-SRDE e UDE-III, o DE-2LS alcançou o maior U-score geral (80.968) e o melhor ranking total (48).
  • Enquanto o UDE-III alcançou a maior pontuação de precisão total, sua pontuação de velocidade significativamente menor resultou em um U-score geral inferior.
  • O DE-2LS equilibrou com sucesso alta precisão final com as características de convergência rápida do RDEx.
• Estabilidade: A análise de média e desvio padrão mostrou que o DE-2LS manteve a qualidade da solução final e a estabilidade competitivas, com a busca local atuando como um mecanismo de polimento controlado em vez de desestabilizar a população.

Significância e Alegações
O artigo afirma que o DE-2LS demonstra que o refinamento controlado em estágio tardio é uma estratégia mais eficaz para otimização com restrições do que a busca local agressiva ou prematura. Ao preservar o framework original do RDEx, o método retém as capacidades inerentes de velocidade e tratamento de viabilidade do algoritmo, enquanto aborda sua fraqueza na exploração local de grão fino.

Os autores concluem que o DE-2LS fornece um perfil de desempenho mais equilibrado e robusto para otimização numérica com restrições sob o critério de pontuação combinada de velocidade-precisão. O trabalho sugere que, em vez de reformular frameworks evolutivos bem-sucedidos, adicionar um componente de busca local leve e estritamente controlado pode gerar ganhos de desempenho significativos em cenários de benchmarks competitivos. O código-fonte é disponibilizado para facilitar pesquisas futuras.