Novelty Search verständlich erklärt

Eine Suche, die nur belohnt, was dem Ziel am nächsten kommt, kann vor einer Mauer hängen bleiben, wenn der Weg erst vom Ziel wegführt. Belohnt man stattdessen, was sich von allem Bisherigen unterscheidet, findet die Suche in einem Beispiel mit einem simulierten Roboter doch durch die Öffnung. Die Seite erklärt das zuerst ohne Formeln und danach für Fachleute.

Zuletzt aktualisiert: 28. Oktober 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Ein Roboter, eine Mauer, ein Ziel

Stellen Sie sich einen Hof vor, in dem ein Roboter vom Start zu einem Ziel fahren soll. Er hat keine Sensoren, sondern fährt nach einem festen Fahrplan aus Lenk- und Gasbefehlen. Zwischen Start und Ziel steht eine lange Mauer, die nur an ihrem rechten Ende eine Öffnung hat. Das Ziel liegt in gerader Linie hinter der Mauer, der Weg führt aber erst seitlich zur Öffnung und damit zunächst vom Ziel weg.

Gute Fahrpläne sucht ein Verfahren, das viele Fahrpläne zugleich ausprobiert, die erfolgreicheren behält und leicht verändert, ähnlich wie bei einer Züchtung. Es heißt Genetischer Algorithmus. Entscheidend ist, was „erfolgreicher“ heißen soll. Dazu gibt es eine Demo zum Ausprobieren, die diesen Roboter am Rechner nachspielt. Sie kennt mehrere Höfe; hier geht es um den mit der Öffnung am rechten Ende der Mauer.

Warum die Nähe zum Ziel in die Irre führt

Die naheliegende Antwort lautet: Erfolgreicher ist der Fahrplan, der am Ende dem Ziel am nächsten steht. Das ist die übliche Auswahl nach Zielnähe, die Demo lässt sie zum Vergleich mitlaufen. Die Fahrpläne sammeln sich dann an der Mauer, denn dort steht man dem Ziel am nächsten.

Ein Fahrplan, der zur Öffnung und damit erst einmal vom Ziel weg führt, wirkt schlechter und wird aussortiert. So wird die Öffnung kaum erprobt. Die Demo wiederholt die ganze Suche mehrmals mit anderem Zufall. In diesem Hof erreicht die Auswahl nach Zielnähe das Ziel nur in etwas mehr als der Hälfte der Wiederholungen.

Was hilft: belohnen, was neu ist

Novelty Search (englisch für Suche nach Neuartigem) wählt anders aus: Es gewinnt der Fahrplan, dessen Fahrt woanders endet als die der anderen. Wer dort endet, wo schon viele stehen, ist wenig neu; wer allein in einer leeren Ecke endet, sehr neu. Wie nah ein Fahrplan dem Ziel kommt, spielt für die Auswahl keine Rolle. Es wird nur nachgemessen, ob eine Fahrt angekommen ist.

Die Fahrpläne verteilen sich dadurch nach und nach über den Hof, denn jeder Platz, den noch niemand erreicht hat, verspricht Belohnung. Irgendwann fährt einer durch die Öffnung, und dahinter führt der Weg ohne weitere Wand zum Ziel. In diesem Hof erreicht die Demo mit dieser Auswahl das Ziel in jeder Wiederholung und besucht dabei alle freien Plätze. Die Auswahl nach Zielnähe lässt Teile des Hofs unberührt.

Das hilft nur, wo die Nähe zum Ziel täuscht: Auf einem Hof ohne Mauer braucht die Auswahl nach Zielnähe in der Demo nicht länger.

Wie ernst ist das Beispiel zu nehmen?

Das ist ein vereinfachtes Spielbeispiel, kein Betriebsergebnis.

Was Sie daraus mitnehmen

Ein Bild aus dem Betrieb, nicht aus der Demo: Eine Tourenplanung liefert Woche für Woche fast dieselben Touren, obwohl sich die Aufträge ändern. Dann lohnt die Frage an Planer oder Anbieter, ob das Verfahren nur Pläne belohnt, die dem Ziel nah kommen, oder auch Pläne, die sich von den bisherigen unterscheiden. Das gilt, solange der Weg zum Ziel zunächst vom Ziel wegführt. Wo die Nähe zum Ziel die Richtung richtig weist, bringt die Belohnung für Neuartiges in der Demo keinen Vorteil.

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.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er fasst die Methodik der README und den Expander „📐 Mathematische Formulierung“ der Demo zusammen. Die Auswahl nach Novelty ersetzt in einem sonst unveränderten Genetischen Algorithmus die Auswahl nach Zielnähe.

