Lokale Suche: Gradientensuche

TL;DR

Lokale Suchverfahren: Nur das Ergebnis zählt! Nicht der Weg ist das Ziel, sondern nur das Erreichen des Ziels.

In Analogie zum Bergsteigen: Gehe in Richtung des stärksten Anstiegs kann man die Suche so formulieren, dass man in jedem Suchschritt den Nachfolgeknoten nach dem stärksten Anstieg der Kostenfunktion auswählen. Dieses Verfahren nennt sich auch Hill-Climbing (bzw. Gradientensuche).

Videos (YouTube)
Videos (HSBI-Medienportal)
Lernziele
  • (K2) Problematik der lokalen Minima bei Gradientenverfahren
  • (K3) Lokale Suche (Gradientenabstieg)

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

"Wie Bergsteigen am Mount Everest in dickem Nebel mit Gedächtnisverlust"
  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
Quizzes
Challenges

Betrachten Sie folgende Landkarte und Restwegschätzungen:

Quelle: MapGermanyGraph.svg by Regnaron and Jahobr on Wikimedia Commons (Public Domain)

Finden Sie mit der Gradienten-Suche jeweils einen Weg von Würzburg nach München. Vergleichen Sie das Ergebnis mit der Best-First-Suche.

Übungsblätter/Aufgaben
Quellen