Maximisation globale d'une fonction objectif coûteuse

Je souhaite maximiser globalement une fonction de nombreux ( ) paramètres réels (résultat d'une simulation complexe). Cependant, la fonction en question est relativement coûteuse à évaluer, nécessitant environ 2 jours pour chaque ensemble de paramètres. Je compare différentes options et je me demandais si quelqu'un avait des suggestions.$\approx 30$

Je sais qu'il existe une série de méthodes pour ce type de processus qui impliquent le développement de fonctions approximatives et leur maximisation (par exemple, Jones et al. "Efficient Global Optimization of Expensive Black-Box Functions" ). Cependant, cela semble être relativement impliqué dans le code.

J'ai la possibilité d'exécuter un grand nombre de simulations en parallèle (50+). Cela semblait suggérer d'utiliser quelque chose comme des algorithmes génétiques pour faire cette optimisation - car je peux créer une population de solutions candidates aussi rapidement que je peux en créer une.

Voici mes questions: 1) Quelqu'un a-t-il des expériences avec des implémentations disponibles gratuitement de ce type de solveurs / recommandations globales? 2) Y a-t-il des raisons de préférer ou d'éviter les algorithmes génétiques ici?

C'est un problème physique, et mes premières expériences ont montré que la valeur du mérite change assez facilement lorsque je change les paramètres.

METTRE À JOUR:

Merci pour l'aide! Encore quelques détails: je n'ai besoin d'aucune information au-delà de l'emplacement du maximum. La simulation est déterministe, pas Monte Carlo, de sorte que la complication n'est pas un gros problème. Il n'y a pas de limites ou contraintes explicites sur les paramètres. Une autre information dont je dispose (et que je n'ai pas mentionnée auparavant) est une idée de la taille du maximum requis. Bien que je recherche un maximum global, je serais également satisfait de tout élément de cette échelle ou plus - je ne sais pas si cela pourrait vous aider. J'espère que si je fais la projection de manière plus systématique (hypercubes latins comme suggéré par Brian Borchers), cela apparaîtra.

Les algorithmes génétiques sont un très mauvais choix lorsque la fonction objective est extrêmement coûteuse à évaluer - ces méthodes nécessitent beaucoup d'évaluations de fonction à chaque génération (ce que le parallélisme peut aider) et beaucoup de générations (qui sont intrinsèquement séquentielles.) À deux jours par génération, ce serait très lent.

Vous n'avez pas mentionné d'où venait ce problème. Analysez-vous statistiquement une surface de vraisemblance (auquel cas vous voudrez plus que les paramètres optimaux et la valeur objective) ou optimisez-vous simplement une fonction objective?

Vous n'avez pas précisé si le calcul de la fonction objectif est précis ou inexact. Il arrive souvent que lorsque la fonction objectif est calculée par simulation Monte Carlo, les valeurs soient assez bruyantes. Cela peut induire en erreur de nombreux algorithmes d'optimisation. Les méthodes de surface de réponse aident à résoudre ce problème en atténuant le bruit.

Vous n'avez mentionné aucune contrainte sur les paramètres. Sont-ils bornés? Existe-t-il des contraintes linéaires ou non linéaires entre les paramètres?

Il est probable que la plupart de vos 30 paramètres ne soient pas vraiment importants pour le problème. Je suggérerais d'utiliser une approche de dépistage de conception expérimentale pour déterminer d'abord lesquels des 30 paramètres sont vraiment importants dans l'optimisation, puis après avoir défini des valeurs raisonnables pour les paramètres sans importance, optimiser les paramètres importants. Des méthodes comme le Latin Hypercube Sampling peuvent être très utiles pour éliminer les paramètres relativement peu importants. Dans cette étape de filtrage, vous pouvez facilement utiliser des centaines de processeurs.

Après avoir réduit le nombre de paramètres à une taille plus raisonnable, j'utiliserais une méthode de surface de réponse pour optimiser les paramètres restants. Si la surface de réponse est vraiment multimodale et que vous utilisez un modèle de surface de réponse trop simple (généralement, les gens s'adaptent simplement à un modèle quadratique), vous pourriez facilement vous tromper et manquer le maximum global. Faites attention! Dans cette étape, vous pouvez à nouveau utiliser de nombreux processeurs en utilisant une conception expérimentale qui offre une très bonne couverture de l'espace des paramètres. Recherchez les points de conception où le modèle ajusté est loin des valeurs calculées - c'est une indication que la surface de réponse ne fonctionne pas bien dans cette région. Vous devrez peut-être créer des surfaces de réponse dans des régions distinctes de l'espace des paramètres.