• Labyrinth und Roboter: 24 × 24 Zellen, Start bei x = 3,5 und y = 3,5, Ziel bei x = 3,5 und y = 20,5. Stufe 0 ist ein freies Feld, Stufen 1 bis 3 haben eine Querwand mit Öffnung links, in der Mitte oder rechts, Stufe 4 drei Wände (Öffnungen rechts, links, rechts). Die Steuerfolge hat 140 Befehle, es gibt keinen Sensor. Das Verhalten ist die Endposition. Erfolg heißt: eine Endposition weniger als 2 Zellen vom Ziel.
• Suche: 100 Individuen, Turnier der Größe 3, die zwei Besten bleiben, Mutation Gauß σ = 0,25 auf 15 % der Gene, keine Kreuzung. Nur der Wert, nach dem ausgewählt wird, wechselt.
• Novelty: mittlerer Abstand der Endposition zu den k = 15 nächsten Endpositionen der Vergleichsmenge aus Population (und Archiv). Der Punkt selbst zählt nicht, ein anderes Individuum am selben Ort zählt mit Abstand 0.
• Drei Archiv-Regeln: nur Population (kein Archiv); Archiv der Neuartigsten (je Generation kommen die neuartigsten 5 % der Population, also 5 Punkte, ins Archiv); Archiv mit Schwelle (alle mit Novelty über der Schwelle, höchstens 5 je Generation und dann die neuartigsten; bei Andrang wird die Schwelle mit 1,1 multipliziert, nach 3 Generationen ohne Neuzugang mit 0,9, Start 1).
• Messgrößen: Evaluationen bis zum ersten Erfolg; besuchte Zellen (Zellen, in denen mindestens eine Endposition lag); wahrer Restweg (kürzester Weg in Zellen von der besten besuchten Zelle zum Ziel, Breitensuche).

Die Formeln

Das Verhalten \(b(g)\in\mathbb{R}^2\) ist die Endposition der Fahrt mit der Steuerfolge \(g\). Die gewöhnliche Auswahl maximiert die Fitness, den negativen Abstand zum Ziel \(z\):

\[f(g)=-\lVert b(g)-z\rVert_2\]

Die Novelty eines Individuums \(i\) der Population \(P\) mit Archiv \(A\) und Vergleichsmenge \(R = P \cup A\) ist der mittlere Abstand zu den \(k\) nächsten anderen Elementen \(N_k(i)\) von \(R\setminus\{i\}\) (bei weniger als \(k\) anderen gehen alle ein):

\[\rho_k(i) = \frac{1}{k}\sum_{j \in N_k(i)} \lVert b(g_i) - b(g_j) \rVert_2\]

Ausgewählt wird nach \(\rho_k\) statt nach \(f(g)\); das Ziel kommt in der Auswahl nicht vor und dient nur der Messung des Erfolgs:

\[\lVert b(g)-z\rVert_2 < 2\]

Befunde

Alle Zahlen stammen aus der README der Demo und werden in deren Tests (tests/test_claims.py) nachgerechnet. Sie gelten für 20 Läufe je Zelle (Zufalls-Seeds 0 bis 19) und 40 000 Evaluationen (100 je Generation), sofern nicht anders genannt. Die Studie ist vorgerechnet; der Live-Lauf der Demo ist ein einzelner Lauf.

