Neuer BegriffNachbarschaft einer Lösung · Eine Meta-Heuristik ist ein allgemein anwendbares Verfahren um zugrundeliegene, problemspezifische Heuristiken (wie lokale Suche) in erfolgversprechende

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 68 Dr. Peter Merz

Lokale Suche und Nachbarschaften

§ Bisher: Suche durch Lösungsveränderung

§ Neuer Begriff: Nachbarschaft einer Lösung• Nachbarschaft ist Menge der Lösungen, die von einer

gegebenen Lösung durch eine einfache (lokale) Veränderungsoperation (Zug/move) erreicht werden können

• TSP: N 2-opt(s) ist die Menge der Lösungen die durch einen Zweikantentausch von s „erreicht“ werden können

• GBP: N 2-opt(s) ist die Menge der Lösungen die durch den Tausch von zwei Knoten erreicht werden können


Lokale Suche - Pseudo Code

§ Neue Definition (Minimierung):

function localSearch(s : S) : Sbegin

repeatWähle s* ∈ N(s);if g(s*, s) > 0 then s = s*;

until ∀ s*∈ N(s) : g(s*, s) ≤ 0;return s;

end;

function localSearch(s : S) : Sbegin

repeatWähle s* ∈ N(s);if g(s*, s) > 0 then s = s*;

until ∀ s*∈ N(s) : g(s*, s) ≤ 0;return s;

end;

g(s*,s) = f(s) - f(s*)


Strategien zur Nachbarschaftssuche

§ Strategien für die Wahl aus N(s):• Auswahl in zufälliger Reihenfolge• Auswahl in systematischer Reihenfolge• First Improvement: Wähle erstes s‘ das Gewinn erhöht• Best Improvement: Wähle s‘ mit maximalem Gewinn

§ Unbekannte Größe:• Anzahl der Iterationen bis lokales Optimum erreicht ist• Begrenzung der Iterationen manchmal sinnvoll


Effizienz der Nachbarschaftssuche

§ Effizienzgrund:• Geringfügige Änderung im Lösungsvektor kann meist sehr

schnell evaluiert werden • Berechnung des Gewinns um Größenordnungen schneller

als die komplette Berechnung der Zielfunktion einer Lösung• Beispiel TSP:

- 2-opt Kantentausch-Berechnung in O(1)- Tourlängenberechnung in O(n)

• Durch Berechnung der Differenz des Gewinnes kann in manchen Fällen Effizienz noch gesteigert werden


BQP: Effiziente Gewinnberechnung (1)

§ Zielfunktion BQP:1 1

( ) , {0,1}n n

ij i j ii j

f x q x x x= =

= ∈∑∑

'

' '

1 1

' ' '

1, 1,

' '

1,

1

( , ') ( ') ( ) ( )

( ) ( ) ( )

( ) 2 ( )

k k

n n

k ij i j i ji j

n n

kk k k ik i k i k kj k j k ji i k j j k

n

kk k k ik i k ki i k

x x

g x x f x f x q x x x x

q x x q x x x x q x x x x

q x x q x x x

= =

= ≠ = ≠

= ≠

= −

= − = −

= − + − + −

= − + −

∑∑

∑ ∑

∑

Gewinn gk bei „flippen“ von Bit k:


BQP: Effiziente Gewinnberechnung (2)

§ Trick: Betrachtung der Änderung von Gewinn g:• Update-Regel für Gewinn gi bei „flippen“ von Bit k:

' '( ) 2 ( )( )i ik i i k kg k q x x x x i k∆ = ⋅ − − ∀ ≠

• Update für Bit k: gk = -gk

• Update nur für gi mit qik ≠0 nötig: gi =gi + ∆gi

§ Effizienzsteigerung:• Berechnung von f(x) à O(n2)• Berechnung von gk à O(n)• Berechnung von ∆gk à O(1)


Nachteil der Nachbarschaftssuche

§ Problematik:• Bessere Lösungen außerhalb der Nachbarschaft werden nicht

gefundenà Lösungen sind lokal optimal

àLösungsansätze:• Starten der lokalen Suche mit verschiedenen Startkonfigurationen• Meta-Heuristiken

