scipy.optimize.

direct#

scipy.optimize.direct(func, bounds, *, args=(), eps=0.0001, maxfun=None, maxiter=1000, locally_biased=True, f_min=-inf, f_min_rtol=0.0001, vol_tol=1e-16, len_tol=1e-06, callback=None)[Quelle]#

Findet das globale Minimum einer Funktion mithilfe des DIRECT-Algorithmus.

Parameter:
funccallable

Die zu minimierende Zielfunktion. func(x, *args) -> float wobei x ein 1D-Array mit der Form (n,) ist und args ein Tupel von festen Parametern ist, die zur vollständigen Spezifikation der Funktion erforderlich sind.

boundssequenz oder Bounds

Grenzen für Variablen. Es gibt zwei Möglichkeiten, die Grenzen festzulegen:

  1. Instanz der Klasse Bounds.

  2. (min, max) Paare für jedes Element in x.

argstuple, optional

Alle zusätzlichen festen Parameter, die zur vollständigen Spezifikation der Zielfunktion erforderlich sind.

epsfloat, optional

Minimal erforderliche Differenz der Zielfunktionswerte zwischen dem aktuell besten Hyperrechteck und dem nächsten potenziell optimalen Hyperrechteck, das geteilt werden soll. Folglich dient eps als Kompromiss zwischen lokaler und globaler Suche: je kleiner, desto lokaler wird die Suche. Standardwert ist 1e-4.

maxfunint oder None, optional

Ungefähre Obergrenze für die Auswertungen der Zielfunktion. Wenn None, wird er automatisch auf 1000 * N gesetzt, wobei N die Anzahl der Dimensionen darstellt. Er wird gegebenenfalls begrenzt, um die RAM-Nutzung von DIRECT auf ca. 1 GiB zu beschränken. Dies tritt nur bei sehr hochdimensionalen Problemen und übermäßigem max_fun auf. Standardwert ist None.

maxiterint, optional

Maximale Anzahl von Iterationen. Standardwert ist 1000.

locally_biasedbool, optional

Wenn True (Standard), wird die lokal voreingenommene Variante des Algorithmus namens DIRECT_L verwendet. Wenn False, wird der ursprüngliche, unverzerrte DIRECT-Algorithmus verwendet. Für schwierige Probleme mit vielen lokalen Minima wird False empfohlen.

f_minfloat, optional

Funktionswert des globalen Optimums. Setzen Sie diesen Wert nur, wenn das globale Optimum bekannt ist. Standardwert ist -np.inf, sodass dieses Abbruchkriterium deaktiviert ist.

f_min_rtolfloat, optional

Beendet die Optimierung, sobald der relative Fehler zwischen dem aktuellen besten Minimum f und dem angegebenen globalen Minimum f_min kleiner als f_min_rtol ist. Dieser Parameter wird nur verwendet, wenn auch f_min gesetzt ist. Muss zwischen 0 und 1 liegen. Standardwert ist 1e-4.

vol_tolfloat, optional

Beendet die Optimierung, sobald das Volumen des Hyperrechtecks, das den niedrigsten Funktionswert enthält, kleiner als vol_tol des gesamten Suchraums ist. Muss zwischen 0 und 1 liegen. Standardwert ist 1e-16.

len_tolfloat, optional

Wenn locally_biased=True, wird die Optimierung beendet, sobald die Hälfte der normalisierten maximalen Seitenlänge des Hyperrechtecks, das den niedrigsten Funktionswert enthält, kleiner als len_tol ist. Wenn locally_biased=False, wird die Optimierung beendet, sobald die Hälfte der normalisierten Diagonale des Hyperrechtecks, das den niedrigsten Funktionswert enthält, kleiner als len_tol ist. Muss zwischen 0 und 1 liegen. Standardwert ist 1e-6.

callbackcallable, optional

Eine Callback-Funktion mit der Signatur callback(xk), wobei xk den bisher besten gefundenen Funktionswert darstellt.

Rückgabe:
resOptimizeResult

Das Optimierungsergebnis, dargestellt als OptimizeResult-Objekt. Wichtige Attribute sind: x der Lösungsvektor, success ein boolesches Flag, das angibt, ob der Optimizer erfolgreich beendet wurde, und message, das die Ursache der Beendigung beschreibt. Siehe OptimizeResult für eine Beschreibung anderer Attribute.

Hinweise

