Evolutionäre Algorithmen: Optimal Repopulation Aufschlüsselungen

Question

Es ist wirklich alles im Titel, aber hier ist eine Aufschlüsselung für jeden, der in Evolutionäre Algorithmen interessiert ist:

In einem EA, ist die grundlegende Prämisse, dass Sie zufällig eine bestimmte Anzahl von Organismen zu erzeugen (die sind wirklich nur Parametersätze), um sie vor einem Problem führen, und lassen Sie dann den Top-Performer zu überleben.

Sie dann mit einer Kombination aus Kreuzungen der Überlebenden, Mutationen der Überlebenden, und auch eine bestimmte Anzahl von neuen Zufall Organismen besiedeln.

Sie, dass mehrere tausend Mal und effiziente Organismen entstehen.

Einige Leute auch Dinge tun, wie einführen mehrere „Inseln“ von Organismen, die getrennten Populationen sind, die einmal erlaubt sind in einer Weile zu kreuzen.

Also, meine Frage ist: Was ist die optimale Neubesiedlung Prozentsatz sind

?

Ich habe die besten 10% Darsteller worden zu halten, und mit 30% Kreuzungen und 30% Mutationen repopulating. Die restlichen 30% ist für neue Organismen.

Ich habe auch die mehrere Insel Theorie ausprobiert, und ich bin in den Ergebnissen auf, dass auch interessiert.

Es ist nicht an mir verloren, dass dies genau die Art von Problem eines EA lösen könnte. Sind Sie sich bewusst von jemand versucht das?

Vielen Dank im Voraus!

Answer 1

Ich versuchte zunächst zu modellieren, was ich dachte, organische Systeme waren wie. Letztlich entschieden, dass war nicht gut, und ging aggressiver, mit 10% gehalten, 20% mutiert, 60% crossbred und 10% zufällig.

Dann bemerkte ich meine Top 10% aller in etwa identisch waren. So stieg ich die zufällig auf 30%. Das half einige, aber nicht viel.

habe ich mehrere Insel versuchen, und Generation-Skipping, und Nachsaat, die bessere Ergebnisse gab, aber immer noch höchst unbefriedigend, nur sehr geringe Unterschiede in den oberen 10%, verrückt langen Zahlen von Generationen keine Ergebnisse zu erhalten. Meistens sind die Code gelernt, wie meine Fitness Auswertung hacken.

Es ist wirklich einfach Top-Performer zu bekommen, also keine Sorge zu viele von ihnen um zu halten. Kreuzungen helfen positive und negative Eigenschaften abspecken, so sind sie nützlich, aber wirklich, was wollen Sie eine Menge guter zufällig zu erhalten ist, gezüchtet in. Auf Mutationen im Fokus und neue randoms in Funktionen zu bringen, und lassen Sie die Kreuzungen und Top-Performer halten nur den Überblick über die besten und verfeinern sie langsamer. IE: Sachen auf der letzten Generation basiert nur eine bessere lokale Maxima zu finden, randoms finden bessere globale Maxima

.

Ich glaube immer noch optimale Antworten auf Ihre Frage kann durch die Beobachtung natürliche Phänomene, wie in einem kürzlich erschienenen Artikel über Zufälligkeit der Fruchtfliegenflugrouten gefunden werden, so dass aus pan kann.

Wahrscheinlich die beste Antwort ist, es einfach zu laufen und es zu zwicken, keine Angst, es zu zwicken ziemlich stark, die Populationen sind robust. Stellen Sie sicher, dass Sie einen Weg implementieren zu speichern und fortzufahren.

Answer 2

Die besten Ressourcen, die ich begegnet bin für GA und EA John Koza Bücher über rel="noreferrer"> . Er deckt das Thema in der Tiefe -. Techniken zur Codierung des Genoms, zufällige Mutation, Züchtung, Abstimmen der Fitness-Funktion