§ Working Definition:Eine Meta-Heuristik ist ein allgemein anwendbares Verfahren um zugrundeliegene, problemspezifische Heuristiken (wie lokale Suche) in erfolgversprechende Regionen des Suchraums zu leiten.


Simulated Annealing (1)

§ Idee:• Lokale Suche, aber• Gelegentliches akzeptieren schlechterer Lösungen• Analogie zum physikalischen Verfahren zum Abkühlen von

Kristallenà Naturinspiriert

• Schlechtere Lösungen werden mit bestimmter Wahrscheinlichkeit angenommen

§ Umsetzung:• Kirkpatrick et al. 1883, Cerny 1985 • Erstes Verfahren zur Vermeidung lokaler Optima



§ Physikalische Analogie:• Thermischer Prozess zur Erlangung eines Zustandes sehr

niedriger Energie in einem Festkörper (z.B. Kristall)1. Der Festkörper wird in einem Hitzebad zum Schmelzen

gebracht2. Die Atome sind zufällig verteilt3. Die Temperatur des Hitzebads wird langsam gesenkt und

somit der Festkörper langsam abgekühlt4. Bei jeder Temperatur stellt sich thermisches Gleichgewicht ein5. Die Atome können sich in der energetisch günstigsten Struktur

(Kristallgitter) anordnen

§ Simulation: • Monte Carlo-Algorithmus



§ Metropolis-Algorithmus:• Monte-Carlo Simulation des Annealingprozesses• Simuliert Entwicklung eines Festkörpers im Hitzebad• Generiert Folge von Zuständen:

1. Vom aktuellen Zustand i mit Energie Ei wird Nachfolgezustand j durch kleine Pertubation generiert

2. Falls Ej – Ei ≤ 0, wird Zustand j akzeptiert3. Falls Ej – Ei > 0, wird j akzeptiert mit Wahrscheinlichkeit

( )exp

: Bolzmannkonstante, T: Temperatur

j i

B

E E

k T

B

p

k

−= −



§ Analogie zur Optimierung:• Zustand ↔ zulässige Lösung• Energie ↔ Zielfunktion• Grundzustand ↔ optimale Lösung• Nachfolgezustand ↔ Lösung aus Nachbarschaft

§ Simulated Annealing:• Oftmals wird benachbarte Lösung zufällig gewählt• Annealing: Temperatur T wird langsam erniedrigt• Metropolis-Akzeptanzkriterium für schlechtere Lösungen

(Minimierung):

( )( *) ( )exp f s f sT−−


Simulated Annealing - Pseudo Code

function simulatedAnnealing(s : S) : Sbegint = T(0), n = 0; sbest =s;repeat

Wähle s* ∈ N(s);if g(s*, s) > 0 then s = s*;else if exp(g(s*,s)/t) > rand[0,1) then s= s*;if g(s, sbest) > 0 then sbest = s;t = T(n);n = n + 1;

until n > nmax;return sbest ;

end;

function simulatedAnnealing(s : S) : Sbegint = T(0), n = 0; sbest =s;repeat

Wähle s* ∈ N(s);if g(s*, s) > 0 then s = s*;else if exp(g(s*,s)/t) > rand[0,1) then s= s*;if g(s, sbest) > 0 then sbest = s;t = T(n);n = n + 1;


end;


Anwendung von SA

§ Anwendung:• Festlegung des Abkühlungsplans (Wahl von T)

- Anfangstemperatur T(0)- Rekursive Definition: T(n+1)=c T(n) (Geometrisches Abkühlen)- IdR. wird T für mehrere Iterationen konstant gehalten

• Problemspezifische Entscheidungen- Definition der Zielfunktion- Definition der Nachbarschaft- Ausgangslösung


Theorie von SA

§ Theoretische Konvergenz gegen das Optimum

§ Bewertung:• Unendliche Anzahl von Zustandsübergängen nötig• Suchraum ist nur endlich groß!!!• Konvergenzbeweise vor allem mathematisch interessant• Aussagen über Konvergenzgeschwindigkeit nur sehr schwer

zu treffen• Praktische Bedeutung eher gering


TSP: Simulated Annealing

§ Beispiel:• Zufällige Ausgangslösungen• 2-opt Nachbarschaft• Einfacher Abkühlungsplan:

- T(0) so dass 3% der Züge abgelehnt werden- Geometrisches Abkühlen (c = 0.95)- Temperatur wird für n(n-1) Schritte konstant gehalten

à Nachbarschaftsgröße

- Abbruch bei: 5 Temperaturen ohne Verbesserung und unter 2% Akzeptanzrate

àErgebnisse: Besser als 2-opt, schlechter als 3-opt, bei n=1000 7500 mal langsamer


Tabu Search (1)

§ Idee:• Meta-Heuristik, die auf der Ausnutzung eines Gedächtnisses

des bisherigen Suchprozesses basiert• Erste Ansätze von Glover, 1986, und Hansen, 1986• Ziel der effizienten Vermeidung lokaler Optima• Ausnutzung eines Gedächtnisses

à Speichern des Lösungsverlaufes

• Deterministische Leitung der Suche


Tabu Search (2)

§ Gedächtnis:• Vermeidung lokaler Minima und strategische Leitung• Kurzzeitgedächtnis (short term memory):

- Wesentlicher Teil, Vermeidung von Schleifen

• Mittelfristiges Gedächtnis (intermediate term memory):- Intensivierung der Suche

• Langzeitgedächtnis (long term memory):- Diversifizierung der Suche


Tabu Search (3)

§ Such-Strategie:• TS verwendet aggressive Suche in der aktuellen

Nachbarschaft (best improvement LS)• In jedem Schritt wird die beste benachbarte Lösung

angenommen, auch wenn diese schlechter ist à Suchstrategie führt zu Zyklen

• Vermeidung von Zyklen durch Verbieten des wiederholten Besuchens von Lösungen

à Ausnutzung des Gedächtnis des Suchprozesses

àDaher der Name Tabu Search


Einfacher Tabu Search Algorithmus

§ Eigenschaften:• Es wird nur Kurzzeitgedächtnis Mst verwendet• Zulässige Nachbarschaft wird durch Verbot früher besuchter

Lösungen eingeschränkt • Zulässige Nachbarschaft hängt vom Kurzzeitgedächtnis ab

à N(s, Mst)

• Verbot früher besuchter Lösungen àTabu-Liste

§ Tabu-Liste:• Explizites Speichern der zuletzt besuchten Lösungen

- Sehr speicherintensiv- Überprüfung zeitaufwendig


Tabu-Listen-Verwaltung (1)

§ Tabu-Attribute:• Alternative: Speichern von Lösungsattributen früher

besuchter Lösungen• Anhand der Lösungsattribute wird entschieden, ob

Lösungen „tabu“ sind• Tabu-Attribute werden in einer Tabu-Liste gespeichert• Wichtige Größe: Tabu-Listenlänge tl• Lösungen sind verboten, falls sie Tabu-Attribute enthalten• Als Tabuattribute werden oft Attribute von Zügen (lokalen

Lösungsveränderungen) benutzt und die Umkehrung der Züge für tl Iterationen verboten


Tabu-Listen-Verwaltung (2)

§ Tabu-Liste:• Oftmals werden verschiedene Tabuattribute verwendet à

mehrere Tabu-Listen• Tabu-Liste wird meist nicht als „Liste“ realisiert• Effizientes Überprüfen des Tabu-Status: Speichern der

Iterationszahl bis zu der ein Attribut tabu ist

§ Aspirationskriterien:• Überschreiben des Tabu-Status „interessanter“ Lösungen• Häufigstes Kriterium: Verbotene Lösung ist besser als beste,

bisher gefundene Lösung• Verschiedene andere Kriterien wurden entwickelt


TS - Abbruchkriterien

§ Abruch der Suche, wenn• eine feste Anzahl Iterationen überschritten ist• seit einer festen Anzahl von Lösungen keine neue beste

Lösung mehr gefunden wurde• die zulässige Nachbarschaft leer ist• eine Lösung ausreichender Güte gefunden wurde


Tabu Search – Pseudo Code

function simpleTabuSearch(s : S) : SbeginT = {}; n = 0; sbest =s;repeat

Finde bestes s* ∈ N(s) mit s* ∉T oder g(s, sbest) > 0 ;s = s*;T = T ∪ {s};if g(s, sbest) > 0 then sbest = s;n = n + 1;


