• :00Tage
  • :00Std
  • :00Min
  • 00Sek
Ein neues Zeitalter des Lernens steht bevorKostenlos anmelden
Login Anmelden

Select your language

Suggested languages for you:
StudySmarter - Die all-in-one Lernapp.
4.8 • +11k Ratings
Mehr als 5 Millionen Downloads
Free
|
|

Genetischer Algorithmus

Ein städtischer Paketdienst erhielt von einem Kunden den Auftrag, Pakete vom Lager an die Adresse des Kunden zu liefern. Die Anzahl der Pakete ist so gering, dass ein LKW ausreicht, um alle Pakete auf einmal transportieren zu können. Die Frage im Lieferprozess lautet: In welche Richtung soll der Lkw-Fahrer fahren, damit die Fahrstrecke möglichst kurz ist?Es wird ein genetischer Algorithmus eingerichtet,…

Von Expert*innen geprüfte Inhalte
Kostenlose StudySmarter App mit über 20 Millionen Studierenden
Mockup Schule

Entdecke über 200 Millionen kostenlose Materialien in unserer App

Genetischer Algorithmus

Illustration

Lerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken

Jetzt kostenlos anmelden

Nie wieder prokastinieren mit unseren Lernerinnerungen.

Jetzt kostenlos anmelden
Illustration

Ein städtischer Paketdienst erhielt von einem Kunden den Auftrag, Pakete vom Lager an die Adresse des Kunden zu liefern. Die Anzahl der Pakete ist so gering, dass ein LKW ausreicht, um alle Pakete auf einmal transportieren zu können. Die Frage im Lieferprozess lautet: In welche Richtung soll der Lkw-Fahrer fahren, damit die Fahrstrecke möglichst kurz ist?

Es wird ein genetischer Algorithmus eingerichtet, um ein ausreichend gutes Ergebnis zu ermitteln.

Genetischer Algorithmus Definition

Genetische Algorithmen sind die bekannteste Art evolutionärer Algorithmen. Der Begriff genetischer Algorithmus geht auf eine von Bagleys frühen Arbeiten zurück. Die Form, die man heute kennt, wurde jedoch von John H. Holland entwickelt.

Ein genetischer Algorithmus ist eine Optimierungstechnik, die Optimierungsprobleme durch die Kombinierung guter Teillösungen löst, die letztlich zu einer guten globalen Lösung führen.

Hollands Ziele waren weitreichend. Die Ziele dieser Arbeit waren zweigeteilt:

  1. Eine Erklärung (Theorie) von Anpassungsprozessen in der Natur.
  2. Entwicklung von Software mit unendlicher Kapazität, um die Mechanismen natürlicher Systeme zu bewahren und sich an die unterschiedlichsten Situationen anzupassen.

Eine der bemerkenswertesten Errungenschaften von Hollands Arbeit war die Formulierung des Schema-Theorems. Damit wurde versucht zu erklären, wie und warum genetische Algorithmen funktionieren. Genetische Algorithmen bilden eine Untergruppe evolutionärer Algorithmen.

Evolutionäre Algorithmen modellieren eine Vielzahl natürlicher Prozesse wie Selektion, Rekombination, Mutation, Migration, Lokalität, Parallelität und Konkurrenz. Jeder dieser Prozesse kann in zahlreichen Varianten auftreten.

Evolutionäre Algorithmen sind probabilistische Suchverfahren, die auf den Prinzipien der natürlichen biologischen Evolution basieren.

Evolutionäre Algorithmen arbeiten gleichzeitig an mehreren potenziellen Lösungen von Populationen von Individuen. Für diese Individuen gilt der Grundsatz: "Der Stärkere überlebt!" Dieser wird angewendet, um gemäß einer Zielfunktion immer bessere Individuen zu schaffen, was letztlich zu einer guten Lösung führt.

Genetischer Algorithmus Terminologie

Genetische Algorithmen sind an der biologischen Evolution beteiligt und basieren auf ihrer Genetik und Terminologie. In der folgenden Tabelle wird kurz auf die wichtigsten Begriffe und ihre Entwicklung eingegangen.

