1

VorlesungEvolutionäre Algorithmen

Vorschlag für Prüfungskriterien: � Bearbeitung einer praktischen (Programmier-) Aufgabe� Fachgespräch – einzeln (15 min) bzw. Modulprüfung (30 min)

Dr. Nicole Drechsler, AG RechnerarchitekturRaum 3480, Tel. 7391, nd@tzi.de

2

Literatur� K. Weicker: Evolutionäre Algorithmen, Teubner Verlag, 2002� W. Kinnebrock: Optimierung mit Genetischen und Selektiven

Algorithmen, Oldenbourg Verlag, 1994

� Sekundärliteratur:� Originalarbeiten� Bücher von J. Holland (1975), D. Goldberg (1989), J. Koza (1992),

Z. Michalewicz (1994), E. Schöneburg (1994)� T. Bäck et. al.: Handbook of Evolutionary Computation, Oxford

University Press, 1997

3

GliederungKapitel 1: Einführung in Evolution und OptimierungKapitel 2: Evolution als OptimierungsprinzipKapitel 3: Prinzipien Evolutionärer AlgorithmenKapitel 4: Evolutionäre Standardalgorithmen

Genetische AlgorithmenEvolutionstrategienEvolutionäre ProgrammierungGenetische Programmierung

Kapitel 5: Problemspezifische Verfahren Kapitel 6: Aktuelle Entwicklungen und Erweiterungen

4

Optimierungsverfahrentreten in fast allen � technischen,� naturwissenschaftlichen,� wirtschafts- und gesellschaftswissenschaftlichen Anwendungen

aufEffiziente und robuste Optimierungsverfahren sind von

großer praktischer Bedeutung

Exakte mathematische Optimierungsverfahren existieren für eingeschränkte Modellklassen, z.B.

� Lineare Probleme (Simplexverfahren)� Branch&Bound� ...

5

Notation� Evolutionäre Algorithmen (EAs) Oberbegriff von

� Genetischen Algorithmen (Holland)� Evolutionsstrategien (Rechenberg/Schwefel)� Evolutionärer Programmierung (Fogel)� Genetischer Programmierung (Koza)� hybriden Verfahren� ...

� Unabhängig entwickelt seit 60er Jahren

6

Viele reale Probleme sind nicht exakt optimierbar!

Heuristiken (griech. heureka)� Numerische Verfahren (mit und ohne Kenntnis der

Ableitungen), z.B. Gradientenverfahren� Probabilistische Verfahren

� Die Ansätze garantieren nicht, dass ein globales Optimum gefunden wird!

� Evolutionäre Algorithmen gehören zur Klasse der probabilistischen Verfahren, die um die Ideen aus der Evolution erweitert werden. � Selektion von Lösungen und deren� Veränderungen sind zufallsgesteuert.

7

Das steigende Interesse an naturanalogen Verfahren ist bedingt durch

� den erfolgreichen Einsatz der Verfahren in vielen realen Anwendungen

� die einfache Umsetzung vieler naturanaloger Verfahren

Aber:� Naturanaloge Verfahren sind kein Allheilmittel

� d.h. sie sind kein Black-Box Optimierungsverfahren� genaue Analyse der Problemstellung ist notwendig� Aussagen über die Qualität der Lösung sind idR nicht

möglich� Kenntnisse über Mathematik und Stochastik sind

notwendig

8

Optimierung� Finden eines Minimums

� Schwierige Probleme� polynomielle bzw. schnelle Algorithmen nicht bekannt

9

Zufälliges Bestimmen � Raten einer Lösung

� Einfache Methode� schnell� häufig schlechte Ergebnisse

10

Greedy-Verfahren� Lokales Verbessern einer Startlösung

� Schnelle Methode � Erreichen eines lokalen Minimums� Abhängig von Startpunkt

11

1. Einführung in die Evolution und Optimierung

� Optimierungsverfahren� Idee: Betrachte mehrere Lösungen� Motivation durch Beobachtungen in der Natur

� Lösungen sind Individuen einer Population� Erzeugen neuer Individuen � Selektion der besser angepassten Lösungen

� Anpassung wird durch Bewertung der Individuen gemessen

� Weiterentwicklung erfolgt durch einen simulierten Evolutionsprozess

survival of the fittest

12

Prinzipien der biologischen Evolution

� Die Beschreibung der Evolutionsmechanismen erfolgt stark vereinfacht, wie sie für das Verständnis Evolutionärer Algorithmen erforderlich ist.

� Die realen Abläufe sind deutlich komplexer und nur teilweise bekannt.

� Die Mechanismen der natürlichen Evolution sind selbst Resultat der Evolution.

� Biologische Evolution ist die Veränderung des Lebens durch Selektion und Variation des genetischen Materials.

13

Biologischer HintergrundErste Erkenntnisse der Evolution basieren auf den

Arbeiten von Charles Darwin (1859):

� Natürliche Selektion bevorzugt Spezies, die besser an ihre Umgebung angepasst sind

� Spezies unterliegen zufälligen Modifikationen (Mutationen)� Nachkommen entstehen durch Fortpflanzung unter Mischen

