Globale Maximierung der teuren Zielfunktion

12

Ich bin daran interessiert, eine Funktion vieler ( ) realer Parameter (ein Ergebnis einer komplexen Simulation) global zu maximieren . Die Bewertung der betreffenden Funktion ist jedoch relativ teuer und erfordert für jeden Parametersatz etwa 2 Tage. Ich vergleiche verschiedene Optionen und habe mich gefragt, ob jemand Vorschläge hat.30

Ich weiß, dass es eine Reihe von Methoden für diese Art von Prozess gibt, bei denen ungefähre Funktionen entwickelt und diese dann maximiert werden (z . B. Jones et al. "Effiziente globale Optimierung teurer Black-Box-Funktionen" ). Dies scheint jedoch relativ mit dem Code verbunden zu sein.

Ich habe die Möglichkeit, eine große Anzahl von Simulationen parallel auszuführen (50+). Dies schien darauf hinzudeuten, so etwas wie genetische Algorithmen zu verwenden, um diese Optimierung durchzuführen - da ich eine Population von Kandidatenlösungen genauso schnell erstellen kann, wie ich eine erstellen kann.

Hier sind meine Fragen: 1) Hat jemand Erfahrungen mit frei verfügbaren Implementierungen dieser Art von globalen Lösern / Empfehlungen? 2) Gibt es Gründe, hier genetische Algorithmen zu bevorzugen oder zu vermeiden?

Dies ist ein physikalisches Problem, und meine frühen Experimente haben gezeigt, dass sich die Zahl der Verdienste ziemlich reibungslos ändert, wenn ich die Parameter ändere.

AKTUALISIEREN:

Danke für die Hilfe! Noch ein paar Details: Ich benötige keine Informationen über den Ort des Maximums hinaus. Die Simulation ist deterministisch, nicht Monte Carlo, so dass Komplikationen keine große Sache sind. Es gibt keine expliziten Grenzen oder Einschränkungen für die Parameter. Eine andere Information, die ich habe (und die ich vorher nicht erwähnt habe), ist ein Gefühl für die Größe des maximal erforderlichen Maximums. Während ich nach einem globalen Maximum suche, würde ich mich auch über etwas in dieser Größenordnung oder darüber freuen - ich weiß nicht, ob dies helfen würde. Wenn ich das Screening systematischer durchführe (lateinische Hyperwürfel, wie von Brian Borchers vorgeschlagen), wird dies hoffentlich angezeigt.

AJK
quelle
Wenn Sie die Zielfunktion bewerten, werden zusätzliche Informationen erzeugt, insbesondere Ableitungen (oder Näherungen) in Bezug auf Parameter? Da die Berechnung der Zielfunktion selbst teuer ist, müssen solche Berechnungen möglicherweise für zusätzliche Informationen gemolken werden.
Hardmath
(Ein Jahr später), was haben Sie am Ende getan - einige der 30 Parameter, Modell ... variiert?
Denis
denis: Ich konnte mit etwas körperlicher Intuition (und Glück) die wichtigsten Parameter erraten und sie dann variieren, um ein "gut genug" Ergebnis zu erzielen. (In diesem Fall war es nicht so wichtig, das genaue Optimum zu finden, wie eine ausreichend große Antwort zu finden.) Ich brauchte nicht die volle Kraft dieser Techniken, aber es ist gut, sie zur Hand zu haben.
AJK
Zugegeben, das war vor 2 1/2 Jahren, aber haben Sie eine Auswahl an Genauigkeitsstufen in Ihrer objektiven Funktionsbewertung (deterministische Simulation) und können Genauigkeit gegen Laufzeit abwägen?
Mark L. Stone

Antworten:

11

Genetische Algorithmen sind eine sehr schlechte Wahl, wenn die Bewertung der Zielfunktion extrem teuer ist. Diese Methoden erfordern viele Funktionsbewertungen in jeder Generation (bei denen Parallelität hilfreich sein kann) und viele Generationen (die von Natur aus sequentiell sind). Nach zwei Tagen pro Generation wäre dies sehr langsam.

Sie haben nicht erwähnt, woher dieses Problem stammt. Analysieren Sie statistisch eine Wahrscheinlichkeitsfläche (in diesem Fall möchten Sie mehr als nur die optimalen Parameter und den Zielwert) oder optimieren Sie nur eine Zielfunktion?

Sie haben nicht erwähnt, ob die Berechnung der Zielfunktion präzise oder ungenau ist. Es ist häufig der Fall, dass bei der Berechnung der Zielfunktion durch Monte-Carlo-Simulation die Werte ziemlich verrauscht sind. Dies kann viele Optimierungsalgorithmen irreführen. Reaktionsoberflächenmethoden helfen bei diesem Problem, indem sie das Rauschen glätten.

