Einführung in genetische Algorithmen im maschinellen Lernen

introduction genetic algorithms machine learning

Fragen und Antworten zu fortgeschrittenen SQL-Interviews pdf

Dieses Tutorial zum genetischen Algorithmus erklärt im Detail, was genetische Algorithmen sind und welche Rolle sie beim maschinellen Lernen spielen ::

In dem Vorheriges Tutorial Wir lernten künstliche neuronale Netzwerkmodelle kennen - Multilayer Perceptron, Backpropagation, Radial Bias & Kohonen Self Organizing Maps einschließlich ihrer Architektur.

Wir werden uns auf genetische Algorithmen konzentrieren, die früher als neuronale Netze kamen, aber jetzt wurde GA von NN übernommen. Obwohl GA immer noch Anwendungen im wirklichen Leben hat, wie Optimierungsprobleme wie Zeitplanung, Spielen, Robotik, Hardware-Design, Probleme mit reisenden Verkäufern usw.

Genetische Algorithmen sind Algorithmen, die auf der evolutionären Idee der natürlichen Selektion und Genetik basieren. GAs sind adaptive heuristische Suchalgorithmen, d. H. Die Algorithmen folgen einem iterativen Muster, das sich mit der Zeit ändert. Es ist eine Art von Verstärkungslernen, bei dem das Feedback notwendig ist, ohne den richtigen Weg anzugeben. Das Feedback kann entweder positiv oder negativ sein.

=> Lesen Sie die komplette Schulungsreihe zum maschinellen Lernen durch

Was du lernen wirst:

• Warum genetische Algorithmen verwenden?
  • Biologischer Hintergrund genetischer Algorithmen
• Was sind genetische Algorithmen?
  • Korrelation eines Chromosoms mit GA
  • Wichtige Terminologie in GA
  • Ein einfacher genetischer Algorithmus
  • Auswahlmethode für Roulette-Räder
  • Andere Auswahlmethoden
  • Frequenzweiche
  • Mutation
  • Wann man den genetischen Algorithmus stoppt
• Vor- und Nachteile des genetischen Algorithmus
• Anwendungen genetischer Algorithmen
• Fazit
  • Literatur-Empfehlungen

Warum genetische Algorithmen verwenden?

GAs sind robustere Algorithmen, die für verschiedene Optimierungsprobleme verwendet werden können. Diese Algorithmen weichen im Gegensatz zu anderen AI-Algorithmen bei Vorhandensein von Rauschen nicht leicht ab. GAs können bei der Suche nach großem oder multimodalem Raum verwendet werden.

Biologischer Hintergrund genetischer Algorithmen

Die Genetik leitet sich vom griechischen Wort „Genesis“ ab, das Wachstum bedeutet. Die Genetik entscheidet über die Vererbungsfaktoren, Ähnlichkeiten und Unterschiede zwischen den Nachkommen im Evolutionsprozess. Genetische Algorithmen werden auch aus der natürlichen Evolution abgeleitet.

Einige Terminologien in einem biologischen Chromosom

• Chromosomen: Alle genetischen Informationen einer Art sind Chromosomen gespeichert.
• Gene: Die Chromosomen sind in mehrere Teile unterteilt, die als Gene bezeichnet werden.
• Allele: Die Gene identifizieren die Charakteristik eines Individuums. Die Möglichkeit einer Kombination von Genen zur Bildung von Eigenschaften wird Allele genannt. Ein Gen kann verschiedene Allele haben.
• Gen Pool: Alle möglichen Kombinationen von Genen, die alle Allele in einem Populationspool sind, werden als Genpool bezeichnet.
• Genom: Der Satz von Genen einer Spezies wird als Genom bezeichnet.
• Ort: Jedes Gen hat eine Position in einem Genom, das als Locus bezeichnet wird.
• Genotyp: Eine vollständige Kombination von Genen in einem Individuum wird als Genotyp bezeichnet.
• Phänotyp: Eine Reihe von Genotypen in dekodierter Form wird als Phänotyp bezeichnet.

Was sind genetische Algorithmen?

Die genetischen Algorithmen stimulieren den Prozess wie in natürlichen Evolutionssystemen. Charles Darwin stellte die Evolutionstheorie auf, dass sich biologische Wesen in der natürlichen Evolution nach dem Prinzip des „Überlebens der Stärksten“ entwickeln. Die GA-Suche soll die Theorie des „Überlebens der Stärkeren“ fördern.

