Suche mit Tiefensuche

Hole das Buch

Das Beispiel ist ein Büroflur in der Uni. Neben den Büros gibt es eine Bibliothek und einen Kopiererraum, wo auch der Roboter sich gerade aufhält. Die Aufgabe für den Roboter lautet: Hole das Buch aus der Bibliothek (und bringe es zum Kopier). (Damit das Beispiel und der sich daraus ergebende Problemgraph nicht zu groß und zu unübersichtlich werden, soll das Ziel hier darin liegen, dass der Roboter das Buch in der Bibliothek aufnimmt.)

Es stehen zwei Aktionen zur Verfügung:

1. Der Roboter kann von einem in den nächsten Raum wechseln (Kosten siehe Pfeile)
2. Der Roboter kann das Buch aufnehmen (Kosten: 3)

Dabei sind die Durchgänge teilweise nur in einer Richtung zu benutzen (Pfeilrichtung).

Problemgraph zum Kopiererbeispiel

=> Problemlösen == Suche im Graphen

Uninformierte ("blinde") Suche:

Keine Informationen über die Kosten eines Pfades: Nur die Pfadlänge (Anzahl der Schritte) zählt.

Varianten:

• Tiefensuche
• Breitensuche

Anmerkungen Wegesuche (Landkarte)

Bei der Wegesuche hat man den Problemgraphen bereits durch die Orte und die Verbindungen (Straßen) zwischen ihnen gegeben. Es gibt nur eine ausführbare Aktion: "fahre nach".

Dabei können nur die Anzahl der Zwischenstationen auf dem Weg gezählt werden ("uninformierte Suche"), oder man ordnet den Kanten Kosten zu (bei der Wegesuche wären dies die Entfernungen zwischen den Orten oder die Zeit, die man von A nach B braucht) und landet damit bei der "informierten Suche".

Normalerweise hat man eine Ordnung auf den Aktionen, d.h. für einen Knoten ergibt sich daraus eine Reihenfolge, in der die Aktionen angewendet werden und die Nachfolger expandiert werden. Bei der Wegesuche hat man dies nicht, insofern muss man willkürlich eine Ordnung festlegen. In dieser Veranstaltung ist dies die alphabetische Reihenfolge der Knoten (Orte).

Tiefensuche (TS, DFS)

Erinnerung Tree-Search

1. Füge Startknoten in leere Datenstruktur (Stack, Queue, ...) ein
2. Entnehme Knoten aus der Datenstruktur:
   • Knoten ist gesuchtes Element: Abbruch, melde "gefunden"
   • Expandiere alle Nachfolger des Knotens und füge diese in die Datenstruktur ein
3. Falls die Datenstruktur leer ist: Abbruch, melde "nicht gefunden"
4. Gehe zu Schritt 2

=> Was passiert, wenn wir einen Stack einsetzen?

Bemerkungen

• Nachfolger eines Knotens: Alle von diesem Zustand durch Aktionen erreichbare Zustände

• Suchalgorithmus mit Stack als Datenstruktur => Tiefensuche

  • Zu betrachtender Knoten in Schritt 2 wird oben vom Stack genommen
  • Expandierte Knoten werden in Schritt 2.a oben auf den Stack gelegt Dabei i.A. die vorgegebene Reihenfolge der Nachfolgeknoten beachten!

  Auswirkung: Weg wird in die Tiefe verfolgt (deshalb "Tiefensuche")

• Im [Russell2020] wird die Datenstruktur zum Halten der zu expandierenden Knoten (also hier im Fall der Tiefensuche der Stack) auch "Frontier" genannt.

• Backtracking: Wenn der Weg in eine Sackgasse führt, d.h. ein Knoten keine Nachfolger hat, werden bei der Expansion des Knotens keine Nachfolger auf den Stack gelegt. Die Evaluation des nächsten Knotens auf dem Stack bewirkt deshalb ein Zurückspringen im Suchbaum zum letzten Knoten auf dem aktuellen Weg mit noch offenen Alternativen ...

