Evolutionäre Algorithmen
DHBW Mannheim [Studiengang Informationstechnik]
DHBW Mannheim [Studiengang Informationstechnik]
-
- 1 / 48
-
Lernkarten
Was ist Evolution?
Verändung vererbbarer Merkmale (Genwerte) einer Population von Lebewesen
Was ist ein Chromosom?
- kodiert in Form von Genen (Teilstück eines Chromosoms)
- wird bei der Fortpflanzung kopiert und an die nächste Generation weitergegeben
Was ist Rekombination?
- Erweiterung der Vielfalt von vererbbaren Merkmalen
- durch: Verbindung von zwei (oder mehrerer) Individuen
Was ist Mutation?
- gerichteter Zufallsprozess
- dabei werden Alternativen/Varianten des vorhandenen Erbguts erzeugt
- neue Merkmale entstehen
Was ist Selektion?
- Ergebnis eines Zufallsexperiments
- bestimmte Merkmale werden vernichtet
- Selektion bestimmt die Richtung der evolutionären Veränderung
Evolution findet statt, durch ...
... die Genfrequenz --> bestimmt die Häufigkeit der Ausprägung einer Population
Evolutionäre Veränderung geschieht durch zwei Faktoren, nämlich ...
- Natürliche Selektion --> "survival of the fittest" (unterschiedliche Überlebens- und Reproduktionsrate der Merkmale)
- Gendrift (zufällig)
Die evolutionäre Veränderung wird durch zwei Faktoren beeinflusst. Was bewirken diese?
- verändern die Zusammensetzung des Genpools
- wirken dabei gleichzeitig
Wie können Evolutions-Prinzipien in der IT eingesetzt werden?
Prinzipien der Evolution können zur Problemlösung mit dem Computer verwendet werden
Wie werden "Probleme" mit Evolutionären Algorithmen gelöst (zwei Schritte)?
- Analyse des "Problems" (Struktur, Eigenschaften)
- Entwicklung eines entsprechenden Algorithmus
- Schritte 1 und 2 führen zur Lösung
Welche Herausforderung gibt es bei der Problemlösung durch Evolutionäre Algorithmen?
- Kosten- und Zeitaufwändig
- Struktur und Eingenschaften nicht immer erkennbar/gegeben
Was sind Evolutinäre Algorithmen aus der Sicht eines Ingenieurs?
- Prozess der Verbesserung
- dieser Prozess wird durch Algorithmen nachgeahmt
- Anwendung: Optimierungsprobleme
Für was steht das Omega Ω ?
Suchraum
Für was steht die Funktion f?
Für was steht der Parameter x der Gütefunktion f?
Lösungskandidat
Für was steht der Wert an der Stelle f(x)?
Gütewert
Was wird bei einem Optimierungsproblem gesucht?
globales Optimum der Bewertungsfunktion f
Nenne die vier Lösungsansätze zur Optimierung (AVBG)
- Analytische Lösung (effizient, selten verwendet)
- Vollständiges durchforsten des Suchraums (ineffizient, kleines Omega)
- Blinde Zufallssuche (ineffizient, keine gute Lsg)
- Gesteuerte Suche (nahe beieinander liegende Funktionswerte geben ähnliche Ergebnisse)
Zu welchen Verfahren gehören die Evolutionären Algorithmen und was sind die Herausforderungen?
- Verfahrensklasse: naturanaloge Verfahren (Bsp: neuronale Netzte)
- aufgrund technischer Begrenzung nicht 1:1 umsetzbar
Beispiel für EVA: Künstiliche Intelligenz
Welche drei Basisansätze für die Evolutinären Algorithmen gibt es?
- Evolutionsstrategien
- Genetische Algorithmen
- Genetische Programmierung
Was wird unter "Evolutionsstrategien" verstanden?
- (Eingangs-) Parameter sind kontinuierlich
- Mechanismen passen ihre Steuerungsparameter eigenständig an
Was wird unter "Genetische Algotithmen" verstanden?
Verwendung von binärer Codierung --> gut für kombinatorische Optimierung
Was wird unter "Genetische Programmierung" verstanden?
- nicht auf Parameteroptimierung ausgerichtet
- Idee: Computer-Programme automatisch generieren (Gen = Programmabschnitt)
- basierend auf Konzepten der Programmierung: Entwicklung von Computer-Programmen zur Aufgabenlösung
Wie sieht das allgemeine Grundgerüst eines Evolutionären Algorithmus aus?
- Suchraum festlegen & Gütefunktion definieren
- zufällige Startpopulation von Lösungen (Neuerschaffung)
- Genetische Operatoren anwenden (neue Generation)
- Selektion - beste Lösung wird in nächste Generation übernommen (Überlebensprüfung)
- Rekombination - Kreuzung zweier Lösungen (Vermehrung der Besten)
- Mutation - kleine & zufällige Änderung einer Lösung (Veränderung des Vorhandenen)
- neue Generation besteht immer aus besseren Lösungen
- Abbruchbedingung: Lösung ist ausreichend gut, kaum Änderungen (Ewiger Kreislauf)
Welchem Zweck dienen die Kanonischen Genetischen Algorithmen?
- Anpassungsfähigkeit (nach Bsp. der Evolution)
- Überprüfung für heutige Problemlösung verwenden
- schematisches, abstraktes Modell der biolog. Evolution
Was ist ein Individuum?
Repräsentant einer Lösung --> mathematisch ein Punkt im Suchraum
Was ist eine Population?
Menge an Individuen zu einem bestimmten Zeitpunkt t
Was wird als "Etern" bezeichnet?
aus einer Population augewählte Individuen zur Reproduktion
Was wird als "Kinder" bezeichnet?
aus den Eltern erzeugtes Individuum
Was ist mit "Fitness" gemeint?
Übereinstimmung des Individuums mit gegebenen Eigenschaften (basierend auf Bewertungsfunktion)
Sicht der Biologie und IT: Chromosom
Bio: festgelegter Bauplan eines Lebewesens
IT: Zeichen- oder Zahlenkette ohne feste Länge
Sicht der Biologie und IT: Gen
Bio: Teilstück eines Chromosoms --> Augenfarbe
IT: Character (Abschnitt eines Strings)
Sicht der Biologie und IT: Allel
Bio: Ausprägung des Gens (z.B. Augenfarbe ist blau)
IT: konkreter Wert eines Zeichens oder einer Zeichenkette
Sicht der Biologie und IT: Lokus
Bio: Ort eines Gens im Chromosoms
IT: Position eines Zeichens (Index)
Sicht der Biologie und IT: Phähnotyp
Bio: Erscheinungsbild des Lebewesens
IT: Chromosom-codierte Problemlösung (Gitter: gleicher Weg, obwohl andere Anordnung)
Sicht der Biologie und IT: Genotyp
Bio: Erscheinungsbild des Chromosoms
IT: unterschiedliche Genotypen können selben Phänotyp haben (verschiedene Wegpunkte des Gitters --> können trotzdem gleichen Weg besitzen)
Sicht der Biologie und IT: Reproduktion
Bio: Erzeugen von Nachkommen aus einem oder mehreren Lebewesen
IT: Erzeugen von Chromosomen aus einem oder mehreren Chromosomen
Welche Struktur haben Evolutionäre Algorithmen?
haploide Strukturen: pro Zelle ein Chromosom als Lösung
Welche Struktur finden wir in der Natur?
diploide Struktur: zwei gleiche Allele oder ein dominanteres und ein rezessives
Was unterscheidet die Begriffe Chromosom und Individuum?
Chromosom: Betrachtung der Erbinformation
Individuum: Betrachtung der einzelnen Lösung einer Population z.B. zur Kreuzung