Sie haben keine Einschränkungen für die Parameter erwähnt. Sind sie begrenzt? Gibt es lineare oder nichtlineare Einschränkungen zwischen den Parametern?

Wahrscheinlich sind die meisten Ihrer 30 Parameter für das Problem nicht so wichtig. Ich würde vorschlagen, einen experimentellen Design-Screening-Ansatz zu verwenden, um zuerst zu bestimmen, welche der 30 Parameter für die Optimierung wirklich wichtig sind, und dann nach dem Festlegen angemessener Werte für die unwichtigen Parameter über die wichtigen Parameter zu optimieren. Methoden wie Latin Hypercube Sampling können sehr hilfreich sein, um die relativ unwichtigen Parameter herauszufiltern. In dieser Screening-Phase können Sie problemlos Hunderte von Prozessoren verwenden.

Nachdem ich die Anzahl der Parameter auf eine vernünftigere Größe reduziert habe, würde ich eine Antwortoberflächenmethode verwenden, um die verbleibenden Parameter zu optimieren. Wenn die Antwortfläche wirklich multimodal ist und Sie ein zu einfaches Antwortoberflächenmodell verwenden (normalerweise passen die Leute nur zu einem quadratischen Modell), können Sie leicht irregeführt werden und das globale Maximum verpassen. Achtung! In dieser Phase können Sie wieder viele Prozessoren verwenden, indem Sie ein experimentelles Design verwenden, das eine sehr gute Abdeckung des Parameterraums bietet. Suchen Sie nach Entwurfspunkten, an denen das angepasste Modell weit von den berechneten Werten entfernt ist. Dies ist ein Hinweis darauf, dass die Antwortfläche in dieser Region nicht gut funktioniert. Möglicherweise müssen Sie Antwortoberflächen in separaten Bereichen des Parameterraums erstellen.

Als letzten Schritt können Sie mit den Parametern Ihrer Antwortoberflächenoptimierung beginnen und versuchen, die Werte der ausgelagerten Parameter zu verbessern, indem Sie sie einzeln anpassen (Koordinatenabstieg).

Ich werde die Empfehlung von DAKOTA als Rahmen für diese Art der Optimierung unterstützen. Wenn Sie diese Optimierung nur einmal durchführen, ist es möglicherweise einfacher, die Berechnungen von Hand zu organisieren. Wenn Sie sie jedoch wiederholt durchführen, ist DAKOTA sehr hilfreich.

Brian Borchers
quelle
4
  1. Ich habe keine Erfahrung mit solchen Lösern. Einige meiner Mitarbeiter haben sie benutzt. DAKOTA scheint das für diese Art von Aufgaben empfohlene Softwarepaket zu sein. Es enthält eine Schnittstelle, über die ein Benutzer Jobs wiederholt an eine Übermittlungswarteschlange senden und die Ausgabe für Parameterstudien, Sensitivitätsanalysen usw. verwenden kann. Ich bin nicht vertraut genug damit, um zu wissen, ob viele Simulationen ausgeführt werden können oder nicht gleichzeitig.

  2. Unter der Annahme, dass Ihre Parameter stetig sind, sollte sich ein Ersatzmodell angemessen an die Gütezahl anpassen, wenn sich die Gütezahl reibungslos ändert, wenn sich die Parameter ändern, und Informationen zu Ersatzableitungen sollten hilfreich sein, um die Konvergenz zu verfeinern. Für 30 Parameter sollten auch deterministische ableitungsfreie Optimierungsmethoden nützlich sein. Auch hier sollte Geschmeidigkeit helfen. Im Gegensatz dazu verwenden genetische Algorithmen überhaupt keine abgeleiteten Informationen und erfordern häufig die Abstimmung von Parametern wie Mutationsrate, Rekombinationsrate und Selektionsparametern, um eine gute Leistung zu erzielen. Als algorithmische Wahl würde ich genetische Algorithmen als Fallback verwenden, da ich erwarten würde, dass eine gut konzipierte Ersatzoptimierung oder eine deterministische derivatfreie Optimierungsmethode ein besseres Konvergenzverhalten aufweist.

Geoff Oxberry
quelle
Einige Gründe, warum die Verwendung einer deterministischen, derivatfreien Optimierungsmethode möglicherweise nicht sinnvoll ist. Erstens sind dies lokale Suchmethoden, die möglicherweise ein lokales Maximum finden und an anderer Stelle im Parameterraum einen viel besseren Punkt verfehlen. Zweitens erfordern diese Methoden normalerweise viele Iterationen mit relativ wenigen Funktionsbewertungen pro Iteration, sodass sie nicht gut parallelisiert werden.
Brian Borchers
Sie haben Recht mit lokalen Suchmethoden. Es gibt globale Suchmethoden (DIREKTE, verzweigte und mehrstufige Koordinatensuche), die keine Ersatzmodelle erstellen und sich besser verhalten sollten als lokale Suchmethoden. Ich kann nicht über die Wirksamkeit der Parallelisierung dieser Methoden sprechen.
Geoff Oxberry
1

