Je travaille sur l'amélioration du processus d'optimisation de certains logiciels de modélisation démographique afin qu'ils puissent mieux adapter les modèles démographiques aux données. Nous aimerions réduire le temps d'optimisation.
Le temps qu'il faut pour évaluer notre fonction objectif varie beaucoup, selon les valeurs d'entrée. La relation entre le temps pour évaluer la fonction objectif et l'entrée est connue. Je me demande s'il existe des méthodes d'optimisation qui tiennent compte du coût relatif en temps de la fonction objectif lors du choix des points à évaluer.
Merci!
Mise à jour:
Comme Paul l'a demandé, voici quelques traits saillants de cette fonction objective particulière:
- Le nombre de paramètres est modéré (~ 12ish)
- Notre problème est non convexe, ou du moins il y a des "crêtes" étroites et plates dans la surface de la fonction objectif. En ce moment, nous traitons cela en utilisant plusieurs optimisations à partir de différents points, mais nous aimerions faire mieux.
- La fonction objectif est assez lisse, bien que nous ne puissions calculer que des approximations de différences finies avec des dérivés.
- Le coût d'évaluation est également une fonction fluide des valeurs des paramètres, et il est tout à fait prévisible. grosso modo, pour chaque paramètre, le coût à évaluer est élevé à une extrémité de la fourchette et faible à l'autre extrémité. Nous avons donc de grandes régions d'ensembles de paramètres coûteux à évaluer, mais nous savons où ils se trouvent.
optimization
nova
la source
la source
Réponses:
Une approche courante pour traiter des fonctions objectives coûteuses consiste à construire (par exemple, par modélisation de régression) un "modèle de surface de réponse" qui se rapproche de la fonction objectif d'origine, puis à optimiser sur cette surface de réponse plutôt que de travailler avec la fonction d'origine. En pratique, les surfaces de réponse ne sont généralement que des modèles quadratiques ajustés par régression, donc trouver un minimum de la surface de réponse devient un problème d'optimisation très facile.
Vous n'avez rien dit sur la fluidité ou la convexité de votre fonction objectif. Si la fonction est non lisse ou non convexe, cela devient évidemment beaucoup plus difficile.
Vous n'avez également rien dit sur l'emplacement des points coûteux dans votre espace de paramètres. S'ils sont répartis de façon aléatoire dans l'espace des paramètres, vous pouvez utiliser des techniques de conception d'expériences pour construire votre modèle de surface de réponse tout en évitant les points coûteux. S'il existe des régions plus grandes de l'espace des paramètres où les évaluations sont coûteuses, vous pouvez essayer de minimiser le nombre de points dans les zones que vous utilisez pour construire le modèle de surface de réponse. Bien sûr, si votre optimum est situé au milieu d'une telle région, vous allez être voué à l'évaluation des fonctions dans la région chère.
la source
Je ne connais pas de méthodes qui pèsent spécifiquement sur les coûts relatifs de l'évaluation de l'objectif à différents points d'essai, mais si vous êtes en mesure de prédire de manière relativement fiable si un candidat sera coûteux à évaluer ou non, alors je pourrais suggérer d'essayer un méthode directe . Les méthodes directes s'inscrivent dans la famille des méthodes sans dérivé. Ce n'est pas nécessairement une mauvaise chose de les utiliser même si vous pensez que votre problème est assez fluide car ils peuvent fournir un certain niveau de flexibilité que les méthodes d'optimisation fluide ne peuvent pas.
L'idée est que les méthodes directes définissent un maillage (dépendant de l'itération) autour de l'itération actuelle et un "pas" de maillage (dépendant de l'itération). Sur la base de cette étape du maillage, la méthode détermine les points d'essai sur le maillage qui sont voisins de l'itération actuelle (ils se trouvent sur le maillage et sont à une distance définie par l'étape du maillage). Il procédera ensuite à l'évaluation de l'objectif chez les voisins. Dès qu'un meilleur candidat est trouvé, il devient le nouvel itération actuel. À votre choix, vous pouvez également évaluer tous les voisins et choisir le meilleur.
Dans votre cas, ce pourrait être une bonne idée de commander les voisins en fonction de votre estimation du coût de l'évaluation de l'objectif là-bas. Évaluez-les dans cet ordre et choisissez le premier succès lors de la prochaine itération. Intuitivement, vous privilégiez les candidats bon marché. Dans les méthodes directes, ces ordonnances correspondent à la catégorie des modèles de substitution , un concept qui généralise celui d'un modèle de surface de réponse mentionné par Brian.
Voici une excellente implémentation d'une méthode directe (en C ++): http://www.gerad.ca/nomad/Project/Home.html
Si cela semble donner des résultats prometteurs, n'hésitez pas à me contacter et je pourrai peut-être suggérer d'autres améliorations.
Je crois que NOMAD possède également des fonctionnalités d'optimisation globale (telles que le multi-démarrage que vous appliquez actuellement) basées sur le concept de recherche de voisinage variable .
la source