scipy.optimize.

differential_evolution#

scipy.optimize.differential_evolution(func, bounds, args=(), strategy='best1bin', maxiter=1000, popsize=15, tol=0.01, mutation=(0.5, 1), recombination=0.7, rng=None, callback=None, disp=False, polish=True, init='latinhypercube', atol=0, updating='immediate', workers=1, constraints=(), x0=None, *, integrality=None, vectorized=False)[Quelle]#

Findet das globale Minimum einer multivariaten Funktion.

Die Methode der differentiellen Evolution [1] ist stochastischer Natur. Sie verwendet keine Gradientenmethoden zur Minimumfindung und kann große Bereiche des Kandidatenraums durchsuchen, erfordert jedoch oft eine größere Anzahl von Funktionsauswertungen als konventionelle gradientenbasierte Techniken.

Der Algorithmus stammt von Storn und Price [2].

Parameter:
funccallable

Die zu minimierende Zielfunktion. Muss die Form f(x, *args) haben, wobei x das Argument in Form eines 1D-Arrays und args ein Tupel von zusätzlichen festen Parametern ist, die zur vollständigen Spezifikation der Funktion erforderlich sind. Die Anzahl der Parameter, N, ist gleich len(x).

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, die die endlichen unteren und oberen Grenzen für das optimierende Argument von func definieren.

Die Gesamtzahl der Grenzen wird verwendet, um die Anzahl der Parameter, N, zu bestimmen. Wenn Parameter mit gleichen Grenzen vorhanden sind, ist die Gesamtzahl der freien Parameter N - N_equal.

argstuple, optional

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

strategy{str, callable}, optional

Die zu verwendende Strategie der differentiellen Evolution. Sollte eine der folgenden sein:

  • ‘best1bin’

  • ‘best1exp’

  • ‘rand1bin’

  • ‘rand1exp’

  • ‘rand2bin’

  • ‘rand2exp’

  • ‘randtobest1bin’

  • ‘randtobest1exp’

  • ‘currenttobest1bin’

  • ‘currenttobest1exp’

  • ‘best2exp’

  • ‘best2bin’

Der Standardwert ist 'best1bin'. Strategien, die implementiert werden können, sind in 'Notes' beschrieben. Alternativ kann die Strategie der differentiellen Evolution durch Bereitstellung eines aufrufbaren Objekts, das einen Versuchvektor konstruiert, angepasst werden. Das aufrufbare Objekt muss die Form strategy(candidate: int, population: np.ndarray, rng=None) haben, wobei candidate eine Ganzzahl ist, die angibt, welcher Eintrag der Population entwickelt wird, population ein Array der Form (S, N) ist, das alle Populationsmitglieder enthält (wobei S die Gesamtpopulationsgröße ist), und rng der Zufallszahlengenerator ist, der innerhalb des Lösers verwendet wird. candidate liegt im Bereich [0, S). strategy muss einen Versuchvektor mit der Form (N,) zurückgeben. Die Fitness dieses Versuchvektors wird mit der Fitness von population[candidate] verglichen.

Geändert in Version 1.12.0: Anpassung der Evolutionsstrategie über ein aufrufbare Objekt.

maxiterint, optional

Die maximale Anzahl von Generationen, über die die gesamte Population entwickelt wird. Die maximale Anzahl von Funktionsauswertungen (ohne Polieren) beträgt: (maxiter + 1) * popsize * (N - N_equal)

popsizeint, optional

Ein Multiplikator zur Einstellung der Gesamtpopulationsgröße. Die Population hat popsize * (N - N_equal) Individuen. Dieses Schlüsselwort wird überschrieben, wenn über das Schlüsselwort init eine Anfangspopulation bereitgestellt wird. Bei Verwendung von init='sobol' wird die Populationsgröße als nächste Zweierpotenz nach popsize * (N - N_equal) berechnet.

tolfloat, optional

Relative Toleranz für die Konvergenz; die Lösung stoppt, wenn np.std(population_energies) <= atol + tol * np.abs(np.mean(population_energies)), wobei atol und tol die absolute bzw. relative Toleranz sind.

