Trajektorien-Metaheuristiken erklärt
Trajektorienbasierte Metaheuristiken verbessern EINE Lösung Schritt für Schritt, statt eine ganze Population zu pflegen (siehe die Populations-Metaheuristiken-Linie). Das durchgehende Beispiel ist eine Lieferroute (Depot + n Stopps, wie in der Tourenplanung); die letzten Stücke wachsen vom TSP zum CVRP (Fahrzeug-Kapazität, mehrere Routen), sobald Züge zwischen Routen den Kern der Sache ausmachen.
Von der Wurzel (Hill Climbing, bleibt im ersten lokalen Optimum stecken) gehen sechs unabhängige Antworten aus: Verschlechterungen akzeptieren (Simulated Annealing → Parallel Tempering), eine gute Tour gezielt stören statt wegwerfen (Iterated Local Search → Variable Neighborhood Search), ein deterministisches Gedächtnis (Tabu Search), randomisiert-gierige Konstruktion (GRASP) und der Nachbarschafts-Zweig (Lin-Kernighan, Dynasearch, VRP-Nachbarschaften). ALNS schließt die Linie als Konvergenzpunkt ab: es lernt, welcher große Umbau sich lohnt, statt wie VNS zu eskalieren oder wie VRP-Nachbarschaften feste Züge zu nutzen. Guided Local Search ist das Gegenstück zu Tabu Search: keine Sperre, die nach einer festen Zahl Iterationen verfällt, sondern eine Strafe in der Zielfunktion selbst, die nie verfällt (gemessen unter knappem Budget nahezu identisch mit Tabu Search, darüber ein klarer, relativ weiter wachsender Vorsprung). Jedes Stück misst zuerst, dann behauptet es: mehrere Vorab-Hypothesen wurden von den eigenen Messungen widerlegt, nicht nur bestätigt.
In short: Covers trajectory-based (single-solution) metaheuristics: hill climbing, simulated annealing, tabu search and adaptive large neighborhood search (ALNS). Interactive demos start with a TSP route and grow to CVRP, with 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
Simulated Annealing verständlich erklärt
Warum eine Route, die nur noch kürzer werden darf, in der ersten Mulde hängen bleibt und wie das Annehmen von Verlängerungen mit sinkender Temperatur herausführt: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Die zwölf Stücke im Überblick
Von der Wurzel (Hill Climbing) führen sieben Kanten aus: zu Simulated Annealing, Iterated Local Search, Tabu Search, GRASP und den drei Stücken des Nachbarschafts-Zweigs (Lin-Kernighan, Dynasearch, VRP-Nachbarschaften). Simulated Annealing führt weiter zu Parallel Tempering, Iterated Local Search zu Variable Neighborhood Search.
ALNS ist der Konvergenzpunkt (Doppelrahmen): eine Kante von Variable Neighborhood Search (lernt statt eskaliert) UND eine von VRP-Nachbarschaften (großer statt kleiner Zug). Die gepunktete Querkante von Iterated Local Search zu Lin-Kernighan zeigt eine übernommene Idee, keinen Fix: Chained Lin-Kernighan nutzt denselben Doppelbrücken-Kick als äußere Schleife.
Die gestrichelte Doppelpfeil-Kante von Tabu Search zu Guided Local Search ist ein Gegenstück, kein Fix: dasselbe Problem (über ein lokales Optimum hinaus, ohne Struktur wegzuwerfen), der entgegengesetzte Mechanismus (eine Strafe statt einer verfallenden Sperre).
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)
- übernimmt nur eine Idee
- Zusammenfluss mehrerer Stränge
Die gepunktete Kante (Iterated Local Search → Lin-Kernighan) ist eine übernommene Idee (Chained LK), kein Fix. Die gestrichelte Doppelpfeil-Kante (Tabu Search ↔ Guided Local Search) ist ein Gegenstück: derselbe Zweck, andere Bauweise. Der Doppelrahmen (ALNS) markiert die Konvergenzkante.
Verwandt in anderen Linien
- Populations-Metaheuristiken — Die Wurzel dieser Linie ist dort selbst Fremdknoten im Graphen: Der Memetische Algorithmus poliert jedes Kind der Population mit genau diesem Hill-Climbing-Abstieg.
- Klassische Scheduling-Theorie — Die Job-Shop-Tabu-Search-Demo dort nutzt dieselbe Grundidee wie Tabu Search hier (eine Tabu-Liste gegen Zyklen), aber mit einer winzigen, gezielten N5-Nachbarschaft am kritischen Pfad statt der vollen paarweisen Nachbarschaft für die Lieferroute. Gemessen konvergiert die Job-Shop-Fassung selbst von einem schwächeren Start aus fast immer zum gleichen Ergebnis, während hier ein guter Start stark zählt: derselbe Mechanismus, zwei unterschiedliche Empfindlichkeiten.
- Turnierplanung — Das Traveling Tournament Problem dort nutzt denselben Verschlechterungen-akzeptieren-Mechanismus wie die Simulated-Annealing-Demo hier: die TTP-Demo wendet ihn auf drei turnierspezifische Zugarten (Heimrecht/Runden/Teams tauschen) statt einer generischen Nachbarschaft an.
- Härte und Struktur — Die iterierte Lokalsuche wirkt auch auf Mengen statt Touren: die Reduktions-Demo der Linie Härte und Struktur stört die Lösung, indem sie einen Knoten der unabhängigen Menge erzwingt, statt wie die Iterated Local Search eine Doppelbrücke in eine Tour zu setzen, und steigt mit dem (1,2)-Tausch wieder ab; vorher verkleinern Reduktionsregeln den Graphen.
- Komplexitätsklassen — Eine Lokalsuche endet in einem lokalen Optimum; die Demo zu lokalen Optima fragt, wie viele Schritte dieser Weg höchstens und typischerweise braucht und welche Wahlregel der Schritte darüber entscheidet.
Hill Climbing an einer Lieferroute
Verfolgen Sie, wie ein Abstieg, der Tourstücke umdreht, solange die Tour kürzer wird, im ersten lokalen Optimum stecken bleibt: bei 60 Stopps und zufälliger Startlösung im Mittel 7,9 % über einer unteren Schranke, mit erheblicher Streuung von Lauf zu Lauf. Die Demo vergleicht Nachbarschaften und Startlösungen. Die Nachbarschaft entscheidet mehr als die Startlösung: Mit zusätzlichem Einfügen von Tourstücken an anderer Stelle (Or-opt) sind es nur 3,7 %.
Demo starten →Simulated Annealing an derselben Lieferroute
Sehen Sie, wie das Akzeptieren von Verschlechterungen mit sinkender Wahrscheinlichkeit einem einzelnen Hill-Climbing-Abstieg klar überlegen ist: bei gleichem Budget liegt die beste Tour bei 1,4 % über der Schranke gegen 7,9 % für einen Abstieg. Der Vorsprung schrumpft mit wachsendem Budget, und der Temperaturbereich muss stimmen: zu heiß kommt die Kette gar nicht zur Ruhe.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Parallel Tempering an derselben Lieferroute
Verfolgen Sie, wie mehrere feste Temperaturen gleichzeitig laufen und Zustände tauschen, statt einen Abkühlplan zu fahren: eine gut platzierte Leiter schlägt kalibriertes Simulated Annealing knapp (1,15 % gegen 1,42 %), und der Vorsprung bleibt auch bei großem Budget bestehen. Aber Parallel Tempering ist nicht tuningfrei: eine schlecht gewählte Leiter kostet 3-6x mehr.
Demo starten →Iterated Local Search an derselben Lieferroute
Sehen Sie, wie ein Doppelbrücken-Zug eine gute Tour gezielt stört, statt sie wegzuwerfen: bei 200 Tausend Vorschlägen liegt die beste Tour bei 0,64 % gegen 0,68 % für Hill Climbing mit derselben lokalen Suche. Der Vorsprung ist bei knappem Budget größer und schrumpft mit wachsendem Budget fast auf null.
Demo starten →Variable Neighborhood Search an derselben Lieferroute
Verfolgen Sie, wie sich die Störstärke selbst anpasst: Sie eskaliert nach einem erfolglosen Stoß und springt nach einem Erfolg zurück auf die kleinste Stufe. Ein Budget-Vergleich zeigt live, dass VNS mit kalibriertem k_max die naive Störstärke 1 bei jedem gemessenen Budget schlägt oder erreicht. Überraschung: Der von Hand kalibrierte Sweet Spot (Störstärke 3) ist selbst nicht robust und verschiebt sich mit dem Budget.
Demo starten →Tabu Search an derselben Lieferroute
Sehen Sie, wie ein deterministisches Gedächtnis verhindert, dass ein Zug sofort rückgängig gemacht wird: Tabu Search braucht ein deutlich höheres Mindestbudget als jedes andere Stück dieser Linie (unter 100 Tausend katastrophal, 55-288 % über der Schranke), gewinnt dann aber klar. Der Vorsprung ist ein Fenster, kein Dauerzustand.
Demo starten →Guided Local Search an derselben Lieferroute
Sehen Sie das Gegenstück zu Tabu Search: Statt Kanten zeitweise zu verbieten, bekommt jede Tourkante eine Strafe, die nie verfällt. Ein Budget-Regler zeigt live, dass beide bei knappem Budget nahezu identisch sind und die dauerhafte Strafe bei großem Budget klar davonzieht (0,52 % gegen 1,9 % über der Schranke am größten getesteten Budget). Bei größeren Instanzen verschwindet der Vorteil wieder.
Demo starten →GRASP an derselben Lieferroute
Verfolgen Sie, wie jeder Neustart randomisiert-gierig statt rein zufällig konstruiert wird: GRASP schlägt zufällige Neustarts bei gleichem Budget klar (4,34 % gegen 4,88 % bei 200 Tausend), aber nur in einem mittleren Budgetfenster, bei sehr großem Budget holt reiner Zufall auf und zieht knapp vorbei.
Demo starten →Lin-Kernighan an derselben Lieferroute
Sehen Sie, wie die lokale Suche mehrere Kanten weit vorausschaut statt nur einen einzelnen Zug: bei Standardbudget sind Tiefe 1 und Tiefe 2 praktisch gleichauf (0,64 % gegen 0,66 %). Die Tiefe zahlt sich erst ab 500 Tausend Vorschlägen oder bei größeren Instanzen aus, und nur mit gezielter Wiederverwendung (Kicks), nicht bei unabhängigen Neustarts.
Demo starten →Dynasearch an derselben Lieferroute
Verfolgen Sie, wie mehrere unabhängige verbessernde Züge auf einmal gefunden werden statt einer nach dem anderen: Dynasearch braucht bei einem einzelnen Abstieg immer weniger Bewertungen (1,1- bis 3,9-fach, wachsend mit der Größe) und gewinnt den Budget-Vergleich bei jedem getesteten Budget klar, aber die Güte des Optimums dreht sich ab etwa 80 Stopps zugunsten der sequentiellen Suche.
Demo starten →VRP-Nachbarschaften an mehreren Routen mit Kapazität
Sehen Sie, wie Züge zwischen mehreren Routen (Relocate, Swap, 2-opt*, CROSS-exchange) erst mit einer Fahrzeug-Kapazität möglich werden. Ein Kapazitäts-Regler zeigt live: Bei mittlerer Kapazität verdreifacht sich die Verbesserung fast (2,47 % gegen 0,87 % bei reiner Suche innerhalb der Routen). Der Haken: Mehr Routen heißen nicht mehr Gewinn, das Maximum liegt bei mittlerer Kapazität; ein einziger der vier Züge trägt fast so viel wie alle zusammen.
Demo starten →ALNS an mehreren Routen mit Kapazität
Verfolgen Sie, wie ein großer, adaptiver Umbau (Destroy + Repair) statt eines kleinen festen Zugs die Lösung verbessert: ALNS schlägt die kleine Nachbarschaft der Schwester-Demo klar (8,89 % gegen 2,28 % Verbesserung bei gleichem Budget). Aber die zweite Hypothese trägt nicht: adaptive Operator-Gewichte bringen praktisch nichts gegenüber gleichverteiltem Zufall.
Demo starten →Welche Trajektorien-Metaheuristik passt zu meiner Aufgabe?
Zwei Entscheidungsbäume: Baum 1 führt durch fünf der sechs unabhängigen Antworten der Wurzel (acht Verfahren von Hill Climbing bis Guided Local Search), Baum 2 durch den Nachbarschafts-Zweig und die CVRP-Konvergenz (vier Verfahren von Lin-Kernighan bis ALNS). Alle Antworten stützen sich auf Messungen in den Demos.
Baum 1: Welche Antwort auf das erste lokale Optimum?
Baum 2: Nachbarschafts-Zweig und CVRP-Konvergenz
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Was die Bäume nicht zeigen: Chained Lin-Kernighan kombiniert Baum 2s Ergebnis mit Baum 1s Iterated-Local-Search-Mechanismus (der Doppelbrücken-Kick als äußere Schleife), eine Kombination, keine eigene Verzweigung. Tabu Search und Guided Local Search teilen sich denselben Budget-Boden: beide bewerten jede Iteration die volle Nachbarschaft, bei sehr knappem Budget ist trotz Gedächtnis oder Strafe ein einzelner Hill-Climbing-Abstieg oft konkurrenzfähiger, und unter 100 Tausend Vorschlägen sind beide Verfahren nahezu ununterscheidbar.
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.
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.
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.