Woher wissen wir, dass die nächste Generation besser sein wird?

32

Ich wurde kürzlich durch diesen MSDN-Artikel mit genetischen Algorithmen bekannt gemacht , in dem er sie als kombinatorische Evolution bezeichnet, aber es scheint dasselbe zu sein, und ich habe Mühe zu verstehen, wie die Kombination zweier möglicher Lösungen immer eine neue Lösung ergibt, die mindestens genauso ist gut wie seine Eltern.

Warum ist das so? Sicherlich könnte das Kombinieren etwas Schlimmeres hervorbringen.

Soweit ich es verstehe, basiert der Algorithmus auf dem Konzept, dass, wenn ein Männchen und ein Weibchen einer Art Nachkommen zeugen, diese Nachkommen Merkmale beider Eltern haben. Manche Kombinationen sind besser, manche schlechter und manche genauso gut. Diejenigen, die besser sind (für was auch immer die Definition von "besser" angemessen ist), haben mehr Chancen zu überleben und Offpsring zu produzieren, der die verbesserten Eigenschaften aufweist. Es wird jedoch Kombinationen geben, die schwächer sind. Warum ist das kein Problem mit GA?

Avrohom Yisroel
quelle
12
However, there will be combinations that are weaker. Why isn't this an issue with GA?- Weil die schwächeren Kombinationen verworfen werden.
Robert Harvey
6
Wir wissen, dass die nächste Generation nicht schlechter wird, weil wir die Guten nicht wegwerfen, aber wir werfen die Schlechten weg. Und es gibt eine vernünftige Chance, dass die Kombination einiger der Guten eine noch bessere ergibt, aber es ist nicht garantiert.
user253751
7
Why isn't this an issue with GA?Nun, es ist oder genauer, es könnte sein. Einer der vielen (vielen) Parameter zur Optimierung mit GAs ist die Populationsgröße: Wenn sie zu niedrig ist, können Sie möglicherweise nur schwächere Individuen produzieren. Wenn sie zu hoch ist, ist die mit der Fitnessfunktion verbundene Rechenzeit möglicherweise zu hoch.
Loufylouf
3
Es ist ein Unterschied zwischen Zucht und Unkraut : Die Zuchtphase kann (wird) schlechtere Nachkommen hervorbringen, aber die Unkrautphase wird (sollte) die schlechteste Leistung vor der nächsten Zuchtphase beseitigen.
TripeHound
Danke euch allen. Wenn ich das richtig verstehe, war es die Art und Weise, wie er es in dem Artikel formuliert hat, die mich von der Spur geworfen hat. Er sagte: " Der neue, vermutlich sehr gute Kinderorganismus ersetzt einen armen Organismus ", was meine Frage aufwirkte. Scheint, dass das falsch war :)
Avrohom Yisroel

Antworten:

43

Ein genetischer Algorithmus versucht, sich bei jeder Generation zu verbessern, indem er die Population aussortiert. Jedes Mitglied wird nach einer Fitnessfunktion bewertet, und nur ein Teil von ihnen mit hoher Punktzahl darf sich fortpflanzen.

Sie haben jedoch Recht: Es gibt keine Garantie dafür, dass sich die nächste Generation im Vergleich zum Vorgänger verbessern wird.

Betrachten Sie Dawkins 'Wieselprogramm : "Entwickeln" Sie die Saite "Methinks it is like a weasel". Ausgehend von einer Population zufälliger Zeichenfolgen wertet die Fitnessfunktion die engste Textübereinstimmung aus, die gestört wird, um die nächste Generation zu erzeugen. Mit einer einfachen Crossover-Reproduktion könnten zwei Saiten mit hoher Punktzahl, die kombiniert werden, sehr leicht Nachkommen mit niedriger Punktzahl hervorbringen. Selbst "asexuelle" zufällige Mutationen einer einzelnen High-Fitness-Saite können die Fitness des Kindes beeinträchtigen.