Konventionen für diese Lehrveranstaltung

In der Beschreibung der Algorithmen werden häufig nur die letzten Knoten der partiellen Wege in den Datenstrukturen mitgeführt (das gilt auch für die Beschreibung im [Russell2020]). Dies erschwert die Nachvollziehbarkeit, wenn man die Queue oder den Stack schrittweise aufschreibt. Deshalb wird für diese Veranstaltung die Konvention eingeführt, immer die partiellen Wege aufzuschreiben.

Nicht Bestandteil der Algorithmen, dient aber der Nachvollziehbarkeit: Expandierte Knoten sollen alphabetisch sortiert an der korrekten Stelle in der Datenstruktur auftauchen, dabei soll aber natürlich die Reihenfolge der ursprünglich in der Datenstruktur enthaltenen Knoten nicht modifiziert werden. (Bei "echten" Problemen wird die Reihenfolge der expandierten Nachfolger in der Regel durch eine Reihenfolge der anwendbaren Operationen bestimmt.)

Weitere Hinweise

• Die Tiefensuche wurde zufällig am Beispiel Tree-Search eingeführt. Man kann auch Graph-Search einsetzen. Wichtig ist nur, dass als Datenstruktur ein Stack genutzt wird.

• Bei Tree-Search werden bereits besuchte Knoten u.U. immer wieder besucht. Zyklen im aktuell entwickelten Pfad sind also möglich! Außerdem sind mehrere Wege zum selben (Zwischen-/End-) Knoten in der Datenstruktur möglich!

• Im [Russell2020] wird der Begriff "Backtracking" für den rekursiven Tiefensuche-Algorithmus verwendet. Dies steht im Gegensatz zum üblichen Sprachgebrauch in der KI!

Tiefensuche (rekursive Variante)

1. Startknoten ist gesuchtes Element: Abbruch, melde "gefunden"
2. Für jeden Nachfolger des Startknotens:
   • Rufe Tiefensuche für aktuellen (Nachfolger-) Knoten auf
   • Ergebnis "gefunden": Abbruch, melde "gefunden"
3. Abbruch, melde "nicht gefunden"

Bemerkungen

• Eigenschaften wie "normale" Tiefensuche
• Einfacher zu implementieren: Nutzung des Stacks wird auf den Compiler verlagert (Funktionsaufruf, Stack des Prozesses ...)
• Speicherbedarf: Für jeden Knoten wird nur der nächste Knoten expandiert, plus Speicher für die Funktion

Eigenschaften der Tiefensuche

Siehe Breitensuche

Wrap-Up

• Uninformierte Suchverfahren
  • Keine weiteren Pfadkosten (nur Anzahl der Schritte)
  • Tiefensuche: Verfolge einen Pfad zuerst in die Tiefe
  • Backtracking bei Sackgassen (automatisch durch den Stack)

Suche mit Breitensuche

Hole das Buch

=> Problemlösen == Suche im Graphen

Uninformierte ("blinde") Suche:

Keine Informationen über die Kosten eines Pfades: Nur die Pfadlänge (Anzahl der Schritte) zählt.

Varianten:

• Tiefensuche
• Breitensuche

Breitensuche (BS, BFS)

Erinnerung Graph-Search

1. Füge Startknoten in leere Datenstruktur (Stack, Queue, ...) ein
2. Entnehme Knoten aus der Datenstruktur:
   • Knoten ist gesuchtes Element: Abbruch, melde "gefunden"
   • Markiere aktuellen Knoten, und
   • Expandiere alle Nachfolger des Knotens und füge alle unmarkierten Nachfolger, die noch nicht in der Datenstruktur sind, in die Datenstruktur ein
3. Falls die Datenstruktur leer ist: Abbruch, melde "nicht gefunden"
4. Gehe zu Schritt 2

=> Was passiert, wenn wir eine Queue einsetzen?

Bemerkungen

• Nachfolger eines Knotens: Alle von diesem Zustand durch Aktionen erreichbare Zustände

