iStratDE: Computação GPU x Populações Ultra-Grandes Libertam Todo o Potencial da Evolução Diferencial

A Evolução Diferencial (DE) é altamente sensível à seleção de estratégia. A maioria das variantes existentes de DE procura melhor desempenho através de mecanismos adaptativos ou estruturas de controlo cada vez mais sofisticadas. No entanto, enquanto a adaptação dinâmica tem sido extensivamente estudada, os benefícios estruturais da diversidade estática de estratégias receberam muito menos atenção.

Para colmatar esta lacuna, a equipa EvoX investigou como a diversidade de estratégias ao nível individual molda a dinâmica de pesquisa e o desempenho de otimização da DE, e propôs uma variante minimalista: iStratDE (Individual-Level Strategy Diversity Differential Evolution). A ideia central é simples: na inicialização, a cada indivíduo é atribuída a sua própria estratégia de mutação e cruzamento, e essa atribuição permanece fixa ao longo de toda a evolução. Ao introduzir diversidade ao nível individual — descartando ciclos complicados de adaptação e retroalimentação — o iStratDE cria uma heterogeneidade comportamental persistente em toda a população.

Esta propriedade torna-se especialmente poderosa em populações grandes. Uma vez que o algoritmo não requer comunicação por conceção, suporta naturalmente a execução paralela eficiente e escala suavemente para ambientes GPU. A equipa também fornece uma análise de convergência sob pressupostos padrão de alcançabilidade, estabelecendo a convergência quase certa do melhor fitness encontrado. Experiências extensivas no conjunto de benchmarks CEC2022 e em tarefas de controlo robótico mostram que o iStratDE pode igualar ou até superar as variantes adaptativas convencionais de DE. O código-fonte foi publicado no GitHub: https://github.com/EMI-Group/istratde

Contexto: A Computação Evolutiva na Armadilha da Complexidade

A DE tem sido há muito uma das ferramentas mais eficazes para a otimização contínua, graças aos seus operadores simples e forte capacidade de pesquisa. No entanto, o seu desempenho depende fortemente da escolha da estratégia de mutação e dos parâmetros de controlo como F e CR. De acordo com o teorema No Free Lunch, nenhuma configuração única pode dominar em todos os problemas.

Ao longo das últimas duas décadas, a resposta predominante tem sido tornar a DE cada vez mais adaptativa. Desde o SaDE até à família LSHADE, os algoritmos tornaram-se mais “inteligentes” mantendo arquivos históricos, estimando taxas de sucesso de estratégias e ajustando parâmetros ao nível da população. Mas esta inteligência tem um custo. A lógica de controlo centralizada introduz sobrecarga computacional substancial e, mais importante, barreiras severas de sincronização. Na era do paralelismo GPU, tal dependência da troca global de informação frequentemente leva a uma fraca utilização do hardware e impede que os algoritmos explorem totalmente o poder computacional disponível.

Quebrar o Impasse: Minimalismo e Diversidade Estrutural

Será possível preservar a natureza minimalista da DE enquanto se alcança a robustez — ou até um desempenho superior — das variantes adaptativas complexas?

A equipa EvoX responde a esta questão com uma proposta contraintuitiva: iStratDE. Em vez de tentar tornar o algoritmo “mais inteligente” durante a execução, o iStratDE confere à população a máxima diversidade desde o início. Apoiado pelo framework distribuído e acelerado por GPU EvoX, o iStratDE demonstra que a evolução paralela em grande escala pode ser dramaticamente reforçada através de uma simples atribuição de estratégias ao nível individual, sem introduzir qualquer mecanismo adaptativo.

O Que É o iStratDE?

A filosofia do iStratDE pode ser resumida como “indivíduos diferentes, papéis diferentes.”

Nas variantes convencionais de DE, as estratégias são geralmente definidas ou adaptadas ao nível da população. No iStratDE, a diversidade de estratégias é introduzida ao nível do indivíduo:

