Warum haben Personen mit geringer Fitness eine Chance, bis zur nächsten Generation zu überleben?

Ich lese und beobachte gerade genetische Algorithmen und finde sie sehr interessant (ich hatte während meines Studiums keine Gelegenheit, sie zu studieren).

Ich verstehe, dass Mutationen auf Wahrscheinlichkeit basieren (Zufälligkeit ist die Wurzel der Evolution), aber ich verstehe nicht, warum das Überleben so ist.

Von dem, was ich verstehe, ein Individuum Fitness mit wie für eine andere Person Fitness mit haben wir , dann eine bessere Wahrscheinlichkeit als , um zu überleben zur nächsten Generation.F ( i ) J F ( j ) F ( i ) > F ( j ) I $I$$F(i)$$J$$F(j)$$F(i) > F(j)$$I$$J$

Wahrscheinlichkeit bedeutet , dass kann überleben und kann nicht (mit „Pech“). Ich verstehe nicht, warum das überhaupt gut ist? Wenn die Auswahl immer überleben würde , was würde im Algorithmus schief gehen? Ich vermute, dass der Algorithmus einem gierigen Algorithmus ähnelt, bin mir aber nicht sicher.$J$ $I$ $I$

Die Hauptidee ist, dass Sie durch Überlebenlassen suboptimaler Individuen durch eine Abfolge kleiner inkrementeller Mutationen von einem "Höhepunkt" in der Evolutionslandschaft zu einem anderen wechseln können. Wenn Sie jedoch nur bergauf gehen dürfen, ist eine gigantische und äußerst unwahrscheinliche Mutation erforderlich, um die Spitzen zu wechseln.

Hier ist ein Diagramm, das den Unterschied zeigt:

Praktisch ist diese Globalisierungseigenschaft der Hauptverkaufspunkt evolutionärer Algorithmen - wenn Sie nur ein lokales Maximum finden möchten, gibt es effizientere Spezialtechniken. (zB L-BFGS mit endlichem Differenzgradienten und Liniensuche)

In der realen Welt der biologischen Evolution schafft das Überleben suboptimaler Individuen Robustheit, wenn sich die Evolutionslandschaft ändert. Wenn sich alle auf einen Gipfel konzentrieren, stirbt die gesamte Bevölkerung, wenn dieser Gipfel zu einem Tal wird (z. B. waren Dinosaurier die am besten geeigneten Arten, bis ein Asteroidenschlag stattfand und sich die Entwicklungslandschaft veränderte). Auf der anderen Seite, wenn es eine gewisse Vielfalt in der Bevölkerung gibt, werden einige überleben, wenn sich die Landschaft ändert.

Die Antwort von Nick Alger ist sehr gut, aber ich werde sie mit einer Beispielmethode, der Metropolis-Hastings-Methode, etwas mathematischer gestalten.

Das Szenario, das ich untersuchen werde, ist, dass Sie eine Bevölkerung von einem haben. Sie schlagen eine Mutation vom Zustand zum Zustand mit der Wahrscheinlichkeit , und wir unterstellen auch die Bedingung, dass . Wir werden auch annehmen, dass für alle ; Wenn Ihr Modell keine Fitness aufweist, können Sie dies beheben, indem Sie überall ein kleines Epsilon hinzufügen.j Q ( i , j ) Q ( i , j ) = Q ( j , i ) F ( i ) > 0 $i$$j$$Q(i,j)$$Q(i,j) = Q(j,i)$$F(i)>0$$i$

Wir akzeptieren einen Übergang von nach mit der Wahrscheinlichkeit:$i$$j$

Mit anderen Worten, wenn mehr passt, nehmen wir es immer, aber wenn weniger passt, nehmen wir es mit der Wahrscheinlichkeit , andernfalls versuchen wir es erneut, bis wir a akzeptieren Mutation.$j$$j$$\frac{F(j)}{F(i)}$

Nun wollen wir , die tatsächliche Wahrscheinlichkeit, mit der wir von nach übergehen .$P(i,j)$$i$$j$

Klar ist es:

Nehmen wir an, dass . Dann = 1 und so:$F(j) \ge F(i)$$\min\left(1, \frac{F(j)}{F(i)}\right)$

Wenn Sie das Argument rückwärts ausführen und auch den trivialen Fall mit , können Sie Folgendes für alle und :$i=j$$i$$j$

Dies ist aus einigen Gründen bemerkenswert.

