scipy.optimize.

basinhopping#

scipy.optimize.basinhopping(func, x0, niter=100, T=1.0, stepsize=0.5, minimizer_kwargs=None, take_step=None, accept_test=None, callback=None, interval=50, disp=False, niter_success=None, rng=None, *, target_accept_rate=0.5, stepwise_factor=0.9)[Quelle]#

Findet das globale Minimum einer Funktion mithilfe des Basin-Hopping-Algorithmus.

Basin-Hopping ist eine zweiphasige Methode, die einen globalen Schrittalgorithmus mit einer lokalen Minimierung in jedem Schritt kombiniert. Sie wurde entwickelt, um den natürlichen Prozess der Energie minimization von Atomclustern zu imitieren, und eignet sich gut für ähnliche Probleme mit „trichterförmigen, aber rauen“ Energielandschaften [5].

Da die Schrittauswahl, die Schrittakzeptanz und die Minimierungsmethoden alle anpassbar sind, kann diese Funktion auch zur Implementierung anderer zweiphasiger Methoden verwendet werden.

Parameter:
funccallable f(x, *args)

Zu optimierende Funktion. args kann als optionales Element im Dict minimizer_kwargs übergeben werden.

x0array_like

Anfangsschätzung.

niterinteger, optional

Die Anzahl der Basin-Hopping-Iterationen. Insgesamt werden niter + 1 Durchläufe des lokalen Minimierers durchgeführt.

Tfloat, optional

Der „Temperatur“-Parameter für das Akzeptanz- oder Ablehnkriterium. Höhere „Temperaturen“ bedeuten, dass größere Sprünge im Funktionswert akzeptiert werden. Für beste Ergebnisse sollte T vergleichbar mit der Trennung (im Funktionswert) zwischen lokalen Minima sein.

stepsizefloat, optional

Maximale Schrittgröße für die zufällige Verschiebung.

minimizer_kwargsdict, optional

Zusätzliche Schlüsselwortargumente, die an den lokalen Minimierer scipy.optimize.minimize übergeben werden. Einige wichtige Optionen könnten sein:

methodstr

Die Minimierungsmethode (z. B. "L-BFGS-B").

argstuple

Zusätzliche Argumente, die an die Zielfunktion (func) und ihre Ableitungen (Jakobi-Matrix, Hesse-Matrix) übergeben werden.

take_stepcallable take_step(x), optional

Ersetzt die Standard-Schrittroutine durch diese Routine. Die Standard-Schrittroutine ist eine zufällige Verschiebung der Koordinaten, aber andere Schrittalgorithmen können für einige Systeme besser geeignet sein. take_step kann optional das Attribut take_step.stepsize haben. Wenn dieses Attribut vorhanden ist, passt basinhopping take_step.stepsize an, um die globale Minimumsuche zu optimieren.

accept_testcallable, accept_test(f_new=f_new, x_new=x_new, f_old=fold, x_old=x_old), optional

Definiert einen Test, der verwendet wird, um zu beurteilen, ob ein Schritt akzeptiert werden soll. Dieser wird zusätzlich zum Metropolis-Test basierend auf der „Temperatur“ T verwendet. Akzeptable Rückgabewerte sind True, False oder "force accept". Wenn einer der Tests False zurückgibt, wird der Schritt abgelehnt. Im letzteren Fall werden alle anderen Tests überschrieben, um den Schritt zu akzeptieren. Dies kann beispielsweise verwendet werden, um aus einem lokalen Minimum auszubrechen, in dem basinhopping gefangen ist.

callbackcallable, callback(x, f, accept), optional

Eine Callback-Funktion, die für alle gefundenen Minima aufgerufen wird. x und f sind die Koordinaten und der Funktionswert des getesteten Minimums, und accept gibt an, ob dieses Minimum akzeptiert wurde. Dies kann beispielsweise verwendet werden, um die N niedrigsten gefundenen Minima zu speichern. Außerdem kann callback verwendet werden, um ein benutzerdefiniertes Abbruchkriterium anzugeben, indem optional True zurückgegeben wird, um die basinhopping-Routine zu stoppen.

intervalinteger, optional

Intervall, wie oft die stepsize aktualisiert werden soll.

dispbool, optional

Auf True setzen, um Statusmeldungen auszugeben.

niter_successinteger, optional

