Einführung in die Optimierung

Im einfachsten Falle ist die Optimierung nur der Prozess, aus einer Reihe möglicher Optionen die beste Auswahl zu treffen.

Wir können das Beste auf viele Arten definieren: Dies kann die Option mit den niedrigsten Kosten, der schnellsten Runtime oder vielleicht der geringsten Auswirkung auf die Umgebung sein. Der Einfachheit halber verwenden wir in der Regel die Definition des Besten als die Option, die die Kosten minimiert. Wenn wir stattdessen die Kosten maximieren möchten (wenn wir z. B. die Energieausgabe einer Solarzelle maximieren möchten), müssen wir die Kosten nur mit -1 multiplizieren und dann minimieren.

Ein Optimierungsproblem bedeutet normalerweise, dass ein ziemlich kompliziertes Problem vorliegt, wobei viele Variablen auf viele Arten interagieren können, um die endgültigen Kosten zu beeinflussen. Eine bestimmte Anordnung der Variablen wird als Konfiguration des Problems bezeichnet.

Da es so viele mögliche Konfigurationen gibt, ist es manchmal sehr schwierig, die beste Lösung zu identifizieren, insbesondere wenn der Problembereich sehr groß ist. Es kann einfach sein, in einem lokalen Optimum stecken zu bleiben. Im folgenden Diagramm sind einige Beispiele lokaler Optima sowie das globale Optimum dargestellt. Dies ist die kostengünstigste Konfiguration, die unser System übernehmen kann.

Diagramm mit einer Kostenfunktion mit zwei lokalen Optima und hervorgehobenem globalen Optimum

Aus der Art und Weise, in der die Kosten als Funktion der Systemkonfiguration variieren, resultiert die sogenannte Kostenfunktion, die Linie im Diagramm. Das Ziel unserer Optimierung ist, den minimalen Punkt dieser Kostenfunktion zu finden (oder sich dem minimalen Punkt so weit wie möglich anzunähern, eine angemessene Zeit vorausgesetzt).

Dies wird anhand eines Beispiels veranschaulicht: Minimierung des Verkehrs. Das Ziel dieser Optimierungsaufgabe ist, die Staus in einem Straßensystem zu reduzieren, um die Wartezeit von Benutzern im Verkehr zu reduzieren.

Jede Konfiguration stellt eine andere Kombination von Routen dar, die den Fahrzeugen im System zugewiesen werden. Die Kosten sind das allgemeine Verkehrsaufkommen (oder das Aufkommen von Staus), das wir minimieren möchten.

Diagramm einer Kostenfunktion mit lokalen Optima gemäß des unterschiedlichen Verkehrsaufkommens in einer Fahrwegsimulation

Das obige Diagramm zeigt einige Beispiele verschiedener Systemkonfigurationen, von denen jede einen anderen Kostenwert hat. Wir haben die Kosten hier mit Farbe visualisiert: je intensiver rot das Straßensegment, desto höher das Verkehrsaufkommen und damit desto höher die Kosten. Im Gegensatz dazu werden intensiver grüne Straßensegmente von weniger Fahrzeugen gleichzeitig genutzt, und somit sind ihre Verkehrs- und Kostenwerte niedriger.