Eine sanfte Einführung in den genetischen Algorithmus

Ein Bild eines Gens

Wenn Sie anfangen, über künstliche Intelligenz zu forschen, haben Sie vielleicht von etwas gehört, das als "genetischer Algorithmus" bezeichnet wird. Nachdem Sie diesen Begriff gesehen haben, möchten Sie ihn möglicherweise nur ungern untersuchen, da er das Wort "Algorithmus" enthält. Keine Angst! In diesem Artikel zeige ich Ihnen die Einfachheit des genetischen Algorithmus und inspiriere Sie hoffentlich dazu, einen für sich selbst zu erstellen.

Was ist ein genetischer Algorithmus?

Der genetische Algorithmus ist im Grunde eine Methode, die stark vom Prozess der natürlichen Selektion inspiriert ist, um die beste Lösung für ein Problem zu finden.

In der Natur überlebt nur der Starke, der Prozess der Beseitigung des Schwachen wird natürliche Selektion genannt. Genetische Algorithmen verwenden dasselbe Prinzip, um die „schwachen“ Lösungen zu eliminieren und schließlich die beste Lösung zu erhalten.

Normalerweise wird ein genetischer Algorithmus verwendet, wenn Sie nicht wissen, wie die Lösung aussehen wird. Sie möchten beispielsweise ein Auto erstellen, das durch verschiedene Geländearten navigieren kann. Sie können nicht wissen, wie das Auto aussehen wird, aber Sie kennen das Ziel des Autos. In diesem Fall kann der genetische Algorithmus verwendet werden, um das Auto für die Fahrt in verschiedenen Gebieten zu erzeugen, aber das Autodesign wird vom Algorithmus bestimmt.

Der Arbeitsprozess des genetischen Algorithmus

Wie bereits erwähnt, ist der genetische Algorithmus stark von der natürlichen Selektion inspiriert. Um zu sehen, wie der genetische Algorithmus funktioniert, sollten Sie sich tatsächlich ansehen, wie die natürliche Selektion funktioniert.

natürlicher Selektionsprozess (vereinfacht)

Das obige Diagramm zeigt den Prozess der natürlichen Selektion. Es ist klar, dass dieser Prozess 5 Hauptschritte umfasst. Der erste Schritt ist die Auswahl. In diesem Schritt wählt die Natur Individuen mit einem starken Gen aus der ursprünglichen Population aus. Danach beginnen sie, in die nächste Phase der Paarung einzutreten. Nach dem Paarungsschritt bringen sie ein Kind zur Welt. Wir nennen diesen Schritt „Fortpflanzung“. Dieses spezifische Kind mutierte dann, um dem Gen eine gewisse Variation hinzuzufügen, und zog schließlich zurück in die Population.

Der Prozess des genetischen Algorithmus ist dem obigen Prozess ziemlich ähnlich. Der einzige Unterschied besteht darin, dass einige zusätzliche Details hinzugefügt wurden.

Arbeitsprozess des genetischen Algorithmus

Zunächst beginnt der Arbeitsprozess des genetischen Algorithmus auch mit einer anfänglichen Population. Die erste Hauptstufe ist die Berechnung der Fitness. Die Berechnung der Fitness kann als Teil des Auswahlprozesses betrachtet werden, da sie im Wesentlichen zur Berechnung der „Punktzahl“ jedes Individuums verwendet wird, um anzugeben, ob es sich um ein starkes oder ein schwaches Individuum handelt. Alle starken Entitäten werden dann ausgewählt und an eine Stufe übergeben, die als Überkreuzung bezeichnet wird. Diese Stufe entspricht der Paarungsstufe im vorherigen Diagramm. In dieser Phase werden 2 zufällige Eltern aus der Liste der starken Entitäten ausgewählt, um eine sogenannte Überkreuzung durchzuführen, die wir später diskutieren werden. Nach dem Crossover wird ein Kind erstellt und mutiert, um dem Gen eine gewisse Variation hinzuzufügen. Schließlich tritt dieses Kind wieder der Bevölkerung bei und der Vorgang wiederholt sich erneut.

