Global Optimization Toolbox

Hauptmerkmale

  • Interaktive Tools zur Definition, Lösung und Bewertung von Optimierungsproblemen
  • Globale Such- und Multistart-Solver zur Suche einzelner oder mehrerer globaler Optima
  • Genetic-Algorithmus-Solver, der lineare, nicht lineare und Grenz-Bedingungen unterstützt
  • Multikriterieller Genetic-Algorithmus mit Pareto-Front-Identifizierung, einschließlich linearer und Grenz-Bedingungen
  • Mustersuch-Solver, der lineare, nicht lineare und Grenz-Bedingungen unterstützt
  • Simulierte Annealing-Tools, die eine Zufallssuchmethode implementieren und Optionen zur Definition des Annealing-Prozesses, des Temperaturplans und der Akzeptanzkriterien bieten
  • Unterstützung des parallelen Rechnens beim Multistart-, Genetic-Algorithmus- und Pattern Search Solver
  • Unterstützung von benutzerdefinierten Datentypen beim Genetic-Algorithmus-, multikriteriellen Genetic-Algorithmus- und simulierten Annealing-Solver
Plot of a nonsmooth objective function (bottom) that is not easily solved using traditional gradient-based optimization techniques. The Optimization Tool (middle) shows the solution found using pattern search in Global Optimization Toolbox. Iterative results for function value and mesh size are shown in the top figure.

Darstellung einer nicht glatten Zielfunktion (unten), die mit herkömmlichen Gradienten-basierten Optimierungsmethoden nicht einfach gelöst werden kann. Das Optimization Tool (mittleres) zeigt die Lösung, die mithilfe der Mustersuche in der Global Optimization Toolbox gefunden wurde. Iterative Ergebnisse für den Funktionswert und die Netzgröße werden in der oberen Abbildung dargestellt.

Definieren, Lösen und Bewerten von Optimierungsproblemen

Auf die Funktionen der Global Optimization Toolbox können Sie über die Befehlszeile und die Optimization-App in der Optimization Toolbox™ zugreifen. Über die Befehlszeile und die App können Sie Folgendes ausführen:

  • Solver auswählen und Optimierungsprobleme definieren
  • Optimierungsoptionen festlegen und genauer untersuchen
  • Optimierungsproblemlösungen ausführen und Zwischen- und Endergebnisse veranschaulichen
  • Genetic-Algorithmus-, simulierte Annealing- und Pattern Search-Ergebnisse mithilfe der Optimization Toolbox-Solver feinabstimmen
  • Optimierungsprobleme und -ergebnisse in den MATLAB®-Arbeitsplatz importieren und aus dem Arbeitsplatz exportieren
  • Speichern und Wiederverwenden der interaktiven Arbeit in der Optimization-App mittels MATLAB-Codeerzeugung

Sie können die Solver auch anpassen, indem Sie Ihre eigenen Algorithmusoptionen und Funktionen definieren. Auf den Multistart- und globalen Such-Solver kann nur über die Befehlszeile zugegriffen werden.

Visualization of Rastrigin's function that contains many local minima and one global minimum (0,0). The genetic algorithm helps you determine the best solution for functions with several local minima, while the Optimization app provides access to all key components for defining your problem, including the algorithm options.

Visualisierung der Rastrigin-Funktion (rechts) mit etlichen lokalen Minima und einem globalen Minimum (0,0). Mit dem Genetischen Algorithmus lässt sich die beste Lösung für Funktionen mit mehreren lokalen Minima ermitteln. Die Optimization-App (links) erlaubt den Zugriff auf alle wichtigen Komponenten für die Problemdefinition, darunter auch die Auswahl der Algorithmus-Optionen.

Die Toolbox bietet mehrere Funktionen zur Darstellung einer Optimierung. Mithilfe dieser Darstellungen können Sie den Optimierungsfortschritt in Echtzeit verfolgen und entscheiden, welche Solveroptionen zu ändern sind oder ob der Solver gestoppt werden soll. Die Toolbox verfügt über benutzerdefinierbare Darstellungsfunktionen für den Genetic-Algorithmus und Pattern Search-Algorithmen. Sie umfassen Zielfunktionswert, Bedingungsverletzung, Auswertungshistogramm, Genealogie, Netzgröße und Funktionsevaluierungen. Sie können mehrere Darstellungen gleichzeitig anzeigen, bestimmte Diagramme in einem neuen Fenster öffnen und näher untersuchen oder Ihre eigenen Darstellungsfunktionen hinzufügen.

