View
3
Download
0
Category
Preview:
Citation preview
Planung und Optimierung mit evolutionären Verfahren
K1: Ausgewählte Grundlagen der Optimierung
1
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 1 1
Ausgewählte
Grundlagen der Optimierung
Eigenschaften von Optimierungsproblemen und Suchräumen
formale Definition eines Optimierungsproblems
Komplexität
Mehrzieloptimierung
Typen von Optimierungsverfahren
gängige Optimierungsverfahren
No-free-Lunch-Theoreme
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 2 2
Grundlagen der Optimierung - Eigenschaften
Eigenschaften von Optimierungsproblemen und Suchräumen
Eigenschaften:
ein Optimum, unimodal
keine Lücken im Definitionsbereich
(keine impliziten Beschränkungen)
stetig
differenzierbar
einfach
Eigenschaften:
viele Optima, multimodal
keine Lücken im Definitionsbereich
(keine impliziten Beschränkungen)
stetig
wahrscheinlich differenzierbar
schwieriger
Planung und Optimierung mit evolutionären Verfahren
K1: Ausgewählte Grundlagen der Optimierung
2
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 3 3
Grundlagen der Optimierung - Eigenschaften
Beschränkte und unstetige Funktionen
zwei Beschränkungen
im Definitionsbereich
Bereich mit Unstetigkeiten und
nur schwacher Kausalität
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 4 4
Grundlagen der Optimierung - Eigenschaften
Weitere Eigenschaften von Optimierungsproblemen:
Wertebereich:
kontinuierlich
diskret (ganze Zahlen, Eigenschaften wie oben, unten, mittig, …)
gemischt (gemischt-ganzzahliger Wertebereich)
Typ:
Parameteroptimierung
kombinatorische Optimierung
Kombination aus beidem
Planung und Optimierung mit evolutionären Verfahren
K1: Ausgewählte Grundlagen der Optimierung
3
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 5 5
Grundlagen der Optimierung – Definitionen
Formale Definition eines Optimierungsproblems
Einfacher Fall: eindimensionale Funktion 𝑭: 𝒙 → ℝ, 𝒙 ∈ ℝ
Gesucht ist ein 𝒙𝒐𝒑𝒕 ∈ ℝ
für das gilt: ∀𝒙 ∈ ℝ: 𝑭 𝒙 ≤ 𝑭 𝒙𝒐𝒑𝒕 = 𝑭𝒐𝒑𝒕
Allgemeiner Fall:
n-dimensionale auf beliebige Mengen definierte Funktion:
𝑭: 𝑴 ⊆ 𝑴𝟏 × 𝑴𝟐 × ... × 𝑴𝒏→ ℝ, 𝑴 ≠ ∅
Gesucht ist ein 𝒙𝒐𝒑𝒕 ∈ 𝑴
für das gilt: ∀𝒙 ∈ 𝑴: 𝑭 𝒙 ≤ 𝑭 𝒙𝒐𝒑𝒕 = 𝑭𝒐𝒑𝒕
globales Optimum
𝒙 heißt Vektor der Entscheidungsvariablen
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 6 6
Grundlagen der Optimierung - Definitionen
Man spricht von einem lokalen Optimum 𝑭𝒍𝒐𝒑𝒕 = 𝑭(𝒙𝒍𝒐𝒑𝒕), wenn gilt:
∃𝜺 > 𝟎 ∀𝒙 ∈ 𝑴: 𝒙 − 𝒙𝒍𝒐𝒑𝒕 < 𝜺 ⇒ 𝑭(𝒙𝒍𝒐𝒑𝒕) ≥ 𝑭(𝒙)
Wegen 𝒎𝒂𝒙 𝑭(𝒙) = −𝒎𝒊𝒏 −𝑭(𝒙) ist eine Minimumsuche immer in
eine Maximumsuche überführbar.
Beschränkungen von 𝑴: 𝑮𝒋(𝒙) ≥ 𝟎
Explizite Beschränkung: 𝑮𝒋(𝒙) hängt von einer Vektorkomponente xi ab.
Obere/Untere Schranken von xi
Implizite Beschränkung: 𝑮𝒋(𝒙) hängt von mehreren Vektorkomponenten ab.
Unzulässige Bereiche im oder
am Rand des Parameterraums
Reale Probleme sind in der Regel beschränkt.
Planung und Optimierung mit evolutionären Verfahren
K1: Ausgewählte Grundlagen der Optimierung
4
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 7 7
Grundlagen der Optimierung - Komplexität
Polynomialzeit
Zeitobergrenze, die als Polynomfunktion n-ten Grades
der Größe k eines Problems angegeben werden kann,
mit der eine deterministische sequentielle Rechenmaschine
das Problem löst.
Vereinfachende O-Notation:
Notation Bedeutung Beispiele für Laufzeiten
beschränkte Komplexität indizierter Zugriff
logarithmisches Wachstum Binäre Suche im geordneten Feld der Größe x
Wachstum gemäß der Wurzelfunktion naiver Primzahlentest
lineares Wachstum lineare Suche im unsortierten Feld der Größe x
super-lineares Wachstum fortgeschrittenere Sortieralgorithmen (Größe x)
quadratisches Wachstum z.B. Sortieralgorithmus Bubblesort
exponentielles Wachstum rekursive Berechnung der Fibonacci-Folge
)( xO
)1(O
)(log xO
)(xO
)( 2xO
)log( xxO
)2( xO
)( xTeiler
0,1
n
n
i
i
i aka
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 8 8
Grundlagen der Optimierung - Komplexität
O-Notation
dient der Beschreibung der Zeit- oder Speicherkomplexität eines
Algorithmus (auf einer sequentiellen Maschine)
ist eine obere Schranke
Vernachlässigung von Faktoren oder Polynomgliedern geringerer Potenz
Die Vorgehensweise bei der O-Notation erlaubt auch die Bildung von
Komplexitätsklassen für Algorithmen.
Die Klasse der P-Probleme:
Alle Probleme, die von einer deterministischen, sequentiellen
Rechenmaschine (Turingmaschine) in Polynomialzeit lösbar sind.
Planung und Optimierung mit evolutionären Verfahren
K1: Ausgewählte Grundlagen der Optimierung
5
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 9 9
Grundlagen der Optimierung - Komplexität
Die Klasse der NP-Probleme:
Alle Probleme, die
in Polynomialzeit lösbar sind.
Nichtdeterministische Turingmaschine (NTM):
theoretisches Maschinenmodell (Konzept der theoretischen Informatik)
Der Folgezustand einer NTM lässt sich nicht aus dem aktuellen Zustand
und den aktuellen Eingabezeichen ableiten.
NTM wählen einen Nachfolgezustand aus mehreren möglichen aus:
daher nichtdeterministisch
Annahme, dass die Auswahl „gut“ sei, auf jeden Fall besser als zufällig
Randomisierte Algorithmen sind nicht identisch mit nichtdeterministischen!
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 10 10
Grundlagen der Optimierung - Komplexität
Es ist nach wie vor unbekannt unbekannt, ob P = NP ?
Ob also die NP-Probleme nicht doch auf einer deterministischen Maschine
in Polynomialzeit lösbar sind.
NP-vollständige Probleme:
Untermenge der NP-Probleme
lassen sich vermutlich nicht effizient (d.h. in Polynomialzeit) lösen
ab einer problemabhängig kleinen Datenmenge
nicht in praktikabler Zeit lösbar
Planung und Optimierung mit evolutionären Verfahren
K1: Ausgewählte Grundlagen der Optimierung
6
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 11 11
Grundlagen der Optimierung - Komplexität
Einige Beispiele NP-vollständiger Probleme:
Travelling Salesman Problem (TSP), Problem des Handlungsreisenden Ermittlung der kürzesten Städtetour
Schedulingprobleme (z.B. Maschinenbelegung, Stundentafeln, Fahrpläne, ...)
Knapsack Problem (Rucksackproblem) Auswahl von Objekten derart, dass der größte Nutzwert unter Einhaltung einer Gewichtsschranke erreicht wird
. . .
Praktische Lösungsansätze:
Beschränkung auf hinreichend kleine Datenmengen
Verzicht auf die exakte Lösung und Akzeptanz hinreichend guter:
Approximative Algorithmen
Heuristiken
Metaheuristiken (z.B. Evolutionäre Algorithmen, EA)
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 12 12
Grundlagen der Optimierung - Mehrzieloptimierung
Mehrzieloptimierung (multikriterielle Optimierung)
Bisher: eine zu optimierende Zielfunktion
praktische Probleme haben i.d.R. mehrere zu optimierende Kriterien
Beispiele:
große Nutzlast
große Geschwindigkeit
geringer Energieverbrauch
oder
kurze Bearbeitungszeit
geringe Maschinenkosten
hohe Auslastung
sich widersprechende Kriterien!
Planung und Optimierung mit evolutionären Verfahren
K1: Ausgewählte Grundlagen der Optimierung
7
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 13 13
Grundlagen der Optimierung - Mehrzieloptimierung
Bild
quelle:
Mis
terr
ab
e,
Wik
imedia
Pareto-Menge
oder
Pareto-Front
Abbildung der zulässigen
Parametermenge S
durch die Fitnessfunktion
f(x) = (f1(x), ..., fk(x))T, x ∈ S
in die zulässige
Kriterienmenge Z
mit Paretofront
Mehrzieloptimierung (multikriterielle Optimierung)
Pareto-Optimierung:
Bestimmung der Pareto-Menge:
Alle Lösungen, bei denen die Verbesserung
eines Kriteriums
nur auf Kosten eines anderen möglich ist.
Menge aller optimalen Kompromisse
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx
Grundlagen der Optimierung – Mehrzieloptimierung
Mehrzieloptimierung (multikriterielle Optimierung)
Aufwand zur Approximation der Pareto-Front:
. . . . .
7 Stützpunkte können
bei günstiger Lage und
halbwegs regelmäßiger
konvexer Front zur
Approximation
genügen.
Mehr sind meist besser:
Wie viel Stützpunkte
werden mindestens
benötigt?
Für zwei Kriterien braucht man mindestens sieben Punkte.
Wie viel braucht man bei gleicher Approximationsgüte für drei Kriterien?
7×7 = 49 bei gleicher Granularität pro zusätzlichem Kriterium (zusätzlicher Achse)
Und bei vier Kriterien?
7×7×7 = 73 = 343
. . . .
Und allgemein bei k Kriterien und s Punkten?
Planung und Optimierung mit evolutionären Verfahren
K1: Ausgewählte Grundlagen der Optimierung
8
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 15 15
Grundlagen der Optimierung - Mehrzieloptimierung
Mehrzieloptimierung (multikriterielle Optimierung)
Aufwand zur Approximation der Pareto-Front:
Bei je s Stützpunkten pro zusätzlichem Kriterium werden für eine Approximation
der Pareto-Front von k > 1 Kriterien werden s(k-1) Stützpunkte (Pareto-optimale
Lösungen) benötigt.
Anzahl benötigter Lösungen bei
7 bzw. 12 Stützpunkten pro Kriterium
und gleichbleibender Qualität der
Approximation:
Wie nennt man dieses Wachstum?
Exponentiell!
[Jak14]
Beachte:
Logarithmische Skala
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 16 16
Grundlagen der Optimierung - Mehrzieloptimierung
Mehrzieloptimierung (multikriterielle Optimierung)
Pareto-Optimierung:
Vorteile:
Bestimmung vieler gleichwertiger Lösungsalternativen (Kompromisse)
Abschätzung von Wertebereichen der Kriterien
Reduktion einer subjektiven Auswahl auf optimale Kompromisse
Nachteile:
keine direkte quantitative Vergleichbarkeit aller Lösungsalternativen
Exponentielle Steigerung des Aufwands bei steigender Kriterienanzahl
bei mehr als 4 Kriterien kaum noch darstellbar ( Aggregation eines Teils der Kriterien)
Multi- und Many-Objective Evolutionary Algorithms (MOEAs):
NSGA-II und NSGA-III (Non-dominated Sorting Genetic Algorithm) [Deb02, Deb14, Jain14]
Komplexität der Suche: O(m·n2) bei m Kriterien und einer Population der Größe n
SPEA2 (Strength Pareto Evolutionary Algorithm) [Zit01]
Bewertungsverfahren für Evolutionäre Algorithmen
zur Bestimmung einer möglichst divergenten Pareto-Menge [Beu06]
Planung und Optimierung mit evolutionären Verfahren
K1: Ausgewählte Grundlagen der Optimierung
9
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 17 17
Grundlagen der Optimierung - Mehrzieloptimierung
Aggregierung der Kriterien:
z.B. gewichtete Summe:
Getrennte Normierung der Werte der Kriterien auf ein einheitliches Maß.
Dadurch werden sie in Form ihres Erfüllungsgrades vergleichbar.
(subjektive) Gewichtung der Kriterien
Bildung der Summe ein Qualitätswert (Zielfunktion)
Vorteile:
quantitative Vergleichbarkeit aller Lösungsalternativen
keine Begrenzung der Kriterienanzahl
leichte Berechenbarkeit
Nachteile:
Bei nichtkonvexen Lösungsmengen werden Lösungen unerreichbar! (siehe Kap. 5 (GLEAM), Abschnitt über Bewertung)
für Experten nachvollziehbar
Subjektive Gewichtung
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 18 18
Grundlagen der Optimierung - Typen von Optimierungsverfahren
Typen von Optimierungsverfahren:
traditionelle mathematische Verfahren (lokale Suchverfahren, LSV)
z.B. Gradienten-, Quasi-Newton- oder Simplex-Verfahren
startpunktabhängig
ungeeignet bei kombinatorischen Problemen
meist schnelle Konvergenz
zwei Arten:
direkte Verfahren arbeiten nur mit dem Funktionswert
indirekte Verfahren benötigen neben dem Funktionswert Ableitungen
problemspezifische Verfahren
Auf die aktuelle Problemstellung zugeschnittene Verfahren
Entwicklung meist kosten- und zeitintensiv
Erstellung nicht immer möglich
meist schnell
Planung und Optimierung mit evolutionären Verfahren
K1: Ausgewählte Grundlagen der Optimierung
10
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 19 19
Grundlagen der Optimierung - Typen von Optimierungsverfahren
Typen von Optimierungsverfahren (2):
Heuristiken
liefern i.d.R. Näherungslösungen
setzen Erfahrungswissen voraus
auch für kombinatorische Probleme geeignet
meist schnell
globale Suchverfahren
z.B. Evolutionäre Algorithmen, Simulated Annealing, Ameisen-Algorithmen
robust und allgemein anwendbar
auch für kombinatorische Probleme geeignet
vergleichsweise langsam
keine Optimalitätsgarantie
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 20 20
Grundlagen der Optimierung - Typen von Optimierungsverfahren
Typen von Optimierungsverfahren (3):
deterministische Verfahren
liefern bei gleichem Startwert(en) immer die gleiche Lösung
Beispiele:
alle mathematischen Verfahren
viele Heuristiken
stochastische Verfahren
enthalten zufällige Entscheidungen und liefern bei gleichem Startwert(en)
i.d.R. unterschiedliche Lösungen
Beispiele:
Monte-Carlo-Verfahren
Evolutionäre Algorithmen
Simulated Annealing
Ameisen-Algorithmen
Planung und Optimierung mit evolutionären Verfahren
K1: Ausgewählte Grundlagen der Optimierung
11
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 21 21
Grundlagen der Optimierung - gängige Optimierungsverfahren
Einige gängige Optimierungsverfahren:
1. Lokale deterministische Suchverfahren
Allgemeines
Ablaufschema:
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 22 22
Grundlagen der Optimierung - gängige Optimierungsverfahren
Indirekte Verfahren:
Gradientenverfahren, konjugierte Gradientenverfahren
Ermitteln die Richtung des stärksten Anstiegs
Quasi-Newton-Verfahren
verwenden ein quadratisches Modell der Zielfunktion durch
Taylor-Reihenansatz und deren Ableitung
Fülle von Varianten, z.B. DFP-Verfahren mit und ohne Ableitungen
Eigenschaften:
Beschränkungen werden nicht berücksichtigt.
Hinzunahme durch Änderung der Zielfunktion soweit möglich
konvergieren schnell
Mehrfachstart bei multimodalen Zielfunktionen erforderlich
Aufwand: nicht unter O(n3)
Planung und Optimierung mit evolutionären Verfahren
K1: Ausgewählte Grundlagen der Optimierung
12
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 23 23
Grundlagen der Optimierung - gängige Optimierungsverfahren
Direkte Verfahren:
Suchrichtung und Schrittweite werden heuristisch bestimmt.
ableitungsfrei
keine Berücksichtigung von Beschränkungen
Gauß-Seidel-Verfahren
Iterative Suche mit fester Schrittweite entlang den Achsen
bis Verbesserung ausbleibt.
Konvergenzgeschwindigkeit stark suchraumabhängig
Fülle von Varianten zur Verbesserung der Konvergenzgeschwindigkeit
Pattern-Strategien
Anpassung der Suchrichtung entsprechend der Zielfunktion
Verfahren von Hooke und Jeeves
Verfahren von Powell (konjugierte Richtungen)
Konvergenzprobleme möglich
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 24 24
Grundlagen der Optimierung - gängige Optimierungsverfahren
Rosenbrock-Verfahren
Suche entlang eines im Raum rotierenden Koordinatensystems,
das in die Richtung zeigt, die den größten Fortschritt verspricht.
Anpassung der Schrittweiten
Berücksichtigung von Beschränkungen durch interne Straffunktion
Benötigt gültigen Startpunkt
Gilt als robustes, ableitungsfreies lokales Suchverfahren.
Aufwand: O(n3)
Planung und Optimierung mit evolutionären Verfahren
K1: Ausgewählte Grundlagen der Optimierung
13
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 25 25
Grundlagen der Optimierung - gängige Optimierungsverfahren
Polyederverfahren:
Arbeiten mit mehreren Punkten (n+1), die einen Polyeder bilden.
Veränderung durch Kontraktion, Expansion und Reflexion des Polyeders
Reflexion des schlechtesten Punktes am Flächenschwerpunkt
Bei Verbesserung Versuch einer Expansion
Bei Verschlechterung erfolgt eine Kontraktion
Abbruch bei zu großer Annäherung der Punkte an den Mittelpunkt
Bewegung eines Polyeders im Raum, wobei kleinere lokale Minima
übersprungen werden können.
Gilt bei wenigen Entscheidungsvariablen (bis zu 10) als robust.
Aufwand: O(n2),
Anzahl der Funktionsaufrufe bei bis zu 10 Entscheidungsvariablen: O(n2.11)
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 26 26
Grundlagen der Optimierung - gängige Optimierungsverfahren
Polyederverfahren (2):
Simplexverfahren von Nelder und Mead: Nicht zu verwechseln mit dem Simplex-Verfahren der linearen Programmierung (Dantzig)
basiert auf einem Startpunkt, von dem aus die anderen bestimmt werden
keine Berücksichtigung von Beschränkungen
Complex-Verfahren von Box
COMPLEX steht für COnstrained siMPLEX),
Erweiterung des Simplexverfahrens für Beschränkungen
ein Startpunkt, der Rest wird ausgewürfelt ( stochastisches Verfahren)
Abbruch, wenn fünf mal hintereinander keine Verbesserung eintritt.
Numerische Tests mit bis zu 10 Entscheidungsvariablen:
Beide Polyederverfahren
verhalten sich ähnlich,
benötigen mehr Funktionsaufrufe als das Rosenbrock-Verfahren
Planung und Optimierung mit evolutionären Verfahren
K1: Ausgewählte Grundlagen der Optimierung
14
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 27 27
Grundlagen der Optimierung - gängige Optimierungsverfahren
2. Globale stochastische Suchverfahren:
Simulated Annealing (SA, simuliertes Auskühlen):
Idee: Durch langsames Auskühlen können die Atome einen Platz mit
energiearmen Zustand einnehmen.
Algorithmus:
Die Bewegungsfähigkeit des Suchpunktes wird gemäß einer
vorgegebenen Temperaturkurve eingeschränkt.
Entsprechend werden mit abnehmender Wahrscheinlichkeit auch
Verschlechterungen akzeptiert.
Konsequenz: Minima können übersprungen werden.
Nachteil:
Wahl einer geeigneten Temperaturkurve (anwendungsabhängig)
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 28 28
Grundlagen der Optimierung - gängige Optimierungsverfahren
Ameisen-Algorithmen (Ant Colony Optimisation):
Idee: Kürzere Wege zu einem Futterplatz werden öfter von Ameisen
frequentiert als längere.
höherer Pheromonkonzentration, Entstehung einer „Ameisenstrasse“
Algorithmus:
Eine effiziente Suche nach der kürzesten Route lässt sich so mit vielen
Versuchen (Ameisen) algorithmisch nachbilden.
gut geeignet für kombinatorische Probleme
Die bisher besten Ergebnisse für das TSP wurden mit
einem modifiziertem Ameisen-Algorithmus erreicht
Planung und Optimierung mit evolutionären Verfahren
K1: Ausgewählte Grundlagen der Optimierung
15
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 29 29
Grundlagen der Optimierung - gängige Optimierungsverfahren
Tabu-Search:
Idee: Vermeidung von Zyklen bei der Suche durch Erstellung einer Tabu-Liste
Wie beim Simulated Annealing gibt es nur eine aktuelle Lösung.
Algorithmus:
Erzeugung einer Nachbarschaft ausgehend von einem zufällig oder
heuristisch generierten Startpunkt
Neue aktuelle Lösung ist die beste der Nachbarschaft,
die nicht auf der Tabu-Liste steht. Ausnahmen möglich.
Update der Tabu-Liste mit der neuen aktuellen Lösung
Die Tabu-Liste ist begrenzt Vergessen
Viele Varianten
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx
Grundlagen der Optimierung – No free Lunch-Theoreme
No-free-Lunch-Theoreme: (Nichts ist umsonst)
Bezogen auf die Menge aller mathematisch möglichen Probleme sind
alle Suchalgorithmen im Durchschnitt gleich gut (oder gleich schlecht).
[Wol95, Wol97]
Metaheuristik mit möglichst viel Anwendungswissen anpassen:
an das Problem oder besser
an die Problemklasse
Umkehrschluss:
Es gibt keinen Universalalgorithmus, der alle Aufgaben am effizientesten löst!
30
Planung und Optimierung mit evolutionären Verfahren
K1: Ausgewählte Grundlagen der Optimierung
16
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K1_Opt-Grundlagen.pptx 31 31
Grundlagen der Optimierung – Das Wichtigste in Kürze
Eigenschaften von Optimierungsproblemen und Suchräumen F2 - F4
Definition eines globalen und lokalen Optimums, Beschränkungen F5, F6
Komplexität, O-Notation, Klasse der NP-vollständigen Probleme F7, 8, 10, 11
Mehrzieloptimierung, gewichtete Summe, Pareto-Menge und -Front F12 - F17
Typen von Optimierungsverfahren:
Deterministische und stochastische Verfahren, Heuristiken,
indirekte und direkte Verfahren F18 - F22
Direkte, also ableitungsfreie Verfahren:
Rosenbrockverfahren, Complex-Algorithmus F23 - F26
Globale stochastische Verfahren:
Simulated Annealing, Ameisenalgorithmen, Tabu-Search F27 - F29
No-free-Lunch-Theoreme F30
Recommended