evolutionäre Algorithmen

• i Info
• Literatur
• & Weicker, Karten: evolutionäre Algorithmen
<Website
• Taxonomie
• COMPUTATIONAL INTELLIGENCEorSOFT-COMPUTING
• NEURONAL NETWORKS
• EVOLUTIONARY ALGORITHMS
• EVOLUTIONARY PROGRAMMING
• EVOLUTIONS STRATEGIES
• GENETIC ALGORITHMS
• GENETIC PROGRAMMING
• FUZZY SYSTEMS
• Regeln "unscharf"
• Intelligente Systeme
• künstliche Intelligenz
• Turing-Test
• Anwender A sitzt vor Konsole
• kann kommunizieren mit Computer oder anderer Person, weiß dies aber nicht
• Idee: wenn A nicht unterscheiden kann ob Person
  am anderen Ende ein Mensch ist oder ein
  Computer, so gilt dieser Computer als intelligent
• Samuels Dame Programm
• Expertensysteme
• arbeitet symblisch
• ®gounding-problem
• fuzzy Systeme
• Regeln "unscharf"
• Neuronale Netze
• Neuronal Network Toolbox


• train-Funktion
• grafische Oberfläche
• "New Data" ®neue Daten für verschiedene Zwecke trainieren
• Eingaben
• Ausgaben (Soll) ® targets
• es öffnet sich das Fenster "Create New Data"
• Name des Netzwerks
• Typ
• Eingabeintervall
• get from Input:
  Bereich wird über bekannte Eingaben zugewiesen
• Neuronenanzahl
• Aktivierungsfunktion
• z.B. Hardlim
• Lernregel
• Button "Create" erzeugt dann Netzwerk
• Button "View" ®grafische Darstellung des aktuellen Netzwerks
• Button "Train" ®weiteres Fenster
• Eingabemuster
• Ausgabemuster
• Epochenzahl
• zu erzielender
  Gesamtfehler
• "Train Network" startet Trainingsvorgang
• Studium
• Einteilung
• feed forward
• einlagig, binär
• Perzeptron
• einfache lineare
  neuronale Netze
• zweischichtige / mehrstufige Systeme
• ®wie Perzeptron
• unterliegen anderen Lernparadigma
• konstruktive Charakteristika
• eine Eingabeschicht
• zustand der Einheiten
  wird von außen gesetzt
• eine Ausgabeschicht
• meist mehr als eine Ausgabeeinheit
• Zustand der Einheiten wird durch lineare Aktivierungsfunktion bestimmt
• Einsatzgebiet
• nicht Musterklassifikation wie bei Perzeptron
• sonder Musterassoziation
  und -Vervollständigung
• Autoassoziation
• Eingabe wird als Abrufschlüssel für ein Ausgabemuster interpretiert
• Assoziativspeicher
• verhalten sich wie inhaltsadressierbare Speicher
• Inhaltszugriff über einen Schlüssel
• Schlüssel wird gleichzeitig mit Schlüsseln aller
  gespeicherten Instanzen verglichen
• nicht
  sequentiell
• Inhalt wird in einem Arbeitsschritt gefunden
• aber:
• keine lokal gespeicherten Instanzen
• Information in Netz-Gewichten
• über alle Muster verteilt
• Kapazität nicht durch Größe, sondern durch lineare
  Ein- / Ausgabe-Transformation bestimmt
• Netz macht Fehler, soald
  diese überschritten wird
• können gewünschte
  Ausgabemuster produzieren trotz
• teilweise gestörter Eingaben
• unvollständiger Eingaben
• formales Modell
• Einheiten U = U_I + U_O
• U_I ,U_O ungleich leere Menge
• U_I geschnitten mit U_O = leere Menge
• Netzwerkstruktur W = U_I x U_O ®R
• nur Verbindungen von Eingabe- zur
  Ausgabeschicht
• keine Verbindungen
  zwschen Einheiten der selben Schicht
