Populations-Metaheuristiken erklärt
Populationsbasierte Metaheuristiken durchsuchen einen Lösungsraum nicht mit einer einzigen Lösung, sondern mit vielen gleichzeitig: Selektion, Rekombination und Mutation (oder ihre Entsprechungen) verbessern die ganze Population über viele Generationen. Das durchgehende Beispiel ist eine Lieferroute (Depot + n Stopps, wie in der Tourenplanung) und, bei den Verfahren für kontinuierliche Landschaften, die Wahl eines Verteilzentrum-Standorts mit mehreren lokalen Minima.
Der Graph geht von der Wurzel (Genetischer Algorithmus) in vier unabhängige Kontraste für unterschiedliche Suchmechanismen aus (CMA-ES, Differential Evolution, Partikelschwarm-Optimierung, Ant System) sowie in NSGA-II für mehrere Ziele gleichzeitig. Mehrere Stücke haben eigene Fix-Nachfolger, die eine benannte Schwäche beheben sollen (NSGA-III, L-SHADE, Max-Min Ant System). Das letzte Stück, der Memetische Algorithmus, ist die einzige Konvergenzkante der Linie: er kombiniert die Wurzel mit der lokalen 2-opt-Suche aus der Trajektorien-Metaheuristiken-Linie.
In short: Covers population-based metaheuristics: genetic algorithms, NSGA-II, CMA-ES, ant colony optimization and memetic algorithms. Interactive demos use delivery-route and facility-location examples and show a measured limit for each method.
Hintergrund zum Thema: Tourenplanung.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. So lesen Sie sie: Das Diagramm zeigt, wie die Stücke zusammenhängen. Jede Kachel darunter öffnet eine interaktive Demo, wo es eine gibt, mit einer Erklärseite für Einsteiger und Fachleute. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.
Zuletzt aktualisiert:
Welches Verfahren passt zu Ihrem Fall? Zum Entscheidungsbaum ↓
Zum Nachlesen: erst einfach, dann fachlich
Der Genetische Algorithmus verständlich erklärt
Warum eine ganze Gruppe von Lösungen mehr erreicht als eine einzelne, was Auswahl, Kreuzung und Mutation je beitragen und wo die Gruppe hängen bleibt: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Die elf Stücke im Überblick
Von der Wurzel (Genetischer Algorithmus) führen vier unabhängige Kontrast-Kanten zu CMA-ES, Differential Evolution, Partikelschwarm-Optimierung und Ant System: vier verschiedene Suchmechanismen für dieselbe Aufgabe. NSGA-II fügt mehrere Ziele hinzu und verzweigt weiter in NSGA-III (gedachter Fix: Referenzpunkte statt Crowding-Distance) und MOEA/D (Kontrast: Zerlegung statt Dominanz-Sortierung).
Differential Evolution und Ant System haben je einen eigenen Fix-Nachfolger (L-SHADE, Max-Min Ant System). Der Memetische Algorithmus führt die Wurzel mit Hill Climbing aus der Trajektorien-Linie (gestrichelter Fremdknoten) zusammen: die einzige Konvergenzkante der Linie.
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- Gegenstück: derselbe Zweck, andere Bauweise (kein Fix)
- Zusammenfluss mehrerer Stränge
- Baustein aus einer anderen Linie
Der gestrichelte Fremdknoten (Hill Climbing) stammt aus der Trajektorien-Metaheuristiken-Linie. Der Doppelrahmen (Memetischer Algorithmus) markiert die Konvergenzkante.
Verwandt in anderen Linien
- Trajektorien-Metaheuristiken — Der Memetische Algorithmus führt die Wurzel dieser Linie mit Hill Climbing aus der Trajektorien-Metaheuristiken-Linie zusammen: eine Population statt einer einzelnen Lösung, aber jedes Kind lokal poliert wie dort.
- Nichtlineare Optimierung — Die Nichtlineare-Optimierung-Linie ist durchgehend ableitungsbasiert (Gradient, Hesse-Matrix); diese Linie löst verwandte, oft ebenfalls nichtkonvexe Landschaften ganz ohne Ableitungen. Wer den Genetischen Algorithmus (Wurzel hier) mit einem ableitungsbasierten Gegenstück vergleichen will, findet in der Gradientenabstieg-Demo die Wurzel der Nichtlineare-Optimierung-Linie.
- Novelty Search und Quality-Diversity — Die Linie Novelty Search und Quality-Diversity beginnt mit einem einfachen Genetischen Algorithmus nach dem Muster der GA-Demo dieser Linie, setzt ihn in einem täuschenden Labyrinth ein und ersetzt die Auswahl nach der Zielnähe durch Neuartigkeit. Ihre Pareto-Auswahl folgt NSGA-II, und jeder Emitter von CMA-ME ist ein CMA-ES, hier allein, dort in einem Archiv.
- Bayessche Optimierung und Gauß-Prozesse — In der Hohe-Dimensionen-Demo der Linie Bayessche Optimierung tritt CMA-ES als Gegner ohne Ersatzmodell an: bei 48 Eingaben und 100 Auswertungen 0,558 gegen 0,129 für die Bayessche Optimierung, auf rauschfreien Testfunktionen.
- Mehrkriterien-Ranking — Die Pareto-Dominanz der Linie Mehrkriterien-Ranking misst das Sättigen der Dominanz ohne Suchlauf an einer gegebenen Menge: Bei 20 Alternativen und 5 Kriterien bleiben 71 % unbesiegt.
Genetischer Algorithmus an einer Lieferroute und Standortwahl
Verfolgen Sie, wie eine ganze Population aus Selektion, Crossover und Mutation eine Startpopulation verbessert: im Standardfall sinkt die beste Tour von 1434 km auf 733 km (48,9 % kürzer). Eine kleine Population verliert dabei oft zu früh an Vielfalt: nur 55 % der Läufe landen im globalen Trichter der Standortwahl, bei einer großen Population 95 %.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →NSGA-II an einer Lieferroute mit zwei Zielen
Sehen Sie, wie NSGA-II mehrere Ziele gleichzeitig über Pareto-Dominanz statt fester Gewichtung sortiert: auf derselben 8-Stopp-Instanz trifft NSGA-II im Median 6 von 8 Frontpunkten, eine feste Gewichtung nur 4 von 8.
Demo starten →NSGA-III an einer Lieferroute mit vier Zielen
Verfolgen Sie, wie NSGA-III bei vier Zielen die Vielfalt der Lösungen nicht mehr über den Abstand zu Nachbarn, sondern über ein festes Gitter aus Referenzpunkten im Zielraum sichert. Die Demo stellt NSGA-III und NSGA-II direkt gegenüber. Ehrlich gemessen liegt NSGA-II bei dieser Instanzgröße vorn (Median 14 gegen 8 von 56 Referenzpunkten abgedeckt), weil früh keine Lösung mehr eine andere schlägt und das Gitter dann nichts mehr auswählt.
Demo starten →MOEA/D an derselben Lieferroute
Sehen Sie, wie MOEA/D Zielkonflikte in Skalarisierungs-Unterprobleme statt Dominanz-Sortierung zerlegt: auf der identischen 8-Stopp-Instanz erreicht MOEA/D im Median 6 von 8 Frontpunkten (ungefähr NSGA-II-Niveau, über einen komplett anderen Mechanismus).
Demo starten →CMA-ES an einer mehrgipfligen Standortwahl
Verfolgen Sie, wie CMA-ES statt einer Population nur eine einzige Gauß-Glocke weiterentwickelt, die sich in flachen Richtungen streckt, in steilen staucht und mit dem Gelände dreht. Die Demo vergleicht CMA-ES mit dem genetischen Algorithmus auf derselben mehrgipfligen Standortwahl. Der Haken: CMA-ES trifft die globale Mulde nur in 15 % der Läufe, und mehr Rechenzeit hilft kaum, weil die Glocke im nächstgelegenen Trichter hängen bleibt.
Demo starten →Differential Evolution an derselben Standortwahl
Sehen Sie, wie Differential Evolution den Abstand zweier zufälliger Populationsmitglieder als Mutationsschritt nutzt: Ist die Population verstreut, sind die Schritte groß, verdichtet sie sich, werden sie klein. Die Demo vergleicht es mit GA und CMA-ES. DE trifft die globale Mulde in 100 % der Läufe, das beweist aber keine generelle Überlegenheit: Die gut getrennten Mulden dieser Landschaft begünstigen es, und bei knappem Budget hängt die Trefferquote vom Differenzgewicht ab.
Demo starten →L-SHADE an derselben Standortwahl
Verfolgen Sie, wie L-SHADE das Differenzgewicht F und die Kreuzungsrate CR selbst aus einem Erfolgsgedächtnis lernt: auf demselben knappen Budget wie DEs eigenem F-Experiment erreicht L-SHADE 80 % Trefferquote, ohne jede Handeinstellung nur knapp unter DEs bestem von Hand gewähltem F (90 %).
Demo starten →Partikelschwarm-Optimierung an derselben Standortwahl
Sehen Sie, wie ein Schwarm über Geschwindigkeit statt Kreuzung sucht: PSO trifft die globale Mulde in 90 % der Läufe. Das erwartete U-förmige Optimum beim Trägheitsgewicht w zeigt sich nicht sauber (Trefferquote steigt eher mit w), während die Diversität am Ende der Theorie sauber folgt.
Demo starten →Ant System an derselben Lieferroute
Verfolgen Sie, wie eine Kolonie über Pheromonspuren statt direkter Kommunikation eine Lieferroute findet: auf der kleinen Vergleichsinstanz trifft Ant System im Median (fast) exakt das Optimum. Eine zu kleine Verdunstungsrate schadet klar messbar, eine zu große kaum.
Demo starten →Max-Min Ant System an derselben Lieferroute
Sehen Sie, wie eine Pheromon-Obergrenze und nur die beste Ameise je Generation Stagnation verhindern: bei lockerem τ-Verhältnis kleben 6,67 % der Pheromonwerte nahe der Obergrenze, bei eng gewähltem Verhältnis 0,0 % (über 5 Seeds exakt reproduzierbar).
Demo starten →Memetischer Algorithmus an derselben Lieferroute
Verfolgen Sie, wie jedes Kind zusätzlich lokal poliert wird, bevor es Teil der nächsten Generation wird: voll memetisch findet auf einem knappen Budget eine um 52 % kürzere Tour als reines GA, kostet dafür aber rund 586.000 zusätzliche Bewertungen der lokalen Suche. Schon 10 % Polierwahrscheinlichkeit erfasst fast den ganzen Qualitätsgewinn.
Demo starten →Welche Populations-Metaheuristik passt zu meiner Aufgabe?
Ein Entscheidungsbaum über alle elf Stücke, entlang der Fragen, die die Linie selbst aufwirft: mehrere Ziele? kontinuierlich oder diskret? Die Antworten stützen sich auf Messungen in den Demos; Ausnahme ist der Zweig „mehr als drei Ziele“ (siehe Anmerkung).
Welche Populations-Metaheuristik passt?
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Was der Baum nicht zeigt: MOEA/D (Kontrast zu NSGA-II, Zerlegung statt Dominanz-Sortierung) und CMA-ES (Kontrast zu Differential Evolution, Kovarianz-Anpassung statt Differenzvektor) sind hier bewusst keine eigenen Blätter. Beide sind ernsthafte Alternativen ohne klaren Auslöser in der Problembeschreibung. Dass Differential Evolution auf der Landschaft dieser Linie messbar besser abschneidet als CMA-ES (100 % gegen 15 % Trefferquote) ist landschaftsspezifisch, keine allgemeine Überlegenheit. Beide Demos sagen das selbst so. Beim Zweig „mehr als drei Ziele“ folgt der Baum der Literatur (Deb und Jain 2014: Vorteil bis 15 Ziele); die Demo selbst misst bei vier Zielen NSGA-II vorn.
Weitere Linien in diesem Bereich
Exakte Suche
Bewiesen beste statt nur guter Lösungen: zwei Linien, Rucksack und Cutting Stock, von Branch & Bound bis Column Generation und Branch & Price.
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.
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.
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.
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.
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.
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.
Klassische Scheduling-Theorie
Ein wachsendes Beispiel von einer Maschine bis zum allgemeinen Ressourcenmodell: elf Stücke, jedes hebt genau eine Annahme des vorigen auf.
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.
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.
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.
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.
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.
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.