Was genau sind genetische Algorithmen und für welche Probleme sind sie gut?

Ich habe bemerkt, dass ein paar Fragen auf dieser Seite genetische Algorithmen erwähnen und mir klar wurde, dass ich nicht wirklich viel darüber weiß.

Ich habe den Begriff schon einmal gehört, aber ich habe ihn noch nie benutzt, daher habe ich keine Ahnung, wie sie funktionieren und wofür sie gut sind. Ich weiß nur, dass sie eine Art Evolution beinhalten und sich zufällig ändernde Werte.

Können Sie mir eine kurze Erklärung geben, vorzugsweise mit einem praktischen Beispiel, das die Grundprinzipien veranschaulicht?

Evolutionäre Algorithmen sind eine Familie von Optimierungsalgorithmen, die auf dem Prinzip der Darwinschen natürlichen Selektion basieren . Als Teil der natürlichen Auslese hat eine gegebene Umgebung eine Population von Individuen, die um Überleben und Fortpflanzung konkurrieren. Die Fähigkeit jedes Einzelnen, diese Ziele zu erreichen, bestimmt seine Chance, Kinder zu haben, dh, seine Gene an die nächste Generation von Einzelpersonen weiterzugeben, die aus genetischen Gründen die Chance haben, diese Ziele besser und besser zu verwirklichen zwei Ziele.

Dieses Prinzip der kontinuierlichen Verbesserung über die Generationen hinweg wird von evolutionären Algorithmen übernommen, um die Lösungen für ein Problem zu optimieren. In der ersten Generation wird eine Population, die sich aus verschiedenen Individuen zusammensetzt , zufällig oder mit anderen Methoden erzeugt. Ein Individuum ist eine mehr oder weniger gute Lösung des Problems: Die Qualität des Individuums in Bezug auf das Problem wird Fitness genannt , was die Angemessenheit der Lösung des zu lösenden Problems widerspiegelt. Je höher die Fitness eines Individuums ist, desto höher ist die Wahrscheinlichkeit, dass ein Teil oder der gesamte Genotyp an die Individuen der nächsten Generation weitergegeben wird.

Ein Individuum wird als ein Genotyp codiert , der eine beliebige Form haben kann, wie beispielsweise ein ** Bit-Vektor ( genetische Algorithmen ) oder ein realer Vektor (Evolutionsstrategien). Jeder Genotyp wird bei der Beurteilung des Individuums, dh bei der Berechnung seiner Fitness , in einen Phänotyp umgewandelt . In einigen Fällen ist der Phänotyp identisch mit dem Genotyp: Man spricht von direkter Kodierung. Andernfalls wird die Codierung als indirekt bezeichnet. Angenommen, Sie möchten die Größe eines rechteckigen Parallelepipeds optimieren, die durch seine Länge, Höhe und Breite definiert ist. Nehmen wir zur Vereinfachung des Beispiels an, dass diese drei Größen ganze Zahlen zwischen 0 und 15 sind. Wir können sie dann jeweils mit einer 4-Bit-Binärzahl beschreiben. Ein Beispiel für eine mögliche Lösung könnte der Genotyp 0001 0111 01010 sein. Der entsprechende Phänotyp ist ein Parallelepiped der Länge 1, Höhe 7 und Breite 10.

Während des Übergangs von der alten auf die neue Generation genannt Variation Operatoren , deren Zweck es ist , Menschen zu manipulieren. Es gibt zwei verschiedene Arten von Variationsoperatoren:

• die Mutation Operatoren , die als genetische Mutationen im gleichen Individuum, einzuführen Variationen verwendet werden;
• die Kreuzungsoperator , die verwendet werden , mindestens zwei verschiedene Genotypen, wie genetische Kreuzungen überqueren aus der Zucht.