Was zum Teufel ist Fitness

Im genetischen Algorithmus spielt Fitness in der Auswahlphase eine entscheidende Rolle. Fitness ist die „Punktzahl“ für die Auswahl eines Unternehmens, das seine Eigenschaften weitergeben kann. Wenn eine Person beispielsweise an einer schweren Krankheit leidet, ist ihr „Fitness-Score“ niedrig und es ist weniger wahrscheinlich, dass sie Kinder bekommt, da seine Kinder auch seine Krankheit erben würden. Wenn die Fitness einer Lösung gering ist, möchten Sie möglicherweise keine weitere Lösungsbasis darauf erstellen, da das Ergebnis genauso schlecht wäre wie die alte Lösung.

Versuchen Sie sich vorzustellen, dass Sie ein Problem haben. Das Problem besteht darin, die beste Route für Rotkäppchen zu finden, um zu ihrem Oma-Haus zu gelangen. Nehmen wir an, sie möchte in kürzester Zeit ihr Oma-Haus erreichen, daher kann die Eignung einer Route anhand der Reisezeit berechnet werden. Wenn es eine Route gibt, die eine Länge von 400 Metern hat und für die sie 10 Minuten gebraucht hat, ist ihre Fitness definitiv geringer als die einer 500 Meter langen Route, aber sie hat nur 8 Minuten gebraucht, um als Fitness einer zu reisen Die Route berechnet die Basis anhand der Reisezeit und nicht anhand der Länge. Daher wird die 500 Meter lange Route eher für die Kombination mit anderen Routen ausgewählt.

Den Guten auswählen!

Bei der Auswahl der geeigneten Lösung geht es um die Auswahlphase des genetischen Algorithmus. Nach der Berechnung des Fitness-Scores besteht der nächste Schritt darin, mithilfe einiger mysteriöser Methoden eine Liste von Lösungen auszuwählen, die später zur Erstellung einer besseren Lösung verwendet werden können.

Obwohl Sie Ihre eigene Methode zur Auswahl der Anpassungslösungen erstellen können, gibt es einige bekannte Methoden, die Sie verwenden können:

  • Fitness proportionale Auswahl
  • Turnierauswahl
  • Kürzungsauswahl
  • Auswahl der Fitnessuniform

Die obige Liste ist keine adäquate Liste. Weitere Methoden finden Sie hier.

Nehmen wir als Beispiel die erste Methode. Im Gegensatz zu seinem Namen ist das eigentliche Konzept hinter dieser Methode absurd einfach. Die Fitness-Proportional-Auswahl AKA, die Roulette-Rad-Auswahl, ist die Methode zur Auswahl „potenzieller“ Lösungen für die Rekombination.

Stellen Sie sich vor, wenn sich in einer Tüte 10 Murmeln befinden, insbesondere 5 blaue Murmeln, 3 rote Murmeln und 2 weiße Murmeln. Sie können leicht berechnen, dass Sie, wenn Sie einen zufälligen Marmor aus der Tasche auswählen, eine Chance von 5/10 haben, einen blauen auszuwählen, 3/10 für Rot und 2/10 für Weiß. So funktioniert die Fitness-proportionale Auswahl, der Prozess ist jedoch etwas anders.

Bei der proportionalen Fitnessauswahl wird zuerst eine Zufallszahl ausgewählt, die dann zum Vergleich mit der Fitness einer zufällig ausgewählten Lösung verwendet wird. Der Fitnesswert ist normalerweise auf 0 bis 1 beschränkt. Wenn der Zufallswert kleiner als dieser Fitnesswert ist, wird die Lösung ausgewählt. Je höher die Eignung einer Lösung ist, desto höher ist die Wahrscheinlichkeit, dass sie ausgewählt wird. Wenn zum Beispiel eine Zufallszahl von 0 auf 1 geht, gibt es 50%, weniger als 0,5 und 80% weniger als 0,8, jedoch wahrscheinlich nicht weniger als 0,2, dh wenn a Lösung hat eine Fitness von 0,8, es gibt 80%, die für die Rekombination ausgewählt werden, und Lösung, die eine Fitness von 0,2 hat, muss nur 20% ausgewählt werden. Die 0,2-Fitnesslösung wird zwar selten ausgewählt, hilft aber auch dabei, die Lösungsmerkmale zu variieren, da diese Lösung einige Attribute enthalten kann, die für den späteren Erfolg erforderlich sind.