Atribuído uma vez, fixo para sempre. Durante a inicialização, a cada indivíduo é aleatoriamente atribuída uma estratégia independente de mutação-cruzamento e um conjunto de parâmetros de controlo.
Execução descentralizada. Uma vez atribuídas, estas estratégias permanecem inalteradas ao longo de todo o processo evolutivo. Cada indivíduo pesquisa de acordo com o seu próprio conjunto de regras, sem reportar a um controlador central ou aguardar retroalimentação de outros.
Paralelismo intrínseco. Uma vez que os indivíduos não dependem uns dos outros através de sincronização complexa, o iStratDE elimina a sobrecarga de comunicação e mapeia-se naturalmente na arquitetura SIMT da GPU.

Se a DE adaptativa tradicional se assemelha a um exército cujas táticas são centralmente coordenadas por um comandante, então o iStratDE assemelha-se a um ecossistema. Alguns indivíduos estão naturalmente vocacionados para a exploração de longo alcance, enquanto outros são melhores na exploração localizada. Esta heterogeneidade não só fornece redundância contra a convergência prematura, como também permite contribuições assíncronas que mantêm a população a avançar constantemente para melhores soluções.

Por Que Funciona o iStratDE?

Apesar da sua simplicidade, o iStratDE apresenta um desempenho notável tanto no conjunto de benchmarks CEC2022 como nas tarefas de controlo robótico com Brax. Dois mecanismos são particularmente importantes:

Elitismo implícito. Nem todas as estratégias são adequadas para todos os problemas, mas numa população suficientemente grande, alguns indivíduos receberão configurações altamente compatíveis. Estes “elites” ascendem rapidamente e guiam a pesquisa para regiões de alta qualidade.
Convergência assíncrona. Diferentes estratégias convergem a diferentes velocidades. Alguns indivíduos fazem avanços agressivos cedo, enquanto outros melhoram de forma mais estável posteriormente. Esta diversidade no ritmo de convergência ajuda a prevenir o colapso prematuro da população em ótimos locais.

Vantagens Centrais do iStratDE

Ao introduzir diversidade de estratégias ao nível individual, o iStratDE oferece vários benefícios importantes:

Extrema simplicidade estrutural. Remove arquivos históricos, módulos de aprendizagem de parâmetros e hiperparâmetros adicionais, devolvendo à DE uma forma limpa e altamente reprodutível.
Excelente eficiência GPU. Graças ao seu design sem comunicação, o iStratDE alcança aceleração quase linear em GPUs e pode gerir populações de mais de 100.000 indivíduos.
Melhor desempenho com populações maiores. Ao contrário de muitas variantes tradicionais de DE, que frequentemente sofrem de estrangulamentos de eficiência quando a população se torna demasiado grande, o iStratDE beneficia diretamente da escala: mais indivíduos significam maior diversidade, cobertura mais ampla de estratégias e desempenho de pesquisa mais forte.
Suporte teórico. O resultado de convergência quase certa fornece uma base matemática sólida para este design minimalista.

Detalhes de Implementação

O iStratDE integra estreitamente a tensorização com a aceleração GPU. A sua eficiência provém de um distintivo design de bloqueio de comunicação: ao contrário dos algoritmos adaptativos que dependem de estatísticas centralizadas, as estratégias dos indivíduos no iStratDE são completamente independentes, eliminando requisitos de sincronização e alinhando-se perfeitamente com o modelo SIMT da GPU.

Com o suporte do framework EvoX, o iStratDE pode evoluir eficientemente populações de mais de 100.000 indivíduos em paralelo. Esta independência tensorizada não só melhora o throughput para otimização em grande escala, como também permite uma ampla cobertura do espaço de pesquisa através de exploração concorrente massiva.

Construção do Pool de Estratégias

Para criar diversidade na população, a equipa constrói um pool de estratégias com 192 configurações. Cada estratégia segue a forma DE/bl-to-br/dn/cs, e é composta por elementos modulares:

Vetor base esquerdo, selecionado de rand, best, pbest ou current
Vetor base direito, também selecionado de rand, best, pbest ou current
Número de vetores diferenciais, escolhido de {1, 2, 3, 4}
Esquema de cruzamento, incluindo cruzamento binomial, exponencial e aritmético

Adicionalmente, o fator de escala F e a taxa de cruzamento CR de cada indivíduo são independentemente amostrados de U(0, 1). Através de diferentes combinações destes componentes, o iStratDE gera um amplo espetro de comportamentos de pesquisa, desde altamente exploratórios até fortemente explorativos.

Visão Geral da Arquitetura

O iStratDE segue um fluxo de trabalho descentralizado extremamente simples:

Atribuição inicial. O sistema inicializa as posições da população e atribui aleatoriamente a cada indivíduo uma estratégia e um conjunto de parâmetros dedicados.
Evolução persistente. Durante o ciclo de otimização, cada indivíduo realiza sempre mutação e cruzamento de acordo com a sua configuração atribuída. As soluções evoluem, mas as estratégias não.
Integração implícita. Uma vez que a população é grande e heterogénea, o iStratDE não requer coordenação adaptativa explícita. Surge uma divisão natural do trabalho: indivíduos orientados para a exploração descobrem novas regiões, enquanto indivíduos orientados para a exploração refinam soluções promissoras.

Fig. 1. Framework do iStratDE, ilustrando a inicialização, atribuição descentralizada de estratégias e evolução persistente.

Destaques Experimentais

Para avaliar o iStratDE em configurações genuinamente paralelas em grande escala, a equipa EvoX realizou experiências sistemáticas sob um orçamento de tempo fixo, que reflete melhor as condições reais de computação de alto desempenho do que a avaliação convencional com número fixo de avaliações de função.

As experiências incluem:

Testes de stress com populações ultra-grandes, escalando até 100.000 indivíduos
Benchmarks CEC2022, comparando o iStratDE com variantes adaptativas convencionais de DE e os melhores métodos de competição em 60 segundos
Análise de escalabilidade populacional, mostrando que o iStratDE continua a melhorar à medida que a população cresce enquanto os métodos tradicionais atingem um limite de escala
Tarefas de controlo robótico, usando populações grandes para otimizar controladores neuronais de alta dimensão em Brax

1. Benchmarks CEC2022 Sob um Orçamento de Tempo Fixo

Sob o mesmo orçamento de 60 segundos, os algoritmos adaptativos tradicionais permanecem restritos ao tamanho clássico de população de cerca de 100 devido à sua lógica serial e sobrecarga de sincronização. Em contraste, o iStratDE é concebido especificamente para execução SIMT em GPU e pode gerir eficientemente populações de 100.000 indivíduos.

Como resultado, o iStratDE realiza até 10^9 avaliações de função na mesma janela temporal, alcançando aproximadamente 100x o throughput computacional dos métodos convencionais. Na maioria das funções de benchmark, esta combinação de estrutura minimalista e paralelismo massivo conduz a maior velocidade de convergência e precisão final.

Fig. 2. Comparação de throughput de avaliações de função sob um orçamento de tempo fixo.

Fig. 3. Comparação de desempenho de otimização no conjunto de benchmarks CEC2022 de 10 dimensões.

2. Robustez em Paisagens de Alta Dimensão

A equipa avalia ainda o iStratDE em desafiantes versões 200-dimensionais rodadas e deslocadas de Schwefel, Rastrigin e Ackley. Os métodos adaptativos tradicionais de DE como JADE e SHADE, bem como CMA-ES, sofrem fortemente com a maldição da dimensionalidade e frequentemente estagnam cedo.

Em contraste, o iStratDE mantém forte impulso de pesquisa através de uma combinação de paralelismo em grande escala e diversidade de estratégias. Não só supera baselines especializadas como CSO, como também demonstra robustez competitiva face ao MetaDE, um otimizador recente baseado em aprendizagem em GPU. Em funções difíceis como Ackley, o iStratDE localiza com sucesso o ótimo global.