mutationfloat oder tuple(float, float), optional

Die Mutationskonstante. In der Literatur ist dies auch als differentielles Gewicht bekannt und wird mit \(F\) bezeichnet. Wenn als Float angegeben, sollte es im Bereich [0, 2) liegen. Wenn als Tupel (min, max) angegeben, wird Dithering verwendet. Dithering ändert die Mutationskonstante zufällig von Generation zu Generation. Die Mutationskonstante für diese Generation wird aus U[min, max) entnommen. Dithering kann die Konvergenzgeschwindigkeit erheblich beschleunigen. Eine Erhöhung der Mutationskonstante erhöht den Suchradius, verlangsamt aber die Konvergenz.

recombinationfloat, optional

Die Rekombinationskonstante sollte im Bereich [0, 1] liegen. In der Literatur ist dies auch als Crossover-Wahrscheinlichkeit bekannt und wird mit CR bezeichnet. Eine Erhöhung dieses Wertes erlaubt einer größeren Anzahl von Mutanten, in die nächste Generation überzugehen, birgt jedoch das Risiko der Populationsstabilität.

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 in 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 sowohl seed als auch rng ist oben beschrieben, aber nur das Schlüsselwort rng sollte in neuem Code verwendet werden.

dispbool, optional

Gibt die ausgewertete func bei jeder Iteration aus.

callbackcallable, optional

Ein aufrufbare Funktion, die nach jeder Iteration aufgerufen wird. Hat die Signatur

callback(intermediate_result: OptimizeResult)

wobei intermediate_result ein Schlüsselwortparameter ist, der eine OptimizeResult mit den Attributen x und fun enthält, die bisher beste gefundene Lösung und die Zielfunktion. Beachten Sie, dass der Name des Parameters intermediate_result sein muss, damit der Callback eine OptimizeResult übergeben wird.

Der Callback unterstützt auch eine Signatur wie

callback(x, convergence: float=val)

val repräsentiert den fraktionellen Wert der Populationskonvergenz. Wenn val größer als 1.0 ist, wird die Funktion beendet.

Introspektion wird verwendet, um zu bestimmen, welche der Signaturen aufgerufen wird.

Die globale Minimierung wird abgebrochen, wenn der Callback StopIteration auslöst oder True zurückgibt; jegliches Polieren wird trotzdem durchgeführt.

Geändert in Version 1.12.0: callback akzeptiert das Schlüsselwort intermediate_result.

polishbool, optional

Wenn True (Standard), dann wird scipy.optimize.minimize mit der Methode L-BFGS-B verwendet, um das beste Populationsmitglied am Ende zu polieren, was die Minimierung leicht verbessern kann. Wenn ein Problem mit Nebenbedingungen untersucht wird, wird stattdessen die Methode trust-constr verwendet. Bei großen Problemen mit vielen Nebenbedingungen kann das Polieren aufgrund der Jacobi-Berechnungen lange dauern.

Geändert in Version 1.15.0: Wenn workers angegeben ist, dann wird der Map-ähnliche aufrufbare Objekt, der func umschließt, an minimize übergeben, anstatt dass func direkt verwendet wird. Dies ermöglicht dem Aufrufer, zu steuern, wie und wo die Aufrufe tatsächlich ausgeführt werden.

initstr oder array-ähnlich, optional

Gibt an, welche Art der Populationsinitialisierung durchgeführt wird. Sollte eine der folgenden sein:

  • ‘latinhypercube’

  • ‘sobol’

  • ‘halton’

  • ‘random’

  • Array, das die Anfangspopulation angibt. Das Array sollte die Form (S, N) haben, wobei S die Gesamtpopulationsgröße und N die Anzahl der Parameter ist.

init wird vor der Verwendung auf bounds gekappt.

Der Standardwert ist 'latinhypercube'. Latin Hypercube Sampling versucht, die Abdeckung des verfügbaren Parameterraums zu maximieren.