• Suchalgorithmus mit Queue als Datenstruktur => Breitensuche

  • Zu betrachtender Knoten in Schritt 2 wird vorn aus der Queue genommen
  • Expandierte Knoten werden in Schritt 2.a hinten in die Queue eingefügt Dabei i.A. die vorgegebene Reihenfolge der Nachfolgeknoten beachten!

  Auswirkung: Suchbaum wird ebenenweise aufgebaut (deshalb "Breitensuche")

• Graph-Search: Markierte Knoten müssen geeignet gespeichert werden: separate Datenstruktur => Aufwand!

Konventionen für diese Lehrveranstaltung

In der Beschreibung der Algorithmen werden häufig nur die letzten Knoten der partiellen Wege in den Datenstrukturen mitgeführt (das gilt auch für die Beschreibung im [Russell2020]). Dies erschwert die Nachvollziehbarkeit, wenn man die Queue oder den Stack schrittweise aufschreibt. Deshalb wird für diese Veranstaltung die Konvention eingeführt, immer die partiellen Wege aufzuschreiben.

Nicht Bestandteil der Algorithmen, dient aber der Nachvollziehbarkeit: Expandierte Knoten sollen alphabetisch sortiert an der korrekten Stelle in der Datenstruktur auftauchen, dabei soll aber natürlich die Reihenfolge der ursprünglich in der Datenstruktur enthaltenen Knoten nicht modifiziert werden. (Bei "echten" Problemen wird die Reihenfolge der expandierten Nachfolger in der Regel durch eine Reihenfolge der anwendbaren Operationen bestimmt.)

Weitere Hinweise

• Die Breitensuche wurde zufällig am Beispiel Graph-Search eingeführt. Man kann auch die Tree-Search-Variante einsetzen. Wichtig ist nur, dass als Datenstruktur eine Queue genutzt wird.

• Im [Russell2020] wird die Breitensuche ebenfalls auf der Basis des Graph-Search-Algorithmus eingeführt. Allerdings wird die Abbruchbedingung modifiziert: Die Zielbedingung wird nicht erst (wie bei Graph-Search eigentlich definiert) geprüft, wenn ein Knoten aus der Queue entnommen wird, sondern bereits bei der Erzeugung der Nachfolgerknoten (vor dem Einfügen in die Queue). Dadurch spart man sich die Expansion einer zusätzlichen Ebene: Die Komplexität wäre in diesem Fall "nur" $O(b^{d})$.

Eigenschaften Breitensuche vs. Tiefensuche

• Zeitkomplexität: maximal zu expandierende Knotenzahl
• Speicher:
  • TS: in jeder Tiefe weitere $b$ Knoten speichern
  • BS: alle Knoten einer Ebene im Speicher halten³

b: Verzweigungsfaktor, d: Ebene d. höchsten Lösungsknotens, m: Länge d. längsten Pfades

Praxisvergleich Breitensuche vs. Tiefensuche

Breitensuche: Annahme: $b=10$, 10.000 Knoten/s, 1.000 Byte/Knoten

Tiefensuche: Annahme: längster Pfad (Tiefe) $m=1000$

=> Speicherbedarf ca. 10 MB

Wrap-Up

• Uninformierte Suchverfahren
  • Keine weiteren Pfadkosten (nur Anzahl der Schritte)
  • Breitensuche: Verfolge alle Pfade (baue den Suchbaum ebenenweise auf)

Suche mit Branch-and-Bound

Hole das Buch

=> Problemlösen == Suche im Graphen

Informierte Suche: Nutzung der Kostenfunktion:

Gesamtkosten: $f(n) = g(n) + h(n)$

• $n \in S$ auf aktuellem Weg erreichter Knoten
• $g(n)$ tatsächliche Kosten für Weg vom Start bis Knoten $n$
• $h(n)$ geschätzte Restkosten für Weg von Knoten $n$ zum Ziel => $h(n)$ wird auch "heuristische Funktion" oder "Heuristik" genannt

Varianten:

• Branch-and-Bound
• Best First
• A*

Branch-and-Bound (BnB)

Variante der Breitensuche mit Kosten

