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.
Bildquelle: praktischer genetischer Algorithmus mit Python, Eyal Wirsansky
Population
Da ein Individuum als Chromosom dargestellt wird, eine Population ist eine Ansammlung solcher Chromosomen.
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
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
Allgemeiner Arbeitsablauf eines einfachen genetischen Algorithmus
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,
- Die Fitness von Individuen in einer Population wird berechnet
- Wählen Sie die fitteste Person mit der Turnierauswahlmethode aus.
- Kreuzung von Personen nach der One-Point-Crossing-Methode
- Mutieren Sie Individuen mit der Flip-Bit-Mutation
- Berechnen Sie die Fitness von Einzelpersonen neu.
- 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.
