Planung und Optimierung mit evolutionären Verfahrenjawi0001/EA-Vorlesung/PDF/K0_EA-Einf… · Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 3 Einführung

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)



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:

[email protected]


K0: Einführung

2



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!



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 . . .


K0: Einführung

3




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




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:


K0: Einführung

4



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. . . .



}


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


K0: Einführung

5




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



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?


K0: Einführung

6



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



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


K0: Einführung

7



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 . . .



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


K0: Einführung

8



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!



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!


K0: Einführung

9



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



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.


K0: Einführung

10



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

. . .



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


K0: Einführung

11



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



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


K0: Einführung

12



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!



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.


K0: Einführung

13



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




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 !


K0: Einführung

14




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




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!


K0: Einführung

15




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)



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


K0: Einführung

16




Quelle: Rechenberg: I. Evolutionsstrategie ‘73

Gegenüberstellung

des Viertelkreises (a)

und der

idealen Krümmung (b):




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


K0: Einführung

17




Vergleich der Ergebnisse mit natürlichen Flussläufen:

Quellen: Autor, Klaus Leidorf




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


K0: Einführung

18




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.




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.


Initialisierung (Generation 0), Gewicht in Klammern


K0: Einführung

19




Evolution einer Bogenbrücke:





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


K0: Einführung

20



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.

Documents

Planung und Optimierung mit evolutionären Verfahrenjawi0001/EA-Vorlesung/PDF/K0_EA-Einf… · Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 3 Einführung