Genetische Algorithmen und ihre Anwendungsfälle im Machine Learning

Teilen auf Facebook
Teilen auf twittern
Teilen auf verlinktin
Teilen auf Telegramm
Teilen auf WhatsApp

Inhalt

Dieser Artikel wurde im Rahmen der Data Science Blogathon

Genetische Algorithmen sind Suchalgorithmen, die von Darwins Evolutionstheorie in der Natur inspiriert sind.

  • Durch die Simulation des Prozesses der natürlichen Selektion, Fortpflanzung und Mutation, genetische Algorithmen können hochwertige Lösungen für verschiedene Probleme liefern, inklusive Suche und Optimierung.

  • Durch den effektiven Einsatz der Evolutionstheorie, genetische Algorithmen können die Probleme herkömmlicher Algorithmen überwinden.

Nach Darwins Evolutionstheorie, eine Evolution erhält eine Population von Individuen, die sich voneinander unterscheiden (Variation). Wer besser an seine Umgebung angepasst ist, hat bessere Überlebenschancen, reproduzieren und ihre Eigenschaften an die nächste Generation weitergeben (Überleben der Stärksten).

‌Wie funktionieren genetische Algorithmen?

‌Bevor Sie in den Betrieb eines genetischen Algorithmus eintreten, Tauchen wir ein in die grundlegende Terminologie genetischer Algorithmen.

Chromosom / Individuell

Ein Chromosom ist eine Sammlung von Genen. Zum Beispiel, ein Chromosom kann als binäre Zeichenfolge dargestellt werden, wobei jedes Bit ein Gen ist.

644781623127595061-8406334

Bildquelle: praktischer genetischer Algorithmus mit Python, Eyal Wirsansky

Population

Da ein Individuum als Chromosom dargestellt wird, eine Population ist eine Ansammlung solcher Chromosomen.

779521623127686493-5364456

Bildquelle: praktischer genetischer Algorithmus mit Python, Eyal Wirsansky

Fitnessfunktion

In jeder Iteration, Personen werden anhand ihrer Fitnesswerte bewertet, die mit der Fitnessfunktion berechnet werden.

Menschen, die einen besseren Fitnesswert erreichen, stellen bessere Lösungen dar und werden eher ausgewählt, um zu wechseln und an die nächste Generation weiterzugeben.

Zum Beispiel, ob genetische Algorithmen zur Auswahl von Merkmalen verwendet werden, dann wäre die Genauigkeit des Modells mit diesen ausgewählten Merkmalen die Angemessenheitsfunktion, wenn es sich um ein Klassifikationsproblem handelt.

Auswahl

Nach der Berechnung der Fitness jedes Individuums in der Population, ein Auswahlprozess wird verwendet, um zu bestimmen, welche Individuen in der Population in der Lage sind, sich fortzupflanzen und die Nachkommen zu zeugen, die die nächste Generation bilden werden.

Verfügbare Auswahlmethoden,

  • Auswahl am Rouletterad
  • Turnierauswahl
  • Reichweitenbasierte Auswahl

Quer

Allgemein, zwei Individuen der aktuellen Generation werden ausgewählt und ihre Gene werden zwischen zwei Individuen ausgetauscht, um ein neues Individuum zu schaffen, das die Nachkommen repräsentiert. Dieser Vorgang wird auch als Paarung oder Kreuzung bezeichnet..

Verfügbare Arten von Kreuzmethoden,

  • Einen Punkt überqueren
  • Zweipunkt-Frequenzweiche
  • Einheitliche Frequenzweiche
505071623128127345-5633004
Einen Punkt überquerenBildquelle: praktische genetische Algorithmen mit Python, Eyal Wirsansky

Mutation

Mutation ist eine zufällige Veränderung auf einem Chromosom, um neue Muster auf einem Chromosom einzuführen. Zum Beispiel, Flip ein bisschen in einer binären Zeichenfolge.

Verfügbare Arten von Mutationsmethoden,

  • Flip-Bit-Mutation
  • Gaußsche Mutation
  • Austauschmutation
550041623128158975-5413371

Allgemeiner Arbeitsablauf eines einfachen genetischen Algorithmus

244111623128199688-4801325

Bildquelle: praktische genetische Algorithmen mit Python, Eyal Wirsansky

