Estratégia de evolução - Evolution strategy

Parte de uma série no
Algoritmo evolutivo
Algoritmo genético
Programação genética

Em ciência da computação, uma estratégia de evolução (ES) é uma técnica de otimização baseada em ideias de evolução . Pertence à classe geral de computação evolutiva ou metodologias de evolução artificial .

História

A técnica de otimização da 'estratégia de evolução' foi criada no início da década de 1960 e desenvolvida ainda mais na década de 1970 e posteriormente por Ingo Rechenberg , Hans-Paul Schwefel e seus colegas de trabalho.

Métodos

As estratégias de evolução usam representações naturais dependentes do problema, e principalmente mutação e seleção , como operadores de busca. Em comum com os algoritmos evolutivos , os operadores são aplicados em um loop. Uma iteração do loop é chamada de geração. A sequência de gerações continua até que um critério de terminação seja atendido.

Para espaços de busca com valor real, a mutação é realizada adicionando um vetor aleatório normalmente distribuído . O tamanho do passo ou força da mutação (isto é, o desvio padrão da distribuição normal) é freqüentemente governado pela auto-adaptação (veja a janela de evolução ). Tamanhos de etapa individuais para cada coordenada, ou correlações entre coordenadas, que são essencialmente definidas por uma matriz de covariância subjacente , são controlados na prática por auto-adaptação ou por adaptação de matriz de covariância ( CMA-ES ). Quando a etapa de mutação é desenhada de uma distribuição normal multivariada usando uma matriz de covariância em evolução , foi hipotetizado que esta matriz adaptada se aproxima do inverso de Hessian do cenário de pesquisa. Esta hipótese foi comprovada para um modelo estático baseado em uma aproximação quadrática.

A seleção (ambiental) nas estratégias de evolução é determinística e baseada apenas nas classificações de aptidão, não nos valores de aptidão reais. O algoritmo resultante é, portanto, invariante em relação às transformações monotônicas da função objetivo. A estratégia de evolução mais simples opera em uma população de tamanho dois: o ponto atual (pai) e o resultado de sua mutação. Somente se a aptidão do mutante for pelo menos tão boa quanto a do pai, ele se tornará o pai da próxima geração. Caso contrário, o mutante é desconsiderado. Este é um (1 + 1) -ES . Mais geralmente, os mutantes λ podem ser gerados e competir com o pai, chamado (1 + λ) -ES . Em (1, λ) -ES, o melhor mutante torna-se o pai da próxima geração, enquanto o pai atual é sempre desconsiderado. Para algumas dessas variantes, as provas de convergência linear (em um sentido estocástico ) foram derivadas em funções objetivo unimodal.

Derivados contemporâneos da estratégia de evolução freqüentemente usam uma população de pais μ e recombinação como um operador adicional, chamado (μ / ρ +, λ) -ES . Isso os torna menos propensos a se estabelecerem em ótimos locais.

Veja também

Referências

Bibliografia

Centros de pesquisa