‘sobol’ und ‘halton’ sind überlegene Alternativen und maximieren den Parameterraum noch weiter. ‘sobol’ erzwingt eine Anfangspopulationsgröße, die als nächste Zweierpotenz nach popsize * (N - N_equal) berechnet wird. ‘halton’ hat keine Anforderungen, ist aber etwas weniger effizient. Weitere Informationen finden Sie unter scipy.stats.qmc.

‘random’ initialisiert die Population zufällig - dies hat den Nachteil, dass es zu Clusterbildung kommen kann, was verhindert, dass der gesamte Parameterraum abgedeckt wird. Die Verwendung eines Arrays zur Angabe einer Population könnte beispielsweise dazu dienen, eine enge Gruppe von Anfangsschätzungen an einem Ort zu erstellen, an dem bekannt ist, dass die Lösung existiert, wodurch die Zeit bis zur Konvergenz reduziert wird.

atolfloat, optional

Absolute Toleranz für die Konvergenz; die Lösung stoppt, wenn np.std(pop) <= atol + tol * np.abs(np.mean(population_energies)), wobei atol und tol die absolute bzw. relative Toleranz sind.

updating{‘immediate’, ‘deferred’}, optional

Wenn 'immediate', wird der beste Lösungsvektor innerhalb einer einzelnen Generation kontinuierlich aktualisiert [4]. Dies kann zu einer schnelleren Konvergenz führen, da Versuchvektoren von kontinuierlichen Verbesserungen der besten Lösung profitieren können. Mit 'deferred' wird der beste Lösungsvektor einmal pro Generation aktualisiert. Nur 'deferred' ist mit Parallelisierung oder Vektorisierung kompatibel, und die Schlüsselwörter workers und vectorized können diese Option überschreiben.

Hinzugefügt in Version 1.2.0.

workersint oder Map-ähnliches aufrufbare Objekt, optional

Wenn workers eine Ganzzahl ist, wird die Population in workers Abschnitte unterteilt und parallel ausgewertet (verwendet multiprocessing.Pool). Geben Sie -1 an, um alle verfügbaren CPU-Kerne zu verwenden. Alternativ geben Sie ein Map-ähnliches aufrufbare Objekt an, wie z.B. multiprocessing.Pool.map, zur parallelen Auswertung der Population. Diese Auswertung erfolgt als workers(func, iterable). Diese Option überschreibt das Schlüsselwort updating mit updating='deferred', wenn workers != 1. Diese Option überschreibt das Schlüsselwort vectorized, wenn workers != 1. Erfordert, dass func serialisierbar ist.

Hinzugefügt in Version 1.2.0.

constraints{NonLinearConstraint, LinearConstraint, Bounds}

Nebenbedingungen für den Löser, zusätzlich zu denen, die durch das bounds kwd angewendet werden. Verwendet den Ansatz von Lampinen [5].

Hinzugefügt in Version 1.4.0.

x0None oder array-ähnlich, optional

Bietet eine anfängliche Schätzung für die Minimierung. Sobald die Population initialisiert wurde, ersetzt dieser Vektor das erste (beste) Mitglied. Dieser Austausch erfolgt auch dann, wenn init mit einer Anfangspopulation angegeben wird. x0.shape == (N,).

Hinzugefügt in Version 1.7.0.

integrality1D-Array, optional

Für jede Entscheidungsvariable ein boolescher Wert, der angibt, ob die Entscheidungsvariable auf ganzzahlige Werte beschränkt ist. Das Array wird auf (N,) erweitert. Wenn eine Entscheidungsvariable ganzzahlig sein muss, wird sie während des Polierens nicht verändert. Nur ganzzahlige Werte zwischen der unteren und oberen Grenze werden verwendet. Wenn keine ganzzahligen Werte zwischen den Grenzen liegen, wird ein ValueError ausgelöst.

Hinzugefügt in Version 1.9.0.

vectorizedbool, optional

