Planung und Optimierung mit evolutionären Verfahren
K0: Einführung
1
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 1
Planung und Optimierung
mit
evolutionären Verfahren
Dr.-Ing. Wilfried Jakob
KIT, Campus Nord
Institut für Automation und angewandte Informatik (IAI)
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 2
KIT, IAI, ... Was ist das?
KIT: Karlsruher Institut für Technologie
Zusammenschluss der Universität Karlsruhe (Campus Süd) und
des ehem. Forschungszentrums Karlsruhe (Campus Nord)
IAI: Institut für Automation und angewandte Informatik (Campus Nord)
Forschungsinstitut, kein Lehrauftrag im universitären Bereich
Trotzdem war das IAI schon immer in der Ausbildung aktiv:
Auszubildende und DHBW-Studierende der entsprechenden Fachrichtungen
Vergabe und Betreuung von
Praktika,
Studienarbeiten,
Bachelorarbeiten,
Masterarbeiten,
Promotionen
von Studierenden der
DHBW,
Hochschulen Karlsruhe und Mannheim,
KIT, Campus Süd
Siehe: http://www.iai.kit.edu/ (Menüpunkt Studentische Arbeiten)
Sie erreichen mich am besten per
Email:
Planung und Optimierung mit evolutionären Verfahren
K0: Einführung
2
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 3
Einführung
Worum geht es?
Um eine Methode zur praktischen Lösung schwieriger Probleme!
Warum schwierige Probleme?
Die „einfachen“ kann man berechnen.
Es gibt etablierte Lösungsverfahren.
Warum „praktische Lösung“?
Weil keine mathematisch exakte Lösung geliefert wird!
Warum?
Das Ergebnis ist also eine Näherungslösung
} Nicht Gegenstand
dieser Vorlesung
Sonst könnte man es ja berechnen!
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 4
Einführung – Beispiel Standortplanung
Beispiele für „schwierige Probleme“
1. Beispiel: Standortplanung
Beispiel: Planung neuer Bahnhöfe zur Verbesserung des
Angebots für Pendler
Situation:
Viele Bahnhöfe entstanden zu Beginn des letzten Jahrhunderts
Die Standorte passen häufig nicht mehr zu den aktuellen Siedlungsstrukturen
Revision von Fehlern bei früheren Schließungen von Bahnhöfen
Ziele:
Gewinnung neuer Kunden
Zeitgewinn für (neue) Pendler
Wirtschaftlichkeit der Standorte
geringe Zeitverluste durch neue Zwischenstopps
kostengünstig zu bauen
Entlastung vorhandener Verkehrswege . . .
Planung und Optimierung mit evolutionären Verfahren
K0: Einführung
3
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 5
Einführung – Beispiel Standortplanung
Umfang:
ca. 6000 mögliche Standorte
ergibt 26000 ≈ 1,5∙101806 Varianten
Bisheriger Lösungsansatz:
Also durch menschliche Kopfarbeit!
Nachdenken Ideen Teamwork Kreativität
Zum Vergleich: geschätzte Anzahl der
Sterne im Universum:
7·1022
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 6
Einführung – Beispiel Standortplanung
Bahnhofsprojekt:
Mehrere Auswahlrunden,
wobei zwei mal evolutionäre
Verfahren eingesetzt wurden,
ergaben eine Liste von rund
350 potentiell lukrativen
Standorten.
Davon werden zunächst
20 Stationen bis 2023
in Bayern gebaut:
Planung und Optimierung mit evolutionären Verfahren
K0: Einführung
4
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 7
Einführung – Beispiel Produktionsplanung
2. Beispiel: Produktionsplanung
Randbedingungen (Beispiel):
Ein Produkt bestehe aus mehreren Teilen, die jeweils in Einzelschritten
(Jobs) hergestellt und zusammengebaut werden müssen.
Die Reihenfolge der Jobs ist teilweise vorgeschrieben.
Jobs können auf mehreren Maschinen ausgeführt werden.
Mehrere Jobs können um die gleiche Maschine konkurrieren.
Maschinen sind unterschiedlich schnell und kostenintensiv.
Gleichartige Maschinen benötigen unterschiedlich viel Energie.
Aufträge haben Kosten- und Zeitlimits. . . .
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 8
}
Einführung – Beispiel Produktionsplanung
Aufgabe:
Erstellung eines Produktionsplanes, der:
zulässig ist. Das heißt, dass alle Jobs:
auf geeigneten Maschinen und
in zulässiger Reihenfolge ausgeführt werden
Einhaltung aller Fertigstellungstermine
Einhaltung aller Kostenlimits
hohe Auslastung der Maschinen
kurze Gesamtbearbeitungszeit
geringer Energieverbrauch
geringe Maschinenkosten
. . .
} Erfüllung
notwendig
abnehmende Priorität
mehrere zum Teil sich widersprechende Bewertungskriterien
Planung und Optimierung mit evolutionären Verfahren
K0: Einführung
5
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 9
Einführung – Beispiel Produktionsplanung
Ab einer gewissen (geringen) Anzahl von n Maschinen und m Jobs
nicht mehr in polynomialer Zeit lösbar!
Der Aufwand steigt mit steigendem n und m exponentiell.
Es gibt ab einem gewissen n und m nur Näherungslösungen.
Praxis: Einsatz von Heuristiken
Polynomialer Aufwand:
Der Aufwand zur Lösung eines Problems
steigt in Abhängigkeit von der Problemgröße k
nicht stärker als eine Polynomfunktion P(k).
Heuristik:
Unexakte Methode zur
Ermittlung „guter Lösungen“
basierend auf Erfahrung
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 10
Einführung – Beispiel Kraftwerks- und Netzausbau
3. Beispiel: Kraftwerks- und Netzausbau
Mehrere Aufgabenstellungen:
1. Wo sollen welche Kraftwerkstypen mit welcher Kapazität gebaut werden?
Biogas
Photovoltaik
Windkraft
Sonnenkraftwerke mit/ohne Wärmespeicher
Gaskraftwerk mit/ohne Wärmekopplung
Wasserkraftwerke . . .
2. Wo sollen welche Speicher mit welcher Kapazität gebaut werden?
Akkuspeicher zur kurzfristigen Netzstabilisierung
Power-to-Gas-Speicher
Wärmespeicher . . .
3. Wo werden neue Leitungskapazitäten in welchem Umfang benötigt?
Planung und Optimierung mit evolutionären Verfahren
K0: Einführung
6
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 11
Einführung – Beispiel Kraftwerks- und Netzausbau
Planungsziele:
niedrige Investitionskosten
niedrige Betriebskosten
kurz- und langfristige Netzstabilität
hohe Ausfallsicherheit
Wartbarkeit
CO2-Ausstoss . . .
Komplexe Aufgabenstellung:
Anordnungsplanung
Kapazitätsplanung (kontinuierliche und ganzzahlige Parameter)
Einige Ziele widersprechen sich,
z.B. niedrige Kosten und
hohe Ausfallsicherheit
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 12
Einführung – Beispielaufgaben
Wichtige Eigenschaften der Beispiele:
Bewertbarkeit: Qualität einer Lösung ist bezifferbar
Lösungen sind vergleichbar
Bewertung: Mehrere sich zum Teil widersprechende Bewertungskriterien
Multikriterielle Bewertung
Unterschiedliche Problemarten:
Designoptimierung: Optimierung kontinuierlicher Parameter
Produktionsplanung: kombinatorische Optimierung
Kraftwerks- u. Netzausbau: kombinatorische u. gemischt-ganzzahlige Optimierung
Planung und Optimierung mit evolutionären Verfahren
K0: Einführung
7
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 13
Einführung – Einsatzgebiet evolutionärer Verfahren
Ausgangssituation:
Ein komplexes Optimierungsproblem (z.B. wegen Nichtlinearitäten)
Keine mathematische Lösung vorhanden modell-basierte Optimierung
Beispiele:
Arbeits- und Belegungsplanung (Scheduling), NP-vollständiges Problem
Anordnungsprobleme, z.B. Standortplanung
Designoptimierung
Reihenfolgeoptimierungen . . .
Eigenschaften:
– viele Parameter
– gemischt-ganzzahlige Parameter
– Zielfunktion mit nur einem Optimum oder mit vielen Suboptima?
– nichtlineare oder diskontinuierliche Zielfunktion
– Restriktionen . . .
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 14
Einführung – Einsatzgebiet evolutionärer Verfahren
Konventionelle Lösungsmethoden wie
numerische Verfahren (lokale Suchverfahren)
problemspezifische Lösungen
heuristische Verfahren
sind entweder nicht anwendbar oder führen nicht zum Erfolg.
Lösung:
Anwendung eines globalen Optimierungsverfahrens,
z.B. einer Metaheuristik wie die evolutionären Verfahren
Planung und Optimierung mit evolutionären Verfahren
K0: Einführung
8
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 15
Einführung – Kennzeichen eines evolutionären Verfahrens
Was ist ein Evolutionäres Verfahren?
Ein Verfahren, das die Prinzipien der biologischen Evolution
Vererbung,
Mutation,
Rekombination und
Überleben der Bestangepassten (survival of the fittest)
nutzt, um Lösungen zu verbessern.
Lösungen werden nicht berechnet,
sondern gezüchtet!
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 16
Einführung – Warum Evolutionäre Algorithmen?
Warum evolutionäre Verfahren oder Evolutionäre Algorithmen?
Was ist der mächtigste natürliche Problemlöser?
1. Das menschliche Gehirn
Es erschuf
das Rad
Karlsruhe
die Medizin
Kriege …
2. Die biologische Evolution
Sie erschuf das menschliche Gehirn!
Planung und Optimierung mit evolutionären Verfahren
K0: Einführung
9
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 17
Einführung – Warum Evolutionäre Algorithmen?
Anpassungs- und Entwicklungsleistungen der Evolution:
Kenntnisse über
Aerodynamik
?
Strömungsmechanik
riechen meilenweit …
… halten bittere Kälte aus
. . . Quellen: Wikipedia: L.Argerich, A.Walk; Autor
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 18
Einführung – Motivation
Welchen Nutzen können Sie aus dieser Vorlesung ziehen?
Häufig Vereinfachung komplexer Aufgaben soweit,
dass konventionelle Verfahren eingesetzt werden können.
Die vorgestellten Verfahren erlauben (wesentlich) bessere Lösungen!
Derzeit noch begrenzte Verbreitung des Wissens um Metaheuristiken
Metaheuristiken gehören (noch) nicht zum Standardkurrikulum der
Informatik und der Ingenieurwissenschaften
Vorbehalte gegen unexakte Methoden
Die Kompetenz zur Lösung
schwieriger Planungs- und Optimierungsaufgaben
verschafft Ihnen einen Wettbewerbsvorteil.
Planung und Optimierung mit evolutionären Verfahren
K0: Einführung
10
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 19
Einführung – Motivation
Die Anwendungsmöglichkeiten evolutionärer Verfahren sind vielfältig:
Designoptimierung:
Turbinen, Flugzeugflügel, Antennen, mikrooptische Bauteile, Leiterplattenlayout, …
kurz: alles was sich simulieren und bewerten lässt
Scheduling:
klassische Produktionsplanung, Produktionsplanung mit Nebenbedingungen
(Energieverbrauch, Mitarbeitereinsatzspitzen, …),
Fahrpläne, Flugpläne, (Hoch)Schulstundenpläne,
Wartungsplanung, Kraftwerkseinsatzplanung, …
Anordnungsplanung
Zuschnittsplanung (Textilindustrie, Schiffsbau, …), Container- oder LKW-Beladung
Standortplanung mit Nebenbedingungen, Kraftwerksausbau, Netzausbau, …
Tourenplanung:
Tourenplanung mit Randbedingungen wie Ladungskapazität, Pausenzeiten,
Energieverbrauch; Standort- und Tourenplanung
. . .
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 20
Einführung – Ziele der Vorlesung
Ziele der Vorlesung:
Vermittlung von
Grundlagenwissen über Evolutionäre Algorithmen (EA)
Wissen über erfolgversprechende Einsatzfelder
Wissen über ein geeignetes Vorgehen beim EA-Einsatz
Befähigung zur
Auswahl geeigneter EA
Auswahl geeigneter Partner für den EA-Einsatz
zur vertiefenden Beschäftigung mit der Thematik
Vermeidung von Anfängerfehlern beim EA-Einsatz
Kein Ziel: Implementierung oder Modifikation eines EA
Planung und Optimierung mit evolutionären Verfahren
K0: Einführung
11
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 21
Einführung – Übersicht über die Vorlesungsinhalte
Übersicht über die Vorlesungsinhalte
1. Ausgewählte Grundlagen der Optimierung
2. Ausgewählte Grundlagen der biologischen Evolution
3. Aufbau und Operatoren evolutionärer Verfahren
4. Klassische evolutionäre Verfahren
5. Der Evolutionärer Algorithmus GLEAM
6. Anwendung Roboterbahnplanung mit Präsentation und Experimenten,
Ausführliches Anwendungsbeispiel ( Hausarbeit eine Klausuraufgabe)
6. Memetische Algorithmen – Erweiterung der evolutionären Verfahren
7. GLEAM-Anwendungen
8. Empfehlungen zum EA-Einsatz,
EAs an Universitäten und Forschungseinrichtungen
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 22
Einführung – Ablauf der Vorlesung, Prüfungsleistungen
Homepage der Vorlesung:
www.home.hs-karlsruhe.de/~jawi0001/EA-Vorlesung/
Handout (Folien ohne die Übungslösungen)
Gliederung der Vorlesung
Literaturliste
Aktuelles und Termine (z.B. verlegte oder ausfallende Vorlesungstermine)
Liste der Wiederholungsfragen
Übungen:
Sowohl kleinere als auch umfangreichere Übungen während der Vorlesung:
Folien-Handout enthält Platz zum Eintragen der Lösungen
Zur Bearbeitung muss teilweise auf vorherige Folien zurückgegriffen werden.
Taschenrechner sind bisweilen hilfreich
Planung und Optimierung mit evolutionären Verfahren
K0: Einführung
12
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 23
Einführung – Ablauf der Vorlesung, Prüfungsleistungen
Zusammenfassung am Ende eines Kapitels
Das Wichtigste in Kürze und mit Verweisen auf die Folien und immer in dieser Farbe
Wiederholung:
Karten mit Wiederholungsfragen zum Stoff der letzten Stunde
Die Fragenliste steht auf der Homepage
Leistungsnachweis:
1. Freiwillige Hausarbeit
Sie wird korrigiert und bewertet: Gute oder sehr gute Noten heben die
Note einer bestandenen Klausur um 1 bzw. 2 Notenstufen an.
2. Einstündige Klausur in der letzten Vorlesungsstunde
Hausarbeit und Wiederholungsfragen
sind mit Sicherheit eine sehr gute Klausurvorbereitung!
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 24
Einführung – Literatur
Das Buch zur Vorlesung:
Enthält einen großen Teil des Stoffes
in der Regel ausführlicher als
in der Vorlesung.
Erhältlich beim Verlag
http://www.ksp.kit.edu/
Dort nach GLEAM suchen:
PDF-Download (kostenlos)
Link unten und unscheinbar
Papierform (31,90 €)
oder dem Link in der Literaturliste
auf der Homepage folgen.
Planung und Optimierung mit evolutionären Verfahren
K0: Einführung
13
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 25
Einführung – Grenzen von Suchverfahren
Evolutionäre Algorithmen gehören zu den Suchverfahren.
Beispiel: Suche nach einem Dokument
Eine Suchstrategie …
… ist nutzlos in einer
chaotischen Welt.
… funktioniert nur in einer
geordneten Welt.
Bildquelle: I. Rechenberg
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 26
Einführung – Grenzen von Suchverfahren
Mit welcher Suchstrategie sucht man am besten eine Nadel im Heuhaufen?
Keine Ordnung! Suche per Zufall (Monte-Carlo-Verfahren)
Strategie = Overhead
Wo ist die Nadel im Heuhaufen?
Na hier!
Bildquellen: Wikipedia: R.Huber; Prof. R. Stauber, Uni Mainz
… und der nützt hier gar nichts !
Planung und Optimierung mit evolutionären Verfahren
K0: Einführung
14
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 27
Einführung – Grenzen von Suchverfahren
Gibt es eine universelle Weltordnung?
Ja!
Kausalität Gleiche Ursache, gleiche Wirkung
Schwache Kausalität Kleine Ursachenänderung, große Wirkungsänderung
Starke Kausalität Kleine Ursachenänderung, kleine Wirkungsänderung
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 28
Einführung – Grenzen von Suchverfahren
Suche nach dem Optimum
in einer
stark kausalen Welt schwach kausalen Welt
Optimumsucher mit Tiefenlot
Bildquelle: I. Rechenberg
? sicher deutlich schwieriger,
aber immerhin noch kontinuierlich!
Planung und Optimierung mit evolutionären Verfahren
K0: Einführung
15
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 29
Einführung – Grenzen von Suchverfahren
Die Grenze aller Suchstrategien beginnt dort,
… wo die Kausalität fehlt,
… wo es nichts zu lernen gibt!
Also zum Beispiel hier:
Nadel im Heuhaufen:
Jede Suchstrategie
= Overhead
= hier nutzloser Overhead!
Konsequenz:
Suche per Zufall
(Monte-Carlo-Verfahren)
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 30
Einführung - Klassische Anwendungsbeispiele der Evolutionsstrategie
Experimente mit frühen Formen der Evolutionsstrategie von
Ingo Rechenberg und Hans-Paul Schwefel Mitte der 60-iger Jahre
Aufgabe:
Minimierung der
Umlenkverluste
bei einem Rohr mit
90° bzw. 180° Krümmung
Quelle: I. Rechenberg: Evolutionsstrategie ‘73
Planung und Optimierung mit evolutionären Verfahren
K0: Einführung
16
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 31
Einführung - Klassische Anwendungsbeispiele der Evolutionsstrategie
Quelle: Rechenberg: I. Evolutionsstrategie ‘73
Gegenüberstellung
des Viertelkreises (a)
und der
idealen Krümmung (b):
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 32
Einführung - Klassische Anwendungsbeispiele der Evolutionsstrategie
Zusammenfassung der Ergebnisse:
Optimaler 90°- Strömungskrümmer
Start Ergebnis
Optimaler 180°- Strömungskrümmer
Start Ergebnis
10% verminderte Strömungsverluste
gegenüber der Kreisform
Quelle: I. Rechenberg
Planung und Optimierung mit evolutionären Verfahren
K0: Einführung
17
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 33
Einführung - Klassische Anwendungsbeispiele der Evolutionsstrategie
Vergleich der Ergebnisse mit natürlichen Flussläufen:
Quellen: Autor, Klaus Leidorf
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 34
Einführung - Klassische Anwendungsbeispiele der Evolutionsstrategie
Optimierung einer Zweiphasen-Überschalldüse zur
Stromerzeugung für ein Raumfahrtprojekt
Ziel:
Optimierung des Wirkungsgrads bei der Stromerzeugung
Parameter:
1. Anzahl der Segmente (Länge der Düse)
2. Segmentdurchmesser (Korrektur zur Vermeidung von Sprüngen)
Versuchsaufbau:
330 Segmente erlauben
1060 Düsenformen.
Quelle: I.
Rechenberg
: E
volu
tionsstr
ate
gie
‘73
Planung und Optimierung mit evolutionären Verfahren
K0: Einführung
18
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 35
Einführung - Klassische Anwendungsbeispiele der Evolutionsstrategie
Ausgangsform:
Wirkungsgrad: 55%
Quelle: R
echenberg
: I.
Evolu
tionsstr
ate
gie
‘73
Wirkungsgrad: fast 80%
Die Strömungsverhältnisse
ließen sich damals
nicht berechnen.
Das völlig unerwartete Ergebnis
zeigt ausgeprägte Kammern
sowohl im konvergenten als auch
im divergenten Düsenteil.
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 36
Einführung - Klassische Anwendungsbeispiele der Evolutionsstrategie
Evolution einer gewichtsminimalen Bogenbrücke
31 Parameter:
1. Position (y-Koordinate) der 11 Knotenpunkte auf der Fahrbahn
2. Position der 10 Bogenpunkte (x- und y-Koordinate)
Der Elementdurchmesser ergibt sich aus den statischen Erfordernissen.
Daraus resultiert das zu minimierende Gewicht.
Quelle: Rechenberg: I. Evolutionsstrategie ‘94
Initialisierung (Generation 0), Gewicht in Klammern
Planung und Optimierung mit evolutionären Verfahren
K0: Einführung
19
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 37
Einführung - Klassische Anwendungsbeispiele der Evolutionsstrategie
Evolution einer Bogenbrücke:
Quelle: Rechenberg: I. Evolutionsstrategie ‘94
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 38
Einführung - Klassische Anwendungsbeispiele der Evolutionsstrategie
Von der Fensterscheibe zur Linse
Veränderung eines
deformierbaren Glaskörpers
(10 Segmente)
Neben der Generationszahl steht
ein Maß für die Strahlenstreuung.
Quelle: Rechenberg: I. Evolutionsstrategie ‘94 Linse
Planung und Optimierung mit evolutionären Verfahren
K0: Einführung
20
Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob
Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 39
Einführung – Das Wichtigste in Kürze
Einsatzbereiche evolutionärer Verfahren F3, F13, F14, F19
Was kennzeichnet ein evolutionäres Verfahren
bzw. einen Evolutionären Algorithmus (EA)? F15
Was ist eine Heuristik? F9
Grenzen aller Suchstrategien und damit auch von EAs F25 – F29
Anmerkung: Dieses Handout ist im Gegensatz zu den Nachfolgenden eine Zusammenfassung der
ersten Vorlesung und des Einführungsteils der Zweiten.
Obige Foliennummern beziehen sich auf das Handout.