BegriffFunktionsweise
ZellenDie Grundbausteine aller Organismen sind Zellen. Die meisten Zellen bilden eukaryotische Zellen.
ChromosomenZellen enthalten Chromosomen, Träger des genetischen Materials. Das Erbgut ist in der Erbsubstanz verschlüsselt und bildet den „Bauplan“ des Organismus (Individuums).
GeneChromosomen können in kleine Teile, sogenannte Gene, zerlegt werden, die ein bestimmtes Merkmal wie die Augenfarbe bestimmen.
AlleleGene können keine Zustände annehmen, sondern haben feste Ausprägungen, die Allele genannt werden. Zum Beispiel es gibt Allele für die braune, grüne und blaue Augenfarbe.

Genetischer Algorithmus Beispiel

Heutzutage gibt es viele Bereiche, in denen genetische Algorithmen zur Lösung von Problemen eingesetzt werden.

Die Form eines Flügels und die Form des Rumpfes von Flugzeugen werden beispielsweise mit genetischen Algorithmen optimiert und mit Computersimulationen getestet.

Auch beim Brückenbau können Position, Form und Gewicht einzelner Brückenbauteile durch den Einsatz von genetischen Algorithmen verbessert werden.

Im Allgemeinen helfen genetische Algorithmen, NP-schwere Probleme wie das Problem des Handlungsreisenden oder das Backpacking-Problem zu lösen.

Der genetische Algorithmus wird verwendet, um den Schwellenpotentialvektor sowie die Netzwerktopologie des neuronalen Netzwerks abzustimmen.

Darüber hinaus unterstützen genetische Algorithmen die Erstellung von Fahrplänen, Stundenplänen und Grundrissen, die von öffentlichen Einrichtungen wie Schulen und Universitäten verwendet werden.

Genetischer Algorithmus Operatoren

Evolution ist die Veränderung vererbter Eigenschaften oder Gene. Gene werden während des Fortpflanzungsprozesses an die Nachkommen weitergegeben. Es gibt drei grundlegende Mechanismen, die die Evolution formen:

  • Selektion
  • Mutation
  • Rekombination

Im Folgenden werden die einzelnen Operatoren eines genetischen Algorithmus mit einigen wichtigen Verfahren aufgelistet. Die einzelnen Verfahren werden in den folgenden Abschnitten erläutert.

Genetischer Algorithmus Selektion

Die Selektion bestimmt, welche Individuen für die Zucht ausgewählt werden und wie viele Nachkommen jedes ausgewählte Individuum produzieren wird. Der erste Schritt besteht darin, jeder Person mithilfe einer der folgenden Methoden die Fitness zuzuordnen:

  • rank-based fitness assignment
  • multi-objective ranking
  • proportional fitness assignment

Die Anpassungsfähigkeit eines Individuums wird als Fitness bezeichnet.

Genetischer Algorithmus Mutation

Nach der Selektion mutieren die Nachkommen. Die Untervariablen werden durch kleine Störungen (Mutationsschritte) verändert. Diese Änderungen sind fast unwahrscheinlich. Abhängig von der Repräsentation der Variablen und der Art der Zielfunktion können unter anderem die folgenden Methoden verwendet werden:

  • Mutation reelle Variablen
  • Mutation binäre Variablen
  • Mutation ganzzahlige Variablen

Genetischer Algorithmus Rekombination

Nachkommen werden von den Eltern durch Rekombination geboren. Dazu werden Informationen der Eltern kombiniert (die Eltern sind die Paarungspopulation). Je nach Repräsentation der Variablen im Individuum und der Zielsetzung (Art der Zielfunktion) können unterschiedliche Methoden verwendet werden:

  • Rekombination reelle Variablen
  • Linien Rekombination
  • Rekombination binäre Variablen

Genetischer Algorithmus Ablauf

Die Grundidee des genetischen Algorithmus ist zunächst die “Empfohlene Lösung“ zu verwenden und zu kombinieren, bis eine ausreichend gute Lösung für das Problem gefunden ist. Dies führt zu folgendem Ablauf des genetischen Algorithmus:

Gegeben: ein Optimierungsproblem mit einem Suchraum S und einer Fitnessfunktion f.
Auflösung:
Generiere eine zufällige Startpopulation P,
WHILE (Endbedingung nicht erfüllt).
{
Die Fitness von Personen aus P.
Wähle nach Fitness aus.
Wende den genetischen Operator an.
}
Ergebnisse: Bestes Individuum(Lösung) aus der Population.

Ein „Individuum“ in einer Population P ist als Zeichenkette, Zahlenfolge oder Variablenfolge binär kodiert, und statt eines Individuums spricht man nur von dem Chromosom, das dieses Individuum repräsentiert.