Beendet den Lauf, wenn der globale Kandidaten-Minimum für diese Anzahl von Iterationen unverändert bleibt.

rng{None, int, numpy.random.Generator}, optional

Wenn rng als Schlüsselwort übergeben wird, werden andere Typen als numpy.random.Generator an numpy.random.default_rng übergeben, um einen Generator zu instanziieren. Wenn rng bereits eine Generator-Instanz ist, dann wird die bereitgestellte Instanz verwendet. Geben Sie rng für reproduzierbares Funktionsverhalten an.

Wenn dieses Argument positionsabhängig übergeben wird oder seed als Schlüsselwort übergeben wird, gilt das Legacy-Verhalten für das Argument seed.

  • Wenn seed None ist (oder numpy.random), wird die Singleton-Instanz von numpy.random.RandomState verwendet.

  • Wenn seed eine Ganzzahl ist, wird eine neue RandomState-Instanz mit seed verwendet.

  • Wenn seed bereits eine Generator- oder RandomState-Instanz ist, dann wird diese Instanz verwendet.

Geändert in Version 1.15.0: Als Teil des SPEC-007-Übergangs von der Verwendung von numpy.random.RandomState zu numpy.random.Generator wurde dieses Schlüsselwort von seed zu rng geändert. Für eine Übergangszeit werden beide Schlüsselwörter weiterhin funktionieren, obwohl nur eines gleichzeitig angegeben werden kann. Nach der Übergangszeit geben Funktionsaufrufe mit dem Schlüsselwort seed Warnungen aus. Das Verhalten von seed und rng wird oben skizziert, aber nur das rng-Schlüsselwort sollte in neuem Code verwendet werden.

Die generierten Zufallszahlen beeinflussen nur den Standard-Metropolis-Test accept_test und die Standard-Schrittroutine take_step. Wenn Sie Ihre eigene take_step und accept_test bereitstellen und diese Funktionen Zufallszahlengenerierung verwenden, sind diese Funktionen für den Zustand ihres Zufallszahlengenerators verantwortlich.

target_accept_ratefloat, optional

Die Zielakzeptanzrate, die zur Anpassung der stepsize verwendet wird. Wenn die aktuelle Akzeptanzrate höher als das Ziel ist, wird die stepsize erhöht. Andernfalls wird sie verringert. Bereich ist (0, 1). Standard ist 0,5.

Hinzugefügt in Version 1.8.0.

stepwise_factorfloat, optional

Die stepsize wird bei jeder Aktualisierung mit diesem schrittweisen Faktor multipliziert oder dividiert. Bereich ist (0, 1). Standard ist 0,9.

Hinzugefügt in Version 1.8.0.

Rückgabe:
resOptimizeResult

Das Optimierungsergebnis, dargestellt als OptimizeResult-Objekt. Wichtige Attribute sind: x das Lösungsarray, fun der Funktionswert an der Lösung und message, das den Abbruchgrund beschreibt. Das von dem ausgewählten Minimierer am niedrigsten Minimum zurückgegebene OptimizeResult-Objekt ist ebenfalls in diesem Objekt enthalten und über das Attribut lowest_optimization_result zugänglich. lowest_optimization_result wird nur aktualisiert, wenn eine lokale Minimierung erfolgreich war. Siehe OptimizeResult für eine Beschreibung anderer Attribute.

Siehe auch

minimieren

Die lokale Minimierungsfunktion, die einmal pro Basin-Hopping-Schritt aufgerufen wird. minimizer_kwargs wird an diese Routine übergeben.

Hinweise

Basin-Hopping ist ein stochastischer Algorithmus, der versucht, das globale Minimum einer glatten skalaren Funktion einer oder mehrerer Variablen zu finden [1] [2] [3] [4]. Der Algorithmus in seiner aktuellen Form wurde von David Wales und Jonathan Doye beschrieben [2] http://www-wales.ch.cam.ac.uk/.

Der Algorithmus ist iterativ, wobei jeder Zyklus aus folgenden Merkmalen besteht:

  1. zufällige Störung der Koordinaten

  2. lokale Minimierung

  3. Akzeptieren oder Ablehnen der neuen Koordinaten basierend auf dem minimierten Funktionswert.

Der hier verwendete Akzeptanztest ist das Metropolis-Kriterium von Standard-Monte-Carlo-Algorithmen, obwohl es viele andere Möglichkeiten gibt [3].

