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 erzeugen (das sind wirklich nur Parameter), führen Sie sie gegen ein Problem und lassen Sie dann die Top-Performer überleben.

Sie dann mit einer Kombination aus Kreuzungen der Überlebenden, Mutationen der Überlebenden wieder zu bevölkern, und auch eine bestimmte Anzahl von neuen Zufall Organismen.

Do mehrere tausend Mal, und effiziente Organismen entstehen.

Manche Menschen tun auch mehrere „Inseln“ von Organismen, die sind getrennte Populationen, die erlaubt sind zu kreuzen einmal in eine Weile Dinge vorstellen.

Also, meine Frage ist: Was sind die optimalen Prozentsätze der Wiederbevölkerung?

Ich habe halten die oberen 10% Ausführende und mit 30% Kreuzungen und 30% Mutationen repopulating. Die restlichen 30% sind für neue Organismen bestimmt.

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

Es ist mir nicht entgangen, dass dies genau die Art von Problem ist, das ein EA lösen könnte. Ist dir bewusst, dass jemand das versucht?

Vielen Dank im Voraus!

Answer 1

Ich habe zunächst versucht zu modellieren, wie organische Systeme aussehen. Letztendlich entschieden, dass das nicht gut war, und ging aggressiver, mit 10% behalten, 20% mutiert, 60% Kreuzungen und 10% zufällig.

Dann bemerkte ich meine Top 10% waren alle ungefähr identisch. Also habe ich den Random auf 30% erhöht. Das half einigen, aber nicht viel.

Ich habe versucht, mehrere Insel und Generation-Skipping und Nachsaat, die bessere Ergebnisse ergab, aber immer noch sehr unbefriedigend, sehr wenig Variation in den Top 10%, verrückten langen Generationen, um irgendwelche Ergebnisse zu erhalten. Meistens hat der Code gelernt, wie man meine Fitnessbewertung hackt.

Es ist wirklich einfach, Top-Performer zu bekommen, also mach dir keine Sorgen darüber, zu viele von ihnen herumzuhalten. 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 Behalte einfach das Beste im Auge und verfeinere sie langsamer. IE: Sachen, die auf der letzten Generation basieren, finden nur ein besseres lokales Maximum, Randoms finden bessere globale Maxima.

Ich glaube immer noch, dass optimale Antworten auf Ihre Frage gefunden werden können, indem Sie natürliche Phänomene beobachten, wie in einem kürzlich erschienenen Artikel über die Zufälligkeit von Fruchtfliegen-Flugpfaden, damit sich herausstellen kann.

Wahrscheinlich ist die beste Antwort, um es auszuführen einfach und es zu zwicken, keine Angst, es ist ziemlich schwer zu zwicken, die Populationen robust sind. Stellen Sie sicher, dass Sie eine Möglichkeit zum Speichern und Fortfahren implementieren.

Answer 2

Sie wissen, was Sie tun könnten ... Sie könnten einen genetischen Algorithmus schreiben, um diese optimale Verteilung zu bestimmen.

Aber normalerweise halte ich die oberen 12% und 28% Kreuzungen; mit jeweils 30% für die anderen.

Answer 3

Die besten Ressourcen, die ich über für GA gekommen sind und EA waren Bücher John Koza die auf Genetic Programming. Er behandelt das Thema ausführlich - Techniken für die Codierung des Genoms, zufällige Mutation, Zucht, Tuning der Fitness-Funktion.

Ich persönlich habe nur eine kleine Handvoll Simulatoren für pädagogische Zwecke geschrieben. Was ich fand, war, dass, wie ich diese Prozentsätze abstimmte, mit den Details der Eignungfunktion zusammenhing, die ich verwendete, wie viel zufällige Mutation ich eingeführt hatte und wie 'klug' ich versucht hatte, die Mutation und die Zucht zu machen - fand ich das weniger Ich versuchte, den Mutator und die Crossover-Logik zu machen, je schneller die Bevölkerung ihren Fitness-Score verbesserte - ich fand auch, dass ich in der Wahrscheinlichkeit einer Mutation zu konservativ gewesen war - meine anfänglichen Läufe trafen lokale Maxima und hatten eine harte Zeit, aus ihnen herauszukommen.

Nichts davon gibt Ihnen konkrete Antworten, aber ich glaube nicht, dass es konkrete Antworten gibt, GA ist von Natur aus unberechenbar und das Einstellen dieser Art von Parametern kann immer noch ein bisschen eine Kunst sein. Natürlich könntest du immer eine Meta-GA versuchen, indem du diese Parameter als ein Chromosom verwendest und nach Einstellungen suchst, die eine schnellere Fitness in der Basis-GA, die du betreibst, hervorbringst.

Hängt davon ab, wie 'Meta' Sie bekommen möchten.

Answer 4

Dies ist ein heiß diskutiertes (in der Literatur und Melanie, et al books) Thema, das sehr domänenspezifisch zu sein scheint. Was für ein Problem eines Typs mit n Parametern funktioniert, funktioniert fast nie für ein anderes Problem, eine andere Domäne oder eine andere parametrische Menge.