• A ordnet der Einheit u Î U eine Funktion A_U : R ®R zu
• berechnet a_u
• a_u = A_u(ex(u)) = ex(u)
• für alle u Î U_I
• a_v = A_v(net_v) = net_v+q_v
• für alle v Î U_O
• q= Bias / Schwellenwert
• Verallgemeinerung des Perzeptrons
• Aktivierungsfunktion unterschiedlich
• es kann mehr als eine Ausgabeeinheit geben
• Modelle:
• ADALINE
• eines der ersten linearen Netze
• vorgestellt von Widrow & Hoff
• ADAptive LInear NEuron


• lineares neuronales Netz mit
• o_v=1 falls a_v > 0,-1 falls a_v £ 0
• ex: U_I ® {-1,1}
• ähnlet dem Perzeptron
• aber
• lineare Aktivierungsfunktion
• Ausgaben mittels LS-Funktion
• aus {-1, 1} statt {0,1}
• Lernalgorithmus
• Widrow-Hoff-Regel
  (Delta-Regel)
• überwachte Lernregel
• Fehler einer Ausgabeeinheit =
  Differenz zwischen Aktivierung und Sollwert
• damit: Lernen auch
  möglich, wenn Ausgabe
  des ADALINEs korrekt ist:
• Gewichtsänderungen können so vorgenommen werden,
  dass Ausgabe des Systems auf aktuelle Eingabe bei
  sofortiger erneuter Propagierung korrekt ist
• dabei kann in späteren Epochen des Lernvorgangs trotz
  korrekter Klassifikation wieder ein Fehler E>0 auftreteten
  und ein Weiterlernen ermöglichen
• Schwellenwertbildung beim ADALINE erfolgt nach
  Aktivierung, die den Fehler bestimmt
• Deltaregel für beliebige
  lineare neuronale Netze
• Sei LN ein lineares NN
• Sei L' eine feste Lernaufgabe
• Gewichts- und Bias-Ändeung für uÎU_I und vÎU_O
• nach Propagierung der Engabe i^(p) des Musters pÎL'
• D_pW(u,v) = s (t_v^(p) - a_v^(p) )a_u^(p)
• D_pq_v = s (t_v^(p) - a_v^(p) )
• dabei:
• t_v^(p) = Sollaktivieung
• a_v^(p) = Istaktivierung
• ® (t_v^(p)-a_v^(p)) = Fehler der Einheit v
• s>0 heißt wieder Lernrate
• Diese D-Werte werden aufsummiert
• Änderung von W und q findet erst nach Ablauf einer Epoche statt
• DW(u,v) = P_pÎL' D_pW(u,v)
• Dq_v = P_pÎL' D_pq_v
• Ziel:
• Fehler für alle Einheiten minimieren
• durch Minimieren des globalen Fehlermaßes
• Anmerkung:
• Verzichtet man auf die Summierung der Einzelfehler,
  setzt die Lernrate auf 1 und passt die Gewichte nach
  der Propagierung des Musters an, so erreicht man
  bei sofortiger erneuter Präsentation dieses Musters
  eine korrekte Ausgabe