• Idee: Expandiere den bisher günstigsten partiellen Weg

• Kostenfunktion: $f(n) = g(n)$

• Datenstruktur: sortierte Queue (Prioritätsqueue)

• Voraussetzung: alle Aktionen haben positive Kosten (jeden Knoten $n$ gilt: $g(n) > 0$)

Hinweis: Die Branch-and-Bound-Suche taucht im [Russell2020] als Erweiterung der "Uniformen Suche" auf ...

BnB: Finde einen Weg von A nach H

Bemerkungen zu BnB mit Graph-Search

Graph-Search fordert: Expandierte Nachfolgerknoten, die schon in der Queue sind, sollen nicht (erneut) in die Queue aufgenommen werden.

• Problem dabei: Was ist mit den Kosten?! Der neu expandierte Weg könnte günstiger sein als der schon in der Queue enthaltene.

• Lösung (vgl. Optimierungsmöglichkeiten für A*):

  Füge zunächst alle neu expandierten partiellen Pfade (mit unmarkierten Endknoten) in die Queue ein, sortiere diese und behalte von mehreren Pfaden zum gleichen Knoten nur den jeweils günstigsten in der Queue

Pfade, deren Endknoten bereits früher im Pfad vorkommt (Schleifen), werden bei Graph-Search in Schritt 2 nicht in die Queue aufgenommen (der Endknoten wäre bei einer Schleife ja bereits markiert und der neue Pfad würde bei Graph-Search nicht weiter beachtet).

Das Einfärben ist kein Problem, da nur der jeweils günstigste Knoten aus der Queue genommen, gefärbt und expandiert wird. D.h. alle anderen Wege sind zu diesem Zeitpunkt bereits teurer. Wenn man nun (später) über einen anderen Weg zu einem bereits gefärbten Knoten kommt, kann der neue Weg nicht günstiger sein (positive Kosten vorausgesetzt).

Konventionen für diese Lehrveranstaltung

In der Beschreibung der Algorithmen werden häufig nur die letzten Knoten der partiellen Wege in den Datenstrukturen mitgeführt (das gilt auch für die Beschreibung im [Russell2020]). Dies erschwert die Nachvollziehbarkeit, wenn man die Queue oder den Stack schrittweise aufschreibt. Deshalb wird für diese Veranstaltung die Konvention eingeführt, immer die partiellen Wege aufzuschreiben.

Auf dem Papier sortiert sich die Queue schlecht, deshalb können Sie darauf verzichten, wenn Sie den im nächsten Schritt zu expandierenden Weg unterstreichen. Wer nicht mit Unterstreichen arbeiten will, muss eben dann manuell sortieren ...

Wenn bei der Graph-Search-Variante ein Weg nicht in die Queue aufgenommen wird, weil bereits ein anderer (günstigerer) Weg zum selben (Zwischen-/End-) Knoten bereits in der Queue enthalten ist, schreiben Sie dies geeignet auf. Dies gilt auch für den analogen Fall, wenn ein Weg aus der Queue entfernt wird, weil ein günstigerer Weg zum selben (Zwischen-/End-) Knoten eingefügt werden soll.

Eigenschaften von BnB

Siehe A*

Wrap-Up

• Informierte Suchverfahren
  • Nutzen reale Pfadkosten und/oder Schätzungen der Restkosten
  • Branch-and-Bound: nur reale Pfadkosten $g(n)$

Suche mit Best First

Hole das Buch

=> Problemlösen == Suche im Graphen

Informierte Suche: Nutzung der Kostenfunktion:

Gesamtkosten: $f(n) = g(n) + h(n)$

• $n \in S$ auf aktuellem Weg erreichter Knoten
• $g(n)$ tatsächliche Kosten für Weg vom Start bis Knoten $n$
• $h(n)$ geschätzte Restkosten für Weg von Knoten $n$ zum Ziel => $h(n)$ wird auch "heuristische Funktion" oder "Heuristik" genannt

Varianten:

• Branch-and-Bound
• Best First
• A*