Also, wie TraumaPony vorgeschlagen, zwicken Sie es selbst für jedes Problem, das Sie lösen oder schreiben Sie etwas, um es für Sie zu optimieren. Das Beste, was Sie tun können, ist, all Ihre "Knob-Twiddling" - und Feinabstimmungsexperimente im Auge zu behalten, um das Lösungs-Terrain abzubilden und ein Gefühl dafür zu bekommen, wie Sie in diesem Bereich schnell optimieren können. Versuchen Sie auch alternative Techniken wie Hill-Climbing, so dass Sie eine Grundlinie zu schlagen haben.

@Kyle Burton: Crossover vs Mutationsraten sind auch constantly debated in jeder Klasse von Problemen an GAs und GPs übergeben.

Answer 5

Angenommen, Sie haben eine Methode zur Quantifizierung der besten X% percent-Performer, würde ich vorschlagen, anstelle einer hart codierten Schwelle analysieren Sie die Leistungsverteilung und machen Sie Ihren Cutoff irgendwo im Bereich der ersten großen Leistungsabfall und dann stimmen Sie Ihre Kreuzungen, Mutationen und neuen Organismen ab, um die Lücken zu füllen. Auf diese Weise, wenn Sie einen sehr "produktiven" Lauf haben, in dem viele Variationen erfolgreich waren, werfen Sie nicht eine signifikante Anzahl von Leistungsträgern. Auch wenn Sie einen "unproduktiven" Lauf haben, können Sie mehr der bestehenden Organismen zugunsten von neueren Organismen, die an ihre Stelle treten sollten, verwerfen.

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 zweite zu bestimmen. Ich kann mir nicht helfen, aber wundere mich über die religiösen Überzeugungen derjenigen, die diesen Ansatz vorschlagen ...

Answer 7

Ich hatte einige Erfolge, die die Vielfalt der Bevölkerung durch Mutation und Crossover von ein paar der Gene von den Elternchromosomen erhöhen.

Dies funktioniert, bis die Mutationsrate auf Null fällt; Da es wahrscheinlich ist, dass es einen periodischen evolutionären Druck dafür geben wird, sollten Sie versuchen, sicherzustellen, dass diese Gene eine minimale Rate haben.

In der Praxis entschied ich mich für einen Multi-Chromosom-Genotyp. Ein Chromosom kodiert für die Fortpflanzungsfunktion des anderen.Das kleinere "Reproduktionschromosom" hatte eine vernünftige feste Rate für Mutation und Crossover.

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

Nebenbei tendiere ich dazu, Crossover und Mutation für jedes Kind zu tun.

Für Generations-GAs versuche ich den Elitismus gänzlich zu meiden, aber wo ich von mehreren Inseln aus bevölkert bin, behalte ich die Spitzenelite von jeder Insel. Wenn die Inseln zusammenkommen, können die Eliten alle zusammen züchten.

Answer 8

Wie andere bereits erwähnt haben, hängt die optimale Mischung von Ihrem spezifischen Problem und anderen problemspezifischen Faktoren wie der Größe des Lösungsraums ab.

Bevor wir die Evolution von einer Generation zur nächsten diskutieren, ist es wichtig, die Größe jeder Generation zu berücksichtigen. Generell ist mein Ansatz, mit einer ziemlich großen Population (~ 100k-500k Individuen) von ziemlich verschiedenen Individuen zu beginnen, was Koza in einigen seiner Arbeiten vorschlägt. Um diese Vielfalt von Anfang an zu erhalten, können Sie Ihren Lösungsraum in Eimer aufteilen und dann sicherstellen, dass mindestens eine bestimmte Anzahl von Personen in jeden Eimer fällt. (ZB wenn Sie eine Baumdarstellung für jedes Individuum haben, stellen Sie sicher, dass gleiche Beträge von Tiefe 2, 3, ..., max_depth erzeugt werden)

Soweit Ihre eigentliche Frage, es gibt keine klare Möglichkeit, es zu nähern, aber Abhängig von Ihrem Problem möchten Sie vielleicht die Zufälligkeit betonen oder sie abschwächen. Wenn Sie es betonen möchten, sollten Sie weniger Individuen intakt halten und eine höhere Anzahl neuer zufälliger Individuen einführen. In der Regel möchten Sie dies, wenn in Ihrem Lösungsbereich viele lokale Höchstwerte vorhanden sind und Sie eine breitere Suche durchführen möchten.

Wenn Sie einen Durchbruch erhalten, gibt es ein paar Dinge zu beachten ... für einen, Duplikation (viele identische oder neu identische Individuen an der Spitze der Inzucht). Um dies zu reduzieren, möchten Sie möglicherweise Ihre Population zwischen den Generationen durchsuchen und Duplikate durch neue zufällige oder gekreuzte Individuen ersetzen.

Das heißt, mein aktueller Ansatz ist es, die Top 1% zu halten, die Top 20% in neue 20% zu kreuzen, die Top 40% in die nächsten 20% zu kreuzen, die Top 90% zu kreuzen um die nächsten 20 zu generieren %, und erzeugen zufällig den Rest (39%). Wenn es Dubletten gibt, entferne ich sie und ersetze sie durch neue zufällige Individuen.

Ich verwende keine Mutationen, da die hohe Anzahl von zufälligen Personen darauf achten sollte, während der folgenden Kreuzung "Mutationen" hinzuzufügen.