In Analogie zur Genetik sind Gene einzelne Merkmale oder Variablen und Allele sind die Werte, die sie annehmen können. Individuen oder Chromosomen entsprechen Lösungen aus dem Suchraum S des Problems.

Genetischer Algorithmus Abbruchkriterium

Die drei Schritte der Fitnessberechnung, der Selection des genetischen Operators und der Anwendung können beliebig oft wiederholt werden.

Mit jeder neuen Generation können Veränderungen eintreten, die neue und bessere Lösungen in Form von Chromosomen schaffen. Allerdings gibt es keine Garantie dafür, dass die neue Lösung immer besser ist als die vorherige.

Daher ist es sinnvoll und notwendig, ein Abbruchkriterium zu definieren, das dem Algorithmus mitteilt, wann die Chromosomen der Population ausreichend sind, um eine gute Lösung darzustellen. Hier sind einige Beispiele für Stoppkriterien:

Nr.Genetischer Algorithmus Abbruchkriterium
1.Algorithmen haben eine gewisse Anzahl von Generationen durchlaufen.
2.Es gibt keine Verbesserung gegenüber der vorherigen Generation.
3.Die durchschnittliche Verbesserung früherer Generationen ist unter einen Wert gefallen.

Genetische Algorithmen künstliche Intelligenz

Das KI-System arbeitet mit intelligenten Algorithmen. In diese Kategorie fallen heuristische Methoden, künstliche neuronale Netze und evolutionäre (genetische) Algorithmen.

Watson ist die KI von IBM. Es ist ein kognitives System, das durch Interaktionen lernt und laut IBM evidenzbasierte Antworten liefert, die bessere Ergebnisse garantieren. Watson basiert auf einem genetischen Algorithmus.

Diese Algorithmen können Daten als Eingabe verwenden und eine Ausgabelösung bereitstellen. Sie kopieren biologische und evolutionäre Mechanismen, um aus einer Vielzahl von Lösungen die beste zu finden. Dabei „lernen“ sie aus ihren Fehlern und verbessern ihr eigenes Verhalten.

Genetische Algorithmen Machine Learning

Genetische Algorithmen werden hauptsächlich im Deep Learning eingesetzt. Dort werden neuronale Netze gebildet, bei denen beim Training die Gewichte der Neuronen angepasst werden, was sich auf das Endergebnis auswirkt. Hier kommen genetische Algorithmen ins Spiel.

Eine neuronale Netzpopulation wird mit zufälligen Gewichtungen für jedes Neuron erstellt. Anschließend werden diese Netze getestet und die Ergebnisse ausgewertet. Die besten werden beibehalten und Neuronen durchlaufen Stadien der Rekombination und Mutation. Das heißt, die Gewichte der Neuronen werden angepasst.

Genetischer Algorithmus Python

Hier ist ein kleines Beispiel für Dich. Dies ist eines der bekanntesten mathematischen Sudoku-Rätsel. Dieses Rätsel kann durch einen genetischen Algorithmus gelöst werden. Siehe unten für den entsprechenden Python-Code.

Sudoku:

#PGAPy ist eine Python-Bibliothek für genetische Algorithmen 
#Die meisten genetischen Methoden sind dort vordefiniert, wie z.B. get_allele()
def evaluate (self, p, pop) :
    sudoku = Sudoku (verbose = False, solvemax = 50)
    count = 0
    for x in range (6) :
        for y in range (6) :
            val = self.get_allele (p, pop, 6 * x + y)
            count += val != 0
            sudoku.set (x, y, val)
    sudoku.resolve ()
    resolvecount = sudoku.resolvecount
    if not resolvecount : return 1000 * count * count
    if resolvecount == 1 : return count
    return 1000 - count + resolvecount

Genetischer Algorithmus – Das Wichtigste

  • Genetischer Algorithmus Definition: Ein genetischer Algorithmus ist eine Optimierungstechnik, die Optimierungsprobleme löst.
  • Genetischer Algorithmus Beispiel: Im Allgemeinen helfen genetische Algorithmen, NP-schwere Probleme wie das Problem des Handlungsreisenden oder das Backpacking-Problem zu lösen.
  • Genetischer Algorithmus Operatoren: Es gibt drei grundlegende Mechanismen, die die Evolution formen:
    • Selektion
    • Mutation
    • Rekombination
  • Genetischer Algorithmus Ablauf: Die Grundidee des genetischen Algorithmus ist zunächst die “Empfohlene Lösung“ zu verwenden und zu kombinieren, bis eine ausreichend gute Lösung für das Problem gefunden ist.
  • Genetische Algorithmen künstliche Intelligenz: Das KI-System arbeitet mit intelligenten Algorithmen. In diese Kategorie fallen heuristische Methoden, künstliche neuronale Netze und evolutionäre (genetische) Algorithmen.

