Lokale Suche Flashcards
Wie ist der Basisalgorithmus der Lokalen Suche beim Suchproblem?
Wann spricht man von einem Gradientenabstieg bei der lokalen Suche?
Wenn alle Nachfolgezustände generiert werden und davon die stärkste Verbesserung ausgewählt wird.
Wie wird die Gradientenabstriegmethode noch bei der lokalen Suche genannt?
steepest descent, greedy search, hill climbing
Was sind Vor- und Nachteile von der Gradientenabstiegsmethode bei der lokalen Suche?
lokale Optima werden besonders schnell gefunden, sollte aber die Nachbarschaft sehr groß sein, kann es effizienter sein nicht alle Nachfolgezustände zu generieren, sondern bereits die erste gefunde Verbesserung zu werden.
Was sind Möglichkeiten für den Basisalgorithmus bei der lokalen Suche aus dem lokalen Optimum zu entkommen?
- Suche mit einer anderen Initiallösung beginnen (Restart)
- nicht verbessernde Zustände erlauben (Random Walk
- Nachbarschaft erweitern
- Heuristik anpassen
- Tabusuche
- Simulated Annealing
- Evolutionäre Algorithmen
Wie kann ich einem lokalen Optimum bei der lokalen Suche mit Nachbarschaftserweiterung entkommen?
Man erweitert die Nachbarschaft durch limiterte Tiefensuche. Im ersten Schritt mit Nachbarschaftsgröße 1 enthält alle Zustände die mit einer Aktion erreichbar sind. Im nächsten Schritt wird dann die Nachbarschaftsgröße auf 2 erhöht, die dann alle Zustände enthält die mit 2 Aktionen erreicht werden können usw.
Wie sieht der Pseudocode aus wenn man den Basisalgorithmus für die lokale Suche mit der Nachbarschaftswerweiterung erweitert?
Wie kann ich einem lokalen Optimum bei der lokalen Suche mit Heuristik anpassen entkommen?
Wenn das Optimierungsproblem mehrere Kriterien hat können die einzelnen Heuristikkomponenten neu Gewichtet werden.
Wie sieht der Pseudocode aus wenn man den Basisalgorithmus für die lokale Suche mit der Heuristik anpassen erweitert?
Wie kann ich einem lokalen Optimum bei der lokalen Suche mit Tabusuche entkommen?
Die Tabusuche verwaltet eine Tabuliste von Zuständen die die Nachbarschaft des aktuellen Zustands einschränken. Typsicherweise enthält diese die letzten n Zustände um Zyklen zu vermeiden.
Wie sieht der Pseudocode aus wenn man den Basisalgorithmus für die lokale Suche mit der Tabusuche erweitert?
Wie sieht der Pseudocode aus wenn man den Basisalgorithmus für die lokale Suche mit simulated Annealing erweitert?
Was ist die Idee hinter Evolutionären Algorithmen zum entkommen aus lokalen Optima bei der lokalen Suche?
Basierend auf einer großen Population von Zuständen vererben die besten Kandidaten durch Mutation, Rekombination und Selektion ihre Eigenschaften an die nächste Generation.
Wie sieht der Pseudocode für einen Evolutionären Algorithmus bei der lokalen Suche aus?
