Evolução Diferencial — Otimizador Estocástico Global
- Proposto por
- Rainer Storn & Kenneth Price
- Ano
- 1997
- Tipo
- Population-based stochastic metaheuristic
Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês
O que ele faz?
A Evolução Diferencial (DE), introduzida por Rainer Storn e Kenneth Price em 1997, é um algoritmo estocástico de otimização baseado em população, projetado para espaços de parâmetros contínuos.
Ela gera soluções candidatas combinando diferenças vetoriais entre membros existentes da população, tornando-a uma alternativa poderosa e com poucos parâmetros aos Algoritmos Genéticos e à Otimização por Enxame de Partículas quando o cenário de busca não é convexo, é multimodal ou é mal adaptado a métodos baseados em gradiente.
A intuição por trás do método
Imagine um grupo de exploradores espalhados por uma paisagem desconhecida em busca do vale mais baixo. A cada passo, cada explorador observa três colegas escolhidos aleatoriamente, move-se na direção sugerida pela diferença entre dois deles, escalada por um fator de tamanho de passo, e então decide se a nova posição ou a antiga é um terreno melhor. Ao longo de muitas rodadas, todo o grupo se aglomera gradualmente em torno do vale mais profundo que coletivamente encontrou. A Evolução Diferencial funciona exatamente assim: a 'diferença' entre dois vetores da população atua como a direção de busca, e o fator de escala F controla a ousadia de cada passo.
História
A Evolução Diferencial foi introduzida por Rainer Storn e Kenneth Price em seu artigo marco de 1997 no Journal of Global Optimization. O algoritmo surgiu do trabalho anterior de Price em annealing genético e dos experimentos de Storn com crossover de ponto flutuante. A variante original, agora chamada DE/best/1/bin, provou ser competitiva com — e muitas vezes superior a — estratégias evolutivas e algoritmos genéticos contemporâneos em benchmarks padrão. Uma revisão abrangente por Das, Mullick e Suganthan (2016) catalogou mais de duas décadas de variantes, esquemas adaptativos e aplicações, estabelecendo a DE como um dos métodos fundamentais na literatura de meta-heurísticas.
Quando usar
A Evolução Diferencial é apropriada quando a função objetivo é contínua, possivelmente não diferenciável ou multimodal, e os limites de busca para todos os parâmetros são conhecidos com antecedência. Ela não requer informação de gradiente e nenhuma suposição de normalidade, portanto, é adequada para projeto de engenharia, ajuste de hiperparâmetros, calibração de modelos de simulação e qualquer tarefa de otimização de caixa preta. Um tamanho de população de aproximadamente 10 vezes o número de parâmetros é um ponto de partida comum. A DE não deve ser aplicada a problemas puramente discretos ou combinatórios; ela também precisa de pelo menos 1.000 iterações para convergir de forma confiável — se o orçamento de avaliação de função for muito apertado, a otimização Bayesiana é uma alternativa mais eficiente em termos de amostra.
Limitações e considerações
- A convergência pode ser lenta se o número de iterações for insuficiente; menos de 1.000 gerações frequentemente produz um resultado subótimo.
- O desempenho é sensível à escolha de F e CR — parâmetros mal ajustados podem levar à convergência prematura ou progresso excessivamente lento.
- Não projetada para espaços de busca puramente discretos ou combinatórios; existem extensões discretas, mas são menos padronizadas.
- Cada iteração requer a avaliação da função objetivo NP vezes, o que pode ser custoso quando cada avaliação é computacionalmente cara.
As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.
Pontos fortes
- Não requer informação de gradiente — funciona com qualquer função objetivo de caixa preta, incluindo as não diferenciáveis e ruidosas.
- Pouquíssimos parâmetros de controle (F, CR, NP) em relação ao seu poder de busca, tornando-a comparativamente fácil de configurar.
- Lida naturalmente com cenários multimodais onde otimizadores baseados em gradiente convergem para ótimos locais.
- As avaliações da população são independentes e podem ser paralelizadas de forma direta, reduzindo o tempo de relógio em sistemas multi-core.
- Competitiva com Algoritmos Genéticos e Otimização por Enxame de Partículas em muitos benchmarks, utilizando uma regra de atualização mais simples.
Aplicações
- Calibração de modelos de simulação e baseados em agentes cujas funções objetivo são não analíticas.
- Otimização de hiperparâmetros para pipelines de aprendizado de máquina quando o espaço de busca é contínuo e limitado.
- Problemas de projeto de engenharia, como projeto de antenas, otimização estrutural e ajuste de controladores.
- Treinamento de redes neurais e ajuste de modelos não lineares em engenharia e ciências naturais.
- Otimização de pesos de portfólio e estimação de parâmetros em modelos financeiros de séries temporais.
Como funciona
Como funciona
Uma população de NP vetores de solução candidata é extraída uniformemente ao acaso dentro dos limites de busca predefinidos para cada parâmetro. Os limites de busca devem ser especificados pelo usuário antes que o algoritmo comece; a DE não pode inferi-los do problema. Uma boa população inicial cobre todo o espaço factível para que o algoritmo não perca regiões promissoras desde o início.
Para cada vetor alvo na população, três vetores distintos são selecionados aleatoriamente. Um vetor mutante é formado adicionando a diferença escalada de dois deles ao terceiro: v = x_r1 + F*(x_r2 - x_r3), onde F é o fator de escala (tipicamente 0.4–1.0). Essa etapa baseada em diferença é o que distingue a DE de outros algoritmos evolutivos e lhe confere informação direcional auto-adaptativa sem exigir cálculo de gradiente.
Um vetor de teste é construído misturando o vetor mutante e o vetor alvo original elemento por elemento. Cada elemento é retirado do mutante com probabilidade CR (a taxa de crossover, tipicamente 0.5–1.0) e do alvo caso contrário; pelo menos um elemento é sempre retirado do mutante. Esta etapa controla o equilíbrio entre exploração e explotação: um CR alto favorece o mutante, um CR baixo preserva mais da solução atual.
O vetor de teste é avaliado na função objetivo e comparado com o vetor alvo. Se o teste atingir um valor objetivo igual ou melhor, ele substitui o alvo na próxima geração; caso contrário, o alvo é mantido inalterado. Essa seleção gulosa um-para-um impede que a população se deteriore e garante a melhoria monótona da melhor solução encontrada.
Mutação, crossover e seleção se repetem por um número suficiente de gerações (comumente 1.000 ou mais) até que um critério de convergência seja atendido — por exemplo, a mudança no melhor valor objetivo cai abaixo de um limite de tolerância, ou a contagem máxima de iterações é atingida. O melhor vetor na população final é a solução do algoritmo.
Erros comuns
- Executar a DE com poucas iterações (abaixo de ~1.000) é o erro mais comum — o algoritmo não teve gerações suficientes para convergir, e o resultado deve ser tratado como preliminar; mude para otimização Bayesiana se o orçamento de avaliação for apertado.
- Definir o fator de escala F muito baixo colapsa a diversidade prematuramente; defini-lo muito alto impede a convergência. Comece com F em [0.4, 1.0] e ajuste empiricamente.
- Omitir ou especificar incorretamente os limites de busca é um erro crítico — a DE usa os limites para inicializar a população e produzirá resultados sem sentido se os limites forem muito estreitos ou ausentes.
- Tratar a DE como uma execução única é arriscado em cenários multimodais — execute vários testes independentes a partir de diferentes sementes aleatórias e relate a melhor solução encontrada entre as execuções.
Perguntas frequentes
Como escolho o fator de escala F e a taxa de crossover CR?
Os padrões mais citados são F = 0.8 e CR = 0.9 para a estratégia DE/best/1/bin. Na prática, F controla o tamanho do passo — valores em torno de 0.4–1.0 são típicos — e CR controla o quanto o mutante substitui o alvo. Se a população convergir muito rapidamente, aumente F ou diminua CR. Variantes adaptativas de DE (jDE, JADE) ajustam esses parâmetros automaticamente durante a execução, o que é uma escolha razoável quando o ajuste manual é impraticável.
Quantas gerações são necessárias?
Como regra geral, pelo menos 1.000 gerações são recomendadas. Para problemas de alta dimensionalidade (muitos parâmetros) ou paisagens complexas, mais iterações podem ser necessárias. Observe o valor objetivo da melhor solução ao longo das gerações: se ele não mudou por centenas de iterações, a DE provavelmente convergiu — ou estagnou, caso em que reexecutar com uma nova semente aleatória é aconselhável.
Como a DE se compara com Algoritmos Genéticos e Otimização por Enxame de Partículas?
Todos os três são meta-heurísticas baseadas em população para otimização contínua. A DE tipicamente usa menos parâmetros de controle do que GAs e tem uma regra de atualização mais simples e determinística em comparação com PSO. Em muitos benchmarks padrão, a DE é competitiva ou supera ambos, mas o desempenho depende do problema. A escolha geralmente se resume à familiaridade e às implementações disponíveis, em vez de um ranking universal.
A DE pode lidar com parâmetros inteiros ou categóricos?
A DE é projetada para espaços contínuos. Parâmetros inteiros podem ser acomodados arredondando a solução contínua para o inteiro mais próximo após cada atualização, mas isso é uma aproximação. Problemas puramente categóricos ou combinatórios — como agendamento ou roteamento — são melhor atendidos por métodos projetados para espaços discretos, como Otimização por Colônia de Formigas ou Busca Tabu.
Métodos relacionados
Fontes
Storn, R. & Price, K. (1997). Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization, 11(4), 341–359.
Abrir referência DOICopiado.Das, S., Mullick, S. S., & Suganthan, P. N. (2016). Recent advances in differential evolution – An updated survey. Swarm and Evolutionary Computation, 27, 1–30.
Abrir referência DOICopiado.