Frage	Befund
Löst Novelty die Falle (Stufe 3)?	Ja, in jedem Lauf. Novelty ohne Archiv: 20 von 20, Median 988,5 Evaluationen (schnellster Lauf 77, langsamster 3 373). Die Fitness: 11 von 20. Vorbehalt: Der Fitness-Median (1 267) gilt nur für ihre 11 erfolgreichen Läufe, der von Novelty für alle 20.
Gilt das auf allen Stufen?	Erfolge 20 / 20 / 20 / 20 / 0 von 20 für Novelty auf Stufe 0 bis 4 (Fitness: 20 / 20 / 20 / 11 / 0). Stufe 4 löst keine Variante.
Ist Novelty schneller, wo die Fitness nicht täuscht?	Nein. Median 63,5 / 146 / 207,5 (Stufe 0 bis 2) gegen 63,5 / 126 / 190,5 für die Fitness; schlimmster Lauf auf Stufe 1 / 2: 307 / 447 gegen 252 / 875. Das „Nein“ gilt für die Mediane; im schlimmsten Lauf auf Stufe 2 ist Novelty besser (447 gegen 875).
Warum löst Novelty die Falle?	Sie besucht alle freien Zellen: auf Stufe 0 bis 3 in allen 60 Novelty-Läufen (drei Varianten à 20 Läufe) alle 484 / 465 / 465 / 465 Zellen; die Fitness im Mittel 327,15 / 376,95 / 422,45 / 343,9 (schlechtester Lauf auf Stufe 3: nur 191). Nach 50 Generationen auf Stufe 3 sind im Mittel 445,5 von 465 Zellen besucht (Fitness 272,6), nach 100 Generationen 463,15 (306,95).
Wie nah kommt die Fitness dem Ziel auf Stufe 3?	Der kleinste wahre Restweg liegt im Mittel bei 5,55 Zellen (schlechtester Lauf 17), bei Novelty bei 0.
Hilft ein Archiv?	Nicht in diesem Labyrinth. Beide Archiv-Varianten lösen Stufe 0 bis 3 in 20 von 20 Läufen, Median 63,5 / 146 / 207,5 / 1 195 (beide gleich) gegen 988,5 ohne Archiv; schlimmster Lauf auf Stufe 3: 4 006 (Neuartigste), 3 764 (Schwelle), 3 373 (ohne).
Hängt es an k oder an der Population?	Kaum. Alle 9 Einstellungen (k = 5 / 15 / 30 × 50 / 100 / 200 Individuen, gleiches Gesamtbudget, Variante ohne Archiv) lösen Stufe 3 in 20 von 20 Läufen. Median 718,5 / 1 186,5 / 1 175 (k = 5), 659 / 988,5 / 1 308,5 (k = 15), 710 / 763,5 / 1 271,5 (k = 30): Die Einstellung verschiebt den Aufwand, nicht den Erfolg.
Und auf Stufe 4 mit diesen Einstellungen?	0 von 180 Läufen in allen 9 Einstellungen. Der kleinste wahre Restweg liegt je Einstellung im Mittel zwischen 25,9 und 27,6 Zellen (Start: 77).
Wie weit kommt Stufe 4 mit 40 000 Evaluationen?	0 / 0 / 0 / 0 von 20 (Fitness, Novelty, beide Archive). Besuchte Zellen im Mittel 223,8 / 264,15 / 257,45 / 255,35 von 427; kleinster Restweg 34,75 / 26,25 / 29,95 / 30,3 Zellen (bester Lauf 22 / 22 / 26 / 26). Novelty kommt dem Ziel näher, erreicht es aber nie.
Hilft das Zehnfache an Budget?	Nein. Mit 400 000 Evaluationen 0 von 60 Läufen (Fitness, Novelty ohne Archiv, Archiv der Neuartigsten). Der mittlere Restweg fällt von 34,75 auf 32,3 (Fitness), von 26,25 auf 22,4 (Novelty ohne Archiv) und von 29,95 auf 23,75 (Archiv der Neuartigsten); der beste Lauf am Ende hat noch 20 / 16 / 21 Zellen. Novelty ohne Archiv: 26,25 (40 000), 24,75 (100 000), 23,85 (200 000), 22,4 (400 000); Fitness 34,75, 33,65, 32,95, 32,3: Die Kurven flachen ab.

Das Archiv war nicht nötig. Erwartet war, dass es Novelty Search erst robust macht (Lehman und Stanley beschreiben es als festen Bestandteil). In diesem Labyrinth liefert die Variante ohne Archiv denselben Erfolg mit einer Vergleichsmenge von nur 100 statt (nach 400 Generationen) 2 100 Punkten: Die Population allein bedeckt den kleinen Raum schnell genug. Das ist ein Befund über diese Aufgabe, nicht über Archive.

Grenzen

• Verhaltensmaß von Hand gewählt: Die Endposition (zwei Zahlen) bestimmt, was als neu gilt. Das Ergebnis hängt an dieser Wahl; ein anderes Maß wird hier nicht untersucht.
• Ein Labyrinthtyp, feste Genomlänge: Mit längerer Steuerfolge löst schon die Fitness Stufe 3 (so die README mit Verweis auf die Demo deception-maze-demo); die Vorteile von Novelty gelten für diese Parametrisierung.
• 20 Läufe je Zelle: Erfolgsquoten wie 11 von 20 haben eine Standardabweichung von etwa 11 Prozentpunkten. Kleine Unterschiede zwischen Archiv-Varianten und Einstellungen (etwa Median 988,5 gegen 1 195) liegen im Rauschen und werden nicht gedeutet.
• Kein Archiv-Test in anderen Aufgaben: Dass das Archiv hier nichts bringt, sagt nichts über größere oder offenere Verhaltensräume. Das Archiv mit Schwelle ist beim Zehnfachen des Budgets nicht mitgerechnet (das Archiv wächst dort auf Tausende Punkte; Rechenzeit).
• Einfacher Genetischer Algorithmus ohne Kreuzung: Kreuzung und andere Operatoren würden die Zahlen ändern (nicht gemessen).
• Stufe 4 bleibt ungelöst: Breit zu suchen genügt dort nicht. Das ist laut README der Anknüpfungspunkt für weitere Demos zum Thema, nicht Gegenstand dieser.

Quellen

• Lehman, J., Stanley, K. O. (2011): Abandoning objectives: evolution through the search for novelty alone. Evolutionary Computation 19(2), 189–223 (Novelty als mittlerer Abstand zu den k nächsten Nachbarn, Archiv mit Schwelle).
• Lehman, J., Stanley, K. O. (2008): Exploiting open-endedness to solve problems through the search for novelty. Proceedings of the Eleventh International Conference on Artificial Life (ALIFE XI), MIT Press.
• Quelltext, vorgerechnete Studie und Tests der Demo: github.com/sebastian-hanisch/novelty-search-demo.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen; die Literaturhinweise stammen aus der README der Demo.