DIviding RECTangles (DIRECT) ist ein deterministischer globaler Optimierungsalgorithmus, der in der Lage ist, eine Black-Box-Funktion mit ihren Variablen, die Einschränkungen bezüglich unterer und oberer Grenzen unterliegen, durch Stichproben potenzieller Lösungen im Suchraum zu minimieren [1]. Der Algorithmus beginnt mit der Normalisierung des Suchraums auf einen n-dimensionalen Einheits-Hyperwürfel. Er wertet die Funktion im Zentrum dieses Hyperwürfels und an 2n (n ist die Anzahl der Variablen) weiteren Punkten aus, 2 in jeder Koordinatenrichtung. Anhand dieser Funktionswerte teilt DIRECT den Bereich in Hyperrechtecke auf, von denen jedes genau einen der Stichprobenpunkte als Zentrum hat. In jeder Iteration wählt DIRECT mithilfe des Parameters eps, der standardmäßig auf 1e-4 gesetzt ist, einige der vorhandenen Hyperrechtecke zur weiteren Teilung aus. Dieser Teilungsprozess wird fortgesetzt, bis entweder die maximale Anzahl von erlaubten Iterationen oder Funktionsauswertungen überschritten ist oder das Hyperrechteck, das den bisher gefundenen Minimalwert enthält, klein genug geworden ist. Wenn f_min angegeben ist, stoppt die Optimierung, sobald dieser Funktionswert innerhalb einer relativen Toleranz erreicht ist. Die lokal voreingenommene Variante von DIRECT (ursprünglich DIRECT_L genannt) [2] wird standardmäßig verwendet. Sie macht die Suche lokaler und effizienter für Fälle mit nur wenigen lokalen Minima.

Ein Hinweis zu den Abbruchkriterien: vol_tol bezieht sich auf das Volumen des Hyperrechtecks, das den bisher gefundenen niedrigsten Funktionswert enthält. Dieses Volumen nimmt mit zunehmender Dimensionalität des Problems exponentiell ab. Daher sollte vol_tol verringert werden, um eine vorzeitige Beendigung des Algorithmus bei höheren Dimensionen zu vermeiden. Dies gilt nicht für len_tol: es bezieht sich entweder auf die Hälfte der maximalen Seitenlänge (für locally_biased=True) oder auf die Hälfte der Diagonale des Hyperrechtecks (für locally_biased=False).

Dieser Code basiert auf dem Fortran-Code DIRECT 2.0.4 von Gablonsky et al. unter https://ctk.math.ncsu.edu/SOFTWARE/DIRECTv204.tar.gz. Diese Originalversion wurde ursprünglich über f2c konvertiert und dann von Steven G. Johnson im August 2007 für das NLopt-Projekt bereinigt und neu organisiert. Die Funktion direct wrappt die C-Implementierung.

Hinzugefügt in Version 1.9.0.

Referenzen

[1]

Jones, D.R., Perttunen, C.D. & Stuckman, B.E. Lipschitzian optimization without the Lipschitz constant. J Optim Theory Appl 79, 157-181 (1993).

[2]

Gablonsky, J., Kelley, C. A Locally-Biased form of the DIRECT Algorithm. Journal of Global Optimization 21, 27-37 (2001).

Beispiele

Das folgende Beispiel ist ein 2D-Problem mit vier lokalen Minima: Minimierung der Styblinski-Tang-Funktion (https://en.wikipedia.org/wiki/Test_functions_for_optimization).

>>> from scipy.optimize import direct, Bounds
>>> def styblinski_tang(pos):
...     x, y = pos
...     return 0.5 * (x**4 - 16*x**2 + 5*x + y**4 - 16*y**2 + 5*y)
>>> bounds = Bounds([-4., -4.], [4., 4.])
>>> result = direct(styblinski_tang, bounds)
>>> result.x, result.fun, result.nfev
array([-2.90321597, -2.90321597]), -78.3323279095383, 2011

Das korrekte globale Minimum wurde gefunden, jedoch mit einer sehr großen Anzahl von Funktionsauswertungen (2011). Das Lockern der Abbruchtoleranzen vol_tol und len_tol kann verwendet werden, um DIRECT früher zu stoppen.

>>> result = direct(styblinski_tang, bounds, len_tol=1e-3)
>>> result.x, result.fun, result.nfev
array([-2.9044353, -2.9044353]), -78.33230330754142, 207
Auf dieser Seite