Ich arbeite daran, den Optimierungsprozess einiger demografischer Modellierungssoftware zu verbessern, damit demografische Modelle besser an Daten angepasst werden können. Wir möchten die Optimierungszeit verkürzen.
Die Zeit, die zur Bewertung unserer Zielfunktion benötigt wird, hängt stark von den Eingabewerten ab. Die Beziehung zwischen der Zeit zur Bewertung der Zielfunktion und der Eingabe ist bekannt. Ich frage mich, ob es Optimierungsmethoden gibt, die die relativen Zeitkosten der Zielfunktion bei der Auswahl der zu bewertenden Punkte berücksichtigen.
Vielen Dank!
Aktualisieren:
Wie Paulus verlangt hat, sind hier einige herausragende Merkmale dieser besonderen Zielfunktion:
- Die Anzahl der Parameter ist moderat (~ 12ish)
- Unser Problem ist nicht konvex, oder zumindest gibt es schmale und flache "Grate" in der Zielfunktionsoberfläche. Im Moment beschäftigen wir uns mit mehreren Optimierungen von verschiedenen Punkten aus, aber wir würden es gerne besser machen.
- Die Zielfunktion ist ziemlich glatt, obwohl wir nur Näherungen mit endlichen Differenzen an Ableitungen berechnen können.
- Die Bewertungskosten sind auch eine reibungslose Funktion der Parameterwerte und ziemlich vorhersehbar. Grob gesagt sind für jeden Parameter die zu bewertenden Kosten an einem Ende des Bereichs hoch und am anderen Ende niedrig. Wir haben also große Regionen mit teuer zu bewertenden Parametersätzen, aber wir wissen, wo sie sich befinden.
optimization
Nova
quelle
quelle
Antworten:
Ein üblicher Ansatz für den Umgang mit teuren Zielfunktionen besteht darin, (z. B. durch Regressionsmodellierung) ein "Antwortoberflächenmodell" zu erstellen, das sich der ursprünglichen Zielfunktion annähert, und dann über diese Antwortoberfläche zu optimieren, anstatt mit der ursprünglichen Funktion zu arbeiten. In der Praxis sind die Antwortflächen typischerweise nur quadratische Modelle, die durch Regression angepasst werden, so dass das Finden eines Minimums der Antwortfläche zu einem sehr einfachen Optimierungsproblem wird.
Sie haben nichts über die Glätte oder Konvexität Ihrer Zielfunktion gesagt. Wenn die Funktion nicht glatt oder nicht konvex ist, wird dies offensichtlich sehr viel schwieriger.
Sie haben auch nichts darüber gesagt, wo sich die teuren Punkte in Ihrem Parameterraum befinden. Wenn sie zufällig im Parameterraum verteilt sind, können Sie mithilfe von Entwurfstechniken Ihr Antwortoberflächenmodell erstellen und dabei die teuren Punkte vermeiden. Wenn es größere Bereiche des Parameterraums gibt, in denen Auswertungen teuer sind, können Sie versuchen, die Anzahl der Punkte in den Bereichen zu minimieren, die Sie beim Erstellen des Antwortoberflächenmodells verwenden. Wenn sich Ihr Optimum in der Mitte einer solchen Region befindet, sind Sie natürlich dazu verdammt, Funktionen in der teuren Region zu bewerten.
quelle
Ich kenne keine Methoden, die speziell die relativen Kosten für die Bewertung des Ziels an verschiedenen Testpunkten abwägen. Wenn Sie jedoch relativ zuverlässig vorhersagen können, ob die Bewertung eines Kandidaten teuer ist oder nicht, kann ich vorschlagen, einen Versuch zu unternehmen direkte Methode . Direkte Methoden passen in die Familie der derivatfreien Methoden. Es ist nicht unbedingt eine schlechte Sache, sie zu verwenden, selbst wenn Sie den Verdacht haben, dass Ihr Problem ziemlich reibungslos ist, da sie ein gewisses Maß an Flexibilität bieten können, das Methoden für eine reibungslose Optimierung nicht bieten können.
Die Idee ist, dass direkte Methoden ein (iterationsabhängiges) Netz über die aktuelle Iteration und einen (iterationsabhängigen) Netz- "Schritt" definieren. Basierend auf diesem Netzschritt bestimmt die Methode die Versuchspunkte auf dem Netz, die Nachbarn der aktuellen Iteration sind (sie liegen auf dem Netz und befinden sich in einem durch den Netzschritt definierten Abstand). Anschließend wird das Ziel bei den Nachbarn bewertet. Sobald ein besserer Kandidat gefunden wird, wird er zur neuen aktuellen Iteration. Nach Ihrer Wahl können Sie auch alle Nachbarn bewerten und die besten auswählen.
In Ihrem Fall könnte es eine gute Idee sein, die Nachbarn auf der Grundlage Ihrer Schätzung der Kosten für die Bewertung des Ziels dort zu bestellen. Bewerten Sie sie in dieser Reihenfolge und wählen Sie den ersten Erfolg als nächste Iteration aus. Intuitiv bevorzugen Sie billige Kandidaten. Bei der direkten Methoden, passen solche Anordnungen ihm die Kategorie der Ersatzmodelle , ein Konzept , das verallgemeinert , dass ein Antwort Oberflächenmodell von Brian erwähnt.
Hier ist eine hervorragende Implementierung einer direkten Methode (in C ++): http://www.gerad.ca/nomad/Project/Home.html
Wenn dies vielversprechende Ergebnisse liefert, können Sie sich gerne an mich wenden, und ich kann möglicherweise weitere Verbesserungen vorschlagen.
Ich glaube, NOMAD bietet auch Funktionen für die globale Optimierung (z. B. den Multi-Start, den Sie derzeit anwenden), die auf dem Konzept der variablen Nachbarschaftssuche basieren .
quelle