Crossover durchführen

Crossover ist die Phase, in der ausgewählte Lösungen zu neuen Lösungen kombiniert werden. Genau wie in der Auswahlphase gibt es auch viele Crossover-Techniken, die Sie auch hier finden.

Ähnlich wie in der Auswahlphase können Sie in der Crossover-Phase auch Ihre eigenen Crossover-Techniken erfinden. Es gibt jedoch auch einige Techniken, die Sie verwenden können:

  • Einpunkt-Frequenzweiche
  • Zweipunkt-Frequenzweiche
  • Einheitliche Frequenzweiche
  • Crossover mit drei Elternteilen

Zum besseren Verständnis erkläre ich die einheitliche Crossover-Technik, die meiner Meinung nach die am einfachsten zu implementierende Technik ist.

Die einheitliche Crossover-Methode umfasste die zufällige Auswahl eines zufälligen Teils des Gens der 2-Lösung, um eine neue (hoffentlich bessere) Lösung zu kombinieren und zu erstellen.

Der erste Schritt bei der einheitlichen Überkreuzung besteht darin, zwei zufällige Lösungen aus dem Satz von Lösungen auszuwählen, die in der vorherigen Auswahlstufe ausgewählt wurden. Dann wird jeder Teil der 2 Lösungen ausgewählt, um die untergeordnete Lösungsbasis auf einer Variablen hinzuzufügen, die als Mischungsverhältnis bezeichnet wird. Das Mischungsverhältnis entscheidet über die Wahrscheinlichkeit, dass eine Lösung ausgewählt wird, um die untergeordnete Lösung zu ergänzen. Zum Beispiel gibt es zwei Lösungen: A und B, und Sie möchten, dass die untergeordnete Lösung mehr Teile enthält, die aus Lösung A entnommen wurden. Sie können das Mischungsverhältnis erhöhen, nachdem diese Schleife durch alle Teile der Lösung A und B geführt wurde. In jeder Schleife Erstellen Sie eine neue Zufallszahl und vergleichen Sie sie mit dem Mischungsverhältnis. Wenn sie kleiner als das Mischungsverhältnis ist, wählen Sie die Lösung aus. Ein anderer Teil wählt das B. Wenn das Mischungsverhältnis 0,5 beträgt, haben A und B ungefähr 50% von ausgewählt werden.

Gleichmäßige Frequenzweiche mit einem Mischungsverhältnis von 0,5

Das obige Bild zeigt die unter Verwendung von Lösung A und B erzeugte Kinderlösung C mit einem Mischungsverhältnis von 0,5 oder 50%. Jeder Teil beider Lösungen wurde auf der Grundlage des Mischungsverhältnisses ausgewählt oder nicht ausgewählt, und das Mischungsverhältnis wurde mit einer Zufallszahl verglichen, um zu entscheiden. Es ist, als würde man eine Münze werfen, um herauszufinden, wo A anstelle von B verwendet werden soll und umgekehrt.

Mutiere das Kind!

Nein, nein, nein, wir werden unsere Kinder nicht in Typen mit Metallkrallen verwandeln und sie auf einem zufälligen Baumstamm sterben lassen!

Stattdessen ist das Hinzufügen einer Mutation zu einem Kind wie das Helfen

Wenn ein Individuum anders denkt, kann es sein, ob es der Anführer der Herde oder ein kompletter Dummkopf wird.

Ein Beispiel für eine Mutation

