Genetischer Algorithmus

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.

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.

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.

Genetischer Algorithmus Beispiel

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

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

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

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:

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.

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.

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