end;

function simpleTabuSearch(s : S) : SbeginT = {}; n = 0; sbest =s;repeat

Finde bestes s* ∈ N(s) mit s* ∉T oder g(s, sbest) > 0 ;s = s*;T = T ∪ {s};if g(s, sbest) > 0 then sbest = s;n = n + 1;


end;


Tabu Search - Kurzzeitgedächtnis

§ Tabu-Listenlänge:• Wesentlicher Parameter von TS• Zu kurze Tabu-Listen à Zyklen• Zu lange Tabu-Listen à Zu starke Beschränkung der Suche• Geeignete Parameterwahl erfolgt experimentell• Geeignete Parameter sind problemspezifisch oder gar

Instanzabhängig

§ Verschiedene Strategien:• Robust Tabu Search, Taillard `91• Reactive Tabu Search, Battiti et al. `94-96.


Tabu Search - Langzeitgedächtnis

§ Mittel- und Langzeitgedächtnis: • Basiert oft auf der Häufigkeit von bestimmten Zügen bzw.

der Häufigkeit von Attributen in guten Lösungen

§ Intensivierungsstrategien:• Intensivieren die Suche in bestimmten Regionen des

Suchraums- Neustart von Elitelösungen z.B. mit leerer Tabu-Liste- Häufig auftretende Lösungsattribute werden fixiert

§ Diversifikationsstrategien:• Lenken die Suche in zuvor ungenügend erkundete

Suchraumregionen- Führen Lösungsattribute ein, die nicht häufig benutzt wurden


Robust Tabu Search

§ RoTS (Taillard 91):• Entwickelt fürs QAP• Tabu-Listenlänge tl wird zufällig aus dem Intervall [tl,min,tl,max]

gewählt• In bestimmten Abständen (alle 2 ⋅ tl,max Iterationen) wird tl neu

bestimmt• Dadurch Problem der Wahl der optimalen Tabu-Listenlänge

umgegangen• Zusätzliches Aspirationskriterium:

- Lösung wird akzeptiert, wenn Lösungsattribut seit mehr als mIterationen nicht geändert wurde

- m idR. sehr groß à Diversifikation


Reactive Tabu Search

§ ReTS (Battiti u. Tecchiolli 94):• Entwickelt für QAP und Knapsack-Problem• Tabu-Listenlänge wird dynamisch angepasst:

- Erhöhung um konstanten Faktor bei Erkennen eines Zyklus- Sei m die durchschnittliche Zyklenlänge- Erniedrigung um konstanten Faktor, wenn letzte Erhöhung

mehr als m Iterationen zurückliegt

• Diversifikationsmechanismus:- Wird ausgeführt, wenn die Anzahl der Lösungen, die öfter als

ein vordefinierter Schwellwert wiederholt besucht wurden, ein Limit überschreitet

- Eine Anzahl proportional zu m von zufälligen Schritten wird ausgeführt


QAP: Vergleich SA und TS

§ QAP Nachbarschaft: Tausch zweier Zuweisungen

§ Ergebnisse aus Merz et al. 2000:

Instanz SA RoTS ReTS Zeit

Tai80a 3.29% 1.02% 0.48% 180sTai80b 5.10% 2.92% 1.60% 180sTai100a 1.85% 0.91% 0.39% 300sSko100a 2.94% 0.19% 0.40% 300sTai100b 6.70% 2.37% 1.47% 300sTai150b 3.79% 2.85% 1.78% 600sTai256c 0.37% 0.33% 0.27% 1200s

Instanz SA RoTS ReTS Zeit

Tai80a 3.29% 1.02% 0.48% 180sTai80b 5.10% 2.92% 1.60% 180sTai100a 1.85% 0.91% 0.39% 300sSko100a 2.94% 0.19% 0.40% 300sTai100b 6.70% 2.37% 1.47% 300sTai150b 3.79% 2.85% 1.78% 600sTai256c 0.37% 0.33% 0.27% 1200s

Documents

Neuer BegriffNachbarschaft einer Lösung · Eine Meta-Heuristik ist ein allgemein anwendbares Verfahren um zugrundeliegene, problemspezifische Heuristiken (wie lokale Suche) in erfolgversprechende