Wenn vectorized True ist, wird func ein x-Array mit x.shape == (N, S) gesendet, und es wird erwartet, dass es ein Array der Form (S,) zurückgibt, wobei S die Anzahl der zu berechnenden Lösungsvektoren ist. Wenn Nebenbedingungen angewendet werden, sollte jede der Funktionen, die zur Konstruktion eines Constraint-Objekts verwendet werden, ein x-Array mit x.shape == (N, S) akzeptieren und ein Array der Form (M, S) zurückgeben, wobei M die Anzahl der Nebenbedingungskomponenten ist. Diese Option ist eine Alternative zur Parallelisierung, die von workers angeboten wird, und kann die Optimierungsgeschwindigkeit durch Reduzierung des Interpreter-Overheads bei mehreren Funktionsaufrufen verbessern. Dieses Schlüsselwort wird ignoriert, wenn workers != 1. Diese Option überschreibt das Schlüsselwort updating mit updating='deferred'. Siehe den Abschnitt "Notes" für weitere Diskussionen darüber, wann 'vectorized' und wann 'workers' verwendet werden sollte.

Hinzugefügt in Version 1.9.0.

Rückgabe:
resOptimizeResult

Das Optimierungsergebnis, dargestellt als OptimizeResult-Objekt. Wichtige Attribute sind: x das Lösungsarray, success ein boolesches Flag, das anzeigt, ob der Optimierer erfolgreich beendet wurde, message, das den Grund für die Beendigung beschreibt, population die in der Population vorhandenen Lösungsvektoren und population_energies der Wert der Zielfunktion für jeden Eintrag in population. Siehe OptimizeResult für eine Beschreibung anderer Attribute. Wenn polish verwendet wurde und durch das Polieren ein niedrigeres Minimum erzielt wurde, enthält OptimizeResult auch das Attribut jac. Wenn die endgültige Lösung die angewendeten Nebenbedingungen nicht erfüllt, ist success False.

Hinweise

Differential Evolution ist eine stochastische, populationsbasierte Methode, die sich für globale Optimierungsprobleme eignet. In jedem Durchlauf der Population mutiert der Algorithmus jede Kandidatenlösung, indem er sie mit anderen Kandidatenlösungen mischt, um einen Versuchskandidaten zu erstellen. Es gibt verschiedene Strategien [3] zur Erstellung von Versuchskandidaten, die für manche Probleme besser geeignet sind als für andere. Die Strategie 'best1bin' ist ein guter Ausgangspunkt für viele Systeme. Bei dieser Strategie werden zwei Mitglieder der Population zufällig ausgewählt. Ihre Differenz wird verwendet, um das bisher beste Mitglied (das 'beste' in 'best1bin'), \(x_0\), zu mutieren:

\[b' = x_0 + F \cdot (x_{r_0} - x_{r_1})\]

wobei \(F\) der mutation-Parameter ist. Anschließend wird ein Versuchvektor konstruiert. Beginnend mit einem zufällig ausgewählten i-ten Parameter wird der Versuch sequenziell (im Modulo) mit Parametern aus b' oder dem ursprünglichen Kandidaten gefüllt. Die Wahl, ob b' oder der ursprüngliche Kandidat verwendet wird, erfolgt mit einer Binomialverteilung (das 'bin' in 'best1bin') - es wird eine Zufallszahl in [0, 1) generiert. Wenn diese Zahl kleiner ist als die recombination-Konstante, wird der Parameter aus b' geladen, andernfalls aus dem ursprünglichen Kandidaten. Der letzte Parameter wird immer aus b' geladen. Sobald der Versuchskandidat erstellt ist, wird seine Fitness bewertet. Wenn der Versuch besser ist als der ursprüngliche Kandidat, ersetzt er ihn. Wenn er auch besser ist als der beste Gesamt-Kandidat, ersetzt er auch diesen.

Die anderen verfügbaren Strategien sind in Qiang und Mitchell (2014) [3] beschrieben.

  • rand1 : \(b' = x_{r_0} + F \cdot (x_{r_1} - x_{r_2})\)

  • rand2 : \(b' = x_{r_0} + F \cdot (x_{r_1} + x_{r_2} - x_{r_3} - x_{r_4})\)

  • best1 : \(b' = x_0 + F \cdot (x_{r_0} - x_{r_1})\)

  • best2 : \(b' = x_0 + F \cdot (x_{r_0} + x_{r_1} - x_{r_2} - x_{r_3})\)

  • currenttobest1 : \(b' = x_i + F \cdot (x_0 - x_i + x_{r_0} - x_{r_1})\)

  • randtobest1 : \(b' = x_{r_0} + F \cdot (x_0 - x_{r_0} + x_{r_1} - x_{r_2})\)

wobei die ganzen Zahlen \(r_0, r_1, r_2, r_3, r_4\) zufällig aus dem Intervall [0, NP) mit NP als der Gesamtpopulationsgröße ausgewählt werden und der ursprüngliche Kandidat den Index i hat. Der Benutzer kann die Erzeugung der Versuchskandidaten vollständig anpassen, indem er ein aufrufbare Objekt für strategy bereitstellt.

Um Ihre Chancen auf die globale Minimumfindung zu verbessern, verwenden Sie höhere popsize-Werte, mit höherer mutation und (Dithering), aber niedrigerer recombination. Dies hat den Effekt, den Suchradius zu erweitern, aber die Konvergenz zu verlangsamen.

Standardmäßig wird der beste Lösungsvektor kontinuierlich innerhalb einer einzelnen Iteration aktualisiert (updating='immediate'). Dies ist eine Modifikation [4] des ursprünglichen Algorithmus der differentiellen Evolution, die zu einer schnelleren Konvergenz führen kann, da Versuchvektoren sofort von verbesserten Lösungen profitieren können. Um das ursprüngliche Verhalten von Storn und Price zu verwenden, bei dem die beste Lösung einmal pro Iteration aktualisiert wird, setzen Sie updating='deferred'. Der Ansatz 'deferred' ist sowohl mit Parallelisierung als auch mit Vektorisierung ('workers' und 'vectorized' Schlüsselwörter) kompatibel. Diese können die Minimierungsgeschwindigkeit verbessern, indem sie Computerressourcen effizienter nutzen. Die 'workers' verteilen Berechnungen auf mehrere Prozessoren. Standardmäßig wird das Python-Modul multiprocessing verwendet, aber auch andere Ansätze sind möglich, wie z.B. das Message Passing Interface (MPI), das auf Clustern verwendet wird [6] [7]. Der Overhead dieser Ansätze (Erstellung neuer Prozesse usw.) kann erheblich sein, was bedeutet, dass die rechnerische Geschwindigkeit nicht unbedingt mit der Anzahl der verwendeten Prozessoren skaliert. Parallelisierung eignet sich am besten für rechenintensive Zielfunktionen. Wenn die Zielfunktion weniger aufwendig ist, kann 'vectorized' helfen, indem die Zielfunktion nur einmal pro Iteration aufgerufen wird, anstatt mehrmals für alle Populationsmitglieder; der Interpreter-Overhead wird reduziert.

Hinzugefügt in Version 0.15.0.

Referenzen

[1]

Differential Evolution, Wikipedia, http://en.wikipedia.org/wiki/Differential_evolution

[2]

Storn, R und Price, K, Differential Evolution - a Simple and Efficient Heuristic for Global Optimization over Continuous Spaces, Journal of Global Optimization, 1997, 11, 341 - 359.

[3] (1,2)

Qiang, J., Mitchell, C., A Unified Differential Evolution Algorithm for Global Optimization, 2014, https://www.osti.gov/servlets/purl/1163659

[4] (1,2)

Wormington, M., Panaccione, C., Matney, K. M., Bowen, D. K., - Characterization of structures from X-ray scattering data using genetic algorithms, Phil. Trans. R. Soc. Lond. A, 1999, 357, 2827-2848

[5]

Lampinen, J., A constraint handling approach for the differential evolution algorithm. Proceedings of the 2002 Congress on Evolutionary Computation. CEC’02 (Cat. No. 02TH8600). Vol. 2. IEEE, 2002.

Beispiele

Betrachten wir das Problem der Minimierung der Rosenbrock-Funktion. Diese Funktion ist in rosen in scipy.optimize implementiert.

>>> import numpy as np
>>> from scipy.optimize import rosen, differential_evolution
>>> bounds = [(0,2), (0, 2), (0, 2), (0, 2), (0, 2)]
>>> result = differential_evolution(rosen, bounds)
>>> result.x, result.fun
(array([1., 1., 1., 1., 1.]), 1.9216496320061384e-19)

Wiederholen Sie nun mit Parallelisierung.

>>> result = differential_evolution(rosen, bounds, updating='deferred',
...                                 workers=2)
>>> result.x, result.fun
(array([1., 1., 1., 1., 1.]), 1.9216496320061384e-19)

Machen wir eine Minimierung mit Nebenbedingungen.

>>> from scipy.optimize import LinearConstraint, Bounds

Wir fügen die Einschränkung hinzu, dass die Summe von x[0] und x[1] kleiner oder gleich 1,9 sein muss. Dies ist eine lineare Einschränkung, die geschrieben werden kann als A @ x <= 1.9, wobei A = array([[1, 1]]). Dies kann als LinearConstraint-Instanz kodiert werden

>>> lc = LinearConstraint([[1, 1]], -np.inf, 1.9)

Geben Sie Grenzen mit einem Bounds-Objekt an.

>>> bounds = Bounds([0., 0.], [2., 2.])
>>> result = differential_evolution(rosen, bounds, constraints=lc,
...                                 rng=1)
>>> result.x, result.fun
(array([0.96632622, 0.93367155]), 0.0011352416852625719)

Finden Sie als Nächstes das Minimum der Ackley-Funktion (https://en.wikipedia.org/wiki/Test_functions_for_optimization).

>>> def ackley(x):
...     arg1 = -0.2 * np.sqrt(0.5 * (x[0] ** 2 + x[1] ** 2))
...     arg2 = 0.5 * (np.cos(2. * np.pi * x[0]) + np.cos(2. * np.pi * x[1]))
...     return -20. * np.exp(arg1) - np.exp(arg2) + 20. + np.e
>>> bounds = [(-5, 5), (-5, 5)]
>>> result = differential_evolution(ackley, bounds, rng=1)
>>> result.x, result.fun
(array([0., 0.]), 4.440892098500626e-16)

Die Ackley-Funktion ist vektorisiert geschrieben, daher kann das Schlüsselwort 'vectorized' verwendet werden. Beachten Sie die reduzierte Anzahl von Funktionsauswertungen.

>>> result = differential_evolution(
...     ackley, bounds, vectorized=True, updating='deferred', rng=1
... )
>>> result.x, result.fun
(array([0., 0.]), 4.440892098500626e-16)

Die folgende benutzerdefinierte Strategiefunktion imitiert ‘best1bin’

>>> def custom_strategy_fn(candidate, population, rng=None):
...     parameter_count = population.shape(-1)
...     mutation, recombination = 0.7, 0.9
...     trial = np.copy(population[candidate])
...     fill_point = rng.choice(parameter_count)
...
...     pool = np.arange(len(population))
...     rng.shuffle(pool)
...
...     # two unique random numbers that aren't the same, and
...     # aren't equal to candidate.
...     idxs = []
...     while len(idxs) < 2 and len(pool) > 0:
...         idx = pool[0]
...         pool = pool[1:]
...         if idx != candidate:
...             idxs.append(idx)
...
...     r0, r1 = idxs[:2]
...
...     bprime = (population[0] + mutation *
...               (population[r0] - population[r1]))
...
...     crossovers = rng.uniform(size=parameter_count)
...     crossovers = crossovers < recombination
...     crossovers[fill_point] = True
...     trial = np.where(crossovers, bprime, trial)
...     return trial