Lokale Suche: Gradientensuche
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).
- (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"
- Setze
currNode
auf den Startknoten 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 voncurrNode
: Abbruch, melde "nicht gefunden" - Setze
currNode
aufnextNode
- Expandiere alle Nachfolger von
- 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
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.
- [Russell2020] Artificial Intelligence: A Modern Approach
Russell, S. und Norvig, P., Pearson, 2020. ISBN 978-0134610993.
Gradientenabstieg: Abschnitt 4.1.1