Persönlich habe ich nur eine kleine Handvoll von Simulatoren für pädagogische Zwecke geschrieben. Was ich fand, war, dass, wie ich diese Prozentsatz abgestimmt wurden die Angaben der Fitness-Funktion im Zusammenhang war ich mit, wie viel zufällige Mutation ich eingeführt hatte und wie ‚intelligente‘ Ich hatte versucht, die Mutation und Zucht zu machen - ich fand, dass die weniger ‚smart‘ ich versuchte, den Mutator und die Cross-over-Logik zu machen, schneller die die Bevölkerung ihres Fitness-Score verbessert - fand ich auch, dass ich in der Wahrscheinlichkeit der Mutation zu konservativ gewesen - meine ersten Läufen treffen lokale Maxima und hatte eine harte Zeit aus ihnen heraus zu bekommen.

Nichts von alldem gibt Ihnen konkrete Antworten, aber ich glaube nicht, es gibt konkrete Antworten, GA von Natur aus unberechenbar ist und diese Arten von Parametern Tuning noch ein bisschen einer Kunst sein kann. Natürlich könnte man immer einen Meta-GA versuchen, diese Parameter als Chromosom unter Verwendung von Einstellungen zu suchen, die eine schnellere Fitness in der Basis produzieren GA Sie ausführen.

Abhängig von wie 'Meta' Sie wollen bekommen.

Answer 3

Dies ist ein heiß diskutiertes (in der Literatur und Melanie, et al Bücher ) Thema, das sehr domänenspezifisch zu sein scheint. Was für ein Problem eines Typs arbeitet mit n-Parametern wird so gut wie nie für ein anderes Problem umgehen, eine andere Domäne oder einen anderen Parametersatz.

So, wie Traumapony vorgeschlagen, zwicken sie sich für jedes Problem, das Sie lösen oder etwas schreiben es für Sie zu optimieren. Das Beste, was Sie tun können, ist, den Überblick behalten alle Ihre „Knopf-Fummeln“ und Feinabstimmung Experimente, so dass Sie die Lösung Gelände kartieren und ein Gefühl dafür bekommen, wie schnell in diesem Raum zu optimieren. Versuchen Sie auch alternative Techniken wie Bergauffahrt, so dass Sie eine Basis haben zu schlagen.

@ Kyle Burton: Crossover vs. Mutationsraten sind auch ständig in jeder Klasse diskutiert von Problemen zu GAs und GPs übergeben.

Answer 4

Angenommen, Sie haben ein Verfahren für die besten X% Prozent Darsteller zu quantifizieren, würde ich vorschlagen, dass stattdessen eine hartcodierte Schwelle verwenden Sie die Performance Verteilung analysieren und Ihre Cutoff irgendwo in der Leistung im Bereich des ersten großen Tropfen machen, und dann Tuning Ihre crossbreads, Mutationen und neue Organismen in den Lücken zu füllen. Auf diese Weise, wenn Sie haben ein sehr „produktiv“ laufen, in denen viele Variationen erfolgreich waren Sie keine signifikante Anzahl von Leistungsträgern werfen. Auch, wenn Sie eine „unproduktive“ haben Sie laufen mehrere der vorhandenen Organismen zu Gunsten von mehr neueren Organismen Schrott kann, die ihren Platz einnehmen soll.

Answer 5

Ich habe einige Erfolge Erhöhung der Vielfalt der Bevölkerung hatte durch Mutation und Crossover von ein paar der Gene von den Elternchromosomen zu setzen.

Das funktioniert, bis die Mutationsrate auf Null sinkt; da es wahrscheinlich ist, dass es ein periodischer evolutionärer Druck, dies zu tun, sollten Sie versuchen und sicherstellen, dass diese Gene eine Mindestrate haben.

In der Praxis entschied ich mich für einen Multi-Chromosom-Genotyp. Ein Chromosom kodiert für die reproduktive Funktion des anderen. Je kleine ‚Wiedergabe Chromosom‘ hatte einen vernünftigen festen Preise für die Mutation und Crossover.