Run-time visualizations generated while the function is being optimized using genetic algorithm plot functions selected in the Optimization app.

Laufzeit-Visualisierungen (rechts), die mit Plot-Funktionen während der Optimierung mithilfe des Genetischen Algorithmus erzeugt wurden, sowie Auswahl der Plot-Funktionen in der Optimization-App (links).

Mithilfe der Output-Funktion lassen sich Ergebnisse in Dateien schreiben, eigene Abbruchbedingungen erzeugen und eigene Apps zur Ausführung von Solvern der Toolbox schreiben. Aus der Optimization-App lassen sich Problem- und Algorithmen-Optionen in den MATLAB Workspace exportieren, Arbeiten abspeichern und später wiederverwenden, oder MATLAB-Code erzeugen, der den aktuellen Stand der Arbeit festhält.

MATLAB file of an optimization created using the automatic code generation feature in the Optimization app. You can export an optimization from the app as commented code that can be called from the command line and used to automate routines and preserve your work.

Dieses MATLAB-File zur Optimierung wurde mithilfe der Funktion zur automatischen Codegenerierung aus der Optimization-App erzeugt. Aus der App kann eine Optimierung als kommentierter Code exportiert werden, der sich von der Kommandozeile aus aufrufen lässt und zur Automatisierung von Routinen sowie zum Abspeichern von Arbeiten genutzt werden kann.

Während eine Optimierung ausgeführt wird, können Sie Optionen ändern, um die Lösung zu verfeinern und die Ergebnisse im Genetic-Algorithmus, multikriteriellen Genetic-Algorithmus, simulierten Annealing-Solver und Pattern Search-Solver zu aktualisieren. Sie können zum Beispiel Darstellungsoptionen, Ausgabeoptionen und die iterative Befehlszeilen-Anzeige während der Laufzeit aktivieren oder deaktivieren, um Zwischenergebnisse anzuzeigen und den Lösungsfortschritt abzufragen, wobei Sie den Solver nicht beenden und neu starten müssen. Sie können auch Stoppbedingungen ändern, um den Lösungsablauf abzustimmen oder die Anzahl der Iterationen, die basierend auf dem Laufzeit-Performance-Feedback zur Erreichung der gewünschten Toleranz erforderlich ist.

Globale Suche und Multistart-Solver

Der Globale Suche-Solver und Multistart-Solver arbeitet mit Gradienten-basierten Methoden zur Ausgabe lokaler und globaler Minima. Bei beiden Solvern werden ein lokaler Solver (in der Optimization Toolbox) von mehreren Startpunkten aus gestartet und lokale und globale Lösungen, die während des Suchvorgangs gefunden wurden, gespeichert.

Der Globale Suche-Solver:

  • erzeugt mehrere Startpunkte mit einem Streu-Such-Algorithmus
  • filtert die nicht aussichtsreichen Startpunkte anhand von Ziel- und Bedingungsfunktionswerten und bereits ermittelten lokalen Minima aus
  • führt einen beschränkten nicht linearen Optimierungs-Solver aus, um unter den verbliebenen Startpunkten das lokale Minimum zu ermitteln

Der Multistart-Solver verwendet entweder innerhalb von vordefinierten Grenzen gleichmäßig verteilte Startpunkte oder benutzerdefinierte Startpunkte, um mehrere lokale Minima sowie ein einzelnes globales Minimum, sofern vorhanden, zu ermitteln. Der Multistart-Solver führt den lokalen Solver von allen Startpunkten aus und kann seriell oder parallel ausgeführt werden (mithilfe der Parallel Computing Toolbox™). Der Multistart-Solver bietet außerdem die Flexibilität, verschiedene lokale nicht lineare Solver auswählen zu können. Zu den verfügbaren lokalen Solvern gehören: unbeschränkt nicht-linear, beschränkt nicht-linear, nicht-linearen Methode der kleinsten Quadrate und nicht lineare Kurvenanpassung mit der Methode der kleinsten Quadrate.

Nicht-lineare Optimierung mit dem Global Search Solver 3:57
Lokale und globale Minima der peaks-Funktion werden ermittelt.

Nicht-lineare Regression mit dem Multistart Solver 4:16
Die geeignetsten Parameter für ein Exponentialmodell werden ermittelt.

