Maximização global de uma função objetiva dispendiosa

Estou interessado em maximizar globalmente uma função de muitos ( ) parâmetros reais (resultado de uma simulação complexa). No entanto, a função em questão é relativamente cara de avaliar, exigindo cerca de 2 dias para cada conjunto de parâmetros. Estou comparando opções diferentes e queria saber se alguém tinha sugestões.$\approx 30$

Sei que há um conjunto de métodos para esse tipo de processo que envolve o desenvolvimento de funções aproximadas e a maximização (por exemplo, Jones et al. "Otimização global eficiente de funções caras da caixa preta" ). No entanto, isso parece estar relativamente envolvido no código.

Eu tenho a capacidade de executar um grande número de simulações em paralelo (mais de 50). Isso parecia sugerir o uso de algoritmos genéticos para fazer essa otimização - já que eu posso criar uma população de soluções candidatas tão rapidamente quanto possível.

Aqui estão minhas perguntas: 1) Alguém tem experiências com implementações disponíveis gratuitamente desse tipo de solucionadores / recomendações globais? 2) Existem razões para preferir ou evitar algoritmos genéticos aqui?

Esse é um problema físico, e meus primeiros experimentos mostraram que a figura do mérito muda bastante suavemente à medida que eu mudo os parâmetros.

ATUALIZAR:

Obrigado pela ajuda! Mais alguns detalhes: não preciso de nenhuma informação além da localização máxima. A simulação é determinística, não Monte Carlo, de modo que a complicação não é grande coisa. Não há limites ou restrições explícitos nos parâmetros. Uma outra informação que eu tenho (e não mencionei antes) é uma noção do tamanho do máximo necessário. Enquanto procuro um máximo global, também ficaria feliz com qualquer coisa dessa escala ou maior - não sei se isso forneceria alguma ajuda. Felizmente, se eu fizer a triagem de forma mais sistemática (hipercubos em latim, como sugerido por Brian Borchers), isso aparecerá.

Os algoritmos genéticos são uma escolha muito ruim quando a função objetivo é extremamente cara de avaliar - esses métodos exigem muitas avaliações de funções em cada geração (com as quais o paralelismo pode ajudar) e muitas gerações (que são inerentemente sequenciais). Em dois dias por geração, isso seria muito lento.

Você não mencionou de onde veio esse problema. Você está analisando estatisticamente uma superfície de probabilidade (nesse caso, deseja mais do que apenas os parâmetros e valor objetivo ideais) ou apenas otimizando uma função objetiva?

Você não mencionou se o cálculo da função objetivo é preciso ou impreciso. Geralmente, quando a função objetivo é calculada pela simulação de Monte Carlo, os valores são bastante barulhentos. Isso pode enganar muitos algoritmos de otimização. Os métodos de superfície de resposta ajudam a solucionar esse problema, suavizando o ruído.

Você não mencionou nenhuma restrição nos parâmetros. Eles são limitados? Existem restrições lineares ou não lineares entre os parâmetros?

As chances são de que a maioria dos seus 30 parâmetros não seja realmente tão importante para o problema. Eu sugeriria o uso de uma abordagem de triagem de projeto experimental para determinar primeiro quais dos 30 parâmetros são realmente importantes na otimização e, depois de definir valores razoáveis ​​para os parâmetros sem importância, otimizar sobre os parâmetros importantes. Métodos como o Latin Hypercube Sampling podem ser muito úteis na triagem de parâmetros relativamente sem importância. Nesta etapa de triagem, você pode facilmente usar centenas de processadores.

Depois de reduzir o número de parâmetros para um tamanho mais razoável, eu usaria um método de superfície de resposta para otimizar os parâmetros restantes. Se a superfície de resposta realmente for multimodal e você usar um modelo de superfície de resposta excessivamente simples (normalmente as pessoas se encaixam em um modelo quadrático), poderá facilmente enganar e perder o máximo global. Seja cuidadoso! Nesse estágio, você pode novamente usar muitos processadores usando um design experimental que oferece uma cobertura muito boa do espaço dos parâmetros. Procure pontos de projeto em que o modelo ajustado esteja longe dos valores calculados - isso é uma indicação de que a superfície de resposta não está funcionando bem nessa região. Pode ser necessário criar superfícies de resposta em regiões separadas do espaço de parâmetros.