Best-First (BF, BFS)

• Idee: Expandiere den partiellen Weg, der verspricht, dem Ziel am nächsten zu sein (Heuristik)

• Kostenfunktion: $f(n) = h(n)$

• Datenstruktur: sortierte Queue (Prioritätsqueue)

• Voraussetzungen: $h(n)$ positiv, $h(n) = 0$ für den Zielknoten

Konventionen BF

In der Beschreibung der Algorithmen werden häufig nur die letzten Knoten der partiellen Wege in den Datenstrukturen mitgeführt (das gilt auch für die Beschreibung im [Russell2020]). Dies erschwert die Nachvollziehbarkeit, wenn man die Queue oder den Stack schrittweise aufschreibt. Deshalb wird für diese Veranstaltung die Konvention eingeführt, immer die partiellen Wege aufzuschreiben.

Auf dem Papier sortiert sich die Queue schlecht, deshalb können Sie darauf verzichten, wenn Sie den im nächsten Schritt zu expandierenden Weg unterstreichen. Wer nicht mit Unterstreichen arbeiten will, muss eben dann manuell sortieren ...

Wenn bei der Graph-Search-Variante ein Weg nicht in die Queue aufgenommen wird, weil bereits ein anderer (günstigerer) Weg zum selben (Zwischen-/End-) Knoten bereits in der Queue enthalten ist, schreiben Sie dies geeignet auf. Dies gilt auch für den analogen Fall, wenn ein Weg aus der Queue entfernt wird, weil ein günstigerer Weg zum selben (Zwischen-/End-) Knoten eingefügt werden soll.

Eigenschaften von BF

Siehe A*

Wrap-Up

• Informierte Suchverfahren
  • Nutzen reale Pfadkosten und/oder Schätzungen der Restkosten
  • Best-First: nur Schätzungen $h(n)$

Suche mit A*

Hole das Buch

=> Problemlösen == Suche im Graphen

Informierte Suche: Nutzung der Kostenfunktion:

Gesamtkosten: $f(n) = g(n) + h(n)$

• $n \in S$ auf aktuellem Weg erreichter Knoten
• $g(n)$ tatsächliche Kosten für Weg vom Start bis Knoten $n$
• $h(n)$ geschätzte Restkosten für Weg von Knoten $n$ zum Ziel => $h(n)$ wird auch "heuristische Funktion" oder "Heuristik" genannt

Varianten:

• Branch-and-Bound
• Best First
• A*

A*-Suche

• Kombination aus Branch-and-Bound und Best-First-Suche

• Kostenfunktion: $f(n) = g(n) + h(n)$

• Datenstruktur: sortierte Queue (Prioritätsqueue)

• Voraussetzung:

  1. Alle Aktionen haben positive Kosten ($g(n) \ge \epsilon$)
  2. Heuristik $h(n)$ muss zulässig/konsistent sein

Konventionen für diese Lehrveranstaltung

In der Beschreibung der Algorithmen werden häufig nur die letzten Knoten der partiellen Wege in den Datenstrukturen mitgeführt (das gilt auch für die Beschreibung im [Russell2020]). Dies erschwert die Nachvollziehbarkeit, wenn man die Queue oder den Stack schrittweise aufschreibt. Deshalb wird für diese Veranstaltung die Konvention eingeführt, immer die partiellen Wege aufzuschreiben.

Notieren Sie die Bestandteile der Kosten für jeden partiellen Weg in der Queue einzeln: "$g(n) + h(n) = f(n)$". Das erleichtert Ihnen die weiteren Schritte, da Sie dort ja nur mit $g(n)$ weiter rechnen dürfen. Gleichzeitig erleichtert es die Nachvollziehbarkeit.

Auf dem Papier sortiert sich die Queue schlecht, deshalb können Sie darauf verzichten, wenn Sie den im nächsten Schritt zu expandierenden Weg unterstreichen. Wer nicht mit Unterstreichen arbeiten will, muss eben dann manuell sortieren ...