Ich fand, dass dies das klassische Plateau und Konvergenz der Bevölkerung stoppen würde.

Als Nebenwirkung, neige ich dazu, für jedes Kind sowohl Crossover und Mutation zu tun.

Für Generationen GAs, ich versuche Elitismus ganz zu meiden, wo aber aus mehreren Inseln bevölkern, halte ich die Top-Elite von jeder Insel. Wenn die Inseln zusammenkommen, dann können die Eliten alle zusammen züchten.

Answer 6

Es scheint ein paar Antworten zu sein was auf eine zweite GA mit optimalen Parameter für den 1. GA, um zu bestimmen, ohne erwähnt, wie die optimalen Parameter für die 2. zu bestimmen. Ich kann nicht helfen, aber frage mich, über die religiösen Überzeugungen von denen dieser Ansatz darauf hindeutet, ...

Answer 7

Wie andere erwähnt haben, die optimale Mischung auf Ihrem spezifisches Problem und anderen problemspezifische Faktoren wie die Größe des Lösungsraumes abhängen würde.

Bevor wir die Entwicklung Zusammenbruch von einer Generation auf die nächste zu diskutieren, ist es wichtig, die Größe jeder Generation zu berücksichtigen. Im Allgemeinen mein Ansatz ist mit einer ziemlich großen Bevölkerung (~ 100k-500k Personen) von ziemlich unterschiedlichen Personen zu beginnen, das ist etwas, das Koza in einigen seiner Arbeit vermuten lässt. Zum Erhalt diese Vielfalt von Anfang an, könnten Sie Ihren Lösungsraum in Eimer aufzuteilen, und dann sicherzustellen, dass zumindest eine gewisse Anzahl von Individuen in jeden Eimer fällt. (Z.B., wenn Sie eine Baumdarstellung für jeden einzelnen haben, stellen Sie sicher, dass gleiche Mengen an Tiefe erstellt werden 2, 3, ..., max_depth)

Was Ihre eigentliche Frage, gibt es keinen klaren Weg, es zu nähern, aber abhängig von Ihrem Problem, sollten Sie Zufälligkeit betonen oder de-betonen sie. Wenn Sie es betonen wollen, sollten Sie weniger indivuduals intakt halten, und die Einführung eine höhere Anzahl von neuen Zufall Individuen. Sie möchten dies in der Regel tun, wenn es viele lokalen Maxima in Ihrem Lösungsraum sind, und Sie wollen eine breitere Suche haben.

Wenn Sie eine Pause bekommen dort unten ein paar Dinge ... zu prüfen, das eine, Vervielfältigung (viele identische oder neu identischen Individuen an der Spitze Inzucht). Um dies zu verringern, die Sie zwischen den Generationen durch Ihre Bevölkerung fegen und ersetzen Vervielfältigungen mit neuem Zufall Einzelpersonen oder crossbred diejenigen mögen.

Wie gesagt, mein aktueller Ansatz ist es, das Top-1% zu halten, kreuzt das obere 20% in ein neues 20%, kreuzt die Top 40% in das nächsten 20%, kreuzen Sie das Top-90% das nächste 20% zu erzeugen und zufällig den Rest (39%) erzeugen. Wenn es Duplikate sind, ich sie entfernen und ersetzen sie durch neue zufällige Einzelpersonen.

Ich benutze Mutationen nicht, da die hohe Anzahl von zufälligen Individuen Pflege der Zugabe in „Mutationen“ während der folgenden Kreuzung nehmen soll.

Answer 8

Sie wissen, was Sie tun können ... Sie einen genetischen Algorithmus schreiben könnte, dass eine optimale Verteilung zu bestimmen.

Aber normalerweise halte ich das Top-12% und 28% Mischlingen; jeweils für die andere mit 30%.