Die GAs führen eine zufällige Suche durch, um Optimierungsprobleme zu lösen. Die GA verwendet Techniken, die die vorherigen historischen Informationen verwenden, um ihre Suche auf die Optimierung im neuen Suchraum auszurichten.

Korrelation eines Chromosoms mit GA

Der menschliche Körper hat Chromosomen, die aus Genen bestehen. Ein Satz aller Gene einer bestimmten Spezies wird als Genom bezeichnet. Bei Lebewesen sind die Genome in verschiedenen Chromosomen gespeichert, während bei GA alle Gene im selben Chromosom gespeichert sind.

Vergleich zwischen natürlicher Evolution und genetischer Algorithmus-Terminologie

Wichtige Terminologie in GA

• Population: Es ist eine Gruppe von Individuen. Die Population umfasst die Anzahl der getesteten Personen, Informationen zum Suchraum und die Phänotypparameter. Im Allgemeinen wird die Population zufällig initialisiert.
• Einzelpersonen: Einzelpersonen sind eine einzige Lösung in der Bevölkerung. Ein Individuum hat eine Reihe von Parametern, die Gene genannt werden. Gene kombiniert, um Chromosomen zu bilden.
• Gene: Gene sind Bausteine ​​genetischer Algorithmen. Ein Chromosom besteht aus Genen. Die Gene können die Lösung des Problems bestimmen. Sie werden durch eine Bitfolge (0 oder 1) zufälliger Länge dargestellt.
• Fitness: Die Fitness gibt den Wert des Phänotyps des Problems an. Die Fitnessfunktion gibt an, wie nahe die Lösung an der optimalen Lösung liegt. Die Fitnessfunktion wird auf viele Arten bestimmt, beispielsweise durch die Summe aller mit dem Problem verbundenen Parameter - euklidischer Abstand usw. Es gibt keine Regel zur Bewertung der Fitnessfunktion.

Ein einfacher genetischer Algorithmus

Eine einfache GA hat eine Population einzelner Chromosomen. Diese Chromosomen stellen mögliche Lösungen dar. Über diese Chromosomensätze werden Reproduktionsoperatoren angewendet, um Mutationen und Rekombinationen durchzuführen. Daher ist es wichtig, geeignete Reproduktionsoperatoren zu finden, da das Verhalten von GA davon abhängt.

Ein einfacher genetischer Algorithmus lautet wie folgt:

# 1) Beginnen Sie mit der zufällig erstellten Population.

#zwei) Berechnen Sie die Fitnessfunktion jedes Chromosoms.

#3) Wiederholen Sie die Schritte, bis n Nachkommen entstehen. Die Nachkommen werden wie unten gezeigt erstellt.

• Wählen Sie ein Chromosomenpaar aus der Population aus.
• Überkreuzen Sie das Paar mit der Wahrscheinlichkeit p_cNachkommen zu bilden.
• Mutieren Sie die Frequenzweiche mit der Wahrscheinlichkeit p_m.

# 4) Ersetzen Sie die ursprüngliche Population durch die neue Population und fahren Sie mit Schritt 2 fort.

Sehen wir uns die Schritte an, die in diesem Iterationsprozess ausgeführt werden. Die anfängliche Population von Chromosomen wird erzeugt. Die anfängliche Population sollte genügend Gene enthalten, damit jede Lösung generiert werden kann. Der erste Bevölkerungspool wird zufällig generiert.

• Auswahl: Der beste Satz von Genen wird abhängig von der Fitnessfunktion ausgewählt. Die Saite mit der besten Fitnessfunktion wird ausgewählt.
• Reproduktion: Neue Nachkommen werden durch Rekombination und Mutation erzeugt.
• Auswertung: Die neu erzeugten Chromosomen werden auf ihre Fitness untersucht.
• Ersatz: In diesem Schritt wird die alte Bevölkerung durch die neu erzeugte Bevölkerung ersetzt.

Auswahlmethode für Roulette-Räder

Die Auswahl von Roulette-Rädern ist die weit verbreitete Auswahlmethode.

Der Auswahlprozess ist kurz wie unten gezeigt:

Bei diesem Verfahren wird eine lineare Suche durch das Roulette-Rad durchgeführt. Die Schlitze im Rad werden nach dem individuellen Fitnesswert gewogen. Der Zielwert wird zufällig entsprechend dem Anteil der Summe der Fitness in der Bevölkerung festgelegt.