Wenn bei der Graph-Search-Variante ein Weg nicht in die Queue aufgenommen wird, weil bereits ein anderer (günstigerer) Weg zum selben (Zwischen-/End-) Knoten bereits in der Queue enthalten ist, schreiben Sie dies geeignet auf. Dies gilt auch für den analogen Fall, wenn ein Weg aus der Queue entfernt wird, weil ein günstigerer Weg zum selben (Zwischen-/End-) Knoten eingefügt werden soll.

A*-Suche -- Anforderungen an Heuristik (Tree-Search)

Tree-Search-Variante: Die Heuristik muss zulässig sein:

• Seien $h^\star(n)$ die tatsächlichen optimalen Restkosten von einem Knoten $n$ zum nächsten Ziel.
• Dann muss für jeden beliebigen Knoten $n$ gelten: $$h(n) \le h^\star(n)$$
• Außerdem muss gelten:
  • $h(n) \ge 0$ für jeden Knoten $n$
  • $h(n) = 0$ für jeden Zielknoten $n$

=> Beispiel: Luftlinie als Abschätzung

Hinweis: Im der englischen Ausgabe des [Russell2020] wird die zulässige Heuristik auch "admissible heuristic" genannt.

A* ist optimal

A* (Tree-Search-Variante) mit zulässiger Heuristik ist optimal.

Beweis siehe Übung :-)

Einfache Verbesserungen A* (Tree-Search)

• Dynamische Programmierung: Behalte von mehreren Pfaden zum gleichen Knoten nur den günstigsten in der Queue

• Pfade, deren Endknoten bereits früher im Pfad vorkommt (Schleifen), werden in Schritt 2 nicht in die Queue aufgenommen

• Übergang zur Graph-Search-Variante und Markierung von Knoten

  => Achtung: Dann schärfere Anforderungen an Heuristik (Konsistenz)

A*-Suche -- Anforderungen an Heuristik (Graph-Search)

Graph-Search-Variante: Die Heuristik muss konsistent sein:

Für jeden Knoten $n$ und jeden durch eine Aktion $a$ erreichten Nachfolger $m$ gilt: $$h(n) \le c(n,a,m) + h(m)$$ mit $c(n,a,m)$ Schrittkosten für den Weg von $n$ nach $m$ mit Aktion $a$.

Außerdem muss gelten:

• $h(n) \ge 0$ für jeden Knoten $n$
• $h(n) = 0$ für jeden Zielknoten $n$

=> Eine konsistente Heuristik ist gleichzeitig zulässig.

Hinweis: Im der englischen Ausgabe des [Russell2020] wird die konsistente Heuristik auch "consistent heuristic" genannt.

Eigenschaften Branch-and-Bound, Best-First, A*

Wrap-Up

• Informierte Suchverfahren

  • Nutzen reale Pfadkosten und/oder Schätzungen der Restkosten
  • A*: komplette Kostenfunktion $f(n) = g(n)+h(n)$ => besondere Anforderungen an die Heuristik! (Tree-Search: zulässige Heuristik; Graph-Search: konsistente Heuristik)

• Ausblick auf Verbesserungen der vorgestellten Suchverfahren:

  • Beschränkung der Suchtiefe ("Depth-Limited-Search")
  • Iterative Vertiefung der Suchtiefe ("Iterative-Deepening-Search"), beispielsweise IDA* ("Iterative-Deepening A*")
  • Beschränkung des verwendeten Speichers, beispielsweise SMA* ("Simplified Memory-Bounded A*")

Lokale Suche: Gradientensuche

Unterschiede in den Suchproblemen?

Bisher betrachtete Suchverfahren:

• Systematische Erkundung des Suchraums
• Weg zur Lösung wichtig

=> Oft aber nur das Ziel an sich interessant! (Und nicht, wie man dort hin gelangt.)

Beispiel: Stundenplan

Analogie: Bergsteigen ohne Karte und Pfade

Gradienten-Suche: "Gehe in Richtung des steilsten Anstiegs der Zielfunktion."

=> Schrittweise Verbesserung des aktuellen Zustands (Lokale Suche)