Como último passo, você pode começar com os parâmetros da otimização da superfície de resposta e tentar melhorar os valores dos parâmetros filtrados, ajustando-os um de cada vez (descida de coordenadas).

Em segundo lugar, recomendarei o DAKOTA como uma estrutura para esse tipo de otimização. Se você estiver fazendo essa otimização apenas uma vez, pode ser mais fácil organizar os cálculos manualmente, mas se você fizer isso repetidamente, o DAKOTA será muito útil.

1. Eu não tenho nenhuma experiência com esse tipo de solucionador; alguns dos meus colegas de trabalho já os usaram. O DAKOTA parece ser o pacote de software recomendado para esse tipo de tarefa. Inclui uma interface que permite ao usuário enviar trabalhos repetidamente para uma fila de envio e usar a saída para estudos de parâmetros, análise de sensibilidade etc. Não estou familiarizado o suficiente para saber se ele vai ou não tirar vantagem da execução de muitas simulações simultaneamente.

2. Supondo que seus parâmetros sejam contínuos, se a figura de mérito mudar suavemente à medida que os parâmetros forem alterados, um modelo substituto deve fazer um trabalho razoável para ajustar a figura de mérito, e as informações derivadas substitutas devem ser úteis para refinar a convergência. Para 30 parâmetros, métodos determinísticos de otimização sem derivadas também devem ser úteis; lá novamente, a suavidade deve ajudar. Por outro lado, os algoritmos genéticos não usam informações derivadas e geralmente exigem ajustes de parâmetros como taxa de mutação, taxa de recombinação e parâmetros de seleção para obter um bom desempenho. Como uma opção algorítmica, eu usaria algoritmos genéticos como substituto, porque esperaria que uma otimização substituta bem projetada ou um método determinístico de otimização livre de derivado determinístico tivesse um melhor comportamento de convergência.

Dê uma olhada no TOMLAB, DAKOTA e OpenMDAO para otimização da caixa preta.

Edit # 3: A otimização bayesiana é muito semelhante ao EGO:

https://github.com/mwhoffman/pybo

https://github.com/hyperopt/hyperopt

licenças limitadas:

https://github.com/rmcantin/bayesopt

https://github.com/HIPS/Spearmint

Edição # 2:

A primeira abordagem é criar um metamodelo / substituto (usando o kriging / GP) em torno de uma função cara e usar essas informações adicionais para encontrar o ponto ideal global mais rapidamente e com menos avaliações (EGO).

A segunda abordagem, como no MDAS, é fazer pesquisa direta com algumas adaptações inteligentes em vários níveis.

As abordagens heurísticas são de natureza genética / aleatória e sem garantias.

Edição nº 1:

O TOMLAB é uma ferramenta baseada no MATLAB que possui a melhor velocidade / qualidade de otimização, de acordo com o artigo de Sahinidis. Mas esta é uma ferramenta comercial com uso corporativo significativo. Eu não estou usando isso.

O DAKOTA é mais adaptado para Quantificação de Incerteza, além de otimização geral. Baseado em c ++ e algum código legado do Fortran. Embora com a licença LGPL e os binários disponíveis para download, é muito difícil recompilar pelo menos minha experiência no Win7 com GCC ou MSVS / ifort. Tem dependências de impulso, lapack, cmake para compilação. Basicamente, este é um invólucro para numerosos solucionadores de código aberto e poucos comerciais. Este é um produto SNL e está totalmente integrado a outros projetos da Sandia NL. Consegui integrar esse com êxito em vez de algumas rotinas IMSL. O jornal de Sahinidis perdeu o paralelismo maciço possível com DAKOTA.

O OpenMDAO é um software de design baseado em otimização desenvolvido em Python pela NASA sob a licença APACHE. Estou tentando isso atualmente.

Se você não puder pagar 30 execuções, cada uma variando um parâmetro, varie-as em grupos:
por exemplo, 8 executa cada uma variando 4 parâmetros juntos, depois refine as melhores 2 execuções / 8 parâmetros ...
(não tenho idéia de como trocar ganho de informação vs. tempo de execução total; bandido com vários braços ?)

Aqui está um código que permite otimizar eficientemente as funções caras da caixa preta usando CPUs multicore.

Uma descrição da matemática por trás do código é fornecida aqui .