Estratégia Evolutiva (CMA-ES) — Adaptação da Matriz de Covariância
- Proposto por
- Nikolaus Hansen & Andreas Ostermeier
- Ano
- 2001
- Tipo
- Derivative-free continuous black-box optimizer
Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês
O que ele faz?
CMA-ES, sigla para Covariance Matrix Adaptation Evolution Strategy, é um otimizador moderno para funções de caixa preta contínuas, livre de gradiente, introduzido por Hansen e Ostermeier em 2001.
Ele mantém uma população de soluções candidatas extraídas de uma distribuição normal multivariada e atualiza iterativamente a média, o tamanho do passo e a matriz de covariância completa da distribuição para direcionar a busca em direção a regiões melhores do espaço de parâmetros. Tornou-se o padrão de fato para otimização contínua de caixa preta e é amplamente utilizado na busca por arquiteturas neurais e na otimização de políticas de aprendizado por reforço.
A intuição por trás do método
Imagine que você está procurando o ponto mais baixo em uma paisagem montanhosa, mas não consegue ver o terreno — você só pode sondar locais individuais e aprender suas altitudes. CMA-ES funciona como um enxame guiado: ele lança uma nuvem de sondas em torno de uma estimativa atual melhor, mede o quão boa é cada sonda e, em seguida, remodela a nuvem para a próxima rodada. A nuvem não é uma esfera simples — ela aprende a forma alongada e inclinada do vale em que está descendo, lembrando-se de quais direções levaram à melhoria. Ao longo de gerações sucessivas, a nuvem se estreita e se inclina para se alinhar com a curvatura da superfície de perda, permitindo que o algoritmo navegue por vales longos e estreitos que prenderiam métodos mais simples.
História
As estratégias evolutivas foram introduzidas nas décadas de 1960 e 1970 como uma família de otimizadores baseados em população inspirados pela evolução biológica. O mecanismo de adaptação da matriz de covariância foi desenvolvido por Hansen e Ostermeier e totalmente descrito em seu artigo de 2001 na Evolutionary Computation, que demonstrou que a auto-adaptação completamente derandomizada — aprendendo a geometria completa de segunda ordem da paisagem de busca a partir do histórico de passos bem-sucedidos — superou dramaticamente as estratégias evolutivas anteriores em problemas mal condicionados e não separáveis. O tutorial de Hansen de 2016 consolidou o algoritmo e suas propriedades teóricas, tornando o CMA-ES o método de referência padrão para benchmarking de otimização contínua de caixa preta.
Quando usar
O CMA-ES é apropriado quando a função objetivo é contínua, possivelmente não convexa, multimodal ou ruidosa, e quando a informação de gradiente está indisponível ou é muito cara para calcular. A faixa de dimensionalidade ideal é de aproximadamente 10 a 1000 parâmetros; abaixo de 10 dimensões, métodos mais simples são frequentemente suficientes, e acima de 1000, o custo de memória quadrático da matriz de covariância pode se tornar proibitivo. Não há requisito mínimo de tamanho de amostra no sentido estatístico — o algoritmo gera seus próprios pontos de avaliação. O CMA-ES é uma adaptação natural para ajuste de hiperparâmetros, busca por arquiteturas neurais, otimização de políticas de aprendizado por reforço e problemas de projeto de engenharia onde o simulador fornece apenas saídas de caixa preta.
Limitações e considerações
- O custo computacional quadrático de memória e por geração em relação ao número de dimensões limita a aplicabilidade além de aproximadamente 1000 parâmetros sem variantes de redução de dimensionalidade.
- Converge para um ótimo local na ausência de reinícios; para paisagens altamente multimodais, múltiplos reinícios (IPOP-CMA-ES ou BIPOP-CMA-ES) são necessários.
- Não adequado para espaços de busca discretos ou combinatórios — o método é inerentemente definido sobre vetores contínuos de valores reais.
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 em qualquer função objetivo chamável, incluindo aquelas ruidosas ou baseadas em simulação.
- Aprende a curvatura local da paisagem de busca através da adaptação da covariância, permitindo-lhe navegar por espaços de busca alongados e mal condicionados que derrotam métodos sem gradiente com distribuições de busca fixas.
- Invariante a transformações que preservam a ordem da função objetivo e a rotações do espaço de busca, tornando-o robusto em uma ampla variedade de geometrias de problemas.
- Bem adequado para problemas contínuos de dimensionalidade moderada a alta (10–1000 parâmetros) com um único hiperparâmetro ajustável — o tamanho do passo inicial.
Aplicações
- Ajuste de hiperparâmetros para modelos de aprendizado de máquina, incluindo arquiteturas de redes neurais e agentes de aprendizado por reforço.
- Busca por arquiteturas neurais — otimização de parâmetros de arquitetura codificados discretamente via relaxamento contínuo.
- Otimização de políticas de aprendizado por reforço quando a política é parametrizada por um vetor contínuo.
- Otimização de projeto de engenharia, como otimização de forma aerodinâmica e ajuste de parâmetros estruturais, onde apenas saídas de simulador estão disponíveis.
- Calibração de modelos científicos — ajuste de modelos de simulação a dados experimentais quando a verossimilhança não é diferenciável ou é computacionalmente cara.
Como funciona
Como funciona
O algoritmo é inicializado com um vetor de solução inicial e um tamanho de passo inicial (sigma). A matriz de covariância começa como a matriz identidade — uma nuvem de busca perfeitamente esférica. O tamanho da população é definido, tipicamente em torno de 4 + floor(3 * ln(dimensão)).
A cada geração, uma população de soluções candidatas é amostrada da distribuição normal multivariada atual definida pelo vetor médio, pelo tamanho do passo e pela matriz de covariância. Como a distribuição é normal multivariada, as amostras refletem tanto a estimativa atual melhor quanto a forma aprendida do espaço de busca.
Cada solução candidata é passada para a função objetivo e recebe uma pontuação de aptidão. Nenhuma informação de gradiente é necessária — apenas o valor objetivo escalar em cada ponto amostrado é necessário. Isso torna o CMA-ES adequado para objetivos ruidosos, não diferenciáveis e baseados em simulação.
A média é movida em direção às soluções de melhor classificação. A matriz de covariância e o tamanho do passo são atualizados usando dois caminhos de adaptação complementares — atualizações de posto um e posto mu — de modo que as direções que produziram boas melhorias se tornem mais prováveis na próxima geração. Este é o mecanismo central pelo qual o CMA-ES aprende a geometria local da paisagem.
O algoritmo repete o ciclo de amostragem–avaliação–atualização até que um critério de parada seja atendido: um número máximo de avaliações de função, uma tolerância na mudança da média ou do tamanho do passo, ou uma degeneração detectada da matriz de covariância. A melhor solução encontrada em todas as gerações é retornada.
Erros comuns
- Definir o tamanho do passo inicial muito pequeno prende a busca em um bairro estreito e impede a exploração; muito grande e as gerações iniciais desperdiçam avaliações longe do ótimo. Uma regra prática comum é definir sigma de modo que o ótimo esteja dentro de três sigma do ponto de partida.
- Aplicar CMA-ES a problemas de dimensionalidade muito baixa (menos de cinco parâmetros) é geralmente um desperdício — busca em grade mais simples ou Nelder-Mead são suficientes, e a sobrecarga da população do CMA-ES não traz benefícios.
- Executar apenas uma única instância de CMA-ES em uma paisagem multimodal arrisca perder o ótimo global; use reinícios múltiplos ou estratégias de reinício baseadas em população (IPOP/BIPOP) quando a paisagem for conhecida por ser altamente multimodal.
- Tratar a melhor solução retornada como o verdadeiro ótimo global sem verificação de reinício é um erro comum — sempre confirme com múltiplas execuções independentes quando o objetivo for altamente não convexo.
Perguntas frequentes
Como o CMA-ES difere de um algoritmo genético simples?
Um algoritmo genético clássico mantém uma população e aplica cruzamento e mutação com operadores fixos. O CMA-ES, em vez disso, modela a população como amostras de uma distribuição normal multivariada e adapta continuamente essa distribuição — sua média, tamanho do passo e matriz de covariância completa — com base em quais soluções foram bem-sucedidas. Isso permite que o CMA-ES aprenda a forma da paisagem de perda e navegue por espaços correlacionados e mal condicionados de forma muito mais eficiente do que um algoritmo genético com operadores fixos.
O CMA-ES garante encontrar o ótimo global?
Não. O CMA-ES é um método de busca local no sentido de que uma única execução pode convergir para um ótimo local. Para paisagens multimodais, múltiplos reinícios independentes — possivelmente com tamanhos de população crescentes (IPOP-CMA-ES) — são recomendados para melhorar a cobertura do espaço de busca.
Qual é o hiperparâmetro mais importante a ser definido?
O tamanho do passo inicial sigma é o hiperparâmetro de maior influência. Uma boa heurística é defini-lo de modo que o ótimo esperado esteja a aproximadamente três sigma do ponto de partida. O tamanho da população e o número máximo de avaliações são controles secundários; a fórmula padrão de tamanho de população (4 + floor(3 * ln(dimensão))) funciona bem na prática.
O CMA-ES pode lidar com funções objetivo ruidosas?
Sim. Como o CMA-ES usa apenas informações de ordem de classificação da população — não valores de função absolutos — ele é relativamente robusto ao ruído. Para avaliações altamente ruidosas, aumentar o tamanho da população ou promediar múltiplas avaliações por candidato pode melhorar ainda mais a robustez.
Métodos relacionados
Fontes
Hansen, N. & Ostermeier, A. (2001). Completely Derandomized Self-Adaptation in Evolutionary Strategies. Evolutionary Computation, 9(2), 159-195.
Abrir referência DOICopiado.Hansen, N. (2016). The CMA Evolution Strategy: A Tutorial. arXiv:1604.00772.
Abrir referência da publicaçãoCopiado.