Künstliches Neuronales Netz - Genetischer Algorithmus
Die Natur war schon immer eine großartige Inspirationsquelle für die ganze Menschheit. Genetische Algorithmen (GAs) sind suchbasierte Algorithmen, die auf den Konzepten der natürlichen Selektion und Genetik basieren. GAs sind eine Teilmenge eines viel größeren Berechnungszweigs, der als bekannt istEvolutionary Computation.
GAs wurde von John Holland und seinen Studenten und Kollegen an der University of Michigan, insbesondere David E. Goldberg, entwickelt und seitdem mit großem Erfolg an verschiedenen Optimierungsproblemen getestet.
In GAs haben wir einen Pool oder eine Population möglicher Lösungen für das gegebene Problem. Diese Lösungen werden dann rekombiniert und mutiert (wie in der natürlichen Genetik), wodurch neue Kinder entstehen, und der Prozess wird über verschiedene Generationen wiederholt. Jeder Person (oder Kandidatenlösung) wird ein Fitnesswert zugewiesen (basierend auf ihrem objektiven Funktionswert), und den fitteren Individuen wird eine höhere Chance gegeben, sich zu paaren und mehr "fitter" Individuen hervorzubringen. Dies steht im Einklang mit der darwinistischen Theorie des „Überlebens der Stärkeren“.
Auf diese Weise „entwickeln“ wir über Generationen hinweg immer bessere Individuen oder Lösungen, bis wir ein Stoppkriterium erreichen.
Genetische Algorithmen sind von Natur aus ausreichend randomisiert, bieten jedoch eine viel bessere Leistung als die zufällige lokale Suche (bei der wir nur verschiedene zufällige Lösungen ausprobieren und die bisher besten verfolgen), da sie auch historische Informationen nutzen.
Vorteile von GAs
GAs haben verschiedene Vorteile, die sie sehr beliebt gemacht haben. Dazu gehören -
Benötigt keine abgeleiteten Informationen (die für viele reale Probleme möglicherweise nicht verfügbar sind).
Ist schneller und effizienter als die herkömmlichen Methoden.
Hat sehr gute parallele Fähigkeiten.
Optimiert sowohl kontinuierliche als auch diskrete Funktionen sowie Probleme mit mehreren Objektiven.
Bietet eine Liste mit „guten“ Lösungen und nicht nur eine einzige Lösung.
Erhält immer eine Antwort auf das Problem, das mit der Zeit besser wird.
Nützlich, wenn der Suchraum sehr groß ist und eine große Anzahl von Parametern beteiligt ist.
Einschränkungen von GAs
Wie jede Technik leiden auch GAs unter einigen Einschränkungen. Dazu gehören -
GAs sind nicht für alle Probleme geeignet, insbesondere für Probleme, die einfach sind und für die abgeleitete Informationen verfügbar sind.
Der Fitnesswert wird wiederholt berechnet, was bei einigen Problemen rechenintensiv sein kann.
Da es stochastisch ist, gibt es keine Garantie für die Optimalität oder die Qualität der Lösung.
Bei nicht ordnungsgemäßer Implementierung konvergiert GA möglicherweise nicht zur optimalen Lösung.
GA - Motivation
Genetische Algorithmen haben die Fähigkeit, eine "gut genug" -Lösung "schnell genug" zu liefern. Dies macht Gas attraktiv für die Lösung von Optimierungsproblemen. Die Gründe, warum GAs benötigt werden, sind folgende:
Schwierige Probleme lösen
In der Informatik gibt es eine Vielzahl von Problemen NP-Hard. Dies bedeutet im Wesentlichen, dass selbst die leistungsstärksten Computersysteme sehr lange (sogar Jahre!) Brauchen, um dieses Problem zu lösen. In einem solchen Szenario erweisen sich GAs als effizientes Instrumentusable near-optimal solutions in kurzer Zeit.
Versagen gradientenbasierter Methoden
Traditionelle kalkülbasierte Methoden beginnen an einem zufälligen Punkt und bewegen sich in Richtung des Gradienten, bis wir die Spitze des Hügels erreichen. Diese Technik ist effizient und funktioniert sehr gut für Zielfunktionen mit einem Peak wie die Kostenfunktion bei der linearen Regression. In den meisten realen Situationen haben wir jedoch ein sehr komplexes Problem, das als Landschaften bezeichnet wird und aus vielen Gipfeln und vielen Tälern besteht. Dies führt dazu, dass solche Methoden fehlschlagen, da sie unter der inhärenten Tendenz leiden, wie gezeigt an den lokalen Optima hängen zu bleiben in der folgenden Abbildung.
Schnelle Lösung
Einige schwierige Probleme wie das Travelling Salesman Problem (TSP) haben reale Anwendungen wie Pfadfindung und VLSI-Design. Stellen Sie sich nun vor, Sie verwenden Ihr GPS-Navigationssystem und es dauert einige Minuten (oder sogar einige Stunden), um den „optimalen“ Pfad von der Quelle zum Ziel zu berechnen. Eine Verzögerung in solchen realen Anwendungen ist nicht akzeptabel, und daher ist eine „ausreichend gute“ Lösung erforderlich, die „schnell“ geliefert wird.
Wie verwende ich GA für Optimierungsprobleme?
Wir wissen bereits, dass Optimierung eine Aktion ist, um etwas wie Design, Situation, Ressource und System so effektiv wie möglich zu gestalten. Der Optimierungsprozess ist in der folgenden Abbildung dargestellt.
Stufen des GA-Mechanismus für den Optimierungsprozess
Das Folgende sind die Stufen des GA-Mechanismus, wenn er zur Optimierung von Problemen verwendet wird.
Generieren Sie die anfängliche Population zufällig.
Wählen Sie die ursprüngliche Lösung mit den besten Fitnesswerten.
Kombinieren Sie die ausgewählten Lösungen mithilfe von Mutations- und Crossover-Operatoren neu.
Fügen Sie Nachkommen in die Population ein.
Wenn nun die Stoppbedingung erfüllt ist, geben Sie die Lösung mit dem besten Fitnesswert zurück. Andernfalls fahren Sie mit Schritt 2 fort.