Wie Sie sehen können, geht das rote Kind einen anderen Weg als andere Kinder. Der Grund dafür ist, dass wir, wenn das rote Kind der Herde folgt, ihm eine Mutation hinzugefügt haben und ihm daher helfen, einen anderen Weg zu wählen. Natürlich kann dieser andere Weg auch eine Sackgasse sein, aber in diesem Fall führt der Weg eindeutig zum Erfolg! Das ist der wahre Zweck des Mutationsstadiums.

Um ein Kind zu mutieren, gibt es auch eine Vielzahl von Techniken, die Sie verwenden können:

  • Bitstring-Mutation
  • Flip Bit
  • Uneinheitlich
  • Uniform

Weitere finden Sie hier.

Um dies besser zu verstehen, werde ich die Technik der "Bitstring-Mutation" demonstrieren.

Stellen Sie sich vor, Sie machen einen Bot, um Objekte davor zu vermeiden. Der Bot muss alle Objekte meiden, um das endgültige Ziel zu erreichen, und sein natürlicher Zustand bewegt sich vorwärts. Um ein Objekt zu vermeiden, besteht sein Gen aus einer Reihe von "linken" und "rechten" Zeichenfolgen, die angeben, wie sich der Bot bewegen soll.

Die "Bitstring-Mutation" wird normalerweise für binäre Strings verwendet, da diese Methode 1 oder mehr zufällig ausgewählte Bits im Gen umdreht. Beispielsweise:

Beispiel für eine Bitstring-Mutation

Versuchen Sie nun, 1 und 0 in links und rechts umzuwandeln und überlegen Sie, wie sich der Bot verhält. Da der Bot stecken bleiben kann, wenn er auf ein großes Objekt trifft, hilft die Mutation seinen Nachkommen, eine neue Bewegungsrichtung zu wählen und dieses Objekt zu meiden. Stellen Sie sich vor, der Bot dreht sich für viele Generationen nur nach rechts, wenn er auf ein Objekt trifft und stirbt, aber in der nächsten Generation dreht sich der Bot plötzlich nach links, als eine rechte Zeichenfolge in seinem Gen nach links gedreht wurde und der Bot schließlich sein Ziel erreichte. So funktioniert im Grunde die 'Bitstring-Mutation'.

Das Ende des Prozesses

Nach der Mutation des Kindes wird es sich wieder mit einem anderen mutierten Kind zusammenschließen, um eine neue Bevölkerung zu reformieren, und der gesamte Prozess beginnt von vorne.

Wann hört es auf? Die Antwort ist sehr einfach: Wann hören Sie auf, das Tippen mit 10 Fingern zu üben? Wenn Ihre Schreibfähigkeiten natürlich perfekt sind. Ähnlich wie beim genetischen Algorithmus stoppt der Prozess, wenn die Fitness einer bestimmten Lösung die gewünschte Fitness erreicht. Sie möchten beispielsweise, dass der Bot im vorherigen Beispiel das Ziel so schnell wie möglich erreicht.

Sie setzen den Fitness-Schwellenwert auf 4 Minuten. Wenn die Zeit des Bots mehr als 4 Minuten beträgt, wird der Vorgang wiederholt, bis die Endzeit des Bots kleiner oder gleich 4 Minuten ist.

Fazit

Das ist das Ende meines Artikels. Ich hoffe, dass Sie nach diesem Artikel einen besseren Einblick in den genetischen Algorithmus erhalten, der Sie dazu inspiriert hat, einen eigenen zu erstellen.

Hier sind einige Links, über die Sie mehr über genetische Algorithmen erfahren können:

  • Daniel Shiffman Videos über genetische Algorithmen:
  • Mein Beispiel für die Verwendung eines genetischen Algorithmus zum Erraten eines Passcodes
  • Tutorialspoint Tutorial über genetische Algorithmen
  • Goran Muric Video über ein Beispiel mit einem genetischen Algorithmus, um einen Pfad zu finden