Moderne Heuristische Optimierungsverfahren · • Tabu Search. Folie 5 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Inhalte der Vorlesung (2) §Fitnesslandschaften

Moderne Heuristische Optimierungsverfahren:

Meta-Heuristiken

Wilhelm-Schickard-Institut für Informatik - WSI-RASand 1, Raum A 316

Dr. Peter Merz

[email protected]

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

Lerninhalte

§ Einführung in Optimierungsprobleme

§ Lösungsverfahren für kombinatorische und nichtlineare Optimierungsprobleme

§ Lokale Suchverfahren und deren Vor- und Nachteile

§ Moderne Ansätze (Meta-Heuristiken) und deren Leistungsfähigkeit

§ Methoden zur systematischen empirischen Untersuchung von (Meta-)Heuristiken

§ Anwendungsmöglichkeiten von (Meta-)Heuristiken


Gründe „Driving Forces“

§ Kombinatorische/nichtlineare Optimierungsprobleme treten in sehr vielen Anwendungsbereichen auf

§ Es gibt keine generelle/universelle Lösungsmethode

§ Neue algorithmische Ideen• Naturinspirierte Suchverfahren• Hybride Algorithmen

§ Verständnis des Verhaltens der Algorithmen notwendig

§ Übertragung der Verfahren auf neue Anwendungsgebiete durch schnelle Hardwareentwicklung möglich


Inhalte der Vorlesung (1)

Vorläufiger Inhalt:

§ Einleitung• Optimierungsprobleme • Exakte Verfahren vs. Heuristiken• Klassifikation von Heuristiken

§ Konstruktionsheuristiken• Problemabhängige Heuristiken• Greedy-Strategien

§ Nachbarschaftssuche• Lokale Suche• Simulated Annealing• Tabu Search


Inhalte der Vorlesung (2)

§ Fitnesslandschaften• Modell und Definition• Effektivität von Heuristiken

§ Populationsbasierte Heuristiken• Evolutionäre Algorithmen• Partikel-Schwärme• Populationsbasiertes Inkrementelles Lernen• Ameisenkolonien• Scatter Search, ...

§ Anwendungsgebiete• Optimierung in der Bioinformatik und Bildverarbeitung


Literatur zur Vorlesung

§ Folien zur Vorlesung im Netz als PDF.

§ Weitere Literatur: D. Corne, M. Dorigo und F. Glover: New Ideas in Optimization, McGraw Hill, 1999.

Z. Michalewicz und D. B. Fogel: How to Solve It: Modern Heuristics, Springer-Verlag, 1999.

C. Reeves: Modern Heuristic Techniques for CombinatorialProblems, McGraw Hill, 1995.

E.H.L. Aarts, J.K. Lenstra (editors): Local search in Combinatorial Optimization, John Wiley Sons, 1997.


Optimierungsprobleme

§ Was ist ein Optimierungsproblem?

• Betriebswirtschaftlich:Entscheidungssituation, in der ein vorgegebener Nutzen in kostenminimaler Weise zu realisieren ist, wobei aus mehreren Alternativen eine nach speziellen Kriterien ausgewählt wird.

• Mathematisch:Zu einer Funktion soll ein Eingabewert gefunden werden, so dass die Funktion einen minimalen Wert annimmt, wobei i. A. eine Beschränkung für die Eingabewerte existiert.


Arten von Optimierungsproblemen (1)

§ Lineare Programmierung (LP):• Lineare Zielfunktion, lineare

Nebenbedingungen• Effizient lösbar durch

Simplexmethode, Interior PointMethode n

T

Rx

xbxA

xcxf

∈

≥≥=

