Skip to content
Voltar aos resultados

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

Tamanho da fonte

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

1

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)).

2

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.

3

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.

4

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.

5

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

  1. Hansen, N. & Ostermeier, A. (2001). Completely Derandomized Self-Adaptation in Evolutionary Strategies. Evolutionary Computation, 9(2), 159-195.

    Abrir referência DOI
    Copiado.
  2. Hansen, N. (2016). The CMA Evolution Strategy: A Tutorial. arXiv:1604.00772.

    Abrir referência da publicação
    Copiado.