Nachweise

  1. diskussionspapiere.wiwi.uni-hannover.de: Genetische Algorithmen - Darstellung, Eigenschaften und eine Anwendung in der Statistik. (15.11.2022)
  2. polheim.com: Anwendung Evolutionärer Algorithmen. (15.11.2022)

Häufig gestellte Fragen zum Thema Genetischer Algorithmus

Ein genetischer Algorithmus ist eine Optimierungstechnik, die Optimierungsprobleme löst. 

Die Grundidee des genetischen Algorithmus ist zunächst die “Empfohlene Lösung“ zu verwenden und zu kombinieren, bis eine ausreichend gute Lösung für das Problem gefunden ist. 

Finales Genetischer Algorithmus Quiz

Genetischer Algorithmus Quiz - Teste dein Wissen

Frage

Wahr oder Falsch

Genetische Algorithmen sind die bekannteste Art evolutionärer Algorithmen. 

Antwort anzeigen

Antwort

Wahr

Frage anzeigen

Frage

Ergänze

Die Form, die man heute kennt, wurde jedoch von John H. (1)              an der University of Michigan, USA, entwickelt. 

Antwort anzeigen

Antwort

(1) Holland

Frage anzeigen

Frage

Was ist ein genetischer Algorithmus?

Antwort anzeigen

Antwort

Ein genetischer Algorithmus ist eine Optimierungstechnik, die Optimierungsprobleme löst.

Frage anzeigen

Frage

Wahr oder Falsch

Evolutionäre Algorithmen modellieren eine Vielzahl natürlicher Prozesse wie Selektion, Rekombination, Mutation, Migration, Lokalität, Parallelität und Konkurrenz. 

Antwort anzeigen

Antwort

Wahr

Frage anzeigen

Frage

Ergänze

Evolutionäre Algorithmen sind probabilistische Suchverfahren, die auf den Prinzipien der natürlichen biologischen (1)               basieren.

Antwort anzeigen

Antwort

(1) Evolution

Frage anzeigen

Frage

Benenne wichtigste Begriffe der genetischer Algorithmus? 

Antwort anzeigen

Antwort

  1. Zellen
  2. Chromosomen
  3. Gene
  4. Allele

Frage anzeigen

Frage

Ergänze

(1)        enthalten (2)       , Träger des genetischen Materials. Das Erbgut ist im Erbsubstanz verschlüsselt und bildet den „Bauplan“ des Organismus (Individuums).

Antwort anzeigen

Antwort

(1) Zellen

(2) Chromosomen

Frage anzeigen

Frage

Wahr oder Falsch

Allele können in kleine Teile, sogenannte Gene, zerlegt werden, die ein bestimmtes Merkmal wie die Augenfarbe bestimmen.

Antwort anzeigen

Antwort

Falsch

Frage anzeigen

Frage

Welche bekannte Problemen lösen genetische Algorithmen?

Antwort anzeigen

Antwort

  1. Problem des Handlungsreisenden 
  2. das Backpacking-Problem

Frage anzeigen

Frage

Wahr oder Falsch

 Es gibt drei grundlegende Mechanismen, die die Evolution formen:

  • Selektion
  • Mutation
  • Rekombination


Antwort anzeigen

Antwort

Wahr

Frage anzeigen

Frage

Die (1)              bestimmt, welche Individuen für die Zucht ausgewählt werden und wie viele Nachkommen jedes ausgewählte Individuum produzieren wird. 

Antwort anzeigen

Antwort

(1)Selektion

Frage anzeigen

Frage

Benenne Methoden von Rekombination!

Antwort anzeigen

Antwort

  • Rekombination reelle Variablen.
  • Linien Rekombination
  • Rekombination binäre Variablen


Frage anzeigen

Frage

Wahr oder Falsch

Die Grundidee des genetischen Algorithmus ist zunächst “Empfohlene Lösung“ zu wechseln und zu kombinieren, bis eine ausreichend gute Lösung für das Problem gefunden ist.

Antwort anzeigen

Antwort

Wahr

Frage anzeigen

Frage

Ergänze