Wie unterscheiden sich genetische Algorithmen von herkömmlichen Algorithmen??

  • ‌Ein Suchraum ist eine Menge aller möglichen Lösungen des Problems. Herkömmliche Algorithmen halten nur eine Menge in einem Suchraum, wohingegen genetische Algorithmen mehrere Sätze in einem Suchraum verwenden (Merkmalsauswahl mit RFE versus genetische Algorithmen).

  • Herkömmliche Algorithmen benötigen mehr Informationen, um eine Suche durchzuführen, wohingegen genetische Algorithmen nur eine objektive Funktion benötigen, um die Fitness eines Individuums zu berechnen.

  • Herkömmliche Algorithmen können nicht parallel arbeiten, während genetische Algorithmen parallel arbeiten können (die Berechnung der Fitness der Individuen ist unabhängig).

  • Ein großer Unterschied bei genetischen Algorithmen besteht darin, dass anstatt direkt mit Kandidatenlösungen zu arbeiten, genetische Algorithmen arbeiten mit ihren Darstellungen (oder Kodierung), oft Chromosomen genannt.

  • ‌Traditionelle Algorithmen können am Ende nur eine Lösung hervorbringen, während in genetischen Algorithmen mehrere optimale Lösungen verschiedener Generationen erhalten werden können.

  • ‌Traditionelle Algorithmen produzieren keine globalen optimalen Lösungen mehr, genetische Algorithmen liefern nicht garantiert auch globale optimale Lösungen, aber sie produzieren aufgrund genetischer Operatoren wie Crossover und Mutation eher globale optimale Lösungen.

  • Herkömmliche Algorithmen sind deterministischer Natur, während genetische Algorithmen probabilistischer und stochastischer Natur sind.

  • Probleme der realen Welt sind multimodal (enthalten mehrere optimale Lösungen lokal), Herkömmliche Algorithmen handhaben diese Probleme nicht gut, während genetische Algorithmen, mit korrekten Parametereinstellungen, kann diese Probleme aufgrund des großen Lösungsraums sehr gut bewältigen.

Vorteile genetischer Algorithmen

  • Parallelität

  • Globale Optimierung

  • Mehr Raum für Lösungen

  • Benötigt weniger Informationen

  • Bietet mehrere optimale Lösungen

  • Wahrscheinlichkeitsrechnung in der Natur

  • Genetische Darstellungen mit Chromosomen

Nachteile genetischer Algorithmen

‌ Anwendungsfälle genetischer Algorithmen im maschinellen Lernen

TPOT(Baumbasierte Pipeline-Optimierung) ist ein Auto-ML-Framework, das genetische Algorithmen verwendet, um Pipelines für maschinelles Lernen mithilfe des genetischen Algorithmus-Frameworks namens . zu optimieren DEAP (Verteilte evolutionäre Algorithmen in Python).

Merkmalsauswahl mit genetischen Algorithmen

Verwendung genetischer Algorithmen, Lassen Sie uns eine Funktionsauswahl für einen in sklearn verfügbaren Weindatensatz durchführen.

zufällig importieren
Pandas als pd importieren
aus sklearn.base Importklon
from deap.algorithms importieren eaSimple
aus Tiefenimportbasis, Schöpfer, Werkzeuge
aus sklearn.datasets import load_wine
von sklearn.metrics import precision_score
aus sklearn.ensemble importieren RandomForestClassifier
aus sklearn.model_selection import train_test_split

data = load_wine()
Funktionen = pd.DataFrame(
    Daten.Daten, Spalten=data.feature_names
)
Ziel = pd.Serie(data.target)

# Teilen Sie die Daten in Train und Test auf
x_train, x_test, y_train, y_test = train_test_split(
    Merkmale, Ziel, test_size=0.2, stratify=ziel
)

model = RandomForestClassifier()

Teilen Sie die Daten in Merkmale und Ziel auf und teilen Sie dann die Merkmale und das Ziel für Training und Test auf.

def compute_fitness_score(Individuell):
    """
    Wählen Sie die Funktionen aus der Person, Bahn
    und berechne den Accuracy_Score.
    
    Beispiel:
    individuell = [0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1]
    Die 1 repräsentiert das Vorhandensein von Funktionen und
    0 steht für das Fehlen von Funktionen
    
    """
    column_support = pd.Series(Individuell).astyp(bool)
    globaler x_train, y_train, x_test, y_test, Modell
    
    x_train_ = x_train[x_train.columns[column_support]]
    x_test_ = x_test[x_test.spalten[column_support]]

    model.fit(x_train_, y_train)
    y_pred = model.predict(x_test_)
    Punktzahl = Genauigkeit_Punktzahl(y_test, y_pred)
    
    Ergebnis zurückgeben,

Definiere den Fitness-Score. compute_fitness_score nimmt eine Person als Eingabe, zum Beispiel, betrachten wir die folgende Person [0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1], auf dieser Liste, 1 repräsentiert das Vorhandensein dieses besonderen Merkmals und 0 steht für das Fehlen dieser Eigenschaft. Die Spalten werden individuell ausgewählt und dann das Modell angepasst und die Präzisionsbewertung berechnet. Dieser Genauigkeitswert ist der körperliche Fitnesswert einer Person.

n_genes = x_train.shape[1]
n_generationen = 10
n_bevölkerung = 10
Überkreuzungswahrscheinlichkeit = 0.6
Mutation_Wahrscheinlichkeit = 0.2