Fig. 4. Comparação de desempenho em problemas de benchmark deslocados e rodados de 200 dimensões.

3. Escalabilidade Populacional

Uma das descobertas mais marcantes é que o iStratDE quebra a suposição clássica de que simplesmente aumentar a população não continua a melhorar a DE. Quando o tamanho da população cresce de 10^2 para 4 x 10^5, o iStratDE continua a melhorar de forma constante, sem sinais claros de saturação.

Em contraste, os algoritmos adaptativos tradicionais de DE geralmente deixam de beneficiar quando a população excede um limiar moderado, podendo até degradar-se devido à sobrecarga de sincronização. Este resultado sugere que o iStratDE pode converter recursos computacionais adicionais diretamente em melhor desempenho de otimização.

Fig. 5. Análise de escalabilidade populacional do iStratDE com tamanhos de população crescentes.

4. Comparação com os Melhores Métodos da Competição CEC2022

Para testar o limite superior de desempenho, a equipa compara o iStratDE com os métodos melhor classificados da competição CEC2022, incluindo EA4eig, NL-SHADE-LBC e NL-SHADE-RSP. Sob orçamentos idênticos de avaliação de funções, o iStratDE permanece altamente competitivo apesar da sua estrutura muito mais simples. Em várias funções difíceis de 10D e 20D, alcança resultados comparáveis — ou melhores — do que estas baselines sofisticadas.

Fig. 6. Comparação do iStratDE com os métodos melhor classificados da competição CEC2022.

5. Aplicação Real: Controlo Robótico com Brax

Finalmente, a equipa aplica o iStratDE a tarefas de controlo robótico em Brax, incluindo Swimmer, Reacher e Hopper, onde o objetivo é otimizar controladores de redes neuronais com aproximadamente 1.500 parâmetros.

Usando uma população de 10.000, o iStratDE é comparado com CMA-ES, CSO e variantes tradicionais de DE. Em tarefas como Swimmer e Hopper, o iStratDE descobre rapidamente políticas de alta recompensa e mostra convergência mais forte do que métodos como CMA-ES e LSHADE. Isto demonstra que o iStratDE não é apenas teoricamente elegante, mas também praticamente eficaz para otimização de caixa negra em alta dimensão.

Fig. 7. Curvas de convergência do iStratDE em três ambientes de controlo Brax.

Conclusão e Perspetivas

O iStratDE é um regresso aos fundamentos algorítmicos. Em vez de empilhar lógica adaptativa cada vez mais complexa, constrói forte capacidade de pesquisa a partir da diversidade de estratégias ao nível individual. Ao libertar totalmente o potencial paralelo das GPUs modernas, o iStratDE revela o poder da diversidade estruturada na otimização multimodal e de alta dimensão.

Os resultados mostram que o iStratDE pode competir com — e em alguns cenários superar — as principais variantes adaptativas de DE tanto em benchmarks como em tarefas de controlo do mundo real. De forma mais ampla, este trabalho destaca um princípio de design importante: a complexidade não é o único caminho para o desempenho; a heterogeneidade populacional pode ser, por si só, um poderoso motor de evolução.

Este paradigma minimalista descentralizado abre uma nova direção para o design de algoritmos evolutivos. Em vez de depender de coordenação centralizada elaborada, demonstra como indivíduos independentes com comportamentos de pesquisa diversos podem coletivamente gerar dinâmicas de otimização inteligentes e escaláveis.

Código Aberto / Recursos da Comunidade

Artigo: https://arxiv.org/abs/2602.01147

GitHub: https://github.com/EMI-Group/istratde

Projeto Principal (EvoX): https://github.com/EMI-Group/evox

Grupo QQ: 297969717

Código QR do grupo comunitário EvoX no QQ.