Algoritmo genético vs método gradiente conjugado

8

Estou tentando otimizar alguns parâmetros do campo de força em uma estrutura molecular para que o resultado da simulação chegue o mais próximo possível da estrutura experimental.

No passado, escrevi um algoritmo genético no qual, essencialmente, amostro aleatoriamente o espaço dos parâmetros, seleciono a combinação que funciona melhor, cria conjuntos de parâmetros mutantes e repita o processo até obter os melhores parâmetros para alguma função objetiva. Também realizo alguma otimização do próprio algoritmo, onde a distribuição dos valores alterados é otimizada para favorecer uma convergência mais rápida.

Meu orientador não ouviu falar de algoritmos genéticos e nunca ouvi falar dos métodos que ele recomendou: método de gradiente conjugado e algoritmo simplex.

Na minha situação, a função objetivo é uma função do desvio de cada átomo de sua localização experimental (portanto, é uma otimização estrutural). O sistema possui 4-10K átomos. Vale a pena investir algum tempo aprendendo CGM ou o algoritmo simplex? Dos três, qual é o melhor para esta situação?

usuario
fonte
5
Sempre vale a pena aprender sobre uma nova ferramenta. (Gradiente conjugado e métodos simplex são os laboriosos de optimização não linear e linear, respectivamente, e têm uma grande variedade de aplicações.)
Christian Clason

Respostas:

12

O método do gradiente conjugado é bom para encontrar o mínimo de uma função estritamente convexa. Isso é típico quando você reformula um PDE elíptico não linear como um problema de otimização. Se você quiser aprender sobre isso, recomendo que você leia primeiro o método de CG para sistemas lineares, para o qual é uma boa referência uma introdução ao método de gradiente conjugado sem dor agonizante . Infelizmente, muitos livros tratam isso retirando o algoritmo da cartola sem a menor preocupação se você o entende em um nível intuitivo, daí o título. A partir daí, não é um grande salto ver como se pode conceber um método de gradiente conjugado não linear.

Pelo que sei sobre algoritmos genéticos, eles seriam mais adequados para encontrar o mínimo global de uma função funcional objetiva que possua muitos mínimos locais, o que pode ser o caso de sistemas moleculares com muitos equilíbrios metaestáveis. Nesse caso, a função objetivo não é convexa em todos os lugares, o que impede o uso de CG. O custo é a convergência mais lenta de algoritmos aleatórios.

Se vale a pena aprender sobre CG depende de:

  • se o CG é ou não aplicável
  • quão rápido sua abordagem já está
  • quanto mais rápido o CG pode ser (meu palpite: muito, se você puder usá-lo)
  • quanto tempo você gastará aprendendo / codificando CG
  • o quanto você deseja não parecer ignorante para o seu conselheiro
  • qual o tamanho que você espera que seu problema chegue mais tarde.

Meus dois centavos: é uma ferramenta bem arrumada, mas eu a uso o tempo todo, então sou tendenciosa.

Daniel Shapero
fonte
2
+1 para 'Uma Introdução ao conjugado Método Gradiente Sem a dor agonizante'
Subodh
3

Você também pode ver o CMAES . Essencialmente, ele se resume ao CG para funções convexas, mas representa um otimizador global e robusto para outros tipos de funções (incluindo funções não convexas com vários mínimos). Não vi, no entanto, sua aplicação a nada maior que algumas centenas de incógnitas.

Observe também que o CG pode ser aplicado em combinação com a regularização de Tikhonov que, de certa forma, torna sua função mais convexa e mais fácil de minimizar, embora à custa de algum viés na solução, o que geralmente é aceitável.

Alexander
fonte