def setup_toolbox():
    # Container für Einzelpersonen
    Ersteller.Erstellen('FitnessMax', base.Fitness, Gewichte=(1.0,))
    Ersteller.Erstellen('Individuell', aufführen, fitness=creator.FitnessMax)

    Toolbox = base.Toolbox()
    toolbox.register(
        'individuelle_generator_funktion',
        random.randint, 0, 1
    )
    # Methode zum Bevölkern von Einzelpersonen
    toolbox.register(
        'individueller_generator',
        tools.initRepeat,
        Schöpfer.Individuell,
        toolbox.individual_generator_function,
        n_gene
    )
    # Methode zur Bevölkerungsbildung
    toolbox.register(
        'population_generator',
        tools.initRepeat,
        aufführen,
        toolbox.individual_generator
    )
    # Fitnessberechnung
    toolbox.register(
        'bewerten', compute_fitness_score
    )
    # Auswahl
    toolbox.register(
        'auswählen', tools.selTurnier, Tournsize=3
    )
    # Überkreuzung
    toolbox.register('Kamerad', tools.cxOnePoint)
    # Mutation
    toolbox.register(
        'mutieren',
        tools.mutFlipBit,
        indpb=mutationswahrscheinlichkeit
    )
    Werkzeugkasten zurückgeben

n_gene stellen die Anzahl der Gene in einem Individuum dar, die der Anzahl der Merkmale entspricht, n_generations stellt die Anzahl der Generationen dar, die gleich ist 10 und auch n_population, was die Bevölkerungszahl darstellt. Die Crossover-Wahrscheinlichkeit wird auf gesetzt 0,6 und die Mutationswahrscheinlichkeit wird auf gesetzt 0,2.

Toolbox ist eine Klasse in einem tiefen Framework, die uns die notwendigen Dienstprogramme zur Verfügung stellt, um Einzelpersonen zu definieren, Bevölkerung und vieles mehr.

Die in der setup_toolbox-Methode ausgeführten Schritte sind,

  • Zuerst, Wir definieren eine Person, die eine mit ihr verbundene Eignungsbewertung hat
  • Dann, Wir definieren eine Funktion, die Gene eines Individuums generiert, in unserem Fall 0 Ö 1 in einem Individuum
  • Wir definieren eine Funktion, die Individuen aus einer Population erzeugt, zum Beispiel, [0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1] ist ein Individuum in einer Population.
  • Dann, wir definieren eine Funktion, die eine Population erzeugt, zum Beispiel, [[0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1],

    [0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1]]ist eine Population von Größe 2.

  • Dann, wir definieren eine Funktion zur Auswertung, In unserem Fall verwenden wir die Funktion compute_fitness_score.

  • Wir wählen die Turnierauswahlmethode für den Auswahlprozess, ein Crossover-Punkt für den Crossover-Prozess und eine Schiebebit-Mutation für den Mutationsprozess.

# tiefe Toolbox einrichten
toolbox = setup_toolbox()

# eine Bevölkerung erstellen
Bevölkerung = toolbox.population_generator(n_bevölkerung)

# Ein einfacher evolutionärer Algorithmus
final_population, Logbuch = eaSimple(
    Population, 
    Werkzeugkasten, 
    Crossover_Wahrscheinlichkeit, 
    Mutation_Wahrscheinlichkeit, 
    n_generationen
)

Wir generieren zunächst eine Population von Individuen der Größe 10. Dann rufen wir die eaSimple-Methode in der Tiefe auf, das einen einfachen genetischen Algorithmus ausführt.

Die Argumente der eaSimple-Funktion,

  • Das erste Argument ist die Bevölkerung
  • toolbox ist die Instanz der Toolbox-Klasse von deap
  • Die Kreuzungswahrscheinlichkeit bezeichnet die Wahrscheinlichkeit, dass sich ein Paar von Individuen kreuzt
  • Mutationswahrscheinlichkeit bezeichnet die Wahrscheinlichkeit, dass ein Individuum mutiert
  • n_generations bezeichnet die Anzahl der zu entwickelnden Generationen.

Der eaSimple-Algorithmus funktioniert wie folgt,

  1. Die Fitness von Individuen in einer Population wird berechnet
  2. Wählen Sie die fitteste Person mit der Turnierauswahlmethode aus.
  3. Kreuzung von Personen nach der One-Point-Crossing-Methode
  4. Mutieren Sie Individuen mit der Flip-Bit-Mutation
  5. Berechnen Sie die Fitness von Einzelpersonen neu.
  6. Folge den Schritten 2 ein 5 bis die gewünschte Generationenzahl erreicht ist.

Daher, kann eine Merkmalsauswahl mit einem genetischen Algorithmus durchführen.

Verweise

[1] Praktische genetische Algorithmen mit Python, Eyal Wirsansky

Vielen Dank!

Die in diesem Artikel gezeigten Medien sind nicht Eigentum von DataPeaker und werden nach Ermessen des Autors verwendet.

Abonniere unseren Newsletter

Wir senden Ihnen keine SPAM-Mail. Wir hassen es genauso wie du.