Maximisation globale d'une fonction objectif coûteuse

12

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

AJK
la source
Lorsque vous évaluez la fonction objectif, cela produit-il des informations supplémentaires, en particulier. dérivées (ou approximations) par rapport aux paramètres? Étant donné que la fonction objective elle-même est coûteuse à calculer, il se peut que ces calculs doivent être traites pour des informations supplémentaires.
hardmath
(Un an plus tard), qu'avez-vous fini par faire - varier quelques-uns des 30 paramètres, le modèle ...?
denis
denis: J'ai pu utiliser une certaine intuition physique (et de la chance) pour deviner les paramètres les plus cruciaux, puis les faire varier pour obtenir un résultat "assez bon". (Dans ce cas, trouver l'optimum précis n'était pas aussi important que de trouver une réponse suffisamment grande.) Je n'ai pas fini par avoir besoin de toute la puissance de ces techniques, mais c'est bien de les avoir à portée de main.
AJK
Certes, c'était il y a 2 ans et demi, mais avez-vous un choix de niveau de précision dans votre évaluation de fonction objective (simulation déterministe), et pouvez-vous faire un compromis entre précision et durée d'exécution?
Mark L. Stone,

Réponses:

11

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.

Brian Borchers
la source
4
  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.

Geoff Oxberry
la source
Deux raisons pour lesquelles l'utilisation d'une méthode d'optimisation déterministe sans dérivé pourrait ne pas être judicieuse. Tout d'abord, ce sont des méthodes de recherche locale qui peuvent finir par trouver un maximum local et manquer un bien meilleur point ailleurs dans l'espace des paramètres. Deuxièmement, ces méthodes nécessitent généralement beaucoup d'itérations avec relativement peu d'évaluations de fonctions par itération, de sorte qu'elles ne se parallélisent pas bien.
Brian Borchers
Vous avez raison sur les méthodes de recherche locales. Il existe des méthodes de recherche globale (DIRECT, branche-and-bound, recherche de coordonnées à plusieurs niveaux) qui ne construisent pas de modèles de substitution et devraient se comporter mieux que les méthodes de recherche locales. Je ne peux pas parler de l'efficacité de la parallélisation de ces méthodes.
Geoff Oxberry
1

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.

denfromufa
la source
Bienvenue chez SciComp! Telle qu'elle est rédigée actuellement, votre message n'explique pas vraiment pourquoi regarder TOMLAB ou OpenMDAO serait une bonne idée (d'autres réponses discutent déjà de DAKOTA). Nous recherchons des réponses qui non seulement fournissent des recommandations, mais expliquent pourquoi ces recommandations sont utiles, les pièges potentiels, etc.
Geoff Oxberry
Je me suis précipité avec ma réponse d'abord et maintenant j'ai ajouté une explication.
denfromufa
0

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

denis
la source
-3

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 .

Paul
la source
1
C'est la même réponse que vous avez fournie dans ce post . De plus, il semble que ce soit votre propre travail. Si tel est le cas, veuillez l'indiquer explicitement dans votre réponse.
nicoguaro
Pouvez-vous fournir des détails sur l'approche décrite dans le document et mise en œuvre dans le logiciel? Quelle est la méthode utilisée? Pourquoi est-il bon? Que propose cette approche que les autres réponses ne couvrent pas?
nicoguaro
1
Veuillez également mentionner que vous êtes l'auteur de ce logiciel , donc toute personne qui le lira sera consciente que vous a) savez de quoi vous parlez et b) peut être un peu partiel.
Christian Clason