Evolução diferencial - Differential evolution

Evolução diferencial otimizando a função Ackley 2D.

Em computação evolutiva , evolução diferencial ( ED ) é um método que otimiza um problema ao tentar melhorar iterativamente uma solução candidata com relação a uma dada medida de qualidade. Tais métodos são comumente conhecidos como metaheurísticas , pois fazem poucas ou nenhuma suposição sobre o problema que está sendo otimizado e podem pesquisar espaços muito grandes de soluções candidatas. No entanto, metaheurísticas como DE não garantem que uma solução ótima seja encontrada.

DE é usado para funções de valor real multidimensionais, mas não usa o gradiente do problema que está sendo otimizado, o que significa que DE não exige que o problema de otimização seja diferenciável , como é exigido por métodos de otimização clássicos, como descida de gradiente e métodos de quase newton . DE pode, portanto, também ser usado em problemas de otimização que nem mesmo são contínuos , são barulhentos, mudam ao longo do tempo, etc.

O DE otimiza um problema mantendo uma população de soluções candidatas e criando novas soluções candidatas combinando as existentes de acordo com suas fórmulas simples e, em seguida, mantendo a solução candidata que tiver a melhor pontuação ou adequação ao problema de otimização em questão. Desta forma, o problema de otimização é tratado como uma caixa preta que meramente fornece uma medida de qualidade dada uma solução candidata e, portanto, o gradiente não é necessário.

A DE foi introduzida por Storn e Price na década de 1990. Livros foram publicados sobre aspectos teóricos e práticos do uso de DE em computação paralela , otimização multiobjetivo , otimização restrita e os livros também contêm pesquisas de áreas de aplicação. Pesquisas sobre os aspectos multifacetados da pesquisa de EAD podem ser encontradas em artigos de periódicos.

Algoritmo

Uma variante básica do algoritmo DE funciona tendo uma população de soluções candidatas (chamadas de agentes). Esses agentes são movidos no espaço de busca usando fórmulas matemáticas simples para combinar as posições dos agentes existentes na população. Se a nova posição de um agente é uma melhoria, então ele é aceito e faz parte da população, caso contrário, a nova posição é simplesmente descartada. O processo é repetido e, ao fazê-lo, espera-se, mas não é garantido, que uma solução satisfatória seja eventualmente descoberta.

Formalmente, seja a função de aptidão que deve ser minimizada (observe que a maximização pode ser realizada considerando a função ). A função pega uma solução candidata como argumento na forma de um vetor de números reais e produz um número real como saída que indica a adequação da solução candidata dada. O gradiente de não é conhecido. O objetivo é encontrar uma solução para o qual para todos no espaço de busca, o que significa que é o mínimo global. ${\ displaystyle f: \ mathbb {R} ^ {n} \ to \ mathbb {R}}$${\ displaystyle h: = - f}$${\ displaystyle f}$${\ displaystyle \ mathbf {m}}$${\ displaystyle f (\ mathbf {m}) \ leq f (\ mathbf {p})}$${\ displaystyle \ mathbf {p}}$${\ displaystyle \ mathbf {m}}$

Vamos designar uma solução candidata (agente) na população. O algoritmo DE básico pode então ser descrito da seguinte forma: ${\ displaystyle \ mathbf {x} \ in \ mathbb {R} ^ {n}}$

• Escolha os parâmetros , e . é o tamanho da população, ou seja, o número de candidatos a agentes ou "pais"; uma configuração clássica é 10 . O parâmetro é chamado de probabilidade de cruzamento e o parâmetro é chamado de peso diferencial . As configurações clássicas são e . O desempenho da otimização pode ser muito afetado por essas escolhas; Veja abaixo.${\ displaystyle {\ text {CR}} \ in [0,1]}$${\ displaystyle F \ in [0,2]}$${\ displaystyle {\ text {NP}} \ geq 4}$${\ displaystyle {\ text {NP}}}$${\ displaystyle n}$${\ displaystyle {\ text {CR}} \ in [0,1]}$${\ displaystyle F \ in [0,2]}$${\ displaystyle F = 0,8}$${\ displaystyle CR = 0,9}$
• Inicialize todos os agentes com posições aleatórias no espaço de busca.${\ displaystyle \ mathbf {x}}$
• Até que um critério de encerramento seja atendido (por exemplo, número de iterações realizadas ou adequação adequada alcançada), repita o seguinte:
  • Para cada agente na população, faça: ${\ displaystyle \ mathbf {x}}$
    • Escolha três agentes e, da população ao acaso, eles devem ser distintos entre si e também do agente . ( é chamado de vetor "base").${\ displaystyle \ mathbf {a}, \ mathbf {b}}$${\ displaystyle \ mathbf {c}}$${\ displaystyle \ mathbf {x}}$${\ displaystyle \ mathbf {a}}$
    • Escolha um índice aleatório onde está a dimensionalidade do problema que está sendo otimizado.${\ displaystyle R \ in \ {1, \ ldots, n \}}$${\ displaystyle n}$
    • Calcule a posição potencialmente nova do agente da seguinte forma: ${\ displaystyle \ mathbf {y} = [y_ {1}, \ ldots, y_ {n}]}$
      • Para cada um , escolha um número aleatório uniformemente distribuído${\ displaystyle i \ in \ {1, \ ldots, n \}}$${\ displaystyle r_ {i} \ sim U (0,1)}$
      • Se ou então defina de outra forma . (A posição do índice é substituída com certeza.)${\ displaystyle r_ {i} <CR}$${\ displaystyle i = R}$${\ displaystyle y_ {i} = a_ {i} + F \ times (b_ {i} -c_ {i})}$${\ displaystyle y_ {i} = x_ {i}}$${\ displaystyle R}$
    • Se então, substitua o agente na população pela solução candidata melhorada ou igual .${\ displaystyle f (\ mathbf {y}) \ leq f (\ mathbf {x})}$${\ displaystyle \ mathbf {x}}$${\ displaystyle \ mathbf {y}}$
• Escolha o agente da população que tem a melhor aptidão e retorne-o como a solução candidata mais bem encontrada.

Seleção de parâmetros

Cenário de desempenho mostrando como o DE básico executa em agregado nos problemas de benchmark Sphere e Rosenbrock ao variar os dois parâmetros de DE e , e mantendo fixo = 0,9.${\ displaystyle {\ text {NP}}}$${\ displaystyle {\ text {F}}}$${\ displaystyle {\ text {CR}}}$

A escolha do DE parâmetros e pode ter um grande impacto sobre o desempenho de otimização. A seleção dos parâmetros de DE que geram bom desempenho, portanto, tem sido objeto de muitas pesquisas. As regras práticas para a seleção de parâmetros foram elaboradas por Storn et al. e Liu e Lampinen. A análise matemática da convergência em relação à seleção dos parâmetros foi feita por Zaharie. ${\ displaystyle F, {\ text {CR}}}$${\ displaystyle {\ text {NP}}}$

Variantes

Variantes do algoritmo DE estão continuamente sendo desenvolvidas em um esforço para melhorar o desempenho da otimização. Muitos esquemas diferentes para realizar crossover e mutação de agentes são possíveis no algoritmo básico fornecido acima, consulte, por exemplo.

Veja também

• Algoritmo de otimização Mayfly
• Algoritmo de colônia de abelha artificial
• CMA-ES
• Estratégia de evolução
• Algoritmo genético

Referências