der Erbinformationen

14

Evolution und GenetikSpezies bzw. Individuen sind durch ihre genetische

Information definiert

� Vollständige genetische Information wird als Genotypbezeichnet,

� einzelne Individuen als Phänotyp.

Die Evolution bzw. die Selektion findet auf Ebene der Phänotypen statt.

in den Genen kodiert

15

Bauplan eines Organismus� In der DNA kodiert (desoxyribonucleic acid)

� String-artiges Molekül bestehend aus Nukleotiden mit den Basen

Adenin (A)Cytosin (C) Guanin (G) Thymin (T)

16

Bauplan eines Organismus (Cont)� Basenpaare bilden die Verbindungen zwischen den

Strängen � Alle Verbindungen sind vom Typ T-A oder G-C

ein Strang ist aus dem anderen ableitbarRedundanz und Fehlertoleranz

� Während der Zellteilung werden die Stränge aufgespalten, so dass die Information repliziert werden kann (Selbstreplikation der DNA).

17

Vom Genotyp zum Phänotyp� DNA ist Informationsträger� Aufbau des Organismus (Phänotyp) aus dem Bauplan (Genotyp)� Auf Zellebene besteht dieser Schritt aus der Proteinbiosynthese� Proteine sind Ketten von Aminosäuren� 20 unterschiedliche Aminosäuren bilden die Buchstaben, aus

denen Wörter (Proteine) gebildet werden � Ein Gen ist Teil der DNA, der Informationen zur Synthese eines

Proteins enthält. � Wert eines Gens nennt man Allel

18

Schritte der ProteinsyntheseDNA (m)RNA ProteinRNA (engl. ribonucleic acid) ist ein einstrangiges Molekül, das

� mit Enzymen interagieren kann und� aus der DNA entsteht

Übersetzungstabelle DNA – RNA

AA-T

CC-G

UT-A

GG-C

RNABasenpaar der DNA

Uracil(U) ersetzt in der RNA das Thymin (T) der DNA

19

RNA-Information ist gemäß des sog. Genetischen Codesin der mRNA gespeichert

Jeweils 3 Nukleotide bestimmen eine Aminosäure in der Aminosäuresequenz eines Proteins

Mit 3 Nukleotiden und 4 Basen können 43 = 64 Aminosäuren kodiert werden

gute Fehlerredundanz

Jede Aminosäuresequenz beginnt mit einem Start- und endet mit einem von drei Stopp-Zeichen

20

Genetischer Code

UCAG

CysCys

(stop)Trp

TyrTyr

(stop)(stop)

Ser

PhePheLeuLeu

U

UCAG

SerSerArgArg

AsnAsnLysLys

Thr

IleIleIle

Met (start)

A

Val

Leu

U

Zweites Nukleotid

Ala

Pra

C

AspAspGluGlu

HisHisGlnGln

A

UCAG

GlyG

UCAG

ArgC

G

Drittes Nukleotid

Erstes Nukleotid

21

Schematischer Ablauf der Proteinbiosynthese

� Struktur der DNA� Aufspalten der DNA durch

Enzyme (RNA-Polymerase) � Selbstreplikation durch

Ergänzung der einzelnen Stränge unter Mitwirkung von Enzymen (Bildung der m-RNA)

22

Proteinbiosynthese (Cont)

� m-RNA wandert aus dem Zellkern in das Zellplasma

� Ribosomen lagern sich an die m-RNA

� An jedem Ribosom entsteht eine Polypeptidkette (Protein) aus der Verknüpfung einzelner Aminosäuren (Zuordnungsvorschrift des genetischen Codes)

� Die Aminosäuren werden von spezifischen t-RNAs herangeschafft

23

Evolution auf Zellebene

� Fehlerrate bei Zellteilung liegt bei 10-10 bis 10-11

� Stabile Erhaltung der Informationen � Wichtig für Erhaltung von

Eigenschaften

� Weniger Spielraum für Evolution� Wichtig für Erreichen von

Verbesserungen

24

Evolution auf Zellebene (2)

� Selektionsvorteile durch Sexualität als evolutions-beschleunigender Mechanismus ?

� Rekombination des Erbguts der Eltern

Keimzellender Eltern

Kinderorganismus

Keimzellender Kinder

25

Evolutionsprinzip� Evolution findet in einer Population von Individuen

statt� Änderung der Häufigkeiten von Allelen durch

Selektionsvorteile� Elternselektion� Umweltselektion

� Fehler bei der Reproduktion der DNAMutation

� Neukombination des genetischen Materials der Eltern Rekombination

26

Evolutionsprinzip� Evolution findet in einer Population von Individuen

statt� Änderung der Häufigkeiten von Allelen durch

Selektionsvorteile� Elternselektion� Umweltselektion

� Fehler bei der Reproduktion der DNAMutation

� Neukombination des genetischen Materials der Eltern Rekombination

27

Mutation� Fehler bei der Reproduktion der DNA� Mutationswahrscheinlichkeiten