Ein „Individuum“ in einer Population P ist als (1)           , Zahlenfolge oder Variablenfolge binär kodiert, und statt eines Individuums sprechen wir nur von dem (2)             , das dieses Individuum repräsentiert.

Antwort anzeigen

Antwort

(1) Zeichenkette

(2) Chromosom

Frage anzeigen

Frage

Wie ist der Ablauf eines genetischen Algorithmus? 

Antwort anzeigen

Antwort

Die Grundidee des genetischen Algorithmus ist zunächst “Empfohlene Lösung“ zu wechseln und zu kombinieren, bis eine ausreichend gute Lösung für das Problem gefunden ist.

Frage anzeigen

Frage

Wahr oder Falsch

Die drei Schritte der Fitnessberechnung, der Selection des genetischen Operators und der Anwendung können beliebig oft wiederholt werden. 

Antwort anzeigen

Antwort

Wahr

Frage anzeigen

Frage

Ergänze

Daher ist es sinnvoll und notwendig, ein (1)               zu definieren, das dem Algorithmus mitteilt, wann die Chromosomen der Population ausreichend gut sind, um eine gute Lösung darzustellen. 

Antwort anzeigen

Antwort

(1) Abbruchkriterium

Frage anzeigen

Frage

Benenne einige Beispiele für  Abbruchkriterium !

Antwort anzeigen

Antwort

  1. Algorithmen haben eine gewisse Anzahl von Generationen durchlaufen.
  2. Es gibt keine Verbesserung gegenüber der vorherigen Generation.
  3. Die durchschnittliche Verbesserung früherer Generationen ist unter einen Wert gefalle

Frage anzeigen

Frage

Wahr oder Falsch

Das KI-System arbeitet mit intelligenten Algorithmen. In diese Kategorie fallen heuristische Methoden, künstliche neuronale Netze und evolutionäre (genetische) Algorithmen. 

Antwort anzeigen

Antwort

Wahr

Frage anzeigen

Frage

Ergänze

Genetische Algorithmen werden hauptsächlich im (1)                      Learning eingesetzt.

Antwort anzeigen

Antwort

(1) Deep

Frage anzeigen

Frage

Wahr oder Falsch

Sherlock ist die KI von IBM. Sherlock basiert auf einem genetischen Algorithmus. 

Antwort anzeigen

Antwort

Falsch

Frage anzeigen

60%

der Nutzer schaffen das Genetischer Algorithmus Quiz nicht! Kannst du es schaffen?

Quiz starten

Wie möchtest du den Inhalt lernen?

Karteikarten erstellen
Inhalte meiner Freund:innen lernen
Ein Quiz machen

94% der StudySmarter Nutzer erzielen bessere Noten.

Jetzt anmelden

94% der StudySmarter Nutzer erzielen bessere Noten.

Jetzt anmelden

Wie möchtest du den Inhalt lernen?

Karteikarten erstellen
Inhalte meiner Freund:innen lernen
Ein Quiz machen

Kostenloser informatik Spickzettel

Alles was du zu . wissen musst. Perfekt zusammengefasst, sodass du es dir leicht merken kannst!

Jetzt anmelden

Finde passende Lernmaterialien für deine Fächer

Alles was du für deinen Lernerfolg brauchst - in einer App!

Lernplan

Sei rechtzeitig vorbereitet für deine Prüfungen.

Quizzes

Teste dein Wissen mit spielerischen Quizzes.

Karteikarten

Erstelle und finde Karteikarten in Rekordzeit.

Notizen

Erstelle die schönsten Notizen schneller als je zuvor.

Lern-Sets

Hab all deine Lermaterialien an einem Ort.

Dokumente

Lade unzählige Dokumente hoch und habe sie immer dabei.

Lern Statistiken

Kenne deine Schwächen und Stärken.

Wöchentliche

Ziele Setze dir individuelle Ziele und sammle Punkte.

Smart Reminders

Nie wieder prokrastinieren mit unseren Lernerinnerungen.

Trophäen

Sammle Punkte und erreiche neue Levels beim Lernen.

Magic Marker

Lass dir Karteikarten automatisch erstellen.

Smartes Formatieren

Erstelle die schönsten Lernmaterialien mit unseren Vorlagen.

Melde dich an für Notizen & Bearbeitung. 100% for free.

Fang an mit StudySmarter zu lernen, die einzige Lernapp, die du brauchst.

Jetzt kostenlos anmelden
Illustration