Überblick über den genetischen Algorithmus

Optimierungstechniken sind die Techniken, die verwendet werden, um die beste Lösung aus allen möglichen Lösungen herauszufinden, die unter den gegebenen Einschränkungen verfügbar sind. Der genetische Algorithmus ist also ein solcher Optimierungsalgorithmus, der auf der Grundlage des natürlichen Evolutionsprozesses unserer Natur aufgebaut ist. Die Idee der natürlichen Auslese und der genetischen Vererbung wird hier verwendet. Anders als bei anderen Algorithmen wird die geführte Zufallssuche verwendet, dh die optimale Lösung wird gefunden, indem mit einer zufälligen Anfangskostenfunktion begonnen wird und dann nur in dem Raum gesucht wird, der die geringsten Kosten verursacht (in der geführten Richtung). Geeignet, wenn Sie mit großen und komplexen Datensätzen arbeiten.

Was ist ein genetischer Algorithmus?

Der genetische Algorithmus basiert auf der genetischen Struktur und dem Verhalten des Chromosoms der Population. Die folgenden Dinge sind die Grundlage für genetische Algorithmen.

  • Jedes Chromosom gibt eine mögliche Lösung an. Somit ist die Population eine Sammlung von Chromosomen.
  • Jeder Mensch in der Bevölkerung ist durch eine Fitnessfunktion gekennzeichnet. Bessere Fitness ist die Lösung.
  • Von den verfügbaren Individuen in der Population werden die besten Individuen für die Fortpflanzung der Nachkommen der nächsten Generation verwendet.
  • Der gebildete Nachwuchs wird Merkmale beider Elternteile aufweisen und ist ein Ergebnis einer Mutation. Eine Mutation ist eine kleine Veränderung der Genstruktur.

Phasen des genetischen Algorithmus

Nachfolgend sind die verschiedenen Phasen des genetischen Algorithmus aufgeführt:

1. Initialisierung der Population (Codierung)

  • Jedes Gen repräsentiert einen Parameter (Variablen) in der Lösung. Diese Sammlung von Parametern, die die Lösung bildet, ist das Chromosom. Die Bevölkerung ist eine Sammlung von Chromosomen.
  • Reihenfolge der Gene auf dem Chromosom ist wichtig.
  • Meistens werden Chromosomen binär als 0 und 1 dargestellt, es sind jedoch auch andere Kodierungen möglich.

2. Fitness-Funktion

  • Aus den verfügbaren Chromosomen müssen wir die besten für die Fortpflanzung von Nachkommen auswählen, damit jedes Chromosom einen Fitnesswert erhält.
  • Der Fitness-Score hilft bei der Auswahl der Personen, die für die Reproduktion verwendet werden.

3. Auswahl

  • Das Hauptziel dieser Phase ist es, die Region zu finden, in der die Chancen größer sind, die beste Lösung zu erhalten.
  • Die Inspiration dafür ist das Überleben der Stärksten.
  • Es sollte ein Gleichgewicht zwischen Erkundung und Nutzung des Suchraums hergestellt werden.
  • GA versucht, den Genotyp im Suchraum auf eine höhere Fitness zu bringen.
  • Eine zu starke Neigung zur Fitnessauswahl kann zu suboptimalen Lösungen führen.
  • Eine zu geringe Auswahl von Fitness-Bias führt zu einer unkonzentrierten Suche.
  • Daher wird Fitness-Proportional-Selektion verwendet, die auch als Roulette-Rad-Selektion bezeichnet wird. Sie ist ein genetischer Operator, der in genetischen Algorithmen zur Auswahl potenziell nützlicher Lösungen für die Rekombination verwendet wird.

4. Vervielfältigung

Die Erzeugung von Nachkommen erfolgt auf zwei Arten:

  • Frequenzweiche
  • Mutation

über

Crossover ist die wichtigste Phase im genetischen Algorithmus. Während der Überkreuzung wird ein zufälliger Punkt ausgewählt, während ein Elternpaar gepaart wird, um Nachkommen zu erzeugen.