Evolutionäre Algorithmen haben sich in verschiedenen Bereichen wie Operations Research, Robotics, Biology, Nuance oder Cryptography bewährt. Darüber hinaus können sie mehrere Objektive gleichzeitig optimieren und können als Black Box verwendet werden, da sie im mathematischen Modell keine zu optimierenden Eigenschaften annehmen. Ihre einzige wirkliche Einschränkung ist die rechnerische Komplexität.

Ein genetischer Algorithmus ist ein Algorithmus, der zufällig eine Reihe von Lösungsversuchen für ein Problem generiert. Diese Menge von Lösungsversuchen wird als "Population" bezeichnet.

Anschließend wird versucht, anhand einer bestimmten Fitnessfunktion zu ermitteln, wie gut diese Lösungen das Problem lösen . Die versuchten Lösungen mit dem besten Fitnesswert werden verwendet, um eine neue Population zu generieren. Dies kann erreicht werden, indem kleine Änderungen an den versuchten Lösungen vorgenommen werden (Mutation) oder indem vorhandene versuchte Lösungen kombiniert werden (Crossover).

Die Idee ist, dass im Laufe der Zeit ein Lösungsversuch entsteht, der einen ausreichend hohen Fitnesswert aufweist, um das Problem zu lösen.

Die Inspiration dafür kam von der Evolutionstheorie; Die besten Lösungen überleben und entwickeln sich.

Beispiel 1

Angenommen, Sie suchen nach der effizientesten Methode, um mehrere Formen aus einem Holzstück zu schneiden. Sie möchten so wenig Holz wie möglich verschwenden.

Ihre versuchten Lösungen wären zufällige Anordnungen dieser Formen auf Ihrem Stück Holz. Die Fitness wird dadurch bestimmt, wie wenig Holz nach dem Schneiden der Formen nach dieser Anordnung übrig bleibt.
Je weniger Holz übrig bleibt, desto besser ist der Lösungsversuch.

Beispiel 2

Angenommen, Sie haben versucht, ein Polynom zu finden, das eine Reihe von Punkten durchläuft. Ihre versuchten Lösungen wären zufällige Polynome.
Um die Eignung dieser Polynome zu bestimmen, bestimmen Sie, wie gut sie zu den angegebenen Punkten passen. (In diesem speziellen Fall würden Sie wahrscheinlich die Methode der kleinsten Quadrate verwenden, um zu bestimmen, wie gut das Polynom zu den Punkten passt.) Bei einer Reihe von Versuchen würden Sie Polynome erhalten, die besser zu den Punkten passen, bis Sie ein Polynom hatten, das genau genug zu den Punkten passt.

Diese Antwort fordert ein praktisches Beispiel für die Verwendung einer Antwort, das ich zusätzlich zu den anderen Antworten geben möchte. Sie scheinen sehr gut zu erklären, was ein genetischer Algorithmus ist. Dies wird also ein Beispiel geben.

Nehmen wir an, Sie haben ein neuronales Netzwerk (obwohl es nicht die einzige Anwendung ist), das von einigen gegebenen Eingaben einige Ausgaben liefert. Ein genetischer Algorithmus kann eine Population von diesen erstellen, und indem er sieht, welche Ausgabe die beste ist, werden Mitglieder der Population gezüchtet und getötet. Letztendlich sollte dies das neuronale Netzwerk optimieren, wenn es kompliziert genug ist.

Hier ist eine Demonstration, die ich gemacht habe, obwohl sie schlecht codiert ist, um Ihnen das Verständnis zu erleichtern. http://khrabanas.github.io/projects/evo/evo.html Drücken Sie den Entwicklungsknopf und spielen Sie mit den Zielen.

Es verwendet einen einfachen genetischen Algorithmus, um zu züchten, zu mutieren und zu entscheiden, welche Population überlebt. Abhängig davon, wie die Eingabevariablen eingestellt sind, kann das Netzwerk eine gewisse Nähe zu ihnen erreichen. Auf diese Weise wird die Population wahrscheinlich zu einer homogenen Gruppe, deren Ergebnisse den Zielen ähneln.