Diese globale Minimierungsmethode hat sich für eine breite Palette von Problemen in Physik und Chemie als äußerst effizient erwiesen. Sie ist besonders nützlich, wenn die Funktion viele Minima aufweist, die durch große Barrieren getrennt sind. Siehe die Cambridge Cluster Database für Datenbanken molekularer Systeme, die hauptsächlich mit Basin-Hopping optimiert wurden. Diese Datenbank enthält Minimierungsprobleme mit über 300 Freiheitsgraden.

Siehe das kostenlose Softwareprogramm GMIN für eine Fortran-Implementierung von Basin-Hopping. Diese Implementierung bietet viele Variationen des oben beschriebenen Verfahrens, einschließlich fortschrittlicherer Schrittalgorithmen und alternativer Akzeptanzkriterien.

Für stochastische globale Optimierung gibt es keine Möglichkeit zu bestimmen, ob das wahre globale Minimum tatsächlich gefunden wurde. Stattdessen kann als Konsistenzprüfung der Algorithmus von einer Anzahl verschiedener zufälliger Startpunkte aus ausgeführt werden, um sicherzustellen, dass das in jedem Beispiel gefundene niedrigste Minimum zum globalen Minimum konvergiert ist. Aus diesem Grund wird basinhopping standardmäßig einfach für die Anzahl der Iterationen niter ausgeführt und gibt das gefundene niedrigste Minimum zurück. Es liegt am Benutzer, sicherzustellen, dass dies tatsächlich das globale Minimum ist.

Auswahl von stepsize: Dies ist ein entscheidender Parameter in basinhopping und hängt vom zu lösenden Problem ab. Der Schritt wird in jeder Dimension gleichmäßig im Bereich von x0-stepsize bis x0+stepsize gewählt. Idealerweise sollte er vergleichbar mit dem typischen Abstand (in Argumentwerten) zwischen lokalen Minima der zu optimierenden Funktion sein. basinhopping passt stepsize standardmäßig an, um einen optimalen Wert zu finden, dies kann jedoch viele Iterationen dauern. Sie erzielen schnellere Ergebnisse, wenn Sie einen sinnvollen Anfangswert für stepsize festlegen.

Auswahl von T: Der Parameter T ist die „Temperatur“, die im Metropolis-Kriterium verwendet wird. Basin-Hopping-Schritte werden immer akzeptiert, wenn func(xnew) < func(xold). Andernfalls werden sie mit der Wahrscheinlichkeit akzeptiert:

exp( -(func(xnew) - func(xold)) / T )

Für beste Ergebnisse sollte T daher mit dem typischen Unterschied (in Funktionswerten) zwischen lokalen Minima vergleichbar sein. (Die Höhe der „Mauern“ zwischen lokalen Minima ist irrelevant.)

Wenn T 0 ist, wird der Algorithmus zu Monotonic Basin-Hopping, bei dem alle Schritte, die die Energie erhöhen, abgelehnt werden.

Hinzugefügt in Version 0.12.0.

Referenzen

[1]

Wales, David J. 2003, Energy Landscapes, Cambridge University Press, Cambridge, UK.

[2] (1,2)

Wales, D J, and Doye J P K, Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 Atoms. Journal of Physical Chemistry A, 1997, 101, 5111.

[3] (1,2)

Li, Z. and Scheraga, H. A., Monte Carlo-minimization approach to the multiple-minima problem in protein folding, Proc. Natl. Acad. Sci. USA, 1987, 84, 6611.

[4]

Wales, D. J. and Scheraga, H. A., Global optimization of clusters, crystals, and biomolecules, Science, 1999, 285, 1368.

[5]

Olson, B., Hashmi, I., Molloy, K., and Shehu1, A., Basin Hopping as a General and Versatile Optimization Framework for the Characterization of Biological Macromolecules, Advances in Artificial Intelligence, Volume 2012 (2012), Article ID 674832, DOI:10.1155/2012/674832

Beispiele

Das folgende Beispiel ist ein 1-D-Minimierungsproblem mit vielen lokalen Minima, die auf einer Parabel überlagert sind.

>>> import numpy as np
>>> from scipy.optimize import basinhopping
>>> func = lambda x: np.cos(14.5 * x - 0.3) + (x + 0.2) * x
>>> x0 = [1.]