• Verschiedene Namen: "Hill-climbing", "Greedy local search"
• Kann auch als Minimierung angewendet werden

Pseudoalgorithmus Gradientensuche

1. Setze currNode auf den Startknoten
2. currNode ist gesuchtes Element: Abbruch, melde "gefunden"
   • Expandiere alle Nachfolger von currNode
   • Setze nextNode auf Nachfolger mit höchster Bewertung
   • Falls Bewertung von nextNode $\leq$ Bewertung von currNode: Abbruch, melde "nicht gefunden"
   • Setze currNode auf nextNode
3. Gehe zu Schritt 2

Beispiel Gradientensuche: $n$-Damen

• Ziel: Setze $n$ Damen auf ein $n \times n$-Spielfeld ohne Konflikte
• Start: Setze $n$ Damen auf ein $n \times n$-Spielfeld (mit Konflikten)
• Suche: Bewege jeweils eine Dame so, daß die Anzahl der Konflikte reduziert wird

Schauen Sie sich auch Abb. 4.3 auf Seite 130 im [Russell2020] an!

Hinweis: Alle Damen stehen von Anfang an auf dem Brett und werden nur verschoben => "vollständige Zustandsformulierung"

Eigenschaften 8-Damen-Problem ($n=8$)

• Zustandsraum: $8^8 \approx 17$ Millionen Zustände!
• Beginnend mit zufällig erzeugtem Startzustand:
  • bleibt in 86% der Fälle stecken, d.h.
  • findet Lösung nur in 14% der Fälle.
• Beobachtung: Lösung nach durchschnittlich 4 Schritten, oder Verfahren bleibt nach durchschnittlich 3 Schritten stecken.

Quelle: nach [Russell2020, p. 131]

Eigenschaften Gradientensuche

• Vollständigkeit: nein
• Optimalität: nein
• Komplexität: linear in der Anzahl der zu expandierenden Knoten

Zielfunktion (Bewertung) nötig!

Problem: lokale Maxima und Plateaus

• Lokale Maxima/Minima: Algorithmus findet nur eine suboptimale Lösung
• Plateaus: Hier muss der Algorithmus mit zufälligen Zügen explorieren

Wrap-Up

Lokale Suchverfahren: Nur das Ergebnis zählt!

• Gradientenverfahren: Gehe in Richtung des stärksten Anstiegs der Kostenfunktion

Lokale Suche: Simulated Annealing

Motivation

Problem: lokale Maxima und Plateaus

• Lokale Maxima/Minima: Algorithmus findet nur eine suboptimale Lösung
• Plateaus: Hier muss der Algorithmus mit zufälligen Zügen explorieren

Mögliche Lösungen:

• Neustart des Algorithmus, wenn kein Fortschritt erzielt wird
• Rauschen "injizieren"

Gedankenexperiment: Ausweg aus lokalen Minima

• "Drehen der Landschaft": Minimieren statt Maximieren
• Ball wird in Zustandsraum-Landschaft gesetzt.
• Folge:
  • rollt steilsten Abstieg hinunter
  • rollt evtl. in Tal auf halber Höhe (lokales Minimum) => bleibt dort gefangen

=> "Schütteln der Landschaft" -- Ball springt aus dem Tal und rollt in anderes Tal

Nicht zu stark schütteln -- sonst wird u.U. globales Minimum verlassen!

Analogie Härten von Metall

• Metall erhitzen bis Atome frei beweglich
• Langsam abkühlen

=> stabiles Atomgitter mit minimalem Energiezustand

Übertragen der Idee

• Starkes "Schütteln" (hohe "Temperatur") am Anfang
• Schrittweises "Abkühlen" => "Schütteln" im Laufe der Zeit verringern

=> Simulated Annealing

Pseudocode Simulated Annealing (Minimierungsproblem)

def simulated_annealing(problem):
    current = problem.startNode
    t = 0;  temp = schedule(t)

    while temp>0:
        temp = schedule(++t)
        neighbors = current.expandSuccessors()
        if not neighbors: return current
        working = random.choice(neighbors)
        dE = problem.value(current) - problem.value(working)
        if dE > 0 or probability(math.exp(dE/temp)):
            current = working

    return current