Der genetische Algorithmus versucht, eine Art "neuronales Netzwerk" zu erstellen, das durch die Aufnahme von RGB eine Ausgabefarbe liefert. Zunächst wird eine zufällige Population erzeugt. Anschließend werden 3 zufällige Mitglieder aus der Bevölkerung ausgewählt, dasjenige mit der geringsten Fitness ausgewählt und aus der Bevölkerung entfernt. Die Fitness entspricht der Differenz zwischen dem oberen und dem unteren Quadrat. Dann werden die beiden verbleibenden zusammen gezüchtet und das Kind wird an dieselbe Stelle in der Bevölkerung wie das tote Mitglied gesetzt. Bei einer Paarung besteht die Möglichkeit, dass eine Mutation auftritt. Diese Mutation ändert einen der Werte nach dem Zufallsprinzip.

Als Randnotiz ist es in vielen Fällen unmöglich, dass es aufgrund seiner Konfiguration völlig korrekt ist, obwohl es eine relative Nähe erreichen wird.

Hier gibt es eine Reihe guter Antworten, die erklären, was genetische Algorithmen sind, und Beispiele für Anwendungen geben. Ich füge einige allgemeine Ratschläge hinzu, wozu sie gut sind, aber auch Fälle, in denen Sie sie NICHT verwenden sollten. Wenn mein Ton scharf erscheint, liegt es daran, dass die Verwendung von GAs in einem der Fälle im Abschnitt Nicht geeignet dazu führt, dass Ihr Papier sofort aus einem hochrangigen Journal abgelehnt wird.

Erstens MUSS Ihr Problem ein Optimierungsproblem sein. Sie müssen eine "Fitnessfunktion" definieren, die Sie optimieren möchten, und Sie müssen eine Möglichkeit haben, sie zu messen.

Gut:

• Crossover-Funktionen sind einfach zu definieren und natürlich : Beim Umgang mit bestimmten Arten von Daten können Crossover- / Mutationsfunktionen einfach zu definieren sein. Beispielsweise können Strings (z. B. DNA- oder Gensequenzen) leicht mutiert werden, indem zwei Kandidaten-Strings gespleißt werden, um einen neuen zu erhalten (aus diesem Grund verwendet die Natur genetische Algorithmen!). Bäume (wie phylogenetische Bäume oder Parse-Bäume) können ebenfalls gespleißt werden, indem ein Ast eines Baumes durch einen Ast eines anderen ersetzt wird. Formen (wie Flugzeugflügel oder Bootsformen) können leicht mutiert werden, indem ein Raster auf die Form gezeichnet und verschiedene Rasterabschnitte von den Eltern kombiniert werden, um ein Kind zu erhalten. Normalerweise bedeutet dies, dass Ihr Problem aus verschiedenen Teilen besteht und das Zusammenfügen von Teilen aus unterschiedlichen Lösungen eine gültige Kandidatenlösung ist.
  • Dies bedeutet, dass GAs keine gute Wahl sind, wenn Ihr Problem in einem Vektorraum definiert ist, in dem die Koordinaten keine besondere Bedeutung haben. Wenn es schwierig ist, Ihr Problem als GA zu formulieren, lohnt es sich nicht.
• Black-Box-Bewertung : Wenn für einen Kandidaten Ihre Fitnessfunktion außerhalb des Computers bewertet wird, sind GAs eine gute Idee. Wenn Sie beispielsweise eine Flügelform in einem Lufttunnel testen, können Sie mithilfe genetischer Algorithmen gute Formen für den Versuch generieren.
  • Ausnahme: Simulationen . Wenn Ihre Fitnessfunktion misst, wie gut eine Düsenkonstruktion funktioniert, und die Fluiddynamik für jede Düsenform simuliert werden muss, funktionieren GAs möglicherweise gut für Sie. Sie können auch funktionieren, wenn Sie ein physikalisches System im Laufe der Zeit simulieren und sich dafür interessieren, wie gut Ihre Konstruktion im Laufe des Vorgangs abschneidet, z. Modellierung von Bewegungsmustern . In der Literatur werden jedoch Methoden entwickelt, die partielle Differentialgleichungen als Randbedingungen verwenden, z. PDE-beschränkte Optimierung , daher kann sich dies in Zukunft ändern.