0mit

)(min

§ Nichtlineare Programmierung (NLP):• Minimierungsfunktion ist mindestens quadratisch• Varianten: linear beschränkte Optimierung, quadratische

Programmierung• Allgemein nicht effizient lösbar


Arten von Optimierungsproblemen (2)

§ Integer Programmierung (IP)• Wie LP/NLP jedoch: x∈ Zn

• Spezialfall: 0/1 IP mit bool‘schen Variablen• Linear (ILP) oder nicht linear (IP)

§ Mixed Integer Programmierung (MIP)• Mischung von reellwertigen und ganzen Zahlen• MILP oder MIP

§ Kombinatorische Optimierung• Mathematisch gleichbedeutend mit IP/ILP• Permutations-, Reihenfolge-Probleme, Zuordnungs-

Probleme, Finden von Teilmengen


Kombinatorische Optimierungsprobleme

§ Definition:• Ein KOP ist ein Maximierungs- oder Minimierungsproblem

und besteht aus:1. Einer Menge DP von Instanzen,2. Einer endlichen Menge SP(I) von (möglichen) Lösungen für

jede Instanz I∈DP,und3. Einer Funktion mP, die jeder Lösung x∈ SP(I) zu jeder Instanz

I∈DP,einen positiven, reellwertigen Lösungswert mP(x,I)zuordnet.

• Optimale Lösung:x*∈ SP(I) mit mP(x,I) ≤ mP(x*,I) ∀ x∈ SP(I) (Maximierung)x*∈ SP(I) mit mP(x*,I) ≤ mP(x,I) ∀ x∈ SP(I) (Minimierung)


)1(),(

1

1)1(),()( πππππ n

n

iii ddL += ∑

−

=+

Problem des Handlungsreisenden

§ Traveling Salesman Problem (TSP):• Gesucht: eine Rundreise durch n Städte, jede Stadt darf

nur einmal besucht werden. • Ziel: Die zurückgelegte Wegstrecke soll minimal sein.

• Lösung: Reihenfolge der Städte: π(1),π(2),...,π(n)→ eine Permutation der Menge 1,2,...,n.

• Die Distanzmatrix (di,j) gibt die Entfernungen der Städte an.


1

n

i=1,i j

n

i=j,j i

min ( )

mit 1 1,...,

1 1,...,

1 1,...,

n

ij iji

ij

ij

iji Q j V Q

L x d x

x j n

x i n

x Q n

=

≠

≠

∈ ∈ −

=

= ∀ ∈

= ∀ ∈

≥ ∀ ⊂

∑

∑

∑

∑ ∑

Problem des Handlungsreisenden (1)

§ Traveling Salesman Problem als ILP:

107

1

6

4

8

3

5

2

9

Constraints verletzt!


1

n

i=1,i j

n

i=j,j i

min ( )

mit 1 1,...,

1 1,...,

1 1,...,

n

ij iji

ij

ij

iji Q j V Q

L x d x

x j n

x i n

x Q n

=

≠

≠

∈ ∈ −

=

= ∀ ∈

= ∀ ∈

≥ ∀ ⊂

∑

∑

∑

∑ ∑



107

1

6

4

8

3

5

2

9

Constraints verletzt!


1

n

i=1,i j

n

i=j,j i

min ( )

mit 1 1,...,

1 1,...,

1 1,...,

n

ij iji

ij

ij

iji Q j V Q

L x d x

x j n

x i n

x Q n

=

≠

≠

∈ ∈ −

=

= ∀ ∈

= ∀ ∈

≥ ∀ ⊂

∑

∑

∑

∑ ∑



Alle Constraints erfüllt!

107

1

6

4

8

3

5

2

9


Graph-Partitionierungsproblem

§ Graph Partitioning Problem (GPP):• Gesucht: Zerlegung eines Graphen G=(V,E) in k gleich

große Teilmengen.• Ziel: Die Anzahl der Kanten zwischen den Teilmengen soll

minimal sein.

:,...,1|),(),...,(

),...,(),...,(

1

11

llk

kk

ViViklEjiVVe

VVeVVc

∉∧∈∈∃∈=

=

• Allgemeinerer Fall: gewichtete Kanten → Minimierung der Summe der Kantengewichte von e

• Spezialfall k = 2: Graph Bipartitioning (GBP)


Graph-Bipartitionierungsproblem

§ Graph Bipartitioning Problem (GBP):• Zerlegung eines Graphen in k=2 gleich große Teilmengen.

107

1

6

4

8

3

5

2

9

12

11

Cut, c(vb,vr) = 3


Quadratisches Zuweisungsproblem

§ Quadratic Assignment Problem (QAP):• Gesucht: Zuordnung von n Objekten zu n Positionen• Gegeben:

- Fluß fij von Objekt i nach Objekt j- Entfernung dij von Position i und Position j

• Ziel: Minimierung des Produktes aus Fluß und Entfernung

∑∑= =

=n

i

n

jjiji fdC

1 1)(),(,)( πππ

• Lösung: Permutation π, π(i)=j bedeutet eine Zuweisung von Objekt j zu Position i


Binäre quadratische Optimierung

§ Binary Quadratic Programming (BQP):• Gesucht: binärer Vektor, der eine quadratische Funktion f(x)

maximiert.• Gegeben: n x n Matrix Q=(qij).

1,0,)(1 1

∈== ∑∑= =

iji

n

i

n

jij

t xxxqxQxxf

• Spezialfälle: Maximum Clique, Maximum Independent Set, Maximum Cut Problem


Transportoptimierung (1)

§ Vehicle Routing Problem (VRP):• Gegeben: n Kunden, m LKW und 1 Depot.• Gesucht: m Touren um alle n Kunden zu bedienen.• Ziel: Minimierung der zurückgelegten Wegstrecke:

)()( )1(,00),(1

1

1)1(),( jjj

j

jjdddL l

m

j

l

iii πππππ ++= ∑∑

=

−

=+

• lj : Anzahl Kunden für LKW j• πj : Besuchsreihenfolge für LKW j


Transportoptimierung (2)

§ Capacitated Vehicle Routing Problem (CVRP):• Wie VRP nur mit zusätzlichen Restriktionen für die Beladung

der LKW: Das Gesamtgewicht darf die Kapazität Cj der einzelnen LKW nicht überschreiten:

mjCw j

l

ii

j

j,...,1

1

1)( =∀≤∑

−

=π

• Wk : Gewicht der Ware für Kunde k• Cj : Maximales Beladungsgewicht

§ Time constrained VRP: Zeitlimit pro Kunde, Zeitlimit pro Route§ VRP with time windows: Für jeden Kunden gibt es ein

Zeitfenster zur Belieferung.


Rucksackproblem

§ Multidimensional Knapsack Problem (MKP):• Gegeben: m Rucksäcke und n Gegenstände• Ziel: Profitmaximierung unter Berücksichtigung des

Gewichtes

• ci : Profit zu Gegenstand i• wij : Gewicht von Gegenstand i in Rucksack j• Wj : Maximalgewicht von Rucksack j

∑∑==

≤=n

ijiij

n

iii WxwmitxcxP

11

)(


Klassifizierung von KOP

§ Arten nach Aufgabenstellung, zum Beispiel:• Zuweisung• Reihenfolgebestimmung• Partitionierung• Teilmengenbestimmung

§ Art der Nebenbedingungen: • Keine Constraints (BQP)• Implizite Constraints (TSP,QAP)• Explizite Constraints (MKP)• Implizite und explizite Constraints (VRP)


Kombinatorische Optimierung

§ Kombinatorische Optimierung heißt:• Endliche Anzahl von möglichen Lösungen• Schnell wachsende Zahl der Lösungen, idR. exponentiell mit

der Problemgröße

§ Problemgröße:• Eigenschaft der Datenmenge einer Instanz bzw. Lösung• Bsp. TSP:

- Anzahl n der Städte- Länge der Permutation π zur Beschreibung der

Besuchsreigenfolge- Der Lösungsraum S hat die Größe |S|=(n-1)!/2


Komplexität

§ Wachstum des Suchraums:

§ Vergleich: • Anzahl der Atome im Universum ca. 1080

• Alter des Universums ca. 5 x 107 s

n 10 100 1000 10000n2 100 10000 106 108

n3 103 106 109 1012

2n 1024 1030 10301 103010

n! 106 10157 102567 1035659

n 10 100 1000 10000n2 100 10000 106 108

n3 103 106 109 1012

2n 1024 1030 10301 103010

n! 106 10157 102567 1035659


Komplexitätstheorie (1)

§ Theorie der NP-Vollständigkeit• Klassifikation der Probleme aufgrund der Schwierigkeit ihrer

algorithmischen Lösung• Klassifikation aufgrund des besten bekannten Algorithmus

für ein Problem• Klassifikation über asymptotisches Verhalten der

Algorithmen

§ Beschränkungen der NP-Vollständigkeit• Nur Zeitkomplexität• Worst-Case Analyse der Algorithmen• Nur Entscheidungsprobleme (Probleme die „Ja“ oder „Nein“

liefern)


Komplexitätstheorie (2)

§ Zeitkomplexität• Wird gemessen an der Anzahl elementarer Operationen• Formalisierung mittels O(•)-Notation:

- Sei f,g : ¥ → ¥- Dann f(n) ∈ O(g(n)), falls positive natürliche Zahlen c und n0

existieren, so dass für alle n ≥ n0 gilt: f(n) ≤ c · g(n)

• Ein Algorithmus ist polynomial, falls seine Zeitkomplexität in O(p(n)) ist, wobei p(n) ein Polynom ist.

• Ein Algorithmus ist exponentiell, wenn Zeitkomplexität nicht polynomial beschränkbar ist.

• Polynomial beschränkt / polynomiell ↔ effizient• Exponentiell ↔ ineffizient


NP-Vollständigkeit (1)

§ Grundlegende Klassen:• Klasse P:

Entscheidungsprobleme, die mit einem polynomiellenAlgorithmus gelöst werden können

• Klasse NP: Entscheidungsprobleme, die mit einem nichtdeterministischen polynimiellen Algorithmus gelöst werden können

• Nichtdeterministischer Algorithmus:- In der ersten Phase wird eine Lösung geraten (nichtdet.

Turingmaschine)- In der zweiten Phase wird deterministisch in polynomieller Zeit

die Lösung verifiziert• P ⊆ NP, aber: P = NP? • Allgemein anerkannte Annahme: P ≠ NP!



§ Polynomielle Reduzierbarkeit:Ein Problem Π ist polynomiell reduzierbar auf ein Problem Π‘, falls ein poynomieller Algorithmus existiert, der jede Instanz von Π in eine Instanz von Π‘ transformiert und für jede Instanz von Π ein „Ja“ ausgegeben wird, gdw. „Ja“ für die entsprechende Instanz von Π‘ ausgegeben wird.

§ NP-Vollständigkeit:• Ein Problem Π ist NP-vollständig, genau dann wenn

1. Π ist in NP und2. Für alle Π‘ in NP gilt, das Π‘ polynomiell reduzierbar auf Π ist.



§ Anmerkungen:• Klasse der NP-vollständigen Probleme umfasst die

schwersten in NP• Wird ein polynimal beschränkter Algorithmus für ein

Problem aus NP gefunden, gilt P=NP!• Es ist unwahrscheinlich, dass für ein NP-vollständiges

Problem ein polynomieller Algorithmus gefunden wird!

§ Beweis der NP-Vollständigkeit:1. Zeige, dass Problem in NP liegt2. Wähle bekanntes, NP-vollständiges Problem und

konstruiere Transformation auf das neue Problem3. Zeige, dass Transformation polynomial beschränkt ist


NP-harte Optimierungsprobleme

§ Erweiterung auf Optimierungsprobleme:• Offensichtlich nicht leichter als die Entscheidungsvariante• Optimierungsvariante nicht in NP• Optimierungsproblem löst das Entscheidungsproblem• Neuer Begriff: NP-hart

§ NP-harte Probleme:Ein Problem ist NP-hart, genau dann wenn für alle Π‘ in NPgilt, dass Π‘ polynomiell reduzierbar auf Π ist.

§ Viele kombinatorische Optimierungsprobleme sind NP-hart!


Exakte Verfahren

§ Vollständige Enumeration:• Möglich, da endlich großer Suchraum• Nicht praktikabel, da exponentielle Laufzeit

§ Implizite Enumeration:• Suchraum wird durch einen Suchbaum eingeteilt• Effizienzsteigerung durch Elimination von Teilbäumen:

- Branch Bound- Branch Cut


Branch Bound

§ Suchbaumverfahren für Optimierungsprobleme: Zusätzliche Berücksichtigung von Lösungskosten

§ Branching: Verzweigung innerhalb des Suchbaums und Betrachtung von (disjunkten) Teilproblemen

§ Bounding: Verwendung oberer und unterer Schranken für Zielfunktionswerte• Obere Schranke: Beste gefundene Lösung (Minimierung)• Untere Schranke: Günstigste Vervollständigung einer

partiellen Lösung / (Diskrete) Relaxation des Problems • Falls untere Schranke größer als obere Schranke, kann

Teilbaum eliminiert werden.


Branch Cut

§ Ähnlich Branch Bound, aber:• Verwendung der LP-Relaxation des Problems für untere

Schranken: ILP → LP• Verwendung leistungsfähiger Heuristiken für obere

Schranken• Iterativer Ansatz:

Stellt die aktuelle Lösung des LP-Problems nicht das Optimum dar, wird eine neue Gleichung eingefügt, um die Lösung zu entfernen (cut) und das neue LP wird mit Simplex-Algorithmus oder anderen LP-Algorithmen gelöst.

• Schwierigkeit: Das Finden zulässiger Cuts

§ Relaxation: Entfernung von Constraints, um das Problem leichter lösbar zu machen


Exakte Lösung des TSP (1)

§ Historie der Rekorde bei der exakten Lösung von TSP-Instanzen mit Branch Cut:

Jahr Forschergruppe n

1954 G. Dantzig, R. Fulkerson und S. Johnson 49 Städte1971 M. Held und R.M. Karp 64 Städte1975 P.M. Camerini, L. Fratta und F. Maffioli 100 Städte1977 M. Grötschel 120 Städte1980 H. Crowder und M.W. Padberg 318 Städte1987 M. Padberg und G. Rinaldi 532 Städte1987 M. Grötschel und O. Holland 666 Städte1987 M. Padberg und G. Rinaldi 2,392 Städte1994 D. Applegate, R. Bixby, V. Chvátal und W. Cook 7,397 Städte1998 D. Applegate, R. Bixby, V. Chvátal und W. Cook 13,509 Städte2001 D. Applegate, R. Bixby, V. Chvátal und W. Cook 15,112 Städte


Exakte Lösung des TSP (2)

§ Aktueller Rekord: • n=15112 Städte• ergibt Suchraumgröße

|S|>1056592

• Netzwerk von 110 Prozessoren von der Rice University und der Princeton University

• Rechenzeit: 22.6 Jahre, skaliert auf Compaq EV6 Alpha Prozessor mit 500 MHz


Exakte Verfahren vs. Heuristiken (1)

§ Generell: Exakte Verfahren nur bei kleiner Problemgröße anwendbar

§ Branch Cut: • Sehr hohe Rechenzeit• Bei TSP sehr leistungsfähig• Aber nicht leicht übertragbar auf andere Probleme• Theorie für das Finden von Cuts notwendig• Gute Verfahren werden für obere Schranken benötigt

àAlternativen zu exakten Verfahren sind nötig!


Exakte Verfahren vs. Heuristiken (2)

§ Heuristik:• Griechisch heuriskein: Finden, entdecken• Eine Technik zur Suche von guten (nahezu optimalen)

Lösungen für ein Optimierungsproblem in möglichst kurzer Zeit

• Ohne Gültigkeit oder Optimalität zu garantieren! • In vielen Fällen wird nicht mal eine Aussage getroffen, wie

nahe die gefundene Lösung am Optimum liegt.


Klassifikation von Heuristiken

§ Problembezogen:• Problemspezifische Heuristiken • Problemunabhängige Heuristiken

§ Nach Komplexität:• Einfache Heuristiken• Hybride Heuristiken

§ Nach Methodik:• Konstruktionsheuristiken• Verbesserungsheuristiken

§ Deterministisch vs. Zufallsgesteuert


Meta-Heuristiken

§ Was sind Meta-Heuristiken?• Kombinieren unterschiedliche Suchstrategien

- Intensifikation und Diversifikation- Lokale und globale Suche- Konstruktion und Verbesserung- Populations- und Individuensuche- Meta-Algorithmus steuert eingebetteten Algorithmus

• Problemunabhängigkeit- Kapselung der problemspezifischen Komponenten- Leichte Übertragung auf neue Probleme


Konstruktionsheuristiken

§ Vorgehen:• Eine Lösung wird schrittweise aufgebaut• In jedem Schritt wird eine Lösungskomponente gewählt• Wahl in Abhängigkeit von Regeln• Ziel der Regeln: Eine möglichst gute Lösung zu produzieren

à Maximierung der erwarteten Lösungsgüte

§ Häufig verwendete Strategie:• „Greedy“ (gierige) Auswahl der Lösungskomponenten, d.h.

momentane Gewinnmaximierung


GBP: Greedy-Heuristiken

§ Vorgehen:• Partitionierung der Knotenmenge durch schrittweises

Zuweisen der Knoten zu den zwei Mengen• Abwechselndes Hinzufügen von Knoten zu den 2 Mengen• Greedy-Strategien zur Wahl der Knoten:

- Minimierung der der neuen Kanten zwischen den Mengen (externe Kanten, Ei), bei mehreren Kandidaten: maximiere Kanten innerhalb der Mengen (interne Kanten, Ii)

- Minimierung der Differenz zwischen externen und internen Kanten


GBP: Differential Greedy (1)

§ Vorgehen (Wahl der Knoten):• Minimierung der Differenz

der neuen Kanten zwischen den Mengen (externe Kanten, Ei) und den Kanten innerhalb der Mengen (interne Kanten, Ii)

• Bei mehreren Kandidaten zufällige Auswahl

107

1

68

3

5

2

9

12

11

Rot:12, d(12)=E12-I12 =0–1= -1d(4)=-1, d(3)=0, d(6)=2

4


GBP: Differential Greedy (2)

107

1

68

3

5

2

9

12

11

Blau: 6, d(6)=E6-I6 =1-2=-1d(4)=1-0=1, d(3)=2-1=1

4§ Vorgehen

(Wahl der Knoten):• Minimierung der Differenz

der neuen Kanten zwischen den Mengen (externe Kanten, Ei) und den Kanten innerhalb der Mengen (interne Kanten, Ii)

• Bei mehreren Kandidaten zufällige Auswahl


TSP: Nächster-Nachbar Heuristik

§ Nearest Neighbor Heuristic:• Beginnend mit einem

Startknoten wird als nächstes der verfügbare Knoten mit der kürzesten Entfernung gesucht und Kante eingefügt

• Gierig, da aktuell bestmögliche Wahl getroffen wird

• Ein Endpunkt der Kante ist fix

107

1

6

4

8

3

5

2

9


TSP: Greedy Heuristik

§ Greedy Heuristic:• Beginnend mit der

kürzesten Kante werden schrittweise Kanten hinzugefügt, bis Tour komplett

• In jedem Schritt wird die kürzmöglichste Kante gewählt ohne die Constraints zu verletzen

• Gierig, da aktuell bestmögliche Wahl getroffen wird

2

107

1

6

4

8

3

5

9


TSP: Einfüge-Heuristiken (1)

§ Insertion Heuristics:• Beginnend mit einer Tour bestehend aus einer Stadt

werden Städte hinzugefügt bis alle Städte besucht sind• Verschiedene Strategien existieren:

- Nearest Insertion: Einfügen der Stadt mit geringster Distanz zu einer Stadt aus der Tour

- Farthest Insertion: Einfügen der Stadt, bei der die geringste Distanz zu einer Stadt aus der Tour maximal ist

- Cheapest Insertion: Einfügen der Stadt, die die geringste Zunahme der Tourlänge bewirkt

• Einfügeposition:- Wahl durch Minimierung der Tourlängenzunahme (insertion)- Nach der nächstgelegenen Stadt in der Tour (addition)


TSP: Einfüge-Heuristiken (2)

§ Insertion-Heuristik:• Beispiel der Nearest Insertion Strategie:

107

1

6

4

8

3

5

9

107

1

6

4

8

3

5

9

22

Einfügereihenfolge: 1, 10, 6, 3, 7, 8, 4, 9, 2, 5


TSP: Vergleich Konstruktionsheuristiken (1)

§ Wie wird verglichen:• Laufzeit: Durch Zeitkomplexität• Speicherbedarf: Speicherkomplexität• Vergleich anhand von TSP-Instanzen aus der TSPLIB• Lösungsgüte: Abweichung vom Optimum in Prozent

(Percentage Excess)

( )( ) 1 100%

( )heu

opt

L xq x

L x

= − ⋅

• q(x)=100%: Doppelte Tourlänge• q(x)=0.0%: Optimale Tourlänge


TSP: Vergleich Konstruktionsheuristiken (2)

§ Ergebnisse:• Aus Reinelt’94, gemittelt über 24 Instanzen (n=198 – 5934)

1. Nearest Neighbor: O(n2) O(n) 26.27%2. Greedy: O(n2 log n) O(n2) 11.96%3. Nearest Insertion: O(n2) O(n) 20.98%4. Farthest Insertion: O(n2) O(n) 13.99%5. Cheapest Insertion: O(n2 log n) O(n2) 17.23%

• Es existieren schelle Varianten, wie

1. Bentley‘s Greedy: O(n log n) O(n) ca. 16%2. Bentley‘s NN: O(n log n) O(n) ca. 26%


Verbesserungsheuristiken

§ Vorgehen:• Eine bestehende Lösung wird schrittweise verbessert, bis

keine Verbesserung mehr erreicht werden kann• IdR. wird geprüft, ob geringfügige Veränderungen bessere

Lösungen im Sinne der Zielfunktion liefernàLokale Suche (local search)

§ Lokale Suche:• Eigenschaft: Es werden lokal optimale Lösungen erzeugt• Globale Optima sind auch lokale Optima, aber nicht

umgekehrt• Voraussetzung: eine gültige Lösung


Lokale Suche

§ Algorithmus (Maximierung):1. Verändere Lösung x → x‘2. Wenn f(x‘) > f(x) x = x‘;3. Wenn für alle x‘ gilt: f(x‘) < f(x), dann stop 4. sonst weiter mit Schritt 1

§ Lösungsveränderung:• Veränderung mit geringfügiger Zielfunktionsveränderung• Veränderung einzelner Komponenten des Lösungsvektors• Beachtung der Nebenbedingungen


GBP: Lokale Suche

§ Lösungsveränderung durch• Tausch eines Knotens aus Menge 1 mit einem Knoten aus

Menge 2• Tausch von mehreren Knoten aus Menge 1 mit gleichviel

Knoten aus Menge 2à Mengen bleiben gleich groß

§ Berechnung des Gewinns:• Nach Tausch von i und j werden von i und j externe Kanten

zu internen Kanten und umgekehrt• Summe aus Differenz von externen und internen Kanten:

∆c = Ei – Ii + Ej - Ij – 2 aij

- aij ist die Adjazenzmatrix des Graphen


GBP: 2-opt Lokale Suche

§ 2-opt: (Pairwise Exchange)• Tausch eines Knotens aus Menge 1 mit einem Knoten aus Menge 2

107

1

6

4

8

3

5

2

9

12

11

Cut, c(vb,vr) = 3

107

1

6

4

8

3

5

2

9

12

11

Cut, c(vb,vr) = 6

∆c = E3 – I3 + E6 – I6 – 2 aij=2 – 1 + 3 – 1 + 0 = 3


GBP: Kernighan-Lin Lokale Suche

§ 2-opt: Austausch von 2 Knoten• O(n2) Möglichkeiten für Tausch (n=|V|)

§ k-opt: Austausch von k Knoten• O(nk) Möglichkeiten für Tausch• Laufzeitreduktion auf O(n2) durch Idee von Kernighan und Lin:

nur eine Teilmenge aller Möglichkeiten wird betrachtet in Abhängigkeit eines Gewinnkriteriums

• Durch geeignete Datenstrukturen kann Laufzeit auf O(|E|) pro Iteration reduziert werden

• Idee wird Kernighan-Lin Heuristik (1970) genannt• Ähnlich zur Lin-Kernighan Heuristik (1973) fürs TSP


TSP: Lokale Suche

§ Lösungsveränderung durch• Städtetausch (Knotentausch)• Entfernen und Einfügen eines Knoten an anderer Position• Entfernen und Einfügen einer Kante an anderer Position• Kantentausch (2 Kanten, 3 Kanten, k Kanten)

§ Berechnung des Gewinns • Gewinn (Tourlängenverkürzung) =

alte Tourlänge – neue Tourlänge =Summe der Kanten, die entfernt werden minus Summe der Kanten die hinzugefügt werden


TSP: Knotentausch (node exchange)

§ Bsp.: Knoten 6 und 3 werden vertauscht

107

1

6

4

8

3

5

2

9

107

1

6

4

8

3

5

2

9

Gewinn:

g = d(1,3) + d(3,4) + d(5,6) + d(6,7) – ( d(1,6) + d(6,4) + d(5,3) + d(3,7) )


TSP: Knotenwiedereinfügen (node insertion)

§ Bsp.: Knoten 3 wird zwischen 5 und 7 eingefügt

107

1

6

4

8

3

5

2

9

107

1

6

4

8

3

5

2

9

Gewinn:

g = d(6,3) + d(3,4) + d(5,7) – ( d(6,4) + d(5,3) + d(3,7) )


TSP: Zwei-Kantentausch (2-opt)

§ Bsp.: Kanten (1,3) + (6,7) werden mit (1,6) + (3,7) getauscht

107

1

6

4

8

3

5

2

9

107

1

6

4

8

3

5

2

9

Gewinn:

g = d(1,3) + d(6,7) – ( d(1,6) + d(3,7) )


TSP: Drei-Kantentausch (3-opt)

§ Bsp.: Kanten (1,8) + (3,4) + (5,6) werden mit (1,6) + (4,8) + (3,5) getauscht

107

1

6

4

8

3

5

2

9

107

1

6

4

8

3

5

2

9

Gewinn:

g = d(1,8) + d(3,4) + d(5,6) – ( d(1,6) + d(4,8) + d(3,5) )


TSP: Lokale Suche im Vergleich

§ Ergebnisse:• Aus Reinelt’94, gemittelt über 24 Instanzen (n=198 – 5934)

Heuristik Zeit/Iteration Kanten q(x)

RT + Node exchange O(n2) 4 >100%RT + Node insertion (ni) O(n2) 3 97.18%NN + Node insertion (ni) O(n2) 3 16.59%RT + 2-opt O(n2) 2 14.67%NN + 2-opt O(n2) 2 8.42%RT + 2-opt/ni O(n2) 3 9.62%NN + 2-opt/ni O(n2) 3 5.80%RT + 3-opt O(n3) 3 8.01%NN + 3-opt O(n3) 3 5.00%

RT: Zufällige Startlösungen, NN: Nearest-Neighbor Lösungen

Heuristik Zeit/Iteration Kanten q(x)

RT + Node exchange O(n2) 4 >100%RT + Node insertion (ni) O(n2) 3 97.18%NN + Node insertion (ni) O(n2) 3 16.59%RT + 2-opt O(n2) 2 14.67%NN + 2-opt O(n2) 2 8.42%RT + 2-opt/ni O(n2) 3 9.62%NN + 2-opt/ni O(n2) 3 5.80%RT + 3-opt O(n3) 3 8.01%NN + 3-opt O(n3) 3 5.00%

RT: Zufällige Startlösungen, NN: Nearest-Neighbor Lösungen


TSP: Schnelle lokale Suche (1)

§ Ziel: Laufzeitreduktion auf O(n) pro Iteration

• 2-opt: d(t2,t1) + d(t4,t3) > d(t2,t3) + d(t4,t1)à d(t2,t3) < d(t2,t1) oder d(t4,t1) < d(t2,t1)

à Übertragung auf 3-opt möglich

à Kandidaten für t3 (t5) in aufsteigender Reihenfolge betrachten bis d(t2,t3) > d(t2,t1) oder bis k nächsten Nachbarn von t2 (t4)


TSP: Schnelle lokale Suche (2)

§ Zu Berechnen: Für jede Stadt k nächste Nachbarn• A priori durch Heapsort : O(n2 log k) • A priori durch 2-dim. Suchbäume: O(n log n + nk)

§ Weitere Laufzeitreduktion - don‘t look bits:• Wenn für ein t1 kein tourverkürzender Kantentausch gefunden

werden konnte, wird don‘t look bit für t1 gesetzt• Ein don‘t look bit für t1 wird gelöscht, wenn t1 Endpunkt einer

entfernten Kante ist• Alle Kandidaten für t1, deren don‘t look bit gesetzt ist, werden

nicht betrachtet• Anfangs sind alle don‘t look bits gelöscht


TSP: Konstruktionsheuristik + Lokale Suche

§ Ergebnisse:• Aus Merz’96, gemittelt über 18 Instanzen (n=51 – 3038)

Heuristik Ohne LS 2-optNearest Neighbor 20.75% 5.35%Nearest Insertion 21.70% 9.67%Farthest Insertion 10.38% 7.48%Cheapest Insertion 17.36% 7.79%

Heuristik Ohne LS 2-optNearest Neighbor 20.75% 5.35%Nearest Insertion 21.70% 9.67%Farthest Insertion 10.38% 7.48%Cheapest Insertion 17.36% 7.79%

• Aus Johnson’96, (n=1000)

Heuristik Ohne LS 2-opt 3-optRandom 2150% 7.9% 3.8%Nearest Neighbor 25.9% 6.6% 3.6%Greedy 17.6% 4.9% 3.1%

Heuristik Ohne LS 2-opt 3-optRandom 2150% 7.9% 3.8%Nearest Neighbor 25.9% 6.6% 3.6%Greedy 17.6% 4.9% 3.1%


TSP: Die Lin-Kernighan-Heuristik (1)

§ Idee von Lin-Kernighan (LK):• Statt 2 oder 3 Kanten wie in 2-opt/3-opt in jeder Iteration k

Kanten tauschen!• Lauftzeit sehr hoch: O(nk) Möglichkeiten

• Ab k=4 nicht mehr praktikabel und Tourlängenreduktion gering

• Betrachtung einer kleinen Teilmenge aller O(nk) Kombinationen à sequentieller Kantentausch

• Tiefensuche, k ist variabel• Tiefensuche besteht aus k Tauschoperationen, die zur

Verkürzung der Tour führen, einzelne Tauschop. Können Tour verlängern



§ Algorithmus:

2 1 2 2 2 1

1

*1 2 1

Schrittweiser Tausch von gegen

Gewinn in Schritt : ( , ) ( , ) | | | |

Bedingung für Tiefensuche: 0

Effektiver Tausch nach Schritten: Kanten mit

( ,

i i

i i i i i i i

i

i kk

k k k

x y

i g d u u d u u x y

G g

n k

G G d u u

− +

=

− −

= − = −

= >

= +

∑

2 2 1) ( , ) 0 maximal (2 )k kd u u k n− > ≤ ≤



§ Backtracking: • Betrachtung von Alternativen zu y1, x2, y2

• Dadurch: Alle 2-opt und 3-opt Züge enthalten

§ Reduktion des Suchraums:• Nur

sequentieller Kantentausch, d.h. xi und yiteilen sich einen Endpunkt Nicht-Sequentieller Kantentausch


TSP: Vergleich 3-opt und LK-Heuristik

§ Ergebnisse nach Johnson’96:• Startlösungen: Randomized Greedy• Zusätzliche Datentypen: (notwendig für große n)

- Cache für Distanzberechungen, keine Distanzmatrix- Two-Level Tree für Touren

Heuristik n=1000 10000 100000

3-opt <3.1% <3.0% <3.0%0.41s 4.7s 69s

Lin-Kernighan <2.0% <2.0% <2.0%0.77s 9.8s 151s

Heuristik n=1000 10000 100000

3-opt <3.1% <3.0% <3.0%0.41s 4.7s 69s

Lin-Kernighan <2.0% <2.0% <2.0%0.77s 9.8s 151s

• CPU-Zeiten: 150 MHz SGI Challenge


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,1n 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


Repräsentation von Lösungen (1)

§ Kontinuierliche Optimierung:

1 2( , , , ) nnx x x x= ∈… ¡ 1 2( , , , ) 0,1n

nx x x x= ∈…

0.50.5 0.90.9 0.20.2 0.10.1 0.70.7 0.70.7

§ Binäre Optimierung:

Lokale Suche: xi = xi + ε

0.50.5 0.90.9 0.10.1 0.10.1 0.70.7 0.70.7

00 11 00 00 11 11

Lokale Suche: xi = 1-xi

00 11 00 11 11 11


Repräsentation von Lösungen (2)

§ Permutationsprobleme• Lösung kann auf

unterschiedliche Arten dargestellt werden1. Permutationsvektor:

Π=π1,π2,π3,π4=4,3,1,2

2. Zuordnungsmatrix:

0 0 1 00 0 0 10 1 0 01 0 0 0

X

=

66 44 11 55 33 22

Lokale Suche: πi ↔ πj

66 55 11 44 33 22


TSP: Repräsentation von Lösungen

§ Pfaddarstellung:• Lösungsvektor gibt

Besuchsreihenfolge an

§ Matrizendarstellung:• Matrix gibt an, ob Kante (i,j) in

Tour enthalten ist (1) oder nicht (0)

§ Adjazenzdarstellung:• Lösungsvektor gibt zu jeder Stadt

den Nachfolger an

0 0 1 00 0 0 10 1 0 01 0 0 0

X

=

Π=π1,π2,π3,π4=1,4,2,3

Π=π1,π2,π3,π4=4,3,1,2

4

1 3

2


TSP: Repräsentation und Lokale Suche

§ Beispiel 2-opt lokale Suche: • Kanten (1,3) + (6,7) werden mit (1,6) + (3,7) getauscht

10 7

1

6

4

8

35

2

9

10 7

1

6

4

8

35

2

9

1010 11 33 55 22 99 88 44 66 77

1010 11 66 44 88 99 22 55 33 77

Pfaddarstellung:

33 99 55 66 22 77 1010 44 88 11

66 55 77 88 33 44 1010 99 22 11

Adjazenzdarstellung:

d


Lösungsrepräsentation und Lokale Suche

§ Welche Repräsentation für ein gegebenes Problem?• Geringfügige Änderungen in der Lösung à geringfügige

Änderungen in der Lösungsrepräsentation (Lösungsvektor)• Geringfügige Änderungen im Lösungsvektor à geringfügige

Änderungen in der Lösung (Fitness der Lösung)• Lokale Suche sollte sehr wenige Lösungskomponenten

ändernà Nicht immer möglich (TSP)à Effiziente Ausführung eines Zuges/Schrittesà Effiziente Berechnung der Fitnessänderung


Distanz zwischen Lösungen (1)

§ Distanz:• Maß für „Unähnlichkeit“ bzw. Verschiedenheit von Lösungen• Starker Zusammenhang mit Nachbarschaften• Basiert auf Vergleich der Lösungskomponenten

§ Beispiele:• Hamming-Distanz: Definiert zwischen Bitstrings:

- Anzahl der Bit in denen sich zwei Binärvektoren unterscheiden

• Euklidische Distanz: Definiert zwischen reellen Vektoren:- Summe der quadratischen Differenzen zwischen den

Komponenten

2

1

( , ) ( ) ,n

ni i

i

d x y x y x y=

= − ∈∑ ¡


Distanz zwischen Lösungen (2)

§ Definition:• Anhand der unterschiedlichen Lösungskomponenten• Anhand der Anzahl der Nachbarschaftzüge/lokalen

Veränderungsoperationen

§ Beispiel TSP:• Anzahl der unterschiedlichen Kanten in zwei Lösungen (d1)• Minimale Anzahl der 2-opt Züge, um die eine in die andere Lösung

zu transformieren (d2)• Es gilt: d1 ≤d2≤2⋅d1

§ Beispiel BQP:• Anzahl der Bit in denen sich zwei Binärvektoren unterscheiden

(Hamming-Distanz)• Minimale Anzahl der „Bitflips“ um die eine in die andere Lösung zu

transformieren (entspricht der Hamming-Distanz)


Nachbarschaft und Distanz

§ Nachbarschaftsdefinition:• N(s)=s‘∈ S: d(s,s‘)≤ dmin

§ Beispiel TSP: • k-opt Nachbarschaft: Nk-opt(s)=s‘∈ S: d(s,s‘)≤ k

• Mit: d(s,s‘) = | e ∈E : e ∈ s ∧ e ∉s‘|

§ Beispiel BQP:• k-opt Nachbarschaft: Nk-opt(s)=s‘∈ S: d(s,s‘)≤ k

• d: Hamming-Distanz


Fitnesslandschaften (1)

§ Konzept zur Beschreibung von Suchräumen• Jeder Lösung im Suchraum wird eine Höhe zugeordnet• Punkt = Lösung• Höhe des Punktes = Fitness der Lösung• Punkte sind räumlich angeordnet• Ähnliche Lösungen sind in der

Fitnesslandschaft benachbart

§ Wichtige Begriffe:• Nachbarschaft• Distanz von Lösungen

24

6

8

10

0.0

0.5

1.0

2

4

6

810

Z A

xis

Y AxisX Axis



§ Wichtige Eigenschaften:• Verteilung der Fitnesswerte (Mittel und Varianz von f)• Unebenheit der Landschaft (landscape ruggedness)• Die Zahl der lokalen Optima / Bergspitzen in der Landschaft• Die Verteilung der lokalen Optima im gesamten Suchraum• Die Anzahl der Schritte auf eine Bergspitze• Struktur und Größe von Attraktionsgebieten lokaler Optima• Größe und Struktur von Ebenen mit gleicher Fitness

à Neutral Networks



§ Beispiele von Fitnesslandschaften (NK-Fitnessmodell):

• Stark uneben (links) und weniger zerklüftet/“ruckelig“ (rechts)


Definition Fitnesslandschaften

§ Formal:• f: Fitnessfunktion / Zielfunktion• S: Suchraum, Menge aller möglichen Lösungen• d: Distanzmaß zwischen Lösungen• N: Nachbarschaftsfunktion• Landschaft: L=(f,S,d) oder L=(f,S, N)

• s∈ S: Punkt in der Fitnesslandschaft• F(s): Höhe des Punktes• N(s)=s‘∈ S: d(s,s‘)=dmin : (räumlich) benachbarte Punkte zu s


Statistische Fitnesslandschaften

§ Ziel: • Messung/Ermittlung der Eigenschaften von

Fitnesslandschaften

§ Autokorrelation:• Ermittlung lokaler EigenschaftenàErmittlung der „Ruggedness“ (Unebenheit)

§ Fitness-Distanz-Korrelation:• Ermittlung globaler EigenschaftenàErmittlung der Verteilung lokaler Optima im Bezug auf das

Optimum


Autokorrelation

§ Fragestellung:• Wie stark sind die Fitnesswerte zweier Punkte mit Abstand d korreliert?

§ Sei:

• Dann ist die Autokorrelationsfunktion definiert als:

2 2

2

( ) ( )

( ) ( ( ) )

( ) ( , ) | ( , )

s S

x S

f f f x

f f x f

S d x y S S d x y d

µ

σ∈

∈

= =

= −

= ∈ × =

∑

∑

22 2

( , )

1( ) ( ( ) )( ( ) )

( ) | ( ) | x y S

d f x f f y ff S d

ρσ ∈

= − −∑


Zufallslauf-Korrelation

§ Random Walk:• Autokorrelationsbestimmung durch Zufallslauf durch die

Landschaft• Die besuchten Punkte stellen eine Zeitreihe f(xt) dar• Random Walk Korrelation r(s) gibt die Korrelation der

Fitnesswerte s Schritte von einander entfernter Lösungen an

21

1( ) ( ( ) )( ( ) )

( )( )

m s

t t st

r s f x f f x ff m sσ

−

+=

≈ − −− ∑

• Leichte experimentelle Bestimmung


Korrelationslänge

§ Annahme:• Isotropische Landschaft• Autoregressive Zeitreihe yt =a yt-1 + et

à AR(1) Landschaft, r(s) = r(1)s = e –s/l

à l: Korrelationslänge

1 1ln(| (1)|) ln(| (1) |)r ρ

= − = −l

• Je kleiner l, desto zerklüfteter die Landschaft

• Je größer l, desto stärker korreliert sind benachbarte Punkte


Fitness-Distanz-Korrelation

§ Korrelation der Fitness und der Distanz zum Optimum von Lösungen (FDC):

1

( , )( , ) mit ( ) ( , )

( ) ( )

1( , ) ( ( ) )( ( ) )

( ) ( )

optopt opt

opt

m

opt i opt i optiopt

Cov f df d d x d x x

f d

f d f x f d x df d m

ρσ σ

ρσ σ =

= =

≈ − −⋅ ∑

• ρ=1.0: Mit steigender Entfernung zum Optimum steigt die Zielfunktion

• ρ=0: Kein Zusammenhang zwischen Fitness und Distanz

• ρ=-1.0: Mit steigender Entfernung zum Optimum sinkt die Zielfunktion


Fitness-Distanz-Korrelation lokaler Optima

§ Besonders wichtig:• Ist die Fitness und die Distanz zum Optimum von lokalen Optima

korreliert? • Sind die lokalen Optima auf den gesammten Suchraum verteilt

oder sind die sie um das globale Optimum herum verteilt?

§ Strukturierte Suchräume:• Lokale Optima konzentrieren sich in einem kleinen Bereich des

Suchraums• Je näher die Fitness an der Fitness des Optimum, desto mehr

Lösungskomponenten stimmen überein (FDC!)

§ Unstrukturierte Suchräume:• Zufällige Verteilung der lokalen Optima


Beispiele für Autokorrelation (1)

§ TSP:• AR(1) Landschaften mit r(s) =exp(-s/l) = exp(-s⋅k / n)

• Mathematisch bewiesen• k: Anzahl der Kanten beim Kantentausch• Korrelationslänge (l = n/k) ist unabhängig von der

Probleminstanz

§ GBP:• Mathematisch berechnet: l ≈ 1/8 ⋅ (n-3)

• Unabhängig von der Struktur des Graphen (Knotengrad)


Beispiele für Autokorrelation (2)

§ QAP:• Korrelationslänge ist

Instanzabhängig• Keine mathematisch

geschlossene Form bekannt• Korrelationslänge: n/l liegt

zwischen 2.8 und 4• AR(1)-Landschaft

§ BQP:• Korrelationslänge ist ebenfalls Instanzabhängig• Korrelationslänge: n/l liegt zwischen 2 und 3 (Schnitt 2.6%)


NK-Landschaften

§ NK-Modell: • zur Untersuchung von Fitnesslandschaften• N und K sind Parameter, Fitness f(x):

1

1

1

1( ) ( , , , ) mit : 0,1 [0,1] (Zufallszahl)

K

NK

i i i i ii

f x f x x x fN

+

=

= →∑ …

• Der Fitnessbeitrag von Gen i hängt vom Wert von Gen i (xi) und K anderen Genen ab

• Unebenheit der Landschaft kann mit N und K verändert werden

• Es gilt:1

( ) 11

sK N

r sN K+ ≈ − ⇒ ≈ +

l


Beispiele für Fitness-Distanz-Korrelation (1)

§ Beispiel Graph-Bipartitioning (GBP):• Zwei Instanzen mit stark unterschiedlichen Eigenschaften

Links: keine Korrelation (ρ≈0) Rechts: hohe Korrelation (ρ≈1)


Beispiele für Fitness-Distanz-Korrelation (2)

§ Verteilung lokaler Optima:• Hohe regionale Konzentration und zufällige Verteilung

Links: strukturiert, ρ≈-0.75 (BQP) Rechts: chaotisch, ρ≈0 (NK landscape)


NK-Fitnesslandschaften

§ Auswirkungen von K im NK-Fitnessmodell:

K=2, N=1024: FDC ρ≈-0.6, l≈341 K=11, N=1024: FDC ρ≈0, l≈85

K=2,N=64 K=11,N=64


Lösungsrepräsentation / Fitnesslandschaften

§ Funktion f(x) = 100 - (x - 8)2

• Ein lokales Optimum = globales Optimum bei x = 8

- In der Integercodierung gibt es 2 Nachbarn pro Lösung (x+1/x-1) und ein lokales Optimum

- In der Binärcodierung gibt es 4 Nachbarn pro Lösung (Bitflip) und zwei lokale Optima: 0111 (7) und 1000 (8)

- In der Gray-Codierung gibt es 4 Nachbarn und ein lokales Optimum

X f(x) binär gray-code

0 36 0000 00001 51 0001 00012 64 0010 00113 75 0011 00104 84 0100 01105 91 0101 01116 96 0110 01017 99 0111 01008 100 1000 11009 99 1001 110110 96 1010 111111 91 1011 111012 84 1100 101013 75 1101 101114 64 1110 100115 51 1111 1000

X f(x) binär gray-code

0 36 0000 00001 51 0001 00012 64 0010 00113 75 0011 00104 84 0100 01105 91 0101 01116 96 0110 01017 99 0111 01008 100 1000 11009 99 1001 110110 96 1010 111111 91 1011 111012 84 1100 101013 75 1101 101114 64 1110 100115 51 1111 1000


Meta-Heuristiken und Fitnesslandschaften

§ Ziele von Meta-Heuristiken:• Überwinden lokaler Optima• Effektive Suche durch Ausnutzen der Eigenschaften des

Suchraums

Globales Minimum

Nicht weit genug

Zu weit

• Intensivierung (Exploitation) und Diversifikation (Exploration)


„Ideale“ Fitnesslandschaften

§ Korrelation von Fitness und Distanz zum Optimum

Globales Minimum

• Je näher die lokalen Minima am Optimum desto bessere Zielfunktionswerte

• Der Abstand zum Optimum nimmt ab, je geringer die Fitnessdifferenz des lokalen Minimums zum Optimum ist


Populationsbasierte Suche

§ Bisherige Meta-Heuristiken:• Simulated Annealing• Tabu Searchà Ausgehend von einer Lösung wird gesucht

àPopulationsbasierte Heuristiken• Suche erfolgt ausgehend von mehreren Lösungen• Ausnutzen der in der Population „gespeicherten“ Information• Robuster als Individual-Suche• Leichter parallelisierbar


Evolutionäre Algorithmen (1)

§ Idee:• Simulation der natürlichen Evolution• Anpassung der Arten ist ein Optimierungsprozess• Populationsbasierte Optimierung

Mechanismen der Optimierung:• Speichern guter Lösungen• Variation/Lösungsänderung• Verwerfen oder Beibehalten

von Lösungen (Bewertung anhand der Zielfunktion)

Mechanismen der Optimierung:• Speichern guter Lösungen• Variation/Lösungsänderung• Verwerfen oder Beibehalten

von Lösungen (Bewertung anhand der Zielfunktion)

Mechanismen der Evolution:• Replikation• Variation• Selektion

Mechanismen der Evolution:• Replikation• Variation• Selektion


Evolutionäre Algorithmen (2)

§ Analogien:• Zielfunktion = Fitness

(Überlebensfähigkeit/Fortpflanzungsfähigkeit)• Lösung des Optimierungsproblems = Individuum/Species• Repräsentation einer Lösung = Genetischer Code• Lösungsveränderung = genetische Variation (Mutation und

Rekombination)• Lösungsauswahl = Selektion (Survival of the Fittest)

àPopulationsbasierte Optimierung


Historie der Evolutionären Algorithmen

§ Historie:• Genetische Algorithmen (Genetic Algorithms, GA) -

Holland 1962• Evolutionsstrategien (Evolution Strategies, ES) –

Rechenberg, Schwefel 1969• Evolutionäre Optimierung (Evolutionary Programming, EP) –

Fogel, Owens, Walsh 1965

• Genetische Programmierung (Genetic Programming, GP) –Koza 1994

§ EA “Flavors“:• 3 Entwicklungrichtungen (GA, ES, EP)• GP, MA, ...


Ablauf eines EA

§ Initialisierung:• Erzeugung von Individuen

§ Fitnessevaluation:• Bestimmung Fitness der Individuen

§ Elternselektion:• Auswahl von Individuen zur Variation

§ Variation:• Rekombination• Mutation

§ Überlebensselektion:• Übernahme von Individuen in die

nächste Generation (Nachkommenselektion)

InitialisierungInitialisierung

ElternselektionElternselektion

VariationVariation

EndeEnde

ÜberlebensselektionÜberlebensselektion

FitnessevaluationFitnessevaluation



Genetische Algorithmen - GA

§ Kodierung:• Binäre Repräsentation Ö genetischer Code• IdR. Decodierung zur Fitnessevaluation nötig• Unterscheidung zwischen Genotyp und Phänotyp

§ Elternselektion:• Fitnessproportionale Selektion

§ Variation:• Rekombination/Crossover Ö sexuelle Reproduktion• Mutation, spielt geringe Rolle

§ Überlebensselektion:• Einfache Ersetzung der Nachkommen durch die Eltern


Genetischer Code

§ Epistasie:• Pleiotropie: Ein Gen

beeinflusst mehrere phänotypischeEigenschaften

• Polygenie: Viele Gene legen eine phänotypischeEigenschaft fest

• Mathematische Sicht: Abhängigkeit der Variablen untereinander àNichtlinearität

11

55

22

33

44

77

66

88

aa

bb

dd

cc

ee

ff

gg

hh


Genotyp vs. Phänotyp

§ Genotyp: • Genetische Kodierung

einer Lösung (à Bauplan eines Organismus)

§ Phänotyp:• Lösung, Element des

Lösungsraumes (Suchraumes)

§ Fitness:• Bewertung des Phänotyps

Genotypen

Phänotypen

G(t)

G‘(t)

P(t+1)P‘(t)

Dekodierungs-funktion


Genetische Operatoren - Crossover

§ Crossover:• Dem Crossover in der

Natur nachempfunden:• Single-Point Crossover

• Verallgemeinerungen: two-point crossover, uniform crossover

• Crossover-Stellen werden zufällig gewählt

11 11 00 00 11 1100 0011

11 11 00 11 00 0011 1100

11 11 000011 11 00 00 11

00 11 11 0011 11 001100

x


Genetische Operatoren – Uniform Crossover

§ Uniform Crossover:• Verallgemeinerung durch

Einführen einer Crossover-Maske:

- 0: Nehme Genwert (Allel) von Elter A

- 1: Nehme Allel von Elter B

• Wichtige Eigenschaften:- Allele, die in den Eltern

gleich sind, sind auch in den Kindern zu finden

- Jedes Gen der Kinder stimmt mit mindestens einem Elter überein

11 11 00 00 11 1100 0011

11 11 00 11 00 0011 1100

11 11

0000

11

11

00 00

11

00

11 11

00

11 11

0011

00

00 00 11 00 11 1111 0000


Genetische Operatoren - Mutation

§ Mutation:• Bit-Flip mit geringer Wahrscheinlichkeit

11 11 00 00 11 1100 0011

11 11 00 11 11 1100 0011

• Wahrscheinlichkeit 1/l pro Bit (l: Länge des Binärvektors)

• Im Schnitt wird ein Bit Pro Mutation geändert


Genetische Operatoren - Selektion

§ Roulette Wheel• Fitnessproportionale Zufallsselektion• Fitness bestimmt erwartete Anzahl der Kopien in temporärer

Population

• Rekombination und Mutation wird auf temporäre Population angewendet

• Temporäre Population ergibt Population der nächsten Generation

49%

31%

6%

14%

Individuum 1Individuum 2

Individuum 3Individuum 4

( )( )

( )i

ij

j

f sp s

f s=

∑


Evolutionsstrategien - ES

§ Kodierung:• Reellwertige Repräsentation• Keine Decodierung zur Fitnessevaluation nötig• Operatoren arbeiten auf Phänotyp

§ Elternselektion:• Rein zufällige Selektion (uniform)

§ Variation:• Mutation mit Selbstadapation• Rekombination (geringerer Stellenwert)

§ Überlebensselektion:• Die besten aus Eltern und Kindern oder die besten Kinder


Evolutionsstrategien – Mutation (1)

§ Repräsentation:• Individum: (x, σ) mit x=(x1,...,xn),σ ∈¡n

§ Einfache Mutation:• Ni(0,1): Normalverteilte Zufallszahl (Mittelwert 0, Varianz 1)

( ) ( )1 1

Globale Schrittweite: (0,1)

Individuelle Schrittweite: (0,1)

Schrittweitenanpassung: exp( (0,1) (0,1))

Lernraten: 2 2

i i i

i i i i

i i i i

x x N

x x N

N N

n n

σ

σ

σ σ τ τ

τ τ− −

′ = + ⋅′ = + ⋅′ ′= ⋅ ⋅ + ⋅

′∝ ∝


Evolutionsstrategien – Mutation (2)

§ Korrelierte Mutation:• Hinzunahme von Winkeln (Erweiterung der Repräsentation)

Globale Schrittweite Individuelle Schrittweite Korrelierte Mutationen

• Ellipsen stellen Bereiche gleicher Mutationswahrscheinlichkeit dar


Evolutionsstrategien – Rekombination

§ Rekombinationsarten:

• Global: Für jede Komponente wird neuer Elter gewürfelt

12

( )

( )12

( )

. ( )( ). ( )

. (global,

generalis

diskret)

(

interme

). (global,intermediär)( ). ( )

diädiskre

ert

rt

i

i i

i ij

i i ij

i ij

i i i i

x yx y

x x y

x yx y xχ

∨ +′ = ∨ +

+ −x

y


Evolutionsstrategien – Selektion

§ (µ,λ)-Selektion: (Überlebensselektion)• Aus µ Eltern werden λ Kinder erzeugt (λ > µ)• Die µ besten der λ Kinder bilden die neue Population

§ (µ+λ)-Selektion: (Überlebensselektion)• Aus µ Eltern werden λ Kinder erzeugt• Die µ besten der µ Eltern und λ Kinder bilden die neue

Population

§ Spezialfälle:• (1,1)-ES: „Random Walk“• (1+1)-ES: zufallsgesteuerte lokale Suche


Evolutionäre Optimierung - EP

§ Kodierung: (wie bei ES)• Reellwertige Repräsentation• Keine Decodierung zur Fitnessevaluation nötig• Operatoren arbeiten auf Phänotyp

§ Elternselektion:• Rein zufällige Selektion (uniform)

§ Variation:• Nur Mutation!

§ Überlebensselektion:• Wettbewerbsauswahl (Tournament selection)


Evolutionäre Optimierung - Selektion

§ Wettbewerbsauswahl: • Engl. Tournament selection• Überlebensselektion• Schrittweise Auswahl• In jedem Schritt werden k > 1 Individuen ausgewählt• Auswahl ist zufällig• Das Beste wird in die Nachfolgegeneration übernommen• Vorgang wird wiederholt, bis Population gefüllt ist


Evolutionäre Optimierung - EP

§ Ursprünglich: (50er Jahre)• Entwickelt mit dem Ziel künstliche

Intelligenz zu kreieren• Evolution eines endlichen Automaten

(FSM) zur Vorhersage von Ereignissen in einer gewählten Umgebung

• Ereignisse : Symbole eines endlichen Alphabets

§ Mutation:• Änderung eines Ausgabesymbols• Änderung eines Zustandübergangs• Hinzufügen/Löschen eines Zustandes• Ändern des Startzustandes

BB

CCAA

0/β

1/γ

0/β

1/α

1/β

0/γ


Gegenüberstellung von GA, ES und EP

§ GA:• Binärkodierung - Genetische Operatoren arbeiten auf Genotyp• Fitnessproportionale Elternselektion• Variation durch Rekombination / Mutation wenig Bedeutung

§ ES:• Selbstanpassung der Strategieparameter• Reelle Kodierung – Operatoren arbeiten auf Phänotyp• Deterministische Überlebensselektion• Mutation, Rekombination weniger bedeutend

§ EP:• Wie ES, aber keine Rekombination• Zufallsgesteuerte Überlebensselektion


Varianten Genetischer Algorithmen (1)

§ GENITOR:• Es wird nur ein Kind bei der Rekombination erzeugt• Steady-State-GA:

- Es wird nur ein Kind pro Generation erzeugt- Kind ersetzt schlechtestes Individuum in der Population

• Rang-basierte Elternselektion: - Auswahlwahrscheinlichkeit wird durch den Rang in der

Population bestimmt- Linear ranking: Rang i ∈ [1,n], Selektionswahrscheinlichkeit :

max max min1

( ) ( )1i

ip s p p p

n−

= − −−


Varianten Genetischer Algorithmen (2)

§ CHC:• Cross-generational elitist selection:

- Nachkommenselektion entspricht Selektion in (µ+λ)-ES- Duplikate werden aus Population entfernt

• Heterogenous Recombination: - Elternauswahl zufällig, aber: Eltern mit minimaler Hamming-

Distanz- Variante von Uniform crossover: genau die Hälfte der

unterschiedlichen Bits werden invertiert

• Cataclysmic mutation: - Bei Konvergenz werden alle Individuen bis auf das Beste stark

mutiert

• CHC verwendet kleine Populationen


EA in der kombinatorischen Optimierung

§ Praxis:• EA/GA sind nicht sehr effektiv• Verwendung von Problemwissen à Hybride Algorithmen• Lokale Suche bietet sich an• Nutzen der Vorteile von EA und LS

§ Variation:• Rolle von Mutation und Rekombination wandeln sich• Rekombination in EA: Crossover erzeugt neue Lösung aus

den Lösungskomponenten der „Elternlösungen“• Rekombination in MA: Neue Lösungskomponenten werden

eingefügt


Memetics

§ Was bedeutet Memetik?

• Nach Biologen R. Dawkins (The Selfish Gene) gibt es neben der genetischen Evolution noch andere Formen

• In der menschlichen Kultur gibt es eine andere viel schnellere Form der Evolution: Die Evolution der Meme

§ Meme:• Einheiten von kultureller Wissensübermittlung• Bsp.: Ideen, Melodien, Rezepte, Theorien, Schmiedekünste• Replikation durch Immitation/Nachahmung• Variation durch Erweiterung, Neukombination, Verbesserung• Selektion durch Auswahl weniger Meme


Memetische Algorithmen

§ Unterschiede zu EA/GA:• Mene vs. Gene• Sehr schnelle Evolution, kleine Populationen• Variation beinhaltet Innovation• Lernen zur Lebenszeit = lokale Suche

§ Lernen und Evolution:• Baldwin‘sche Evolution: Lernen wirkt sich nicht auf Gene aus• Lamarck‘sche Evolution: Lernen bewirkt Änderung der Gene

§ Historie:• Brady, 1985: Erster MA (TSP)• Moscato, 1989: Einführung des Begriffs


Ablauf eines Memetischen Algorithmus

§ Idee:• Hybrider Evolutionärer Algorithmus• MA=EA+LS (Lokale Suche)

§ Prinzip:• Alle Individuen in der Population stellen

lokale Optima dar

InitialisierungInitialisierung

ElternselektionElternselektion

VariationVariation

EndeEnde

ÜberlebensselektionÜberlebensselektion



Lokale SucheLokale Suche

Lokale SucheLokale Suche

§ Variation:• Erzeugung neuer Startpositionen für

lokale Suche (Diversifikation)• Lokale Suche: Intensifikation


MA Pseudo-Code

procedure MA begin

Initialisiere Population P, gen = 0;foreach s in P do s = localSearch(s);repeat

P‘ = 0;for i=0 to nRecombinations do

sa = selectForVariation(P);sb = selectForVariation(P);

s* = recombine(sa, sb);s* = localSearch(s*);add s* to P‘;

endfor;for i=0 to nMutations do

s = selectForVariation(P);s* = mutate(s);

s* = localSearch(s*);add s* to P‘;

endfor;P = selectForSurvival(P, P‘);gen = gen +1;

until gen > genmax;end;

procedure MA begin

Initialisiere Population P, gen = 0;foreach s in P do s = localSearch(s);repeat

P‘ = 0;for i=0 to nRecombinations do

sa = selectForVariation(P);sb = selectForVariation(P);

s* = recombine(sa, sb);s* = localSearch(s*);add s* to P‘;

endfor;for i=0 to nMutations do

s = selectForVariation(P);s* = mutate(s);

s* = localSearch(s*);add s* to P‘;

endfor;P = selectForSurvival(P, P‘);gen = gen +1;

until gen > genmax;end;


ASPARAGOS (1)

§ ASPARAGOS ist...• Einer der ersten MA (M. Gorges-Schleuter, 1987)• Eine ASynchrone PARAllele Genetische OptimierungsStrategie• Ein Parallelisierungsmodell für EA• Ein MA mit 2-opt lokaler Suche fürs TSP

§ Populationsmodell:• Individuen sind räumlich angeordnet• Jedes Individuum kennt nur die Nachbarn• Individuen sind aktive Einheiten à Prozesse


ASPARAGOS (2)

§ Populationsstruktur:• Graph: Knoten=Prozess• Beispiele: Gitter, Hypercube,

geschlossene Leiter

§ Individuum-Prozess: • Auswahl eines Partners in der

Nachbarschaft• Rekombination mit Partner• Mutation mit geringer Wahrscheinlichkeit• Lokale Suche• Ersetzung des Individuums bei besserer

Fitness

Gitterstruktur

Geschlossene Leiter


Weitere MA

§ Weitere MA:• Die meisten MA verwenden ein EA-Framework angelehnt an

Genetische Algorithmen• Effektives Framework CHC, da kleine Populationen

- Rein zufällige Elternselektion- (µ+λ)-Nachkommenselektion mit Entfernung von Duplikaten- Restart durch starke Mutation (Diversifikation) bei Konvergenz

• Viele MA existieren, u.a. für- TSP, QAP, BQP, NK-Modell, GBP, Clustering- Scheduling, Knapsack-Problem, Graph-Färbung,

VLSI-Routing, ...


TSP: Rekombinationsoperatoren

§ k-Punkt-Crossover:• Nicht auf Permutationen ohne weiteres übertragbar• Alternative: PMX (1985)

§ Partially-mapped Crossover:• Mapping-Sektion wird zufällig gewählt• In Elter A und Elter B werden so lange Städte getauscht, bis

die beiden Lösungen in der Mapping-Sektion übereinstimmen


TSP: PMX-Rekombination (1)

§ Partially-mapped Crossover:

91 10 7 6 4 8 2 5 3

91 6 4 8 5 2 3 7 10

Elter A:

Elter B:

91 10 7 8 5 2 6 4 3

91 2 5 6 4 8 3 7 10

Kind A:

Kind B:

Tausch von 6 und 8, 4 und 5, 6 und 2

Tausch von 8 und 6, 5 und 4, 2 und 8


TSP: PMX-Rekombination (2)

§ Partially-mapped Crossover:

10 7

1

6

4

8

35

2

9

10 7

1

6

4

8

35

2

9

10 7

1

6

4

8

35

2

9

• Die rot markierten Kanten stammen von keinem der beiden Eltern à implizite Mutation!


TSP: MPX-Rekombination

§ Maximally Preservative Crossover:

34 2 10 8 9 5 7 6 1

102 9 8 3 7 5 1 6 4

Elter A:

Elter B:

110 8 9 5 7 3 6 4 2Kind C:

• (5,7) und (7,3) sind von B• Nächste Stadt zu 3 in B ist 1• (1,6), (6,4) und (4,2) von B

• Teilpfad wird von A nach C kopiert

• Tour wird erweitert durch Kanten von B

• Sind keine Kanten mehr vorhanden, werden Kanten von A verwendet

• Sind keine Kanten mehr vorhanden, wird nächste Stadt in Tour B gesucht


TSP: Rekombination + Repair

§ Repair:• Auch MPX enthält implizite Mutationen• Lokale Suche kann als „Repair“ verwendet werden, um

fremde Kanten zu eliminieren à Memetische Algorithmen

§ Alternative:• Entwicklung von Rekombinationsoperatoren ohne implizite

Mutationen• Sehr schwer, algorithmisch aufwendig


Rekombinationsarten

§ Respectful Recombination:• Allele, die in beiden Eltern (A und B) identisch sind, werden

im Kind (C) erhalten•

§ Assorting Recombination:• Das Kind enthält nur Allele von den Eltern• Keine impliziten Mutationen!•

( , ) ( , ) ( , ) ( , )d A C d A B d B C d A B≤ ∧ ≤

( , ) ( , ) ( , )d A C d C B d A B+ =

A

B

C

A

B

C


Rekombinationsarten (2)

§ Rekombinationsschemata:

Child C

P arent A

P a rent B

d

Child C

Parent A

Pa re nt B

d

Child C

P a re nt A

Pare nt B

(a) Assorting (b) Respectful (c) Unrespectful, not assorting


TSP: DPX-Rekombination (1)

§ DPX:• Erzeugung eines Kindes mit dem selben Abstand zu den Eltern wie

der Abstand der Eltern

55 33 99 11 22 88 00 66 77 44

11 22 55 33 99 44 88 66 00 77

55 33 99 11 22 88 00 66 77 44

55 33 99 1122880066 77 44

Elter A:

Elter B:

Kind C:

Segmente:

( , ) ( , ) ( , ) ( , )d A C d A B d B C d A B= ∧ =


TSP: DPX-Rekombination (2)

§ DPX:• Tour wird an den Kanten getrennt, die nicht in beiden

Elternteilen vorkommen• Die Tour-Segmente werden neu durch Nearest-Neighbor-

Heuristik verbunden• Kanten die nicht in beiden Elternteilen vorkommen, werden

nicht eingefügt (sind Tabu)

§ Eigenschaften:• Hoher Grad an impliziten Mutationen, im Verlaufe der

Evolution abnehmend• Nur in Kombination mit lokaler Suche• Gut geeignet für Memetische Algorithmen


TSP: MA Ergebnisse

• GX: Generische Rekombination (Merz 2000)

Instanz Oper Gen Qualität Nopt t in s

lin318 DPX 19 42029/0.00% 30/30 8 lin318 GX 13 42029/0.00% 30/30 8pcb442 DPX 824 50778/0.00% 30/30 147 pcb442 GX 286 50778/0.00% 30/30 68att532 DPX 560 27686/0.00% 30/30 127 att532 GX 289 27686/0.00% 30/30 106rat783 DPX 122 8806/0.00% 30/30 26 rat783 GX 136 8806/0.00% 30/30 35pr1002 DPX 333 259045/0.00% 30/30 112 pr1002 GX 182 259045/0.00% 30/30 98

pr2392 GX 2407 378032.6/0.000% 27/30 2588pcb3038 GX 5248 137702.6/0.006% 3/30 6955 fl3795 GX 341 28794.7/0.079% 1/30 7212

Instanz Oper Gen Qualität Nopt t in s

lin318 DPX 19 42029/0.00% 30/30 8 lin318 GX 13 42029/0.00% 30/30 8pcb442 DPX 824 50778/0.00% 30/30 147 pcb442 GX 286 50778/0.00% 30/30 68att532 DPX 560 27686/0.00% 30/30 127 att532 GX 289 27686/0.00% 30/30 106rat783 DPX 122 8806/0.00% 30/30 26 rat783 GX 136 8806/0.00% 30/30 35pr1002 DPX 333 259045/0.00% 30/30 112 pr1002 GX 182 259045/0.00% 30/30 98

pr2392 GX 2407 378032.6/0.000% 27/30 2588pcb3038 GX 5248 137702.6/0.006% 3/30 6955 fl3795 GX 341 28794.7/0.079% 1/30 7212

• Zeit t auf Pentium III 500 MHz


QAP: CX-Rekombination (1)

§ CX - Cycle Crossover:• QAP Lösung stellt Zuweisung von Objekten zu Positionen dar• Alle Gene/Allele identisch in beiden Eltern werden übernommen• Eine Position wird zufällig gewählt und eine Zuweisung von einem

Elter übernommen.• Um implizite Mutation zu verhindern, werden daraufhin so viele

Zuweisungen vom selben Elter übernommen, wie nötig• Es ergibt sich eine zyklische Abhängigkeit der Zuweisungen von

Objekten zu Positionen


QAP: CX-Rekombination (2)

§ Beispiel:

Elter A: 22 44 77 11 88 99 33 55 66

Elter B: 77 44 55 88 33 99 11 22 66

Positionen: 11 22 33 44 55 66 77 88 99

44 99 66

22 44 77 99 55 66

22 44 77 88 33 99 11 55 66

Kind C: 22 44 77 88 33 99 11 55 66


QAP: MA und andere Meta-Heuristiken

§ QAP: Vergleich Meta-HeuristikenZahlen: Abweichung von besten Lösung in %

Instanz MA-1 MA-2 Ro-TS Re-TS FANT MMAS SA t/sectai60a 1.314 1.597 1.313 0.794 2.577 1.159 3.199 90tai80a 1.106 1.305 1.023 0.482 2.525 0.768 3.298 180tai100a 1.089 1.252 0.909 0.385 2.569 0.728 1.848 300sko100a 0.096 0.127 0.191 0.397 0.474 0.195 2.942 300tai60b 0.000 0.000 1.898 0.929 0.213 0.075 1.760 90tai80b 0.191 0.004 2.929 1.602 0.821 0.718 5.092 180tai100b 0.076 0.038 2.373 1.469 0.360 0.328 6.696 300tai150b 0.361 0.397 2.851 1.775 1.176 1.167 3.787 600tho150 0.151 0.202 0.548 0.488 0.765 0.395 2.939 600tai256c 0.070 0.099 0.326 0.266 0.273 0.067 0.370 1200

Ro-TS, Re-TS: Robust/Reactive Tabu SearchFANT, MMAS: Ant Colony Optimization: Fast Ant System, Min-Max Ant SystemSA: Simulated Annealing


Iterierte lokale Suche (1)

§ Iterated Local Search:• ILS: MA mit Populationsgröße 1, nur Mutation• Sehr effektiv beim TSP à Iterated Lin-Kernighan• Mutation ähnlich Diversifikationsmechanismus in Tabu-

Search• Einfachste Strategie, aus lokalen Minima zu entkommen• MA effektiver als ILS bei vielen Optimierungsproblemen (z.B.

GBP, QAP)

§ Iterated Lin-Kernighan:• Lokale Suche: Lin-Kernighan-Heuristik• Mutation: nicht-sequentieller 4-Kantentausch


Iterierte lokale Suche (2)

§ Pseudo-Code:

function iteratedLocalSearch : Sbegin

erzeuge Startlösung s;n = 0, s = localSearch(s);repeat

s* = mutate(s);s* = localSearch(s*);if g(s*, s) > 0 then s = s*;n = n +1;

until n > nmax;return s;

end;

function iteratedLocalSearch : Sbegin

erzeuge Startlösung s;n = 0, s = localSearch(s);repeat

s* = mutate(s);s* = localSearch(s*);if g(s*, s) > 0 then s = s*;n = n +1;

until n > nmax;return s;

end;


TSP: Iterated Lin-Kernighan

• MA Ergebnisse (oben), ILK (unten):

Instanz Gen Qualität sdev. t in sFnl4461 528 183366.3 (0.438 %) 163.7 294pla7397 1155 23307621.7 (0.202 %) 14120.4 1860rl11849 536 928115.5 (0.523 %) 795.8 1006Us13509 1082 20125182.2 (0.712 %) 27980.9 2422d18512 1226 650803.2 (0.869 %) 477.8 2873Pla33810 3832 66321344.7 (0.479 %) 45162.4 11523Pla85900 9069 142986675.5 (0.477 %) 79510.3 52180

Instanz Gen Qualität sdev. t in sFnl4461 528 183366.3 (0.438 %) 163.7 294pla7397 1155 23307621.7 (0.202 %) 14120.4 1860rl11849 536 928115.5 (0.523 %) 795.8 1006Us13509 1082 20125182.2 (0.712 %) 27980.9 2422d18512 1226 650803.2 (0.869 %) 477.8 2873Pla33810 3832 66321344.7 (0.479 %) 45162.4 11523Pla85900 9069 142986675.5 (0.477 %) 79510.3 52180

Fnl4461 7108 183191.1 (0.343%) 72.7 300 Pla7397 1830 23324376.2 (0.273%) 17985.5 1800Rl11849 11274 926139.9 (0.309%) 772.9 1000Us13509 9912 20063763.7 (0.405%) 13400.8 2400D18512 22243 647949.3 (0.426%) 229.1 2900Pla33810 7930 66270531.2 (0.402%) 22368.1 7200Pla85900 19437 142919653.4 (0.430%) 54291.6 14400

Fnl4461 7108 183191.1 (0.343%) 72.7 300 Pla7397 1830 23324376.2 (0.273%) 17985.5 1800Rl11849 11274 926139.9 (0.309%) 772.9 1000Us13509 9912 20063763.7 (0.405%) 13400.8 2400D18512 22243 647949.3 (0.426%) 229.1 2900Pla33810 7930 66270531.2 (0.402%) 22368.1 7200Pla85900 19437 142919653.4 (0.430%) 54291.6 14400


Parameterwahl in MA

§ Parametervorschläge:• Populationsgröße: P=10-50

- Gering im Vergleich zu GAs (100-1000)

• Anzahl Rekombinationen: 0.5P• Anzahl Mutationen: 0.1P

§ Terminierungskriterium:• Zeitlimit• Konvergenz:

- Lösungen in der Population sind sich sehr ähnlich (Distanz!)- Kein Fortschritt (durchschnittliche Fitness) seit k Generationen


Erweiterungen von EA

§ Rekombination:• Üblich: Rekombination von zwei Eltern• Möglich: Rekombination von mehreren Eltern

§ Variation allgemein:• Neue Lösungen werden durch Hinzunahme von

Informationen aus mehr als einer Lösung gefunden:- Differential Evolution- Particle Swarm Optimization


Differential Evolution (1)

§ DE:• Von R. Storn und K. V. Price, 1995

§ Ziel:• Einfaches, effektives Verfahren zur kontinuierlichen

Optimierung• Keine Verwendung von normalverteilten Zufallszahlen zur

Mutation, wie bei ES• Einfache Implementierbarkeit (kein Sortieren der Population)

§ Initialisierung:• Population erhält Zufallslösungen gleichmäßig über

Defintionsraum verteilt


Differential Evolution (2)

§ Variation:• Wähle zu jedem Elternvektor xi∈¡n drei weitere Vektoren aus

der Population xr1, xr2 und xr3

• Erzeuge Mutanten-Vektor v:

1 2 3( )r r rv F x x x= ⋅ − +

,,

, wenn

, sonstj r rand

i ji j

v r C j ju

x

< ∨ ==

• Erzeuge Trial-Vektor ui durch Rekombination von v und xi

§ Selektion:• Wenn ui bessere Fitness hat, wird der Elter xi durch ui ersetzt

r: Zufallszahl in [0,1]jrand: Zufallszahl in 1,..,n

F: Zufallszahl in (0,1.2]


Differential Evolution - Pseudo-Code

procedure DEbegin

Initialisiere P=x1,..,xp; n = 0;repeat

foreach xi in PWähle r1, r2, r3 aus 1,..,pv = mutate(xr1, xr2, xr3);ui = recombine(v, xi);if f(ui) > f(xi) then xi = ui;

end;n = n +1;

until n > nmax;end;

procedure DEbegin

Initialisiere P=x1,..,xp; n = 0;repeat

foreach xi in PWähle r1, r2, r3 aus 1,..,pv = mutate(xr1, xr2, xr3);ui = recombine(v, xi);if f(ui) > f(xi) then xi = ui;

end;n = n +1;

until n > nmax;end;


Differential Evolution - Varianten

§ Varianten der DE:

1 2 3

1 2

1 2 3 4

2 3

3 1 2

DE/rand/1: ( )

DE/best/1: ( )

DE/best/2: ( )

DE/rand-to-best/1: ( ) ( )

DE/current-to-rand/1: ( ) ( )

r r r

r r best

r r r r best

r r best i i

i i r i r r

v F x x x

v F x x x

v F x x x x x

v F x x x x x

u x K x x F x x

λ

= ⋅ − +

= ⋅ − +

= ⋅ + − − +

= ⋅ − + − +

= + ⋅ − + ⋅ −

xbest: Individuum mit höchster Fitness in der Population


Differential Evolution - Variation

§ Vektordarstellung:

xr3

xr2

xr1

(xr1-xr2)

F(xr1-xr2)

v

xi

Kandidaten für ui

xr3

xr1

xr2

(xr1-xr2)

F(xr1-xr2)

xi

ui

K(xr3-xi)

DE/rand/1 DE/current-to-rand/1


Differential Evolution - Übertragbarweit

§ Anwendungen:• Ausschließlich reelwertige Optimierung• Keine Übertragung auf binäre Probleme

§ Permutationsprobleme:

• Verfahren auf TSP, QAP,... nicht so ohne weiteres anwendbar


Differential Evolution - Parameterwahl

§ Parametervorschläge:• Populationsgröße: 5n – 20n (n: Dimension des Suchraums)• CR (Crossover-Wahrscheinlichkeit): 0.8-1.0• F (Mutations-Koeffizient): 0.3-0.9• K (Rekombinations-Koeffizient): 0, 0.5, 1.0


Particle Swarm Optimization (PSO)

§ Idee:• Von J. Kennedy und R. C. Eberhart 1995• Simulation von sozialem Verhalten• Genauer: kollektives Verhalten eines Vogelschwarms

§ Soziales Verhalten:• Individuen wiederholen ihr vorheriges Verhalten• Individuen orientieren sich an Gruppenführern

(Gruppenbesten)


PSO - Population

§ Population:• Menge von Individuen (Partikeln)• Nachbarschaften: Jedes Individuum hat benachbarte

Individuen

§ Individuum: Jedes Individuum besitzt:• Eine aktuelle Position (Lösung des Optimierungsproblems)• Die bisher beste Position (Bisher beste Lösung)• Eine Fluggeschwindigkeit


PSO – Variation (1)

§ Variation:• Anpassung der Geschwindigkeit, Bestimmung einer neuen

Position

1 2 ,

n

,

( ) ( )

: Lösungsvektor - Partikel i

: Geschwindigkeit von Partikel i

:Beste Position von Partikel i

:Position des besten Partikel in der Nachbarschaft von

i i i i best i i

i i i

i

i

i

best i

v v p x p x

x x v

x

v

p

p

ρ ρ= + ⋅ − + ⋅ −

= +

∈ ¡

1 2

i

, [0,2] (gleichverteilte Zufallszahlen)ρ ρ ∈


PSO – Variation (2)

§ Grafische Darstellung:

vi

xi

pbest,i

(pbest,i-xi)

pi

(pi-xi)

xi,neu


PSO - Nachbarschaften

§ Globale Nachbarschaft:• Alle Individuen der Population!

§ 3-er Nachbarschaft:• Bestehend aus Individuum i-1, i, und i+1

§ Selektion:• Nicht vorhanden!• Indirekte Favorisierung guter Lösungen durch Anziehung

des Nachbarschaftsbesten


PSO - Ablauf

§ Berechnungsschritte in PSO:1. Initialisiere Schwarm2. Passe Geschwindigkeiten an3. Bestimme neue Position der Partikel4. Ermittle die Nachbarschaftsbesten5. Bei Konvergenz: Ende, sonst gehe zu 2


PSO – Diskrete Suchräume

§ Lösung ist Binärvektor:• x und p sind Binärvektoren, v reeller Vektor• Anpassung von x mittels v:

,,

,,

1, wenn ( )0, sonst

1mit ( )

1 exp( )

i ji j

i ji j

r S vx

S vv

<=

=+ −

§ Permutationsprobleme:• Verfahren auf TSP, QAP nicht so ohne weiteres anwendbar


PSO – Parameterwahl

§ Geschwindigkeit:• Es ist sinnvoll, die Geschwindigkeit durch |vi|≤vmax zu

begrenzen

§ Parametervorschläge:• Populationsgröße (Individuenanzahl): 20-60• Trade-off mit Anzahl der Iterationen bis zur Konvergenz!• Intervall für ρ‘s: (0,2]• vmax : Proportional zu xmax

• Nachbarschaftsgröße: Wahl zwischen schneller Konvergenz (n) und robusterer Suche (2)


Lernende Optimierungsverfahren

§ „Lernende“ Optimierungsverfahren• Probabilistic Search Meta-Heuristics• Jedem Wert für eine Lösungskomponente wird eine

Wahrscheinlichkeit zugeordnet• Anpassung der Wahrscheinlichkeiten durch Lernregeln• Bestärkendes oder Wettbewerbs-Lernen• Beispiele:

- Bit-simulated Crossover- Population-based Incremental Learning (Competitive Learing)- Ant Colony Optimization (Reinforcement Learning)


Lernende Optimierungsverfahren

§ Ablauf: (für binäre Probleme)

• Kann auf nicht-binäre Probleme übertragen werden

• Die Lernverfahren unterscheiden sich in der Aktualisierung von V

Initialisiere VInitialisiere V

Generiere P mit VGeneriere P mit V

Evaluiere PEvaluiere P

EndeEnde

Aktualisiere V mit PAktualisiere V mit P

Seif: S→¡ mit S=0,1l

V=(p1,...,pl) mit pi ∈ [0,1] P=(s1,...,sn) mit si ∈ S

Seif: S→¡ mit S=0,1l

V=(p1,...,pl) mit pi ∈ [0,1] P=(s1,...,sn) mit si ∈ S


Bit-Simulated Crossover (1)

§ Idee: (Syswerda, 1993)• Simulation von Crossover mit Selektion in GA (BSC)• Jedes Bit si im Binärvektor erhält eine Wahrscheinlichkeit pi

auf 1 gesetzt zu werden (1-pi auf 0 gesetzt zu werden)

( )

( )

is P

i

s P

s w sp

w s∈

∈

⋅=

∑∑

Möglichkeiten: w(s)=1w(s)=f(s)w(s)=n-Rang(s)

• Simulation der Mutation in GA:- Addition/Substraktion von pm von pi


Bit-Simulated Crossover (2)

§ Ablauf:1. Initialisierung von V=(p1,...,pl)=(0.5,0.5,...)2. Erstellung einer Population P von l Lösungen mit

Wahrscheinlichkeitsverteilung V3. Evaluation der Population P4. Neuberechnung von V5. Bei Konvergenz Ende, sonst weiter mit Schritt 2


Population-based Incremental Learning

§ PBIL:• Von S. Baluja, 1994• Inspiriert durch Competitive Learning• Ähnlich zu BSC• Unterschied zu BSC: Update Regel für V• Inkrementelles Lernen, da Wahrscheinlichkeiten pi aus der

Vorgeneration berücksichtigt werden• Nicht alle Lösungen aus P werden zum Update von V

herangezogen


PBIL Update-Regel (1)

§ Update (Variante 1):

,

best

(1.0 )

: Lernrates : Beste Lösung aus

i i best ip p s

P

λ λ

λ

← − ⋅ + ⋅

§ Mutation: (Jedes pi wird mit Wahrscheinlichkeit pm mutiert)

(1.0 )

: Mutationseinfluß: Zufallszahl, 0 oder 1

i ip p r

r

µ µ

µ

← − ⋅ + ⋅


PBIL Update-Regel (2)

§ Graphische Dartellung:

(1.0 ) ( )

(Vektorschreibweise)best bestp p s p s pλ λ λ← − ⋅ + ⋅ = − ⋅ −

p

sbest

sbest-p

λ⋅(sbest-p)


PBIL Varianten (1)

§ Update (Variante 2):• Statt zur besten Lösung aus P wird

Wahrscheinlichkeitsvektor zu besten m Lösungen hingezogen

- Anwendung auf alle Komponenten, Lernrate für alle Lösungen gleich

- Anwendung auf alle Komponenten, Lernrate gewichtet durch Rang der Lösungen

- Anwendung nur auf Komponenten, die in den m Lösungen identisch sind


PBIL Varianten (2)

§ Update (Variante 3):• Zusätzlich zur Anziehung zur Besten erfolgt Abstoßung von

der schlechtesten Lösung aus P• Abstoßung erfolgt indirekt durch Vergleich der schlechtesten

mit der besten Lösung (nur unterschiedliche Komponenten werden betrachtet)

, , ,

worst

(1.0 ) :

: Negative Lernrates : Schlechteste Lösung aus

i i best i best i worst ip p s i s s

P

λ λ

λ

− −

−

← − ⋅ + ⋅ ∀ ≠


PBIL - Ablauf

Initialisierung der piInitialisierung der pi

Erzeuge PErzeuge P

Evaluiere PEvaluiere P

EndeEnde

Mutation der piMutation der pi

Update der piUpdate der pi


PBIL im Vergleich

§ PBIL Parameter:• Populationsgröße: 100• λ=0.1, λ-=0.075, Pm=0.02, µ=0.05

§ Ergebnisse:• Von Baluja, 1994• PBIL2 (λ->0) besser als PBIL• Wahl von λ- problemabhängig (Getestet: 0.025, 0.075, 0.1)• PBIL besser oder vergleichbar mit GA


Ameisenkolonien (1)

§ Idee:• Von M. Dorigo, 1992• Verhalten von Ameisen bei der Futtersuche• Ameisen hinterlassen Pheromon-Spur (Chem. Substanz)• Pfade mit hoher Pheromon-Konzentration werden bevorzugt• Indirekte Kommunikation durch Pheromone• Ameisen lösen kollektiv das Problem des kürzesten Pfades

§ Reale Ameisen:• Idee basierend auf Experimenten von Goss et al. 1989 mit

argentinischen Ameisen


Ameisenkolonien (2)

§ Kürzeste Pfade:• Kollektives Finden des kürzesten Pfades vom Futter zum Nest bei

vorhanden sein eines Hindernisses

Nest Nahrung

Hindernis

Nest Nahrung

Hindernis

Nest Nahrung

Hindernis

Nest Nahrung

1 2

3 4


Ameisenkolonien (3)

§ Historische Entwicklung:• Ant System – AS

(M. Dorigo, 1992)• Ant Colony System – ACS

(M. Dorigo und L. M. Gambardella, 1997)• Ant Colony Optimization Meta-Heuristic – ACO

(Dorigo und DiCaro, 1999)

• AS und ACS:• Ursprünglich entwickelt fürs TSP• Übertragen auf viele weitere COP


Ant System fürs TSP

§ Ant Sytem fürs TSP:• Ameisen konstruieren Touren• Kanten mit höherer Pheromon-Konzentration τ werden mit höherer

Wahrscheinlichkeit gewählt

?

• Jede Ameise hinterlegt Pheromonspur nachdem Tour komplett ist• Hinterlegte Pheromonmenge ist umgekehrt proportional zur Länge

der Tour der Ameise• Duftspur verflüchtigt sich mit der Zeit

τ(s,t)t

s

u

v

rτ(s,r)

τ(s,u)τ(s,v)


Ant Sytem - Übergangsregel

§ Ant System fürs TSP:• Ameisen sind Tour-Konstruktoren: Jede Ameise erzeugt eine

Tour• Wahrscheinlichkeit für Ameise k von Stadt r nach s zu

gehen:

( )

k

(r,s) (r,s), wenn ( )

(r,u) (r,u)( , )

0, sonst

: Pheromon-Konzentration( , ) 1/ ( , ) : Heuristische Information

J ( ) : Menge der noch nicht besuchten Städte

k

k

k u J r

s J rp r s

r s d r sr

β

β

τ ητ η

τη

∈

⋅∈ ⋅=

=

∑


Ant System – Update-Regel

§ Globale Lernregel:• Pheromon-Update:

1

( , ) (1 ) ( , ) ( , )

1, wenn( , )

( , )

0, sonst

:Tour von Ameise

:Länge der Tour von Ameise

: Verflüchtigung der Pheromone

m

kk

kkk

k

k

r s r s r s

r s TLr s

T k

L k

τ α τ τ

τ

α

=

← − ⋅ + ∆

∈∆ =

∑


Ant Colony System – Übergangsregel

§ State Transition Rule:• Pseudo-zufälliger Zustandsübergang:

( ) 0

0

k

argmax ( , ) ( , ) , wenn

S, sonst

:Zufallsvariable gleichverteilt in [0,1]:Explorationsparameter

: Zufallsvariable nach p ( , ) aus AS

ku J r r u r u q qs

qq

S r s

βτ η∈ ⋅ ≤=


Ant Colony System – Update-Regeln (1)

§ Globale Lernregel:• ACS Global Update Rule:

( , ) (1 ) ( , ) ( , )

1, wenn( , )

( , )

0, sonst

: Tour der besten Ameise

: Länge der besten Tour

: Verflüchtigung der Pheromone

bestbest

best

best

r s r s r s

r s TLr s

T

L

τ α τ α τ

τ

α

← − ⋅ + ⋅ ∆

∈∆ =


Ant Colony System – Update-Regeln (2)

§ Lokale Lernregel:• ACS Local Update Rule:

( )

0

0

( , ) (1 ) ( , ) ( , )

( , ) max ( , ) (Variante 1)

( , ) (Variante 2)( , ) 0 (Variante 3)

: Parameter (0,1]: Q-Learning Parameter [0,1):Initialer Pheromonlevel

kz J s

r s r s r s

r s s z

r sr s

τ ρ τ ρ τ

τ γ τ

τ ττ

ργτ

∈

← − ⋅ + ⋅ ∆

∆ = ⋅

∆ =∆ =

∈∈


ACS - Pseudocode

Procedure ACS-TSP;

beginInitialisierung;repeat

Jede Ameise wird in einem Startknoten positioniertrepeat

foreach Ameise do Ameise wendet Zustandsübergangsregel anAmeise wendet lokale Update-Regel an

endforeach;until Lösungen komplett;Globale Update-Regel wird angewendet

until Ende-kriterium;end;

Procedure ACS-TSP;

beginInitialisierung;repeat

Jede Ameise wird in einem Startknoten positioniertrepeat

foreach Ameise do Ameise wendet Zustandsübergangsregel anAmeise wendet lokale Update-Regel an

endforeach;until Lösungen komplett;Globale Update-Regel wird angewendet

until Ende-kriterium;end;


ACS - Parameterwahl

§ Parameter:• Einfluss der heuristischen Information β=2• Exploration q0=0.9• Pheromon-Evaporation α=ρ=0.1• Initialer Pheromonwert τ0 = 1/(n·Lnn)

Lnn: Länge der Lösung der Nearest-Neighbor-Heuristik• Anzahl Ameisen: m=10


ACS - Varianten

§ Ergebnisse eines Vergleichs:• ACS mit lokalem Update besser als ohne• Lokales Update: Variante 1 und 2 besser als Variante 3• Heuristische Information wichtig à β>0• Igonorieren der Pheromonwerte à schlechte Performance• ACS im Vergleich zu anderen Meta-Heuristiken relativ

schlecht à Verwendung lokaler Suche

§ ACS + 3-opt (TSP):• 3-opt lokale Suche vor globalem Update• Ergebnisse deutlich besser, aber schlechter als MA

(1st International Contest on Evolutionary Optimization)


Min-Max Ant System

§ Idee:• Von Stützle und Hoos, 1997• Verbesserung des AS

§ Unterschiede zu AS:• Nur beste Ameise (global Beste oder Iterationsbeste) darf

Pheromonspur aktualisieren• Pheromonwerte werden auf ein Intervall [τmin,τmax] festgelegt• Pheromonwerte werden mit τmax initialisiert• Verwendung von lokaler Suche


Fast Ant System

§ FANT: (QAP)• Von Taillard und Gambardella, 1997• Nur eine Ameise• Lokale Suche nach Konstruktion einer Lösung• Pheromone verflüchtigen sich nicht• Pheromonwerte werden mit 1 initialisiert• Pheromon-Update:

: 1, wenn ( , ) Element der aktuellen Lösung ist

: 1, wenn ( , ) Element der besten Lösung ist, : Parameter

gbij ij ij ij

ijgbij

r r

i j

i jr r

τ τ τ τ

ττ

∗

∗

← + ⋅ ∆ + ⋅ ∆

∆∆


Ant Colony Optimization

§ ACO Meta-Heuristik:• Von Dorigo und DiCaro, 1999• Verallgemeinerung des ACS• Framework erlaubt Integration von lokaler Suche

§ Anwendung:• Diskrete Optimierungsprobleme (kombinatorische

Optimierungsprobleme) mit bestimmten Eigenschaften àProblemdarstellung als Graph, Wahl einer

Lösungskomponente wird durch Kante im Graph dargestellt


ACO – Optimierungsprobleme (1)

§ Voraussetzungen:• Endliche Menge C von Komponenten C=c1,c2,...,cn • Endliche Menge L von möglichen Verbindungen/Übergängen

zwischen den Elementen von C, L=lij | (i,j) ∈ C x C, |L|≤n2

• Für jedes lij ∈L Verbindungkosten Jij(lij,t), möglicherweise zeitabhängig

• Eine endliche Menge von Nebenbedingungen Ω(L,C,t)


ACO – Optimierungsprobleme (2)

§ Weitere Voraussetzungen:• Die Zustände des Problems ausgedrückt als Sequenzen

s=<ci,cj,...,ck> über den Elementen von C, S sei die Menge aller möglichen Sequenzen und S* die Menge der gültigen Sequenzen bezüglich Ω(L,C,t)

• Eine Nachbarschaftsstruktur, d.h. s1 und s2 sind Nachbarn, wenn s1=<...,c1> und s2=<s1,c2> ∈ S, c1, c2 ∈ C und lc1,c2 ∈ L

• Eine Lösung x ∈ S* mit einer Kostenfunktion f(x,L,t)abhängig von den Kosten lij der Lösung


ACO – Problembespiele (1)

§ Aufgabe:• Pfad im Graphen G=(C,L)

§ Beispiel TSP:• C : Menge der Städte / Knoten• L : Menge der Verbindungen / Kanten• Verbindungkosten Jij(lij,t) = dij

• Ω(L,C,t) : Jede Stadt darf nur einmal besucht werden• Die Zustände des Problems: Städtefolge s=<ci,cj,...,ck>• Eine Nachbarschaftsstruktur: alle Städte sind benachbart • Lösung x ∈ S*: gültige Tour• Kostenfunktion f(x,L,t): Tourlänge


ACO – Problembespiele (2)

§ Beispiel binäres Problem:• Schrittweises Festlegen der Bits von links nach rechts• Graph:

SS00

11

00

11

00

11

00

11

00

11EE

00 11 11 00 00Lösung:


ACO - Datenstrukturen

§ Gedächtnis M:• Jede Ameise hat ein Gedächtnis• Wichtig für Erzeugung gültiger Lösungen• Verwendet zur Evaluation einer Lösung• Benötigt zum Rückverfolgen des Pfades

§ Routing-Tabelle A:• Gewichtet Kanten im Graph durch Kombination der

Pheromonkonzentration und der heuristischen Information• Benötigt zur Berechnung der

Zustandsübergangswahrscheinlichkeiten


ACO - Pseudocode

procedure ACO;

beginrepeat

scheduleantsGenerationAndActivity();pheromoneEvaporation();daemonActions();

end schedule;until Ende-kriterium;

end;

procedure antsGenerationAndActivity;

beginrepeat

scheduleCreationNewAnt();newActiveAnt();

until noResources();end;

procedure ACO;

beginrepeat

scheduleantsGenerationAndActivity();pheromoneEvaporation();daemonActions();

end schedule;until Ende-kriterium;

end;

procedure antsGenerationAndActivity;

beginrepeat

scheduleCreationNewAnt();newActiveAnt();

until noResources();end;

procedure newActiveAnt;

begininitializeAnt();M = updateAntMemory();repeat

A = readLocalAntRoutingTable();P = computeTransitionProbabilities(A,M,Ω);nextState = applyAntDecisionPolicy(P, Ω);moveToNextState(nextState);if (onlineStepByStepPheromoneUpdate())

depositPheromoneOnVisitedArc();updateAntRoutingTable();

end if;M = updateInternalState();

until currentState == targetState;if (onlineDelayedPheromoneUpdate())

foreach arc in x dodepositPheromoneOnVisitedArc();updateAntRoutingTable();

end foreach;endif;

end;

procedure newActiveAnt;

begininitializeAnt();M = updateAntMemory();repeat

A = readLocalAntRoutingTable();P = computeTransitionProbabilities(A,M,Ω);nextState = applyAntDecisionPolicy(P, Ω);moveToNextState(nextState);if (onlineStepByStepPheromoneUpdate())

depositPheromoneOnVisitedArc();updateAntRoutingTable();

end if;M = updateInternalState();

until currentState == targetState;if (onlineDelayedPheromoneUpdate())

foreach arc in x dodepositPheromoneOnVisitedArc();updateAntRoutingTable();

end foreach;endif;

end;


QAP: ACO und andere Meta-Heuristiken

§ QAP: Vergleich Meta-HeuristikenZahlen: Abweichung von besten Lösung in %

Instanz MA-1 MA-2 Ro-TS Re-TS FANT MMAS SA t/sectai60a 1.314 1.597 1.313 0.794 2.577 1.159 3.199 90tai80a 1.106 1.305 1.023 0.482 2.525 0.768 3.298 180tai100a 1.089 1.252 0.909 0.385 2.569 0.728 1.848 300sko100a 0.096 0.127 0.191 0.397 0.474 0.195 2.942 300tai60b 0.000 0.000 1.898 0.929 0.213 0.075 1.760 90tai80b 0.191 0.004 2.929 1.602 0.821 0.718 5.092 180tai100b 0.076 0.038 2.373 1.469 0.360 0.328 6.696 300tai150b 0.361 0.397 2.851 1.775 1.176 1.167 3.787 600tho150 0.151 0.202 0.548 0.488 0.765 0.395 2.939 600tai256c 0.070 0.099 0.326 0.266 0.273 0.067 0.370 1200

Ro-TS, Re-TS: Robust/Reactive Tabu SearchFANT, MMAS: Ant Colony Optimization: Fast Ant System, Min-Max Ant SystemSA: Simulated Annealing


Konstruktions-Verbesserungsheuristiken

§ Idee:• 2-Phasen-Suche• 1. Phase: Randomisierte

Konstruktionsheuristik• 2. Phase: Lokale Suche

§ Beispiele:• Multi-Start lokale Suche• GRASP: Greedy Randomized

Adaptive Search Procedure (Feo und Resendre, 1995), ohne Gedächtnis

• ACS+LS, verwendet Gedächtnis (h)

Initialisiere(h)Initialisiere(h)

s = konstruiere(h)s = konstruiere(h)

s* = lokaleSuche(s, h)s* = lokaleSuche(s, h)

EndeEnde


Iterierte lokale Suche (ILS)

§ ILS:• Idee von mehreren Wissenschaftlern unabhängig von

einander verfolgt à Viele Namen:- Iterated Descent (Baum, 1986)- Large Step Markov Chains (Martin, Otto, Felten, 1991)- Iterated Lin-Kernighan (Johnson, 1990)- Chained Local Optimization (Martin und Otto, 1996)

• Weiterentwicklungen:- Reactive Search (Battiti und Protasi, 1997)- Variable Neighborhood Search (Hansen und Mladenovic, 1998)


ILS - Ablauf

§ Initialisierung:• Zufallslösung oder

heuristische Lösung

§ Perturbation:• Zufällig (Mutation) • Oder deterministisch• Verwendung eines

Gedächtnisses (h : history)

§ Akzeptanzkriterien:• Nur bessere Lösungen• Nach Wkeitsverteilung• Mit Hilfe des

Gedächtnisses

s0 = erzeugeStartLösungs0 = erzeugeStartLösung

s‘ = perturbation(s*, h)s‘ = perturbation(s*, h)

s*‘ = lokaleSuche(s‘)s*‘ = lokaleSuche(s‘)

EndeEnde

s* = lokaleSuche(s0)s* = lokaleSuche(s0)

s* = akzeptiere(s*, s*‘, h)s* = akzeptiere(s*, s*‘, h)


ILS – Akzeptanzkriterien (1)

§ Nur bessere Lösungen:• Häufig verwendet• Lokale Meta-Suche

* ', wenn ( * ') ( *)( *, * ', )

*, wenn ( * ') ( *)s f s f s

best s s hs f s f s

<=

≥

( *, * ', ) * 'rw s s h s=

§ Random Walk:• Immer neue Lösung s*‘ akzeptieren• Zufällige Meta-Suche

(Im folgenden: Minimierung)



§ LSMC:• Bessere Lösungen akzeptieren• Schlechtere Lösungen mit geringer Wahrscheinlichkeit

akzeptieren à Metropolis-Kriterium• Simulated Annealing Meta-Suche

( )( *) ( *') /* ', wenn ( * ') ( *)( *, * ', )*, sonst

: Annealing Temperatur: Zufallszahl zwischen 0 und 1

f s f s Ts f s f s r elsmc s s hs

Tr

− < ∨ <=



§ Restart:• Bessere Lösungen akzeptieren• Wenn seit ∆ir Iterationen keine Verbesserung, erzeuge

neue Lösung

r

* ', wenn ( * ') ( *)( *, * ', ) ( *, ), wenn ( * ') ( *) -

* sonst

: aktuelle Iteration: Letze Iteration mit besserer Lösung

i : restart-Parameter

last r

last

s f s f srestart s s h new s h f s f s i i i

s

ii

<= ≥ ∧ > ∆

∆


ILS - Pertubation

§ Ziel:• Suche eines nahe gelegenen lokalen Optimums• Verlassen des Attraktionsgebietes des aktuellen lokalen

Optimums

§ Mögliche Vorgehensweise:• Perturbation kann über Nachbarschaften definiert werden• Auswahl aus Nachbarschaft zufällig oder deterministisch• Nachbarschaft der lokalen Suche und der Perturbation

disjunkt à Wähle s∈Npert mit Nls ∩ Npert =∅


Variable Neighborhood Search

§ Idee:• Von Hansen und Mladenovic, 1998• VNS und ILS sind ähnlich• Dynamische Änderung der Nachbarschaften der lokalen

Suche• Wie ILS mit schrittweiser Veränderung der

Pertubationsnachbarschaft N1, N2, N1 ,..., Nkmax

• Akzeptanzkriterium: Akzeptanz besserer Lösungen


Variable Neighborhood Search

§ Ablauf VNS:

Procedure VNS;

begins = konstruiereLösung();k = 1;repeat

wähle zufällig s‘ ∈ Nk(s);s* = lokaleSuche(s‘);if f(s*) < f(s) then

s = s*;k = 1;

elsek = k + 1;

endifuntil k > kmax;

end;

Procedure VNS;


wähle zufällig s‘ ∈ Nk(s);s* = lokaleSuche(s‘);if f(s*) < f(s) then

s = s*;k = 1;

elsek = k + 1;

endifuntil k > kmax;

end;


VNS - Varianten

§ VNDS:• Variable Neighborhood Decomposition Search• Wie VNS, aber eingeschränkte lokale Suche• Einschränkung erfolgt durch fixieren von Attributen

(Lösungskomponenten)• Drastische Laufzeitreduktion möglich à nötig bei großen

Problem-Instanzen

§ VND:• Variable Neighborhood Descent• Lokale Suche mit variierter Nachbarschaft


Variable Neighborhood Descent

§ Ablauf VND:

Procedure VND;


Finde bestes s* ∈ Nk(s);if f(s*) < f(s) then

s = s*;else

k = k + 1;endif

until k > kmax;end;

Procedure VND;


Finde bestes s* ∈ Nk(s);if f(s*) < f(s) then

s = s*;else

k = k + 1;endif

until k > kmax;end;


Scatter Search

§ Idee:• Von Glover 1968, 1998• Meta-Heurisitik, sehr allgemein gehaltenes Template• Gewichtung von Nebenbedingungen und Kombination zur

Erzeugung neuer Nebenbedingungen –Surrogate Constraints

• Neue Lösungen werden durch Kombination von Lösungen aus einer Referenzmenge erzeugt

àpopulationsbasierter Ansatz ähnlich zu evolutionären Algorithmen bzw. memetischen Algorithmen


Scatter Search Phasen

1. Phase: Erzeugung einer Referenzmenge• Erzeugung einer Initialen Menge an Lösungen• Verbesserung der Lösungen (lokale Suche, Tabu

Search,...)• Die besten Lösungen ergeben die Referenzmenge unter

Berücksichtigung der Diversität

2. Phase: Scatter Search Evolution• Erzeuge systematisch neue Lösungen durch Kombination

mehrerer Lösungen• Gewährleistung der Gültigkeit der Lösungen durch Rundung• Verbessung der Lösungen wie oben• Aktualisierung der Referenzmenge


Scatter Search Template (1)

1. Diversification Generation Method:• Aus einer Lösung werden mehrere Kandiatenlösungen

erzeugt

2. Improvement Method:• Verbesserungsheuristik: Lokale Suche, Tabu Search

3. Reference Set Update Method:• Methode/Strategie zum Hinzufügen und Löschen von

Lösungen aus der Referenzmenge• Größe der Menge (z.B. b=20) soll konstant gehalten werden


Scatter Search Template (2)

4. Subset Generation Method:• Auswahl von Teilmengen der Referenzmenge zur

Lösungskombination

5. Solution Combination Method:• Kombination mehrer Lösungen zu einer Lösung


Scatter Search Ablaufschema

Erzeuge Startlösung(en)Erzeuge Startlösung(en)

ImprovementImprovement

Reference Set UpdateReference Set Update

Diversification GeneratorDiversification Generator Solution CombinationSolution Combination

ImprovementImprovement

Subset GenerationSubset Generation

Reference Set UpdateReference Set Update

EndeEnde

Phase I Phase II


Scatter Search vs. Memetische Algorithmen

§ Begriffe:• Referenzmenge = Population• Improvement = Lokale Suche• Reference Set Update = Überlebensselektion• Subset Generation = Variationsselektion• Solution Combination = Rekombination (Multi-Parent)

§ Wichtigste Unterschiede:• Deterministisch vs. Zufallsgesteuert• Vollständige, systematische Kombination

(erst alle Paare dann alle 3er Kombinationen, usw.)vs. zufällige oder fitnessbasierte Selektion


Scatter Search Methoden (1)

§ Diversifikation:• Beispiel binäres Problem f: S→¡ mit S=0,1l

• Startlösung x=(0,...,0)

1 1

1 1

1

1 1,..., /

1 1,...,hk hk

i i

x x

x x k n h

x x i n+ +

′ = −′ = − ∀ =′′ ′= − ∀ =

§ Improvement:• 1-opt lokale Suche (single bit-flip)



§ Referenzmengen Update:• Unterteilung in zwei Mengen• Menge B der sehr guten Lösungen und• Menge D der sich stark unterscheidenden Lösungen• Hinzufügen zu Menge B, wenn Fitness besser als

schlechteste Lösung der Menge B ist• Hinzufügen der Lösung, die die minimale Distanz zu einer

Lösung der Menge D maximiert



§ Teilmengen-Erzeugung:• Alle 2-elementigen Teilmengen• 3-elementige Teilmengen durch Hinzunahme der besten,

nicht enthaltenen Lösung zu allen Paaren• 4-elementige Teilmengen durch Hinzunahme der besten,

nicht enthaltenen Lösung zu 3-elementigen Teilmengen• Alle Teilmengen der i besten Lösungen von 5 bis zur Größe

der Referenzmenge



§ Lösungskombination:• Für jede Lösungskomponente (jedes Bit) wird ein score

berechnet

,( )( )

( )

1, wenn ( ) 0.50, sonst

: Lösungen/Teilmenge für Kombination

j j ij R

jj R

i

f x xscore i

f x

score ix

R

∈

∈

⋅=

>′ =

∑∑


Scatter Search und Path Relinking (1)

§ Lösungskombination:• Kann aufgefasst werden als finden eines Punktes auf dem

Pfad von einer zur anderen Lösung• Verallgemeinerbar auf m Lösungen

§ Path Relinking:• Erzeugen von Pfaden zwischen Lösungen und darüber

hinaus• Lösungen auf einem Pfad können zur Erzeugung weiterer

Pfade herangezogen werden• Pfade werden über die Nachbarschaftsstruktur der

Suchlandschaft definiert


11 00 11

11 00 11

11 00 11

11 00 11

11 00 11

Scatter Search und Path Relinking (2)

§ Path RelinkingVorgehen:• Nachbarschaftssuche durch

schrittweise Einfügen von Lösungskomponenten anderer Lösungenà Transformation einer Lösung in die andere

• Pfad ist von der Nachbarschaftssuche besuchte Sequenz von Lösungen

11 00 00 11 11 00 00 11 00 11

11 11 00 00 11 00 11

11 11 11 00 11 00 11

00 11 11 00 11 00 11

00 11 11 00 11 00 00

00 11 11 11 11 00 00

Beispiel: Binäre Kodierung


Übersicht Metaheuristiken (1)

Local SearchLocal Search

Simulated AnnealingSimulated Annealing Tabu SearchTabu Search

Threshold AcceptingThreshold Accepting

Multi-Start Local SearchMulti-Start Local Search

Iterated DescentIterated DescentGRASPGRASP

Iterated Local SearchIterated Local Search

Ant Colonies + LSAnt Colonies + LS

Variable Neighborhood SearchVariable Neighborhood Search Large Step Markov ChainsLarge Step Markov Chains

Grand DelugeGrand Deluge



Evolutionary AlgorithmsEvolutionary Algorithms

Genetic AlgrorithmsGenetic AlgrorithmsEvolution StrategiesEvolution Strategies

Genetic ProgrammingGenetic Programming

Evolutionary ProgrammingEvolutionary Programming

Hybrid GAsHybrid GAs

Memetic AlgorithmsMemetic Algorithms

Local SearchLocal Search

Scatter SearchScatter Search

Tabu SearchTabu Search



Evolutionary AlgorithmsEvolutionary Algorithms

Probabilistic Learning Probabilistic Learning Differential EvolutionDifferential Evolution

P-based Incremental LearningP-based Incremental Learning

Particle Swarm OptimizationParticle Swarm Optimization

Bit-Simulated Crossover EABit-Simulated Crossover EA

Ant Colony SystemAnt Colony System

Ant SystemAnt System

Bayesian OptimizationBayesian OptimizationLocal SearchLocal Search

Ant Colony OptimizationAnt Colony Optimization

COMITCOMIT MIMICMIMIC


Clustering

§ Clustering:• Gruppierung und Einteilung einer Datenmenge nach

ähnlichen Merkmalen• Unüberwachte Klassifizierung (Neuronale Netze-

Terminologie)• Distanzkriterium: Ein Datenvektor ist zu anderen

Datenvektoren seiner Gruppe nahe (näher als zu Vektoren anderer Gruppen

• k-Clustering: Clustern einer Datenmenge in k Gruppen• Viele Clusterungsprobleme sind NP-hart!


Clustering

§ Beispiel:

×

×

×

Cluster-Zentrum

Cluster 2

Cluster 3

Cluster 1


Genexpression (1)

§ Genexpression:• Biosynthese eines Genprodukts

(Umsetzung der genetischen Information in Proteine) • IdR. Transkription von DNA zu mRNA und anschließender

Translation von mRNA zu Protein.

§ Experimentelle Mikrobiologie:• Experimentelle Bestimmung der Expression von Genen• Microarray-Technologie: Viele Gene können gleichzeitig

untersucht werden (>10000)• cDNA Microarrays: komplementäre DNA


Genexpression (2)

§ cDNA-Microarrays:• Glasscheibe mit mehreren tausend regelmäßig

angeordneten Feldern (Spots)• Jeder Spot enthält cDNA eines bestimmten Gens• Ziel mRNA wird markiert• Alle nicht hybridisierten Targets

werden abgewaschen• Lichtintensität wird anschließend

gemessen• Intensität spiegelt

Expressionslevel wieder


Genexpression (3)

§ Biologische Fragestellungen:• Welche Funktionen haben die einzelnen Gene und in

welchen zellulären Prozessen sind sie beteiligt?• Wie werden Gene reguliert, wie interagieren Gene und

Genprodukte? Wie sind die Interaktionsnetzwerke aufgebaut?

• Wie unterscheiden sich die Expressionslevel in verschiedenen Zelltypen und Zuständen?


Genexpressionsanalyse

§ Aufgabenstellung:• Datenanalyse, Data Mining• Dimensionsreduktion und Visualisierung• Finden von Gruppen co-regulierter Gene, funktional

zusammenhängender Gene

§ Lösung:• Clusteranalyse, Clustering der Gene

§ Algorithmen:• Hierarchisches Clustern• Self-organizing maps (SOMs)• Hauptkomponentenanalyse (PCA)• K-Means, ...


Minimum Sum of Squares Clustering

§ MSSC:• NP-hartes kombinatorisches Minimierungsproblem

2 2( )

1 1

ˆ ˆmin ( , ) ( , )

1ˆmit | |

und 1,..., | ( )

, 1,..., : Eingabevektoren der Dimension : zu Cluster zugeordnete Vektoren

: 1,.., 1,..., : Zuordn

i

i

K n

p i j p i ii j C i

i jj Ci

i

mi

i

d x x d x x

x xC

C j n p j i

x i n n mC ip n k

= ∈ =

∈

=

=

= ∈ =

∈ =

→

∑ ∑ ∑

∑

¡

ung von Vektor zu Cluster


Der k-Means Algorithmus

§ k-Means:• Wiederholtes Zuweisen der

Inputvektoren zu Clustern und Neuberechnung der Clusterzentren

• Zuweisen durch Bestimmung des Zentrums mit geringstem Abstand

• Abbruchkriterium: Clusterzentren haben sich nicht geändert

• Konvergiert gegen lokales Optimum der MSSC Zielfunktion

Wähle ClusterzentrenWähle Clusterzentren

Neuberechnung der Clusterzentren

Neuberechnung der Clusterzentren

EndeEnde

Zuordnung Vektoren zu Clustern

Zuordnung Vektoren zu Clustern


Memetische Algorithmen fürs MSSC

§ Wichtige Schritte:• Bestimmung der Zielfunktion• Bestimmung der Repräsentation von Lösungen• Wahl der lokalen Suche• Entwicklung eines Mutationsoperators• Entwicklung eines Rekombinationsoperators



§ Bestimmung der Zielfunktion:• MSSC Funktion

§ Bestimmung der Repräsentation von Lösungen:• Abbildung p kann so kodiert werden:

2( )

1

ˆ( ) ( , )n

p i ii

f p d x x=

= ∑

11 33 22 11 11 33 33 22 22 11 22 33 22 11 11 33 11 22 33 11

Vektor 1 wird Cluster 1 zugewiesen

Vektor 2 wird Cluster 3 zugewiesen

p :

• Clusterzentren können aus p berechnet oder gespeichert werden à Werden in MA gespeichert



§ Wahl der lokalen Suche:• K-Means, Input: k Clusterzentren

§ Mutationsoperatoren:• Operator MM:

- Ein zufällig gewählter Vektor wird als Clusterzentrum für ein zufällig gewähltes Cluster herangezogen

• Operator FM:- Zwei Cluster i und j werden zufällig gewählt- Der Vektor mit der größten Distanz zum Mean von Cluster i

wird als Clusterzentrum (mean) von Cluster j verwendet



§ Rekombinationsoperatoren:• Operator UX (uniform Crossover):

- Die Mean-Vektoren werden mit gleicher Wahrscheinlichkeit von den beiden Eltern gewählt

• Operator RX:- Mean-Vektoren in Elter a werden durch Mean-Vektoren von

Elter b ersetzt- Mean-Vektoren aus überrepräsentierten Bereichen sollen

gelöscht werden- Mean-Vektoren sollen zu unterrepräsentierten Bereichen

hinzugefügt werden


MSSC: RX Rekombination

§ Rekombinationsoperator RX:

a1a1 a2

a2 a3a3 a4

a4 a5a5 a6

a6 a7a7 a8

a8 a9a9 a10

a10Elter a:

b1b1 b2

b2 b3b3 b4

b4 b5b5 b6

b6 b7b7 b8

b8 b9b9 b10

b10Elter b:

Discard List:a2a2 a5

a5 a7a7 a10

a10

Split List:a3a3 a6

a6 a8a8

a1a1 b4

b4 a3a3 a4

a4 b6b6 a6

a6 b3b3 a8

a8 a9a9 a10

a10Kind:Gewählte Paare:(a3,a2) (a8,a5) (a6,a7)

bi : aj ist nächster Mean-Vektor zu bi aj


Clustering - Distanzen zwischen Lösungen

§ Distanzen:• Wichtig, wenn man Lösungen von Clusterungsalgorithmen

vergleichen will• Wichtig für Fitnesslandschaftsanalyse

§ Vorschlag 1:• Center-Distanz:

• Nachteil: Abhängig vom MSSC-Kriterium, schwer interpretierbar

( ) ( )1

ˆ ˆ( , ) ( , )n

p i q ii

D p q d x x=

= ∑


Clustering - Distanzen zwischen Lösungen

§ Ziel:• Zählen, der Vektoren die unterschiedlich zugeordnet wurden

§ Vorschlag 2:• Matching:

Ordne Cluster von Lösung A Clustern von Lösung B zu• Zuordnung über Clusterzugehörigkeit• Zähle die gemeinsamen Vektoren der zugeordneten Cluster


Clustering – Matching & Distanzberechnung

§ Matching:• Zähler = 0• Für jedes Cluster i aus Lösung A:

- Finde Cluster j aus Lösung B mit den meisten Vektoren aus i- Finde Cluster k aus Lösung A mit den meisten Vektoren aus j- Wenn i=k, erhöhe Zähler um Anzahl der gemeinsamen

Vektoren

• Distanz = Anzahl Vektoren - Zähler


Clustering – Matching & Distanzberechnung

§ Illustration:

a1a1 a2

a2 a3a3 a4

a4 a5a5 a6

a6 a7a7 a8

a8 a9a9 a10

a10Lösung A:

b1b1 b2

b2 b3b3 b4

b4 b5b5 b6

b6 b7b7 b8

b8 b9b9 b10

b10Lösung B:

94 3

9 7 0 8 10 14 0 5 7 2

7 8 10 14 2 75

+ + ++++++ + = 62Gemeinsame Vektoren:


MSSC – Fitness-Distanz-Korelation

§ Verteilung der k-Means Lösungen:

Matching, FDC: 0.59 Center-Distanz, FDC: 0.66


Genexpressionsanalyse mit MA (1)

§ Clusterung der Expressionsdaten• Minimum-Sum-Of-Squares Clustering (NP-Hart)• Minimierung des Abstandes zum Repräsentanten eines

Clusters• MA mit k-Means lokaler Suche• Genexpressionsuntersuchung:

- Expression von 6565 Genen über 2 Zellzyklen (Messung an 17 Zeitpunkten)

- 2 Zeitpunkte wurden eliminiert à Expressionsmuster sind Zeitreihen aus 15 Punkten

- Variationsfilter reduziert Datensatz auf 2931



§ Ergebnisse Vergleich MA-Operatoren:• Oben: zuvor beschriebene Daten, unten: zufällig erzeugte

Daten mit bekanntem Optimum

Alg. Gen Nr. LS Iter LS Best Avg. Obj. Error

MLS 2000.0 74632.5 16966.7 816984.32 0.46%MA-UX 100 2000.0 51371.7 16908.3 216933.44 0.16%MA-RX 98 1979.0 12475.9 16907.0 616916.60 0.06%MA-FM 100 2000.0 34405.5 16912.6 116924.54 0.10%MA-MM 100 2000.0 35784.3 16909.0 916919.03 0.07%


Alg. Gen Nr. LS Iter LS Best Avg. Obj. Error





§ Ergebnisse:• Vergleich zu einfachem k-Means:• Zuordnung der Gene zu den

Clustern stark unterschiedlich!• Gene in MA-Cluster 14 verteilen

sich auf 5 k-Means-Cluster: 1(5 Gene), 5(3 Gene), 15(36 Gene), 22(4 Gene), 23(40 Gene)

MA

k-Means

Documents

Moderne Heuristische Optimierungsverfahren · • Tabu Search. Folie 5 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Inhalte der Vorlesung (2) §Fitnesslandschaften