Die Population wird dann durchsucht, bis der Zielwert erreicht ist. Diese Methode garantiert nicht die Stärksten der Individuen, hat aber die Wahrscheinlichkeit, die Stärksten zu sein.

Sehen wir uns die Schritte zur Auswahl des Roulette-Rads an.

Der erwartete Wert eines Individuums = Individuelle Fitness / Fitness der Bevölkerung. Die Radschlitze werden Personen aufgrund ihrer Fitness zugewiesen. Das Rad wird N-mal gedreht, wobei N die Gesamtzahl der Personen in der Bevölkerung ist. Wenn eine Umdrehung beendet ist, wird die ausgewählte Person in einen Pool von Eltern aufgenommen.

1. Der erwartete Gesamtwert einer Anzahl von Personen in der Bevölkerung sei S.
2. Wiederholen Sie die Schritte 3-5 n Mal.
3. Wählen Sie eine ganze Zahl s zwischen 0 und S.
4. Durchlaufen Sie Einzelpersonen in der Bevölkerung und summieren Sie die erwarteten Werte, bis die Summe größer als s ist.
5. Die Person, deren erwarteter Wert die Summe über den Grenzwert s setzt, wird ausgewählt.

Nachteile der Roulette-Radauswahl:

1. Wenn sich die Fitness stark unterscheidet, wird der Umfang des Roulette-Rads vom Chromosom mit der höchsten Fitnessfunktion maximal erfasst, sodass die anderen nur eine sehr geringe Chance haben, ausgewählt zu werden.
2. Es ist laut.
3. Die Entwicklung hängt von der Varianz in der Fitness der Bevölkerung ab.

Andere Auswahlmethoden

Es gibt viele andere Auswahlmethoden, die in der 'Auswahl' Schritt des genetischen Algorithmus.

Wir werden die 2 anderen weit verbreiteten Methoden diskutieren:

# 1) Rangauswahl: Bei dieser Methode erhält jedes Chromosom einen Fitnesswert aus der Rangfolge. Die schlechteste Fitness ist 1 und die beste Fitness ist N. Es ist eine langsame Konvergenzmethode. Bei dieser Methode bleibt die Vielfalt erhalten, was zu einer erfolgreichen Suche führt.

Potenzielle Eltern werden ausgewählt und anschließend wird ein Turnier abgehalten, um zu entscheiden, welche der Personen Eltern sein werden.

# 2) Turnierauswahl: Bei dieser Methode wird eine selektive Druckstrategie auf die Bevölkerung angewendet. Der beste Mensch ist der mit der höchsten Fitness. Diese Person ist der Gewinner des Turnierwettbewerbs unter Nu-Personen in der Bevölkerung.

Die Turnierpopulation wird zusammen mit dem Gewinner erneut in den Pool aufgenommen, um neue Nachkommen zu generieren. Der Unterschied in den Fitnesswerten des Gewinners und der Personen im Paarungspool sorgt für einen selektiven Druck für optimale Ergebnisse.

Frequenzweiche

Es ist ein Prozess, bei dem zwei Personen genommen und daraus ein Kind geboren werden. Der Reproduktionsprozess nach der Auswahl macht Klone der guten Stiche. Der Crossover-Operator wird auf die Saiten angewendet, um einen besseren Nachwuchs zu erzeugen.

Die Implementierung des Crossover-Operators ist wie folgt:

1. Zwei Individuen werden zufällig aus der Population ausgewählt, um Nachkommen zu zeugen.
2. Eine Cross-Site wird zufällig entlang der Länge der Zeichenfolge ausgewählt.
3. Die Werte auf der Site werden ausgetauscht.

Die durchgeführte Frequenzweiche kann eine Einzelpunktkreuzung, eine Zweipunktkreuzung, eine Mehrpunktkreuzung usw. sein. Die Einzelpunktkreuzung hat eine Kreuzungsstelle, während eine Zweipunktkreuzungsstelle zwei Stellen hat, an denen die Werte vertauscht werden.

Wir können dies im folgenden Beispiel sehen:

Single Point Crossover

Zweipunkt-Frequenzweiche

Crossover-Wahrscheinlichkeit

P._cDie Überkreuzungswahrscheinlichkeit ist der Begriff, der beschreibt, wie oft die Überkreuzung durchgeführt wird. Eine Wahrscheinlichkeit von 0% bedeutet, dass die neuen Chromosomen eine exakte Kopie der alten Chromosomen sind, während eine Wahrscheinlichkeit von 100% bedeutet, dass alle neuen Chromosomen durch Überkreuzung hergestellt werden.