Nicht angemessen:

• Sie können einen Gradienten für Ihre Funktion berechnen : Wenn Sie Zugriff auf den Gradienten Ihrer Funktion haben, können Sie einen Gradientenabstieg durchführen, der im Allgemeinen viel effizienter ist als GAs. Gradientenabstieg kann Probleme mit lokalen Minima haben (wie auch GAs), aber es wurden viele Methoden untersucht, um dies zu mildern.
• Sie kennen die Fitnessfunktion in geschlossener Form : Dann können Sie wahrscheinlich die Steigung berechnen. Viele Sprachen verfügen über Bibliotheken, die die automatische Unterscheidung unterstützen , sodass Sie diese nicht einmal manuell ausführen müssen. Wenn Ihre Funktion nicht differenzierbar ist, können Sie die Abstufung verwenden .
• Ihr Optimierungsproblem hat eine bekannte Form, z. B. ein lineares oder ein quadratisches Programm : GAs (und Black-Box-Optimierungsmethoden im Allgemeinen) sind in Bezug auf die Anzahl der zu bewertenden Kandidaten sehr ineffizient und sollten nach Möglichkeit vermieden werden.
• Ihr Lösungsraum ist klein : Wenn Sie Ihren Suchraum effizient gittern können, können Sie sicherstellen, dass Sie die beste Lösung gefunden haben, und Sie können Konturdiagramme des Lösungsraums erstellen, um festzustellen, ob es eine Region gibt, die Sie weiter untersuchen müssen.

Wenn Sie sich für eine GA entscheiden, sollten Sie sich auch mit neueren Arbeiten zu Evolutionsstrategien befassen. Ich bin voreingenommen in Richtung CMA-ES , was meiner Meinung nach ein guter einfacher Algorithmus ist, der die Vorstellung eines Gradienten in der Fitnesslandschaft auf eine Weise erfasst, die herkömmliche GAs nicht erfassen.

Wie in einer anderen Antwort erwähnt, müssen Sie lediglich eine mögliche Lösung für Ihr Problem in einer Form darstellen, die einem Übergang und einer Mutation unterliegt. Idealerweise liefert die Fitness-Funktion eine Art flüssiges Feedback über die Qualität einer Lösung, anstatt nur eine „Nadel im Heuhaufen“ zu sein.

Hier sind einige Merkmale von Problemen, für die genetische Algorithmen (und tatsächlich Metaheuristiken im Allgemeinen) gut sind:

• NP-vollständig - Die Anzahl der möglichen Lösungen für das Problem ist exponentiell, die Überprüfung der Eignung einer Lösung ist jedoch relativ kostengünstig (technisch gesehen mit Zeitpolynom in der Eingabegröße).
• Black Box - GAs funktionieren relativ gut, auch wenn Sie kein besonders fundiertes Modell für das zu lösende Problem haben. Dies bedeutet, dass diese Ansätze auch als Rapid-Prototyping-Ansatz zur Lösung von Problemen nützlich sind.

Beachten Sie jedoch, dass GAs trotz ihrer weit verbreiteten Verwendung für diesen Zweck eigentlich keine Funktionsoptimierer sind. GA-Mechanismen neigen nicht dazu, "abgelegene" Bereiche des Suchraums zu erkunden, in der Hoffnung, eine entfernte, qualitativ hochwertige Lösung zu finden, sondern sich eher zu Gruppen zusammenzuschließen leicht erreichbare Gipfel in der "Fitnesslandschaft".

Weitere Einzelheiten zur Anwendbarkeit von GAs enthält ein berühmter früher Aufsatz "Was macht ein Problem für einen genetischen Algorithmus schwierig?"