Mutation (genetischer Algorithmus)

Mutation (genetischer Algorithmus)

Unter Mutation bei einem genetischen Algorithmus versteht man die zufällige Abänderung eines Genoms. Sie ist die Umsetzung der biologischen Mutation für genetische Algorithmen. Eine solche Zuordnung von einem alten Genom (und eventuell Zufallszahlen) zu einem neuen Genom ist eine Funktion und heißt Mutations-Funktion. Jede Mutations-Funktion ist ein genetischer Operator.

Eine Mutation sollte idealerweise nur kleine Änderungen hervorrufen, jedoch in der Summe so viel, dass die Individuen über die Laufzeit eines genetischen Algorithmus' fast die gesamte Wertelandschaft abdecken, auf der optimiert werden soll. Am Anfang des Laufens eines genetischen Algorithmus ist es deswegen günstiger, größere Änderungen zuzulassen, während im fortgeschrittenerem Stadium nur noch kleine Änderungen erlaubt sein sollten, um Individuen, die sich bereits nahe eins Optimums befinden, nicht von diesem Optimum wegzubringen.

Ein genetischer Algorithmus mit einer globalen Mutationsrate (Anteil der Gesamtpopulation, die der Mutation unterzogen wird) von 0 wird sehr schlechte Ergebnisse liefern, da einmal durch Kreuzungsfunktionen aus der Population gefallene Allele niemals wieder in die Population zurückkehren können und somit, falls sie ein Teil des Building Blocks der global optimalen Lösung waren, zum Auffinden dieser fehlen. Ist die Mutationsrate hingegen zu hoch, werden Individuen nahe beim Optimum wieder von diesem weggedrängt und der Algorithmus kann nicht konvergieren.

Bei Verwendung von für das Problem nicht gut geeigneten Kreuzungsfunktionen oder Problemrepräsentationen kann es zu ungewollten Mutationen bei der Kreuzung kommen. Dabei entsteht an manchen Stellen des Chromosoms eine Ausprägung des Allels, die sich auf keinen der Elternindividuen zurückführen lassen, noch bevor es zum eigentlichen Mutationsschritt kommt.

Für unterschiedliche Genom-Typen eignen sich unterschiedliche Mutations-Typen unterschiedlich gut:

  • Mutation von Bitstrings
Die Mutation von Bitstrings erfolgt durch Bit-Flips an zufälligen Stellen.
Beispiel:
1 0 1 0 0 1 0
1 0 1 0 1 1 0
Die Wahrscheinlichkeit für eine Mutation eines Bits beträgt \frac{1}{l}, wobei l die Länge des Binärvektors ist. Dadurch wird im Schnitt eine Mutationsrate von 1 je Mutation und zur Mutation gewählten Individuum erreicht (siehe oben, globale Mutationsrate) .

Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • genetischer Algorithmus — genetischer Algorithmus,   Algorithmus, der Strategien aus der Evolutionstheorie nachahmt, um zu einem Optimierungsproblem eine möglichst gute Lösung zu finden. Dabei werden Lösungen eines Problems als Chromosomen dargestellt, nämlich jeweils als …   Universal-Lexikon

  • Genetischer Algorithmus — Genetische Algorithmen (GA) sind Algorithmen, die auch nicht analytisch lösbare Probleme behandeln können, indem sie wiederholt verschiedene „Lösungsvorschläge“ generieren, dabei verändern sowie miteinander kombinieren und einer Auslese… …   Deutsch Wikipedia

  • genetischer Algorithmus — allgemein verwendbare globale ⇡ Heuristik zur Lösung von Entscheidungsproblemen. Wie auch bei den ⇡ Evolutionsstrategien muss das Entscheidungsproblem auf ein Individuum abgebildet werden. Eine Menge von Individuen, die zu einem Zeitpunkt… …   Lexikon der Economics

  • Mutation (Begriffsklärung) — Mutation (v. lat. mutatio „Veränderung“, „Wechsel“) bezeichnet: in der Genetik für die Veränderung des Erbguts, siehe Mutation und Mutation (genetischer Algorithmus) in der Medizin benutzt für den Stimmwechsel in der Grammatik für die Veränderung …   Deutsch Wikipedia

  • Genom (genetischer Algorithmus) — Ein Genom ist im Kontext eines genetischen Algorithmus diejenige Information, die Eigenschaften eines Individuums ausmacht. Damit ist ein Genom eine Datenstruktur. Es ist vom biologischen Genom inspiriert. Inhaltsverzeichnis 1 Genomtypen 2 Schema …   Deutsch Wikipedia

  • Rekombination (genetischer Algorithmus) — Mit Rekombination wird bei genetischen Algorithmen die Erzeugung eines neuen Kind Genoms aus (in der Regel) 2 Eltern Genomen bezeichnet. Eine Funktion, die jede zulässige Menge von Eltern Genomen auf ein Kind Genom (oder eine Menge von Kind… …   Deutsch Wikipedia

  • Mutation binärer Zahlen — Die Artikel Evolutionsstrategie, Evolutionärer Algorithmus und Genetischer Algorithmus überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zu vereinigen. Beteilige dich dazu an der Diskussion über diese… …   Deutsch Wikipedia

  • Mutation von binären Zahlen — Die Artikel Evolutionsstrategie, Evolutionärer Algorithmus und Genetischer Algorithmus überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zu vereinigen. Beteilige dich dazu an der Diskussion über diese… …   Deutsch Wikipedia

  • Bergsteiger-Algorithmus — Bergsteigeralgorithmus (englisch hill climbing) ist ein einfaches, heuristisches Optimierungsverfahren. Von einer gegebenen Startlösung aus wird solange zum besten Punkt aus der Nachbarschaft der aktuellen Lösung gegangen, bis keine Verbesserung… …   Deutsch Wikipedia

  • Genetischer Operator — Ein genetischer Operator bei einem genetischen Algorithmus ist ein Operator, der für bestimmte Genome und (unter Umständen zusätzliche Eingaben wie Zufallszahlen) ein neues Genom zurückliefert. Als genetische Operatoren werden insbesondere… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”