Es ist erwähnenswert, dass dies nicht unbedingt ein Fehler ist. Bei dieser Art der Suche gibt es die Idee der lokalen Maxima . Ein Mitglied der Bevölkerung könnte eine Lösung darstellen, die nicht das optimale Ergebnis ist, sondern die beste, die erreicht werden kann, ohne sich auf dem Weg zu verschlechtern.

Stellen Sie sich vor, dass die Fitnessfunktion für das Wieselprogramm nicht nur die Bearbeitungsentfernung ermittelt, sondern auch eine Vorstellung von "Wort" hat und testet, ob das letzte Wort der Zeichenfolge der Name eines Tieres ist. Jeder Tiername punktet gut, "weasel"bekommt aber einen großen Bonus.

Was passiert nun, wenn "Methinks it is like a walrus"sich weiterentwickelt? Es punktet gut. Nicht so gut wie die ultimative Zielkette, aber besser als "Methinks it is like a walrut"oder andere enge Variationen, die durch einen einzigen Mutationsschritt erreicht werden könnten.

Die Walross-Zeichenfolge ist ein lokales Maximum, und die Suche kann dort hängen bleiben, sofern das Programm nicht zulässt, dass die Punktzahl der nächsten Generation schlechter wird.

Josh Caswell
quelle
1
Relevant: youtube.com/watch?v=YT1vXXMsYak - die Demonstration von Dawkins Computerprogramm dauert ungefähr 12 Minuten, obwohl die gesamte Vorlesung einen Besuch wert ist, da sie die theoretischen Grundlagen beschreibt, auf denen die Evolution (ob biologisch oder simuliert) beruht geerdet.
Periata Breatta
24
In der Tat lassen Sie manchmal einen bestimmten Prozentsatz schwächerer Mitglieder überleben, um die "genetische Vielfalt" zu erhöhen, und führen völlig zufällige Mutationen ein, die überhaupt nicht auf einem vorhandenen Mitglied basieren.
Jörg W Mittag
@JoshCaswell Danke dafür. Obwohl alle Antworten ausgezeichnet waren, werde ich dies als die akzeptierte markieren, da es alles abdeckt, was ich gefragt habe, und ein paar Dinge, die ich noch nicht gefragt hatte!
Avrohom Yisroel
Froh, dass ich helfen konnte, @AvrohomYisroel
Josh Caswell
6

Wir wissen nicht, dass es besser wird, wir wissen, dass es nicht schlimmer wird.

Besteht in jeder Generation nicht nur aus dem Ursprung der besten Elemente, sondern umfasst auch die besten Elemente selbst - wenn Sie so wollen, Klone. Da sie noch anwesend sind, erzielen sie die gleichen Ergebnisse wie zuvor. Das heißt, wenn keiner der Nachkommen besser ist, gewinnen die Gewinner der vorherigen Generation erneut - und werden re-mutiert / gezüchtet.

Bedenken Sie: Wenn ein Stammvater ein Buchstabe ist, z. B. A ein mutiertes Kind definiert wird, indem eine Zahl hinzugefügt wird, z. A1B. (A1B2) Kreuzbrotlösungen mit Klammern um den Elternteil geschrieben werden[12]

Zur Demonstration betrachten wir einen Pool von 5, in dem wir den 2. besten behalten und mit jeweils 1 Mutanten plus einer Kreuzung füllen

Generation 1

  • A [10]
  • B [5]
  • C [4]
  • D [3]
  • E [1]

Behalten Sie A, Bwie sie die besten zwei sind, und füllen Sie andere 3 Steckplätze mit ihren Nachkommen auf

Generation 2

  • A [10]
  • B [5]
  • (AB) [7]
  • A1 [12]
  • B1 [4]

Halten Sie Aund (AB), da sie die besten 2 sind - Dies bedeutet, dass Opa Aimmer noch im Pool ist, da die meisten Kinder schwächer arbeiten

Generation 3

  • A [10]
  • (AB) [12]
  • (A(AB)) [14]
  • A2 [8]
  • (AB)1 [13]

Halten (AB)1und (A(AB))- diesmal wurden keine Großeltern unterhalten, als zwei ihrer Kinder sie schlugen. Aber wenn (AB1)es nur ein bisschen schlechter gelaufen wäre, hätten wir es (AB)stattdessen gehalten .