Mutation

Die Mutation erfolgt nach Crossover. Während sich Crossover nur auf die aktuelle Lösung konzentriert, durchsucht die Mutationsoperation den gesamten Suchraum. Diese Methode dient dazu, die verlorene genetische Information wiederherzustellen und die genetische Information zu verteilen.

Dieser Operator trägt zur Erhaltung der genetischen Vielfalt in der Bevölkerung bei. Es hilft, lokale Minima zu vermeiden und nutzlose Lösungen aus jeder Bevölkerung zu generieren.

Die Mutation wird auf viele Arten durchgeführt, beispielsweise indem der Wert jedes Gens mit geringer Wahrscheinlichkeit invertiert wird oder eine Mutation nur durchgeführt wird, wenn sie die Qualität der Lösung verbessert.

Einige der Arten der Mutation sind:

• Umdrehen: Wechsel von 0 zu 1 oder 1 zu 0.
• Austausch: Es werden zwei zufällige Positionen ausgewählt und die Werte ausgetauscht.
• Umkehren: Die zufällige Position wird gewählt und die Bits daneben werden umgekehrt.

Sehen wir uns jeweils einige Beispiele an:

Umdrehen

Austausch

Umkehren

Mutationswahrscheinlichkeit

P._mDie Mutationswahrscheinlichkeit ist ein Begriff, der entscheidet, wie oft die Chromosomen mutiert werden. Wenn die Mutationswahrscheinlichkeit 100% beträgt, bedeutet dies, dass das gesamte Chromosom verändert wird. Wenn keine Mutation durchgeführt wird, werden direkt nach dem Crossover neue Nachkommen erzeugt.

Ein Beispiel für einen allgemeinen genetischen Algorithmus Mutationswahrscheinlichkeit: P._mDie Mutationswahrscheinlichkeit ist ein Begriff, der entscheidet, wie oft die Chromosomen mutiert werden. Wenn die Mutationswahrscheinlichkeit 100% beträgt, bedeutet dies, dass das gesamte Chromosom verändert wird.

Wenn keine Mutation durchgeführt wird, werden die neuen Nachkommen direkt nach der Überkreuzung erzeugt. Die anfängliche Population von Chromosomen wird als A, B, C, D angegeben. Die Populationsgröße beträgt 4.

Die Fitnessfunktion wird als Anzahl von Einsen in der Zeichenfolge verwendet.

Die Summe der Fitness ist 12, was bedeutet, dass die durchschnittliche Fitnessfunktion ~ 12/4 = 3 wäre

Übergangswahrscheinlichkeit = 0,7

Mutationswahrscheinlichkeit = 0,001

# 1) Wenn B und C ausgewählt sind, wird die Frequenzweiche nicht ausgeführt, da der Fitnesswert von C unter der durchschnittlichen Fitness liegt.

#zwei) B ist mutiert => B: 11101110 -> B.^': 01101110 zur Erhaltung der Bevölkerungsvielfalt

#3) B und D ausgewählt sind, wird die Frequenzweiche durchgeführt.

B: 11101110 E: 10110100 -> D: 00110100 F: 01101110

# 4) Wenn E mutiert ist, dann

E: 10110100 -> E.^': 10110000

Entsprechende Chromosomen sind in der folgenden Tabelle aufgeführt. Die Reihenfolge wird zufällig festgelegt.

Obwohl die fittere Person mit einem Fitnesswert von 6 verloren geht, steigt die durchschnittliche Fitness der Bevölkerung insgesamt an und würde betragen: 14/4 = 3,5

Wann man den genetischen Algorithmus stoppt

Ein genetischer Algorithmus wird gestoppt, wenn einige der unten aufgeführten Bedingungen erfüllt sind:

# 1) Beste individuelle Konvergenz: Wenn das minimale Fitnessniveau unter den Konvergenzwert fällt, wird der Algorithmus gestoppt. Dies führt zu einer schnelleren Konvergenz.

# 2) Schlechteste individuelle Konvergenz: Wenn die am wenigsten gesunden Personen in der Bevölkerung einen minimalen Fitnesswert unterhalb der Konvergenz erreichen, wird der Algorithmus gestoppt. Bei dieser Methode wird der Mindestfitnessstandard in der Bevölkerung beibehalten. Dies bedeutet, dass die beste Person nicht garantiert ist, aber Personen mit minimalem Fitnesswert anwesend sind.