• Dieses Vorgehen verlängert aber den Lernvorgang
• mehrlagig
• Backpropagation-Netze
• Counterpropagation
• feed back
• deterministisch
• selbstorganisierend
• BSB
• Hopfield Netze
• bipolare Neuronen
• Aktivierungen aus {+1, -1}
• aber auch {0, +1} denkbar
• symmetrische Netzwerkstruktur
• Gewichte
• hemmend
• anregend
• je nach Vorzeichen
• nicht rückkopplungsfrei
• kein Neuron mit sich selbst verbunden
• Energiefunktion
• E_u:= -a_u((P_u'ÎU-u W(u',u)*a_u'-q_u)
• stell sicher, dass die Gesamtenergie nie zunimmt
• Änderungen von Aktivierungen haben
  Verringerung der Energie zur Folge
• ® Das Netz kommt nach endlich
  vielen Takten zur Ruhe
• Lernregeln für
  Hopfield-Netze
• direkte Berechnung
• über Ungleichungssysteme
• Simplex-Verfahren
• Problem: oft mehrere Lösungen!
• Hebb'sche Lernregel
• Þ Hebb'sches Lernen
• hier: Variation
• Variante der Widrow-Regel
• zu lernende Muster nacheinander an Netz anlegen
• jeweils bis Ruhephase erreicht
• Boltzmann-Maschine
• visomotorische
  Koodrination
  eines Roboterarmes
• Aufgabe
• Roboterarm positionieren
• so dass Gegenstand auf Arbeits-
  fläche gegriffenwerden kann
• Input
• 2 Kameras
• liefern 2d-Vektoren i₁ und i₂
• geben Position in der Bildebene der jeweiligen Kamera an
• (i₁,i₂) bestimmt Raumposition eindeutig
• vierdimensionale Eingabe
• Idee
• aus i = ( i₁,i₂ ) die Winkel q= (q₁,q₂, q₃) bestimmen
• Greifer über Gegenstand positionieren
• Erklärung
• 4-dimensionale Vektoren beschreiben
  Punkte einer Ebene
• ® typische Anwendung einer topologieerhaltenden Abbildung
• Dimensionsreduktion 4 ® 2
• Wettbewerbsneuronen
  planar angeordnet
• jedes für Erkennung einer Position
  auf der Arbeitsfläche zuständig
• Siegerneuron u_s
• verantwortlich für alle Zielpunkte i mit:
• || w^(u_s) - i || £ || w^(v) - i ||
• v = von u_s verschiedene Neuronen der Wettbewerbsschicht
• für jedes Neuron:
• Winkeleinstellung q^(v) für die Gelenke
• entsprechend Zuständigkeitsbereich zugeordnet
• (3 x 4)-Matrix A^(v)
• dient der Korrektur der Armwinkel
• falls i nicht exakt =w^(v)
• beide zu erlernen
• neuer Knoten
• Transformation q(i)
• abhängig von
• Geometrie des Roboterarms
• Kameras
• Stellung
• Abbildungscharakteristik
• soll selbstständig adaptiert werden
• führen in Zentrum des Zuständigkeitsbereiches von v_i
• bringen Greifer zur Position w^(v)
• nach Abschluss des Lernvorgangs
• Kohonen-
  Netze
• TSP-Problem
• Traveling Sales Person
• TSP, Handelsreisender
• Problembeschreibung
• Input
• N Städte
• Kosten @ Entfernungen
• Ziel
• alle Städte je einmal ansteuern
• Reisekosten minimieren
• Output
• Reihenfolge der Städte mit minimalen Wegstrecken
• Problem: ((N - 1) ! )/(2) Möglichkeiten
• Ansätze:
• Heuristiken
• inkrementelle Konstruierer
• lokale Optimierer
• greifen Untermenge
• optimieren diese Teilmenge
• "k-opt"-Regeln
• Kombinierte Methoden
• damit behandelbar:
• N<10⁴, wenn man maximal 1% vom Optimum abweichen will
• N<10⁶, wenn man maximal 4% vom Optimum abweichen will
• Idee: Netz von linear angeordneten Neuronen
• Kohonenalgorithmus analog zur selbstorganisierenden Karte
• dist(j, j*) := min ( |i - j*| , M-| i-j* |)
• dist(i-1,i) = dist(i,i+1) = 1
• dist(M,1) = dist (1,M) = 1
• s = Siegerneuron
• Dw_s(t) = s(t)×n_s(r,t)×(n-w_r^alt(t))
• n = Konstante der Stadt, für die Lernschritt gemacht wird
• s = Lernrate
• Nachbarschaft n_s(r,t) = (1-(dist(r;s)/L)^t falls dist(r;s) < L,0 sonst
• L = (N )/(2 )
• TSP
  Varianten
• dynamisch neue Stationen hinzufügen/löschen
• Start: Karte mit 1 Station
• Dupliziere Knoten, wenn er zweimal nacheinander
  Sieger war (bei einem Durchlauf durch die Städte)
• Lösche Knoten in Karte, wenn er im Verlauf
  von drei Durchläufen nicht einmal Sieger war
• n_s(r,t,k) = (1)/((2)^(1/2))e^{- (dist(r;s)²)/(k²)}
• Lernrate weglassen, dafür neuer Parameter k
• ® Nachbarschaftsfunktion erledigt
  Aufgabe der Lernrate mit:
• für k ®¥ alle Knoten bewegen sich in
  Richtung des Eingangssignals
• für k® 0 nur der der Sieger bewegt sich in
  Richtung des Eingangssignals
• Anwendungen in der Bioinformatik
• Sequenz- und Strukturalignment
• Proteinfaltung
• Lernen und Inferenz
• Mustererkennung / Feature selection
• siehe
• Mustererkennung
• Literatur
• Website
• Modelloptimierung / -anpassung
• Grundlagen
• wie betreibt man Wissenschaft?
• Vorgehen
• Messung
• Hypothese
• Modell
• Vorhersage
• ®Neue Messung/Beobachtung
• ® ist eine Art evolutionärer Prozess
• Wie sehen Probleme aus?
• viele Probleme können gelöst werden als
• Optimierungsproblem
• suchen der besten Lösungen aus einer Menge von möglichen Lösungen
• Q nicht jedes Problem ist ein Optimierungsproblem
• historisch:
• Leibnitz, 1710: die optimale Welt
• Darwin: Paleontologie
• siehe auch:
• Charles Darwin


• 1809-1882
• & the origins of species by means of natural selection
• 1859
• Begründer des
• Darwinismus
• Theore der natürlichen Auslese
• Individuen in einer Population variieren
• Überproduktion
• ® Selektion tritt ein
• Weitergabe der Variationen
• Beispiel
• Darwin-Finken


• Darwins Evolutionstheorie
• Variation innerhalb einer Population
• Variationen aufgrund genetischer Ursachen in bestimmten Merkmalen
• Merkmal vorteilhaft ® Reproduktionserfolg höher ® Verhalten wird an Nachkommen vererbt
• Merkmalsausprägungen verändern sich schrittweise
• Populationen mit verschiedenen Merkmalen ® nicht mehr kreuzungsfähig
• evolutionäre Kontinuität
• "Vater" der Verhaltensforschung
• Vorstellung vom Instinkt
• bedeutende Verhaltensbeobachtungen
• theoretisch kann JEDES Problem als Optimierungsproblemformuliert werden, dies ist aber nicht immer sinnvoll
• Arten der Optimierung
• Parameteroptimierung
• suche nach optimalen Parametern
• funktionale Optimierung
• suche nach geeigneter Funktion
• stehen in Beziehung: Funktionen können über Parameter angepaßt werden
• Zielfunktion: f:X ® G
• ordnet einer möglichen Funktion eine Güte zu
• Suchraum X
• Menge aller möglichen Lösungen
• oft mit
• Randbedingungen
• constraints
• Speziallfall: Vergleichende Zielfunktion
• erhält nur zwei mögliche Lösungen
• gibt eine vergleichende Wertung (Gütevergleich)
• Güte G
• z.B. Reelle Zahlen
• f:IRÞ IR
• mit Vergleichsoperator
• multikriteriell:
• mehrere Zielfunktionen
• i.d.R. ist G Í IRⁿ
• Zielfunktionen widersprechen sich
• Beispiel: suche x Î X, so dass f(x) optimal ist
• Beispiel: Suche Sequenz, die Protein ergibt, dass einem Zielprotein möglichst ähnlich ist


• oft auch fitness-function genannt
• i ist aber mehrdeutig belegt!
• ® möglichst nicht verwenden
• erweitert: Zielfunktion f:XÄC ®GÄI
• kontextabhängigKontext C
• I = zusätzliche Information,zum Beispiel Gradient
• Beispiel:
• Zielfunktion ist Abbildung IR®IR
• f(x) = x²
• Gradient = (df(x))/(dx)
• Klassifikation nach Zielfunktion
• deterministisch « stochastisch
• dynamisch « statisch
• dynamisch = zeitabhängig
• statisch = zeit-unabhängig
• diskret « kontinuierlich « gemischt ganzzahlig
• X selbst kann auch eine Funktion sein
• ® Suche nach eine optimalen Funktion
• Beispiel Akteinkurse:
• Suche nach einer geeigneten Funktion zur Vorausbestimmung von Aktienkursen
• x: IRⁿ ® {Kaufen , Nicht_Kaufen}
• beschränkt « unbeschränkt
• bezogen auf Qualitäts-/Wertebereich
• linear « nichtlinear
• lineares System
• Ausgangspunkt f: X®G
• sei f(x₁) = g₁, f(x₂) = g₂
• f ist linear, wenn f(x₁ + x₂) = g₁ + g₂ = f(x₁)+f(x₂)
• ® f(ax₁) = af(x₁)
• ® einfach zu handhaben
• manchmal auch gemeint:
• lineare Abhängigkeit von zwei Funktionen, die nicht linear sein müssen
• f(a+b)=f₁(a)+f₂(b)
• f₁, f₂ nichtlinear
• einfache Suchverfahren
• hill climbing
• start mit zufälligem Element des Suchraums
• mutiere dieses
• behalte das bessere von beiden und führe damit weitere Mutation fort
• Zufallssuche
• ziehe zufällig Element aus Scuhraum
• bewerte es
• ziehe weiteres Element ®bestes merken ...
• Problem: kein Verfahren ist besser
• ® NFL - Theorie
  (no free lunch)
• "jedes Suchverfahren ist gleich gut"
• was ist ein evolutionärer Algorithmus?
• Vorgehen


• erzeuge initiale Menge potenzieler Lösungen
• solange kein Abbruch:
• Wähle bestes Individuum s_best (beste Lösung) aus.
• Selektionsoperator S: Population ® Individuen
• erzeuge aus dem besten Individuum eine Menge von n-1 Mutanten
• Erzeuge neue Menge.
• Mutationsoperator M: Individuum ® Individuum
• Rekombinationsoperator R: Individuen ® Individuen
• Feststellung: Fortschrittsgeschwindigkeit nimt ab
• Genoty-Phänotyp-Abbildung
• Genotyp ®Phenotyp ®Güte
• über Dekodierung
• allgemeine Struktur eine Individuums
• Phänotyp: Raum W
• Genotyp: G = G₁ x G₂ x ... x G_l
• Strategieparameter
• liefern weitere Informationen
• z.B. Mutationswahrscheinlichkeiten
• weitere Begriffe
• Evolutionsstrategie
• Individuum: reellwertig
• Variationsoperatoren:
• Mutation
• Rekombination
• Selektion
• Unterscheidung nach
• Komma-Strategie
• Plus-Strategie
• Unterscheidung nach
• Umweltselektion
• nicht alle Kinder kommen in die Population der nächsten Generation
• Elternselektion
• auswählen von Eltern, die Nachkommen erzeugen dürfen
• Schrittweite: wie stark werden Nachkommen mutiert
• Mutation
• primärer Operator zur Erzeugung von neuen Suchpunkten
• Rekombination
• sekundärer Operator
• evolutionäre Programmierung
• ursprünglich zur Suche endlicher Automaten verwendet
• sollten Zeitreihen vorhersagen
• heute: ähnlich der Evolutionsstrategie
• keine Rekombination
• genetischer Algorithmus
• Genotyp: Bitstring
• Genotyp-Phänotyp-Abbildung
• Fitnessproportionale Selektion
• primärer Variationsoperator:
• Rekombination
• Hintergrundoperator:
• Mutation
• genetische Programmierung
• Züchten von Computerprogrammen
• Bei der Zielfunktionsauswertung wird Genotyp irgendwo als Computerprogramm interpretiert
• Variationsoperatoren
• Mutation
• Rekombination
• Grundelemente
• Suchraum
• Genotyp
• Phänotyp
• Repräsentation
• Fitnessfunktion
• Population
• Selektionsmethoden
• m,l-Selektion
• m+l-Selektion
• Fitnessproportionale Selektion
• Turnierselektion
• Variationsoperatoren
• Abbruchkriterium
• Meta-Anpassung
• Kausalität
• schwache
• Änderung der Eingabegröße führt (zu beliebiger) Änderung der Ausgabegröße
• starke
• Änderungen an Eingabegröße führen zu fast proportionaler Änderung der Ausgabegröße
• Dimensionen der Dynamik
• Phylogenie
• Zeitskala mit Fortschreiten der Entwickung von Nachfahren
• Ontogenese
• Ausbildung des "Rohgerüsts"
• Epigenese
• Anpassung / Lernen
• ® "POE-Modell"
• Mutation in evolutionären
  Strategien
• (m / r ,+ l) - Strategie
• m = Anzahl Eltern
• r = mixing number
• l = Anzahl Nachkommen
• y' = y + N(n, s)
• Addition einer normalverteilten Zufallszahl
• isotropisch: alle Raumrichtungen haben gleiche Priorität
• nicht-isotopisch:
• bestimmte Richtung in der Fitnesslanschaft wird bevorzugt
• geeignet, wenn Fitnessraum in bestimmte Richtung gestreckte Form hat
• Repräsentation durch Vektor y' = (y'1
  y'2)
• y'1 = y1+N(n, s₁)
• y'2 = y2+N(n, s₂)
• Rotationen möglich durch Multiplikation mit Rotationsmatrix
• Rekombination in
  evolutionären Algorithmen
• intermediär
• "weiche Variante"
• Bildung eines Mittelwertes für jede Koodinate des Individuums aus entsprechenden Koordinaten der Eltern
• = (1)/(m)P_i=1^my_i
• = Zentroid
• ^(g+1) = ^(g) +
• g = Generation
• = Mittel der Zufallsvektoren
• = (1)/(m)P_i=1^mz_ii^(g)l
• diskret
• für jede Koordinate wird zufällig ein Elter bestimmt, von welchem der Wert übernommen wird
• Vorteile
• building block hypothesis
• gute Eigenschaften verschiedener Individuen können zusammenkommen
• ist sehr kontrovers
• genetic repair effectandsimilarity extraction
• Probleme bei der Konvergenz
• Fitness wächst am Anfang schnell, ab einem bestimmten Niveau nur noch sehr Langsam
• Grund: Zufall macht zu große Sprünge
• ® wir brauchen Anpassung der Mutationsrate
• Meßzahlen
• Erfolgsrate
• success rate
• Wahrscheinlichkeit, dass man ein besseres Individuums erzeugt
• bei Erzeugung eines neuen Individuums
• Fortschrittsrate
• progress rate
• (erwarteter) Fortschritt des Verfahrens im Suchraum
• wie kommt man im Suchraum weiter
• =Abstand von einem Individuum zum Vorgänger
• Qualitätsgewinn
• quality gain
• beschreibt Fortschritt umgerechnet auf die Fitnessfunktion
• 1/5-Erfolgsregel
• verwendet, um bei einer (1+1)-Strategie die Mutationsstärke zu tunen
• Grundsatz: stelle Mutationsstärke so ein, dass Fortschrittsrate bei etwa 0.2 liegt
• wie?
• selbst-Adaption
• log-normal rule
• ein Sigma pro Individuum
• für alle Koordinaten gleich
• Anpassung gemäß: s'_l = f(s) = se^N(0,t)
• Streuung t @ (1)/((N)^(1/2)) ist ein heuristischer Wert
• Literatur
• Evolution strategies - Paper