Comme dernière étape, vous pouvez commencer avec les paramètres de votre optimisation de surface de réponse et essayer d'améliorer les valeurs des paramètres filtrés en les ajustant un par un (descente de coordonnées).

J'appuie la recommandation de DAKOTA comme cadre pour ce type d'optimisation. Si vous ne faites cette optimisation qu'une seule fois, il peut être plus facile d'organiser les calculs à la main, mais si vous le faites à plusieurs reprises, alors DAKOTA serait très utile.

1. Je n'ai aucune expérience avec ces types de solveurs; certains de mes collègues les ont utilisés. DAKOTA semble être le progiciel recommandé pour ce type de tâches. Il comprend une interface qui permet à un utilisateur de soumettre à plusieurs reprises des travaux à une file d'attente de soumission et d'utiliser la sortie pour les études de paramètres, l'analyse de sensibilité, etc. Je ne le connais pas suffisamment pour savoir s'il profitera de l'exécution de nombreuses simulations simultanément.

2. En supposant que vos paramètres sont continus, si la valeur du mérite change en douceur à mesure que les paramètres changent, un modèle de substitution devrait faire un travail raisonnable d'ajustement de la valeur du mérite, et les informations de dérivation de substitution devraient être utiles pour affiner la convergence. Pour 30 paramètres, des méthodes déterministes d'optimisation sans dérivé devraient également être utiles; là encore, la douceur devrait aider. En revanche, les algorithmes génétiques n'utilisent pas du tout d'informations dérivées et nécessitent souvent un réglage des paramètres tels que le taux de mutation, le taux de recombinaison et les paramètres de sélection afin d'obtenir de bonnes performances. En tant que choix algorithmique, j'utiliserais des algorithmes génétiques comme solution de rechange, car je m'attendrais à une optimisation de substitution bien conçue ou à une méthode d'optimisation sans dérivé déterministe pour avoir un meilleur comportement de convergence.

Jetez un œil à TOMLAB, DAKOTA et OpenMDAO pour l'optimisation de la boîte noire.

Edit # 3: L'optimisation bayésienne est très similaire à EGO:

https://github.com/mwhoffman/pybo

https://github.com/hyperopt/hyperopt

licences limitées:

https://github.com/rmcantin/bayesopt

https://github.com/HIPS/Spearmint

Édition n ° 2:

La première approche consiste à créer un métamodèle / substitut (en utilisant le krigeage / GP) autour d'une fonction coûteuse et à utiliser ces informations supplémentaires pour trouver le point optimal global plus rapidement et avec moins d'évaluations (EGO).

La deuxième approche, comme dans MDAS, consiste à effectuer une recherche directe avec des adaptations intelligentes à plusieurs niveaux.

Les approches heuristiques sont de nature génétique / randomisée et sans aucune garantie.

Édition n ° 1:

TOMLAB est un outil basé sur MATLAB qui a la meilleure vitesse / qualité d'optimisation selon le papier de Sahinidis. Mais c'est un outil commercial avec une utilisation importante par les entreprises. Je n'utilise pas ça.

DAKOTA est plus adapté à la quantification de l'incertitude, en plus de l'optimisation générale. Basé sur c ++ et du code Fortran hérité. Bien que sous licence LGPL et binaires disponibles en téléchargement, très difficile à recompiler au moins d'après mon expérience sur Win7 avec GCC ou MSVS / ifort. A des dépendances sur boost, lapack, cmake pour la construction. Fondamentalement, il s'agit d'un wrapper pour de nombreux solveurs open source et peu de commerciaux. Il s'agit d'un produit SNL et est étroitement intégré à d'autres projets de Sandia NL. J'ai réussi à intégrer celui-ci au lieu de certaines routines IMSL. L'article de Sahinidis a raté le parallélisme massif possible avec DAKOTA.

OpenMDAO est un logiciel de conception basé sur l'optimisation développé en Python par la NASA sous licence APACHE. J'essaye ceci actuellement.

Si vous ne pouvez pas vous permettre 30 runs, chacun variant un paramètre, faites-les varier en groupes:
par exemple, 8 runs chacun variant 4 paramètres ensemble, puis affinez les 2 meilleurs runs / 8 paramètres ...
(je ne sais pas comment faire un compromis gain d'informations par rapport à la durée d'exécution totale; bandit multi-bras ?)

Voici un code qui permet d'optimiser efficacement les fonctions de boîte noire coûteuses à l'aide de processeurs multicœurs.

Une description des mathématiques derrière le code est donnée ici .