Lokales Minimum/Local Search

Moderator: Optimierungsalgorithmen

PeterZwegat
Neuling
Neuling
Beiträge: 3
Registriert: 10. Feb 2016 15:48

Lokales Minimum/Local Search

Beitrag von PeterZwegat »

Hallo allerseits,

ich habe eine Verständnisfrage zu Local Search. Zu einem Input \(I\) und einer Lösung \(s \in F_I\) ist das lokale Minimum die Lösung \(s^* \ in F_I\), die in der Nachbarschaft von \(s\) liegt und dort den kleinsten Wert aller Nachbarn annimmt.

Local Search funktioniert folgendermaßen. Ausgehend von einer beliebigen Lösung \(s^*\) wird zunächst das lokale Minimum \(s\) in der Nachbarschaft von \(s^*\) gesucht. Von dem lokalen Minimum wird wieder das lokale Minimum in dessen Nachbarschaft gesucht usw., bis keine Verbesserung mehr möglich ist.

Daraus folgt, dass die finale Lösung von Local Search nicht zwangsweise mit der Ausgangslösung benachbart sein muss. Zwar sind beide Lösungen im Nachbarschaftsgraphen, jedoch sind sie nicht zwingend direkt miteinander verbunden. Ist diese Annahme richtig oder habe ich etwas falsch verstanden?

freundliche Grüße

PeterZwegat
Neuling
Neuling
Beiträge: 3
Registriert: 10. Feb 2016 15:48

Re: Lokales Minimum/Local Search

Beitrag von PeterZwegat »

Okay, ich habe es nun verstanden. Hatte die Definition vom lokalen Minimum falsch herum gelesen, also [...] with \((s,s^*)\) statt \((s^*,s)\). Jetzt gibt das ganze mehr Sinn.

Antworten

Zurück zu „Optimierungsalgorithmen“