Novelty Search und Quality-Diversity erklärt
Zwölf Stücke mit demselben wachsenden Beispiel: ein Hof-Roboter, der mit einer offenen Steuerfolge von 140 Schritten durch ein Labyrinth zum Ziel fahren soll. Die Wurzel ist die Falle: eine Fitness, die „nah am Ziel“ misst, führt in die Sackgasse (Stufe 3 löst sie in 11 von 20 Läufen, die Schlangenlinie der Stufe 4 in keinem). Novelty Search wählt statt nach der Zielnähe nach der Neuartigkeit der Endposition und löst Stufe 3 in jedem Lauf. Die Folgestücke fragen, woran das hängt (die Verhaltensbeschreibung, ein Ziel in der Auswahl), und gehen dann zu Quality-Diversity über: MAP-Elites sammelt je Verhalten die beste Fahrt, mit lernenden CMA-Emittern, mit CVT-Zellen für viele Verhaltenswerte und mit einer aus den Rohdaten gelernten Beschreibung (AURORA).
Dazu zwei Gegenstücke: Go-Explore löst als einziges Verfahren der Linie die Schlangenlinie (erst zu einem Zwischenstand zurückkehren, dann erkunden), und ein Stück, das ehrlich misst, wo Novelty nicht hilft. Den Abschluss bilden zwei Stücke, die die Linie an Aufgaben der übrigen Seiten binden: Quality-Diversity im Routing (was kostet ein Fahrzeug mehr?) und POET, das Umgebungen und Agenten gemeinsam entwickelt. Alle Zahlen stehen in den README der Demos, jede Demo prüft ihren Kern gegen eine unabhängige Referenz (Orakel-Tests), und mehrere Stücke enden mit einem Negativbefund: auf die beste Strecke hilft Quality-Diversity im Routing nicht, und die einfache POET-Fassung löst keine der schweren Umgebungen.
In short: Covers novelty search and quality-diversity algorithms such as MAP-Elites, Go-Explore and POET, which counter deceptive fitness landscapes. Interactive demos build on one maze-robot example, with the objective-driven search as the starting point.
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
Novelty Search verständlich erklärt
Warum eine Suche, die nur die Nähe zum Ziel belohnt, vor einer Mauer hängen bleibt und wie die Belohnung für Neuartiges den Weg durch die Öffnung findet: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Die zwölf Stücke im Überblick
Die Täuschenden Landschaften sind die Wurzel: eine Fitness, die zum Ziel zeigt und in die Sackgasse führt. Daraus verzweigt die Linie nach der Schwäche, die jeweils behoben wird: Novelty Search (suchen, ohne das Ziel zu kennen), danach Verhaltensraum (was heißt „anders“?), Novelty plus Ziel (das Ziel kehrt zurück) und MAP-Elites (nicht eine Lösung, sondern die beste je Verhalten). Von MAP-Elites aus folgen CMA-ME und CMA-MAE (die Mutation lernen) und CVT-MAP-Elites (Zellen für viele Verhaltenswerte), beide zusammen mit dem Verhaltensraum führen zu AURORA (die Beschreibung lernen). Go-Explore ist das Gegenstück zur Novelty Search (derselbe Zweck, andere Bauweise: erst zurückkehren, dann erkunden).
Die Grenzen von Novelty folgen aus Novelty plus Ziel und führen mit MAP-Elites zusammen: Quality-Diversity im Routing (Doppelrahmen) ist der Zusammenfluss, MAP-Elites auf einer Tourenplanung aus der Praxis. POET (oranger Rahmen, eigene Forschung) schließt die Linie: es übernimmt das Mindestkriterium aus Novelty plus Ziel und die Zwischenstände aus Go-Explore als Idee. Die gestrichelten Fremdknoten sind Bausteine anderer Linien: der Genetische Algorithmus, NSGA-II und CMA-ES aus den Populations-Metaheuristiken und der Autoencoder aus der Dimensionsreduktion.
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
- Baustein aus einer anderen Linie
- eigene oder frische Forschung, kein etablierter Standard
Verwandt in anderen Linien
- Populations-Metaheuristiken — Die Wurzel dieser Linie ist ein einfacher Genetischer Algorithmus (Turnier, Elite, Mutation ohne Kreuzung), der Gedanke der GA-Demo der Populations-Metaheuristiken, hier im täuschenden Labyrinth statt an einer Lieferroute. Die Pareto-Auswahl von Novelty plus Ziel folgt NSGA-II, und jeder Emitter von CMA-ME ist ein CMA-ES, dort allein, hier in einem Archiv.
- Dimensionsreduktion — Die gelernte Verhaltensbeschreibung von AURORA verdichtet die Rohdaten einer Fahrt mit einer PCA oder einem Autoencoder, wie ihn die Autoencoder-Demo der Dimensionsreduktion zeigt: dort das Thema, hier eine Beschreibung für ein Archiv. Der Befund ist ernüchternd: der Autoencoder rekonstruiert nicht besser als die PCA, und ein kleiner Rekonstruktionsfehler sagt nichts über die Vielfalt der Zellen.
Täuschende Landschaften: wenn die Fitness in die Sackgasse führt
Sehen Sie, wie ein Genetischer Algorithmus einen Roboter durch ein Labyrinth zum Ziel steuern will, während die Fitness (Abstand der Endposition zum Ziel) ihn in die Sackgasse unter der Wand lockt. Ein Stufen-Regler zeigt live, wie die Täuschung mit dem Umweg wächst. Der Haken: auf der Falle-Stufe findet fast die Hälfte der Läufe den Weg auch mit 40 000 Evaluationen nicht, und die Schlangenlinie bleibt unlösbar.
Demo starten →Novelty Search: suchen, ohne das Ziel zu kennen
Sehen Sie, wie Novelty Search sucht, ohne das Ziel zu kennen: Ausgewählt wird nicht, wer nah am Ziel endet, sondern wessen Endposition anders ist als die der anderen. Ein Vergleich mit der Fitness-Suche zeigt live, wo das die Falle löst. Der Haken: wo die Fitness nicht täuscht, ist Novelty nicht schneller, ein Archiv hilft hier nicht, und die Schlangenlinie löst keine Einstellung, auch nicht mit dem Zehnfachen an Budget.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Verhaltensraum: was Novelty Search als „anders“ ansieht
Sehen Sie, wie Novelty Search entscheidet, was „anders“ heißt: Eine Beschreibung der Fahrt (Endposition, Wegpunkte, Fahrstil, Restweg zum Ziel) legt fest, welche Fahrten als verschieden gelten. Ein Umschalter über zwölf Beschreibungen zeigt live, wie viel an dieser Wahl hängt. Der Haken: selbst eine Beschreibung, die die Antwort schon enthält, löst die Schlangenlinie nicht, der Engpass ist der Suchraum und nicht der Verhaltensraum.
Demo starten →Novelty plus Ziel: wie viel Ziel verträgt die Suche?
Sehen Sie, wie sich der Novelty-Auswahl das Ziel zurückgeben lässt: als gewichtete Summe, als Pareto-Auswahl, als lokaler Wettbewerb oder als Minimalkriterium. Ein Gewichts-Regler zeigt live, wie viel Ziel die Suche verträgt, bevor die Falle zurückkehrt. Der Haken: ab einem Fitness-Gewicht von 0,75 schadet das Ziel, und die Schlangenlinie löst keines der Verfahren.
Demo starten →MAP-Elites: nicht die eine beste Lösung, sondern die beste je Verhalten
Verfolgen Sie, wie MAP-Elites nicht die eine beste Lösung sucht, sondern je Zelle des Verhaltensraums (der Endposition) die beste, also direkteste Fahrt sammelt. Ein Vergleich mit Novelty- und Fitness-Suche zeigt live, was dieses Archiv bringt und was es beim Weg zum Ziel kostet. Der Haken: die Qualität-Vielfalt-Kennzahl liegt um 19,7 % höher als bei Novelty, doch beim Ziel ist MAP-Elites nicht schneller.
Demo starten →CMA-ME und CMA-MAE: wann lohnt es sich, die Suchverteilung zu lernen?
Sehen Sie, wie CMA-ME jeder Teilsuche einen Lernalgorithmus (CMA-ES) gibt, der Richtung und Stärke der Verbesserungen lernt, statt wie MAP-Elites fest zu mutieren. Ein Vergleich über verschieden große Suchräume zeigt live, wann das etwas bringt. Der Haken: der Vorteil schmilzt mit der Dimension. Bei 20 Dimensionen gewinnt CMA-MAE 42,5 % QD-Score gegenüber MAP-Elites, bei den 280 Dimensionen der früheren Stücke verliert jedes CMA-Verfahren leicht.
Demo starten →CVT-MAP-Elites: Zellen für hochdimensionales Verhalten
Sehen Sie, wie CVT-MAP-Elites das Archiv bei vielen Verhaltenswerten kompakt hält: Statt eines Rasters, das exponentiell wächst, legt ein k-Means eine feste Zahl von Zellen fest. Ein Vergleich von Gitter und zwei Schwerpunkt-Varianten zeigt live, wo die Zellen liegen sollten. Der Haken: ein Gitter bleibt bei 16 Verhaltenswerten fast leer (6,17 % belegt), und in der Falle gibt es keine Rangfolge der Varianten.
Demo starten →AURORA: wie viel ist Vorwissen über die Verhaltensbeschreibung wert?
Verfolgen Sie, wie AURORA die Verhaltensbeschreibung selbst lernt: Ein Autoencoder oder eine PCA verdichtet die Rohdaten jeder Fahrt zu wenigen Werten, nach denen das Archiv seine Zellen bildet, statt dass jemand von Hand festlegt, was „anders“ heißt. Die Demo vergleicht gelernte mit handgemachten Beschreibungen. Der Haken: die handgemachte Endposition bleibt klar besser (137,15 gegen höchstens 77,15 verschiedene Endzellen), und das Neulernen lohnt sich nur selten.
Demo starten →Go-Explore: erst zurückkehren, dann erkunden
Verfolgen Sie, wie Go-Explore Zwischenstände merkt, zu einem von ihnen zurückkehrt und von dort mit ein paar zufälligen Schritten weiter erkundet, sodass eine Fahrt Stück für Stück wächst. Ein Umschalter für die Rückkehr zeigt live, was der Erfolg an der Schlangenlinie voraussetzt, an der Fitness und Novelty scheitern. Der Haken: ohne Zurücksetzen kostet die Rückkehr mehr als das Siebenfache, und die gefundene Fahrt entgleist, sobald die Welt Rauschen hat.
Demo starten →Wo Novelty nicht hilft: und was dann
Sehen Sie, wann Novelty Search nicht hilft: Ein Regler mischt Novelty und Fitness, weitere verändern, wie täuschend das Labyrinth ist und wie genau das Ziel getroffen werden muss. Der Vergleich zeigt live, wo Novelty gewinnt und wo es verliert. Der Haken: ohne Täuschung ist Novelty bei kleinem Ziel viel langsamer (Zielradius 0,25: Median 6 147,5 gegen 567,5 Evaluationen), und die Schlangenlinie löst keine Auswahl.
Demo starten →Quality-Diversity im Routing: was kosten verschiedene Routenpläne?
Verfolgen Sie, wie MAP-Elites auf eine Tourenplanung mit Kapazität angewandt wird: Statt einer besten Lösung sammelt die Suche je Zelle (Zahl der Routen, Anteil der längsten Route) die billigste, eine Preisliste für Fahrzeuge. Ein Vergleich mit gezielten Einzelsuchen zeigt live, was ein Fahrzeug mehr kostet. Der Haken: auf die beste Strecke hilft das nicht, und die einfachen Züge liegen bei 200 000 Evaluationen 3,73 % über OR-Tools.
Demo starten →POET: Umgebungen und Agenten gemeinsam entwickeln, tragen Stepping Stones?
Sehen Sie, wie POET Aufgaben und Löser zugleich entwickelt: Aus einer gelösten Aufgabe entsteht durch kleine Änderungen eine neue, und Agenten wandern zwischen den Aufgaben, in der Hoffnung auf Zwischenstufen (Stepping Stones). Vergleiche ohne Transfer, ohne Neuheit und mit direkter Suche zeigen live, ob das trägt. Der Haken: in dieser einfachen Fassung löst POET keine der schweren Testumgebungen, auch nicht mit 2 000 000 Evaluationen.
Demo starten →Welches Verfahren passt zu meinem Suchproblem?
Ein Entscheidungsbaum über alle zwölf Stücke: er fragt nach dem Suchproblem und danach, was die Suche liefern soll, nicht nach dem Verfahren.
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Alle zwölf Antworten sind durch die Messreihen der Demos belegt (siehe jede README): wo Novelty die Falle löst, wo sie nichts bringt, was ein Archiv gewinnt und was es kostet, und wo auch die Stepping Stones von POET nicht tragen.
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.
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.
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.