Genetischer Algorithmus

Mit dem Genetic-Algorithmus werden Optimierungsprobleme gelöst, indem die Prinzipien der biologischen Evolution nachgeahmt werden. Dies geschieht durch das wiederholte Ändern einer Population von einzelnen Punkten mithilfe von Regeln, die anhand von Genkombinationen gebildet wurden, die in der biologischen Fortpflanzung vorkommen. Dieser zufallsbedingte genetische Algorithmus erhöht die Chancen, eine globale Lösung zu finden. Mithilfe des Algorithmus können Sie allgemeine, unbeschränkte und Grenz-Bedingungs-Optimierungsprobleme lösen, und die Funktionen müssen nicht differenzierbar oder stetig sein.

In der folgenden Tabelle werden die Standard-Genetic-Algorithmus-Optionen der Global Optimization Toolbox angeführt.

SchrittGenetic-Algorithmus-Option
ErstellungGleichmäßig, zulässig
Fitness ScalingRang-basiert, proportional, abschneiden, Shift linear
AuswahlRoulette, Stochastic Uniform Selection (SUS), Tournament, gleichmäßig, Rest
CrossoverArithmetisch, heuristisch, intermediär, gestreut, Einzelpunkt, Zweipunkt
MutationAdaptiv zulässig, gaußverteilt, gleichmäßig
GlättungBeste Fitness, bestes Individuum, Abstände zwischen Individuen, Diversität von Populationen, Erwartung von Individuen, Max.-Bedingung, Bereich, Auswahlindex, Stoppbedingungen

Die Global Optimization Toolbox ermöglicht auch folgende Festlegungen:

  • Populationsgröße
  • Anzahl von Elite Children
  • Crossover-Bruchzahl
  • Migration unter Subpopulationen (unter Verwendung von Ringtopologie)
  • Lineare, nicht lineare und Grenzbedingungen für ein Optimierungsproblem

Sie können diese Algorithmusoptionen anpassen, indem Sie benutzerdefinierte Funktionen bereitstellen und das Problem in mehreren Datenformaten abbilden, indem Sie beispielsweise ganzzahlige, gemischt-ganzzahlige, kategorische oder komplexe Variablen definieren.

Sie können die Stoppkriterien für den Algorithmus auf Zeit, Stalling, Fitness-Grenzwert oder Generationenanzahl stützen. Außerdem können Sie die Fitness-Funktion vektorisieren, um die Ausführungsgeschwindigkeit zu erhöhen. Oder Sie führen die Ziel- und Bedingungsfunktionen mithilfe der Parallel Computing Toolbox parallel aus.

Optimal Component Selection Using the Mixed-Integer Genetic Algorithm 5:25
Use the mixed-integer genetic algorithm to solve an engineering design problem.

Multikriterieller Genetischer Algorithmus

Aufgabe einer Mehrzieloptimierung ist die gleichzeitige Minimierung mehrerer Zielfunktionen mit verschiedenen Nebenbedingungen. Mit dem multikriteriellen Genetic-Algorithmus-Solver werden multikriterielle Optimierungsprobleme gelöst, indem die Pareto-Front identifiziert wird - der Satz von gleichmäßig verteilten nicht majorisierten optimalen Lösungen. Mit diesem Solver können Sie glatte und nicht glatte Optimierungsprobleme mit oder ohne lineare und Grenzbedingungen lösen. Der multikriterielle Genetic-Algorithmus setzt nicht voraus, dass die Funktionen differenzierbar oder stetig sind.

In der folgenden Tabelle werden die Standardoptionen des multikriteriellen Genetic-Algorithmus, die in der Global Optimization Toolbox verfügbar sind, angeführt.

SchrittOption des multikriteriellen Genetic-Algorithmus
ErstellungGleichmäßig, zulässig
Fitness ScalingRang-basiert, proportional, abschneiden, lineare Skalierung, Shift
AuswahlTournament
CrossoverArithmetisch, heuristisch, intermediär, gestreut, Einzelpunkt, Zweipunkt
MutationAdaptiv zulässig, Gauß, gleichmäßig
Grafische DarstellungDurchschnittlicher Pareto-Abstand, durchschnittliche Pareto-Streubreite, Abstand zwischen Individuen, Diversität der Population, Erwartung von Individuen, Pareto-Front, Ranghistogramm, Auswahlindex, Stoppbedingungen