Es gibt 3 Haupttypen von Frequenzweichen.

  • Single Point Crossover: Ein Punkt auf den Chromosomen beider Eltern wird zufällig ausgewählt und als Crossover-Punkt bezeichnet. Bits rechts von diesem Punkt werden zwischen den beiden Elternchromosomen ausgetauscht.
  • Zweipunkt-Überkreuzung: Zwei Überkreuzungspunkte werden zufällig von den Elternchromosomen ausgewählt. Die Bits zwischen den beiden Punkten werden zwischen den Elternorganismen ausgetauscht.
  • Gleichmäßige Überkreuzung: Bei einer gleichmäßigen Überkreuzung wird in der Regel jedes Bit mit gleicher Wahrscheinlichkeit aus einem der übergeordneten Elemente ausgewählt.

Die neuen Nachkommen werden in die Population aufgenommen.

b) Mutation

Bei einigen neu gebildeten Nachkommen können einige ihrer Gene einer Mutation mit einer geringen Zufallswahrscheinlichkeit ausgesetzt sein. Dies zeigt an, dass einige der Bits im Bit-Chromosom umgedreht werden können. Mutationen sorgen zufällig für Vielfalt in der Bevölkerung und verhindern eine vorzeitige Konvergenz.

5. Konvergenz (wann zu stoppen)

Wenige Regeln, die befolgt werden, sagen, wann zu stoppen ist wie folgt:

  • Wenn sich die Qualität der Lösung nach Abschluss einer bestimmten Anzahl von Generationen nicht verbessert, die vor der Hand liegen.
  • Wenn eine harte und schnelle Spanne von Generationen und Zeiten erreicht ist.
  • Bis eine akzeptable Lösung erhalten wird.

Anwendung des genetischen Algorithmus

In diesem Abschnitt werden einige Bereiche besprochen, in denen der genetische Algorithmus häufig angewendet wird.

1. Reise- und Versandweg

Das Problem des Handlungsreisenden ist eine der Hauptanwendungen des genetischen Algorithmus. Wenn ein Reiseplaner beispielsweise gebeten wird, eine Reise zu planen, greift er auf einen genetischen Algorithmus zurück, der nicht nur die Gesamtkosten der Reise senkt, sondern auch die Zeit verkürzt. GE wird auch für die Planung der Zustellung verwendet der Produkte von Ort zu Ort auf die effizienteste Weise.

2. Robotik

Der genetische Algorithmus ist in der Robotik weit verbreitet. Roboter unterscheiden sich durch den Zweck, für den sie gebaut wurden. Zum Beispiel sind nur wenige für eine Kochaufgabe, nur wenige für Unterrichtsaufgaben usw. gebaut.

  • Auswahl wichtiger Merkmale im angegebenen Datensatz.
  • Bei der herkömmlichen Methode werden die wichtigen Features im Datensatz mithilfe der folgenden Methode ausgewählt. Sie sehen sich die Wichtigkeit dieses Modells an und legen dann einen Schwellenwert für die Features fest. Wenn das Feature einen Wichtigkeitswert hat, der größer als ein Schwellenwert ist, wird dies berücksichtigt.
  • Aber hier verwenden wir eine Methode, die als Rucksackproblem bezeichnet wird.
  • Wir werden wieder mit der Population eines Chromosoms beginnen, wobei jedes Chromosom eine binäre Kette sein wird. 1 bezeichnet die "Einbeziehung" von Merkmalen in das Modell und 0 bezeichnet die "Ausschließung" von Merkmalen in das Modell.
  • Die Fitness-Funktion hier wird unsere Genauigkeitsmetrik des Wettbewerbs sein. Je genauer unser Chromosomensatz die Werte vorhersagt, desto besser passt er.
  • Es gibt viele andere Anwendungen von genetischen Algorithmen wie DNA-Analyse, Scheduling-Anwendungen und Engineering-Design.

Fazit

Im aktuellen Szenario wird GE in großen Fertigungsunternehmen wie Flugzeugen usw. eingesetzt, um den Zeit- und Ressourcenverbrauch zu optimieren. Weitere Wissenschaftler arbeiten daran, neue Wege zu finden, um genetische Algorithmen mit anderen Optimierungstechniken zu kombinieren.

Empfohlene Artikel

Dies ist eine Anleitung zu Was ist ein genetischer Algorithmus? Hier diskutieren wir die Einführung, Phasen und Anwendungen des genetischen Algorithmus. Sie können auch unsere anderen Artikelvorschläge durchgehen -

  1. Routing-Algorithmen
  2. Arten von Algorithmen
  3. Neuronale Netzwerkalgorithmen
  4. Data Mining-Algorithmen
  5. Anleitung zu Beispielen für C ++ - Algorithmen

Kategorie:

Große Daten