Schauen Sie sich TOMLAB, DAKOTA und OpenMDAO für die Black-Box-Optimierung an.


Edit # 3: Die Bayes'sche Optimierung ist EGO sehr ähnlich:

https://github.com/mwhoffman/pybo

https://github.com/hyperopt/hyperopt

begrenzte Lizenzen:

https://github.com/rmcantin/bayesopt

https://github.com/HIPS/Spearmint


Edit # 2:

Der erste Ansatz besteht darin, ein Metamodell / Ersatz (unter Verwendung von Kriging / GP) um eine teure Funktion herum zu erstellen und diese zusätzlichen Informationen zu verwenden, um den globalen optimalen Punkt schneller und mit weniger Bewertungen (EGO) zu finden.

Der zweite Ansatz wie in MDAS besteht darin, eine direkte Suche mit einigen cleveren Anpassungen auf mehreren Ebenen durchzuführen.

Heuristische Ansätze sind genetischer / randomisierter Natur und ohne Garantie.


Edit # 1:

TOMLAB ist ein MATLAB-basiertes Tool, das laut Sahinidis 'Artikel die beste Geschwindigkeit / Qualität der Optimierung aufweist. Dies ist jedoch ein kommerzielles Tool mit erheblicher Unternehmensnutzung. Ich benutze das nicht.

DAKOTA ist neben der allgemeinen Optimierung eher auf die Quantifizierung von Unsicherheiten zugeschnitten. Basierend auf c ++ und etwas altem Fortran-Code. Obwohl unter LGPL-Lizenz und Binärdateien zum Download verfügbar, ist es zumindest aus meiner Erfahrung mit Win7 mit GCC oder MSVS / ifort sehr schwierig, diese neu zu kompilieren. Hat Abhängigkeiten von Boost, Lapack, cmake für Build. Grundsätzlich ist dies ein Wrapper für zahlreiche Open-Source-Löser und wenige kommerzielle. Dies ist ein SNL-Produkt und eng in andere Projekte von Sandia NL integriert. Ich konnte diese anstelle einiger IMSL-Routinen erfolgreich integrieren. Sahinidis 'Artikel verfehlte die massive Parallelität, die mit DAKOTA möglich ist.

OpenMDAO ist eine optimierungsbasierte Design-Software, die von der NASA in Python unter der APACHE-Lizenz entwickelt wurde. Ich probiere das gerade aus.

denfromufa
quelle
Willkommen bei SciComp! Wie derzeit geschrieben, erklärt Ihr Beitrag nicht wirklich, warum ein Blick auf TOMLAB oder OpenMDAO eine gute Idee wäre (andere Antworten diskutieren bereits DAKOTA). Wir suchen nach Antworten, die nicht nur Empfehlungen liefern, sondern auch diskutieren, warum diese Empfehlungen nützlich sind, potenzielle Fallstricke usw.
Geoff Oxberry
Ich beeilte mich zuerst mit meiner Antwort und fügte jetzt eine Erklärung hinzu.
Denfromufa
0

Wenn Sie sich 30 Läufe mit jeweils einem Parameter nicht leisten können, variieren Sie sie in Gruppen:
Zum Beispiel 8 Läufe mit jeweils 4 Parametern zusammen, dann verfeinern Sie die besten 2 Läufe / 8 Parameter ...
(Ich habe keine Ahnung, wie ich einen Kompromiss eingehen soll Infogewinn vs. Gesamtlaufzeit; mehrarmiger Bandit ?)

denis
quelle
-3

Hier ist ein Code , mit dem teure Black-Box-Funktionen mithilfe von Multicore-CPUs effizient optimiert werden können.

Eine Beschreibung der Mathematik hinter dem Code finden Sie hier .

Paul
quelle
1
Dies ist die gleiche Antwort, die Sie in diesem Beitrag gegeben haben . Es scheint auch, dass dies Ihre eigene Arbeit ist. Wenn dies zutrifft, geben Sie dies bitte ausdrücklich in Ihrer Antwort an.
Nicoguaro
Können Sie Details zu dem in diesem Dokument beschriebenen und in der Software implementierten Ansatz angeben? Was ist die verwendete Methode? Warum ist es gut? Was wird in diesem Ansatz bereitgestellt, das in den anderen Antworten nicht behandelt wird?
Nicoguaro
1
Bitte erwähnen Sie auch, dass Sie der Autor dieser Software sind , damit jeder, der dies liest, weiß, dass Sie a) wissen, wovon Sie sprechen, und b) möglicherweise etwas parteiisch sind.
Christian Clason