Die Global Optimization Toolbox ermöglicht auch folgende Festlegungen:

  • Populationsgröße
  • Crossover-Bruchzahl
  • Pareto-Bruchzahl
  • Messen des Abstands zwischen Individuen
  • Migration unter Subpopulationen (unter Verwendung von Ringtopologie)
  • Lineare und Grenzbedingungen für ein Optimierungsproblem

Sie können diese Algorithmusoptionen anpassen, indem Sie benutzerdefinierte Funktionen bereitstellen und das Problem in mehreren Datenformaten abbilden, indem Sie beispielsweise ganzzahlige, gemischt-ganzzahlige, kategorische oder komplexe Variablen definieren.

Sie können die Stoppkriterien für den Algorithmus auf Zeit, Fitness-Grenzwert oder Generationenanzahl stützen. Außerdem können Sie die Fitness-Funktion vektorisieren, um die Ausführungsgeschwindigkeit zu erhöhen. Oder Sie führen die Zielfunktionen mithilfe der Parallel Computing Toolbox parallel aus.

Multiobjective genetic algorithm defined in the Optimization app, used to identify the Pareto front containing disconnected regions for the Kursawe function.

In der Optimization-App definierter multikriterieller Genetic-Algorithmus (oben), mit dem die Pareto-Front identifiziert wird, die die unzusammenhängenden Gebiete (Mitte) der Kursawe-Funktion (unten) enthält.

Pattern Search

Die Global Optimization Toolbox verfügt über drei Algorithmen zur direkten Suche: Generalized Pattern Search (GPS), Generating Set Search (GSS) und Mesh Adaptive Search (MADS). Während bei herkömmlichen Optimierungsalgorithmen der optimale Punkt mithilfe von genauen oder Näherungsdaten des Gradienten oder der höheren Ableitungen gesucht wird, wird bei diesen Algorithmen eine Mustersuchmethode verwendet, die ein positives Minimum- und Maximumgrundmuster implementiert. Bei der Pattern Search-Methode werden Optimierungsprobleme mit nicht linearen, linearen und Grenzbedingungen verarbeitet, wobei die Funktionen nicht differenzierbar oder stetig sein müssen.

In der folgenden Tabelle werden die Pattern Search-Algorithmus-Optionen der Global Optimization Toolbox angeführt. Sie können die Optionen über die Befehlszeile oder das Optimization Tool ändern.

Pattern Search Solver-OptionBeschreibung
Polling-MethodenEntscheiden Sie, wie die Punkte in einem Muster und die maximale Anzahl von Punkten, die in einem Schritt erzeugt wird, erzeugt und evaluiert werden sollen. Sie können auch die Polling-Reihenfolge der Punkte festlegen, um die Effizienz zu steigern.
SuchmethodenWählen Sie einen optionalen Suchschritt, der möglicherweise effizienter als ein Polling-Schritt ist. Sie können eine Suche in einem Muster oder im gesamten Suchraum ausführen. Um einen guten Startpunkt zu erhalten, kann eine globale Suchmethode, wie der Genetic-Algorithmus, verwendet werden.
NetzLegen Sie fest, wie sich das Muster im Laufe mehrerer Iterationen ändert, und passen Sie das Netz bei Problemen an, dessen Skalierung der Größen variiert. Sie können die Anfangsnetzgröße, den Netzverfeinerungsfaktor und den Netzzusammenziehungsfaktor wählen. Der Netz-Accelerator beschleunigt die Konvergenz in der Nähe eines Minimums.
CacheSpeichern Sie Punkte, die während der Optimierung von rechenintensiven Zielfunktionen evaluiert wurden. Sie können die Größe und Toleranz des Cache festlegen, das den Pattern Search-Algorithmus verwendet. Während der Algorithmus ausgeführt wird, können Sie die Cache-Toleranz ändern, um die Optimierungsgeschwindigkeit zu erhöhen.
Einstellungen des nicht linearen BedingungsalgorithmusLegen Sie einen Penalty-Parameter für die nicht linearen Bedingungen und einen Penalty-Aktualisierungsfaktor fest.

Using the Optimization Tool (top) to find the peak, or global optima, of the White Mountains (middle and bottom) using pattern search.

Ermittlung der Gipfelhöhe oder globalen Optima der White Mountains (Mitte und unten) mithilfe der Optimization-App (oben) unter Verwendung der Mustersuche.

