Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Evolution im Computer

Evolution im Computer

Vortragsfolien für den Vortrag "Evolution im Computer" beim JUG Saxony Day 2018 am 28.09.2018 von Stephan Pirnbaum und Steffen Gemkow.

Stephan Pirnbaum

September 28, 2018
Tweet

More Decks by Stephan Pirnbaum

Other Decks in Programming

Transcript

  1. Infinite-Monkey Theorem • Man nehme: ◦ Unendliche Anzahl Affen ◦

    Je Affe eine Schreibmaschine ◦ Unendlich Zeit • Man erhalte: ◦ Shakespeares Werke ◦ Ressourcenproblem ◦ Problem mit den Tierschützern https://www.theinfinitemonkeytheorem.com/
  2. Methinks it is like a weasel • Gedankenexperiment von Richard

    Dawkins ◦ Tastatur mit 26 + 1 Tasten (Buchstaben + Space) ◦ Einen Fehler-machenden Copy-Paste-Affen ◦ Eine Ausgangstextsequenz (Zufällig, Länge 28) https://www.worldatlas.com/articles/what-are-the-differences-between-a-stoat-and-a-weasel.html
  3. Darwins Evolutionstheorie • 3 Grundthesen ◦ Alles Leben hat sich

    im Laufe der Zeit entwickelt ◦ Die Weiterentwicklung von Arten erfolgt durch natürliche Selektion ◦ Arten passen sich an die Natur an https://www.dkfindout.com/uk/science/famous-scientists/charles-darwin/
  4. Darwins Evolutionstheorie - Grundbegriffe • Individuum ◦ Ein einzelnes Lebewesen

    oder Ding • Population ◦ Menge aller Individuen einer Art, die untereinander genetisch, physiologisch und räumlich fähig sind, sich fortzupflanzen • Generation ◦ Menge aller Individuen, die den gleichen Abstand zu ihren gemeinsamen Vorfahren haben
  5. Darwins Evolutionstheorie - Grundbegriffe • Selektion ◦ Auslese der stärksten

    bzw. angepasstesten Individuen einer Generation • Kreuzung ◦ Kombination der Erbanlagen zweier Individuen zur Fortpflanzung • Mutation ◦ Zufällige Änderung von Teilen der Erbanlagen
  6. Darwins Evolutionstheorie - Algorithmus 1: population = Initiale Population (Generation

    0) 2: while (true) do 3: selektion = selektiere ( population ) 4: population = mutiere ( kreuze ( selektion ) )
  7. Das Problem - Anforderungen • Optimierungsproblem o Mehrere mögliche Lösungen

    ◦ Lösungen kodierbar ◦ Lösungen bewertbar ◦ Bereitschaft, auf die BESTE Lösung zu verzichten
  8. Die Kodierung - Genotyp vs. Phänotyp • Genotyp ist das

    Erbbild eines Merkmals • Phänotyp ist das Erscheinungsbild (Ausprägung) eines Merkmals • Genetische Algorithmen: Genotyp != Phänotyp • Evolutionsstrategie: Genotyp = Phänotyp
  9. Die Kodierung • “Methinks it is like a weasel” ◦

    Lineare Repräsentation → Evolutionsstrategie da Genotyp = Phänotyp
  10. Die Selektion • Qualität einer Lösung im Kontext des Problems

    • Höhere Qualität = Höhere Wahrscheinlichkeit für “Vermehrung” • Ein oder mehrere Kriterien, Skalarisierung möglich • Fitnessfunktion
  11. Die Selektion - Single vs. Multi Objective • Single Objective

    Optimization ◦ Lösungsqualität ist von einer skalarisierbaren Eigenschaft abhängig ▪ Direkte Nutzung dieser zur Bewertung ◦ Lösungsqualität ist von mehreren skalarisierbaren Eigenschaften abhängig ▪ Kombination aller Eigenschaften zu einem Skalar notwendig ▪ Gewichtung der Eigenschaften spielt große Rolle für Resultat ◦ (normalisierter) Skalar entspricht der Wahrscheinlichkeit für die Auswahl zur Weiterentwicklung
  12. Die Selektion - Single vs. Multi Objective • Multi Objective

    Optimization ◦ Lösungsqualität ist von mehreren skalarisierbaren Eigenschaften Abhängig ▪ Bei n Eigenschaften → n-dimensionaler Bewertungsraum ▪ Pareto-Front enthält gleich-gute Lösungen ▪ Auswahl aus Pareto-Front gleichwahrscheinlich
  13. Die Kreuzung • Rekombination des Erbmaterials zweier Lösungen • Dient

    der breiten Exploration des Suchraums • Auswahl zweier Lösungen aus der aktuellen Population ◦ Basierend auf deren Wahrscheinlichkeit (Fitness) • Rekombination beider Lösungen durch Teilen und Zusammensetzen ◦ Mittig oder an zufälliger Position
  14. Die Mutation • Zufällige Veränderung von Werten abhängig von der

    Mutationsrate • Höhere Mutationsrate → Mehr Werte werden geändert • Zufällige Auswahl des neuen Werte
  15. SARF - Evolutionäre Architekturrecovery • Problem: ◦ Über Jahre gewachsene,

    stark errodierte Softwaresysteme ◦ Undokumentierte bzw. von Dokumentation abweichende Architektur • Ziel: ◦ Restrukturierung der Anwendung anhand fachlicher Gesichtspunkte • Frage: ◦ Wie sollte das Softwaresystem strukturiert sein?
  16. SARF - Evolutionäre Architekturrecovery • Gesucht: ◦ Sinnvolle Dekomposition des

    Systems in Komponenten ▪ Dekomposition = Systemzerlegung ▪ Komponente = Menge von Klassen ▪ Kodierung = ? ▪ Sinnvoll = ?
  17. SARF - Evolutionäre Architekturrecovery • Kodierbarkeit von Lösungen ◦ Zuordnung

    von Klassen zu Komponenten ▪ Klasse => Identifiziert durch ID ▪ Komponente => Identifiziert durch ID
  18. SARF - Evolutionäre Architekturrecovery • Bewertbarkeit von Lösungen ◦ Single-Responsibility

    Principle => Hohe Kohäsion ◦ Separation of Concerns => Geringe Kopplung 2 Objectives
  19. SARF - Evolutionäre Architekturrecovery • Bewertbarkeit von Lösungen ◦ Single-

    vs. Multi-Objective Optimization ▪ Konkurrierende Objectives, schwer zu gewichten ▪ “Die eine Lösung” existiert nicht Multi-Objective Optimization
  20. SARF - Evolutionäre Architekturrecovery • Umsetzung mit Jenetics ◦ Open

    Source Java Bibliothek ◦ EvolutionStream als Grundlage ▪ Verschiedene vordefinierte Kodierungsarten und Datentypen ▪ Verschiedene Crossover- und Mutationsoperatoren ▪ SOO- und MOO-Unterstützung ▪ Parallelisierbar und umfangreiche Statistiken
  21. TTBN - Evolutionäre Befahrbarkeitsprüfung • Schwertransporte planen und genehmigen •

    Frage: ◦ Kann der Transport durch die Engstelle fahren? • Ziel: ◦ Nachweis §§ © Fotolia 6674750
  22. TTBN - Evolutionäre Befahrbarkeitsprüfung • Das Fahrzeug startet von definierter

    Position und Ausrichtung • Das Fahrzeug folgt einer Leitlinie zum Ziel • Die Leitlinie ist eine Sequenz von X/Y Paaren und damit das GENOM • Eine Leitlinie pro Individuum
  23. TTBN - Evolutionäre Befahrbarkeitsprüfung • Bewertbarkeit (Teilaspekte) ◦ Keine Kollisionen

    mit Hindernissen (KO-Kriterium) ◦ Alle Räder sind auf Fahrbahn (KO-Kriterium) ◦ Eingehaltene Fahrzeugparameter (KO-Kriterium) ◦ Streckenlänge ◦ Lenkmanöver ◦ Ausrichtung an der Zielposition
  24. TTBN - Evolutionäre Befahrbarkeitsprüfung • Bewertbarkeit von Lösungen (Fitness) ◦

    Gewichtete Summe aus der Bewertung von Teilaspekten • Selektion von Lösungen ◦ Anhand der Fitness in Relation zur Summe aller Fitnesswerte ◦ Anhand der Position in der nach Fitness sortierten Liste ◦ Selektion des unfittesten Individuums muss möglich sein
  25. TTBN - Evolutionäre Befahrbarkeitsprüfung • Umsetzung mit eigener Implementierung ◦

    volle Flexibilität ◦ Klassen wie: Evolution, Population, Individual, Gene, ... ◦ Methoden wie: evolve, select, mutate, crossOver, … • Realisierung mit AWS Lambda (bis zu 32 Threads gleichzeitig) ◦ Hierarchie und Sequenz von Lambda-Prozessen
  26. Evolutionäre vs. Hochspezialisierte Algorithmen • Evolutionäre Algorithmen sind generischer ◦

    Liefern möglicherweise weniger gute Ergebnisse ◦ Brauchen teilweise länger als spezielle Algorithmen ◦ Aber: Nicht für jedes Problem existiert ein passender Optimierungsalgorithmus
  27. EA als Ergänzung ML und AI • Big Data treibt

    ML und AI voran ◦ Gute und umfangreiche Lern- und Prüfdaten notwendig ◦ Schwierig anpassbar, wenn Ergebnisse “gefühlt” nicht passen • Hohe Komplexität von ML und AI ◦ Für Machbarkeits-Untersuchungen ungeeignet
  28. Evolution, und weiter? • Stetige Analyse und Optimierung wichtig ◦

    Mutationsrate, Populationsgröße, Anzahl explorierte Generationen ◦ Fitnessfunktion ▪ SOO vs. MOO ▪ Neue Einflussfaktoren ▪ Gewichtung der Kriterien ◦ Performanz und Logging