Basinhopping verwendet intern einen lokalen Minimierungsalgorithmus. Wir werden den Parameter minimizer_kwargs verwenden, um basinhopping mitzuteilen, welcher Algorithmus verwendet werden soll und wie dieser Minimierer konfiguriert werden soll. Dieser Parameter wird an scipy.optimize.minimize übergeben.

>>> minimizer_kwargs = {"method": "BFGS"}
>>> ret = basinhopping(func, x0, minimizer_kwargs=minimizer_kwargs,
...                    niter=200)
>>> # the global minimum is:
>>> ret.x, ret.fun
-0.1951, -1.0009

Betrachten wir nun ein 2-D-Minimierungsproblem. Dieses Mal werden wir auch Gradienteninformationen verwenden, um die Suche erheblich zu beschleunigen.

>>> def func2d(x):
...     f = np.cos(14.5 * x[0] - 0.3) + (x[1] + 0.2) * x[1] + (x[0] +
...                                                            0.2) * x[0]
...     df = np.zeros(2)
...     df[0] = -14.5 * np.sin(14.5 * x[0] - 0.3) + 2. * x[0] + 0.2
...     df[1] = 2. * x[1] + 0.2
...     return f, df

Wir werden auch einen anderen lokalen Minimierungsalgorithmus verwenden. Außerdem müssen wir dem Minimierer mitteilen, dass unsere Funktion sowohl Energie als auch Gradient (Jakobi-Matrix) zurückgibt.

>>> minimizer_kwargs = {"method":"L-BFGS-B", "jac":True}
>>> x0 = [1.0, 1.0]
>>> ret = basinhopping(func2d, x0, minimizer_kwargs=minimizer_kwargs,
...                    niter=200)
>>> print("global minimum: x = [%.4f, %.4f], f(x) = %.4f" % (ret.x[0],
...                                                           ret.x[1],
...                                                           ret.fun))
global minimum: x = [-0.1951, -0.1000], f(x) = -1.0109

Hier ist ein Beispiel für die Verwendung einer benutzerdefinierten Schrittroutine. Stellen Sie sich vor, Sie möchten, dass die erste Koordinate größere Schritte als die übrigen Koordinaten macht. Dies kann wie folgt implementiert werden:

>>> class MyTakeStep:
...    def __init__(self, stepsize=0.5):
...        self.stepsize = stepsize
...        self.rng = np.random.default_rng()
...    def __call__(self, x):
...        s = self.stepsize
...        x[0] += self.rng.uniform(-2.*s, 2.*s)
...        x[1:] += self.rng.uniform(-s, s, x[1:].shape)
...        return x

Da MyTakeStep.stepsize existiert, wird basinhopping die Größe von stepsize anpassen, um die Suche zu optimieren. Wir verwenden dieselbe 2-D-Funktion wie zuvor.

>>> mytakestep = MyTakeStep()
>>> ret = basinhopping(func2d, x0, minimizer_kwargs=minimizer_kwargs,
...                    niter=200, take_step=mytakestep)
>>> print("global minimum: x = [%.4f, %.4f], f(x) = %.4f" % (ret.x[0],
...                                                           ret.x[1],
...                                                           ret.fun))
global minimum: x = [-0.1951, -0.1000], f(x) = -1.0109

Nun ein Beispiel mit einer benutzerdefinierten Callback-Funktion, die den Wert jedes gefundenen Minimums ausgibt.

>>> def print_fun(x, f, accepted):
...         print("at minimum %.4f accepted %d" % (f, int(accepted)))

Wir werden diesmal nur für 10 Basin-Hopping-Schritte laufen.

>>> rng = np.random.default_rng()
>>> ret = basinhopping(func2d, x0, minimizer_kwargs=minimizer_kwargs,
...                    niter=10, callback=print_fun, rng=rng)
at minimum 0.4159 accepted 1
at minimum -0.4317 accepted 1
at minimum -1.0109 accepted 1
at minimum -0.9073 accepted 1
at minimum -0.4317 accepted 0
at minimum -0.1021 accepted 1
at minimum -0.7425 accepted 1
at minimum -0.9073 accepted 1
at minimum -0.4317 accepted 0
at minimum -0.7425 accepted 1
at minimum -0.9073 accepted 1

Das Minimum bei -1,0109 ist tatsächlich das globale Minimum, das bereits in der 8. Iteration gefunden wurde.

Auf dieser Seite