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?

Genetischer Algorithmus Genetischer Algorithmus

Erstelle Lernmaterialien über Genetischer Algorithmus mit unserer kostenlosen Lern-App!

  • Sofortiger Zugriff auf Millionen von Lernmaterialien
  • Karteikarten, Notizen, Übungsprüfungen und mehr
  • Alles, was du brauchst, um bei deinen Prüfungen zu glänzen
Kostenlos anmelden
Inhaltsverzeichnis
Inhaltsangabe

    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

    Was ist ein genetischer Algorithmus? 

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

    Wie ist der Ablauf eines genetischen Algorithmus? 

    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. 

    Teste dein Wissen mit Multiple-Choice-Karteikarten

    Wahr oder FalschGenetische Algorithmen sind die bekannteste Art evolutionärer Algorithmen. 

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

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

    Weiter
    1
    Über StudySmarter

    StudySmarter ist ein weltweit anerkanntes Bildungstechnologie-Unternehmen, das eine ganzheitliche Lernplattform für Schüler und Studenten aller Altersstufen und Bildungsniveaus bietet. Unsere Plattform unterstützt das Lernen in einer breiten Palette von Fächern, einschließlich MINT, Sozialwissenschaften und Sprachen, und hilft den Schülern auch, weltweit verschiedene Tests und Prüfungen wie GCSE, A Level, SAT, ACT, Abitur und mehr erfolgreich zu meistern. Wir bieten eine umfangreiche Bibliothek von Lernmaterialien, einschließlich interaktiver Karteikarten, umfassender Lehrbuchlösungen und detaillierter Erklärungen. Die fortschrittliche Technologie und Werkzeuge, die wir zur Verfügung stellen, helfen Schülern, ihre eigenen Lernmaterialien zu erstellen. Die Inhalte von StudySmarter sind nicht nur von Experten geprüft, sondern werden auch regelmäßig aktualisiert, um Genauigkeit und Relevanz zu gewährleisten.

    Erfahre mehr
    StudySmarter Redaktionsteam

    Team Genetischer Algorithmus Lehrer

    • 8 Minuten Lesezeit
    • Geprüft vom StudySmarter Redaktionsteam
    Erklärung speichern

    Lerne jederzeit. Lerne überall. Auf allen Geräten.

    Kostenfrei loslegen

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

    Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!

    Die erste Lern-App, die wirklich alles bietet, was du brauchst, um deine Prüfungen an einem Ort zu meistern.

    • Karteikarten & Quizze
    • KI-Lernassistent
    • Lernplaner
    • Probeklausuren
    • Intelligente Notizen
    Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!