Die Übergangswahrscheinlichkeit ist unabhängig von . Natürlich kann es eine Weile dauern, bis wir im Attraktor landen, und es kann eine Weile dauern, bis wir eine Mutation akzeptieren. Sobald wir dies tun, ist die Übergangswahrscheinlichkeit vollständig von und nicht von abhängig .$Q$$F$$Q$

Zusammenfassend gebe :$i$

Es ist klar, dass auf summieren muss, wenn Sie über alles summieren (dh, die Übergangswahrscheinlichkeiten aus einem Zustand müssen auf summieren ), sodass Sie Folgendes erhalten:$P(j,i)$$1$$i$$1$

Das heißt, ist die (nicht normalisierte) Wahrscheinlichkeitsdichtefunktion, für die die Methode Zustände auswählt. Sie werden nicht nur garantiert die ganze Landschaft erkunden, Sie tun dies auch proportional dazu, wie "fit" jeder Staat ist.$F$

Dies ist natürlich nur ein Beispiel von vielen. Wie ich weiter unten bemerkte, handelt es sich um eine Methode, die sehr einfach zu erklären ist. In der Regel verwenden Sie eine GA nicht, um ein PDF zu durchsuchen, sondern um ein Extrem zu finden. In diesem Fall können Sie einige Bedingungen lockern und dennoch mit hoher Wahrscheinlichkeit eine eventuelle Konvergenz gewährleisten.

Der Vorteil einer GA besteht darin, dass Sie breitere Suchbereiche erkunden können, indem Sie Pfaden folgen, die von potenziell schlechteren Kandidaten stammen. Es sollte schlechtere Kandidaten geben, die es schaffen, diese verschiedenen Bereiche der Suche zu erkunden, nicht viele, aber definitiv einige. Wenn Sie bei jedem Entfernen dieses Erkundungsaspekts des Algorithmus nur das Allerbeste nehmen, wird er eher zu einem Bergsteiger. Auch die konstante Auswahl der besten kann zu einer vorzeitigen Konvergenz führen.

Tatsächlich verfolgen Auswahlalgorithmen beide Ansätze. Ein Weg ist, was Sie vorgeschlagen haben, und der andere ist, dass Personen mit höherer Fitness ausgewählt werden und solche mit niedrigerer Fitness nicht.

Der Ansatz, den Sie zur Auswahl auswählen, ist auch auf das Problem zugeschnitten, das Sie modellieren möchten. In einem Experiment in der Schule versuchten wir, Kartenspieler zu entwickeln, indem wir sie gegeneinander spielen ließen (dh Turnierauswahl ). In einem solchen Szenario könnten wir einfach immer gegenüber favorisieren (aus Ihrem Beispiel), da der Aspekt „Glück“ bereits im Spiel selbst enthalten ist. Selbst wenn für zwei beliebige und in einer bestimmten Runde wäre, hätte die Runde gewinnen können und wir könnten$I$$J$$F(i) > F(j)$$I$$J$$J$$F(j) > F(i)$. Denken Sie daran, dass eine Bevölkerung oft groß genug ist, um einige gute Individuen zu verlieren, und im Großen und Ganzen wird es nicht so wichtig sein.

Da GAs anhand der realen Evolution modelliert werden, werden sie bei der Verwendung probabilistischer Verteilungen hauptsächlich danach modelliert, wie sich reale Gemeinschaften entwickeln, in denen manchmal Personen mit geringerer Fitness überleben können, während Personen mit höherer Fitness dies möglicherweise nicht tun (eine grobe Analogie: Autounfälle, natürlich) Katastrophen etc. :-)).

Es ist ganz einfach: Manchmal können "Kind" -Lösungen mit höherer Fitness aus "Eltern" -Lösungen mit niedrigerer Fitness durch Überkreuzen oder Mutation entstehen (das ist eigentlich ein Großteil der Theorie genetischer Algorithmen). Im Allgemeinen möchte man die Lösungen mit höherer Fitness suchen / tragen, aber eine zu große Betonung auf das Halten / Züchten von Lösungen mit hoher Fitness kann dazu führen, dass die lokalen Minima nicht eingehalten werden und die große "evolutionäre Landschaft" nicht durchsucht wird. Tatsächlich kann man den "Cutoff für höhere Fitness" für das Überleben so streng oder lasch machen, wie man es wünscht und experimentieren, wie er die Qualität der endgültigen Lösung beeinflusst. Sowohl zu strenge als auch zu lockere Abschneidestrategien führen zu minderwertigen Endlösungen. Natürlich hat all dies eine gewisse Beziehung zur realen biologischen Evolution. es ist mehr "