# 3) Summe der Fitness: Wenn bei dieser Methode die Summe der Fitness kleiner oder gleich dem Konvergenzwert ist, wird die Suche gestoppt. Es garantiert, dass sich die gesamte Bevölkerung im Fitnessbereich befindet.

# 4) Median Fitness: Bei dieser Methode ist mindestens die Hälfte der Personen in der Bevölkerung besser oder gleich dem Konvergenzwert.

Einige Konvergenzkriterien oder Stoppbedingungen können sein:

• Wenn sich eine bestimmte Anzahl von Generationen entwickelt hat.
• Wenn die angegebene Ausführungszeit erreicht ist, wurde der Algorithmus eingehalten.
• Wenn sich der Fitnesswert der Bevölkerung mit Iterationen nicht weiter ändert.

Vor- und Nachteile des genetischen Algorithmus

Vorteile eines genetischen Algorithmus sind:

1. Es hat einen größeren Lösungsraum.
2. Es ist einfacher, das globale Optimum zu entdecken.
3. Parallelität: Mehrere GAs können mit derselben CPU zusammen ausgeführt werden, ohne sich gegenseitig zu stören. Sie laufen parallel isoliert.

Einschränkungen von GA:

1. Die Identifizierung der Fitnessfunktion ist eine Einschränkung.
2. Die Konvergenz der Algorithmen kann zu schnell oder zu langsam sein.
3. Die Auswahl der Parameter wie Crossover, Mutationswahrscheinlichkeit, Populationsgröße usw. ist begrenzt.

Anwendungen genetischer Algorithmen

GA ist effektiv, um hochdimensionale Probleme zu lösen. Eine GA wird effektiv verwendet, wenn der Suchraum sehr groß ist, keine mathematischen Problemlösungstechniken verfügbar sind und andere herkömmliche Suchalgorithmen nicht funktionieren.

Einige Anwendungen, bei denen GA verwendet wird:

• Optimierungsproblem: Eines der besten Beispiele für die Optimierungsprobleme ist das Problem der Reiseverkäufer, bei dem GA verwendet wird. Andere Optimierungsprobleme wie Job Scheduling und GAs zur Optimierung der Klangqualität sind weit verbreitet.
• Immunsystemmodell: GAs werden verwendet, um verschiedene Aspekte des Immunsystems für einzelne Gen- und Multi-Gen-Familien während der Evolutionszeit zu modellieren.
• Maschinelles Lernen: GAs wurden verwendet, um Probleme im Zusammenhang mit Klassifizierung, Vorhersage, Lernregeln und Klassifizierung zu lösen .

Fazit

Genetische Algorithmen basieren auf der Methode der natürlichen Evolution. Diese Algorithmen unterscheiden sich von den anderen Klassifizierungsalgorithmen, da sie codierte Parameter (0 oder 1) verwenden, mehrere Personen in einer Population vorhanden sind und die probabilistische Methode zur Konvergenz verwenden.

Mit dem Prozess der Überkreuzung und Mutation konvergieren die GAs bei aufeinanderfolgenden Generationen. Die Ausführung eines GA-Algorithmus garantiert nicht immer eine erfolgreiche Lösung. Die genetischen Algorithmen sind hocheffizient bei der Optimierung - Probleme bei der Auftragsplanung.

Hoffe, dieses Tutorial hätte Ihr Wissen über das Konzept der genetischen Algorithmen bereichert!

=> Besuchen Sie hier für die exklusive maschinelle Lernserie

Literatur-Empfehlungen

• Modellbasiertes Testen mit genetischem Algorithmus
• Data Mining gegen maschinelles Lernen gegen künstliche Intelligenz gegen tiefes Lernen
• Tutorial für maschinelles Lernen: Einführung in ML und seine Anwendungen
• Arten des maschinellen Lernens: Überwachtes gegen unbeaufsichtigtes Lernen
• Eine vollständige Anleitung zum künstlichen neuronalen Netz beim maschinellen Lernen
• 11 beliebtesten Software-Tools für maschinelles Lernen im Jahr 2021
• Top 13 der BESTEN Unternehmen für maschinelles Lernen (Aktualisierte Liste 2021)
• Was ist Support Vector Machine (SVM) beim maschinellen Lernen?