Genetische Algorithmen - Einführung
Der genetische Algorithmus (GA) ist eine suchbasierte Optimierungstechnik, die auf den Prinzipien von basiert Genetics and Natural Selection. Es wird häufig verwendet, um optimale oder nahezu optimale Lösungen für schwierige Probleme zu finden, deren Lösung sonst ein Leben lang dauern würde. Es wird häufig zur Lösung von Optimierungsproblemen, in der Forschung und beim maschinellen Lernen verwendet.
Einführung in die Optimierung
Optimierung ist der Prozess von making something better. In jedem Prozess haben wir eine Reihe von Eingaben und eine Reihe von Ausgaben, wie in der folgenden Abbildung gezeigt.
Optimierung bezieht sich darauf, die Werte von Eingaben so zu finden, dass wir die „besten“ Ausgabewerte erhalten. Die Definition von "am besten" variiert von Problem zu Problem, bezieht sich jedoch mathematisch auf das Maximieren oder Minimieren einer oder mehrerer objektiver Funktionen durch Variieren der Eingabeparameter.
Die Menge aller möglichen Lösungen oder Werte, die die Eingaben annehmen können, bildet den Suchraum. In diesem Suchraum liegt ein Punkt oder eine Menge von Punkten, die die optimale Lösung ergeben. Das Ziel der Optimierung besteht darin, diesen Punkt oder diese Menge von Punkten im Suchraum zu finden.
Was sind genetische Algorithmen?
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 wurden 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 eine pool or a population of possible solutionsauf 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 dabei 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 Zielen.
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 der 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 genetische Algorithmen 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 Tälern besteht. Dies führt dazu, dass solche Methoden fehlschlagen, da sie unter der inhärenten Tendenz leiden, an den lokalen Optima hängen zu bleiben wie in der folgenden Abbildung gezeigt.
Schnelle Lösung
Einige schwierige Probleme wie das Travelling Salesperson 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 "gut genug" -Lösung erforderlich, die "schnell" geliefert wird.