Wer entwickelte die Evolutionstheorie? Was beschreibt diese? Was sind ihre wesentlichen Bestandteile?
Die Evolutionstheorie wurde von Charles Darwin entwickelt. Sie beschreibt die Entwicklung von Lebewesen als Optimierungsprozeß mit folgenden Elementen:
Wann und von wem wurden evolutionäre Optimierungsverfahren für technische Systeme angewandt?
Nach ersten Entwicklungen um 1960 nutzten 1963 I. Rechenberg und H.-P. Schwefel an der Evolution nachgeahmte Verfahren zur Optimierung von strömungstechnischen Anwendungen.
Daraus entstanden die Evolutionsstrategien als allgemeine Optimierungsverfahren
Wie lassen sich Evolutionäre Algorithmen einteilen?
Man kann sie in Evolutionsstrategien und genetische Algorithmen einteilen
Wie wird bei Evolutionsstrategien die Ausprägung eines Individuums dargestellt?
Die Ausprägung wird als Zahlenvektor dargestellt, der durch kleinere Änderungen mutiert werden kann
Was unterscheidet die genetischen Algorithmen von den Evolutionsstrategien?
Die Informationen werden bei genetischen Algorithmen angelehnt an die DNA codiert dargestellt. Dabei sind verschiedenste Codes zulässig.
Ein weiter Unterschied besteht darin, dass die Mutation hier eine untergeordnete Rolle spielt. Dafür wird die Rekombination verwendet die die Eigenschaften der Eltern kreuzt wie es von höheren Lebewesen bekannt ist.
Rekombination = Kombination von Teilen der DNA der Eltern (Cross-Over)
Was sucht man im Allgemeinen bei Optimierungsaufgaben?
Im Normalfall sucht man das (globale) Minimum bzw. Maximum einer Funktion, die den zu optimierenden Sachverhalt bewertet. Zum Beispiel eine Funktion, die von den zu optimierenden Parametern abhängt
Was ist der Unterschied zwischen unimodalen und multimodalen Funktionen?
Unimodale Funktionen haben nur ein Extremum. Multimodale haben mehrere Minima und Maxima. Hier unterscheidet man zwischen globalen und lokalen Extrema
Wann ist die Durchführung der Optimierung am einfachsten?
Die Lösung der Optimierungsaufgabe ist am einfachsten zu berechnen, wenn das Minimum der Gütefunktion analytisch zu bestimmen ist. Dazu muss der Gradient der Funktion analytisch ermittelbar sein
Mit welchen Verfahren kann man das Minimum iterativ bestimmen?
Zur iterativen Bestimmung des Minimums verwendet man Hill-Climbing- Strategien. Diese tasten sich schrittweise von einem Startpunkt an Extrema heran.
Was sind Restriktionen bzw. restringierte Minimierungsaufgaben?
Restriktionen sind Nebenbedingungen, die das Gebiet in dem das gesuchte Minimum liegen darf begrenzen. Sie werden durch Ungleichungen der Form u_min ≤ u(x) ≤ u_maxausgedrückt.
Restringierte Minimierungsaufgaben lassen sich mit im linearen Fall mit dem Simplexalgorithmus lösen. Bei quadratischen Funktionen wird das Verfahren von Wolfe eingesetzt
Mit welchem Trick kann man restringierte Minimierungsaufgaben mit normalen Hill-Climbing-Verfahren lösen?
Um restringierte Minimierungsaufgaben mit normalen Hill-Climbing-Verfahren zu lösen, wandelt man sie in unrestringierte Aufgaben um. Dazu bedient man sich so genannter Barrierefunktionen.
Diese werden so gewählt, dass sie am Rand des erlaubten Bereiches gegen ∞ gehen und dann zu der zu minimierenden Funktion addiert. Das sorgt dafür, dass sich das Minimum nur in diesem Bereich befinden kann
Wie wählt man dabei den Wert p?
Bei kleineren Werten für p ist die Barrierefunktion an den Rändern steiler.
Da dies aber auch zu Konvergenzproblemen führen kann, ermittelt man x zuerst mit großen Werten für p. Das ermittelte Minimum dient dann als Startpunkt x_0 für Berechnungen mit niedrigerem p.
Wie geht man vor, wenn der Abstieg entlang des Gradienten fast nur in eine Richtung verläuft?
Man kann entweder die Schrittweitensteuerung dimensionsweise durchführen oder sie vom Gradienten unabhängig machen.
Alternativ ist es möglich die Eingangsgrößen zu skalieren, so dass die Höhenlinien kreisförmig werden und so der Abstieg in alle Richtungen gleich verläuft: z = T*x
Welche Eigenschaften eines mathematischen Zusammenhangs können optimiert werden?
Man kann sowohl die Parameter als auch die Struktur eines Zusammenhangs optimieren. Beispielsweise die Koeffizienten einer DGL und die Anzahl der auftretenden Ableitungen. Man spricht von Parameter- und Strukturoptimierung.
Außerdem gibt es die kombinatorischen Optimierungsaufgaben. Bei diesen wird die optimale Kombination diskreter Möglichkeiten gesucht. Beispiel sind hier das Travelling-Salesman-Problem oder Maschinenbelegungspläne
Wodurch wird bei den Evolutionsstrategien ein Individuum repräsentiert?
Individuen werden durch einen reellwertigen Vektor x (Eigenschaften) und einen Vektor von Standardabweichungen σ (Mutationsweiten) repräsentiert. Die Mutationsweiten entsprechen dabei quasi der Schrittweite.
Da dieser Vektor mit mutiert wird, entsteht eine adaptive Schrittweitensteuerung.
In welchen Schritten verläuft eine Evolutionsstrategie?
Ausgehend von µ Eltern werden λ Nachkommen leicht mutiert erzeugt (Reproduktion). Die µ Individuen mit dem kleinsten Gütewert werden selektiert. Dies wird so lange wiederholt bis sich die Gütewerte des besten und schlechtesten Individuums um einen vorgegebenen Wert ε unterscheiden.
Wenn man auch bei den Evolutionsstrategien die Rekombination einsetzt, verbessert sich ihr Konvergenzverhalten
Wie werden die Eltern in der Startphase verteilt? Wie werden ihre Mutationsweiten gewählt?
Die Eltern werden in der Startphase zufällig über den Suchraum verteilt.
Das steigert die Wahrscheinlichkeit das globale Minimum zu finden.
Die Mutationsweiten dürfen weder zu groß noch zu klein sein, da sonst da Konvergenzverhalten unstetig wird oder die Fitnessfunktionswerte abnehmen.
Welche Formen der Rekombination können hier angewendet werden?
Man unterscheidet die diskrete und die intermediäre Rekombination. Bei der diskreten Rekombination werden die zu vererbenden Komponenten zufällig aus denen der Eltern ausgewählt.
Für die intermediäre Rekombination wählt man 2 der µ Eltern zufällig aus.
Ihr Nachkomme erbt dann die Mittelwerte ihrer Eigenschaften.
Am günstigsten hat es sich dabei erwiesen x diskret und σ intermediär zu rekombinieren
Wie erfolgen Reproduktion und Mutation?
Entweder durch Rekombination der Eltern und anschließendes Mutieren oder durch Mutieren von Klonen.
Zur Mutation werden zuerst die Mutationsweiten erst global dann lokal über normierte Normalverteilungen variiert. Im Anschluß werden die Werte x_i über µ mutiert.
Welche Rolle spielt die Wahl der Mutationsweiten für das Konvergenzverhalten?
Je nach Wahl der Mutationsweiten kann das Verfahren stagnieren oder zum reinen Suchverfahren (Chaos) entarten. Das Optimum der Mutationsweiten liegt irgendwo dazwischen im so genannten Evolutionsfenster. Dieses wird im Fortschrittgeschwindigkeits-Mutationsweiten-Diagramm besonders anschaulich dargestellt
Welche Möglichkeiten ergeben sich für Bewertung und Selektion?
Die Individuen mit den niedrigsten Gütewerten bilden die Eltern der nächsten Generation. Die Auswahl kann dabei mit oder ohne Aussterben der Eitern erfolgen.
Welches Abbruchkriterium wird verwendet?
Wenn die relative Differenz zwischen den Individuen mit dem besten und dem schlechtesten Gütewert einen vorgegebenen Wert unterschreitet, wird abgebrochen. Die relative Differenz ist der Betrag der normalen Differenz der Gütewerte geteilt durch den Gütewert des besten Individuums.
Problem dieses Kriteriums ist, dass es teilweise in flachen Ebenen grundlos stoppt. Deshalb ist es oft sinnvoll die Verbesserung der Gütewerte über mehrere Generationen zu beobachten.
Ein anderes Abbruchkriterium kann auch die Rechenzeit sein (z.B. wenn sie bezahlt werden muss).
Wie kann sich der Gütewert bei (µ+λ)- Strategien ändern? Wie bei (µ,λ)?
Bei (µ+λ)-Strategien kann der Gütewert nur gleich bleiben oder abnehmen. Bei (µ,λ)-Strategien kann er auch zunehmen.
Wie wirkt sich eine hohe Zahl zu optimierender Parameter aus?
Die Zahl n der zu optimierenden Parameter entspricht der Dimension des Suchraumes. Bei äquidistanter Überdeckung des Suchraumes mit r Stützstellen pro Dimension, ergibt sich die Anzahl der nötigen Stützstellen zu N = r^n.
Sie wächst also stark mit der Zahl der Parameter
Für welche Art von Optimierungsaufgaben sind Evolutionsstrategien besonders geeignet? Welche anderen Aufgaben sind möglich?
Evolutionsstrategien eigenen sich insbesondere zur Lösung von
Parameteroptimierungsausfgaben. Nebenbedingungen können dabei durch z.B. durch Barrierefunktionen berücksichtigt werden.
Außerdem können sie zur Lösung nichtlinearer Gleichungssysteme oder nichtlinearer Ungleichungen verwendet werden.
Welche Möglichkeiten gibt es zur Ermittelung des Gütewertes?
Zur Ermittlung des Gütewertes kann man die berechneten Werte in die Gütefunktion einsetzen. Falls das nicht möglich ist, simuliert man den Vorgang. Das kostet jedoch weitere Rechenzeit. Die Optimierungsdauer ist dabei ungefähr proportional zur Anzahl der Zielfunktionswerte
Wodurch wird bei den genetischen Algorithmen ein Individuum repräsentiert?
Ein Individuum wird bei diesen Methoden durch ein Codewort repräsentiert. Dabei ist die Art des Codes nicht vorgeschrieben. Der Binärcode ist üblich. Codiert werden z.B. reelle Zahlen, logische Ausdrücke oder Abfolgen von Operatoren
Welche Anzahl an Nachkommen wird pro Generation generiert?
Pro Generation werden µ Nachkommen generiert. Ihre Anzahl ist also gleich der Anzahl µ der Eltern
Wie sind die Mutation und die Rekombination gewichtet?
Bei den genetischen Algorithmen ist die Reproduktion wesentlich wichtiger. Die Mutation nimmt eine Nebenrolle ein. Sie ist schwächer ausgeprägt als bei den Evolutionsstrategien.
Wie werden die Eltern in der Startphase gewählt? Wie hoch ist ihre Anzahl (im Vergleich zu Evolutionsstrategien)?
Die µ Individuen werden zufällig verteilt. Ihre Anzahl µ bewegt sich üblicherweise zwischen 30 und 500. Bei Evlutionsstrategien wählt man µ um ca. den Faktor 10 kleiner
Was bezeichnet man bei genetischen Algorithmen als Selektion? Welche Verfahren gibt es?
Man bezeichnet hier die Auswahl zweier Eltern als Selektion. Diese zeugen dann durch Rekombination Nachkommen. Man unterscheidet zufällige Selektion und Selektion durch lineares Ranking.
Bei der zufälligen Selektion werden 2 Individuen zufällig gewählt und das mit dem besseren Gütewert wird Elter.
Bei Selektion mit linearem Ranking werden die Individuen nach ihrem Gütewert sortiert und ordnet ihnen dann entgegengesetzt die Werte einer linearen Fitneßfunktion zu. Die Selektionswahrscheinlichkeit eines Individuums ergibt sich dann aus dem Quotient seiner eigenen Fitneßsumme und der aller Individuen.
Was bewirkt der Parameter S?
Bei Selektion mit linearem Ranking stellt man mittels dieses Parameters den Unterschied der Fitneßfunktion für die Individuen 1 und µ ein. Der so genannte Selektionsdruck ist deshalb ein Maß für die bevorzugte Auswahl des besten Individuums µ
Auf welche Arten kann die Rekombination durchgeführt werden?
Man unterscheidet die n-Punkt-Rekombination und die gleichmäßige Kombination.
Bei der n-Punkt-Rekombination werden n gleichverteilte Zufallszahlen z_i ermittelt. Zwischen den Positionen z_i und z_i+1 (i = 1,3,5...) werden die Codeelemente der Eltern vertauscht.
Bei der gleichmäßigen Rekombination wird eine binäre Zufallszahl erzeugt.
An den Stellen , wo diese 1en enthält, werden die Elemente der Eltern vertauscht.
Wie läuft die Bildung einer neuen Generation ab?
Durch die Rekombination wurden aus den µ Eltern µ Nachkommen erzeugt. Aus dieser Menge 2µ müssen nun µ Individuen für die nächste Generation ausgewählt werden.
Eine mögliche Methode ist hierbei das Vollständige Ersetzen. In diesem Fall bilden nur die Nachkommen die neue Generation. Hier ist es wie bei den (µ,λ)-Evolutionsstrategien möglich, dass sich die Güte verschlechtert.
Als Alternative steht der so genannte Elitismus zur Verfügung. In diesem Fall bilden die k besten Eltern und die (µ-k) besten Nachkommen die neue Generation
Wie unterscheiden sich Mutation und Abbruchkriterium verglichen mit den Evolutionsstrategien?
Die Mutationsrate wird sehr niedrig angesetzt, da die Rekombination einen höheren Stellenwert hat. Das Abbruchkriterium entspricht dem der Evolutionsstrategien
Wovon hängt die Konvergenz dieser Verfahren maßgeblich ab?
Entscheidend für die Konvergenz ist die Wahl des Codes. Ein mögliches Problem ist hierbei, dass kleine Mutationen große Veränderungen hervorrufen könnten - bei Binärcode für reelle Zahlen könnte z.B. aus einer 1 eine 65 werden. In diesem Spezialfall kann der Gray-Code Abhilfe schaffen
Für welche Aufgaben sind genetische Algorithmen besonders geeignet?
Sie sind besonders zur Lösung kombinatorischer Aufgaben geeignet. Bei der Parameteroptimierung sind die Evolutionsstrategien meist leistungsfähiger
Was versteht man unter genetischer Programmierung?
Bei der genetischen Programmierung werden arithmetische Ausdrücke codiert und optimiert. Die Codierung bezieht sich dabei auf die Operatoren (+, /, exp, sinh usw.).
Beispiel: sin(x)/(2+b) => /(sin(x), +(2,b))
Diese wird auch oft als Baumstruktur dargestellt. Dabei sind die Durchlaufknoten mathematische Operatoren (function set) und die Endknoten Variable und Konstanten (terminal set).
Die genetische Programmierung stellt also ein Verfahren der Strukturoptimierung dar. Man kann auch ganze Programme damit generieren, wenn man die Menge der Operatoren durch Programmierstatements wie if oder do erweitert
Was ist bei der Rekombination und Mutation bei der genetischen
Programmierung besonders zu beachten?
Beim Vertauschen (Rekombination) oder Ersetzen (Mutation) von Teilsequenzen, dürfen nur syntaktisch intakte Abschnitte verwendet werden
Wie kann man genetische Programmierung auf Fuzzy-Systeme anwenden?
Genetische Programmierung kann zur Generierung und Optimierung der Regeln von Fuzzy-Systemen dienen. Dazu verwendet man folgende sets:
function set: {if, akk, und, =}
terminal set: {Variablen x_i, linguistische Werte NB und PM, leer emp}
Auch hier dürfen nur syntaktisch korrekte Ausdrücke erzeugt werden
Wie auf Neuronale Netze?
Auch Neuronale Netze lassen sich mittels genetischer Programmierung in ihrer Struktur optimieren.
Für welchen Typ von Optimierungsaufgabe verwendet man welches Verfahren?
Wenn die Aufgabe analytisch lösbar ist, ist dies einem Suchverfahren vorzuziehen.
Bei unimodalen Funktionen verwendet man klassische Hill-Climbing-Verfahren. Sie konvergierende hier schneller als Evolutionäre Algorithmen.
Bei multimodalen Funktionen verwendet man Evolutionäre Algorithmen, da sie mit höherer Wahrscheinlichkeit das globale Minimum finden. Dafür benötigen diese mehr Funktionsaufrufe
Welche Omptimierungsprobleme können mit Evolutionären Algorithmen bewältigt werden?
Evolutionäre Algorithmen sind universell einsetzbar. Sie können für
Parameteroptimierung
kombinatorische Optimierung
Strukturoptimierung
verwendet werden. Diese Bandbreite bietet keine andere Optimierungsmethode
Welche Evolutionären Algorithmen sind für welche Probleme besonders geeignet?
Wo liegen die methodischen Unterschiede zwischen Evolutionsstrategien, genetischen Algorithmen und genetischer Programmierung?
Last changeda month ago