Simulated Annealing

Mit Simulierter Annealing werden Optimierungsprobleme unter Verwendung eines wahrscheinlichkeitstheoretischen Suchalgorithmus gelöst. Der Algorithmus bildet den physikalischen Prozess einer Glühung nach, bei dem ein Material erhitzt wird und die Temperatur dann langsam gesenkt wird, um Defekte zu verringern, so dass die Systemenergie minimiert wird. Analog wird mit jeder Iteration eines simulierten Glühalgorithmus versucht, das aktuelle Minimum zu verbessern, indem der Suchumfang langsam reduziert wird.

Der simulierte Glühalgorithmus akzeptiert alle neuen Punkte, die das Ziel verringern, jedoch auch mit einer bestimmten Wahrscheinlichkeit Punkte, die das Ziel erhöhen. Indem Punkte akzeptiert werden, die das Ziel erhöhen, wird vermieden, dass der Algorithmus bei frühen Iterationen in lokalen Minima gefangen bleibt. Der Algorithmus kann somit globale Untersuchungen vornehmen, um bessere Lösungen zu erzielen.

Mithilfe des simulierten Annealing-Algorithmus können Sie unbeschränkte oder Grenzbedingungs-Optimierungsprobleme lösen, und es ist nicht erforderlich, dass die Funktionen differenzierbar oder stetig sind. Sie können auf die Toolbox-Funktionen über die Befehlszeile oder die Optimization-App zugreifen und Folgendes ausführen:

  • Probleme mit adaptiv simulierten Annealing-, Boltzmann-Annealing- oder schnellen Annealing-Algorithmen lösen
  • Benutzerdefinierte Funktionen erstellen, um den Annealing-Prozess, die Akzeptanzkriterien, den Temperaturplan, die Darstellungsfunktionen, die Simulationsausgabe oder eigene Datentypen zu definieren
  • Hybrid-Optimierung ausführen, indem eine weitere Optimierungsmethode angegeben wird, die in definierten Intervallen oder nach der Solverbeendigung ausgeführt wird
Using simulated annealing to solve a challenging problem that contains flat regions between basins.

Lösung eines anspruchsvollen Problems, das flache Bereiche zwischen Becken umfasst, mithilfe eines simulierten Annealing-Algorithmus.

Lösung von Optimierungsproblemen durch Parallel Computing

Sie können die Global Optimization Toolbox zusammen mit der Parallel Computing Toolbox bei Problemen verwenden, die mit parallelem Rechnen effektiver gelöst werden können. Sie können die zur Lösung benötigte Zeit verkürzen, indem Sie die integrierten Parallelrechenfunktionen verwenden oder eine eigene Parallelrechenimplementierung für das Optimierungsproblem definieren.

Mit den integrierten Parallelrechenfunktionen kann die Evaluierung von Ziel- und Bedingungsfunktionen im Genetic-Algorithmus-, multikriteriellen Genetic-Algorithmus- und Pattern Search Solver beschleunigt werden. Sie können den Multistart-Solver beschleunigen, indem Sie die lokalen Solver-Aufrufe auf mehrere MATLAB-Arbeitsplätze verteilen oder indem Sie die Parallel-Gradient-Schätzung in den lokalen Solvern aktivieren.

Optimierung des Schaltvorgangs zur Optimierung des Kraftstoffverbrauchs 5:33
Optimieren Sie 20 Parameter bei einem Schaltvorgang, um den Kraftstoffverbrauch für ein Doppelkupplungsgetriebe zu optimieren. Globale Optimierungsalgorithmen und paralleles Rechnen werden zur Beschleunigung der Optimierung verwendet.

Bei der benutzerdefinierten Parallelrechenimplementierung muss das Optimierungsproblem festgelegt werden, bei dem die Parallelrechenfunktion verwendet werden soll. Sie können entweder die Zielfunktion oder die Constraint Funktion für die Verwendung von parallelem Rechnen definieren und somit die für die Evaluierung des Ziels bzw. der Nebenbedingung erforderliche Zeit verringern.

Nicht-lineare Regression mit dem Multistart Solver 4:16
Die geeignetsten Parameter für ein Exponentialmodell werden ermittelt.

Probieren Sie Global Optimization Toolbox

Testsoftware anfordern

Mathematische Optimierung mit MATLAB

Webinar anzeigen