� MenschWahrscheinlichkeit einer Mutation 10-10

Genom mit etwa 105 Genen und 104 Bausteine je GenErgibt Mutationswahrscheinlichkeit von 10-1 pro Zellteilung

� Viele Veränderungen haben keine Auswirkungen oder sind rezessiv

� Mutationen sind Grundlage für Modifikationen im Evolutionsprozess� Einzelne Veränderungen sind sehr klein� Große Veränderungen sind Summe vieler kleiner Veränderungen� Große Veränderungen in einem Schritt sind idR schlecht

Wechselwirkungen zwischen den Komponenten

28

Evolutionsprinzip� Evolution findet in einer Population von Individuen

statt� Änderung der Häufigkeiten von Allelen durch

Selektionsvorteile� Elternselektion� Umweltselektion

� Fehler bei der Reproduktion der DNAMutation

� Neukombination des genetischen Materials der Eltern Rekombination

29

Rekombination� Neu-Kombination des genetischen Materials der

Eltern (kein Evolutionsfaktor aus Sicht der klassischen Evolutionslehre)

� Es entsteht keine neue Information bzw. Eigenschaften, die vorhandene Information wird neu gemischt

� Neuere Forschungen lassen vermuten, dass durch Rekombination erzeugte Allele für den Evolutionsprozess wichtiger sind als die durch Mutationen erzeugten

30

Selektion und Fitness

� Veränderung der Häufigkeit von Allelen durch unterschiedlich viele Nachkommen der einzelnen AlleleUrsachen:� Unterschiedliche Überlebenschancen� Unterschiedliche Fortpflanzungsrate� Unterschiedlicher Erfolg bei der Partnersuche� Unterschiedliche Länge der Generationsdauer

� Selektionsmaß ist gegeben durch Fitnesswerte der Genotypen� Relative Fitness eines Genotyps G ist definiert über Anzahl der

überlebenden Nachkommen in einer PopulationFitness(G) = #Nachkommen(G)/#Nachkommen(G‘)

mit G‘ bester Genotyp in Population

31

� Selektion ist kein reiner Auswahlprozess, der jeweils nur die vorteilhafteste Form auswählt

� Mögliche Gründe:� nur geringfügige Selektionsunterschiede der Phänotypen� oder unterschiedliche Selektionsvorteile bei wechselnden

Umweltbedingungen� Rezessive Allele:

A dominant, a rezessivAa und AA haben den gleichen PhänotypenAa kann Vorteile gegenüber AA haben, so dass aa immer wieder

entstehen kann� Räuber-Beute Systeme (Selektionsvorteile von

Minderheitsphänotypen)� Polymorphe Population hat

� mehr Potential zur Anpassung � bessere Überlebenschance

Polymorphismus

32

Genfluss� Genhäufigkeiten ändern sich durch Zu- und

Abwandern von Individuen in einer Population

� Durch Austausch von Individuen zwischen den (isolierten) Teilpopulationen entsteht ein Genfluss

� Getrennte Population können sich auseinander entwickeln

� Entstehung neuer Arten ohne Genfluss� Geographische oder zeitliche Trennungen

Teilpopulationen

33

Gendrift� Alle Allele einzelner Gene sterben durch Zufallseffekte

aus� Bewirkt Reduktion der Vielfalt in einer Population� Vor allem in kleinen Populationen (<1000) ist

Gendrift ein wesentlicher Evolutionsfaktor� Evolutionsbeschleunigung durch Gendrift und

Genfluss?� Keine Relevanz in großen Populationen

34

Nischenbildung� Aufteilung der Umwelt an verschiedene Arten� Jeder nutzt die vorhandenen Ressourcen auf eigene

Art und Weise für Wachstum und Ernährung� Bei Überschneidung der Nischen werden

Selektionsmechanismen aktiv und stellen Gleichgewicht wieder her

Genfluss/Gendrift Nischenbildung� Evolution ökologischer Beziehungen

� Wechselwirkungen zwischen Änderungen der unterschiedlichen Arten Koevolution

35

Selektionsvorteil durch Lernen?(Widerlegte) Theorie von Lamarck (1809):

Baldwin-Effekt: Vererbung von spezifischen Lernfähigkeiten durch Selektionsvorteile (1896):

Genotyp 1

Phänotyp 1

Genotyp 2

bestimmt bestimmtLernen

Genotyp 1

Phänotyp 1 Phänotyp 2

Genotyp 2

Phänotyp 1 Phänotyp 2

bestimmt bestimmt

Lernen Lernen

Evolution

Baldwin-Effekt

Phänotyp 2

36

Evolution und Optimierung� Evolutionsprozess:

� lässt angepasste Individuen entstehen und passt sie dynamisch geänderten Umweltbedingungen an

� erhält Diversität im Genpool

� Mechanismen der Evolution sind zufallsgesteuert (Mutation, Selektion, Rekombination)

� Evolution optimiert die Entwicklung von Spezies

Können die erfolgreichen Konzepte der Evolution auch im Zusammenhang mit mathematischen

Optimierungsproblemen genutzt werden?