Optimierung erklärt
Optimieren heißt, aus sehr vielen zulässigen Lösungen eine beste oder zumindest gut begründete zu wählen. Die fünfzehn Linien dieses Bereichs unterscheiden sich vor allem darin, was sie über das Ergebnis garantieren: Exakte Verfahren liefern eine nachweislich beste Lösung oder eine Schranke, Metaheuristiken eine gute Lösung in vertretbarer Zeit, die Verfahren für Unsicherheit und mehrere Ziele eine Entscheidung, die trägt, wenn Eingaben schwanken oder Ziele sich widersprechen.
Jede Linie hat eine eigene Seite mit einem Abhängigkeitsgraphen und ihren Demos. Die Themenfelder unten ordnen die Linien nach Verwandtschaft, der Beziehungsgraph am Ende zeigt, welche Linien sich Bausteine teilen.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
Mathematische Programmierung
Das Problem wird als Modell mit Variablen, Nebenbedingungen und Zielfunktion gefasst, und die Verfahren nutzen seine Struktur (Ganzzahligkeit, Linearität, Glattheit), um Lösungen zu finden oder ihren Abstand zum Besten abzuschätzen.
Exakte Suche
Bewiesen beste statt nur guter Lösungen: zwei Linien, Rucksack und Cutting Stock, von Branch & Bound bis Column Generation und Branch & Price.
Zur Linie →Lineare Programmierung
Was steckt in einem LP-Löser? Elf Stücke vom Tableau-Simplex über Schattenpreise und Innere Punkte bis zum Crossover, alle von Grund auf geschrieben und gemessen.
Zur Linie →Nichtlineare Optimierung
Wie findet man ein Minimum, wenn nichts linear ist? Acht Stücke vom ersten Schritt bergab über Krümmung und Nebenbedingungen bis zur Brücke ins Deep Learning, jedes mit gemessenem statt behauptetem Befund.
Zur Linie →Metaheuristiken und Suche
Verfahren ohne Beweis, dafür mit guten Lösungen auch dort, wo exakte Verfahren aufgeben: Nachbarschaften, Populationen, Baumsuche mit Heuristik und gezielte Vielfalt.
Populations-Metaheuristiken
Wie durchsucht eine ganze Population den Lösungsraum? Elf Verfahren von der Kreuzung über Kovarianzmatrizen bis zu Pheromonspuren, jedes mit seiner gemessenen Grenze.
Zur Linie →Trajektorien-Metaheuristiken
Wie kommt eine einzelne Lösung über ihr erstes lokales Optimum hinaus? Zwölf Verfahren von Verschlechterungen akzeptieren bis Destroy-and-Repair, jedes mit seiner gemessenen Grenze.
Zur Linie →Heuristische Baumsuche
Was bleibt von der Suche, wenn man das Optimum nicht abwarten kann? Acht Verfahren von der gierigen Suche bis Monte Carlo Tree Search, jedes mit seiner gemessenen Grenze.
Zur Linie →Novelty Search und Quality-Diversity
Ein Hof-Roboter im täuschenden Labyrinth, zwölf Stücke: von der Sackgasse der Fitness über Novelty Search und MAP-Elites bis zu Go-Explore, Routing und POET.
Zur Linie →Planung und Betrieb
Entscheidungen über Aufträge, Standorte und Wartezeiten: wer wann an die Reihe kommt, wo etwas stehen soll und wie ein System unter Last reagiert.
Standortplanung
Welche Standorte eröffnen, wenn jeder Kunde zum nächsten offenen geht? Sechs Stücke von der einfachen Fixkosten-Entscheidung über Kapazität, Maximum statt Summe und Lagerbestand bis zum Wettbewerb zweier Spieler und zum Hub mit Rabatt.
Zur Linie →Klassische Scheduling-Theorie
Ein wachsendes Beispiel von einer Maschine bis zum allgemeinen Ressourcenmodell: elf Stücke, jedes hebt genau eine Annahme des vorigen auf.
Zur Linie →Warteschlangentheorie und Simulation
Ein Terminal-Gate, dreizehn Stücke und ein Zusatzstück: jedes hebt genau eine Annahme der Formel davor auf, bis zum Netz aus Gate, Kran und Stapel und seinem Ersatzmodell.
Zur Linie →Mittelwerte und Lagemaße
Welche Zahl steht für die Mitte der Daten, wie genau rechnet man sie, und was geschieht bei Ausreißern, Quotienten, Uhrzeiten und Standorten in der Ebene? Sieben Stücke vom Mittelwert bis zur Mitte im Raum.
Zur Linie →Unsicherheit und mehrere Ziele
Entscheidungen, bei denen die Eingaben nicht feststehen, jede Auswertung teuer ist oder mehrere Ziele zugleich zählen.
Optimierung unter Unsicherheit
Eine Kapazität, die vor der unbekannten Nachfrage gewählt wird, sechs Stücke: vom Wert der Information über Stichprobe, CVaR, Robustheit und Garantie bis zur rollierenden Planung.
Zur Linie →Bayessche Optimierung und Gauß-Prozesse
Eine teure Simulation, sieben Stücke: vom Gauß-Prozess und der erwarteten Verbesserung über Rauschen und Nebenbedingungen bis zu hohen Dimensionen, parallelen Läufen und mehreren Genauigkeiten.
Zur Linie →Mehrkriterien-Ranking
Eine neutrale Entscheidungsmatrix, fünfzehn Stücke: von der Pareto-Dominanz über Gewichte, AHP, TOPSIS und Outranking bis zu unsicheren Gewichten, DEA, Gruppen und dem Verfahrensvergleich.
Zur Linie →Komplexität und Härtegrenzen
Was die Einordnung als NP-schwer wirklich sagt und welcher Ausweg zu welchem Härtegrund passt.
Komplexitätsklassen
Was sagt es aus, wenn ein Problem als NP-schwer gilt, und welcher Ausweg passt zu welchem Grund der Härte? Zehn Stücke über Reduktionen, typische Instanzen, große Zahlen, Garantien, Parameter, Zufall, Zählen, Spiele und lokale Optima.
Zur Linie →Empfohlene Reihenfolge
Wer einen Bereich von vorn lesen möchte: Die Reihenfolge folgt den Bausteinen, die eine Linie von einer anderen übernimmt (die Belege stehen auf den Linienseiten unter „Verwandt in anderen Linien“). Alles lässt sich auch einzeln lesen.
- Lineare Programmierung: Der Simplex ist der Baustein, dessen LP-Schranke die exakten Verfahren bei jedem Knoten neu rechnen.
- Exakte Suche: Bewiesen beste Lösungen: Branch & Bound und Schnittebenen nutzen die LP-Schranke aus dem Schritt davor.
- Nichtlineare Optimierung: Ableitungsbasiert (Gradient, Hesse-Matrix): der Gegenpol zu den ableitungsfreien Verfahren danach.
- Trajektorien-Metaheuristiken: Eine einzelne Lösung über ihr erstes lokales Optimum hinausbringen; Hill Climbing ist die Wurzel der Linie.
- Populations-Metaheuristiken: Eine ganze Population, ganz ohne Ableitungen; der Memetische Algorithmus führt sie mit dem Hill Climbing des Schritts davor zusammen.
- Novelty Search und Quality-Diversity: Beginnt mit einem einfachen Genetischen Algorithmus nach dem Muster der Populations-Linie und fragt, was passiert, wenn Fitness in die Sackgasse führt.
Die übrigen Linien (Standortplanung, Scheduling-Theorie, Warteschlangentheorie, Optimierung unter Unsicherheit, Bayessche Optimierung, Mehrkriterien-Ranking) greifen einzelne dieser Bausteine auf, ohne feste Reihenfolge; die Verbindungen zeigt der Beziehungsgraph weiter unten.
Wie die Linien dieses Bereichs zusammenhängen
Jede Kante steht für einen belegten Zusammenhang: Ein Verfahren nutzt innen eine Technik der anderen Linie, oder beide gehen dasselbe Problem aus verschiedenen Blickwinkeln an. Die Farbe zeigt das Themenfeld, gestrichelte Kästen sind Linien aus anderen Bereichen, mit denen es Verbindungen gibt. Die jeweilige Linienseite erklärt jeden Zusammenhang unter „Verwandt in anderen Linien“.
Die Kästen sind klickbar und öffnen die jeweilige Seite.
- Mathematische Programmierung
- Metaheuristiken und Suche
- Planung und Betrieb
- Unsicherheit und mehrere Ziele
- Komplexität und Härtegrenzen
- Linie eines anderen Bereichs
Weitere Bereiche
Maschinelles Lernen
Verfahren, die aus Daten lernen: Struktur finden, wenn niemand die Antwort vorgibt, vorhersagen, wenn Beispiele vorliegen, und handeln oder Wirkung messen.
Signalverarbeitung
Verfahren, die aus gemischten oder unscharfen Messungen die ursprünglichen Signale zurückgewinnen oder aus verrauschten Messungen einen Zustand schätzen.
Graphentheorie
Verfahren, die Fragen über Netze selbst beantworten: erreichbar, verbunden, kritisch, zugeordnet, zentral, schmalbandig oder wie sich etwas auf dem Netz ausbreitet.
Kooperation und Wettbewerb
Verfahren für Entscheidungen mit mehreren Beteiligten: Anreize und Kooperation, direkte Gegner, Turniere, Ranglisten und gemeinsames Entscheiden und Teilen.