Wenn dE positiv ist, dann ist der Nachfolger "besser" (hier: kleiner bewertet) als der aktuelle Knoten und wird immer als nächster Knoten übernommen.

Wenn dE negativ ist, dann ist der betrachtete Nachfolger "schlechter" (hier: größer bewertet) als der aktuelle Knoten. Dann wird er mit einer Wahrscheinlichkeit math.exp(dE/temp) als nächster Knoten übernommen. Diese Wahrscheinlichkeit ist bei hohen Temperaturen temp eher hoch, und sinkt, je niedriger die Temperatur temp wird.

Die Temperatur temp bewegt sich dabei von hohen positiven Werten auf den Wert Null (wird also nicht negativ).

Detail: Akzeptieren von Verschlechterungen

• Wahrscheinlichkeit zum Akzeptieren einer Verschlechterung: math.exp(dE/temp)
• $dE$ negativ => $\exp\left(\text{dE}/\text{temp}\right) = \exp\left(-\frac{|\text{dE}|}{\text{temp}}\right) = \frac{1}{\exp\left(\frac{|\text{dE}|}{\text{temp}}\right)}$

$\exp(a)$ bzw. $e^a$:

• $a<0$: geht gegen 0
• $a=0$: 1
• $a>0$: steil (exponentiell) gegen Unendlich ...

Wenn $dE$ negativ ist, wird math.exp(dE/temp) ausgewertet. Damit ergibt sich wegen $dE$ negativ: $\exp\left(\text{dE}/\text{temp}\right) = \exp\left(-\frac{|\text{dE}|}{\text{temp}}\right) = \frac{1}{\exp\left(\frac{|\text{dE}|}{\text{temp}}\right)}$. Betrachtung für $dE$ (nur negativer Fall!) und $\text{temp}$:

• Temperatur $\text{temp}$ hoch: $a = \frac{|\text{dE}|}{\text{temp}}$ ist positiv und klein (nahe Null), d.h. $\exp(a)$ nahe 1 (oder größer), d.h. die Wahrscheinlichkeit $1/\exp(a)$ ist nahe 1 (oder kleiner)
• Temperatur $\text{temp}$ wird kleiner und geht gegen Null: $a = \frac{|\text{dE}|}{\text{temp}}$ ist positiv und wird größer, d.h. $\exp(a)$ geht schnell gegen Unendlich, d.h. die Wahrscheinlichkeit $1/\exp(a)$ geht gegen 0

Abkühlungsplan problemabhängig wählen

• Initiale Temperatur: So hoch, daß praktisch jede Änderung akzeptiert wird

• Abkühlen: $T_k = \alpha T_{k-1}$ mit $0.8 \le \alpha \le 0.99$

  • Ausreichend langsam abkühlen!
  • Typisch: jede Stufe so lange halten, daß etwa 10 Änderungen akzeptiert wurden

• Stop: Keine Verbesserungen in 3 aufeinander folgenden Temperaturen

Der Abkühlungsplan muss problemabhängig gewählt werden. Das Beispiel zeigt typische Elementes eines solchen Abkühlungsplans.

Eigenschaften Simulated Annealing

• Vollständigkeit: ja (mit gewisser Wahrscheinlichkeit)
• Optimalität: ja (mit gewisser Wahrscheinlichkeit)

Voraussetzung: geeigneter Abkühlungsplan

Anwendungen von Simulated Annealing

• Flugplan-Scheduling
• Layout-Probleme (Chipentwurf, Leiterplatten)
• Produktionsplanung

Wrap-Up

Lokale Suchverfahren: Nur das Ergebnis zählt!

• Gradientenverfahren
  • Analogie Bergsteigen: Gehe in Richtung des stärksten Anstiegs der Kostenfunktion => Hill-Climbing
  • Achtung: Probleme mit lokalen Minima => Simulated Annealing