Dies wird fortgesetzt, bis sich die Punktzahl stabilisiert hat. Was darauf hinweist, dass Sie eine Art lokales Maxima (möglicherweise ein globales Maxima) erreicht haben. Ein Grund, dies zu erkennen, wäre, wenn dieselben Individuen weiterhin in die nächste Generation "geklont" werden. (obwohl für hochdimensionale Probleme, die zu lange dauern könnten, besser, nur die Verbesserung <eine bestimmte Toleranz zu überprüfen)

Lyndon White
quelle
1
"Besteht in jeder Generation nicht nur aus der Entstehung der besten Elemente, sondern beinhaltet auch die besten Elemente selbst." Dies hängt von der Implementierung ab. Einige Implementierungen tun dies nicht. Dies wird manchmal als "Elitismus" bezeichnet.
jpmc26
4

Im Allgemeinen funktionieren genetische Algorithmen, indem sie eine Reihe von (zufälligen) Variationen bei den Eltern in jeder Generation erzeugen. Dann wird eine Auswahlfunktion angewendet, und der Nachwuchs, der gemäß dieser Funktion am besten geeignet ist, überlebt. Der Nachwuchs ist also nicht unbedingt besser, da die Variation zufällig ist, aber in Kombination mit der Selektion erhalten Sie eine Verbesserung im Laufe der Zeit.

JacquesB
quelle
4
Ah, so wie es klingt, war der Artikel ein wenig irreführend. Er sagte: " Der neue, vermutlich sehr gute Kinderorganismus ersetzt einen armen Organismus ", was mich verwirrte. Ich denke, wenn er eine Menge Organismen kombiniert, dann würden wir insgesamt einen Anstieg erwarten, auch wenn einzelne neue Organismen schwächer sein könnten als frühere. Ist das richtig? Vielen Dank
Avrohom Yisroel
@ AvrohomYisroel: Genau.
JacquesB
1
@AvrohomYisroel: Achten Sie auf das ungefähre Verständnis von Nichtfachleuten. (Achten Sie auch auf die Präzision der Fachsprache.)
Eric Towers
@EricTowers Ja, ich sehe das Problem! Ich dachte, er sei ein Experte, nach früheren Artikeln zu urteilen, die er geschrieben hat, aber er scheint in diesem Artikel einige große Fehler gemacht zu haben.
Avrohom Yisroel
4

Als ich am College genetische Algorithmen studierte, wurde das folgendermaßen erklärt:

Stellen Sie sich vor, eine Lösung besteht aus einer Kombination von "Genen", wobei jedes Gen beeinflusst, wie gut die Lösung insgesamt ist. Wenn zwei Lösungen gepaart sind, werden sie zufällig von jedem Elternteil ausgewählt.

Wenn nun ein Gen im Allgemeinen zu einer guten Lösung führt, nimmt seine Häufigkeit im Genpool zu. Im Extremfall wird das Gen die Bevölkerung dominieren.

Wenn Sie also an genetische Algorithmen (und die Evolution im Allgemeinen) denken, sollten Sie nicht an Individuen denken. Sie sollten über Gene und Populationen als Ganzes nachdenken. Selbst wenn eine "beste" Lösung verloren geht, bedeutet dies nicht, dass die Gene verloren gehen.

Es gibt auch eine Idee von Elitismus in genetischen Algorithmen. Dies bedeutet, dass die beste (n) Lösung (en) immer über Generationen hinweg beibehalten wird (werden). Dies kann die Konvergenz des Algorithmus beschleunigen, es ist jedoch für den Algorithmus einfacher, in lokalen Optima zu stecken.

Euphorisch
quelle
2

GA-Algorithmen sind nicht deterministisch, sie garantieren keine Verbesserung in jeder Generation und sie garantieren auch nicht, ein Gesamtoptimum zu finden. Durch die Auswahlphase eines GA mit einer Fitnessfunktion ist es jedoch wahrscheinlicher, dass "gute Lösungen" überleben.

Doc Brown
quelle