Evolutionäre Algorithmen

DHBW Mannheim [Studiengang Informationstechnik]

DHBW Mannheim [Studiengang Informationstechnik]

48

0.0 (0)

H. L.

Study

H. L.

About these flashcards

Diese Lernkarten behandeln evolutionäre Algorithmen auf Universitätsniveau und konzentrieren sich auf die Grundlagen der Codierung, Mutation, Rekombination und Selektion. Sie erklären die Struktur und Funktion von Chromosomen, Individuen und Populationen sowie die Anwendung dieser Prinzipien in der Informatik und Biologie. Die Karteikarten sind ideal für Studierende und Forscher, die sich mit Problemlösungsstrategien und Optimierungsverfahren auseinandersetzen, da sie die theoretischen Konzepte und praktischen Anwendungen dieser Algorithmen vermitteln.

Flashcards

48

Students

2

Language

German

Category

Computer Science

Level

University

Created / Updated

10.05.2016 / 10.05.2016

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

Wie funktioniert die Rekombination?

auch Cross-Over genannt
Eltern-Chromosome werden am Cross-Over-Point aufgetrennt
Teilstücke werden ausgetauscht (Überkreuzt zusammengesetzt)
Ergebnis: große Unterschiede zwischen Eltern und Kind

Welche Arten der Mutation gibt es und wie funtionieren diese?

Mutation = Veränderung der Vorhandenen
Genmutation: vernachlässigbare oder deutliche Auswirkung
Chromosomen-Mutation: Verdopplung von Teilketten (Umbau oder Verlust)
Genom-Mutation: Änderung der Gen- oder Chromosomenzahl

Was bedeutet Codierung?

Darstellung eines Chromosoms in einer speziellen Form z.B. binär oder Zeichenkette

Die Codierung hat ein Alphabet was ist zu beachten, wenn dieses zu groß ist?

hoher Rechenaufwand, da nicht lösungsrelevante Bereiche durchsucht werden

Die Codierung hat ein Alphabet was ist zu beachten, wenn dieses zu klein ist?

gute Lösungen können evtl. nie erreicht werden --> konvergiert zu schnell

Welche Codierung liefert schnelle und genaue Lösungen?

Ganzzahl / reelwertige Codierung, mehr als binäre

Was ist der Gray Code?

Veränderte Struktur der Fitness Landschaft
Schrittweise zu Folgeelement (Heming Distanz) immer 1 Mutationsschritt

Was ist der Vorteil des Gray Code?

Bei Mutationsschritten ändert sich nur ein Bit, wenn man beispielsweise im dezimalen Zahlenraum aufsteigend zählt.

Nützlich für: Nachbarschaftsbeziehungen zwischen Mutationen darstellen

Was ist Evolution?

Keyboard commands:

= turn,

= for-/backward,

= scroll

Verändung vererbbarer Merkmale (Genwerte) einer Population von Lebewesen

Was ist ein Chromosom?

Keyboard commands:

= turn,

= for-/backward,

= scroll

kodiert in Form von Genen (Teilstück eines Chromosoms)
wird bei der Fortpflanzung kopiert und an die nächste Generation weitergegeben

Was ist Rekombination?

Keyboard commands:

= turn,

= for-/backward,

= scroll

Erweiterung der Vielfalt von vererbbaren Merkmalen
durch: Verbindung von zwei (oder mehrerer) Individuen

Was ist Mutation?

Keyboard commands:

= turn,

= for-/backward,

= scroll

gerichteter Zufallsprozess
dabei werden Alternativen/Varianten des vorhandenen Erbguts erzeugt
neue Merkmale entstehen

Was ist Selektion?

Keyboard commands:

= turn,

= for-/backward,

= scroll

Ergebnis eines Zufallsexperiments
bestimmte Merkmale werden vernichtet
Selektion bestimmt die Richtung der evolutionären Veränderung

Evolution findet statt, durch ...

Keyboard commands:

= turn,

= for-/backward,

= scroll

... die Genfrequenz --> bestimmt die Häufigkeit der Ausprägung einer Population

Evolutionäre Veränderung geschieht durch zwei Faktoren, nämlich ...

Keyboard commands:

= turn,

= for-/backward,

= scroll

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?

Keyboard commands:

= turn,

= for-/backward,

= scroll

verändern die Zusammensetzung des Genpools
wirken dabei gleichzeitig

Wie können Evolutions-Prinzipien in der IT eingesetzt werden?

Keyboard commands:

= turn,

= for-/backward,

= scroll

Prinzipien der Evolution können zur Problemlösung mit dem Computer verwendet werden

Wie werden "Probleme" mit Evolutionären Algorithmen gelöst (zwei Schritte)?

Keyboard commands:

= turn,

= for-/backward,

= scroll

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?

Gütefunktion

Suchraum

Bewertungsfunktion

Gütewert

Gütefunktion

Suchraum

Bewertungsfunktion

Gütewert

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

1 / 48

Flashcards

Wie funktioniert die Rekombination?

auch Cross-Over genannt
Eltern-Chromosome werden am Cross-Over-Point aufgetrennt
Teilstücke werden ausgetauscht (Überkreuzt zusammengesetzt)
Ergebnis: große Unterschiede zwischen Eltern und Kind

Welche Arten der Mutation gibt es und wie funtionieren diese?

Mutation = Veränderung der Vorhandenen
Genmutation: vernachlässigbare oder deutliche Auswirkung
Chromosomen-Mutation: Verdopplung von Teilketten (Umbau oder Verlust)
Genom-Mutation: Änderung der Gen- oder Chromosomenzahl

Was bedeutet Codierung?

Darstellung eines Chromosoms in einer speziellen Form z.B. binär oder Zeichenkette

Die Codierung hat ein Alphabet was ist zu beachten, wenn dieses zu groß ist?

hoher Rechenaufwand, da nicht lösungsrelevante Bereiche durchsucht werden

Die Codierung hat ein Alphabet was ist zu beachten, wenn dieses zu klein ist?

gute Lösungen können evtl. nie erreicht werden --> konvergiert zu schnell

Welche Codierung liefert schnelle und genaue Lösungen?

Ganzzahl / reelwertige Codierung, mehr als binäre

Was ist der Gray Code?

Veränderte Struktur der Fitness Landschaft
Schrittweise zu Folgeelement (Heming Distanz) immer 1 Mutationsschritt

Was ist der Vorteil des Gray Code?

Bei Mutationsschritten ändert sich nur ein Bit, wenn man beispielsweise im dezimalen Zahlenraum aufsteigend zählt.

Nützlich für: Nachbarschaftsbeziehungen zwischen Mutationen darstellen

1
2

Study