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, wobeixdas Argument in Form eines 1D-Arrays undargsein Tupel von zusätzlichen festen Parametern ist, die zur vollständigen Spezifikation der Funktion erforderlich sind. Die Anzahl der Parameter, N, ist gleichlen(x).- boundssequenz oder
Bounds Grenzen für Variablen. Es gibt zwei Möglichkeiten, die Grenzen festzulegen:
Instanz der Klasse
Bounds.(min, max)-Paare für jedes Element inx, 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, wobeicandidateeine Ganzzahl ist, die angibt, welcher Eintrag der Population entwickelt wird,populationein Array der Form(S, N)ist, das alle Populationsmitglieder enthält (wobei S die Gesamtpopulationsgröße ist), undrngder Zufallszahlengenerator ist, der innerhalb des Lösers verwendet wird.candidateliegt im Bereich[0, S).strategymuss einen Versuchvektor mit der Form(N,)zurückgeben. Die Fitness dieses Versuchvektors wird mit der Fitness vonpopulation[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 voninit='sobol'wird die Populationsgröße als nächste Zweierpotenz nachpopsize * (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 ausU[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.Generatorannumpy.random.default_rngübergeben, um einenGeneratorzu instanziieren. Wenn rng bereits eineGenerator-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 vonnumpy.random.RandomStateverwendet.Wenn seed eine Ganzzahl ist, wird eine neue
RandomState-Instanz mit seed verwendet.Wenn seed bereits eine
Generator- oderRandomState-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.RandomStatezunumpy.random.Generatorwurde 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_resultein Schlüsselwortparameter ist, der eineOptimizeResultmit den Attributenxundfunenthält, die bisher beste gefundene Lösung und die Zielfunktion. Beachten Sie, dass der Name des Parametersintermediate_resultsein muss, damit der Callback eineOptimizeResultübergeben wird.Der Callback unterstützt auch eine Signatur wie
callback(x, convergence: float=val)
valrepräsentiert den fraktionellen Wert der Populationskonvergenz. Wennvalgrößer als1.0ist, wird die Funktion beendet.Introspektion wird verwendet, um zu bestimmen, welche der Signaturen aufgerufen wird.
Die globale Minimierung wird abgebrochen, wenn der Callback
StopIterationauslöst oderTruezurü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.minimizemit 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 unterscipy.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 alsworkers(func, iterable). Diese Option überschreibt das Schlüsselwort updating mitupdating='deferred', wennworkers != 1. Diese Option überschreibt das Schlüsselwort vectorized, wennworkers != 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 Trueist, wird func ein x-Array mitx.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 einesConstraint-Objekts verwendet werden, ein x-Array mitx.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, wennworkers != 1. Diese Option überschreibt das Schlüsselwort updating mitupdating='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:xdas Lösungsarray,successein boolesches Flag, das anzeigt, ob der Optimierer erfolgreich beendet wurde,message, das den Grund für die Beendigung beschreibt,populationdie in der Population vorhandenen Lösungsvektoren undpopulation_energiesder Wert der Zielfunktion für jeden Eintrag inpopulation. SieheOptimizeResultfür eine Beschreibung anderer Attribute. Wenn polish verwendet wurde und durch das Polieren ein niedrigeres Minimum erzielt wurde, enthält OptimizeResult auch das Attributjac. Wenn die endgültige Lösung die angewendeten Nebenbedingungen nicht erfüllt, istsuccessFalse.
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, obb'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 ausb'geladen, andernfalls aus dem ursprünglichen Kandidaten. Der letzte Parameter wird immer ausb'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
strategybereitstellt.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 Sieupdating='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-Modulmultiprocessingverwendet, 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
roseninscipy.optimizeimplementiert.>>> 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]undx[1]kleiner oder gleich 1,9 sein muss. Dies ist eine lineare Einschränkung, die geschrieben werden kann alsA @ x <= 1.9, wobeiA = array([[1, 1]]). Dies kann alsLinearConstraint-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